QuIP: 2-Bit Quantization of Large Language Models With Guarantees

Checklist

Our work pushes the quantization of large language models into the 2 bits per weight regime. Our aim is to drive foundational research on theoretical and empirical aspects of quantization. The ultimate goal is to enable more powerful LLMs to run more efficiently. However our work is unaware to what ends those LLMs are used.

2 Limitations

The adaptive rounding [nagel2020up] proxy objective considers each layer in isolation; it remains to be seen what other computationally tractable proxies could improve quantization. For example quantization methods do exist which consider interactions between layers, but so far have been too computationally expensive to be applied to the largest open LLMS.

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.

Additional Method Clarifications

2 Subsection 7.2 (Greedy Updates)

(Note that $\hat{W}-e_{i}e_{j}^{T}\hat{W}_{ij}+e_{i}e_{j}^{T}z$ is the result of setting the $(i,j)$th entry of $\hat{W}$ to $z$.) A full pass of greedy updates constitutes $mn$ 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 a bit more intuition about this method by showing how this greedy algorithm falls within our framework of adaptive rounding with linear feedback.

Since when we use greedy local search as a stand-alone method, we have not updated $\hat{w}_{j}$ yet, at this point $\hat{w}e_{j}=we_{j}$, and so this means that a single step of greedy updates looks like

for $\mathcal{Q}$ referring to nearest rounding with the necessary clamping. Since $\hat{w}-w$ is zero for all entries following the $j$th one, this is equivalent to

where $U$ is set as $U=(H\odot M)\operatorname{diag}(H)^{-1}$ as above. This shows how this single-pass version of greedy updates fits into our adaptive rounding with linear feedback framework.

where $M$ is the strictly upper triangular mask and $\odot$ is elementwise multiplication. This yields a final quantization step of

So, more generally, if we define $U$ as above, and set

we can write a single pass of greedy updates in matrix form as

which is very close to our rounding with linear feedback form, albeit with the difference that here $V$ is in place of $W$. This is made explicit in the included Greedy Updates Algorithm.

Additional Experimental Descriptions and Results

Theorem 6 gives the average-case proxy loss for LDLQ in terms of $\operatorname{tr}\left(D\right)$, where $D$ is from the LDL decomposition of $H$. Lemma 6 gives the average-case proxy loss for standard nearest rounding in terms of $\operatorname{tr}\left(H\right)$. We know that LDLQ is better in practice, but comparing these equations is difficult because we need to reason about $\operatorname{tr}\left(D\right)$ vs $\operatorname{tr}\left(H\right)$. Our paper resolves this difficulty by deriving bounds on the proxy loss for LDLQ in terms of the spectrum of $H$ (with and without incoherence). However we also perform a quick empirical check: if $\operatorname{tr}\left(D\right)\ll\operatorname{tr}\left(H\right)$, then our theory explains the empirical superiority of LDLQ over nearest rounding (at least on these models). Table 1 gives the ratio $\operatorname{tr}\left(D\right)/\operatorname{tr}\left(H\right)$ 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𝐻H is approximately low-rank.

Subsection 6.3 plotted the normalized eigenvalues of $H$ from 3 randomly chosen layers in OPT-2.7b. Table 1 gives much more evidence that $H$ is consistently approximately low-rank. Across each model, we calculate the absolute and approximate fractional rank 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 is $\approx 0.02(\pm 0.02)$.

2 Subsection 8.1 (Empirical Verification of OPTQ Equivalence)

We share a python script in the supplementary code which empirically verifies that our implementation of LDLQ produces quantized values exactly matching OPTQ’s [frantar2023gptq] implementation. While we prove the equivalence between LDLQ and OPTQ’s respective algorithm statements, empirically comparing ours and frantar2023gptq’s code ensures that the respective implementations are sufficiently close to their algorithmic statements. Therefore we can be sure that LDLQ and OPTQ are equivalent in their implementation.

3 Subsection 8.2 (Empirical Verification of LDLQ/OPTQ Finite Grid Counterexample)

The following code constructs a weight matrix $W$ and Hessian matrix $H$ where OPTQ performs worse than nearest when rounding to a finite grid.

The intuition behind this counterexample is as follows: we want to 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 we can achieve this poor OPTQ behavior with c=0, but here nearest rounding also does poorly. We make a small perturbation (c=0.01) to make OPTQ round in the wrong direction, but not nearest.

4 Additional Details on the Experimental Setup and Computational Resources

