QBB: Quantization with Binary Bases for LLMs

Authors: adrian  bulat
yassine  ouali
georgios  tzimiropoulos
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 15:19:04

Abstract: Current post-training quantization methods for LLMs compress the weights down to 4-bits, with moderate to low degradation in accuracy. However, further reducing the number of bits or accelerating the network while avoiding large accuracy drops, especially for smaller, sub 7B models, remains an actively researched and open problem. To address this, in this work, we introduce Quantization with Binary Bases (QBB), a new approach for low-bit quantization that effectively removes (nearly) all multiplications, reducing the implementation to summations. Our novel approach works by decomposing the original weights into a set of binary (1-bit) matrices using an iterative process. For a given layer, starting from a weight matrix, we first construct an initial approximation using an analytical solution, where each new binary matrix, paired with a scaling vector, approximates the residual error of the previous estimation. Secondly, using gradient descent and a progressive learning curriculum, we find the optimal set of binary matrices and scaling vectors that minimize the $\ell_2$ distance between the produced approximation and original weights. Thirdly, as previous steps are input agnostic, we holistically optimize the scaling vectors alone, calibrating them in student-teacher fashion, with the teacher providing both the data, 
 by autoregressive generation starting from a random token, and the target logits.
 When evaluated across multiple LLM families, our approach matches and outperforms all prior works, setting a new state-of-the-art result using a summation-only based approach.

