QuIP: 2-Bit Quantization of Large Language Models With Guarantees
Authors: Jerry Chee
Yaohui Cai
Volodymyr Kuleshov
Christopher De Sa
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Quantization
Large Language Models
Adaptive Rounding
Theoretical Guarantees
TL;DR: Our method QuIP yield the first viable LLM quantization at 2 bits per weight, and comes with guarantees.

Abstract: This work studies post-training parameter quantization in large language models (LLMs). We introduce quantization with incoherence processing (QuIP), a new method based on the insight that quantization benefits from incoherent weight and Hessian matrices, i.e., from the weights being even in magnitude and the directions in which it is important to round them accurately being unaligned with the coordinate axes. QuIP consists of two steps: (1) an adaptive rounding procedure minimizing a quadratic proxy objective; (2) efficient pre- and post-processing that ensures weight and Hessian incoherence via multiplication by random orthogonal matrices. We complement QuIP with the first theoretical analysis for an LLM-scale quantization algorithm, and show that our theory also applies to an existing method, OPTQ. Empirically, we find that our incoherence preprocessing improves several existing quantization algorithms and yields the first LLM quantization methods that produce viable results using only two bits per weight. Our code can be found at https://github.com/Cornell-RelaxML/QuIP.

QulP: 2-Bit Quantization of Large Language Models With Guarantees
Jerry Chee
Yaohui Cai Cornell University yc26328cornel1, edu
Comell University jerrychee@cs. cornell. edu
Volodymyr Kuleshoy Cornell University kuleshoo@ccrnell..
Christopher De Sa Cornell University cdesašcs. cornell..... edu
Abstract
This work studies post-training parameter quantization large language models (LLMs). We introduce quantization with incoherence processing (QulP), new method based on the insight that quantization benefits from incoherent weight and Hessian matrices, i.e., from the weights being even in magnitude and the directions in which is important to round them accurately being unaligned with the coordinate axes. QulP consists of two steps: (1) adaptive rounding procedure minimizing a quadratic proxy objective; (2) efficient pre- and post-prec post-processing that ensures weight and Hessian incoherence via multiplication by random orthogonal matrices. We complement QulP with the first theoretical analysis for an LLM-scale quantization algorithm, and show that theory also applies OPTQ. Empirically, we find that our incoherence preprocessing improves several existing quantization algorithms and yields the first LLM quantization methods that produce viable results using only two bits per weight. Our code can be found at https:: //g: tiighu...... Ctcr//oooelleeelleee
existing method,
Introduction
Large language models (LLMs) have enabled advances in text generation, few-shot learning, reason- ing, protein sequence modeling, and other tasks 30 35). The massive size of these models- often reaching into hundreds of billions of parameters requires sophisticated deployment methods and motivates research into efficient inference algorithms.
This work studies the post-training quantization of LLM parameters way to improve their runtime efficiency [4] 31 33 34). Our key insight is that quantization can be most effective when weight the weights themselves and the directions in which is important to have good rounding accuracy are not too large in any one coordinate. Intuitively, incoherence can be thought of principled form of outlier reduction. which makes it casier to adaptively round the weights to finite set of compressed values. We use this intuition develop theoretically sound two-bit quantization algorithms that scale to LLM-sized models.
and proxy Hessian matrices incoherent-
even in magnitude,
Specifically, introduce quantization with incoherence processing (QulP), by the above insight. QulP consists two steps: (1) an adaptive rounding [20) procedure, which minimizes a quadratic proxy objective ((W) = tr((W W) HWW WWT) of the error between the original weights W and the quantized weights V using an estimate of the Hessian H; (2) efficient pre- and post- processing that ensures that the weight and Hessian matrices are incoherent by multiplying
method motivated
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

them by Kronecker product of random orthogonal matrices. We denote "incoherence processing" as both the pre- and post- processing steps of our procedure. Incoherence processing can be viewed as form of outlier suppression across the weights and the activation space.
We complement method with theoretical analysis- the first for quantization algorithm that scales to LLM-sized models-which analyzes the role of incoherence and shows that our quantization procedure optimal within general class of rounding methods. Interestingly, we find that QulP without incoherence processing yields a more efficient implementation of an earlier algorithm, our paper thus also provides the first theoretical analysis for that method.
OPTQ
g
Empirically. we find that incoherence processing greatly improves the quantization of large models, especially at higher compression rates, and yields the first LLM quantization method that produces viable results using only two bits per weight. For large LLM sizes (>2B parameters), we observe small gaps between 2-bit and 4-bit compression that further decrease with model size, hinting the feasibility of accurate 2-bit inference in LLMs.
Contributions. In summary, this paper makes the following contributions: (1) we propose QulP, quantization method based on the insight that model parameters should ideally be incoherent; (2) we provide a theoretical analysis for broad class of adaptive rounding methods that encompass QulP and OPTQ; (3) we demonstrate that QulP makes wwo-bit LLM compression viable for the first time.
2 Related Work
Adaptive rounding. Nagel et al. 20 are the first to motivate the "adaptive rounding" proxy objective (Eq. ( in a principled way. There are many quantization methods which quantize by optimizing this proxy objective 6 12 14 20 32). Many require further retraining which can be expensive, and are not evaluated on the current largest open LLMs (OPT (35), BLOOM (30).. Lybrand and Saab [5 propose a greedy per-neuron quantization procedure that is similar to ours, except they do not consider arbitrary linear functions of the error correction. Their work bounds the proxy objective, albeit on the first layer only.
Post training quantization in large models. There is growing body of work on PTQ in LLMs such as OPT and BLOOM. The size of these models make it difficult to apply previously developed methods. The majority of these methods make quantization easier by somehow reducing the range of weights or activations, but still use nearest rounding. SmoothQuant B1 rescales between acti- vations and weights to remove outliers from the activations and make quantization overall easier. ZuroQuant (33] proposes a per-layer knowledge distillation method. LLM.int80 [4] decompose matrix multiplications into a majority of bit and minority of 16 bit operations. LUT-GEMM (2 designs kernels to accelerate quantized matrix multiplications. RPTQ (4 reorders activations and quantizes them in groups, reducing the impact of range differences between channels.
OPTQ (Formerly known as GPTQ). OPTQ [8] is based on OBQ 77.. and proposes a novel rounding method that can work on the largest OPT and BLOOM models. The method works iteratively over the weight columns in a fixed order: (1) quantize with nearest rounding and compute the error, (2) update the remaining weights with a scaled error, and (3) repeat.
Other quantization methods. There are other quantization procedures which do not round based on the proxy objective of [20), or are not designed for the largest language models [10 I1] 13
19
28 29)
3 Quantization With Incoherence Processing: Adaptive Rounding Step
This section introduces quantization with incoherence processing (QulP), new method consisting of: (1) an adaptive rounding step: (2) efficient pre- and post-processing that ensures weight and Hessian incoherence. We define and analyze step (1) in this section; the next section focuses step (2).
Following existing state-of aff-the-rrt post-training quantization methods, we round weights lay- by minimizing the "adaptive rounding" proxy objective, as in Nagel et al. 200.
(W) E ((r-W)>>
||
w)x 2] |]]
tr ( N W) HW -W)-
(1)
Here, W E IR mg the original weight matrix for a given linear layer, W E RR are the quantized weights, x E Rº is an input vector drawn uniformly at random from calibration set, and H is the

---

second moment matrix of these vectors, interpreted as a proxy Hessian. Crucially, this formulation lets the quantization be run in parallel across neurons, which is tractable for large language models [8]. For simplicity, we will focus in this section on rounding to the integers; subsequent sections will extend the analysis to finite grids.
3.1 L.I.Q: An Optimal Adaptive Rounding Method
Our strategy is to define family of adaptive rounding methods for optimizing objective ① and then define LDLQ, the optimal method within that class. Our defined methods iteratively perform the following update for k: 1, ....
W₂ Q(W + +WI:(K-1) W1=(k-1))az),
where Wi denotes the k-th column, Wi:(k-1) denotes the first k 1 columns, the subroutine Q denotes either nearest rounding or standard unbiased rounding to the integers (which rounds up or down such that [2)] 2). and 0g E * is some sequence of vectors. This scheme rounds columns one at a time; at each step, it adds a "correction" term that is linear function of the residual from the rounding we have done so far. The final W satisfies the following matrix equation:
W Q(W + (W W)U),
where U is strictly upper-triangular matrix whose columns are the vectors ag and Q acts elementwise. Because U is upper-triangulat W₁ only depends on Wi.(k-1--
we let 17 Q(W + (W - W) - (W + (W W) denote the quantization error of Q, we find that W W = mnU + +1) and we can rewrite objective [ as
tr((W WWW w (U) =(U
How should we specify U, the linear feedback from the quantization error of preceding columns in (2) Equation provides an answer. If we choose U <- Ú such that the LDL.
The LDLQ Method
decomposition H
H (Ū + IID(C + +1",
where (non-negative) diagonal matrix and Ü is upper unit triangular, then the terms (U + I) Eq. (3) cancel. We denote as LDLQ the rounding procedure in Eq. 2 with U <- Ù as the LDL assignment from Eq. We will now see that the LDL assignment of U is in fact optimal.
3.2 Deriving the Optimality of the LDLQ Adaptive Rounding Procedure
In order to reason about optimality, we consider weights which are worst and average-case for the proxy loss. Let A denote rounding method, and let A(W, H) be the resulting quantized weights. Define the worst-case (Lworst) ) and average (Lavg) proxy losses with respect to the input weights as
Cworst (A, H))
sup WERmxn
E tr ((A(W, H)) W)H H) W)?)]
(5)
Covg(A, H) Ew-Umif(o, [tr ((A(W,H)
H)
(6)
Theorem I. LDLQ worst and average-case optimal amongst rounding methods which specify the linear feedback U as a function of H (not of W J, and when rounding to the integers. That is, for all rounding methods A in the class described by Eq. for all positive semi-definite H, and for as either nearest stochastic rounding,
tr(D) Loworst (LDLQ, H) S Lworsh (A, H) and en (r(rDD = Lavy (LDLQ. Q. H) < LLvg((A H),
where D is the matrix from the LDL decomposition of H. and e = f2r nearest, c = 6 for stochastic.
The number rows being quantized m, and each quantization method operates across the entries of each row. For all rounding methods described by Eq. (2) and for all positive semi- definite H, Q as nearest rounding achieves the same worst-case proxy loss as stochastic rounding, but achieves better average proxy loss.
Remarks.
3

---

After incoherence [nigunc(H)))
After incaherence max (W])
-.0
Block k_proj Block o_pro]
Normatzen eigenteignnn
20:1
04-
Block
20-1
02-
da 2/ Before incoherence (W]]
01
ca de Before incoheeence (egg
500
1000
1500
2003
2500
Figure 1: cig(H) from OPT-2.7b.
Figure 2: Max [Waj| before and after incoherence process- ing on OPT-2.7b.
Figure Max [Qiyl before and after incoherence process- ing, with Q the eigenvectors of H on OPT-2.7b.
Moving beyond generic algorithm A within our framework, we consider the common baselines of nearest and stochastic rounding. These methods are represented within our framework by choosing the appropriate Q subroutine, and setting all entries of the linear feedback to zero.
For these baseline methods, their optimality gap LDLQ governed by tr (D) vs. (H). For any non-diagonal H ž 0, LDLQ achieves strictly lower worst and average-case proxy loss because tr (D) < tr tr(H). Let favg (LDLQ, H) < Lavg(B, fr). Across OPT models 125m to 2.7b, Lr (D()) / s 0.65
(Near, Stoch}. Then, Lworst (worstLDLL QLDLQ, H) Lworst (Stoch, H) and
empirically verifying that the gap is not insignificant. See Supplement for full details.
3.3 Incoherence: Optimality with a Spectral Bound
Theorem I gives exact expressions for the proxy loss, albeit with tr (D), which can be difficult reason about. In Figure [ we empirically observe that H is approximately low-rank: we visualize the spectrum of several randomly chosen H from OPT-2.7b, and observe that the spectrum decays rapidly. In fact, across all layers of OPT-125m to 2.7b models, vast majority of H matrices have fewer than a quarter of eigenvalues > 1% of the max eigenvalue; see Supplement [ full details. Given this observation about the low rank of H. can we bound the behavior of LDLQ, and thus tr (D), using the spectrum of H?
We do this building on a variant of the incoherence assumption that is specialized to our case 3 Definition i. We say a symmetric Hessian matrix H R xxnn is p-incoherent if has an eigende- composition = QAQ" such that for all i and j. 1Qall = je Qeyl S pl VT. By extension, we say weight matrix W E Rmx* is j-incoherent if all i and j. W = c. We, S [| / /mn.
Note that "most" X matrices are incoherent with μ ((Vllgg nz) Õ(1) because random orthogonal matrix has entries with squared-magniuue Incoherence in W can be viewed as form of outlier reduction: small bound on the magnitude of its entries means that we do not need to scale it as much make it fit in the finite range representable low-precision numbers. Figures 2 and plot the max absolute weight and hessian eigenvector entries before and after our incoherence processing, on all layers OPT-2.7b. A line with slope=1 drawn for reference. We that W and H are more incoherrent after our incoherence processing is applied. Making H incoherent less intuitive, but its utility motivated by the following lemma.
that concentrate around their mean of 1/n.
Lemma 2] Let H E ROxa be u-incoherent positive semi-definite symmetric matrix and let H H (Ü DÚD I)T be its LDL Cholesky decomposition, where Ú is strictly upper triangular matrix and D is (non-negative) diagonal matrix. Then,
2 tr (D) < tr (H122)²
To the best of our knowledge, this is novel result using incoherence to obtain bound on ir (D) that depends only on the spectrum of H. help interpret this result, we derive explicit proxy losses for plain nearest and stochastic rounding, which will then compare to what LDLQ gets via Lemmal 2

---

Algorithm QulP- Incoherence Pre-Processing
Require: b N, H IR= SPD, original W _R"x" p E R4, a E [0,
I: seeded sample random two-factor orthogonal matrices U E IR and V E R Rexa
2:
+ a mean (diag H))
from OPTQ
4: W <- WD; diag//a///// W)
3: + Vdiag(H)
b applies element-wise
DD-HHD1
P diagonal rescaling
5: W + UWVI; H t- VHVT
b incoherence
6: 8 + p| Vmn; W + 2 +1)
reduced quantization range due to incoherency > rescale W to lie within [0, 2 1]
7: W + clamp(W (W * (2' - 1),0,2--11
8: return W, H,H,7
Algorithm QulP- Incoherence Post-Processing
Require: b E N, H E R
1|mxx, fmxx,,s SE R & Rex (Alg) I: seeded sample random two-factor orthogonal matrices U E IR and V E Ruxn
x SPD, quantized W E [0. 2h
2: W + & ((W/ (2 1)) 2
3: W + WV; H t VV
}> revert incoherence D revert diagonal rescaling
4: return W WD-1
Lemma 3 Let H be symmetric positive definite. In the worst case stochastic rounding achieves worst (Stoch, Hi = fm/4)uz (H). In the average case nearest and stochastic rounding achieve Lavgl (Near, Stoch), H) = (m/c) (H), where e = 12 for nearest, and c 6.for stochastic.
To interpret this result, consider H rank-k with 1² < n. By Cauchy-Schwarz, tr (r(22/2222 < k (H). Combining Lemma 2 with the LDLQ proxy losses of Theorem I and comparing with Lemma
Lwarst (LDLQ, H) < tr
my² 4n
(H122²²
< my²k
tr (H)
tr (H) wworst (Stoch, H)
4n
Lavg (LD(L,H,,
my²
tr ( (=
my²k k
tr (H) < m
tr (H) Lavg (B, H),
en
on
where B E (Near, Stoch), ). and c is as given in Theorem This shows that for sufficiently low-rank H, LDLQ asymptotically better than plain nearest and stochastic rounding by a factor of p² k/n.
Without incoherence: no improvement with a spectral bound. By assuming incoherence, we were able show LDLQ gets asymptotically better bound in terms of just the spectrum of H. We might ask: was the incoherence assumption necessary to gel this result? The following theorem answers this question in the affirmative by showing that without incoherence, the best spectral bound for LDLQ cannot differentiate it from the nearest and stochastic rounding baselines.
Theorem 4 Consider all H with the same spectrum H. For any positive semi-defiitte H, the following holds. On the worst-case loss LDLQ achieves the same error as stochastic rounding,
m woorst (LDLQ, A) = Lworst (Stoch, H) tr (H).
sup
Ns.t. eig( =oigg()
On the average-case loss LDLQ achieves the same error as the corresponding rounding routine. Let B = (Near, Stoch) and c = 12 for nearest, c = 6oror stochastic.
Lavg (LDLQ" H) Lavg (B, H) tr (H).
sup a.t. =ein()
Note that the worst case for comparing LDL.Q against these baselines occurs when H is diagonal, see Thcorem and Lemma Assuming incoherence do is natural way to exclude such cases.
4 Quantization With Incoherence Processing: Incoherence Processing Step
Next, we leverage the above incoherence analysis to introduce incoherence ancoherenceprocessinng the second step of the QulP algorithm. Our strategy will be to pre-process weight and Hessian matrices to ensure
5

---

the favorable incoherence properties outlined above. One straightforward way to make symmetric matrix incoherent conjugate by a uniform random orthogonal matrix: this will result in each of its eigenvectors being a random unit vector, whose entries will concentrate around magnitude n 1/2
Specifically, let U E IR and V | be two random orthogonal matrices. (Let's temporarily ignore how these matrices are generated, or how would efficiently perform inference.) We ensure the weight and Hessian are incoherent with high probability through random orthogonal multiplications t V HHT and W < UWVT. Importantly, this transformation preserves the proxy quadratic form since tr(W (WWW ( = tr(W HW?).
4.1 Incoherence via Efficient Orthogonal Multiplication
If all we wanted to do was to store or transmit the weights of the quantized neural network, the above procedure would introduce no overhead, since we can generate a random orthogonal matrix from a seed moddmmaiig essentially free to store. However, for running inference on a DNN, we need to multiply by the weight matrix W, and here the need to manifest and multiply by n x random orthogonal matrices U, V would be prohibitive.
To handle this, we propose to instead use a distribution over random orthogonal matrices for which multiplication is fast. Let = pq be factorization of n (where p = q = vn), and set U Un @ Un where UL is sampled uniformly from the p p orthogonal matrices and UR is sampled uniformly from the q X q orthogonal matrices. Multiplication of vector E II" by the matrix U can be accomplished by reshaping to p x matrix. multiplying on the left by Uy and the right by UZ-- and then reshaping back: this takes (m((p + q)) = o(n²) operations. Using more than two factors in this way is also possible, but using two suffices to make this preprocessing asymptotically non-dominant.
Lemma 5 Let H be positive remi-definite matrix on R and W matrix on Rm and suppose that m P1 P.... p& and = q1 92 .. [k- Let U1,U2, U2...., UR. V1, V2.2.... Vx be independent random orthogonal matrices on RP:KP: and Ra x respectively. Set U as the Kronecker product U U1 @ U2 8 ..... & Us and V as V Vi s V/2 8 ... @ V& Then VHVT is pgg-incoherent with probability at least 5, and UWVT is pw pw--nncoherent with probability at least 1 - 6, where
Ckn
k/2
2Ckmm
рH //2 log
(1) and pw A log
(1)
8
for some global constants A and C independent of and k.
This lemma means that multiplying by a random matrix in this family suffices to make matrix incoherent with parameter μ only poly-logarithmic in the matrix size. In our experiments we use k- = 2 factors to construct the orthogonal matrices U, V.
Remarks.
4.2 Additional Heuristics
We outline QulP pre- preeeeecesing and post-processing in Algorithms/ I and respectively. In line of Algorithm [ apply the aforementioned fast orthogonal multiplication procedure ensure W and H are incoherent. We also randomly permute entries at the fast matrix multiplication step to prevent any correlation between attention heads from worsening performance. We introduce number of additional heuristic improvements that further improve performance.
Incoherence-Bann Based Heuristics. Line 4 diagonally rescales W and И to minimize E(W) R tr (#t) ||W]| effectively trading off the spectrum of these matrices to find minimum. Moti- vated by the incoherence of W. Line computes the quantization range depending on the spectrum [[W]e, instead of the typical max,,; à [Wayl- Our full QulP procedure is described in Algorithm which contains calls to the pre- and post-processing sub-steps in Algorithms and
Greedy local search. Our basic procedure yields a good initial guess with emrr guarantees. We can further lower the proxy loss by running coordinate descent after LDIQ (but before post-processing), updating the weights in the same order in the initial pass. See Supplement B for full details.

---

Algorithm 3 QulP: Quantization with Incoherence Processing
Require: be N, H E
R x SPD, W E Rmxx Q {Near, Stoch P E R4, a E [0, QulP Incoherence Pre-Procesing
T b, H. 2: = = (U + (U + -
1: W, H, s, - Alg
H.W.p.aj
D LDL decomposition
3: for lark E (1,...... do We c clamp(Q(Wa) + (W- - 0, -1 D QulP Incoherence Post-Processing
> L.D.Q
4: return W 2 b. H. H.W.s,
Extensions and Further Analyses
5.1 OPTQ is Special Case of LDLQ
We prove novel theoretical insight: QulP without incoherence processing (i.e., LDLQ) is equivalent to more efficient version of the OPTQ algorithm. That is, OPTQ falls under our class adaptive rounding procedures with linear feedback, and is within-class optimal.
Theorem 6, OTPQ [8] falls within the class of adaptive rounding procedures with linear feedbackk as described by Eq. 2 and is equivalent to LDLQ in Section 3
Remarks. To the best of our knowledge, this equivalence yields the first theoretical analysis of OPTQ. Even though the two methods are equivalent, LDIQ is more efficient. OPTQ's implementation requires matrix inversion of H, and two Cholesky decompositions. Our implementation of L.L.Q performs no matrix inversion, and only one Cholesky decomposition.
Empirical Verification. The quantized outputs of the OPTQ implementation S are shown to be exactly identical to the outputs of our LDLQ implementation. Synthetic random data was used, with W Uni 1000x1000 Full details can be found in Supplement
C
5.2 A Bound for Rounding to a Finite Grid
10a
In Section we saw that LDLQ (equivalently, OPTQ) is optimal for minimizing the adaptive rounding objective. However, this analysis assumed rounding the integers. In practice, we do not want to round W just to the integers, but instead scale it, shift it, and round a finite subset corresponding to b-bit integer. To do this, the "real" LDLQ algorithm uses a clamp operation to restrict the range of quantized values. Is LDLQ still optimal when this small change is made? It turns out that the answer is no, the following concrete example illustrates.
trw www wy
10a
LDLQ (nearest)
(stoch)
nearest
10a
stoch
LDLQ (nearest, no clamp)
10a
102
10a
matrix size n Figure 4: LDLQ underperforms.
Finite Grid Counterexample. Figure 4 illustrates the behavior of LDLQ and other rounding methods-when restricted via clamping to finite 4-bit grid [0, 15] particular example where H is a (cleverly chosen) small perturbation of (T, + 1nxn e,
e )/n, and W has m 16 and is small perturbation of 1 mxx/22 22. Details of the setup appear in Supplement C The figure shows that clamped LDLQ with nearest rounding is asymptotically worse, and the clamping to the finite grid is what causes to be worse in this case.
Note that in our experiments in practice, OPTQ has been shown soundly beat nearest rounding. This clamping issue does not seem to arise in practice; however, since it is possible we do need to take into account to prove useful end-to-end bounds.
Procedure With a Bound. In order to address the above issues in theory, here we describe a method that acts to restrict the value of [ Wirl, so that the rounded weights will remain inside the grid if W is sufficiently far inside. We do this via the optimization problem with hyperparameter
minimize: tr (HRT R)
over: R unit upper triangular
(7)
subject to: of R" Re; < + Vi (1.....n).
7

---

Our "fixed" algorithm solves this convex problem (e.g. with ADMM), then runs QulP using stochastic rounding and U RR- in place of the LDL decomposition. Observe that for sufficiently large c, this is exactly equivalent to base QulP, since the solution of that optimization problem is given by the LDL. decomposition when the constraint dropped. Doing this (the full algorithm is given in the supplemental) yields the following theorem.
Theorem 7 Suppose that we run Algorithm [ (Supplement) to quantize a matrix W E m by solving the objective (7). Then there exists an assignment of the algorithm's 's hyperparameters and p such that with probability at least 1 - 6, all the quantized weights will be in range (no overflow or need for clipping) and
( ( WW w))) -
(1240 (12500 (B!)E) IWIIE)
In practice, because clamping rarely causes issues, and because of the significant additional compute needed to solve this program, we always just use QulP as described in the previous sections, which is equivalent to setting e large and using nearest rounding.
6 Experiments
Overview, We quantize the OPT (35] family of models (up to 66B parameters) and Llama 70B [27 using various quantization and processing methods. QulP is superior to OPTQ and other baselines across all model sizes and evaluation tasks. Most interestingly, incoherence processing yields excellent performance using little as two bits per weight when paired with any of the quantization methods we consider (including nearest rounding). Two-bit quantization with QuIP is viable at even moderate model sizes (1B parameters), regime where other two-bit quantization methods fail. At the largest model sizes, the difference between 2-bit and 16-bit weight performance becomes small. We compare the throughput of QulP with OPTQ's efficient implementation on language generation and show that it is not much slower. Additional results on the effectiveness of the proxy loss, unbiased rounding, and Algorithm are presented in the Supplement(C C
Setup. The experimental infrastructure is built on top of OPTQ's repository which is implemented in PyTorch [23). We quantize the HuggingFace implementations of the OPT and Llama 2 model families. All models are quantized on a single GPU, with up to 48GB of memory. Our calibration set is the same OPTQ; 128 random 2048 token segments from the C4 dataset (25) consisting of generic text data from crawled websites. Therefore, no task-specific data is viewed when quantizing. Following OPTQ, quantization is performed one Transformer block at time: loaded into GPU mem- ory, the Hessian computed, and then the weights quantized. The current block's 's inputs are then passed through the quantized block produce inputs for the following block. The Hessian is computed from the quantized Transformer up to that point rather than from the full precision model; like OPTQ, we find this improves quantization. Further details on the setup can be found in Supplement C including a description of the computational resources used to perform the experiments.
Methods. We evaluate compositions of several quantization and pre/post processing methods. For quantization methods, we evaluate nearest rounding, LDLQ (or OPTQ), and two variations. LDLQ- RG re-orders the weights based on diag(H ()) to modify the quantization order and adds further greedy updates to the proxy. "Greedy" performs the greedy updates only. We evaluate the baseline preprocessing from OPTQ which adds H <- H + mcan (diag(H)) for numerical stability. We also evaluate our incoherence processing in A Algorithms] I and denoted as "IncP". With this notation QulP = LDLQQ + IncP, and QulP-RG LDLQ-RG + IncP.
Datasets. We evaluate on the following language generation tasks: WikiTex12 17 Penn Treebank (PTB) 16). and C4. We also evaluate zero-shot tasks, including LAMBADA (LAMB) (1), ARC D. PiQA (26), and StoryCloze (SC) [8] See Supplement C for the full set of results.
Easy (ArcE)
Main Results. QulP is the first PTQ procedure to achieve good quantization at two bits per weight, across a variety of LLM sizes and evaluation tasks. In Figure 5 we compare QuIP and OPTQ when quantizing to 2 and 3 bits per weight (4-bit quantization works equally well for both methods); we evaluate OPT models (up to 66B) on PTB, C4, ARC Easy, and LAMBADA. QuIP is superior to OPTQ across the model sizes and evaluation tasks. At three bits, QulP matches the full precision model reasonably well. At two bits and for larger L.MSs (>2B parameters), QulP begins to approach the performance of the full precision model. As model size increases, does the quality of QulP's
8

---

FP16
OPTQ-W3
OPTQ-W2
Qu
QuIP-W2
Perplexity PTB
10"
Perplexity on C4
10*
102
10
Accuracy on LAMB
0.5
Accuracy on
0.5
0.4
0.2
10a1
10P
10a
10a
10
10
params billions
# params in billions
Figure Quantizing OPT models up to 66B parameters. Our method QulP is the first PTQ procedure to achieve good quantization at 2 bits per weight, across variety of model sizes and evaluation tasks.
OPTQ
QulP (Ours)
WBits
Wiki
C44
ArcEf
PIQAT
SC1
Wiki
C4
ArcEf
PiQAt
SCT
16
3.319
5,709
59.72
80.90
79.95
3,319
5,709
59,72
80.90
79.95
4
3.596
5.905
58.96
80.52
79.12
3.531
5.869
59.81
80.47
79.63
3
4.907
7.099
54.38
78.56
77.72
3.853
6.135
59.81
80.25
79.31
2
123.908
70.541
25.34
50.54
51.75
6.326
8.937
54.38
75.08
75.37
Table
Quantizing Llama 2 70B with QulP and OPTQ, and evaluating on language generation and
zeroshot tasks. Our incoherence processing enables step function change in quantization at 2 bits.
Baseline Processing
Incoherence Processing (Ours)
WBits
Wikil
PTB.
C44
ArcEt
LAMB
Wikil
PTB/
C41
ArcE1
LAMB
16
9.56
14.04
11.45
65.40
72.40
9.56
14.04
11.45
65.40
72.40
OPTQ
QulP
4
9.59
14.22
11.56
64.77
72.39
9.60
14.18
11.50
65.32
73.20
3
10.32
15.36
12.23
60.19
68.89
9.79
14.37
11.66
65.28
72.68
2
71.70
88. 19
29.59
42.47
25.77
11.48
17.40
13.55
57.87
65.24
LDLQ-RG
QuTP-RG
4
9,64
14.20
11,56
63.76
71.94
9.66
14.11
11,51
64.86
71.86
3
10.31
15.15
12.15
63.43
69.78
9.75
14.44
11.68
63.51
71.53
2
49.40
73.45
29.12
41.20
26.35
11.68
16.94
13.44
59.51
62.31
Greedy
Greedy
IncP
4
9.69
14,33
11.59
63.09
72.37
9.72
14.23
11.52
65.99
71.71
3
13.63
23.05
16.30
50.51
56.76
9.92
14.45
11.71
63.80
71.38
2
4816.6
3473.81
3183.2
26.30
0.00
11.59
17.39
13.30
58.80
64.47
Near
Near IncP
4
10.77
15.41
13.52
61.28
70.42
9.77
14.16
11.53
64.06
71.41
3
1564.9
1526.2
1808.2
34.47
1.73
9.89
14,49
11.74
64.06
71.41
41547.8
34348.6
24815.7
25.80
0.00
12.04
18.12
14.11
56.36
60.64
Table
Quantizing OPT-30b with various quantization and processing methods, and evaluating on language generation and zeroshot tasks, Our incoherence processing enables step function change quantization bits, across all rounding methods.

---

Wbits Rescale
Incoherence
Rescale+Incoherence
Rnsccale+nncohherneee+- Range
24.30
24.32
24.05
23.89
32.62
42.28
31.32
26.36
Table 3:
Ablating sub-steps of QulP's incoherence processing, Algorithm averaged over WikiTex12, PTB, and C4 for OPT-350m.
[ Perplexities
2-bit quantization. We provide plots on the remaining datasets in Supplement C OPTQ on OPT-66B is documented in their paper.
Note that the dip in
Table I shows the results of quantizing Llama 70B using QulP and OPTQ. Again, QulP achieves good quantization at two bits while OPTQ does not.
Incoherence Processing Ablation. Table 2 shows all combi- nations of quantization and processing methods evaluated on OPT-30B. At lower weight bits, QulP's incoherence processing dramatically improves the performance of all quantization meth- ods, across all evaluation tasks. Remarkably, all quantization methods- nearest-arr viable at two bits with our inco- herence processing, Our modifications in QulP-RG sometimes give an improvement over QulP, but further study required to evaluate these modifications. Figures for OPT- OPT-125M to 13B are Supplement C
Method
Throughput
QulP
81ms
OPTQ
53ms
Table 4:
Average per-token
throughput (batch size 1) when gen- crating sequences of length 128 with OPT-66B
A6000 GPU.
Throughput Comparison. We evaluate the additional overhead of our incoherence processing during model inference by modifying OPTQ's efficient forward pass. OPTQ's implementation contains a quantized-matrix hull-precision-vecto product kernel and was shown to offer speedups over a FP16 baseline. Our incoherence processing additions are performed in PyTorch. Table shows that our QulP implementation is about 1.5x slower than OPTQ.
Further Ablation. QulP's incoherence processing contains several sub-steps. 3 their relative contributions; all are necessary for the full improvement. Table shows that the random permutation step within the fast orthogonal multiplication also significantly reduces perplexity.
Conclusion
This paper introduced quantization with incoherence process- ing (QulP), an algorithm consisting of (1) an optimal adaptive rounding procedure which minimizes quadratic proxy of the weight error, and (2) efficient pre- and post-processing to ensure the incoherence of the weight and Hessian matrices by mul- tiplying them by a Kronecker product of random orthogonal matrices. We showed that QulP quantization is optimal in general class of adaptive rounding methods with linear feed- back; this theoretical analysis is the first for any quantization algorithm that scales to LLM-sized models.
APerplexity from random permute..
Wbits
4
-0.22
3
-9.96
2
-74.2
Table 5: Ablating random permu- tation within fast orthogonal multi- plication. Differences perplexity are averaged over WikiText2, PTB, and C4 for OPT-125m.
Empirically, QulP achieves the first viable two-bit quantization results for LLMs, especially at large model sizes, hinting at the fcasibility of accurate 2-bit inference in LLMs.
Acknowledgements and Disclosure of Funding
This work was partially funded by the National Science Foundation under awards 1GE-1922551, CAREER awards 2046760 and 2145577, by the National Institute of Health under award MIRA R35GM151243, and gift from CISCO.
10

---

References
[1] Michael Boratko, Harshit Padigela, Divyendra Mikkilineni, Pritish Yuvraj, Rajarshi Das, Andrew McCallum, Maria Chang, Achille Fokoue-Nkoutche, Pavan Kapanipathi, Nicholas Mattei, Ryan Musa, Kartik Talamadupula, and Michael Witbrock. A systematic classifica- tion of knowledge, reasoning, and context within the ARC dataset. In Proceedings of the Workshop on Machine Reading for Question Answering. pages 60-70, Melbourne, Australia, 111818551///// 10133//1/11-2660 URL
July 2018. Association for Computational Linguistics. doi: 10. 10.18665500
htttp::/aclaartoology) wrg/////////o....oo N18-2607
[2] Tom Brown, Benjamin Mann, Nick Ryder, Mclanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, and et. al. Language models are few-shot learners. In Conference on Neural Information Processing Systems, 2020.
[3] Christopher De Sa, Kunle Olukotun, and Christopher Ré. Global convergence of stochastic gradient descent for some non-convex matrix problems. In International Conference on Machine Learning. PMLR, 2015.
[4] Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Llm.int80: 8-bit matrix multiplication for transformers at scale. In Conference on Neural Information Processing Systems, 2022.
[5] Zhen Dong, Zhewei Yao, Amir Gholami, Michael W. Mahoney, and Kurt Keutzer. Hawq: Hes- sian aware quantization of neural networks with mixed- preecisie.sioon. In International Conference on Computer Vision, 2019.
[6] Zhen Dong. Zhewei Yao, Daiyaan Arfeen, Amir Gholami, Michael W. Mahoney, and Kurt Keutzer. H2: Hessian aware trace-weighted quantization of neural networks. In Confer- ence Neural Information Processing Systems, 2020.
[7] Elias Frantar, Sidak Pal Sing, and Dan Alistarh. Optimal brain compression: A framework for accurate post-training quantization and pruning. In Conference on Neural Information Processing Systems, 2022.
[8] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Optq: Accurate quan- tization for generative pre-trained transformers. In International Conference on Learning Representations, 2023.
[9] Itay Hubara, Yury Nahshan, Yair Hanani, Ron Banner, and Daniel Soudry. Accurate post training quantization with small calibration sets. In International Conference on Machine Learning. PMLR, 2021.
[10] Yongkweon Jeon, Chungman Lee, Eulrang Cho, and Yeonju Ro. Mr.biq: Post-training non- uniform quantization based on minimizing the reconstruction error. Conference on Computer Vision and Pattern Recognition, 2022.
[11] Yanjing Li, Sheng Xu, Baochang Zhang, Xianbin Cao, Peng Gao, and Guodong Guo. Q-vit: Accurate and fully quantized low-bit vision transformer. In Conference on Neural Information Processing Systems, 2022.
[12] Yuhang Li, Ruihao Gong, Xu Tan, Yang Yang, Peng Hu, Qi Zhang, Fengwei Yu, Wei Wang. and Shi Gu. Brecq: Pushing the limit of post-training quantization by block reconstruction. In International Conference on Learning Representations, 2021.
[13] Yijian Liu, Huanrui Yang, Zhen Dong, Kurt Keutzer, Li Du, and Shanghang Zhang. Noisyquant: Noisy bias-enhanced post-training activation quantization for vision transformers. In Conference on Computer Vision and Pattern Recognition, 2023.
[14] Zhenhua Liu, Yunhe Wang, Kai Han, Wei Zhang, Siwei Ma, and Wen Gao. Post-training quantization for vision transformer. In Conference Neural Information Processing Systems, 2021.
[15] Eric Lybrand and Rayan Saab. greedy algorithm for quantizing neural networks. In Journal of Machine Learning Research, 2021.

---

[16] Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. The Penn Treebank: Annotating predicate argu- ment structure. In Human Language Technology: Proceedings of Workshop held at Plainsboro, New Jersey, March 8-11, 1994, 1994. w.k..attpps//aalantthlloo oog. H94- 1020
[17] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv:1609.07000
2016.
[18] Nasrin Mostafazadch, Nathanael Chambers, Xiaodong He, Devi Parikh, Dhruv Batra, Lucy Vanderwende, Pushmeet Kohli, and James Allen. A corpus and cloze evaluation for deeper understanding of commonsense stories. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, pages 839 849, San Diego, California, June 2016. Association for Computational Linguistics. doi: 10. 115.6////11///-/ 1/N16- 1098. URL htt.hhttss:/// /eatps://aclasee www.aaalanoooooooooooooooooo orgN/111088
[19] Markus Nagel, Mart van Baalen, Tijmen Blankevoort, and Max Welling. Data-free quantization through weight equalization and bias correction. In International Conference on Computer Vision, 2019.
[20] Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort. Up or down? adaptive rounding for post-training quantization. In International Conference on Machine Learning, pages 7197-7206. PMLR, 2020.
[21] Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Ngoc Quan Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. The LAMBADA dataset: Word prediction requiring a broad discourse context. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1525 1534, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/11/11-1144 144.. URL https: www.annollogyoorooo.o.ooooo 1144
[22] Gunho Park, Baeseong Park, Minsub Kim, Sungjae Lee, Jconghoon Kim, Beomseok Kwon, Se Jung Kwon, Byeongwook Kim, Youngjoo Lee, and Dongsoo Lee. Lut-gemm: Quantized matrix multiplication based on luts for efficient inference in large-scale generative language models, arXiv preprint wrXiv:220600955 2023.
[23] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang. Zach Vito,o, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Conference on Neural Information Processing Systems, 2019.
[24] Jain Prateek, Netrapalli Pranceth, and Sanghavi Sujay. Low-rank matrix completion using alternating minimization. Proceedings of the Forty-fifth Anmual ACM STOC, 2013.
[25] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang. Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1 67, 2020. URL http://jmlr. org httppappess///// v2t/:/211///////// -0 074.hmll
[26] Sandeep Tata and Jignesh M Patel. Piga: An algebra for querying protein data sets. In International Conference on Scientific and Statistical Database Management, 2003.
[27] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiao- qing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng
12

---

Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models, 2023.
[28] Peisong Wang, Qiang Chen, Xiangyu He, and Jian Cheng. Towards accurate post-training network quantization via bit-split and stitching. In International Conference on Machine Learning. PMLR, 2020.
[29] Xiuying Wei, Yunchen Zhang, Xiangguo Zhang, Ruihao Gong, Shanghang Zhang, Qi Zhang, Fengwei Yu, and Xianglong Liu. Outlier suppression: Pushing the limit of low-bit transformer language models. In Conference Neural Information Processing Systems, 2022.
[30] BigScience Workshop, :, Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilié, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, and François Yvon et. al. Bloom: A 176--parameter open-access multilingual language model, 2023.
[31] Guangxuan Xiao, Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Accurate and efficient post-training quantization for large language models. arXiv preprint urXiv:2211.104533 2023.
[32] Zhewei Yao, Zhen Dong, Zhangcheng Zheng, Amir Gholami, Jiali Yu, Eric Tan, Leyuan Wang, Qijing Huang, Yida Wang, Michael W. Mahoney, and Kurt Keutzer. Hawq-v3: Dyadic neural network quantization. In International Conference on Machine Learning. PMLR, 2021.
[33] Zhewei Yao, Reza Yazdani Aminabadi, Minjia Zhang, Xiaoxia Wu, Conglong Li, and Yuxiong He. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. In Conference on Neural Information Processing Systems, 2022.
[34] Zhihang Yuan, Lin Niu, Jiawei Liu, Wenyu Liu, Xinggang Wang, Luzhang Shang, Guangyu Sun, Qiang Wu, Jiaxiang Wu, and Bingzhe Wu. Rptq: Reorder-basee post-training quantization for large language models. arXiv preprint arXiv:2304.01003 2023.
[35] Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, Todor Mihaylov, Myle Ott, Sam Shleifer, Kurt Shuster, Daniel Simig, Punit Singh Koura, Anjali Sridhar, Tianlu Wang, and Luke Zettlemoyer. Opt: Open pre-trained transformer language models, 2022.
13

---

A Checklist
A.1 Broader Impacts
Our work pushes the quantization of large language models into the 2 bits per weight regime. Our aim to drive foundational research on theoretical and empirical aspects of quantization. The ultimate goal is to enable more powerful LLMs more efficiently. However work is unaware to what ends those LLMs are used.
A.2 Limitations
The adaptive rounding 3 proxy objective considers each layer in isolation; it remains to be seen what other computationally tractable proxies could improve quantization. For example quantization methods exist which consider interactions between layers, but so far have been too computationally expensive to be applied to the largest open LLMS.
A.3 Experiments, Reproducibility
Our code is included in the Supplement. See the included README for instructions on how to reproduce the various experiments, including random seeds. The code also downloads all datasets used to quantize or evaluate the models.
B
Additional Method Clarifications
B.1 Subsection 4.2 (Incoherence-Based) Heuristies)
Line 4 diagonally rescales W and H to minimize E(W) s tr (H) |W]] effectively trading off the spectrum of these matrices to find minimum. Note to minimize ir (D- || [[D (E H. ( 11?) implies that D, = / /. Motivated by the incoherence of Line computes the quantization range depending on the spectrum [[][F, instead of the typical max.,) v- The parameter p controls the quantization range; we tune it and find that a value 2.4 works well across all our experiments. We use 2.4 consistently across all experiments. Our full QulP procedure is described in Algorithm which contains calls to the pre- and post-processing sub-steps in Algorithms 1 and
B.2 Subsection 4.2 (Greedy Updates)
In this subsection, we describe the "greedy local search" method mentioned in the main body of the paper in more detail. The basic idea is to iterate over coordinates of the weights the same order as the initial quantization method, modifying each weight in turn-but still restricting it to be representable quantized value-so as minimize the proxy loss while keeping the other weights fixed. These greedy updates amount to coordinate descent on the proxy loss, but restricted to the quantization grid. Greedy updates can be performed after any initial quantization method, or as standalone method. When performed after initial quantization method, greedy local search is descent method because the individual weight updates cannot increase the loss, but when performed alone, these greedy updates are not a descent method because the initial point (W = W) is not feasible because it contains unquantized values that off the representable quantization grid. Concretely, greedy update of weight (i.j) to the grid {0, 1, 1,...,2b 26 1} does the following, where f is the proxy loss:
WH + arg
min =E
E(W eeW W.J 2)
(Note that / - W.3 + eve is the result of setting the (i. jhh entry of V.' to 2.) A full pass of greedy updates constitutes van of these updates performed in the same order as LDLQ. This algorithm is very simple, since it is just greedy coordinate descent. In the rest of this subsection, we will give bit more intuition about this method by showing how this greedy algorithm falls within framework of adaptive rounding with linear feedback.
14

---

Algorithm 4 Greedy Updates: A Single Pass
Require: b N, H E R SPD, weights W E mmx" initial guess W
1: W + W
2: U < (H ④ M) ding(H)-1
M is the strictly upper triangular mask b can skip if W W by setting + W
3: V + W - (W ( o diag(()))
4: for E (1....,,)) n) do We t clamp( Quear (V& + (W W, -1)
5: refurn W
An application of greedy local search as a single-pass stand-alone method falls under our Adaptive Rounding with Linear Feedback framework, with the linear feedback set to U = (HoM) diag (H) where M is the strictly upper triangular mask and @ denotes the Hadamard (entrywise) product, we will derive below. For ease of explanation consider single (row) weight vector 1x1x. When looking only at column j. the proxy loss from setting vy to is
fww eejee + ze²)) = (w w) H w)" + 2(2e] - ) ww) ( [ weje,))
+ {ze} e
This is just quadratic function in 2, and its minimum value the grid {0, 1 .... 2 13 will just be its minimum value on R rounded to that grid. To find this minimum over IR, we differentiate minimize, yielding
0 = 26 H(u w) + 26 H(ze w
and solving for 2,
(u weje, - W) T He,
( w) He;
De, o/ Hej
(8)
Since when we use greedy local search stand-alone method, we have not updated dy yet, at this point dhe wej, and so this means that a single step of greedy updates looks like
we, + @ ((we, we, - (u- w) of He,
He₃
for Q referring to nearest rounding with the necessary clamping, Since é w is zero for all entries following the jth one, this is equivalent to
wej +- Q(ue, - (1é w))ee)
where U set as U = (H @ M) diag (H) as above. This shows how this single-pass version of greedy updates fits into adaptive rounding with linear feedback framework.
Analyzing greedy local search as a post- processiin pass is bit more difficult, but we will see that can also be written as something like adaptive rounding with linear feedback. Suppose that we do pass of greedy updates, but our quantized weights start an initial value = already quantized from some previous method (e.g. LDLQ). Returning to have
(8), since we haven' itentttonn updated úy yet, we'll
(10 He
we e He
Now, all the entries of u which come after j are still the ones from wh This means that we can split this up
(w - H 1)5 + ( w). Huthmn
wej
e, He;
where the first part of this comes from the entries which may have already updated during this pass, the second comes from the entries which are still equal to their initial values in úū and the case of wy is handled specially, cancelling with the we, term. We can write this more compactly in matrix form as
(ύ (H O M)e, + (w - wH c M
= wej
e He
15

---

Absolute Fractional Rank
Approximate Fractional Rank
Model
Processing
tr (D)) /tr (H)
Baseline
0.926 (=0.172)
0.112 (#00117)
0.540 (=t0.093)
OPT-125m
Incoherent
0.910 (#0.196)
0.124 (#0..44)
0.534 (#0.094)
Baseline
0.916 (#:0.100)
0.047 (#:0.032)
0.445 (000,100)
OPT-350m
Incoherent
0.908 (#:0.133
0.059 (#:0.62)
0.440 (#00.106)
Baseline
0.541 (#00404)
0.020 (#:0023)
0.399 (#00.177)
OPT-1.3b
Incoherent
0.543 (=0.405)
0.028 (#0.023)
0.393 (#0.189)
Baseline
0.426 (=0.441)
0.019 (#0.015)
0.384 (#0.206)
OPT-2.7b
Incoherent
0.427 (+0.415)
0.018 (+0.025)
0.375 (+0.205)
Table 6: We compute H in each layer of a given model, and compute the following summary statisties. tr (D) /r (Hf) decreases the mode size increases, though the variance also increases. We compute the fraction of nonzero eigenvalues (i.e. absolute), and the fraction of eigenvalues 0.01 max(eig(H)) (i.e. approximate). The fractional rank is k/n for a rank-k matrix H with dimension n. Mean and standard deviations are computed across layers in a model.
where M is the strictly upper triangular mask and @ is elementwise multiplication. This yields final quantization step
(H 3 MT)e; (v w) of He,
Hej
úej + 2 wej (w w)
e Heg
So, more generally, if we define U as above, and set = (W - W)(H @ M diag HH)
we can write single pass of greedy updates in matrix form as
W + @(V + (W - WW)),
which is very close to our rounding with linear feedback form, albeit with the difference that here V in place of W. This is made explicit in the included Greedy Updates Algorithm.
We can use this algorithm both as whole quantization method (by setting W = W) or as post- processing step (by setting W to the output of some other initial quantization algorithm, such as LDLQ). When we do use it as a post-processing step, we typically run multiple passes of greedy updates (e.g. 10 passes): this involves passing the output of the greedy updates algorithm back in as the input guess W to another run of the greedy updates algorithm, and repeating this multiple times.
C Additional Experimental Descriptions and Results
C.1 Subsections 3.2 and 3.3 (Empirical Properties of H Across OPT-125m to 2.7b)
Interpreting the exact proxy loss of LDLQ and nearest rounding by empirically comparing tr (D) vs (H). Theorem gives the average-case proxy loss for LDLQ terms of tr (D), where D from the LDL decomposition of H. Lemma 3 gives the average- case proxy loss for standard nearest rounding in terms of ir (H.. We know that LDLQ is better in practice, but comparing these equations is difficult because we need to reason about ir (D) vs tr (H). Our paper resolves this difficulty by deriving bounds on the proxy loss for L.I.Q in terms of the spectrum of H (with and without incoherence). However we also perform a quick empirical check: if tr (D) < tr (H), then our theory explains the empirical superiority of LDLQ over nearest rounding (at least on these models). Table Glives the ratio tr (D) / tr (ff) across all layers for OPTQ models 125m to 2.7b; the mean value is always less than 0.55, and it falls as the model gets larger.
H is approximately low-rank. Subsection 3.3 plotted the normalized eigenvalues of H from 3 randomly chosen layers OPT-2.7b. Table gives much more evidence that H consistently ap- proximately low-rank. Across each model, we calculate the absolute and approximate fractional rank
16

---

of H across all layers in OPT models 125m to 2.7b (explanations in the caption). The approximate fractional rank decreases as model size increases; for OPT-2.7b the fractional rank 0.02(#0.02).
C.2 Subsection 5.1 Empirical Verification of OPTQ Equivalence)
We share a python script in the supplementary code which empirically verifies that our implementation of L.D.Q produces quantized values exactly matching OPTQ's [ implementation. While we prove the equivalence between LDLQ and OPTQ's respective algorithm statements, empirically comparing ours and Frantar et al. MI's 's's code ensures that the respective implementations sufficiently close to their algorithmic statements. Therefore we can be sure that LDLQ and OPTQ are equivalent their implementation.
C.3 Subsection 5.2 (Empirical Verification of LDLQ/OPTQ Finite Grid Counterexample)
The following code constructs weight matrix W and Hessian matrix H where OPTQ performs worse than nearest when rounding to a finite grid.
import torch def make_ coakeeccouteeeeempllee (n, d, c=0.01):
= torch. ones nn, + torch eye (n)
[n-1inn-]] 1.0
[[0,1: 2
[[1: c
7
H[0,n-1] +=
8
H[n-1,0] +-
H[0,0] +- 4
(c*+2) 0.499 torch. ones (d 0.002 (torch arange (n) % 2)
11 return N,
The intuition behind this counterexample is as follows: want quantize many coordinates in W in such a way that OPTQ excepts there to be a very large error correction to quantize the last entry. However, the finite grid restricts this large error correction. Note that OPTQ behavior with c=0, but here nearest rounding also does poorly. We make small perturbation (c=0.01) make OPTQ round in the wrong direction, but not nearest.
achieve this poor
C.4 Additional Details on the Experimental Setup and Computational Resources
We run experiments on university cluster managed by Slurm workload manager which has GPUs with up to 48GB of memory, though larger GPUs are only required for some methods on larger model sizes. Note we use the LAMBADA OpenAl version. When Greedy updates are used, we perform 10 passes over the weights in the same order as LDLQ and OPTQ, except for 5 passes on OPT-30b and OPT-66b. For the incoherence based quantization range, tune the parameter p and find that value of 2.4 works well across all model sizes and quantization methods. We use this value for all our experiments.
C.5 Section (Main Results on Additional Evaluations)
Figure shows additional results for QuIP and OPTQ on WikiText2, PiQA, and StoryCloze when quantizing to 2 and bits per weight. The insights about our method QulP remain the same after viewing these additional results: QuIP is the first PTQ procedure to achieve good quantization at two bits per weight, across variety of LLM sizes and evaluation tasks. We evaluate on OPT models (up to 30B); 4-bit quantization works equally well for both methods. QulP is superior to OPTQ across model sizes and evaluation tasks here.
On WikiText2 2-bit quantization, note that the trend in perplexity for QulP mirrors the trend in perplexity for OPTQ. We run OPTQ's [ implementation, though they did not report 2-bit results this model size. Because OPTQ equivalent to QulP's quantization sub-procedure, it thus makes sense that worse performance in the quantization sub-procedure could result in worse overall performance. OPTQ increases perplexity when going from OPT-1.3b to OPT-2.7b. QulP's perplexity also increases from OPT-1.33 to OPT-2.7b, and is unusually higher than the adjacent OPT-1.3b and
17

---

FP36
OPTQ-W2
OPTOWW2
QuiPW3
Quik-2
Perplexity on Wikhlext2
Accuracy on StoryCloze
Accuracy PIQA
0.70
0.70
0.85
0.90
0.60
0.50
0.50
10
20P
10
20"
109
10t
10"
209
params in billions
# params in billions
params in billions
Figure 6: Quantizing OPT models up to 66B parameters. Additional evaluation tasks shown here in the Supplement. Our method QulP is the first PTQ procedure to achieve good quantization at 2 bits per weight, across variety of model sizes and evaluation tasks. Note the drop in performance for OPTQ on OPT-66B is documented their paper.
OPT-6.7b models. However QuIP still beats OPTQ in this setting. Our observations about OPTQ and QulP on WikiText2 and OPT-2.7b were consistent across multiple independent runs.
C.6 Section (All Methods, All Model Sizes, All Bit Weights, All Evaluation Tasks)
Tables 7 13 provide results on all combinations of the following: methods, model sizes (OPT 125m- 30b), weights(433.22) and evaluation tasks. Across our extensive array of experiments, we see that incoherence processing always enables step function change in quantization at 2 bits.
Incoherence Processing OPT-30b
QulP
QulP-RG
Greedy+IncP
Near+IneP
W2
W4
W2
W2
W4
W3
Wiki)
9.79
11.48
9.66
11.59
9.77
9.89
12.04
PTB.
14.04
14.18
14.37
17.40
14.11
14.44
16.94
14.23
14.45
17.39
14.16
14.49
18.12
C41
11.45
11.50
11.66
13.55
11.51
11.68
13.44
11.52
11.71
13.30
11.53
11.74
14.11
AreRf
65.40
65.32
65.28
57.87
64.86
63.51
59.51
65.99
63.80
58.80
64.06
64.06
56.36
LAMB1
72.40
73.20
72.68
65.24
71.86
71.53
62.31
71.71
71.38
64.47
71.41
71.41
60.64
PIQAT
78.13
78.45
78.73
75.24
78.51
78.73
76.17
77.86
77.58
75.95
78.24
77.53
75.46
SC
77.28
76.96
76.51
73.39
77.02
77.08
73.01
76.70
76.64
73.33
76.77
75.94
71.93
Baseline Processing
OPT-30b
Full
OPTQ
LDLQ-RG
Greedy
Near
W16
W3
W22
W4
W3
W2
W3
W2
W4
W3
W2
Wikil
10.32
71.70
9.64
10.31
49.40
13.63
4,817
10.77
1.565
41,548
PTB.
14.04
14.22
15.36
88.19
14.20
15.15
73.45
14.33
23.05
3,474
15.41
1.526
34,349
C41
11.45
11.56
12.23
29.59
11.56
12.15
29.12
11.59
16.30
3,183
13.52
1,808
24,816
ArcEt
65.40
64.77
60.19
42.47
63.76
63.43
41.20
63.09
50.51
26.30
61.28
34.47
25.80
LAMBT
72.39
25.77
71.94
00.00
70.42
PIQAT
78.13
78.56
78.02
66.05
78.56
77.80
64.58
78.35
70.46
49.89
56.37
49.56
SC*
77.28
77.53
75.62
63.59
76.89
75.56
63.53
76.45
68.43
48.31
75.24
49.59
48.57
Table 7:
Quantizing OPT-30b with all combinations of quantization and pre-post processing methods,
evaluating language generation and zeroshot tasks. Our incoherence processing enables step function change in quantization at 2 bits, across all rounding methods.
18

---

Incoherence Processing OPT-13b
Full
QulP
QulP-RG
Greedy+IncP
Neur+IneP
W16
W3
W3
W2
W3
W2
Wiki
10.13
10.21
10.5
16.02
10.35
10.69
13.81
10.25
10.61
13.91
10.34
10.59
16.12
PTB.
14.52
14.69
15.05
21.64
14.73
15.20
22.23
14.85
15.11
20.20
14.93
15.27
23.18
C45
12.06
15.19
12.56
17.37
ArdEr
61.78
61.41
59.47
53.91
60.35
61.78
52.86
60.10
59.43
53.79
60.56
59.30
50.00
LAMB1
70.25
72.09
71.10
56.24
69.47
69.07
55.70
70.83
68.43
56.98
68.37
67.86
46.48
PIQAT
76.82
76.17
72.52
76.55
76.22
76.33
76.17
71.87
76.66
70.73
SCT
76.58
75.62
74.92
70.21
75.88
75.75
70.53
75.43
75.62
72.50
74.47
75.43
68.43
Baseline Processing
OPT-13b
Full
OPTQ
LDLQ-RG
Greedy
Near
W16
W4
W3
W4
W3
W4
W3
W22
W4
W3
W22
Wiki
10.13
10.31
11.60
372.68
10.28
11.54
213.75
10.73
13.67
8,370
3,333
186,069
PTB.
14.52
14.91
16.59
344,44
14.85
16.43
220.38
15.25
18.62
7,053
16.40
2.708
121.291
C41
12.06
12.26
13.34
135.48
12.24
13.17
67.48
12.55
14.30
4,316
13.32
2,711
93.834
ArdE
61.78
64.77
60.19
42.47
60.77
58.54
32.07
56.61
51.22
25.38
31.10
25.42
LAMB1
70.25
72.39
68.89
25.77
68.72
65.30
6.58
68.12
59.36
00.02
67.22
00.06
00.00
PIQAT
76.82
56
78.02
66.05
76.28
75.08
$9.09
76.50
73.45
50.98
76.06
53,10
49.62
SCT
76.58
77.53
75.62
76.32
73.52
75.68
72.44
49.40
49.71
48.70
Table 8:
Quantizing OPT-13b with all combinations of quantization and pre-post processing methods,
evaluating on language generation and zeroshot tasks. Our incoherence processing enables step function change in quantization at 2 bits, across all rounding methods.
Incoherence Processing OPT-6.7b
Full
QulP
QuIP-RG
Greedy+IncP
Near=IneP
W16
W4
W3
W2
W4
W3
W2
W4
W3
W2
W4
W3
W2
Wiki,
10.98
11.51
22.33
11.20
11.61
23.75
11.13
11.62
19.06
11.18
11.73
PTB.
15.77
15.93
16.52
31.73
15.99
16.43
45.53
15.88
16.50
35,94
16.06
16.47
27.04
C4)
12.71
12.86
13.30
21.62
12.88
13.39
24.98
12.89
13.27
19.62
12.96
13.37
19.15
AreEt
60.06
59.89
59.60
52.61
59.30
58.21
53.32
59.18
58.25
51.43
59.85
57.62
50.59
LAMB
70.00
65.77
49.91
67.65
54,80
49.49
PIQAT
76.55
76.77
76.33
72.47
76.71
76.33
72.91
76.39
75.46
72.20
76.55
76.71
71.22
SCT
74.47
75.18
73.65
68.43
75.05
73.33
69.51
74.35
73.77
68.94
74.22
74.09
68.75
Baseline Processing
OPT-6.7b
Full
OPTQ
LDLQ-RG
Greedy
Near
W16
W4
W3
W22
W3
W2
W4
W3
W2
W4
W3
W2
Wiki,
11.49
14.87
2,958
12.56
739.9
11.75
39.09
16,298
12.15
6,011
20,780
PTB.
15.77
16.54
22.05
2.521
16.28
18.58
1.109
16.93
66.57
10,708
18.92
5,440
14,217
C41
12.71
13.16
17.13
500.7
12.98
14.34
154.0
13.27
37.13
9,968
14.40
5,225
12,419
ArcEt
60.06
58.84
53.41
31.86
59.18
55.26
33.00
54.63
32.49
26.09
58.75
25.42
25.80
LAMB
68.72
66.18
52.36
01.07
67.46
61.89
01.79
66.19
02.56
00.00
64.53
00.00
00.00
RIQA
76.55
76.01
73.23
55.11
76.77
74.48
54,46
74.48
53.59
51.90
76.28
50.71
49.78
SCT
74.47
73.71
71.42
52.07
74.09
72.37
52.45
72.82
50.99
49.40
73.58
47.87
47.80
Table 9:
Quantizing OPT-6.7b with all combinations of quantization and pre-post processing
methods, evaluating on language generation and zeroshot tasks. Our incoherence processing enables a step function change in quantization 2 bits, across all rounding methods.
19

---

Incoherence Processing OPT-2.7b
QulP
QulP-RG
Greedy+IncP
Near+IneP
W16
W4
W3
W2
W2
W4
Wiki,
12.47
12.39
17.44
2,998
12.58
15.07
1,676
12.68
12.96
155.6
12.79
13.79
28.98
PTB.
17.97
18.42
20.79
63.59
18.43
20.49
42.05
18.34
20.03
46.28
18.43
19.51
39.23
C41
14.34
14.55
15.63
38.07
14.65
15.97
27.89
14.64
15.22
26.84
14.67
15.52
27.34
ArcEi
53.28
52.99
52.36
46.93
52.61
50.93
LAMB1
64.82
66.04
64.99
36.06
64.64
63,46
43.39
64.68
62.95
45.53
65,40
61.05
35.65
POOA
74.76
74,54
73.94
68.06
73.88
73.45
68.28
74.54
73.83
68 28
73.61
73.56
67.85
SCT
71.74
71.80
70.21
66.14
71.55
70.15
64.67
70.85
71.10
65.82
71.16
70.02
63.27
Baseline Processing
OPT-2.7b
OPTQ
LDLQ-RG
Greedy
Near
W16
W4
W3
W3
W2
W4
W2
W4
Wiki,
12.47
12.93
17.09
8,949
12.77
16.47
7.718
12.95
18.92
9,665
16.69
15,685
10,641
PTB.
17.97
19.10
25.36
8,281
19.05
23.94
7,389
19.06
28.75
8,254
32.22
14,532
10,516
C41
14.34
14.99
18.14
4,388
14.85
17.37
2,113
15.01
20.87
5,139
18.75
11,257
9,356
ArcEt
54.34
52.57
50.04
26.94
52.02
48.95
25.76
52.02
43.39
25.46
52.74
26.56
27.19
LAMB1
64.82
62.00
51.43
00.00
64.04
53.25
00.00
63.50
40.75
00.00
59.15
00,00
00.00
PIQAT
74.76
73.88
70.73
48.42
74.54
69.91
49.95
73.61
66.05
50.65
73.83
51.41
50.22
SC1
71.74
70.91
68.56
71.42
67.79
47.17
70.66
48.44
70.59
47.55
Table 10:
Quantizing OPT-2.7b with all combinations of quantization and pre-post processing
methods, evaluating on language generation and zeroshot tasks. Our incoherence processing enables step function change in quantization 2 bits, across all rounding methods.
Incoherence Processing
OPT-1.3b
Full
QuIP
QuIP-RG
Greedy+Ine2 IInP
Near+IncP
W16
W4
W3
W2
W4
W3
W2
W4
W3
W2
W4
W3
W2
WikiL
14.62
14.88
16.21
41.64
16.49
17.76
42.37
16.75
17.11
48.69
16.43
17.83
56.56
PTB.
20.29
20.87
22.76
47.72
21.93
23.25
50.17
23.76
22.19
24.82
C41
16.07
16.38
17.12
29.78
17.53
18.44
31.49
17.60
18.54
34.10
17.74
19.03
45.56
Archtt
50.84
50.72
49.12
41.88
49.54
18.82
41.20
49.66
48.74
41.08
48.61
46.59
38.64
LAMB1
58.92
56.36
52.47
27.81
51.62
48.36
27.27
49.95
48.38
19.21
49.76
51.12
20.20
PIQAT
72.31
71.22
71.11
64.85
71.06
70.24
63.33
71.00
70.35
63 63.66
71.16
69.80
62.51
SCT
70.78
70.08
68.81
63.02
69.00
68.05
63.14
68.49
67.92
62.64
69.13
67.79
58.43
Baseline Processing
OPT-1.3b
Full
OPTQ
LDLQ-RB RG
Greedy
Near
W16
W4
W3
W2
W4
W3
W2
W4
W3
W2
W4
W3
W2
Wiki,
14.62
15.59
21.35
7.856
15.36
20.22
7.739
15.58
22.68
9,786
47.62
12,658
11.690
PTB.
20.29
22.03
30.74
6,858
21.85
30.10
5.368
22.00
35.18
8,441
73.51
14,705
11,690
C4j
16.07
16.96
21.59
4,028
16.70
20.21
2.123
16.96
22.11
5.129
27.20
6,415
8,360
Arelst
50.84
49.33
45.58
25.46
48.95
45.41
26.68
19
42.42
26.01
42. 80
27.82
25.13
LAMB
58.92
57.03
37.32
00.00
41.08
00.02
59.15
00.00
36.91
00.00
PIQAT
72.31
70.73
68.66
49.73
70.40
67.95
52.18
70.67
66.43
50.87
67.74
51.41
49.78
SCT
70.78
70.15
65.18
48.38
70.34
66.45
49.27
70.40
64.48
48.76
59.13
47.87
48.25
Table 11:
Quantizing OPT-1.3b with all combinations of quantization and pre-post processing
methods, evaluating language generation and zeroshot tasks. Our incoherence processing enables a step function change in quantization at 2 bits, across all rounding methods.
20

---

Incoherence Processing OPT-350m
Full
QulP
QulP-RG
Greedy+IncP
Near+IncP
W16
W4
W3
W4
W3
W3
W4
W3
Wiki
22.00
22.5
25.19
672.3
23.57
25.54
418.0
23.14
25.38
239.9
23.41
27.86
1.444
PTB.
31.07
32.57
35.65
744.2
32.46
37.00
587.4
33.10
37.07
301.0
33.32
39.49
1.354
C45
22.59
25.48
320.0
25.50
215.4
25.48
27.41
ArdEr
40.36
39.44
38.13
27.44
39.31
38.47
29.67
39.77
40.24
30.64
38.89
38.76
28.41
LAMB1
46.67
46.89
42.03
01.03
43.04
39.80
04.99
42.44
40.62
06.38
41.47
34.45
00.08
PIQAT
64.80
63.28
50.87
64.25
63.17
64.25
55.01
63.00
52.23
SCT
63.14
62.13
61.55
53.15
61.74
61.23
51.43
62.83
61.62
53.28
62.38
61.49
50.22
Baseline Processing
OPT-350m
Full
OPTQ
LDLQ-RG
Greedy
Near
W16
W4
W3
W4
W3
W2
W4
W3
W4
W3
Wiki
22.00
24.16
33.51
18.687
23.77
31.87
10,446
27.01
137.3
23,952
25.94
64.56
23,668
PTB.
31.07
34.17
47.69
18,161
33.35
44.38
8,508
40.39
153.5
15.176
36.78
87.22
28,881
C41
22.59
24.71
31.26
8,418
24.10
29.86
3,064
27.84
73.59
9,099
26.21
55.15
17.094
ArdE
40.36
38.43
38.38
26.30
39.06
37.42
25.46
38.34
31.06
24.33
38.68
36.11
25.88
LAMB1
46.67
45.60
39.20
00.00
45.26
32.54
00.02
51.45
16.63
00.00
40.66
27.46
00.00
PIQAT
64,80
64.04
63.44
51.25
65.13
61.97
49.67
63.49
55.44
50.60
63.38
60.55
51.58
SCT
63.14
63.78
61.04
47.55
62.57
60.53
48.95
61.36
54.87
48.44
63.02
56.84
48.95
Table 12:
Quantizing OPT-350m with all combinations of quantization and pre-post processing
methods, evaluating on language generation and zeroshot tasks. Our incoherence processing enables step function change in quantization at 2 bits, across all rounding methods.
Incoherence Processing OPT-125m
Full
QulP
QulP-RG
GrePdy+IncP
Near+IneP
W16
W4
W/3
W2
W4
W3
W2
W4
W3
W2
W4
W3
W2
Wiki]
27.66
33.35
34,22
347
31.51
42,94
361.8
30.65
55.54
230.8
31.93
37.57
397.5
PTB.
38.99
40.80
47.34
430.3
43.28
$1.69
414.1
41.96
48.79
250.6
43.08
52.20
441.9
C41
26.56
27.63
30,92
177.4
28.74
33.54
159.0
28.82
31.41
99.01
29.28
35.88
224.0
ArcEt
40.03
38.89
31.99
39.27
38.26
31.36
38.80
37.67
33.21
38.55
37.42
32.91
LAMBT
39.16
33.03
26.37
01.05
33.75
16.96
02.17
37.78
25.34
04.66
35.65
25.21
01.82
PIQAT
61.92
61.64
61.64
54.24
61.64
61.92
55.44
61.10
60.83
56.47
61.43
61.10
53.48
SCT
59.96
60.03
59.20
52.13
59.07
59.26
51.94
60.15
59.52
54.04
59.13
58.88
53.41
Baseline Processing
OPT-122m
Full
OPTQ
LDLQ-RG
Greedy
Near
W16
W4
W3
W4
W3
W2
W4
W3
W2
Wikil
31.44
53.26
4,563
32.29
53,25
3,704
77.80
1,791
3,707
37.14
1,293
5,375
PTB.
38.99
45.31
74.79
4,410
45.56
75.85
3,596
101.1
1,403
4,622
53.93
1,418
4,267
C41
26.56
29.13
42.55
2.260
29.40
41.77
1,820
65.54
809.5
1,897
33.90
836.5
3,665
AreE
40.03
38.51
35.73
28.62
39.02
36.36
27.19
34.05
26.43
27.15
36.66
30.39
26.01
LAMB
39.16
33.69
12.36
00.00
33.26
15.00
00.00
12.25
00.00
00.00
18.22
00.08
00.00
PIQAT
61.92
60.83
59.47
52.23
61.70
59.58
50.05
57.62
49.29
50.49
61.43
55.88
$1.20
SCt
59.96
58.88
56.97
49.78
59.20
$7.03
48.95
50.99
47.55
48.82
59.96
50.03
47.93
Table 13:
Quantizing OPT-125m with all combinations of quantization and pre-post processing
methods, evaluating on language generation and zeroshot tasks. Our incoherence processing enables step function change in quantization at 2 bits, across all rounding methods.
C.7 Section 6 (Evaluating the Effectiveness of the Proxy Objective)
In Table 14 show the proxy loss of the four quantization methods we evaluate, evaluated over OPT models 125m to 2.7b. The proxy is averaged over models proxy losses normalized by their model dimension; we H matrices computed as a result of OPTQ and nearest rounding. We do not conduct any processing in the proxy evaluation; this is an evaluation of the rounding methods only. Trends in the proxy reflect end-to-end results. OPTQ/LDLO. LDLQ-RG, and Greedy are roughly equivalent at 2 bits, and do better than Nearest.
C.8
Section 6 (Evaluating Unbiased Rounding in LDLQQ/OPQ))
Note in our formulation for Adaptive Rounding with Linear feedback, the Q subroutine could be biased, unbiased. It is typical to perform biased rounding in practice; here investigate if there is
21

---

WBits
LDLQ/OPTQ
LDLQ-RG
Greedy
Near
4
104.09
105.23
120.74
301.18
3
529.53
475.25
537.98
1,308.05
2
2,554.89
2,291.02
2,587.17
5,971.69
Weighted average of proxy Loss tr ((W - (W) - -W)? over OPT models 125m to
Table 14:
2.7b. Proxy is averaged over models normalized by their model dimension (768, 1024, 2048, 2560) respectively, to ensure proxy loss is comparable across models of different size. We do not conduct any processing in the proxy evaluation. Trends in the proxy largely reflect end-to-end results: at bits OPTQ, LDLQ-RG, and Greedy are roughly equivalent, and all do better than nearest.
AVERAGE(Pepleexty Unbiased Perplexity Biased) on Wiki, PTB, C4 (L)
Incoherence Processing
Baseline Processing
WBits
125m
350m
1.3b
2.7b
125m
350m
1.3b
2.7b
4
1,23
0.73
0.79
0.19
27.81
5.58
1.62
0.87
13.26
7.79
2.14
4.66
880.4
499.4
28.63
16.23
2,501
18,732
544.8
2,251
241.3
17,945
4,831
3,798
Table 15:
Average perplexity difference (i.e. unbiased biased) for LDLQ/OPTQ on WikiText2,
PTB, and C4. That is, we can run LDLQ with the Q subroutine as stochastic rounding, instead of nearest. The average difference is positive, meaning that unbiased rounding performs worse than biased (i.e. nearest) across OPT models 125m to 2.7b. Note the magnitude of the gap increases at lower bits.
any benefit to switching to unbiased rounding schemes. Table computes the average perplexity difference (i.e. unbiased biased) for LDLQ/OPTQ on WikiText2, PTB, and C4. That is, we run LDLQ with the Q subroutine as stochastic rounding, instead of nearest. The average difference positive (and large for 2 and 3 bits), meaning that unbiased rounding performs worse than biased (i.e. nearest) across OPT models 125m to 2.7b. These results indicate that in practice, we want to stick with biased rounding schemes.
C.9 Section
6 (Evaluating Algorithm Which Accounts for Clamping)
Incoherence Processing (ours)
Baseline Processing
Model
WBits
Wiki
PTB
C4
Wiki
PTB
C4
4
16.54
22.12
17.58
15.43
21.92
16.80
OPT-1.3b
3
18.27
23.96
18.66
20.45
28.86
20.68
2
38.13
51.78
31.09
6,438.75
6,099.27
2,057.71
4
23.19
32.55
23.48
23.71
33.73
24.29
OPT-350m
3
25.54
36.74
25.52
33.01
45.15
30.09
2
286.71
367.26
144.08
8,006.22
7,445.70
2,317.18
32.04
44.56
29.08
32.59
41.95
28.67
025-125m
3
40.66
51.90
32.91
50.73
74.14
41.04
2
1,649.83
240.86
136.55
3,714.11
4,703.76
1,848.7
Table 16:
Quantizing OPT models using Algorithm eevaluaee WikiText2, PTB, and C4. At bits and incoherence processing, we see improvements over LDLQ and LDLQ-RG on OPT-125m and OPT-350m, but diminishing improvements on D.T-1.3b. Due Algorithm 5|s relatively equivalent performance relative to QulP at OPT-1.3b, and due to this algorithm's 's increased computational cost, we decide not user
Table 16 shows results from using Algorithm 5 to quantize OPT models 1 125m to 1.3b, with incoher- ence processing and baseline processing. At bits and incoherence processing, we observe modest improvements over QulP in terms of perplexity on OPT models 125m and 350m. However, at the
22

---

larger OPT-1.3b QulP beats Algorithm 55 2/3 language generation tasks. In addition, Algorithm computationally more work to run. Therefore we decide not to use it.
Another observation: in practice, we don't t seem to encounter constructions of W and that are bad for LDLQQ/PPTO. Therefore this "clamping" issue seems not be issue in practice, especially as model size increases.
D Proofs for Section 3 (Quantization With Incoherence Processing: Adaptive Rounding Step)
Subsection 3.2 (Deriving the Optimality of the LDLQ Adaptive Rounding Procedure)
Theorem
LDLQ worst and average-case optimal amongst rounding methods which specify the linear feedback U as a function of H (not of W J. and when rounding to the integers. That is, for all rounding methods A in the class described by Eq. (2) for all positive semi-definite H, and for Q as either nearest stochastic rounding,
tr D) --oorsa H) S Eworst (A, (A, H) and m tr(()) Lavg (LDLQ, H) CA,g(A,
where D is the matrix from the LDL decomposition of H, and c. 12 for nearest, c 6 for stochastic.
Proof. Let X be the strictly upper triangular matrix associated with the rounding procedure A such that U <- X in Eq. ② Let B = (X 1Ú- I) where Ú is from the LDL decomposition of H
Eq. The proxy loss then,
Ir ((A(W, H) W) H))
Ir + +1X++)-100 DDD( 11
= (nBDB""
(9)
With the LDL assignment of U, we further have that,
tr (nBDB* tr (nDn²))
(10)
First, consider the worst-case loss, Lworst. The goal is to construct particularly bad case where the entries of W are 1/2 + e, and thus when rounding to the integers we will always have error 1/2. Construct weight matrix W E gmxx such that each entry satisfies,
0.5 w.p. 1/2
+0.5 w.p. 1/2
Wi
0.5 + w.p. 1/2
Tkj
-0.5 w.p. 1/2
and the quantization errors m are for each entry { (+1/ -1/2 with equal probability. For m tr (BDB").
this particular W, .A achieves proxy loss Lwrrst (.A, H) E tr (n with as either nearest or stochastic rounding. It follows from the supremum in the definition of wwrrst in Eq. 5 that, Lwonst (A, H) 2 T tr (BDB"). For the LDL assignment of U, the worst
rounding to the integers is 1/2. Therefore, Lworst (LDrt (LDLQ, H) m tr (D), again for Q as either nearest or stochastic rounding. B must be a unit triangular matrix since it is the product of unit triangular matrices. Therefore tr (BDBT) is minimized when B = I, and
case expected quantization
[
4
Lworst (LDLQ, H) & Cworst (A,
Next, consider the average loss, Lavg. where W ~ Uni m| For Q as nearest rounding, the
entries of the quantization error are Unif[= 2. 11. because each entry is independent and uniformly
distributed. It follows that for any entry of E [n]]] |2 z²dr m Therefore, Lavg (A, H) Ew =x [tr (TBDBTT")) ??") of the quantization error 7) are Uni
12 tr (BDB*). For Q as stochastic rounding, the entries 1, 1]. follows that for any entry of 1). E [ = fo x(1
m
I )dr 1 Note that for stochastic rounding, the quantization error will be x with probability (1 |æ]). Therefore, Lavg (A, H) tr (BDBT). Based these same calculations of E [n
6-
23

---

we have that ( H)
tr (D) with Q nearest, and m2 tr (D) with Q as stochastic
12
6
rounding. By the same reasoning on the minimization of tr (BDB"),
Lavg (LDLQ, H) S Lavg(A, H).
Subsection 3.3 (Incoberence: Optimality with a Spectral Bound)
Definition 1 We say symmetric Hessian matrix H E R is p-incoherent if has an eigende-
composition H = QAQ" such that for all i and j. [Qill = ee Qe,l S p/ vn. By extension, we say a weight matrix W E mmxa is p-incoherent if all i and j. [ = e, Wel S p [| htwll///mn /mnn.
Lemma 8. Let H E R be positive semi-definte symmetric matrix, and let .1.... an be sequence of vectors in IR. Consider the recurrence given by En
Rax" and from k 0 to
Ex+1 = (I= age + e
Let f(a1...., an) tr (HE,). Then if H LDL" is the LDL decomposition of H, global minimum of occurs when ag is the kih column of L. and at this minimum, tr (D).
Proof. First observe that at step k Σg will be 0 in all entries (Ek); if min(i.)) > k: This means that changing the last n - entries of ag does not change E (or E) at all. Without loss of generality, set those entries of dg to 0. If A is the matrix whose kth row is ag, this is equivalent saying that A is strictly lower triangular.
Next, let 7 be a random Gaussian sampled from No, /), and consider the recurrence given by zo = 0 IR and
Tk+1 Tg Cgag T Tx + e
It's straightforward to see that Σg = E [
T) But it's also easy to see that the step-k update only
modifies/assigns the leth entry of z. and does based only on earlier entries of æ. Since cf. zv and no later step assigns the k-or-lower entries of r,
In = e Øx41 = 0 - af σx + e = aak In + +
which in vector form yields
(I + A)xn = 17.
In partieular, this immediately implies that
(1+, Σn = (1 - A)-T
and
L = tr (HE.) = tr
(1+ tt H(1 + A) tr (B-THB-))
where B = 1 + A. Differentiating with respect to B in strictly lower triangular direction A (the only direction in which have degress of freedom, since the diagonal of B must be unit) yields
-2tr (B-THBI) (B-THB-'AB-1)
It's not hard to that if H LDITT is the LDL decomposition of H, and BT L, that the gradient is
2r (DAB-))= = 2 (AB-ID)
-2 B-!D).
Since AT is strictly upper triangular, but B B D must be lower triangular, this is 0 so we have minimum. The uniqueness of this minimum (up to assignments of the trianuuri elements of A or B, which have no effect on f) also immediately follows from the recurrence relation. This implies the minimum global. This is what we wanted to show.
Lemma 2 Let H E Rax" be j-imcoherent positive semi-definite symmetric matrix and let H (Ü TTD(U + TTT be its LDDI Cholesky decomposition, where U is strictly upper triangular matrix and D is (non-negative) diagonal matrix. Then,
41
(T) tr (H212) n

---

Proof. By continuity of tr (D) and tr (H it suffices to prove the lemma for positive definite H. First, the closure of positive definite symmetric matrices is the of positive semi-definite symmetric matrices. Second, consider the set of H that are positive definite and satisfy = tr (H 1232 - (D) 2 0, i.e. are non-negative. The closure of this set (i.e. H È 0) must also satisfy that the inequality is non-negative.
Let H QAQ" be the eigendecomposition of H. First, observe that by incoherence,
n²2 tr (11/2)
e 2 =
X 2
(e) @ex)
x
Set
a 2t2
11113)
and consider the recurrence from Lemma
g with
H1/2er
ak
a
Then
Σk+1 1--a-ee H1/2) En (I-0- =22 ekek.
Suppose by way of induction that for some scalar the covariance Σx I aH 1/2, For the base case, this obviously holds since Eu O. At step k,
Σx+1 = (I (I a H aH-1/22 (I-a-1H\eead) eno
= -aH sexel + a aa- exef + exe
3 aHH -
Note that with this assignment,
T E S (a (a H 13H (13)0aaaaaaaa))))a)aaaaaa (1))ex)) = ==a==)))===- aa o'e c $ 1.
So, by induction it follows that
En x 2 br (H1/2) 112
and so
< 42 tr (H1/2 ir H. H-11 n
= _²² tr (H1/2)
tr (HE
But from Lemma g we know that tr (D) is the global minimum of ir (HE,) for any assignment of ag. This immediately gives us the desired result.
Lemma 3 Let H be symmetric positive definite. In the worst case stochastic rounding achieves Lworst Stoch, H) = (m/4) tr (H). In the average case nearest and stochastic rounding achieve Lavg (Near, Stoch), H) (m/c) tr (H), where 12 for nearest, and for stochastic.
Proof. For nearest and stochastic rounding, set the linear feedback U in Eq. to be zero. Stochastic rounding achieves worst-case loss,
Lworst (Stoch, H)
sup We
E fr (n
m tr (H).
(11)
For the average-case proxy loss, recall the computations of [hy] from the proof of Theorem
Lavg (Near, H)
Ew-UUn//lo.1jmm [ir [n]
m
(H)
(12)
12
Lavg (Stoch, H) Eww-Unifff..jxx [tr (n)H,
tr (H).
(13)
25

---

Without incoherence: no improvement with a spectral bound
Theorem 4 Consider all H with the same spectrum as H. For wny positive semi-definite H, the following holds. On the worst-case loss LDLQ achieves the same error as stochastic rounding.
sup
worst (LDLQ, H) -worst (Stoch, H)
m tr (H).
Hs. eig( ( (H)
On the average-case loss LDLQ achieves the same error as the corresponding rounding routine. Let 6 for stochastic.
B (Near, Stoch) and 12 for nearest,
(LDLQ", H) = Lavg (B, H)
171 tr (H).
sup
Hs.t. cig( (r) (
Proof. See Lemma for calculations on the proxy loss for nearest and stochastic rounding.
For LDLQ, will derive lower and upper bounds sup Ha.t. eig( =e) C (LDLQ, H) and sup Hs.t. eig( (H)) Favg (LDLQ, H). and show they are equal. To construct lower bound, con- sider f = TAI where A are the eigenvalues of H. This decomposition is also the LDL decomposition of H. rewritten as / = (U + IUD(U + 1)- follows that ur (D) tr ( for this H. Combine this result with the worst and average-case losses calculated in the proof of Theorem For the worst-case loss from the proof of Theorem > 22
4 tr (H).. The lower bound for the average-case loss H for as stochastic. Now upper bounds derived
is tr (H) for Q as nearest, and
using the preceding calculations in Eq. [II-([3 (3) and using the worst and average-cant case optimality of LDLQ proven in Theorem |
The lower and upper bounds are tight, proving result.
E Proofs for Section 4 (Quantization With Incoherence Processing: Incoherence Processing Step )
Subsection
4.1 (Incoherence via Efficient Orthogonal Multiplication)
Lemma 9 (Theorem 2.4 from Lalley 2 ). There exist constants C and A independent of n such that for any function F from the unit sphere in dimensions to R that is I-Lipschitz relative the Riemannian metric on the sphere,
nd22
P Pz~S, (F(x) Ex-s, (F(x)) 2 S C exp
Lemma 10. Let B E Rmx be a matrix, and let x be a random vector uniformly distributed on the unit sphere in Rd, Then there exist global constants A 0 and C independent of m and such that
A|
C 8
P |Bx| 2
log
S 5,
Proof. Let
|B
F(x)
|BI
Observe that
BTT Bar
VF(x)
|Bx] ||
||B||
and
VF <
Also observe that for æ drawn uniformly from the sphere in dimensions,
E [[F()) S
F())
E
Ba
27
1
B
Vn
26

---

So, applying Lemma
9
|xxl
1
nt²
2t
Cexp
|B|
F
vn
A
we let be
nt²²
5 = Cexp
A
then
A
C
log
t
8
Trivially, then, for some modified global constants A' and C²
A'
log
= t
8
Vrl
This means that
Br
A'
C"
P
log
|B|
i.e.
A' B log
C"
P
|Bx|
S 8
n
This is what we wanted to prove.
Lemma 5 Let be a positive semi-definite matrix RRax and W matrix on Ruxn, and suppose that m P1 P22 ... Pk and n
922 qk- Let U1, U,,,...,U V1, V2,..., VE be independent random orthogonal matrices on RP.XP. and RR x respectively. Set U the Kronecker product & Up and V V Vi @ V2 ..... VR Then V VHVT is jun-incoherent with
U = U1 @ U2 probability at least 8, and UW VT jw--incoheret with probability at least 1 8, where
Ckn? = A/2 log (-8)
h/2
22'kmn
= (1) and pa = A² log
= 5
8
for some global constants A and C' independent of n and k.
Proof. First we will prove what we want to prove about H: then we will prove what we want to prove about W. Let Q be matrix of eigenvectors of H. Observe that since Q is an orthogonal matrix (by the spectral theorem, because H is symmetric), Qe, is unit vector, i.c. [[Qe,]| = Call QE, = y. Also observe that
(U 2 U2 & ... U+) ((e U1) & (c[,U2)
U2)
@ (c) UL)
for some indices ig. Call e,, U, = 25. and observe that the ay are all independent unit random vectors. So,
(U1 & U2 0 Uw))) (a) x2 3
for random unit vectors F1; , Fy and unit vector y. We easily bound this with à applications of Lemma 10 and a union bound, yielding
4 log
(C)²)
C K
P
2 (01
K5,
8
Setting + b yields
P ((1 ((. v))
2 At log
Ckn
5 n
n
and unioning over all the entries of the large orthogonal matrix,
A
Ckn
P max
((U
8 U2 2 8 U.))),
2 log
S 8.
27

---

Next, for W, observe that if we flatten W, then W/ [W|lp is unit vector. Then any entry of the resulting matrix can be written as
(01 T2 X 24 W(M @ U2 @ yk)
where .1...., Fy and yl..... y/ are independent random unit vectors. We can easily bound this with 2k applications of Lemma 10 and union bound, yielding
A log
C'
2h
((x) 22 ................................ & x4 xxx)" y2 00. yx))
2kd,
mn
5
Setting 8 2kmn yields
2Ckmm
2h
8
T x2 Wn
P 8x
@ yx))
log
mn
Treea
and unioning over all the mn entries of the large orthogonal matrix,
2
2Ckmm
max P
@ U2 w
&Weels
V mn
log
S 8.
This is what we wanted to show.
F Proofs for Section 5 (Extensions and Further Analyses)
Subsection 5.1 (OPTQ is Special Case of LDLQ)
Theorem 6. OTPQ [T] falls within the class of adaptive rounding procedures with linear feedback as described by Eq. 2 and is equivalent to LDLQ in Section
Proof. OPTQ works in the following way. After OPTQ has quantized the first f components of the row vector w. it minimizes the proxy loss over the remaining n - t + elements, keeping the first f elements fixed. It then quantizes the /th element using nearest rounding the grid and clamping. It then proceeds to the next column. If we let = à w. this proxy loss that minimizes can be written in block form as
i A1:(t-1 1oft--iHHitt- 1) ((--)) + 2A H1 11,mm + HunHenntenn tmn AT
and its minimum over A.. will occur when
11 (11(1- + Atn Hemm,t
i.e.
Ann = - 11 D). (Him)tm)
Now, suppose that H ÜDÜT is the LDL decomposition of H, where Ú is unit upper triangular and D diagonal. Since Ü upper triangular,
Hum Ütn, Desntton UT ton
Similarly,
H Histt-1)dm U1se-11) 1) Demitnn Unn,ttn-
This means that
At.. = - 1)am (Uen,ten)
Now, the only part of the value of At: which matters is the first entry, since this is the one that's going to be used to make the next quantization decision. But since Ürantto unit upper triangular and so is its inverse, (Uem,.ee))
e Ce, and so
A, Atnei - A1 1),t:et = - -1100-))0 -AÚ - -T)et.
Finally, we quantize the t-th weight
i Q(w, ( W) I)e.).
This update is equivalent to our adaptive rounding with linear feedback procedure in Eq. with U assigned from the LDL decomposition of H.
0
28

---

Subsection 5.2 (A Bound for Rounding to Finite Grid)
Algorithm 5 presents a quantization procedure which theoretically address OPTQ's clamping issue, by incorporating a restriction of [W,; W into objective 7 Note that for simplicity, here we present the explicit case where only two factors are used in each Kronecker product of orthogonal matrices; however, the proof should generalize to any number of factors.
Algorithm 5 "Fixed" Rounding via a Convex Program
Require: W E RR x H R C > 0, >
Require: factorization
P1P2. n. PsP4
draw U1 E I XP1 uniformly from the set of orthogonal matrices using seed seed(U))
draw U2 E R222 uniformly from the set of orthogonal matrices using seed seed (U2)
draw U3 E IRpaxps uniformly from the set of orthogonal matrices using seed seed (U3)
draw U4 E RRaxxps uniformly from the set of orthogonal matrices using seed seed (U4)
W +- (U, & (U3s @ Uq)
H + (U3 U4 H(U3 @ U4)
W 2"-1 W +1)
elementwise
P
W clamp(W, min 0, max 2 -h
1y-1)) 1)) elementwise
use ADMM or some other solver to solve
minimize: ir ()
over: unit upper triangular
subject to: of L Le, < 1 c Vi E nI.
note that when e = oc, oc L- is the factor from the LDL decomposition of H Ú <- T,-l -
for E n. do We- + clamp(Q(Wa + (W 0,
b round with LF
W 0 2-11
2F
W + (UT & WUT OUT)
return W encoded tuple of the integer rounded values, the scale factor and the seeds
Lemma 11. Suppose that for positive definite p-incoherent matrix H E R and sealar c >>> 0, L is the solution the optimization problem
minimize: tr (HT. T.)
over: L unit upper triangular
subject to: c I Ley S 1 + Vi (I....,m..
Then the solution satisfies
2 ir (1112)²
(HL* n. min(1,
Proof. Let 1) E R x be random standard Gaussian variable row vector, let A be matrix, and consider the recurrence relation over E R x given by zy = 0 and
St _ - Aese T + ne,e?"
We first note that since x, is supported only on (1....,t) t), if M denotes the strictly upper triangular mask, this update step is equivalent to
It-1 I ( Me,e + ne,eT.
From here, it's fairly easy to see by induction that
Fx -A M) 4
and so
1n A1 M) 1)
29

---

Or
In =
===
Now, since I + A M is a unit upper triangular matrix, its inverse is also unit upper triangular matrix. If we let = (7 + A @ M) then L is unit upper triangular matrix and
E
I = L"L.
We are going to choose such that I. is feasible solution to our optimization problem and has the desired objective. Next, let En E [z] mz). and observe that
m = (1 (1- Ae,e) T E.-1 (1 AeGe,) + ege.
Let a > 0 be some constant to be set later, and set A = aHH//2 Suppose by way of induction that for some constant 3 > 0 to be set later, De 3 3H -1/2, The base case clearly holds since 2n = For the inductive step,
E, 3 3 (T- aH aH! H- 1/2
( (T-aH(PeeE) + tGee"
-1221/2- 2aBere? t 11 + te,e..
This inductive step will hold if, letting max; of H1
2aB 2 1 + 2 3h
On the other hand,
T L. Le,
E [ }
E (-z,-1Ae; + )
E (--i-1 Ae;) /²] +1
of A +1
= azee 11 12 1/ +
S sa² 1- 122 /2
S s Bee H1 E; +
So the constraint of optimization problem will be satisfied if
a²3h S c.
To satisfy these constraints, set B = max(h, h/c) and a = B-1 Then max(h, h/c)/ max(h, 2 + max(h, h/c) max(h, (1, h/c) h,
and
max(h, h/c) maxxhh, h/c) c.
Also, the objective will bounded by
tr (HLLL) (HE.) $ Bt (H1/2) max(1, -) -) hh tr (H1/2)
Now, applying incoherence to bound h, where H = UAUT is the eigendecomposiiiin of H.
1/222 n1 tr (11
of H Σ (c
n
So this yields whole bound of
2
tr (H1/2)2
(HL"L)) =
n min(1,c)
This is what wanted to show.
30

---

Lemma 12. Suppose that we quantize the row vector w E R 1m using L the solution to the optimization problem
minimize: tr (HL"L)
over: I, unit upper triangular
subject to: o, I. Le S 11 ViE
and
é = Qstoch (w- -w) 1)) where Qstoch denotes elementwise unbiased stochastic rounding. Then for any u R and any 8>0 0
P (w w)ul 2 212221100 L|
log
I 6.
In particular,
P [10 - w)(L= - 1)ea
c
log
2 i
S 6.
Proof. Let 17 be the error of stochastic rounding, and observe that each entry is, conditioned on earlier steps, zero mean and supported on two values that differ by 1. Also observe that
(w (m w) I)) 17.
and so
i 1
and
(exp ((w w) yu) E lexp (nLu)]
From a repeated application of Hoeffding's ' lemma, we get
( [|uul3)
E lexp ((ú w)w)] S exp
Setting u + yu for > O,
n2 [|Lull?)
E lexp ( s exp
And by Markov's inequality,
x2
P (exp (r(1 w)u) exp(>R)) S exp(->?R)
i...
22 [ull?)
P ((1 - w)u 2 R) - exp -RR +
8
Minimizing the right side over yields 4R Lul|
-2 and
(-21²² ||ساا|| -2)
P ((ú - w)u 2 R) S exp
By union bound,
P ([((w- - - 2 R) < 2exp (-2R² ||u||| -2)
Now setting the right side equal 6,
log ) 8.
P (t0 ((- w)ul 2 | |
<
This is what we wanted to show. The second statement follows from the fact that
[I- T)eill = |le Leal( of e; - e Le, of eT L ee te L Le, & 111))+(1+))= =c.
31

---

Lemma 13. Suppose that we quantize the row vector E R 1x using L the solution to the optimization problem
minimize: tr (HL"L)
over: unit upper triangular
subject to el L Le, S c, Vie (1....,,}
and
+ = Qstoc (w (ú ( where Qstnch, denotes elementwise unbiased stochastic rounding. Suppose that for some integer b, 1 I why S 2 22 Then we
4mn
C= 2 log 5
then with probability least 1 8, 5 waj S 2h and
(( - H(O w) < tr (H122)²
pm
4mn
log
4n
Proof. First, from the previous lemmas, if Ue: is the ith eigenvector of H, with eigenvalue ) since
P (Nlef (10 (ílef(w-w)ee w)Ue)}² 2 x 1|
- log
1
2
S 8.
2
8
By the union bound,
2mn 8
Bijj. (10 - 2 A || log
S
And so
2mn
Σ - Σ N ||Ueee11
log
8
i
which simplifies
p tr (w 2 tr (HI.")) T.)
2mn
log
s 8.
2
8
Now applying the other lemma,
m
tr (1122)² log
2mm
P tr ((ύ - (w) -
2
< 8.
2n min(1,c)
And substituting + 6/2,
P tr ((1 H)H H( -) 2
2n min tr (H1/2) log
m
4mn 5
8
2
On the other hand, again by union bound from the previous lemma,
4mn
Bi,js 1o, (5[(0=- w)(L 1)es P
log
2
Setting
4mn
))
c= log
8
yields
8
P (3i.j, |0 (10 w) D)e, 21 S
32

---

And so by another union bound, the probability that
p²m tr ((v - H - w) = 4n tr (1)2)
4mn
log
and
max (e - w) 6.
Des 21
is no less than 1- It's clear that if this second inequality holds, the value we pass in to the stochastic quantizer will be in range, and thus so will the output. This proves what want.
Theorem 14. Suppose that given input matrix with bounded maximum entry magnitude || and we want to quantize it using b bits. Suppose that we first re-scale the entries of w by mapping
2 3 3
Wij
Waj
2
||
+1 -1;
this guarantees that S Wij S 2 2. Then, suppose we quantize using the procedure described in the previous lemma. Finally, we undo the scaling. Then then with probability least 6, all the quantized weights will be in range (no overflow or need for clipping) and
tr
pmm < n222 3)2
tr (12)2)²
log
[4mm
2
Proof. This a straightforward consequence of the previous lemma.
Theorem 15. Suppose that we are given an input matrix with bounded |/=l| and we want to quantize it using bits. Suppose that we first multiply by two-factor orthogonal matrices, and then we re-seale the entries of by mapping
2
Waj
Wij
1 1;
||m||
A2 log (20mn)
man
this guarantees that Wij S 2b -2 2. Then, suppose quantize using the procedure described in the previous lemma. Finally, we undo the scaling and multiplication. Then then with probability at least 1 8, all the quantized weights will be in range (no overflow or need for clipping) and
tr ((D - wi) w)
A²
tr (11122²
1|
[log
12C ))
n
3)2
244 Ur (1122) ||l||
Proof. It is straightforward consequence of Lemma 5 that unioning over the three bounds on the infinity norm of w, the incoherence of H, and the stochastic rounding, with probability least 38,
((w - w)HHi w)²) < n(2b - 3)2
(1)
2 ||0l
log
4mn
2On2
A22
2C'
A log
log
mi
8
Substituting 5 1++8% 8/3,
2 (H2/2)²
12mn
(r ((w w) H(w ww)²) ) <
3)2 Ir
||
log
n(2b
6Cn
2
6Cnn
12 log
log
33

---

And this right side is clearly less than
A4 tr (m-=w)H(d - w)²) I n² 3)2 tr (1122) 2
12Cmn² 6
/|w|| log
This is what we wanted to show.
Theorem 7, Suppose that
Algorithm (Supplement) quantize matrix W E TRmx by solving the objective (7). Then there exists an assignment of the algorithm's 's hyperparameters c and such that with probability at least 1 all the quantized weights will be in range (no overflow or need for clipping) and
-) tr ( (WW - -))) = - (1²00= tr (HL/3)² [W]12
Proof. This follows directly from the previous theorem, which says explicitly what the hyperparame- ter assignments should be.
References for the Appendix
[1] Elias Frantar, Salch Ashkboos, Torsten Hoefler, and Dan Alistarh. Optq: Accurate quantization for generative pre-trained transformers. In Infernational Conference Learning Representations, 2023.
[2] Steve Lalley. Lecture notes on measure-theoretic probability 2. http://galton. http:///galton.ucccaggg. uchicago http:/aallercuurree//////eeeeeee
pdf 2018.
[3] Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort. Up or down? adaptive rounding for post-training quantization. In International Conference on Machine Learning, pages 7197-7206. PMLR, 2020.
34


Reviews:
[{"review_id": "a1k0ONbXcl", "reviewer": "Reviewer_t6VC", "summary": "This paper introduces QuIP, an algorithm for weight quantization in large language models, with theoretical guarantees. The experimental results demonstrate that QuIP achieves nearly lossless performance when using 3-bit quantization for models larger than 3B, and it shows good performance with 2-bit quantization for models larger than 7B.", "questions": "As mentioned in Section 5.1., OPTQ is equivalent to LDLQ in the class of adaptive rounding methods with linear feedback (proof in Supplement E), and thus is a special case of LDLQ in general. Is there any further case study why OPTQ performs worse in general?\n\nIs there any analysis on quantization outliers under QuIP/LDLQ and how would QuIP handle those cases?", "limitations": "We believe that considering activation quantization could lead to further improvements in the future. However, the implementation of QuIP as a weight quantization method has already overcome major obstacles and enabled the deployment of LLMs.\n\nCurrently, there is a lack of realistic experiments to assess the performance, in terms of compute speed. Nevertheless, implementing and optimizing 2/3-bit performance on CUDA would likely be a highly challenging task, and it could be worthwhile to explore this further in a separate research paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "First of all, QuIP is the first post-training quantization algorithm that compresses weights to 2 bits with reasonable loss of performance, significantly pushing the boundary of LLM on-device deployment and making larger LLMs available to ordinary users.\n\nSecond, the paper proposes LDLQ rounding method, which is both worst-case and average-case optimal in a family of adaptive rounding methods, i.e. iterative quantization through each column of weights. The family is carefully selected so that OPTQ (previously known as GPTQ) falls within this family.\n\nThird, solid proof is shown that LDLQ is optimal in its family assuming rounding to integers, while a rigid study, with counterexamples and more careful analysis is conducted in more realistic cases in Section 5.2.", "weaknesses": "The experiments are mostly conducted on OPT, which might not be the most standard model at the time of reviewing. Models like Llama, Falcon and MPT might be more popular LLMs. However, the reviewer understand the paper was submitted months ago and there might be limited time to conduct all the experiments. Also, the main experiments are conducted on decoder-only auto-regressive language models, while there are other models/domains of interest, for example, FastChat-T5 which is encoder-decoder architecture, Vision transformers, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Evaluating on more models.**\nThanks for the feedback; we agree it is important to evaluate our quantization method on additional models. At the suggestion of the reviewers, we conducted additional experiments on LLaMa-2-70b, and share preliminary results below. We will include a fully comprehensive set of LLaMa results in the revision. Encouragingly, the message of our paper remains the same. QuIP is able to successfully quantize down to 2 bits, as evaluated on Lambada and PiQA zeroshot tasks. \n\n| | Lambada Accuracy | PiQA Accuracy |\n| --  | -- | -- |\n| LLaMa-2-70b-chat 2 Bit | 74.02 | 77.48 |\n\n**Clarification on LDLQ vs OPTQ.** \nTo clarify, we show that OPTQ and LDLQ are in fact equivalent methods. We develop a general class of quantization methods (adaptive rounding with linear feedback), which encompasses LDLQ, OPTQ, as well as nearest and stochastic rounding. Within this general class of methods, we show that LDLQ/OPTQ is worst and average-case optimal (Theorem 1). \n\nOne of the main insights of our paper is the benefit of what we call “incoherence processing”. This development greatly improves the performance of all rounding methods at 2 and 3 bits per weight, even nearest rounding. \n\n\n**Outlier analysis.**\nIntuitively, our incoherence processing reduces the prevalence of outliers. When the weight and proxy Hessian matrices are incoherent, the weights themselves and the directions in which it’s important to have good rounding accuracy are not too large in any coordinate. The empirical success of our method indicates the benefit of this outlier reduction. \n\nTheoretically, Definition 1 gives a definition for incoherent weight matrices such that each entry is not too large. Under this incoherence assumption, we show in Lemma 3 that LDLQ can be superior to nearest and/or stochastic rounding, depending on worst or average case settings. Section 5.1 and Lemma 5 show how we can achieve incoherence in practice with high probability, using Kronecker products of random orthogonal matrices.\n\n**Considering activation quantization.**\nWe agree that investigating activation quantization is an exciting direction, albeit out of scope for this paper. \n\n**Evaluating inference speed.**\nThis is a valid point. We have developed a non-optimized implementation including a \n2-bit CUDA kernel and performed initial inference timing results. Based on these results, the additional overhead of the incoherent matrix multiplies do not translate to a significant slowdown. We conducted sequence generation of length 512 on LLaMa-2-70b quantized to 2 bits, with and without our incoherence processing. Our observations so far indicate that loading the weights onto the GPU dominates the inference time, which is not changed by our method. Further optimizations such as tiling the incoherent matrix multiplies are expected to speed up inference. Section 4.1 also demonstrates why the incoherence processing operations are asymptotically non-dominant.\n\n|     | Inference time (s) |\n| -- | ------------------------ |\n| With incoherent matrix multiplies | 416.575 |\n| Without incoherent matrix multiplies | 377.166 |\n\nExperiments conducted on an NVIDIA RTX A6000 GPU.\n\n"}, {"review_id": "ADJbBuvt2r", "reviewer": "Reviewer_Av5n", "summary": "- The authors coin a family of adaptive rounding methods for layer-wise quantization, establish that the state-of-the-art method GPTQ is optimal within this family, and prove quality guarantees.\n- The paper further introduces incoherence preprocessing, together with a Kronecker-factor based inference scheme, which leads to significant accuracy improvements for very low bitwidth compression.", "questions": "- Given that the largest models are usually more robust to quantization, I am wondering how QuiP performs on the 66B and 175B variants, is there any reason why those results are missing?\n- How does QuiP perform with groups, which are generally very effective for standard GPTQ / RTN?\n- 221: GPTQ only requires one inverse + one Cholesky decomposition\n- 282: It would be good to reference that the official GPTQ repository also proposed a similar trick in the context of LLaMa models several months ago.\n- The incoherence post-processing code currently returns a matrix that is not quantized anymore, which is a bit confusing. Related to that, I would also suggest to provide pseudocode for the efficient Kronecker-factor inference scheme.", "limitations": "The paper briefly discusses limitations and broader impact in the Appendix.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a non-obvious and useful optimization to GPTQ which fully eliminates the matrix inversion while obtaining equivalent results.\n- The authors present what seem like the first theoretical guarantees for an adaptive layerwise rounding algorithm.\n- The proposed incoherence preprocessing leads to greatly improved results for 2-bit compression. While the idea of multiplying with an orthogonal matrix to produce more uniform and thus easier to compress data is not new, I have not seen it applied in the context of LLM quantization before.\n- The paper also studies the impact of some additional heuristics, like greedy post-processing passes on top of GPTQ. While those are mostly small tricks, it is good to have those implemented and evaluated.\n- Code is provided for reproducabilty, including also a script to verify the equivalence of their GPTQ optimization.", "weaknesses": "- The method is only evaluated on OPT, which is not considered a great LLM anymore by today's standards; good results on e.g. LLaMa would be significantly stronger.\n- There do not seem to be any runtime numbers for inference via the proposed efficient Kronecker-factored scheme. I think that the tripling of required FLOPs (2 additional o(n^2) matmuls if I understood this part correctly) may be challenging to implement in practice without significant overheads (both for low- and large-batch inference), which would limit the practicality of incoherence preprocessing.\n- The algorithm family seems to be somewhat designed around how GPTQ works and the corresponding optimality is thus not exactly super surprising.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Evaluating on more models.**\nThanks for the feedback; we agree it is important to evaluate our quantization method on additional models. At the suggestion of the reviewers, we conducted additional experiments on LLaMa-2-70b, and share preliminary results below. We will include a fully comprehensive set of LLaMa results in the revision. Encouragingly, the message of our paper remains the same. QuIP is able to successfully quantize down to 2 bits, as evaluated on Lambada and PiQA zeroshot tasks. \n\n| | Lambada Accuracy | PiQA Accuracy |\n| --  | -- | -- |\n| LLaMa-2-70b-chat 2 Bit | 74.02 | 77.48 |\n\n**Evaluating inference speed.**\nThis is a valid point. We have developed a non-optimized implementation including a \n2-bit CUDA kernel and performed initial inference timing results. Based on these results, the additional overhead of the incoherent matrix multiplies do not translate to a significant slowdown. We conducted sequence generation of length 512 on LLaMa-2-70b quantized to 2 bits, with and without our incoherence processing. Our observations so far indicate that loading the weights onto the GPU dominates the inference time, which is not changed by our method. Further optimizations such as tiling the incoherent matrix multiplies are expected to speed up inference. Section 4.1 also demonstrates why the incoherence processing operations are asymptotically non-dominant.\n\n|     | Inference time (s) |\n| -- | ------------------------ |\n| With incoherent matrix multiplies | 416.575 |\n| Without incoherent matrix multiplies | 377.166 |\n\nExperiments conducted on an NVIDIA RTX A6000 GPU.\n\n**The algorithm family is somewhat designed around GPTQ, and therefore its optimality is not super surprising.**\nWe’d like to respectfully push back on this statement. While we believe the LDLQ algorithm formulation and its subsequent in-class optimality proof are intuitive to understand, the equivalence of LDLQ and GPTQ is not intuitive. The GPTQ paper clearly demonstrated its empirical success, but deriving a theoretical proof of optimality based on its method formulation was not clear. Only by showing equivalence to LDLQ could we leverage LDLQ’s optimality to show GPTQ’s in-class optimality, but from looking at their respective formulations this connection is not clear. \n\n**How does QuIP perform on larger OPT models 66B/176B? Why are these missing?**\nDue to time and compute constraints we were unable to submit experiments on larger OPT models. We include some results of our method QuIP on OPT-66b evaluated on language generation tasks, and will include a full set of results on 66B and 176B in the revised paper. Our story on these larger OPT models remains the same: with our incoherence processing we are able to achieve good quantization down to 2 bits. \n\nQuIP on OPT-66b:\n| W Bits | Wiki | PTB | C4 |\n| -------- | ------ | ------ | ---- |\n| 16      | 9.34 | 13.36 | 10.99 |\n| 4        | 9.35 | 13.39 | 11.03 |\n| 3        | 9.45 | 13.55 | 11.17 |\n| 2        | 10.64 | 15.68 | 12.67 |\n\n\n**How does QuIP perform with groups?**\nWe tried groupsize 32 and 128 on the OPT-350m model. At 2 bits, we see there is a modest improvement from using grouping. There are interesting research questions here regarding the effect of groupsize with our method. Theoretically, we would not expect groupsize to help too much since incoherence processing should be making the weights relatively uniform. We do however see some benefit at 2 bits for OPT-350m, and further exploration is warranted on additional models.\n\nQuIP on OPT-350m with various groupsizes:\n| quant method  |     | wiki   | ptb    | c4     |\n| -------- | --- | ------ | ------ | ------ |\n| full     | W16 | 22.00  | 31.07  | 22.59  |\n| quip     | W4  | 22.50  | 32.57  | 23.23  |\n|          | W3  | 25.19  | 35.65  | 25.48  |\n|          | W2  | 672.29 | 744.18 | 320.04 |\n| quip-groupsize 32  | W4  | 23.05  | 32.57  | 23.39  |\n|          | W3  | 25.70  | 36.98  | 25.91  |\n|          | W2  | 197.02 | 244.10 | 133.76 |\n| quip-groupsize 128 | W4  | 23.03  | 32.77  | 23.39  |\n|          | W3  | 25.59  | 36.82  | 25.81  |\n|          | W2  | 192.59 | 220.44 | 128.27 |\n\n\n**Clarify number of matrix inverse / Cholesky in GPTQ.**\nWe realize Algorithm 1 in GPTQ’s paper states only one inverse + one Cholesky decomposition. However, in [GPTQ’s code](https://github.com/IST-DASLab/gptq/blob/2d65066eeb06a5c9ff5184d8cebdf33662c67faf/gptq.py#L101) we can see two calls to `torch.linalg.cholesky(H)`, and one call to `torch.cholesky_inverse(H)`. \n\n**Acknowledge reordering also used in GPTQ.**\nThanks for pointing that out, we will make sure to reference the GPTQ repo.\n\n**Clarify incoherence post-processing, in converting back to float. Suggest psuedocode for Kronecker-factor inference.**\nTo perform a linear layer forward pass in our current implementation, we (given input activations):\n\n\n(1) perform a multiplication by each of the input-side Kronecker factor matrices (2 small matrix-matrix multiplies)\n\n(2) multiply the result by the quantized weights using a specialized kernel that does quantized-matrix-vector multiplies without having to decompress (as in GPTQ)\n\n(3) multiply the result by each of the output-side Kronecker factor matrices.\n\nThis gives a speedup relative to a baseline of offloading the original 16-bit weight matrix to the CPU and loading it to the GPU on-demand, because loading the weights onto the GPU is very expensive due to limited host-device bandwidth. The additional Kronecker factor matrix multiplies slow us down a bit relative to GPTQ, however the slowdown is small since the work of the extra matrix multiplies is asymptotically small.\n\nWe will make sure to include psuedocode and an improved explanation in the paper revision.\n"}, {"review_id": "KsSsYwJLiR", "reviewer": "Reviewer_Rfzg", "summary": "The work presented in this paper introduces quantization with incoherence processing, which enables better quantization with fewer bits per parameter. The authors provide a theoretical analysis for adaptive rounding methods and present experimental results demonstrating performance of 2-bit quantization..To do this, the paper introduces the LDLQ adaptive rounding method and demonstrates its optimality compared to other rounding methods which specify linear feedback U for hessians, and rounding to integers (see Theorem 1). The authors define incoherence and demonstrate its effectiveness in achieving a theoretically superior asymptotic bound for LDLQ in terms of the spectrum of H. Additionally, the authors propose efficient pre and post incoherence processing techniques to transform W and H matrices, eliminating the need for nxn matrix multiplications.", "questions": "1)I may have overlooked some details, but it appears that the paper only show how making H incoherent reduce loss upper bounds, nothing about W incoherence. What is benefit for making also W  incoherent?\n2) In line 169 you write that \"to make symmetric matrix incoherent is to conjugate it by uniform random orthogonal matrix\". Can you please add citation or explanation why this is true?\n3) Again I may have overlooked some details, in 172- 176 you said that the procedure described there makes the matrix H and W incoherent with high probability/ Why is that, and where is the proof?   \n\nSuggestions:\n1. In line 64, it seems that \"OBC\" might be a typographical error, and \"OBQ\" could be the correct term.\n2. It would be helpful to include a citation for LDL decomposition. \n3.In line 99, it would enhance clarity to present a equation that demonstrates the result obtained when equation (4) is applied in equation (3). \n4.In line 217, it appears that \"OTPQ\" might be a typographical error, and you mean \"OPTQ\".", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper encompasses numerous interesting new concepts, theorems, and their corresponding proofs. The extensive experimentation serves to prove the authors' claims effectively. The writing is solid, making the paper relatively accessible despite the number of theorems and proofs. Proposed incoherence seems to improve baseline methods, for example OPTQ (table 6,7 appendix). The utilization of the incoherence technique has the potential to contribute significantly to achieve usable 2-bit quantization. They provided code, which is always a plus.", "weaknesses": "1) One significant drawback of the paper is that despite the aforementioned enhancements, the performance of 30-bit 2-bit quantization, although much better than 2 bit OPTQ, still falls short compared to 13b model 4-bit quantization with OPTQ(and even 4 bit RTN), making it practically unusable. This limitation diminishes the practical usability surrounding the work on 2 bit quantization.\n\n2) The concept of incoherence remains unclear until page 4 of the paper, which is problematic considering it is one of the main focal points. I believe the introduction should include a clear definition and intuitive explanation of what incoherence entails. Furthermore, I found it challenging to establish a connection between the intuition provided in line 22 and the definition presented in line 134.\n\n3) It is possible I missed, but it appears that there is no mention or measurement of inference speed presented in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**What’s the best use of bits.**\nWe conducted a thorough analysis of the experimental data submitted in our paper. The reviewer is accurate in their observation that 2 bit quantization with QuIP is not worthwhile in terms of total memory budget. However, QuIP is the first method we are aware of to achieve decent and usable results at 2 bits quantization. Other methods including OPTQ cannot sensibly quantize at 2 bits. \n\nOur results indicate that QuIP at 3 bit quantization may be the best for a fixed bit budget, assuming our results generalize to other models. Please see the attached figure where we plot total memory vs perplexity/accuracy on the full set of language generation and zeroshot tasks we include in our paper submission. Over all 7 settings and all OPT models up to 30b, QuIP at 3 bits (and 4 bits) quantization achieves a better use of memory than OPTQ quantized to 4 bits, and the full precision models.\n\nPrevious quantization methods did not work at 2 bits, but our method gives decent and usable results at this quantization level. Our work indicates that quantizing to 3 bits with QuIP is the best use of a fixed bit budget, and paves the way towards making 2 bit inference viable.\n\n\n**Improving incoherence explanations.**\nGreat point, we’ll improve our explanations based on your feedback.\n\nIn Definition 1, incoherent Hessian matrices are defined as having sufficiently small eigenvectors. Incoherent weight matrices are defined as having sufficiently small entries. The intuitive explanation in Line 22 states “the weights themselves and the directions in which it is important to have good rounding accuracy are not too large in any one coordinate”. We see the definition of incoherent weight matrices ensures not too large weights. Note the Hessian is in the proxy objective $tr( (\\hat{W} - W) H (\\hat{W} - W)^T )$, and the eigenvectors of H indicate directions in which rounding accuracy is important. Nagel et. al. [1] also give a nice explanation on the derivation of H.\n\n[1] Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort. Up or down? adaptive rounding for post-training quantization. In International Conference on Machine Learning, pages 7197–7206. PMLR, 2020.\n\n**Evaluating inference speed.**\nThis is a valid point. We have developed a non-optimized implementation including a \n2-bit CUDA kernel and performed initial inference timing results. Based on these results, the additional overhead of the incoherent matrix multiplies do not translate to a significant slowdown. We conducted sequence generation of length 512 on LLaMa-2-70b quantized to 2 bits, with and without our incoherence processing. Our observations so far indicate that loading the weights onto the GPU dominates the inference time, which is not changed by our method. Further optimizations such as tiling the incoherent matrix multiplies are expected to speed up inference. Section 4.1 also demonstrates why the incoherence processing operations are asymptotically non-dominant.\n\n|     | Inference time (s) |\n| -- | ------------------------ |\n| With incoherent matrix multiplies | 416.575 |\n| Without incoherent matrix multiplies | 377.166 |\n\nExperiments conducted on an NVIDIA RTX A6000 GPU.\n\n**What does our theory say about the benefit of making W incoherent?**\nTheorem 7 shows that the method in Algorithm 4 is theoretically optimal when rounding to a finite grid. Theorem 7 requires that the weights are incoherent, and ensures this by applying Lemma 5 to make the weights incoherent with high probability. The theorem statement could also be rewritten to require weight incoherence as an assumption.\n\nBeyond our theoretical analysis, weight incoherence provides several empirical benefits. Weight incoherence ensures that every weight entry is essentially the same. Therefore the need for different scale factors per group is reduced.\n\n\n**Line 169 question on incoherence.**\nConjugating a matrix $H$ by a matrix $U$ results in producing the matrix $U H U^{-1}$, which in the case of orthogonal $U$ is equivalent to $U H U^T$. Let $Q D Q^T$ be the eigendecomposition of $H$. It follows that $(UQ) D (UQ)^T$ is an eigendecomposition of $U H U^T$. If $U$ is drawn uniformly at random from the set of orthogonal matrices, then because $Q$ is also an orthogonal matrix, $U Q$ is also a random variable distributed uniformly on the set of orthogonal matrices. It follows that each column of $U Q$ (aka the eigenvectors of $U H U^T$) is a random variable distributed uniformly on the unit sphere. The entries of such random vector in $n$ dimensions concentrate in magnitude $n^{-1/2}$, and so must the entries of $U Q$. Therefore, $U H U^T$ will (with high probability) be incoherent with a small factor $\\mu$, and we can get bounds on this factor $\\mu$ using concentration inequalities on the magnitude of entries of a random point on the unit sphere).\n\nWe will make sure to improve the explanation in the paper.\n\n**Lines 172-176 incoherence with high probability.**\nPlease see section 4.1 and Lemma 5 for explanation on how we can ensure the Hessian and weight matrices are incoherent with high probability. \n\n**OBC vs OBQ.**\nSections 3 and 4 of the OPTQ paper reference the “OBQ” method that is proposed within the “OBC” paper.\n\n**LDL citation.**\nThanks, we will include a citation for the LDL decomposition.\n\n**Line 99 better clarity when showing Eq.(4) applied to Eq.(3).**\nThis is a good point, we will include the additional explanation.\n\n**Line 217 typo.**\nThanks for pointing this typo out, we will fix it.\n"}, {"review_id": "KCywntL8Lw", "reviewer": "Reviewer_Jvy8", "summary": "This work proposes a unified framework for weight quantization with error feedback together with preprocessing and postprocessing transformation that makes the model more quantization-friendly. Authors derive theoretical bounds on the quantization error and investigate the failure cases of OPTQ quantization. The introduced LDLQ method with incoherence processing is evaluated on quantization of LLM for 2,3 and 4 bit quantization. ", "questions": "How well does LDLQ+QuIP perform on other families of LLM? Would be interesting to evaluate QuIP on LLaMA given the popularity and impressive performance of this model family. Since it is not fully open-sourced one could consider the recent Falcon family (Falcon-7B and Falcon-40B) instead.", "limitations": "Not applicable", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Paper proposes a unified view on quantization with the objective of minimization of layer-wise MSE loss that involves well-known OPTQ as a particular case.\n* Authors derive explicit average and worst-case bounds on quantization error. \n* The introduced incoherence processing is well-motivated and supported by quantitative analysis.\n* The demonstrated LDLQ failure case example despite being very different from typical cases occurring in practice is still interesting and shows potential limitations of the optimal quantization methods.\n* Different variants of LDLQ achieve strong performance on quantization of models from OPT family at various bit widths considered. The most impressive result is that the model attains reasonable perplexity and zero-shot accuracy for 2 bit quantization, which is known to be very challenging and all the competitive methods experience massive performance drop. \n* Overall, the work is well-structured and accompanied with thorough theoretical analysis and empirical study.\n", "weaknesses": "* Method is evaluated only on a single model LLM family. To be sure that the method achieves strong performance on LLM quantization in general one should consider at least one more family of LLM. \n* Minor. $U^{\\prime}$ in formula (4) is not upper unit triangular but rather strictly upper triangular (I guess  $U^{\\prime}  + I$ is supposed to be upper unit triangular). \n* Minor.  This will result in each of its eigenvalues being a random unit vector. I guess the authors meant eigenvectors instead of eigenvalues.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Evaluating on more models.**\nThanks for the feedback; we agree it is important to evaluate our quantization method on additional models. At the suggestion of the reviewers, we conducted additional experiments on LLaMa-2-70b, and share preliminary results below. We will include a fully comprehensive set of LLaMa results in the revision. Encouragingly, the message of our paper remains the same. QuIP is able to successfully quantize down to 2 bits, as evaluated on Lambada and PiQA zeroshot tasks. \n\n| | Lambada Accuracy | PiQA Accuracy |\n| --  | -- | -- |\n| LLaMa-2-70b-chat 2 Bit | 74.02 | 77.48 |\n\n**Minor linear algebra clarification on Eq. (4)**\nThanks for catching the typo, yes $U'$ should be strictly upper triangular. \n\n**Line 170 eigenvalue vs eigenvector clarification.**\nThanks for catching the typo, yes we meant to say eigenvectors. \n"}]

Author rebuttal:
We thank the reviewers for their helpful feedback. 

In summary, reviewers noted how the proposed method pushed the boundary of LLM quantization down to 2 bits, provided a novel theoretical understanding of adaptive layerwise rounding algorithms, and conducted extensive experiments. Previous quantization methods did not work at 2 bits, but our method gives decent and usable results at this quantization level. Our work indicates that quantizing to 3 bits with QuIP is the best use of a fixed bit budget, and paves the way towards making 2 bit inference viable.

The primary concerns were regarding:

**(1) Evaluation on additional models:** QuIP achieves good 2 bit quantization on LLaMa-2. We conducted preliminary experiments quantizing another model, LLaMa-2-70b, to 2 bits, and see that it achieves good zeroshot accuracy on Lambada and PiQA tasks. 

**(2) Evaluation of inference speed:** Based on a non-optimized implementation, the additional operations from our incoherence processing translate to only a 10% increase in inference time. Additional optimizations are expected to speed up inference time. Section 4.1 also demonstrates why the incoherence processing operations are asymptotically non-dominant.

**(3) Evaluating the optimal bit quantization level for fixed bit budget:** An analysis of the experimental data from our submission shows that quantization with QuIP at 3 bits achieves the best tradeoff curve for total memory and model performance. QuIP at 3 bits makes use of a fixed memory budget better than OPTQ, and the full precision OPT models. This insight is consistent across all 7 of our language generation and zeroshot tasks, and on all OPT models up to 30b. 

Full details can be found in the specific reviewer responses. We will include a comprehensive set of experiments and analysis in the paper revision.

**Figure:** QuIP at 3 bits (and 4 bits) achieves a better use of a fixed bits budget compared to OPTQ and full precision OPT models. Evaluated on 3 language generation tasks, 4 zeroshot tasks, and OPT models up to 30b parameters.

Meta-review: The submission proposes a new and interesting formulation of GPTQ-like quantization methods specifically focused on LLM compression. It derives a new approach (QuIP) which seems to improve the behavior of known approaches specifically in the extreme compression (2bit) range by leveraging incoherence. While the practical results are not yet quite fully-baked (a fact made evident by the interesting discussion), the reviewers and AC agreed that the submission covers a very broad area, and brings a solid set of contributions. 

Therefore, I propose to accept.
Decision: Accept (spotlight)