We run experiments on a university cluster managed by a 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 OpenAI 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, we tune the parameter $\rho$ and find that a value of 2.4 works well across all model sizes and quantization methods. We use this value for all our experiments.

5 Section 9 (Main Results on Additional Evaluations)

Figure 1 shows additional results for QuIP and OPTQ on WikiText2, PiQA, and StoryCloze when quantizing to 2 and 3 bits per weight. The insights about our method QuIP remain the same after viewing these additional results: QuIP is the first PTQ procedure to achieve good quantization at two bits per weight, across a variety of LLM sizes and evaluation tasks. We evaluate on OPT models (up to 30B); 4-bit quantization works equally well for both methods. QuIP is superior to OPTQ across model sizes and evaluation tasks here.

On WikiText2 2-bit quantization, note that the trend in perplexity for QuIP mirrors the trend in perplexity for OPTQ. We run OPTQ’s [frantar2023gptq] implementation, though they did not report 2-bit results at this model size. Because OPTQ is equivalent to QuIP’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. QuIP’s perplexity also increases from OPT-1.3b to OPT-2.7b, and is unusually higher than the adjacent OPT-1.3b and OPT-6.7b models. However QuIP still beats OPTQ in this setting. Our observations about OPTQ and QuIP on WikiText2 and OPT-2.7b were consistent across multiple independent runs.

6 Section 9 (All Methods, All Model Sizes, All Bit Weights, All Evaluation Tasks)

Tables 2-8 provide results on all combinations of the following: methods, model sizes (OPT 125m-30b), bit weights(4,3,2), and evaluation tasks. Across our extensive array of experiments, we see that incoherence processing always enables a step function change in quantization at 2 bits.

7 Section 9 (Evaluating the Effectiveness of the Proxy Objective)

In Table 9 we 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 use $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/LDLQ, LDLQ-RG, and Greedy are roughly equivalent at 2 bits, and do better than Nearest.

8 Section 9 (Evaluating Unbiased Rounding in LDLQ/OPTQ)

Note in our formulation for Adaptive Rounding with Linear feedback, the $\mathcal{Q}$ subroutine could be biased, or unbiased. It is typical to perform biased rounding in practice; here we investigate if there is any benefit to switching to unbiased rounding schemes. Table 10 computes the average perplexity difference (i.e. $\operatorname{unbiased}-\operatorname{biased}$) for LDLQ/OPTQ on WikiText2, PTB, and C4. That is, we run LDLQ with the $\mathcal{Q}$ subroutine as stochastic rounding, instead of nearest. The average difference is 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.

9 Section 9 (Evaluating Algorithm 5 Which Accounts for Clamping)

Table 11 shows results from using Algorithm 5 to quantize OPT models 125m to 1.3b, with incoherence processing and baseline processing. At 2 bits and incoherence processing, we observe modest improvements over QuIP in terms of perplexity on OPT models 125m and 350m. However, at the larger OPT-1.3b QuIP beats Algorithm 5 on 2/3 language generation tasks. In addition, Algorithm 5 is computationally more work to run. Therefore we decide not to use it.

Another observation: in practice, we don’t seem to encounter constructions of $W$ and $H$ that are bad for LDLQ/OPTQ. Therefore this “clamping” issue seems to not be an issue in practice, especially as model size increases.

Introduction

Large language models (LLMs) have enabled advances in text generation, few-shot learning, reasoning, protein sequence modeling, and other tasks . 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 as a way to improve their runtime efficiency . Our key insight is that quantization can be most effective when weight and proxy Hessian matrices are incoherent—that the weights themselves are even in magnitude, and the directions in which it is important to have good rounding accuracy are not too large in any one coordinate. Intuitively, incoherence can be thought of as a principled form of outlier reduction, which makes it easier to adaptively round the weights to a finite set of compressed values. We use this intuition to develop theoretically sound two-bit quantization algorithms that scale to LLM-sized models.

We complement our method with a theoretical analysis—the first for a quantization algorithm that scales to LLM-sized models—which analyzes the role of incoherence and shows that our quantization procedure is optimal within a general class of rounding methods. Interestingly, we find that QuIP without incoherence processing yields a more efficient implementation of an earlier algorithm, OPTQ [frantar2023gptq]; our paper thus also provides the first theoretical analysis for that method.

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 at the feasibility of accurate 2-bit inference in LLMs.