Main paper: 
 introduction: 
 Large Language Models (LLMs) demonstrated proficiency in natural language understanding and generation across multiple domains, exhibiting strong in-context learning abilities [3; 52; 53] . This remarkable performance can be in part attributed to the ever-increasing model and dataset sizes [25; 9] , with the current generation of models being trained on Trillion-sized (tokens) datasets [53] , using Billions of parameters [53; 24; 29] . This, in turn, made deploying such models, even on consumer-grade GPUs, problematic. A promising and flexible direction that disentangles the training and the deployment process, while being hardware friendly, is given by post-training and/or datafree quantization [16; 32; 48] . Within this area, current methods have successfully achieved 4× compression (i.e. 4-bit quantization) with small drops in accuracy [16; 7; 32] , especially for larger (7B+) models. However, compressing the model further and/or applying said methods to smaller models yields unsatisfactory results [16; 32] . Importantly, on the inference side, this class of PTQ approaches replaces 16b multiplications with mixed-precision (i.e., 16b-4b) ones, which have limited hardware support and rely on software-based solutions. Our aim is to alleviate these limitations, enabling higher compression rates while removing (nearly) all multiplications.To this end, departing from prior work, we focus on the most extreme case of quantization, that of binarization (which, as we will show, enables us to remove costly multiplications). As binarizing the weights directly, without retraining, results in unsatisfactory performance, we propose to approximate the weights W using a set of binary matrices B i , i ∈ {1, ..., N } with corresponding fp16 scaling vectors α i . The main case of interest studied is that of N = 4. We note that binarising the weights is a particularly interesting case as the matrix multiplications can be implemented using masked selection/data loading and summations, removing all the multiplications, but 1, that with the scaling vector.As binarising the weights directly is suboptimal (see Sec. 4), we introduce a new iterative approach for estimating the optimal binary matrices B i and scaling vectors α i : Firstly, for a given weight W belonging to the l-th layer, we construct an initial approximation using an analytical solution, whereby each new additional binary matrix approximates the residual error of the previous estimation(s). Secondly, using gradient descent, we iteratively adjust the binary weights and scaling vectors one by one by minimizing the ℓ 2 norm between the target weights and the produced estimation. As until now the process is agnostic to the input distribution of the data, we plug the approximated weights back into the model, optimizing in the interest of speed and generalizability the scaling vectors only. This step uses a teacher-student approach and does not require any training dataset. Instead, we generate synthetic data starting from random tokens by adapting [38] to be more sample efficient. Note that this bypasses the need for any real data. Our approach matches and outperforms prior 4-bit quantization methods across a wide variety of LLMs models (e.g: LLaMA-2, Phi-2, etc.) while removing all multiplication (except the final one with the scaling vector), being fast to calibrate and being amenable, in certain conditions to higher compression rates (see Sec. 4.6) , setting a new state-of-the-art result.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] . Justification: The contributions presented in the introduction and abstract align with the method described in Section 3. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 LLMs quantization is a particular application of network quantization [18; 8; 22; 42; 56] to LLMs. As for the former, broadly speaking, these methods can be split into two categories: Quantization-Aware Training (QAT) -which requires retraining or training in quantized form, and Post-Training Quantization (PTQ), which can be applied directly, without additional retraining. As retraining such models, especially without losing generality, is challenging, most of the work focused on PTQ [16; 49; 32; 30] , although a recent line of work tackles the latter too using data-free strategies [38] or parameters efficient fine-tuning [14] . One of the most prominent recent lines of work was the introduction of GPTQ [16] that proposes a one-shot low-bit weight quantization method based on approximate second-order information. Follow-up work improves upon it by considering the outliers [27; 13] , the effect of the activations on the weight quantization performance [32; 30] , by training the quantization parameters [48] or by grouping and reordering the parameters [62] . Methodologically, our approach stands in between PQT and QAT, as we support both layer-wise input agnostic binarization and fast data-free recalibration. In either case, our approach doesn't require a training corpus.Binarization also known as 1-bit quantization, represents the most extreme case of quantization. In this instance, when both operands are binary, the multiplications can be replaced with bitwise operations, while when one is binary and the other real, the multiplications become summations. These desirable properties make binarization a particularly interesting case of quantization. The current base formulation can be traced to [10; 11] , which proposes to binarize the values using the sign function, whose gradient is estimated using a straight-through estimator [2] . Subsequent works primarily focus on training-aware solutions for vision models [46; 33; 34; 5; 4; 15; 58; 64; 63; 26; 6; 40; 35; 61; 45] . For example, Rastegari et al. [46] introduces analytically computed scaling vectors for both the input and the weights, while [4] building on top, proposes to learn them holistically, via backpropagation instead. Liu et al. [34] argues for the use of real-valued down-sampling layers and the use of double skip connections, while [5] replaces ReLU with PReLUs and makes use of two-staged optimization.Many works have also studied network binarization in the context of transformers [1; 44; 36; 37] , focusing on either full retraining or fine-tuning on labeled datasets using mostly smaller models (e.g., BERT, BART). More relevant to our work are the recent attempts to adapt and apply binarization to LLMs [55; 39; 47; 60] . BitNet [55] swaps all linear layers with BitLinear, their 1-bit weight's replacement, which are then trained from scratch. PB-LLM [47] explores the partial binarization of LLMs, in which the salient weights are stored in higher bits, and the rest are binarized, with a fine-tuning step (i.e., a QAT step) to recover the original LLM performance. BitNet b1.58 [39] encodes every weight using three states {-1, 0, 1} instead of two, which are then trained from scratch similar to BitNet [55] . Finally, OneBit [60] proposes a 1-bit QAT method that decomposes the weights into 1-bit weights and two full-precision scaling vectors, which are then fine-tuned with aStep N Step 2Step 1Figure 1 : Binary weights initialization phase: starting from the target weight W, we construct N binary matrices B i and scaling vectors α i analytically. The 1st binary weight and scaling vector are obtained using Eq. 2 while the subsequent ones use Eq. 3.Step 1Step N Figure 2 : Iterative weights binarization: Starting from the weights initialized as shown in Fig. 1 , we update the binary weights one-by-one, where at each step i ∈ {1 . . . N }, only B i is updated by minimizing the loss function in eq. ( 4), while the rest are frozen. Note that all of the scaling vectors α i are updated at every step. distillation loss for a better approximation. However, all these approaches require full retraining or fine-tuning on labeled datasets with a large training overhead. In contrast, our approach is applicable post-training, doesn't require any labeled (nor unlabeled) datasets, is fast to optimize, makes use of multiple binary bases, and scales well to billion-sized models.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Please see the section titled "Broader impact and limitations". Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