Contributions. In summary, this paper makes the following contributions: (1) we propose QuIP, a quantization method based on the insight that model parameters should ideally be incoherent; (2) we provide a theoretical analysis for a broad class of adaptive rounding methods that encompass QuIP and OPTQ; (3) we demonstrate that QuIP makes two-bit LLM compression viable for the first time.

Related Work

Adaptive rounding. nagel2020up are the first to motivate the “adaptive rounding” proxy objective (Eq. (2)) in a principled way. There are many quantization methods which quantize by optimizing this proxy objective [dong2019hawq1, dong2020hawq2, hubara2021adaq, li2021brecq, liu2021ptqvit, nagel2020up, yao2021hawq3]. Many require further retraining which can be expensive, and are not evaluated on the current largest open LLMs (OPT [meta2022opt], BLOOM [workshop2023bloom]). lybrand2021greedy 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 a 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 [xiao2023smooth] rescales between activations and weights to remove outliers from the activations and make quantization overall easier. ZeroQuant [yao2022zero] proposes a per-layer knowledge distillation method. LLM.int8() [dettmers2022int8] decompose matrix multiplications into a majority of 8 bit and a minority of 16 bit operations. LUT-GEMM [park2023lutgemm] designs kernels to accelerate quantized matrix multiplications. RPTQ [yuan2023rptq] reorders activations and quantizes them in groups, reducing the impact of range differences between channels.

OPTQ (Formerly known as GPTQ). OPTQ [frantar2023gptq] is based on OBQ [frantar2022obc], 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 [nagel2020up], or are not designed for the largest language models [jeon2022biq, li2022qvit, liu2023noisy, nagel2019dfq, wang2020bit, wei2022outlier].

Quantization With Incoherence Processing: Adaptive Rounding Step

This section introduces quantization with incoherence processing (QuIP), a 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 on step (2).

Following existing state-of-the-art post-training quantization methods, we round weights per-layer by minimizing the “adaptive rounding” proxy objective, as in nagel2020up,

Our strategy is to define a family of adaptive rounding methods for optimizing objective (2) and then define LDLQ, the optimal method within that class. Our defined methods iteratively perform the following update for $k=1,2,...,n$:

where $U$ is a strictly upper-triangular matrix whose columns are the vectors $a_{k}$ and $\mathcal{Q}$ acts elementwise. Because $U$ is upper-triangular, $\hat{W}_{k}$ only depends on $\hat{W}_{1:(k-1)}$.

If we let $\eta=\mathcal{Q}(W+(W-\hat{W})U)-(W+(W-\hat{W})U)$ denote the quantization error of $\mathcal{Q}$, we find that $\hat{W}-W=\eta(U+I)^{-1}$ and we can rewrite objective (2) as

How should we specify $U$, the linear feedback from the quantization error of preceding columns in (3)? Equation 4 provides an answer. If we choose $U\leftarrow\grave{U}$ such that the LDL decomposition of $H$ is

where $D$ is a (non-negative) diagonal matrix and $\grave{U}$ is upper unit triangular, then the terms $(U+I)$ in Eq. (4) cancel. We denote as LDLQ the rounding procedure in Eq. (3) with $U\leftarrow\grave{U}$ as the LDL assignment from Eq. (5). We will now see that the LDL assignment of $U$ is in fact optimal.

2 Deriving the Optimality of the LDLQ Adaptive Rounding Procedure

Subsection 6.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 $\mathcal{A}$ denote a rounding method, and let $\mathcal{A}(W,H)$ be the resulting quantized weights. Define the worst-case ($\mathcal{L}_{\operatorname{worst}}$) and average ($\mathcal{L}_{\operatorname{avg}}$) proxy losses with respect to the input weights as

$\mathsf{LDLQ}$ is worst and average-case optimal amongst rounding methods which specify the linear feedback $U$ as a function of $H$ (not of $W$), and when rounding to the integers. That is, for all rounding methods $\mathcal{A}$ in the class described by Eq. (3), for all positive semi-definite $H$, and for $\mathcal{Q}$ as either nearest or stochastic rounding,

where $D$ is the matrix from the LDL decomposition of $H$, and $c=12$ for nearest, $c=6$ for stochastic.

Let $X$ be the strictly upper triangular matrix associated with the rounding procedure $\mathcal{A}$ such that $U\leftarrow X$ in Eq. (3). Let $B\equiv(X+I)^{-1}(\grave{U}+I)$ where $\grave{U}$ is from the LDL decomposition of $H$ in Eq. (5). The proxy loss is then,

With the LDL assignment of $U$, we further have that,

Next, consider the average loss, $\mathcal{L}_{\operatorname{avg}}$, where $W\sim Unif^{m\times n}$. For $\mathcal{Q}$ as nearest rounding, the entries of the quantization error $\eta$ are $Unif[-\frac{1}{2},\frac{1}{2}]$, because each entry is independent and uniformly distributed. It follows that for any entry of $\eta$, $\mathbf{E}\left[\eta_{ij}^{2}\right]=\int_{-1/2}^{1/2}x^{2}dx=\frac{1}{12}$. Therefore, $\mathcal{L}_{\operatorname{avg}}(\mathcal{A},H)\stackrel{{\scriptstyle\eqref{eqnThm1proofa}}}{{=}}\mathbf{E}_{W\sim Unif^{m\times n}}\left[\operatorname{tr}\left(\eta BDB^{T}\eta^{T}\right)\right]=\frac{m}{12}\operatorname{tr}\left(BDB^{T}\right)$. For $\mathcal{Q}$ as stochastic rounding, the entries of the quantization error $\eta$ are $Unif$. It follows that for any entry of $\eta$, $\mathbf{E}\left[\eta_{ij}^{2}\right]=\int_{0}^{1}x(1-x)dx=\frac{1}{6}$. Note that for stochastic rounding, the quantization error will be $x$ with probability $(1-|x|)$. Therefore, $\mathcal{L}_{\operatorname{avg}}(\mathcal{A},H)=\frac{m}{6}\operatorname{tr}\left(BDB^{T}\right)$. Based on these same calculations of $\mathbf{E}\left[\eta_{ij}^{2}\right]$, we have that $\mathcal{L}_{\operatorname{avg}}(LDL,H)\stackrel{{\scriptstyle\eqref{eqnThm1proofa}}}{{=}}\frac{m}{12}\operatorname{tr}\left(D\right)$ with $\mathcal{Q}$ as nearest , and $=\frac{m}{6}\operatorname{tr}\left(D\right)$ with $\mathcal{Q}$ as stochastic rounding. By the same reasoning on the minimization of $\operatorname{tr}\left(BDB^{T}\right)$,

Remarks. The number of rows being quantized is $m$, and each quantization method operates across the $n$ entries of each row. For all rounding methods described by Eq. (3), and for all positive semi-definite $H$, $\mathcal{Q}$ as nearest rounding achieves the same worst-case proxy loss as stochastic rounding, but achieves better average proxy loss.