layer-wise input-agnostic weights binarization: 
 Given a linear layer, represented as f (X, W, b) = X • W + b, with X ∈ R n×cin the input tensor, W ∈ R cin×cout the weight matrix and, optionally, b ∈ R cout the bias term. n represents the number of tokens, c in and c out the number of input, and respectively output channels. Note that we are considering the batch size to be 1 and the bias 0 for brevity, as the formulations are independent of them. Our goal is to then quantize the elements of W with W such that X•W ≈ X• W. Unlike prior works [16; 32] that focus primarily on 3 and 4-bit quantization, herein, we focus on compressing the weights using a set of binary bases, without comprising the model's accuracy and importantly, without requiring any training or calibration dataset(s), enabling in the process a potential implementation based (nearly) solely on summations.For our purposes, let us consider the most extreme case of quantization, that of binarization, whereby the values are represented using 1-bit. In this instance, the real-valued weights W can be approximated as W ≈ W = αB, where B = sign(W) is a binary matrix and α ∈ R cout + a scaling vector. Given a set of real-valued weights that are binarized, following Rastegari et al. [46] , the optimal value for α can be computed analytically as α = 1 cout ∥W ∥ ℓ1,col with ∥W ∥ ℓ1,col as the ℓ 1 -norm computed over the columns of W . Note, that in order to avoid spurious states (i.e. states at which the function is ill-defined -0), the sign function used is defined as: sign(x) = -1, x < 0 1, x ≥ 0 .In essence, this relation tells us that we can find the optimal values for B and α by solely looking at W, i.e. without requiring any training data. The downside is that the quantization errors are very high due to reduced representation power, which completely degrades the model's performance. This is perhaps not surprising, as the number of representable states for one given value drops from 2 16 for 16-bits to 2 4 for 4 bits and, finally, 2 1 for the binary case. This discrepancy is even more noticeable when considering the total number of unique permutations representable on such a weight matrix.To address this, we propose to represent W with a linear combination of N binary matrices:EQUATIONIn this case, finding the optimal values for α i , B i , i ∈ {1, ..., N } can no longer be achieved using the analytical solution of Rastegari et al. [46] . As such, we propose a new iterative optimization approach in which the weights and the scaling vectors are iteratively learned via gradient descent. The exact optimization process requires, however, careful considerations. The gradients of sign(.) are 0 almost everywhere, taking the form of the Dirac Delta function. Hence, to make training possible, in practice they are approximated using a straight-through estimator [2] taking the form of a clipped identity function [46; 11] . These gradients are however noisy with the training prone to oscillations and instabilities: for a value infinitesimally close to 0, there exists a full state transition to either of the extremes, i.e. -1 or +1, for any non-zero gradient, hence any noise, even a machine representation error, can result in large swings. To alleviate this, we study (i) how to initialize the weights and the scales, and (ii) how to stabilize the optimization process.Weights and scale initialization: Given an initial estimation α 1 B 1 computed analytically by directly approximating the weight matrix W as:EQUATIONwe then initialize the subsequent α i , B i , i ∈ {2 . . . N } values by approximating the residual error ∆ i at step i:EQUATIONThis sets the underlying distribution behind each B i matrix to the direction that would minimize the overall quantization error. See Fig. 1 for an illustration.Iterative weights and scales optimization: Starting from the above initialization, we aim to minimize the following loss function:EQUATIONwhere both α i and B i are trainable parameters, with B i maintained in the binary state using the sign function. However, the direct, naïve approach of optimizing all parameters jointly leads to training instability. To alleviate this, we devise an iterative training procedure, akin to block coordinate descent, in which the weights are trained one-by-one. Specifically, and as shown in Fig. 2 , for N binary matrices, we have N training steps. During each training step, only one binary weight is updated, while the rest stay frozen. We note, however, that the scales are trained in all cases. This approach prevents us from concomitantly changing too many binary weights, effectively simplifying the problem at each step to learning a binary correction factor to an existing approximation.Progressive weights quantization: To further simplify the approximation of full-precision weights using binary bases, we follow previous binarization approaches [5; 40] and progressively reduce the gap between full-precision and binary weights. Specifically, instead of directly approximating full-precision weights, we first quantize them to a lower precision using an off-the-shelf method (e.g., 4-bit using GPTQ). Then, we apply the proposed method with these quantized weights as a starting point (i.e. initialization followed by iterative optimization).Until now, our binarization process was input-agnostic, considering only the to-be-binarized weights W on a per-layer basis. However, this does not factor two important aspects: (1) the effect of cumulative errors resulted from imperfect approximations of the previous layer's weights and (2) the effect on the overall model's output objectives, given that a local approximation isn't necessarily the optimal global solution under quantization induced errors.To maintain the generalization properties of the target LLM, instead of making use of downstream datasets, we generate synthetic data using the (full-precision) model itself, following Liu et al. [38] . Specifically, the 1st token is randomly selected, with the model generating the subsequent ones up to a certain length or until the EOS token is encountered. Note that the next token is selected stochastically to increase the diversity of the output sequences.Once the data is generated, we can directly use it to train the model with the standard next-token CE loss. However, as the synthetic data is noisy, forcing these labels into the quantized model is suboptimal. Instead, we directly use the produced logits p T as soft ground truth, effectively performing Knowledge Distillation [20] . In practice, we use the MSE loss between the student (quantized model) and teacher (full precision model) logits, which is analogous to a cross-entropy based distillation at high-temperature [20] . The loss is defined as:EQUATIONwhere V represents the size of the vocabulary and n the number of tokens.By inspecting the per-layer quantization (Sec. 3.1), we notice that different layers within different regions of the model have different quantization errors that are sometimes different by up to an order of magnitude. Hence, training them only with a signal applied at the very end of the model is suboptimal. Thus, we also apply a layer-wise MSE loss between the corresponding features of the teacher and student and the end of every transformer block:EQUATIONwhere f T i,l and f S i,l are the features after the l-th transformer module of the i-th token produced by the teacher, and respectively student (quantized) model.The overall loss is then computed as:EQUATIONwith s 1 and s 2 scaling factors for balancing the two loss terms.It's generally accepted that higher accuracy gaps between the student-teacher pair hinder the learning process, as the student has a difficult job of matching the teacher's output. To alleviate this, herein, we randomly swap parts of the teacher model with blocks from the student model. Effectively, this creates an instant family of models, with a performance situated between that of student and teacher models. The sampling is varied, with increasing difficulty (i.e. fewer blocks swapped) as the training progresses.Efficient Calibration: To improve the efficiency of our calibration process, firstly, we only fine-tune the scaling vectors α i making the training process compute and time efficient, keeping everything else, including the binary weights B i , frozen. Secondly, to speed up the training further and make it more sample-efficient, we propose a simple filtering step of the generated training data. Specifically, we only train on self-generated sequences where the quantized student and full-precision teacher differ the most, instead of directly using all the generated samples as in Liu et al. [38] . This is done by first scoring the generated sequences using Eq. 5, then keeping the top-K samples with the highest student-teacher discrepancy. This reduces the training time without any impact on the final results.4 Ablation studies and analysis Moreover, to validate that binarization is inherently unstable, we first ablate the initialization step. In Fig. 3 we plot, on a layer-by-layer basis, the ℓ 2 quantization error for different weight initialization strategies: random initialization -the weights are sampled from a normal distribution; w/o cascaded initialization -all weights attempt to minimize the global error at initialization; with cascaded initialization -each weight approximates the remaining residual error (Eqs. 2 and 3). We can immediately observe that random initialization results in errors that are an order of magnitude higher. Furthermore, the proposed cascaded initialization results in reconstruction errors that are on average 2× smaller than the direct alternative, that minimizes the global error instead of the residual one, as proposed in our work. Interestingly, there are a few layers (the ones harder to quantize) for which the two are behaving similarly. Such layers tend to have more outliers, which makes the finding of the optimal solution (that minimizes the average reconstruction error), more prone to local minimums. To offer some insights on the binarization process, in Fig. 4 we show the proportion of the weights that change state between initialization and the end of the iterative training process, on a per-layer basis, for each binary base. Interestingly, the first and last binary matrix undergo minimal changes, with typically only 0.01 -0.2% of the weights transitioning to a different state. In comparison, the second, and particularly the third base change approximately 40% and respectively 50% of their bases. Moreover, we can observe that for layer IDs 6 and 8, while the proportion of transitions decreases for the second one, the amount increases for the third, which appears to compensate in order to maintain the same overall proportion of bit flips when aggregated across all bases. These phenomena can be tied to how the initialization is performed: the first binary matrix directly approximates the full precision weights W, hence it is already close to its optimal solution while the last one has to approximates a relatively small residual error, as 3 bases give relative similar results (see Fig. 6 ).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [NA]Answer: [No] Justification: No code was included with the paper at submission time.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