Moving beyond a generic algorithm $\mathcal{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 $\mathcal{Q}$ subroutine, and setting all entries of the linear feedback to zero.

3 Incoherence: Optimality with a Spectral Bound

Subsection 6.3 (Incoherence: Optimality with a Spectral Bound)

Theorem 6 gives exact expressions for the proxy loss, albeit with $\operatorname{tr}\left(D\right)$, which can be difficult to reason about. In Figure 4, 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, a vast majority of $H$ matrices have fewer than a quarter of eigenvalues $>1\%$ of the max eigenvalue; see Supplement 3 for full details. Given this observation about the low rank of $H$, can we bound the behavior of LDLQ, and thus $\operatorname{tr}\left(D\right)$, using the spectrum of $H$?

It’s straightforward to see that $\Sigma_{k}=\mathbf{E}\left[x_{k}x_{k}^{T}\right]$. But it’s also easy to see that the step-$k$ update only modifies/assigns the $k$th entry of $x$, and does so based only on earlier entries of $x$. Since $e_{k}^{T}x_{k}=0$, and no later step assigns the $k$-or-lower entries of $x$,

In particular, this immediately implies that

where $B=I+A$. Differentiating with respect to $B$ in strictly lower triangular direction $\Delta$ (the only direction in which we have degress of freedom, since the diagonal of $B$ must be unit) yields

It’s not hard to see that if $H=LDL^{T}$ is the LDL decomposition of $H$, and $B^{T}=L$, that the gradient is

By continuity of $\operatorname{tr}\left(D\right)$ and $\operatorname{tr}\left(H^{1/2}\right)$, it suffices to prove the lemma for positive definite $H$. First, the closure of positive definite symmetric matrices is the set of positive semi-definite symmetric matrices. Second, consider the set of $H$ that are positive definite and satisfy $\frac{\mu^{2}}{n}\operatorname{tr}\left(H^{1/2}\right)^{2}-\operatorname{tr}\left(D\right)\geq 0$, i.e. are non-negative. The closure of this set (i.e. $H\succeq 0$) must also satisfy that the inequality is non-negative.

Let $H=Q\Lambda Q^{T}$ be the eigendecomposition of $H$. First, observe that by incoherence,

and consider the recurrence from Lemma 1 with

Suppose by way of induction that for some scalar the covariance $\Sigma_{k}\preceq\alpha H^{-1/2}$. For the base case, this obviously holds since $\Sigma_{0}=0$. At step $k$,

But from Lemma 1, we know that $\operatorname{tr}\left(D\right)$ is the global minimum of $\operatorname{tr}\left(H\Sigma_{n}\right)$ for any assignment of $a_{k}$. This immediately gives us the desired result. ∎

To the best of our knowledge, this is a novel result using incoherence to obtain a bound on $\operatorname{tr}\left(D\right)$ that depends only on the spectrum of $H$. To help interpret this result, we derive explicit proxy losses for plain nearest and stochastic rounding, which we will then compare to what LDLQ gets via Lemma 6.

Let $H$ be symmetric positive definite. In the worst case stochastic rounding achieves $\mathcal{L}_{\operatorname{worst}}(\mathsf{Stoch},H)=(m/4)\operatorname{tr}\left(H\right)$. In the average case nearest and stochastic rounding achieve $\mathcal{L}_{\operatorname{avg}}(\{\mathsf{Near},\mathsf{Stoch}\},H)=(m/c)\operatorname{tr}\left(H\right)$, where $c=12$ for nearest, and $c=6$ for stochastic.

For nearest and stochastic rounding, set the linear feedback $U$ in Eq. (3) to be zero. Stochastic rounding achieves worst-case loss,

For the average-case proxy loss, recall the computations of $\mathbf{E}\left[\eta_{ij}^{2}\right]$ from the proof of Theorem 6.

To interpret this result, consider $H$ rank-$k$ with $\mu^{2}k<n$. By Cauchy-Schwarz, $\operatorname{tr}(H^{1/2})^{2}\leq k\operatorname{tr}\left(H\right)$. Combining Lemma 6 with the LDLQ proxy losses of Theorem 6 and comparing with Lemma 6,

where $\mathcal{B}\in\{\mathsf{Near},\mathsf{Stoch}\}$, and $c$ is as given in Theorem 6. This shows that for sufficiently low-rank $H$, LDLQ is asymptotically better than plain nearest and stochastic rounding by a factor of $\mu^{2}k/n$.

By assuming incoherence, we were able to show LDLQ gets an asymptotically better bound in terms of just the spectrum of $H$. We might ask: was the incoherence assumption necessary to get 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. {toappendix}

Without incoherence: no improvement with a spectral bound

On the average-case loss $\mathsf{LDLQ}$ achieves the same error as the corresponding rounding routine. Let $\mathcal{B}=\{\mathsf{Near},\mathsf{Stoch}\}$ and $c=12$ for nearest, $c=6$ for stochastic.

See Lemma 6 for calculations on the proxy loss for nearest and stochastic rounding.

Note that the worst case for comparing LDLQ against these baselines occurs when $H$ is diagonal, see Theorem 6 and Lemma 6. Assuming incoherence as we do is a natural way to exclude such cases.

Quantization With Incoherence Processing: Incoherence Processing Step

Next, we leverage the above incoherence analysis to introduce incoherence processing, the second step of the QuIP algorithm. Our strategy will be to pre-process weight and Hessian matrices to ensure the favorable incoherence properties outlined above. One straightforward way to make a symmetric matrix incoherent is to conjugate it 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}$.

Subsection 7.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—making it 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\times n$ random orthogonal matrices $U,V$ would be prohibitive.

Also observe that for $x$ drawn uniformly from the sphere in $n$ dimensions,

Trivially, then, for some modified global constants $A^{\prime}$ and $C^{\prime}$,

for some global constants $A$ and $C$ independent of $n$ and $k$.

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 a matrix of eigenvectors of $H$. Observe that since $Q$ is an orthogonal matrix (by the spectral theorem, because $H$ is symmetric), $Qe_{j}$ is a unit vector, i.e. $\left\|Qe_{j}\right\|=1$. Call $Qe_{j}=y$. Also observe that

for some indices $i_{j}$. Call $e_{i_{j}}^{T}U_{j}=x_{j}^{T}$, and observe that the $x_{j}$ are all independent unit random vectors. So,

for random unit vectors $x_{1},\ldots,x_{k}$ and unit vector $y$. We can easily bound this with $k$ applications of Lemma 3 and a union bound, yielding

Setting $\delta\mapsto\frac{\delta}{kn^{2}}$ yields

and unioning over all the entries of the large orthogonal matrix,

Next, for $W$, observe that if we flatten $W$, then $W/\left\|W\right\|_{F}$ is a unit vector. Then any entry of the resulting matrix can be written as

where $x_{1},\dots,x_{k}$ and $y_{1},\dots,y_{k}$ are $k$ independent random unit vectors. We can easily bound this with $2k$ applications of Lemma 3 and a union bound, yielding

Setting $\delta\mapsto\frac{\delta}{2kmn}$ yields

and unioning over all the $mn$ entries of the large orthogonal matrix,

Remarks. This lemma means that multiplying by a random matrix in this family suffices to make a matrix incoherent with parameter $\mu$ only poly-logarithmic in the matrix size. In our experiments we use $k=2$ factors to construct the orthogonal matrices $U,V$.

2 Additional Heuristics

We outline QuIP pre-processing and post-processing in Algorithms 2 and 3, respectively. In line 6 of Algorithm 2, we apply the aforementioned fast orthogonal multiplication procedure to 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 a number of additional heuristic improvements that further improve performance.

Greedy local search. Our basic procedure yields a good initial guess with error guarantees. We can further lower the proxy loss by running coordinate descent after LDLQ (but before post-processing), updating the weights in the same order as in the initial pass. See Supplement 2 for full details.

Extensions and Further Analyses

Subsection 8.1 (OPTQ is a Special Case of LDLQ)

We prove a novel theoretical insight: QuIP without incoherence processing (i.e., LDLQ) is equivalent to a more efficient version of the OPTQ algorithm. That is, OPTQ falls under our class of adaptive rounding procedures with linear feedback, and is within-class optimal.

OTPQ [frantar2023gptq] falls within the class of adaptive rounding procedures with linear feedback as described by Eq. (3), and is equivalent to LDLQ in Section 6.

OPTQ works in the following way. After OPTQ has quantized the first $t-1$ components of the row vector $w$, it minimizes the proxy loss over the remaining $n-t+1$ elements, keeping the first $t-1$ elements fixed. It then quantizes the $t$th element using nearest rounding to the grid and clamping. It then proceeds to the next column. If we let $\Delta=\hat{w}-w$, this proxy loss that it minimizes can be written in block form as

and its minimum over $\Delta_{t:n}$ will occur when

Finally, we quantize the $t$-th weight as

This update is equivalent to our adaptive rounding with linear feedback procedure in Eq. (3), with $U$ assigned from the LDL decomposition of $H$. ∎

Remarks. To the best of our knowledge, this equivalence yields the first theoretical analysis of OPTQ. Even though the two methods are equivalent, LDLQ is more efficient. OPTQ’s implementation requires a matrix inversion of $H$, and two Cholesky decompositions. Our implementation of LDLQ performs no matrix inversion, and only one Cholesky decomposition.

Empirical Verification. The quantized outputs of the OPTQ implementation [frantar2023gptq] are shown to be exactly identical to the outputs of our LDLQ implementation. Synthetic random data was used, with $W\sim\operatorname{Unif}^{1000\times 1000}$. Full details can be found in Supplement 3.

2 A Bound for Rounding to a Finite Grid

Subsection 8.2 (A Bound for Rounding to a Finite Grid)

In Section 6, we saw that LDLQ (equivalently, OPTQ) is optimal for minimizing the adaptive rounding objective. However, this analysis assumed rounding to the integers. In practice, we do not want to round $W$ just to the integers, but instead to scale it, shift it, and round it a finite subset corresponding to a $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, as the following concrete example illustrates.

Finite Grid Counterexample. Figure 5 illustrates the behavior of LDLQ and other rounding methods—when restricted via clamping to a finite 4-bit grid $$—on a particular example where$H$is a (cleverly chosen) small perturbation of$(I_{n}+\mathbf{1}_{n\times n}-e_{n}e_{n}^{T})/n$, and$W$has$m=16$and is a small perturbation of$\mathbf{1}_{m\times n}/2$. Details of the setup appear in Supplement 3. The figure shows that clamped LDLQ with nearest rounding is asymptotically worse, and the clamping to the finite grid is what causes it to be worse in this case.