effect of distillation: 
 Knowledge Distillation [20] was shown to improve the performance of smaller models by the virtue of providing guidance either at the feature level [19] or at the output space, by providing (soft) pseudo-labels. Herein, we ablate various design choices, summarizing the results in Tab. 2. In particular, we consider the following options: (1) CE -using directly the synthetic data as hard labels and then calibrating the model using the standard next token prediction Cross-Entropy Loss; (2) KD -Using the soft probabilities provided by the teacher, this is identical to standard Knowledge Distillation [20] ; (3) KD-MSE -Compute a ℓ 2 (MSE) loss between the logits of the student and teacher; (4) KD-MSE with swap -gradually vary the strength of teacher, from weaker to stronger, by randomly swapping some block in the teacher model with ones from the student and then apply the KD-MSE loss. Note that the per-layer feature loss (eq. 6) is used for all cases except (1) CE, i.e. when the teacher model is not utilised. As the results show, the KD-MSE with swap outperforms all other variants. Moreover, for this use case, the KD-MSE variant outperforms the vanilla KD loss. Here, we compare the performance when using the generated data directly, or when filtering is applied.During the calibration step, in order to make the training more sample efficient, we proposed to filter the randomly self-generated data and only keep the sequences with the highest teacherstudent discrepancy as measured by the MSE between their output logits (i.e. Eq. 5). As shown in Fig. 5 , this simple filtering step results in faster convergence for the same amount of training samples (i.e. lower perplexity) compared to directly training on the randomly generated sequences.Figure 6 : Per-layer reconstruction error after the initial layer-by-layer optimization for a Phi-2 model. Notice that the performance is generally stable for N ≥ 3.Throughout this work, we mainly focus on the N = 4 case as it provides an optimal balance between accuracy, compute cost and storage. For clarity and completeness, herein, we explore how the performance varies for different values of N . As a study case, we take the Phi-2 (2.7B) model and plot the initial reconstruction errors, after applying the method described in Sec. 3.1.We do so on a layer-by-layer basis, as this will also reveal wherever certain layers are harder to quantize. Looking at the results shown in Fig. 6 we can make the following observations: (1) There is a notable performance drop and phase transition for N ≤ 2;(2) Perhaps unsurprisingly, not all layers are made equal, with different layers having different approximation errors, and hence exhibiting variable difficulty levels from a quantization point of view; This could be indicative for future quantization efforts; (3) For the layers located in the middle, a pattern emerges, with every block being (nearly) equally hard/easy to quantize. This aligns well with the idea that transformers learn a similar representation across most of their layers, unlike, let's say, a convolutional model; (4) For N = 5, we can observe improvements, especially for the most difficult layers, while the easier one has a similar value as for N = 4. As the results from Fig. 7 updating all weights jointly leads to signigicantly worse results, leading to an average error that is one order of magnitude higher.In line with prior work on binarization [40] , we aim to gradually increase the quantization level, as this simplifies the problem by reducing the apparent difficulty of the target. To this end, in Tab. 3 we measure the impact of progressive quantization and showcase that our approach is amenable to different quantization targets. On one hand, we can observe that attempting to directly quantize the fp16 weights results in degraded performance, on the other, our approach works with target weights produced by different approaches, in this case: QPTQ and OmniQuant. Moreover, we can observe that better int4 weights also translate in better binary bases, with our method incorporating the improved scale and outlier handling from OmniQuant for example.Table 3 : Effect of progressive weight quantization strategies measured using a LLama-2 (7B) model in terms of perplexity on WikiText2.Starting perf: 5.12 5.61 5.58 Ours:7.10 5.49 5.21Current low-bit post-training quantization methods result in implementations that replace the full/half precision multiplications present within a linear layer with ones performed using operators represented on fewer bits, most frequently 16b-4b (activation-weights). When the number of bits for at least one of the operands drops to the most extreme case, i.e., 1-bit, all these multiplications are removed. Depending on the implementation, they become either a masked selection ({0, 1}) or a conditional sign set ({-1, 1}). Herein, we opt in for the former, as depending on the target hardware, it is possible to reduce the number of summations too, by implementing a masked load, given that the binary matrices generally have a sparsity level between 50-80%. Getting back to the core message, by removing all the multiplications inside the linear layer, except for the final one with the scaling vector, the power consumption could be reduced, and on custom hardware, it could translate into a smaller die size and faster execution [51; 50; 31; 57] , as in principle an adder circuit can be implemented using a flip-flop. While different implementation and technological nodes will result in some variations, taking as an example [21] , on a 45nm node, and depending on the bit-width of the activation, an adder consumes 4 -8× less energy compared with a multiplier. While left for future studies, further decreasing the activations too to 1-bit can enable even faster implementations based solely on bit-wise operations [4; 10] . Memory-wise, as we learn a sum of binary bases, certain implementations, although not trivial to construct, can exploit either a left-most significant bit alignment to compress the weights to log 2 (N + 1) bits, as a sum of N binary matrices results in N + 1 states, or can make use of codebooks given the cross-matrix similarities and sparsity levels. All in all, we highlight that such representation, which removes (nearly) all the multiplications, opens the door to important energy savings, which are especially important in a world where the total energy consumption of AI models is expected to reach 85-135 TWh by 2027 [12] (if current trends follow) -this equates to the entire power consumption of the Netherlands. 
results: 
 We compare our approach with the current state-of-the-art for low-bit quantization in terms of perplexity score on the main benchmark for quantization -WikiText2 [41] , focusing mainly on the LLaMA-2 [53] {7, 13, 70}B family of models. However, we also include results for LLaMA [52] {7, 13, 30, 65}B and Phi-2 [23] 2.7B models. This allows us to effectively cover a wide range of model architectures and sizes, from the "smaller", and hence harder to quantize, Phi-2 (2.7B parameters) model to the large 70B LLaMA-2 model.Training details. We implement our method using PyTorch [43] , sourcing the pretrained models from Hugging Face [59] repo, as provided by their respective authors. The evaluation code is based on [17] . During the input-agnostic quantization part, presented in Sec. 3.1 and using a single A100 GPU, we optimize each set of binary matrices and scaling vectors, layer by layer, using the following hyperparameters: Adam optimizer [28] , 15000 iterations, no weight decay, an initial learning rate of 1e -4 decayed to 0 using a cosine scheduler. For the data-free distillation step, presented in Sec. 3.2, we fine-tune the scaling vectors only for 2 epochs using an Adam optimizer, a cosine learning rate scheduler, no weights decay, and an initial learning rate set to 2.5e -4. For added stability, we clip the gradients with a norm higher than 1.Baselines. For weight-only quantization, we compare with the primary baseline which is the vanilla Round-to-nearest (RTN) quantization, in addition to current state-of-the-art methods for both W4A16 (i.e. weights in 4-bits and activations in 16-bits) and W3A16 quantization. Specifically, we consider GPTQ [16] , SpQR [13] , QuIP# [54] , and OmniQuant [48] . Here, we report the results for both per-channel weight quantization and group-wise weight quantization with a group size of 128 (i.e. denoted as g128).Outcome. As the results from Tab. 4 show, our approach matches or outperforms prior PTQ approaches across all model sizes.As our work removes nearly all multiplications, it could improve the energy efficiency of the current generation of AI models, reducing costs while being more environmentally friendly.In terms of limitations, our work builds on top of existing pre-trained LLMs, some trained on closed datasets, hence any potential biases present in the original data, affecting the original models would likely propagate to the quantized models too. Therefore, we recommend caution before deploying such models. Moreover, the benefits and gains mentioned are theoretical, as no custom implementation was constructed. Additional effort may be required to translate the theoretical gains into practice. 