Note that in our experiments in practice, OPTQ has been shown to soundly beat nearest rounding. This clamping issue does not seem to arise in practice; however, since it is possible we do need to take it into account to prove useful end-to-end bounds.

A 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 $|\hat{W}_{ij}-W_{ij}|$, 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 $c$

Algorithm 5 presents a quantization procedure which theoretically address OPTQ’s clamping issue, by incorporating a restriction of $|\hat{W}_{ij}-W_{ij}|$ into objective (13). 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.

We first note that since $x_{t}$ is supported only on $\{1,\ldots,t\}$, if $M$ denotes the strictly upper triangular mask, this update step is equivalent to

From here, it’s fairly easy to see by induction that

Now, since $I+A\odot M$ is a unit upper triangular matrix, its inverse is also a unit upper triangular matrix. If we let $L=(I+A\odot M)^{-1}$, then $L$ is a unit upper triangular matrix and

We are going to choose $A$ such that $L$ is a feasible solution to our optimization problem and has the desired objective. Next, let $\Sigma_{t}=\mathbf{E}\left[x_{t}^{T}x_{t}\right]$, and observe that

Let $\alpha>0$ be some constant to be set later, and set $A=\alpha H^{1/2}$. Suppose by way of induction that for some constant $\beta>0$ to be set later, $\Sigma_{t}\preceq\beta H^{-1/2}$. The base case clearly holds since $\Sigma_{0}=0$. For the inductive step,

This inductive step will hold if, letting $h=\max_{i}e_{i}^{T}H^{1/2}e_{i}$,

So the constraint of our optimization problem will be satisfied if

To satisfy these constraints, set $\beta=\max(h,h/c)$ and $\alpha=\beta^{-1}$. Then

Now, applying incoherence to bound $h$, where $H=U\Lambda U^{T}$ is the eigendecomposition of $H$,

Let $\eta$ 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

From a repeated application of Hoeffding’s lemma, we get

Setting $u\mapsto\gamma u$ for $\gamma>0$,

Minimizing the right side over $\gamma$ yields $\gamma=4R\left\|Lu\right\|^{-2}$ and

Now setting the right side equal to $\delta$,

This is what we wanted to show. The second statement follows from the fact that

where $\mathcal{Q}_{\operatorname{stoch}}$ denotes elementwise unbiased stochastic rounding. Suppose that for some integer $b$, $1\leq w_{ij}\leq 2^{b}-2$. Then if we set

then with probability at least $1-\delta$, $0\leq\hat{w}_{ij}\leq 2^{b}-1$ and

First, from the previous lemmas, if $Ue_{i}$ is the $i$th eigenvector of $H$, with eigenvalue $\lambda_{i}$ since

And substituting $\delta\mapsto\delta/2$,

On the other hand, again by a union bound from the previous lemma,

And so by another union bound, the probability that

is no less than $1-\delta$. 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 we want. ∎

Suppose that we are given an input matrix $w$ with bounded maximum entry magnitude $\left\|w\right\|_{\infty}$ and we want to quantize it using $b$ bits. Suppose that we first re-scale the entries of $w$ by mapping

this guarantees that $1\leq w_{ij}\leq 2^{b}-2$. Then, suppose we quantize using the procedure described in the previous lemma. Finally, we undo the scaling. Then then with probability at least $1-\delta$, all the quantized weights will be in range (no overflow or need for clipping) and

This is a straightforward consequence of the previous lemma. ∎

Suppose that we are given an input matrix $w$ with bounded $\left\|w\right\|_{F}$ and we want to quantize it using $b$ bits. Suppose that we first multiply by two-factor orthogonal matrices, and then we re-scale the entries of $w$ by mapping

this guarantees that $1\leq w_{ij}\leq 2^{b}-2$. Then, suppose we quantize using the procedure described in the previous lemma. Finally, we undo the scaling and multiplication. Then then with probability at least $1-\delta$, all the quantized weights will be in range (no overflow or need for clipping) and

It is a straightforward consequence of Lemma 7, that unioning over the three bounds on the infinity norm of $w$, the incoherence of $H$, and the stochastic rounding, with probability at least $1-3\delta$,