conclusions: 
 In this work, we introduced Quantization with Binary Bases (QBB), a new approach for low-bit quantization that effectively removes (nearly) all multiplications, reducing the implementation to summations. Our new approach decomposes the original weights into a set of binary matrices and scaling vector(s) using an iterative process, whereby starting from an initial approximation obtained using an analytical solution, each new binary matrix and scaling vector is optimized in a progressive manner using gradient descent by minimizing the ℓ 2 distance between the produced approximation and the original weights. Finally, as the previous steps were input agnostic, the scaling factors are optimized holistically, calibrating them in student-teacher fashion, with the teacher providing both the data, by autoregressive generation starting from a random token, and the target logits. When evaluated across multiple LLM families, our approach matches and outperforms all prior works, setting a new state-of-the-art result using a summation-only based approach.NeurIPS Paper ChecklistQuestion: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Yes, they are listed in Section 5.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: No bar plots are provided, however, the process is deterministic, hence subsequent runs should result in very similar outcomes.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: -Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: Please see the Broader Impact section.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: -Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: All prior resources used are appropiately cited.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix:  


Decision: This paper presents a novel approach called "Quantization with Binary Bases (QBB)" for low-bit quantization of large language models (LLMs). The method decomposes original weights into binary matrices, significantly reducing computational complexity by replacing most multiplications with summations. The authors demonstrate that QBB achieves state-of-the-art performance across various LLMs.

Reviewers acknowledged the technical soundness of the approach but raised concerns about its novelty, particularly in relation to existing methods like LQ-Net. They also questioned the paper's claims regarding computational efficiency and the fairness of comparisons with linear quantization methods. Some reviewers suggested additional experiments and comparisons to strengthen the paper's contributions.

In response, the authors provided detailed clarifications and additional comparisons, addressing the reviewers' concerns. Most reviewers agreed that the paper offers a solid contribution to the field, particularly in its innovative application of binary matrices to LLM quantization. Considering the paper's strengths, including its thorough experimentation and practical implications, the AC recommends acceptance.