Our “fixed” algorithm solves this convex problem (e.g. with ADMM), then runs QuIP using stochastic rounding and $U=R^{-1}-I$ in place of the LDL decomposition. Observe that for sufficiently large $c$, this is exactly equivalent to base QuIP, since the solution of that optimization problem is given by the LDL decomposition when the constraint is dropped. Doing this (the full algorithm is given in the supplemental) yields the following theorem.

This follows directly from the previous theorem, which says explicitly what the hyperparameter assignments should be. ∎

In practice, because clamping rarely causes issues, and because of the significant additional compute needed to solve this program, we always just use QuIP as described in the previous sections, which is equivalent to setting $c$ large and using nearest rounding.

Experiments

Overview. We quantize the OPT [meta2022opt] family of models (up to 66B parameters) and Llama 2 70B [meta2023llama] using various quantization and processing methods. QuIP is superior to OPTQ and other baselines across all model sizes and evaluation tasks. Most interestingly, incoherence processing yields excellent performance using as 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), a 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 QuIP 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 5 are presented in the Supplement 3.

Setup. The experimental infrastructure is built on top of OPTQ’s [frantar2023gptq] repository which is implemented in PyTorch [paszke2019pytorch]. 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 as OPTQ; 128 random 2048 token segments from the C4 dataset [raffel2020c4] 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 a time: loaded into GPU memory, the Hessian computed, and then the weights quantized. The current block’s inputs are then passed through the quantized block to 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 3, 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 $\operatorname{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\leftarrow H+\alpha*\operatorname{mean}(\operatorname{diag}(H))I$ for numerical stability. We also evaluate our incoherence processing in Algorithms 2 and 3, denoted as “IncP”. With this notation QuIP = LDLQ + IncP, and QuIP-RG = LDLQ-RG + IncP.

Datasets. We evaluate on the following language generation tasks: WikiText2 [merity2016wiki], Penn Treebank (PTB) [marcus1994penn], and C4. We also evaluate on zero-shot tasks, including LAMBADA (LAMB) [paperno2016lambada], ARC Easy (ArcE) [boratko2018arc], PiQA [tat2003piqa], and StoryCloze (SC) [2016storycloze]. See Supplement 3 for the full set of results.

Main Results. QuIP 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 6 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, QuIP matches the full precision model reasonably well. At two bits and for larger LLMs (>2B parameters), QuIP begins to approach the performance of the full precision model. As model size increases, so does the quality of QuIP’s 2-bit quantization. We provide plots on the remaining datasets in Supplement 3. Note that the dip in OPTQ on OPT-66B is documented in their paper.

Table 12 shows the results of quantizing Llama 2 70B using QuIP and OPTQ. Again, QuIP achieves good quantization at two bits while OPTQ does not.

Incoherence Processing Ablation. Table 13 shows all combinations of quantization and processing methods evaluated on OPT-30B. At lower weight bits, QuIP’s incoherence processing dramatically improves the performance of all quantization methods, across all evaluation tasks. Remarkably, all quantization methods—even nearest—are viable at two bits with our incoherence processing. Our modifications in QuIP-RG sometimes give an improvement over QuIP, but further study is required to evaluate these modifications. Figures for OPT-125M to 13B are in Supplement 3.

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 full-precision-vector product kernel and was shown to offer speedups over a FP16 baseline. Our incoherence processing additions are performed in PyTorch. Table 15 shows that our QuIP implementation is about 1.5$\times$ slower than OPTQ.

Further Ablation. QuIP’s incoherence processing contains several sub-steps. Table 14 shows their relative contributions; all are necessary for the full improvement. Table 16 shows that the random permutation step within the fast orthogonal multiplication also significantly reduces perplexity.

Conclusion

This paper introduced quantization with incoherence processing (QuIP), an algorithm consisting of (1) an optimal adaptive rounding procedure which minimizes a quadratic proxy of the weight error, and (2) efficient pre- and post-processing to ensure the incoherence of the weight and Hessian matrices by multiplying them by a Kronecker product of random orthogonal matrices. We showed that QuIP quantization is optimal in a general class of adaptive rounding methods with linear feedback; this theoretical analysis is the first for any quantization algorithm that scales to LLM-sized models.

Empirically, QuIP achieves the first viable two-bit quantization results for LLMs, especially at large model sizes, hinting at the feasibility of accurate 2-bit inference in LLMs.

Acknowledgements and Disclosure of Funding

This work was partially funded by the National Science Foundation under awards DGE-1922551, CAREER awards 2046760 and 2145577, by the National Institute of Health under award MIRA R35GM151243, and a gift from CISCO.

References