Reviews: review: paper_summary: paper_summary: This research brings the sum of binary bases to the post-training quantization of the large language models. The authors propose a three-step algorithm. In step1: taking the sign of the full-precision weights and use the norm of the weights as the scalings, step2: adjusting the binary bases using gradient descent, step 3: adjusting scales using teacher-student (knowledge distillation).

Step 1 was initiated in computer vision [49], and step 2 introduced in [36]. Set of binary bases for inference was suggested in [36] and later in LQ-Net. https://arxiv.org/pdf/1807.10029

The full binary base for efficient inference is not novel, authors tried to adapt [36] for post-training of large language models, which necessitates step 3 for a better performance. The paper needs to clarify its connection with [36] and LQNet. I was confused in the middle of reading the paper about the main contribution of the paper. My final judgment is "this paper is an adaptation of existing ideas," but I congratulate the authors on putting considerable effort into bringing it to post-training and large language model context.
strength_weakness: strength_weakness: I doubt that Table 3 fairly shows the strength and the weakness of the method. First explain what W4A16g128 mean. I suppose it means weight quantized to 4 bit fixed point, activation to floating point 16 (half precision or brain float?) or maybe fixed point, g128 referees to the grouping size of the weight quantization for the fixed point representation. 
- SpQR baseline is missing in Table 3. https://arxiv.org/abs/2306.03078
questions: questions: - Did you try your method on the fixed-point activations? if yes please specify, if not please make it clear in the paper.
- Why competing methods are on 4 and 3 bits but yours is 2.3? Is it a mistake or 2.3 is the average bit to be 2<2.3<3. I think it is fair to report your result on W4 and W3 just like the other baselines and then show it on a lower lower average bit.
limitations: limitations: The paper focuses on LLamA models. I would prefer a similar comparison for other mainstream language models as well.
paper_summary: paper_summary: This paper proposed QBB by discomposing the original weights into 4 binary matrics and scaling factor. 
To compensate the error, two techniques are further proposed: 
1. use gradient descent to find the optimal set of binary matrices and scaling vectors
2. use knowledge distillation to optimize the scaling vector only.
strength_weakness: strength_weakness: - The technique of decomposing the weights into several binary matrics is similar to BiLLM [1]. In BiLLM, they proposed residual approximation method, which is just the same to QBB when N=2. And this paper was published on arxiv on Feb. 2024. 

- In the related work, QBB listed the PB-LLM, which is a mixed-precision framework that achieved around 2-bit quantization. However, the experiments in Table3 did not involve it. Additionally, BitDistiller [2] also conducted experiment on 2-bit weight quantization. 

- This paper did not provide the code in supplementary material.

- In QBB, two additional adjustments were conducted to minimize the error, which involves additional training cost. However, I haven't found any experiments w.r.t. training cost. Correct me if I am wrong. 

- From my understanding, the computational cost of QBB is between PTQ and QAT. You should compare with PTQ and QAT method separately. For QAT, LLM-QAT and Bitdistiller should be involved. 

- From line 154 to 157, you proposed progressive weights quantization technique by first quantizing weights to 4-bit and then applying the QBB. There is no additional process between these two procedure. From my point, I think it is useless and uneffective. There is no experiment that can prove that your progressive weights quantization is better than directly quantizing. 

- From Figure 6, when we set the N to 5, it is more stable than 4. Why not just use 5?

- In section 3.2, "Data-free" is not properly used. Because I find that you utilized the generated data by LLM. It is not completely data-free. Please refer to [3].

- Teacher-student swaps can easily cause training collapses, especially for floating-point & low-bit models. I am more curious about any strategies employed  to alleviate this problem. 

[1] https://arxiv.org/pdf/2402.04291 
[2] https://arxiv.org/abs/2402.10631
[3] https://arxiv.org/abs/1906.04721
questions: questions: See weakness.
limitations: limitations: This paper missed some important reference. The experiments part should be put more efforts.
paper_summary: paper_summary: This paper introduces Quantization with Binary Bases (QBB), a novel method designed to reduce the computational complexity of large language models (LLMs) by replacing most multiplications with summations. QBB decomposes original weights into a set of binary (1-bit) matrices through an iterative process, optimizing them to minimize quantization error. Additionally, the quantized model is refined via Knowledge Distillation. Tested across multiple LLM families, QBB demonstrates superior performance compared to existing methods.
strength_weakness: strength_weakness: 1. I believe comparing it with non-uniform quantization methods, such as QuIP#, would enhance this paper, as it does not utilize uniform quantization.
2. Regarding progressive weights quantization, I'm unclear whether starting with a quantized model means that $W$ in Equation 4 represents quantized weights rather than full-precision weights. If so, this approach may not be optimal for the quantization step.
3. For Training details, does each layer need 15000 iterations? Can you provide the details of runtime and overhead?
4. How were the values of $s_1$ and $s_2$ specified in Equation 7?
questions: questions: Please refer to Weakness.
limitations: limitations: Please refer to Weakness.
paper_summary: paper_summary: This paper proposes a PTQ technique which decompose the model weitghs into a set of binary matrices. An interactive binarization process and a progressive model distillation procedure are conducted to reduce the quantization error. The paper claims to set a new SOTA of a summation-only based approach.
strength_weakness: strength_weakness: 1. From the novelty prespective, the proposed binary decomposition method is largely similar to previous nonlinear quantization methods line LQ-Net (https://arxiv.org/pdf/1807.10029 ECCV'18). The similarity and difference between the proposed method and LQ-Net should be discussed and the performance should be compared.
2. The paper claims the achieved model can be efficient by removing all the multiplications. However, I don't believe this can be achieved from the formulation of quantized weights in Equ. (1). Although no multiplication is needed to multiply the binary part B with the activation, the multiplication of scaling factor alpha to the activation is still needed, and can be costly when N is large. In fact, the proposed quantization scheme is effectively an N-bit quantization with non-uniform quantization bins, which theortically shouldn't be more efficient than an N-bit linear quantization with integer weights.
3. Deriving from my second point, the efficiency discussion in Sec 4.6 is not concrete. An estimation on exactly how memory and computation is saved comparing to a regular linear W4A16 quantized model should be provided.
4. The comparison is mainly done against PTQ methods with linear weight quantization, yet the proposed method performs non-linear quantization of the weight and requires several epochs of finetuning. This will result in both higher training cost and inference cost comparing to previous methods, making the comparison results unfair.
questions: questions: 1. Please revise the discussion in Sec 4.6 to provide detailed memory and computation savings comparing to regular linear W4A16 quantized models.
2. Please explain in detail about the quantization configuration of the reported W2.3 quantized model
limitations: limitations: The limitation of the work is adequately addressed.

Comments: title: RE: Further discussion on efficiency
Further discussion on efficiency
comment: We thank the reviewer for considering our rebuttal, and we are glad that the reviewer is satisfied with the first point. We hope to have addressed/clarified your remaining concern below.

The reviewer is correct that the weights for GPTQ/AWQ can be expressed as a summation of binary matrices too, and we also agree with the parallel drawn with [1] Squeezellm; It is indeed fair to state that under such representation, both approaches will be subject to similar reduction in multiplication (i.e. the remaining multiplications are with the activations, post matrix-multiplication). We will revise the text to make this aspect clear. Do please note, that we don't claim to be more efficient than AWQ/GPTQ, but simply, that depending on the HW, a binary matrices views can be a more efficient framework to operate in. We thank you for this, we will make a parallel to [1] in the paper.

Regarding the comparisons, we do believe that the numerical comparisons are fair, as our main comparison is with W4, in which case GPTQ/AWQ is not put at a disadvantage.
I would like to thank the author for the rebuttal. I'm satisfied with the first point. 

However, I'm still confused on how the proposed method is able to "remove nearly all multiplication" comparing to traditional W4A16 scheme. From my understanding, the linear quantized weights, like those in GPTQ and AWQ, can also be represented as a summation of binary matrices, specifically
$$W = \sum_{n=0}^3 2^n B_n,$$
with $B_n$ each being a binary matrix. This is a special case of your quantized weight formulation in Eq. (1), with the scaling factor alpha being exponenets of 2. From my understanding, you do not constrain the value of alpha in your formulation. Therefore, I do not see exactly why you can bring additional efficiency comparing to linear weight quantization.

From my understanding, the proposed method is more comparable with non-linear weight quantization methods like SqueezeLLM [1], which benefits from memory saving, but not computational efficiency. This makes the reported comparisons with previous linear quantization methods like GPTQ and AWQ unfair.

[1] Kim, Sehoon, et al. "Squeezellm: Dense-and-sparse quantization." arXiv preprint arXiv:2306.07629 (2023).