# QuIP$\\#$: Even Better LLM Quantization with
Hadamard Incoherence and Lattice Codebooks

Albert Tseng  Jerry Chee  Qingyao Sun  Volodymyr Kuleshov  Christopher De Sa

###### Abstract

Post-training quantization (PTQ) reduces the memory footprint of LLMs by
quantizing their weights to low-precision. In this work, we introduce
QuIP$\\#$, a weight-only PTQ method that achieves state-of-the-art results in
extreme compression regimes ($\leq$ 4 bits per weight) using three novel
techniques. First, QuIP$\\#$ improves the incoherence processing from QuIP
(Chee et al., 2023) by using the randomized Hadamard transform, which is
faster and has better theoretical properties. Second, QuIP$\\#$ uses vector
quantization techniques to take advantage of the ball-shaped sub-Gaussian
distribution that incoherent weights possess: specifically, we introduce a set
of hardware-efficient codebooks based on the highly symmetric $E_{8}$ lattice,
which achieves the optimal 8-dimension unit ball packing. Third, QuIP$\\#$
uses fine-tuning to improve fidelity to the original model. Our experiments
show that QuIP$\\#$ outperforms existing PTQ methods, enables new behaviors in
PTQ scaling, and supports fast inference.

Machine Learning, ICML, Quantization, Large Language Models, LLMs, Low
Precision, Inference, Systems, Hardware, 2 bit, QuIP, Incoherence Processing,
Lattice Codebooks, Vector Quantization

##  1 Introduction

Figure 1: QuIP$\\#$ offers unprecedented quantization quality at extreme
compression ratios. QuIP$\\#$ 3-bit models also scale better than
theoretically lossless 4-bit models, a previously unseen result. Figure 2:
QuIP$\\#$ performs incoherence processing with a Randomized Hadamard Transform
and uses lattice codebooks to achieve state-of-the-art quantized models.

Large language models (LLMs) have driven rapid advances across diverse fields
such as natural language processing (Touvron et al., 2023b), scientific
modeling (Nguyen et al., 2023), and program synthesis (Rozière et al., 2024).
However, the massive size of these models poses significant challenges to
their deployment. For example, the largest model in the Llama2 family has 70B
parameters, and requires 140GB of GPU memory in native 16-bit precision
(Touvron et al., 2023b). This massive memory footprint motivates research into
methods that can compress LLMs without sacrificing quality.

Post-training quantization (PTQ) reduces the memory requirements of large
models by converting trained weights to a lower precision. For example, with
2-bit quantization, a 16-bit LLama2 model with 70B parameters fits on a single
consumer-grade 24GB GPU and benefits from increased inference throughput (Cai
et al., 2024). However, 2-bit quantization also often reduces the quality of
the model and pushes the limits of PTQ algorithms (Chee et al., 2023).

In this work, we introduce QuIP$\\#$, a weight-only PTQ method that achieves a
new state-of-the-art in model quantization. QuIP$\\#$ improves over existing
work via three techniques: incoherence processing, lattice codebooks, and
fine-tuning. Incoherence processing is a principled form of outlier
suppression that produces approximately sub-Gaussian distributed weight
matrices (Chee et al., 2023). QuIP$\\#$ performs incoherence processing with
the computationally-efficient randomized Hadamard transform (Halko et al.,
2011) (Section 3). To quantize incoherent matrices, QuIP$\\#$ uses the
BlockLDLQ block adaptive rounding algorithm with compressible codebooks based
on the $E_{8}$ lattice, which achieves the highest density 8 dimensional unit-
ball packing (Viazovska, 2017) (Section 4). The $E_{8}$ lattice is highly
structured and symmetric, which means that our codebooks are hardware-friendly
and admit fast inference. Finally, QuIP$\\#$ includes an inter-layer fine-
tuning algorithm that further improves quantization quality (Section 5).

These developments allow QuIP$\\#$ to significantly outperform existing PTQ
methods including OmniQuant (Shao et al., 2024), QuIP (Chee et al., 2023) (a
previous, separate work), and AQLM (Egiazarian et al., 2024). To the best of
our knowledge, QuIP$\\#$ is also the first PTQ method where 3-bit models scale
better than 4-bit models. This directly refutes Dettmers & Zettlemoyer
(2023)’s claim that 4-bit models are “optimal” and indicates that as the field
of PTQ develops, 2-bit models are likely to scale better than 3-bit models in
the near future.

Finally, we note that QuIP$\\#$ was designed from the ground up to be fast.
Algorithm 2 describes fast inference with a QuIP$\\#$-quantized linear layer.
Our “proof of concept” CUDA implementation of QuIP$\\#$ achieves over 50% of
peak memory bandwidth on a NVIDIA RTX 4090, validating our design choices.

In summary, we introduce QuIP$\\#$, a post-training quantization method that
achieves state-of-the-art results by

  1. 1.

Performing incoherence processing with the Randomized Hadamard Transform,
which has better incoherence properties and faster runtime than the Kronecker
factorization in QuIP.

  2. 2.

Rounding incoherence-processed weight matrices with block adaptive rounding
and codebooks based on the $E_{8}$ lattice, which achieves the highest
8-dimension unit ball packing density (kissing number).

  3. 3.

Introducing an inter-layer fine-tuning algorithm that further improves
quantization quality.

Algorithm 1 QuIP$\\#$ without Fine-Tuning (QuIP$\\#$-NoFT)

0: Weight $W\in\mathbb{R}^{m\times n}$, hessians $H\in\mathbb{R}^{n\times n}$,
$g$-dim. $k$-bit codebook $C$

$\hat{W},\hat{H},S_{U},S_{V}\leftarrow\mbox{IP-RHT}(W,H)$ (Alg. 3)

$\hat{W}\leftarrow\mbox{BlockLDLQ}(\hat{W},\hat{H},C)$ (Sec. 4.1)

$\hat{W},S_{U},S_{V}$

Algorithm 2 QuIP$\\#$ Inference (for a Linear Layer)

0: $\hat{W}$, $S_{U},S_{V}$ from Alg. 1, $g$-dim. $k$-bit codebook $C$, input
$x\in\mathbb{R}^{n}$.

$y\leftarrow\texttt{Had}(S_{V}\odot x)$ where Had performs an orthogonal
Hadamard transform (Sec. 3)

$y\leftarrow\texttt{decompress_multiply}(\hat{W},C,y)$

$y\leftarrow\texttt{Had}(S_{U}\odot y)$

$y$

##  2 Background / Related Work

###  2.1 Compressing LLMs

A large body of work has focused on compressing LLMs, as doing so can directly
benefit LLM inference at scale. Methods such as pruning, quantization aware
training (QAT), and post-training quantization (PTQ) all focus on different
areas of this problem and are not strictly orthogonal to each other. Pruning
removes weights from models while preserving model quality and inference
performance (Chee et al., 2022; Sun et al., 2023). QAT focuses on training
models that are more “quantizable” but usually requires training models from
scratch (Nagel et al., 2022). PTQ, which QuIP$\\#$ falls under, instead
quantizes pre-trained models. PTQ generally requires much less compute than
QAT and achieve competitive performance (Chee et al., 2023; Frantar et al.,
2023; Shao et al., 2024; Egiazarian et al., 2024). For the rest of this paper,
we focus on the PTQ realm of LLM compression.

###  2.2 Quantization and Adaptive Rounding

In QuIP$\\#$, we follow existing state-of-the-art PTQ methods and round
weights to minimize the per-layer proxy loss, as formalized by Nagel et al.
(2020):

$\displaystyle\ell(\hat{W})$
$\displaystyle=E_{x}\left[\|(\hat{W}-W)x\|^{2}\right]$ (1)
$\displaystyle=\operatorname{tr}\left((\hat{W}-W)H(\hat{W}-W)^{T}\right).$ (2)

Here, $W\in\mathbb{R}^{m\times n}$ is the original weight matrix in a linear
layer, $\hat{W}\in\mathbb{R}^{m\times n}$ are the quantized weights,
$x\in\mathbb{R}^{n}$ is an input vector drawn uniformly at random from a
calibration set, and $H=E_{x}[xx^{T}]$ is a proxy Hessian. This intra-layer
formulation makes quantization tractable for LLMs. One way to minimize $\ell$
is to use adaptive rounding methods that iteratively round weight matrices by
considering the current rounding error for that specific matrix. For example,
the LDLQ111OPTQ(Frantar et al., 2023) and QuIP independently introduced
alternative formulations of this rounding method, and QuIP showed them to be
equivalent. LDLQ is the name given by QuIP. rounding algorithm iteratively
rounds rows of model weights using linear feedback from quantization error of
already rounded rows. LDLQ is optimal within the class of adaptive rounding
methods with linear feedback and offers provably better error rates than
nearest or stochastic rounding (Chee et al., 2023).

###  2.3 Incoherence Processing

Multiple works have observed that outliers in model activations and weights
can hinder quantization quality, motivating methods that “suppress” outliers
during quantization. For example, AWQ (Lin et al., 2023) scales model weights
by information from activations and OmniQuant (Shao et al., 2024) uses simple
learnable model-preserving transformations. However, these heuristic-based
approaches tend to fail at lower bitrates.

Instead, in QuIP, Chee et al. (2023) proposed that _incoherence_ is important
for LLM quantization. Informally, incoherent matrices have concentrated entry
magnitudes—ruling out outliers. In LLMs, incoherent weight and Hessian
matrices mean that both the thing being rounded (weights) and important
rounding directions (Hessians) are not too large in any coordinate. This
enables quantization with _provably_ bounded error.

######  Definition 2.1 (Chee et al. (2023)).

A Hessian $H\in\mathbb{R}^{n\times n}$ is $\mu$-incoherent if its
eigendecomposition $H=Q\Lambda Q^{T}$ has

$\textstyle\max_{i,j}\;|Q_{ij}|=\max_{i,j}\;|e_{i}^{T}Qe_{j}|\leq\mu/\sqrt{n}.$

A weight matrix $W\in\mathbb{R}^{m\times n}$ is $\mu$-incoherent if

$\max_{i,j}\;\textstyle|W_{ij}|=\max_{i,j}\;|e_{i}^{T}We_{j}|\leq\mu\|W\|_{F}/\sqrt{mn}.$

To exploit incoherence, Chee et al. (2023) introduced _incoherence processing_
as a part of their quantization method QuIP. QuIP’s incoherence processing
works by conjugating $W$ and $H$ by structured random orthogonal matrices.
Specifically, QuIP constructs orthogonal matrices $U\in\mathbb{R}^{m\times m}$
and $V\in\mathbb{R}^{n\times n}$ via a Kronecker product by drawing uniform
random orthogonal matrices $U_{1}$, $U_{2}$ (of sizes about $\sqrt{n}$),
$V_{1}$, and $V_{2}$ (of sizes about $\sqrt{m}$) and setting $U=U_{1}\otimes
U_{2}$ and $V=V_{1}\otimes V_{2}$. If we assign $\tilde{H}\leftarrow VHV^{T}$
and $\tilde{W}\leftarrow UWV^{T}$, $\tilde{H}$ and $\tilde{W}$ become
$\tilde{O}(1)$-incoherent with high probability (see their Lemma 5). Note that
this transformation preserves the proxy objective, as
$\operatorname{tr}\left((UWV^{T})(VHV^{T})(VW^{T}U^{T})\right)=\operatorname{tr}\left(WHW^{T}\right)$.
After quantizing the transformed weight matrix $\tilde{W}$ using $\tilde{H}$,
during inference, QuIP-quantized models transform model activations $x$ with
$V$ and $U^{T}$ to compute

$\textstyle U^{T}(\operatorname{quantized}(\tilde{W})(Vx))\approx
U^{T}(\tilde{W}(Vx))=Wx.$

These structured orthogonal multiplies by a Kronecker product lead to a
runtime overhead of $\Theta(n\sqrt{n}+m\sqrt{m})$, which is small relative to
the $\Theta(mn)$ cost of the multiply by $W$.

Incoherence processing can be seen as a principled alternative to more
complicated and heuristic methods for outlier suppression. Methods such as
grouping require extra storage and can negatively impact performance. For
example, using a 16 bit scale per group of 64 weights requires an extra 0.25
bits per weight. This increase is significant in extreme compression regimes,
whereas incoherence processing allows more bits to be spent on actually
quantizing model weights.

###  2.4 Vector Quantization

Prior PTQ works have focused on quantizing each scalar weight $W_{ij}$
individually (Chee et al., 2023; Lin et al., 2023; Shao et al., 2024).
However, this can be suboptimal as the resulting codebook has low density and
ignores the shape of the source distribution. Vector quantization (VQ) (Gray,
1984) instead quantizes a group of $d$ weights together by assigning them to a
$d$ dimensional vector from some codebook $C$. To effectively use VQ, $C$
should resemble the shape of the source distribution of $W$ and have high code
density. To quantize $v\in\mathbb{R}^{d}$ to $k$ bits per entry, $C$ should
have $2^{kd}$ entries. VQ becomes intractable when $kd$ is large, such as for
large $k$ or $d$. We resolve this exponential dependency on $d$ with our
rounding method BlockLDLQ in Section 4.1.

##  3 Incoherence Processing with the Randomized Hadamard Transform

Algorithm 3 Incoherence Processing with RHT (IP-RHT)

0: $W\in\mathbb{R}^{m\times n},H\in\mathbb{R}^{n\times n}$

Sample sign vectors $S_{V}\sim\mathcal{U}\\{\pm
1\\}^{n},S_{U}\sim\mathcal{U}\\{\pm 1\\}^{m}$

$\hat{W}\leftarrow\texttt{Had}(diag(S_{U})\texttt{Had}(diag(S_{V})W^{T})^{T})$
where Had is the Hadamard transform (sec. 3)

$\hat{H}\leftarrow\texttt{Had}(diag(S_{V})\texttt{Had}(diag(S_{V})H)^{T})$

$\hat{W},\hat{H},S_{U},S_{V}$

In this section, we propose a way of improving the incoherence processing of
QuIP by replacing the 2-factor Kronecker product by a Randomized Hadamard
Transformation (RHT) (Halko et al., 2011). This change yields three
advantages: (1) the theoretical bound on the incoherence parameter $\mu$ is
improved; (2) the asymptotic cost of multiplying by the structured random
orthogonal matrix is improved from $\Theta(n\sqrt{n})$ to $\Theta(n\log n)$;
(3) the cost to multiply is further reduced by a constant factor, since a
Hadamard matrix multiply can be performed without any floating-point
multiplies as its entries are in $\\{-1,+1\\}$. Additionally, we show in
Section 6.4 that this change by itself improves the perplexity of quantized
LLMs.

Recall from section 2.3 that one way to efficiently perform incoherence
processing is to conjugate $W$ and $H$ by structured random orthogonal
matrices. QuIP$\\#$ uses the RHT, which performs $x\to VSx$ where
$V\in\mathbb{R}^{n\times n}$ is a Hadamard matrix, $S$ is a random sign vector
$\\{\pm 1\\}^{n}$, and $x\in\mathbb{R}^{n}$. The RHT can be computed in
$O(n\log n)$ time with the Fast Walsh-Hadamard Transform (Fino & Algazi, 1976)
when $n$ is a power of $2$. We will temporarily assume that all dimensions are
powers of 2. Later in the section we will explain 2 methods for incoherence
processing when the dimension is not a power of 2.

lemmalemmahadincoh Let $H$ be any positive semidefinite matrix on
$\mathbb{R}^{n\times n}$ and $W$ any weight matrix on $\mathbb{R}^{m\times
n}$. Let $U\in\mathbb{R}^{m\times m}$ and $V\in\mathbb{R}^{n\times n}$ be
orthogonal scaled Hadamard matrices. Let $S_{U}\in\mathbb{R}^{m\times m}$ and
$S_{V}\in\mathbb{R}^{n\times n}$ be random diagonal matrices with independent
diagonal elements drawn uniformly from $\\{-1,+1\\}$. Then for any $\delta>0$,
$VS_{V}HS_{V}V^{T}$ is $\mu_{H}$-incoherent with probability at least
$1-\delta$, and $US_{U}WS_{V}V^{T}$ is $\mu_{W}$-incoherent with probability
at least $1-\delta$, where

$\mu_{H}=\sqrt{2\log\left(\frac{2n^{2}}{\delta}\right)}\;\;\text{ and
}\;\;\mu_{W}=2\log\left(\frac{4mn}{\delta}\right).$

In QuIP (Chee et al., 2023), the 2-factor Kronecker approach achieves
$\mu_{W}^{Kron}=A^{2}\log\left(4Cmn/\delta\right)^{2}$, where $A$ and $C$ are
global constants independent of $n$ and the number of factors. QuIP$\\#$’s RHT
achieves superior incoherence via a log dependence on the matrix size rather
that the Kronecker method’s log-squared dependence. All of QuIP’s theory
analyzing the proxy loss in Eq. (1) still holds with the RHT, with the
improved incoherence rates propagating through.

Now, what about dimensions $n$ that are not powers of 2? In most cases, we can
factorize $n=pq$ where that $p$ is the largest power of 2 such that there
exists a known Hadamard matrix of size $q$. This allows us to construct
$V\in\mathbb{R}^{n\times n}=H_{p}\otimes H_{q}$ where $H_{p}$ and $H_{q}$ are
size $p$ and $q$ Hadamard matrices, respectively. Then we can compute $VSx$ in
$O(q^{2}p\log p)$ time, which is faster than the $O(n(p+q))$ time of QuIP’s
2-factor Kronecker approach when $p\gg q$. For example, Llama 2 70B has
intermediate dimension $28672=1024*28$; $1024\gg 28$. Algorithm 3 describes
how to perform incoherence processing with the RHT. Doing so requires storing
two sign vectors $S_{U}\in\\{\pm 1\\}^{m}$ and $S_{V}\in\\{\pm 1\\}^{n}$.
Since $n,m\gg 1000$ for LLMs, $S_{U}$ and $S_{V}$ add less than 0.01 bits per
weight.

While the Hadamard conjecture states that $\exists H_{k}\forall k,4\mid k$,
finding such Hadamard matrices is still an open problem (Hedayat & Wallis,
1978). In cases when there does not exist a factorization $n=pq$ where
$\exists H_{p},H_{q}$, we present a Randomized Fast Fourier Transform (RFFT)
incoherence processing algorithm with similar runtime and concentration
properties as the RHT. At a high level, the RFFT performs incoherence
processing with the Fast Fourier Transform (FFT) (Cochran et al., 1967) and a
random complex phase. The RFFT only requires $n$ to be even, which is much
weaker than the RHT’s restrictions on $n$. The RFFT is also useful when there
does exist a decomposition $n=pq$ but $p\not\gg q$, resulting in reduced
speedups over an $\Theta(n\sqrt{n})$ algorithm. The FFT itself is also well
supported on a wide variety of hardware, meaning that it may be easier to
implement a fast RFFT when adapting QuIP$\\#$ to new hardware. In practice, we
find that the RFFT performs slightly worse than the RHT but still achieves
strong results (Table 1). We describe the RFFT in detail in Section A.2 in the
Appendix.

Table 1:  RHT vs. RFFT incoherence processing using 2 Bit QuIP$\\#$ (no FT). WikiText2 perplexity ($\downarrow$), context length 4096. Incoherence | 2-7B | 2-13B | 2-70B
---|---|---|---
Hadamard | 8.22 | 6.06 | 4.16
Fourier | 8.30 | 6.08 | 4.17

##  4 BlockLDLQ and Lattice Codebooks

The proof of Lemma 3 tells us that the incoherence-processed weights follow a
roughly ball-shaped sub-Gaussian distribution. However, rounding weights one
at a time, as QuIP does with its LDLQ, ignores this shaping—producing a set of
representable weight vectors that is shaped like a hypercube rather than a
ball. Vector quantization (VQ) lets us shape codebooks to better match the
source distribution. In Section 4.1, we introduce BlockLDLQ, which iteratively
rounds blocks of weights with VQ. Within BlockLDLQ’s VQ step, QuIP$\\#$ uses
the 2 bit E8P codebook (Section 4.2). E8P is based on the $E_{8}$ lattice,
which achieves the highest density unit ball packing in $\mathbb{R}^{8}$
(Viazovska, 2017). E8P achieves good shaping while admitting fast inference
from only needing to lookup from a size 256 codebook.

###  4.1 Adaptive Rounding for Vector Quantization

Chee et al. (2023) formulated a class of adaptive rounding algorithms with
linear feedback. These methods round columns one at a time with linear
feedback $a_{k}$ from the already rounded columns. Specifically, columns of a
weight matrix $W\in\mathbb{R}^{m\times n}$ are iteratively rounded for
$k=1,2,\dots,n$:
$\hat{W}_{k}=\mathcal{Q}(W_{k}+(W_{:(k-1)}-\hat{W}_{:(k-1)})a_{k}),$ where
$W_{k}$ is the $k$-th column of $W$, $W_{:(k-1)}$ is the first $k-1$ columns
of $W$, $\mathcal{Q}$ performs nearest or stochastic rounding, and
$a_{k}\in\mathbb{R}^{k-1}$. The resulting $\hat{W}$ satisfies
$\hat{W}=\mathcal{Q}(W+(W-\hat{W})U)$, where $U\in\mathbb{R}^{n\times n}$ is a
upper triangular matrix whose columns are $a_{k}$ and $\mathcal{Q}$ acts
elementwise.

The LDLQ algorithm sets U to be $L^{T}-I$ where $H=L^{T}DL$ is the LDL
decomposition of the proxy Hessian $H$. From QuIP, we know that LDLQ is
optimal within adaptive rounding methods with linear feedback when rounding to
the integers. However, LDLQ does not work with vector quantization, which
rounds multiple columns together.

We propose to extend LDLQ to support vector quantization. Given a block size
$g$ that evenly divides $n$, our block LDLQ is based on a novel $g$-block LDL
decomposition $H=\mathbf{L}^{T}\mathbf{D}\mathbf{L}$, where $\mathbf{L}$ is a
unit block lower triangular matrix (among the $n^{2}/g^{2}$ $g\times g$ blocks
of $L\in\mathbf{R}^{n\times n}$, the $n/g$ diagonal blocks are all $I$ and all
blocks above the diagonal are $0$), and $\mathbf{D}$ is a block diagonal
matrix.222It is straightforward to produce the $g$-block LDL decomposition
from the Cholesky decomposition of $H$. As before, we set
$\mathbf{U}=\mathbf{L}^{T}-I$, and round $W$ in a block-wise fashion via

$\hat{W}_{k}=\mathbf{Q}(W_{k}+(W_{:(k-1)}-\hat{W}_{:(k-1)})\mathbf{A}_{k}),$

where $\mathbf{A}_{k}\in\mathbb{R}^{n\times g}$ contains the $k-g+1$ through
$k$-th columns of $\mathbf{U}$ (the $k$th block), $W_{k}$ similarly denotes
the $k$th block of $W$, and $\mathbf{Q}$ denotes a vector quantizer. As in the
original QuIP paper, we can bound the error of this method. theoremthmLDLQ
Suppose that we round $W\in\mathbb{R}^{m\times n}$ using $g$-block LDLQ with
Hessian $H$, producing $\hat{W}$. Suppose that $H$ is $\mu$-incoherent, and
that we use a (possibly stochastic) vector quantizer $\mathbf{Q}$ that
satisfies
$\mathbf{E}[(\mathbf{Q}(x)-x)(\mathbf{Q}(x)-x)^{T}]\preceq\sigma^{2}I$ for any
$x\in\mathbb{R}^{g}$. Then

$\textstyle\mathbf{E}[\operatorname{tr}((\hat{W}-W)H(\hat{W}-W)^{T})]\leq\frac{gm\mu^{2}\sigma^{2}}{n}\operatorname{tr}(H^{1/2})^{2}.$

Observe that under the same conditions, just quantizing all blocks
independently would yield
$\mathbf{E}[\operatorname{tr}((\hat{W}-W)H(\hat{W}-W)^{T})]\leq
gm\sigma^{2}\operatorname{tr}(H)$: this “improvement” from the trace of $H$ to
the square of the trace of its square root divided by $n$ is the same factor
achieved in the scalar case in QuIP.333The original QuIP paper also included
multiple other technical guarantees, including a bound that considers more
rigorously the “real” case of finite-sized codebooks. While these results
could also be generalized to the block-LDLQ case, we view this as not
providing much insight relevant to QuIP$\\#$ beyond Theorem 4.1, so (if
desired) they are left as an exercise for the reader.

###  4.2 The E8P (“E8 Padded”) Codebook

BlockLDLQ relies on an internal vector quantization (VQ) step $\mathbf{Q}$
that rounds a $d$-dimension ($g$ in the previous section) vector to a codebook
$C$. To effectively apply VQ, $C$ should be shaped like the source
distribution and have high packing density. One way to improve shaping is by
increasing $d$. However, recall from Section 2.4 that to quantize a vector
$v\in\mathbb{R}^{d}$ to $k$ bits with VQ, $C$ must have size $2^{kd}\times d$.
Since the codebook size is exponential in both the vector dimension and
bitrate, VQ quickly becomes intractable at high dimensions or bitrates.

For QuIP$\\#$, we propose a novel 2-bit 8 dimensional _E8P codebook_ , which
contains $2^{16}$ entries but only requires lookups into a $2^{8}$-entry
table, with the remaining $8$ bits being used to store signs and shifts. E8P
bypasses the scaling issues of VQ by taking advantage of the structure and
symmetries of the $E_{8}$ lattice on which it is based. The $E_{8}$ lattice is
composed of all-integer or all-half-integer vectors in $\mathbb{R}^{8}$ whose
sum is an even number, that is

$\textstyle
E_{8}=\left(\mathbb{Z}^{8}\cup\left(\mathbb{Z}^{8}+\frac{1}{2}\right)\right)\cap\left\\{x\mid\mathbf{1}^{T}x\text{
is even}\right\\}.$

The construction of the E8P codebook starts with an equivalent way to write
$E_{8}$ via the $\hat{D}_{8}$ lattice, where
$\hat{D}_{8}=\left\\{x\in\mathbb{Z}^{8}+\frac{1}{2}\mid\mathbf{1}^{T}x\text{
is even}\right\\}$ is the set of half-integer vectors with even parity: here,
$E_{8}=\hat{D}_{8}\cup(\hat{D}_{8}+\frac{1}{2})$. It follows that
$(\hat{D}_{8}-\frac{1}{4})\cup(\hat{D}_{8}+\frac{1}{4})=E_{8}+\frac{1}{4}$ is
just a shifted copy of $E_{8}$ (keeping the same optimal packing density).

$\hat{D}_{8}$ has nice symmetry properties: flipping any (nonzero) even number
of signs of an element in $\hat{D}_{8}$, yields another distinct element in
$\hat{D}_{8}$. This means that if $|\hat{D}_{8}|$ denotes the set of
elementwise absolute values of entries in $\hat{D}_{8}$, then each element of
$\hat{D}_{8}$ can be expressed (uniquely) as the elementwise product of an
entry $s\in|\hat{D}_{8}|$ and a sign vector of appropriate parity. So, if we
start from some “source codebook” of absolute entries $S\subset|\hat{D_{8}}|$,
we can use the 128 possible odd- or even-parity sign flips to generate a
subset of $\hat{D_{8}}$. Each entry in $S$ is either an odd or even number of
flips away from an entry in $\hat{D_{8}}$, but not both. Thus, given $s\in S$
and 7 out of the 8 sign flips, we can infer the last one from the parity of
the 7 sign flips and $s$. This lets us use the following pattern to store a
16-bit codeword in $E_{8}+\frac{1}{4}$: 8 bits for the entry in $S$, 7 bits
for sign flips, and 1 bit to $\pm\frac{1}{4}$. This lets us decode a size
$2^{16}$ codebook by looking up into only a size $2^{8}$ codebook ($S$) and
performing some operations. All that remains is how to choose $S$: we set $S$
to be the 227 elements of $|\hat{D_{8}}|$ with norm $\leq\sqrt{10}$ plus 29
“padding” elements from $|\hat{D_{8}}|$ with norm $\sqrt{12}$ (see Section
C.1). We call this ball-shaped $2^{16}$-entry lattice codebook “E8P.”

Figure 3: Minimum achievable elementwise MSE of quantizing a Gaussian to
various codebooks. $E_{8}$-based codebooks outperform other presented
codebooks due to the underlying packing density and high dimensionality of
$E_{8}$.

Figure 3 plots the elementwise MSE of quantizing a standard multivariate
Gaussian to various $k$ bit codebooks. Each $k$-bit codebook consists of a
$d$-dimensional base lattice intersected with a ball to reach $2^{kd}$ points.
The $E_{8}$-based codebooks achieve lower MSEs than all other presented
codebooks, including those based on the $D_{4}$ lattice (the even-parity
vectors in $\mathbb{Z}^{4}$), which achieves the kissing number in
$\mathbb{R}^{4}$. This figure illustrates the importance of dimension for
vector quantization. Increasing the vector dimension decreases the error for
the half integer grid, as the resulting codebook is closer in shape to the
source distribution. Finally, while K-means on the source distribution would
achieve lower MSE (Lloyd, 1982), there are a number of practical reasons why a
K-means based codebook would be less practical, including worse end-to-end
empirical performance. We discuss this more in Section C.3.

###  4.3 Scaling $E_{8}$ to Higher Bitrates

The $E_{8}$ lattice works well for low bitrates (e.g. 2 bits), but quickly
becomes intractable at higher bitrates due to codebook size. In QuIP$\\#$, we
use residual vector quantization (RVQ) (Juang & Gray, 1982) to get the
benefits of lattice codebooks at higher bitrates. RVQ quantizes a vector $x$
to $p$ bits with a set $q$ of $q_{i}$-bit codebooks (denoted
$\mbox{RVQ}(x,p,q)$ where $p=\sum_{0\leq i<|q|}q_{i}$) by repeatedly
quantizing the quantization residual. That is, $\mbox{RVQ}(x,p,q)=\sum_{0\leq
i<|q|}\delta_{i}$ where $\delta_{i}=Q_{q_{i}}\left((x-\sum_{0\leq
j<i}\delta_{j})/s_{i}\right)\cdot s_{i}$, we let $Q_{q_{i}}(\cdot)$ denote
quantizing to a $q_{i}$ bit codebook, and $s_{i}\in\mathbb{R}$. Using RVQ, we
can quantize to 4 bits by rounding with the 2 bit E8P codebook twice. We can
also quantize to 3 bits by using the 2 bit E8P codebook and a 1-bit $E_{8}$
codebook (elements of $E_{8}$ with norm $\leq 2$ and 15 elements of $E_{8}$
with norm 4). One could also use more advanced multi-codebook quantization
approaches other than RVQ, but we found that RVQ was sufficient to achieve
strong quantization performance.

##  5 Fine-Tuning During Quantization

Recent works have suggested that at extreme quantization levels (e.g. 2 bits),
inter-layer interactions are a significant hurdle to lossless quantization
(Shao et al., 2024; Egiazarian et al., 2024). Here, we employ a simple fine-
tuning algorithm that attempts to recover the original unquantized model
during quantization. Our fine tuning method runs on a small development set
and works by relaxing the sign vectors in the RHT to arbitrary real vectors
after quantization.

Our fine tuning method contains two steps. First, we fine-tune within each
transformer block by quantizing the first linear layer, fine-tuning the
remaining parameters to match the unquantized model’s output activations on
the unquantized model’s input activations, quantizing the second linear layer,
fine-tuning, and so on until all linear layers are quantized. This step
attempts to minimize the activation error caused by an individual linear layer
during quantization, and it is parallelizable across transformer blocks as the
activation error does not consider the effect of quantizing preceding blocks.
The idea of fine-tuning on the level of a transformer block was previously
proposed in Egiazarian et al. (2024); our methodology differs in that we set a
different set of parameters to be trainable. In the second step, after all
linear layers in the model are quantized, the unquantized parameters
(layernorms, sign vectors, language model head) are fine-tuned to minimize
activation error over the entire model.

By optimizing the sign vectors as real vectors instead of binary vectors in
both steps, we allow the incoherence processing step to shape the weight
matrix to the codebook. While this means we must store the sign vectors in
FP16 instead of as bitvectors, the size of LLM matrices means that the sign
vectors still add less than 0.01 bits per weight. We describe these steps in
more detail in Section D.

##  6 Experiments

Table 2: Llama 1 & 2 Wikitext2 and C4 perplexity ($\downarrow$), context length 2048. |  | Wikitext 2 | C4
---|---|---|---
Method | Bits | 1-7 | 1-13 | 1-30 | 1-65 | 2-7 | 2-13 | 2-70 | 1-7 | 1-13 | 1-30 | 1-65 | 2-7 | 2-13 | 2-70
FP16 | 16 | 5.68 | 5.09 | 4.10 | 3.53 | 5.47 | 4.88 | 3.32 | 7.08 | 6.61 | 5.98 | 5.62 | 6.97 | 6.47 | 5.52
AWQ | 4 | 6.08 | 5.34 | 4.39 | 3.76 | 6.15 | 5.12 | - | 7.52 | 6.86 | 6.17 | 5.77 | 7.68 | 6.74 | -
OmniQ | 4 | 5.86 | 5.21 | 4.25 | 3.71 | 5.74 | 5.02 | 3.47 | 7.34 | 6.76 | 6.11 | 5.73 | 7.35 | 6.65 | 5.65
QuIP# no FT & no $E_{8}$ | 4 | 5.83 | 5.20 | 4.23 | 3.63 | 5.66 | 5.00 | 3.42 | 7.25 | 6.70 | 6.06 | 5.68 | 7.17 | 6.59 | 5.59
QuIP# | 4 | 5.76 | 5.17 | 4.18 | 3.60 | 5.56 | 4.95 | 3.38 | 7.18 | 6.67 | 6.03 | 5.66 | 7.07 | 6.54 | 5.56
AWQ | 3 | 11.9 | 7.45 | 10.0 | 5.21 | 24.0 | 10.5 | - | 13.3 | 9.13 | 12.7 | 7.11 | 23.9 | 13.1 | -
OmniQ | 3 | 6.49 | 5.68 | 4.74 | 4.04 | 6.58 | 5.58 | 3.92 | 8.19 | 7.32 | 6.57 | 6.07 | 8.65 | 7.44 | 6.06
QuIP# no FT & no $E_{8}$ | 3 | 6.29 | 5.52 | 4.54 | 3.91 | 6.19 | 5.34 | 3.71 | 7.82 | 6.98 | 6.29 | 5.86 | 7.85 | 6.98 | 5.78
QuIP# | 3 | 5.98 | 5.31 | 4.36 | 3.78 | 5.79 | 5.10 | 3.56 | 7.39 | 6.83 | 6.17 | 5.77 | 7.32 | 6.72 | 5.67
OmniQ | 2 | 15.5 | 13.2 | 8.71 | 7.58 | 37.4 | 17.2 | 7.81 | 24.9 | 18.3 | 13.9 | 10.8 | 90.6 | 26.8 | 12.3
QuIP# no FT & no $E_{8}$ | 2 | 9.95 | 7.18 | 5.80 | 5.02 | 12.3 | 7.60 | 4.87 | 11.7 | 8.67 | 7.55 | 6.83 | 14.8 | 9.57 | 6.82
QuIP# | 2 | 6.86 | 5.97 | 5.02 | 4.36 | 6.66 | 5.74 | 4.16 | 8.36 | 7.48 | 6.71 | 6.19 | 8.35 | 7.45 | 6.12
Table 3: Zeroshot Accuracy (acc in LM Eval, not acc_norm), Llama 2. | 2-70 | 2-13 | 2-7
---|---|---|---
Method | Bits | ArcC | ArcE | PiQA | Wino | Bits | ArcC | ArcE | PiQA | Wino | Bits | ArcC | ArcE | PiQA | Wino
FP16 | 16 | 51.1 | 77.7 | 81.1 | 77.0 | 16 | 45.6 | 73.3 | 73.5 | 69.6 | 16 | 40.0 | 69.3 | 78.5 | 67.3
OmniQ | 4 | 49.8 | 77.9 | 80.7 | 75.8 | 4 | 43.1 | 70.2 | 78.4 | 67.8 | 4 | 37.9 | 67.8 | 77.1 | 67.0
QuIP | 4 | 47.0 | 74.3 | 80.3 | 76.0 | 4 | 44.9 | 73.3 | 79.0 | 69.7 | 4 | - | - | - | -
AQLM | 4.07 | 51.0 | 78.1 | 81.4 | 76.9 | 3.94 | 43.9 | 72.2 | 78.6 | 70.4 | 4.04 | 40.3 | 68.9 | 77.7 | 67.3
QuIP# | 4 | 50.6 | 78.1 | 81.4 | 77.1 | 4 | 45.5 | 73.9 | 78.9 | 69.9 | 4 | 40.5 | 69.1 | 78.4 | 67.6
OmniQ | 3 | 47.6 | 75.7 | 79.7 | 73.5 | 3 | 42.0 | 69.0 | 77.7 | 65.9 | 3 | 35.3 | 62.6 | 73.6 | 63.6
QuIP | 3 | 46.3 | 73.2 | 80.0 | 74.6 | 3 | 41.5 | 70.4 | 76.9 | 69.9 | 3 | - | - | - | -
AQLM | 3.01 | 50.0 | 77.6 | 81.3 | 77.2 | 3.03 | 43.6 | 73.5 | 77.8 | 67.6 | 3.04 | 38.7 | 67.8 | 76.6 | 68.4
QuIP# | 3 | 50.9 | 77.7 | 81.4 | 76.4 | 3 | 44.0 | 72.5 | 78.4 | 69.1 | 3 | 39.2 | 68.4 | 77.3 | 66.5
OmniQ | 2 | 28.7 | 55.4 | 68.8 | 53.2 | 2 | 23.0 | 44.4 | 62.6 | 52.6 | 2 | 21.6 | 35.2 | 57.5 | 51.5
QuIP | 2 | 34.0 | 62.2 | 74.8 | 67.5 | 2 | 23.5 | 45.2 | 62.0 | 52.8 | 2 | 19.4 | 26.0 | 54.6 | 51.8
AQLM | 2.07 | 47.9 | 77.7 | 80.4 | 75.9 | 1.97 | 38.5 | 67.0 | 75.1 | 69.5 | 2.02 | 33.6 | 62.8 | 73.5 | 64.6
QuIP# | 2 | 48.7 | 77.3 | 80.3 | 75.9 | 2 | 39.5 | 69.3 | 77.3 | 67.7 | 2 | 34.6 | 64.6 | 75.1 | 64.9
Table 4: Wikitext2 and C4 perplexity ($\downarrow$), context length 4096. |  | 2-7 |  |  | 2-13 |  |  | 2-70 |
---|---|---|---|---|---|---|---|---|---
Method | Bits | W2 | C4 | Bits | W2 | C4 | Bits | W2 | C4
FP16 | 16 | 5.12 | 6.63 | 16 | 4.57 | 6.05 | 16 | 3.12 | 4.97
QuIP# | 4 | 5.19 | 6.75 | 4 | 4.63 | 6.13 | 4 | 3.18 | 5.02
no FT | 4 | 5.22 | 6.79 | 4 | 4.65 | 6.15 | 4 | 3.18 | 5.02
no $E_{8}$ | 4 | 5.29 | 6.86 | 4 | 4.68 | 6.20 | 4 | 3.22 | 5.05
QuIP | 4 | - | - | 4 | 4.76 | 6.29 | 4 | 3.58 | 5.38
AQLM | 4.04 | 5.21 | 6.74 | 3.94 | 4.64 | 6.14 | 4.07 | 3.17 | 5.01
QuIP# | 3 | 5.41 | 7.04 | 3 | 4.78 | 6.35 | 3 | 3.35 | 5.15
no FT | 3 | 5.60 | 7.34 | 3 | 4.90 | 6.50 | 3 | 3.41 | 5.20
no $E_{8}$ | 3 | 5.77 | 7.61 | 3 | 4.99 | 6.65 | 3 | 3.48 | 5.28
QuIP | 3 | - | - | 3 | 5.12 | 6.79 | 3 | 3.87 | 5.67
AQLM | 3.04 | 5.46 | 7.10 | 3.03 | 4.83 | 6.37 | 3.01 | 3.36 | 5.17
QuIP# | 2 | 6.19 | 8.16 | 2 | 5.35 | 7.20 | 2 | 3.91 | 5.71
no FT | 2 | 8.22 | 11.0 | 2 | 6.06 | 8.07 | 2 | 4.16 | 6.01
no $E_{8}$ | 2 | 11.2 | 14.5 | 2 | 7.04 | 9.37 | 2 | 4.58 | 6.51
QuIP | 2 | - | - | 2 | 13.5 | 16.2 | 2 | 5.90 | 8.17
AQLM | 2.02 | 6.93 | 8.84 | 1.97 | 5.70 | 7.59 | 2.07 | 3.94 | 5.72
Table 5: 2 and 4 bit QuIP$\\#$ Llama model generation speed measured on a NVIDIA RTX 4090 with a “proof of concept” CUDA implementation of E8P. QuIP$\\#$ achieves $>50\%$ peak memory bandwidth (1008GB/s) during generation and is fast and scalable. Model |  | 2 Bit
---
tok/s
| 2 Bit %
---
Mem BW
| 4 Bit
---
tok/s
| 4 Bit %
---
Mem BW
2-7B | 170.50 | 29.60% | 117.73 | 40.87%
2-13B | 104.83 | 33.80% | 71.09 | 45.84%
1-30B | 51.60 | 38.39% | 32.50 | 48.36%
2-70B | 32.74 | 56.84% | OOM | OOM
Figure 4: QuIP$\\#$ scaling, Llama 1. Like Llama 2, QuIP$\\#$ 3 bit scales
better than QuIP$\\#$ 4 bit for Llama 1 models and QuIP$\\#$ 2 bit scales
similarly to higher bitrates.

Our main experiments show the performance of QuIP$\\#$ on the Llama 1 (Touvron
et al., 2023a) and 2 (Touvron et al., 2023b) family of models. These models
range in size from 7 billion to 70 billion parameters and offer good
performance, making them suitable for understanding how quantization methods
perform and scale. Additional results for other models are available in the
Appendix.

In Section 6.1, we compare QuIP$\\#$ with recently published weight-only PTQ
methods. AWQ scales weights by activation magnitudes before quantizing to
reduce outliers (Lin et al., 2023). OmniQuant learns model-preserving
layerwise transformations that reduce outliers per transformer block (Shao et
al., 2024). AQLM uses additive quantization with learnable per-layer codebooks
and performs a fine-tuning step on codebook entries and layernorms (Egiazarian
et al., 2024). We also include QuIP (Chee et al., 2023) as a baseline for the
improvements in QuIP$\\#$.

We report W$x$A16 numbers for AWQ and OmniQuant from the OmniQuant paper and
AQLM numbers from AQLM. We note that there are currently 2 methods for
evaluating perplexity: using the Llama 1 context length of 2048 or using the
model’s native context length (e.g. 4096 for Llama 2). OmniQuant and AWQ use
2048 for Llama 2 while AQLM uses 4096; we report both sets of numbers. We also
note that AQLM paper reports QuIP$\\#$ numbers from an outdated version of
QuIP$\\#$. QuIP$\\#$ is under active development and the numbers here
represent the latest QuIP$\\#$ numbers. Finally, we bold numbers in our tables
when they are clearly better, such as a smaller model matching or
outperforming a larger model or a similar sized model significantly
outperforming another model.

###  6.1 QuIP$\\#$ on Llama Models

Table 2 shows a comparison of QuIP$\\#$ with OmniQuant, AWQ, and QuIP$\\#$(no
FT and no lattice codebook $E_{8}$) with context length 2048. QuIP$\\#$ offers
a paradigm shift in quantization quality over OmniQuant and AWQ. Notably,
while AWQ falls apart at even 2.15 bits (Shao et al., 2024) and OmniQuant
produces unusable models at 2 bits, QuIP$\\#$ produces high quality models
that are close to OmniQuant 3 bit models. Table 2 also shows the importance of
incoherence processing. QuIP$\\#$ without fine-tuning or lattice codebooks
significantly outperforms OmniQuant and AWQ, which both rely on heuristics to
reduce model outliers during quantization.

Table 4 shows a comparison of QuIP$\\#$ with AQLM with context length 4096.
QuIP$\\#$ offers strong improvements over AQLM at the 2 and 3 bit level,
either significantly outperforming similarly sized models or offering similar
performance with a smaller model444In our experience, at extreme quantization
levels, even 0.1 bits can make a significant difference in quantization
quality.. At the 4 bit level, QuIP$\\#$ and AQLM both perform similarly. This
is not surprising as state-of-the-art 4 bit models are all very close to FP16
performance. Furthermore, the QuIP$\\#$ 3 and 4 bit results presented in this
paper use residual vector quantization; one could potentially achieve better
numbers with more advanced multi-codebook quantization approaches.

Table 3 shows zeroshot results for QuIP$\\#$, AQLM, and OmniQuant. Both AQLM
and QuIP$\\#$ signficantly outperform OmniQuant, which correlates with the
perpelxity results. AQLM and QuIP$\\#$ both perform very close to FP16 at
higher bitrates and for larger models, but QuIP$\\#$ tends to outperform AQLM
at lower bitrates and model sizes. We note that zeroshot tasks have an element
of randomness and even FP16 numbers can disagree by up to $0.5\%$.

###  6.2 QuIP$\\#$ Bit Scaling

Figures 1 (first page) and 4 show how QuIP$\\#$ scales on the Llama family of
models and Wikitext2. On both Llama 1 and 2, QuIP$\\#$ 3 bit outperforms
QuIP$\\#$ 4 bit and QuIP$\\#$ 2 bit offers similar scaling to 3 and 4 bit
models. Furthermore, on Llama 2, QuIP$\\#$ 3 bit outperforms a theoretical
lossless 4 bit model (FP16 at 4 bits). To the best of our knowledge, this is
the first time a 3 bit PTQ method has outperformed a theoretical lossless 4
bit model and also the first time a 2 bit PTQ method has offered similar
scaling to higher bitrates.

###  6.3 Efficient Inference with QuIP$\\#$

Table 5 shows 2 and 4 bit QuIP$\\#$ Llama model generation speed measured on a
NVIDIA RTX 4090 GPU with a “proof of concept” CUDA implementation of E8P and
the FlashAttention library (Dao et al., 2022; Dao, 2023) implementation of
Llama. 4 bit generation speed is faster than 50% of the 2 bit speed since both
bitrates still need to perform two Hadamard multiplies per linear layer. We
note that we are not CUDA experts and a better optimized implementation of E8P
could likely achieve higher throughput. Nevertheless, we find that QuIP$\\#$
inference is fast and scalable on modern GPUs.

###  6.4 Ablations

Table 4 also contains an ablation on the various components of QuIP$\\#$. The
“no FT” row shows QuIP$\\#$ without fine-tuning and the “no $E_{8}$” row shows
QuIP$\\#$ without fine-tuning and lattice codebooks. For the latter, we round
to the 1-dimensional half-integer grid. We also include QuIP numbers as
reported by AQLM. At all bitrates, each component of QuIP$\\#$ brings
additional performance gains. The difference between QuIP and QuIP$\\#$
without fine-tuning and lattice codebooks also shows the difference between
QuIP’s Kronecker factorization and QuIP$\\#$’s RHT. The RHT offers stronger
incoherence properties than the Kronecker factorization (Section 3), which
improves performance.

##  7 Conclusion

We present QuIP$\\#$, a weight-only post training compression method that
achieves state-of-the-art results on LLMs at 2, 3, and 4 bits per weight.
QuIP$\\#$ uses the Randomized Hadamard Transform as am efficient and
principled form of outlier suppression, and introduces the $E_{8}$ lattice-
based E8P codebook to better quantize RHT transformed weights. The E8P
codebook is highly symmetric and admits fast inference, allowing a “proof of
concept” QuIP$\\#$ CUDA implementation to achieve over 50% peak memory
bandwidth on modern GPUs. QuIP$\\#$ also implements inter-layer fine tuning,
further improving quantization. To the best of our knowledge, QuIP$\\#$ is the
first PTQ method to achieve superior scaling at 3 bits over 4 bits and similar
scaling at 2 bits to higher bitrates. Our results indicate that, in the near
future, 2 bit models are likely to scale better than 3 bit ones.

##  8 Impact Statement

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## Acknowledgements

We thank, in no particular order, David Hou for helping with the QuIP$\\#$
CUDA implementation, Tiancheng Yuan for lending his RTX 4090 and helping with
acquiring QuIP$\\#$ timing numbers, Tri Dao for a fast CUDA implementation of
the Hadamard transform and general help with QuIP$\\#$, and Together AI for
compute resources.

## References

  * Almazrouei et al. (2023) Almazrouei, E., Alobeidli, H., Alshamsi, A., Cappelli, A., Cojocaru, R., Debbah, M., Étienne Goffinet, Hesslow, D., Launay, J., Malartic, Q., Mazzotta, D., Noune, B., Pannier, B., and Penedo, G.  The falcon series of open language models, 2023.
  * Cai et al. (2024) Cai, T., Li, Y., Geng, Z., Peng, H., Lee, J. D., Chen, D., and Dao, T.  Medusa: Simple llm inference acceleration framework with multiple decoding heads.  _arXiv preprint arXiv: 2401.10774_ , 2024.
  * Chee et al. (2022) Chee, J., Renz, M., Damle, A., and Sa, C. D.  Model preserving compression for neural networks.  In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=gt-l9Hu2ndd.
  * Chee et al. (2023) Chee, J., Cai, Y., Kuleshov, V., and Sa, C. D.  QuIP: 2-bit quantization of large language models with guarantees.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=xrk9g5vcXR.
  * Cochran et al. (1967) Cochran, W., Cooley, J., Favin, D., Helms, H., Kaenel, R., Lang, W., Maling, G., Nelson, D., Rader, C., and Welch, P.  What is the fast fourier transform?  _Proceedings of the IEEE_ , 55(10):1664–1674, 1967.  doi: 10.1109/PROC.1967.5957.
  * Computer (2023) Computer, T.  Redpajama: An open source recipe to reproduce llama training dataset, 2023.  URL https://github.com/togethercomputer/RedPajama-Data.
  * Dao (2023) Dao, T.  FlashAttention-2: Faster attention with better parallelism and work partitioning.  2023\.
  * Dao et al. (2022) Dao, T., Fu, D. Y., Ermon, S., Rudra, A., and Ré, C.  FlashAttention: Fast and memory-efficient exact attention with IO-awareness.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Dettmers & Zettlemoyer (2023) Dettmers, T. and Zettlemoyer, L.  The case for 4-bit precision: k-bit inference scaling laws.  In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), _Proceedings of the 40th International Conference on Machine Learning_ , volume 202 of _Proceedings of Machine Learning Research_ , pp. 7750–7774. PMLR, 23–29 Jul 2023.  URL https://proceedings.mlr.press/v202/dettmers23a.html.
  * Egiazarian et al. (2024) Egiazarian, V., Panferov, A., Kuznedelev, D., Frantar, E., Babenko, A., and Alistarh, D.  Extreme compression of large language models via additive quantization, 2024.
  * Fino & Algazi (1976) Fino and Algazi.  Unified matrix treatment of the fast walsh-hadamard transform.  _IEEE Transactions on Computers_ , C-25(11):1142–1146, 1976.  doi: 10.1109/TC.1976.1674569.
  * Frantar et al. (2023) Frantar, E., Ashkboos, S., Hoefler, T., and Alistarh, D.  OPTQ: Accurate quantization for generative pre-trained transformers.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=tcbBPnfwxS.
  * Gao et al. (2023) Gao, L., Tow, J., Abbasi, B., Biderman, S., Black, S., DiPofi, A., Foster, C., Golding, L., Hsu, J., Le Noac’h, A., Li, H., McDonell, K., Muennighoff, N., Ociepa, C., Phang, J., Reynolds, L., Schoelkopf, H., Skowron, A., Sutawika, L., Tang, E., Thite, A., Wang, B., Wang, K., and Zou, A.  A framework for few-shot language model evaluation, 12 2023.  URL https://zenodo.org/records/10256836.
  * Gray (1984) Gray, R.  Vector quantization.  _IEEE ASSP Magazine_ , 1(2):4–29, 1984.  doi: 10.1109/MASSP.1984.1162229.
  * Halko et al. (2011) Halko, N., Martinsson, P.-G., and Tropp, J. A.  Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.  _SIAM review_ , 53(2):217–288, 2011.
  * Hedayat & Wallis (1978) Hedayat, A. and Wallis, W. D.  Hadamard Matrices and Their Applications.  _The Annals of Statistics_ , 6(6):1184 – 1238, 1978.  doi: 10.1214/aos/1176344370.  URL https://doi.org/10.1214/aos/1176344370.
  * Jiang et al. (2024) Jiang, A. Q., Sablayrolles, A., Roux, A., Mensch, A., Savary, B., Bamford, C., Chaplot, D. S., de las Casas, D., Hanna, E. B., Bressand, F., Lengyel, G., Bour, G., Lample, G., Lavaud, L. R., Saulnier, L., Lachaux, M.-A., Stock, P., Subramanian, S., Yang, S., Antoniak, S., Scao, T. L., Gervet, T., Lavril, T., Wang, T., Lacroix, T., and Sayed, W. E.  Mixtral of experts, 2024.
  * Juang & Gray (1982) Juang, B.-H. and Gray, A.  Multiple stage vector quantization for speech coding.  In _ICASSP ’82. IEEE International Conference on Acoustics, Speech, and Signal Processing_ , volume 7, pp. 597–600, 1982.  doi: 10.1109/ICASSP.1982.1171604.
  * Kingma & Ba (2017) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization, 2017.
  * Lin et al. (2023) Lin, J., Tang, J., Tang, H., Yang, S., Dang, X., Gan, C., and Han, S.  Awq: Activation-aware weight quantization for llm compression and acceleration, 2023.
  * Lloyd (1982) Lloyd, S.  Least squares quantization in pcm.  _IEEE Transactions on Information Theory_ , 28(2):129–137, 1982.  doi: 10.1109/TIT.1982.1056489.
  * Nagel et al. (2020) Nagel, M., Amjad, R. A., Van Baalen, M., Louizos, C., and Blankevoort, T.  Up or down? Adaptive rounding for post-training quantization.  In III, H. D. and Singh, A. (eds.), _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 7197–7206. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/nagel20a.html.
  * Nagel et al. (2022) Nagel, M., Fournarakis, M., Bondarenko, Y., and Blankevoort, T.  Overcoming oscillations in quantization-aware training.  In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pp. 16318–16330. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/nagel22a.html.
  * Nguyen et al. (2023) Nguyen, E., Poli, M., Faizi, M., Thomas, A., Birch-Sykes, C., Wornow, M., Patel, A., Rabideau, C., Massaroli, S., Bengio, Y., Ermon, S., Baccus, S. A., and Ré, C.  Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution.  2023\.
  * Rozière et al. (2024) Rozière, B., Gehring, J., Gloeckle, F., Sootla, S., Gat, I., Tan, X. E., Adi, Y., Liu, J., Sauvestre, R., Remez, T., Rapin, J., Kozhevnikov, A., Evtimov, I., Bitton, J., Bhatt, M., Ferrer, C. C., Grattafiori, A., Xiong, W., Défossez, A., Copet, J., Azhar, F., Touvron, H., Martin, L., Usunier, N., Scialom, T., and Synnaeve, G.  Code llama: Open foundation models for code, 2024.
  * Shao et al. (2024) Shao, W., Chen, M., Zhang, Z., Xu, P., Zhao, L., Li, Z., Zhang, K., Gao, P., Qiao, Y., and Luo, P.  Omniquant: Omnidirectionally calibrated quantization for large language models.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=8Wuvhh0LYW.
  * (27) Sloane, N.  Hadamard Matrices — neilsloane.com.  http://neilsloane.com/hadamard/.  [Accessed 02-02-2024].
  * Sun et al. (2023) Sun, M., Liu, Z., Bair, A., and Kolter, J. Z.  A simple and effective pruning approach for large language models.  In _Workshop on Efficient Systems for Foundation Models @ ICML2023_ , 2023.  URL https://openreview.net/forum?id=tz9JV2PRSv.
  * Touvron et al. (2023a) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., and Lample, G.  Llama: Open and efficient foundation language models, 2023a.
  * Touvron et al. (2023b) Touvron, H., Martin, L., Stone, K., Albert, P., Almahairi, A., Babaei, Y., Bashlykov, N., Batra, S., Bhargava, P., Bhosale, S., Bikel, D., Blecher, L., Ferrer, C. C., Chen, M., Cucurull, G., Esiobu, D., Fernandes, J., Fu, J., Fu, W., Fuller, B., Gao, C., Goswami, V., Goyal, N., Hartshorn, A., Hosseini, S., Hou, R., Inan, H., Kardas, M., Kerkez, V., Khabsa, M., Kloumann, I., Korenev, A., Koura, P. S., Lachaux, M.-A., Lavril, T., Lee, J., Liskovich, D., Lu, Y., Mao, Y., Martinet, X., Mihaylov, T., Mishra, P., Molybog, I., Nie, Y., Poulton, A., Reizenstein, J., Rungta, R., Saladi, K., Schelten, A., Silva, R., Smith, E. M., Subramanian, R., Tan, X. E., Tang, B., Taylor, R., Williams, A., Kuan, J. X., Xu, P., Yan, Z., Zarov, I., Zhang, Y., Fan, A., Kambadur, M., Narang, S., Rodriguez, A., Stojnic, R., Edunov, S., and Scialom, T.  Llama 2: Open foundation and fine-tuned chat models, 2023b.
  * Viazovska (2017) Viazovska, M.  The sphere packing problem in dimension $8$.  _Annals of Mathematics_ , 185(3), May 2017.  ISSN 0003-486X.  doi: 10.4007/annals.2017.185.3.7.  URL http://dx.doi.org/10.4007/annals.2017.185.3.7.

##  Appendix A Concentration Inequalities for the Randomized Hadamard
Transform and Fast Fourier Transform

###  A.1 Incoherence Processing with the Randomized Hadamard Transform

######  Lemma A.1.

For any non-negative real number $n$,

$\frac{1}{B\left(n,1/2\right)}\int_{-1}^{+1}(1-x^{2})^{n-1}\cdot\exp(tx)\;dx\leq\exp\left(\frac{t^{2}}{4n+2}\right).$

###### Proof.

We start with the following “standard” integral. For non-negative integer $m$
and real $n>0$,

$\displaystyle\int_{-1}^{+1}x^{2m}(1-x^{2})^{n-1}\;dx=B\left(m+\frac{1}{2},n\right)=\frac{\Gamma\left(m+\frac{1}{2}\right)\Gamma\left(n\right)}{\Gamma\left(m+n+\frac{1}{2}\right)}.$

This means that

$\displaystyle\frac{1}{B\left(\frac{1}{2},n\right)}\int_{-1}^{+1}x^{2m}(1-x^{2})^{n-1}\;dx$
$\displaystyle=\frac{B\left(m+\frac{1}{2},n\right)}{B\left(\frac{1}{2},n\right)}$
$\displaystyle=\frac{\Gamma\left(m+\frac{1}{2}\right)\Gamma\left(n\right)}{\Gamma\left(m+n+\frac{1}{2}\right)}\cdot\frac{\Gamma\left(n+\frac{1}{2}\right)}{\Gamma\left(\frac{1}{2}\right)\Gamma\left(n\right)}$
$\displaystyle=\frac{\Gamma\left(m+\frac{1}{2}\right)\Gamma\left(n+\frac{1}{2}\right)}{\sqrt{\pi}\cdot\Gamma\left(m+n+\frac{1}{2}\right)}.$

Applying the Legendre duplication formula, for integer $m$,

$\Gamma\left(m+\frac{1}{2}\right)=\frac{(2m)!\sqrt{\pi}}{4^{m}m!},$

then

$\displaystyle\frac{1}{B\left(\frac{1}{2},n\right)}\int_{-1}^{+1}x^{2m}(1-x^{2})^{n-1}\;dx$
$\displaystyle=\frac{(2m)!\sqrt{\pi}}{4^{m}m!}\cdot\frac{(2n)!\sqrt{\pi}}{4^{n}n!}\cdot\frac{1}{\sqrt{\pi}}\cdot\frac{4^{m+n}(m+n)!}{(2m+2n)!\sqrt{\pi}}$
$\displaystyle=\frac{(2m)!(2n)!(m+n)!}{m!n!(2m+2n)!}.$

In particular, this means that

$\displaystyle\frac{1}{B\left(\frac{1}{2},n\right)}\int_{-1}^{+1}\exp(tx)(1-x^{2})^{n-1}\;dx$
$\displaystyle=\sum_{m=0}^{\infty}\frac{t^{2m}}{(2m)!}\cdot\frac{1}{B\left(\frac{1}{2},n\right)}\int_{-1}^{+1}x^{2m}(1-x^{2})^{n-1}\;dx$
$\displaystyle=\sum_{m=0}^{\infty}\frac{t^{2m}}{(2m)!}\cdot\frac{(2m)!(2n)!(m+n)!}{m!n!(2m+2n)!}$
$\displaystyle=\sum_{m=0}^{\infty}\frac{t^{2m}}{m!}\cdot\frac{(2n)!(m+n)!}{n!(2m+2n)!}$
$\displaystyle=\sum_{m=0}^{\infty}\frac{t^{2m}}{m!}\cdot\prod_{k=1}^{m}\frac{k+n}{(2k+2n)(2k+2n-1)}$
$\displaystyle=\sum_{m=0}^{\infty}\frac{t^{2m}}{m!}\cdot\frac{1}{2^{m}}\prod_{k=1}^{m}\frac{1}{2k+2n-1}$
$\displaystyle\leq\sum_{m=0}^{\infty}\frac{t^{2m}}{m!}\cdot\frac{1}{2^{m}}\left(\frac{1}{2n+1}\right)^{m}$
$\displaystyle=\sum_{m=0}^{\infty}\frac{1}{m!}\left(\frac{t^{2}}{4n+2}\right)^{m}$
$\displaystyle=\exp\left(\frac{t^{2}}{4n+2}\right).$

This proves the lemma

$\frac{1}{B\left(n,1/2\right)}\int_{-1}^{+1}(1-x^{2})^{n-1}\cdot\exp(tx)\;dx\leq\exp\left(\frac{t^{2}}{4n+2}\right).$

∎

######  Lemma A.2.

Call $U\in\mathbb{R}^{nd\times nd}$ an $(n,d)$-block orthohadamard matrix if
it has the following properties: (1) $U$ is a orthogonal matrix, and (2) each
aligned $d\times d$ block of $U$ is $1/\sqrt{n}$ times an orthogonal matrix.
This generalizes the notion of Hadamard matrices. Let
$S\in\mathbb{R}^{nd\times nd}$ be a random block diagonal matrix, where each
$d\times d$ block of the diagonal is sampled independently and uniformly from
the set of (possibly special) orthogonal matrices. Then we call multiplication
by $US$ a _randomized orthohadamard transform_ , and observe that it has the
following nice property. Let $x\in\mathbb{R}^{nd}$ be any fixed vector, and
let $b\in\mathbb{R}^{nd}$ be a fixed vector that is _sparse_ in the sense that
it is supported only on a single $d$-sized aligned block (i.e. all but one of
the $n$ blocks are zero). Then

$\mathbf{P}\left(\left|b^{T}USx\right|\geq a\right)\leq
2\exp\left(-\frac{a^{2}nd}{2\left\|b\right\|^{2}\left\|x\right\|^{2}}\right).$

###### Proof.

If we let the $i$th block of $x$ be $x_{i}\in\mathbb{R}^{d}$ and let the $i$th
block of $S^{T}U^{T}b^{T}$ be $v_{i}$, then the $v_{i}$ will be independent
and uniformly distributed on the sphere in $d$ dimensional space of radius
$\left\|b\right\|/\sqrt{n}$, and so
$v_{i}^{T}x_{i}=\left\|b\right\|\left\|x_{i}\right\|n^{-1/2}z_{i}$, where the
$z_{i}$ are all independent and distributed according to an entry of a random
point on the unit sphere in $d$ dimensional space. Observe that this means
that

$\mathbf{P}(z_{i})\propto(1-z_{i}^{2})^{\frac{d-1}{2}-1}.$

So,

$\displaystyle\mathbf{E}\left[\exp\left(tb^{T}USx\right)\right]$
$\displaystyle=\mathbf{E}\left[\exp\left(t\sum_{i=1}^{n}\left\|b\right\|\left\|x_{i}\right\|n^{-1/2}z_{i}\right)\right]$
$\displaystyle=\prod_{i=1}^{n}\mathbf{E}\left[\exp\left(t\left\|b\right\|\left\|x_{i}\right\|n^{-1/2}z_{i}\right)\right]$
$\displaystyle\leq\prod_{i=1}^{n}\mathbf{E}\left[\exp\left(\frac{1}{4\cdot\frac{d-1}{2}+2}\right)\left(t\left\|b\right\|\left\|x_{i}\right\|n^{-1/2}\right)^{2}\right]$
$\displaystyle=\prod_{i=1}^{n}\mathbf{E}\left[\exp\left(\frac{t^{2}\left\|b\right\|^{2}\left\|x_{i}\right\|^{2}}{2nd}\right)\right]$
$\displaystyle=\mathbf{E}\left[\exp\left(\frac{t^{2}\left\|b\right\|^{2}\left\|x\right\|^{2}}{2nd}\right)\right],$

where the the last line follows from Lemma A.1. It follows from the standard
application of Markov’s inequality that for any $a>0$,

$\mathbf{P}\left(\left|b^{T}USx\right|\geq a\right)\leq
2\exp\left(-\frac{a^{2}nd}{2\left\|b\right\|^{2}\left\|x\right\|^{2}}\right).$

This is what we wanted to show. ∎

######  Lemma A.3.

Let $H\in\mathbb{R}^{n\times n}$ be an orthogonal scaled Hadamard matrix or
$F\in\mathbb{R}^{n\times n}$ be an orthogonal FFT matrix (the FFT understood
as operating on a real vector space). Let $S\in\mathbb{R}^{n\times n}$ be a
random diagonal matrix with diagonal elements supported on $\mathbb{R}^{n}$,
and let $P\in\mathbb{R}^{n\times n}$ be a random 2-block-diagonal matrix with
$2\times 2$ diagonal blocks supported on $\operatorname{SO}(2)$ (we can also
think of this as acting like a diagonal complex matrix with each diagonal
element a random complex number of absolute value $1$). Let
$U\in\mathbb{R}^{n\times n}$ be any fixed orthogonal matrix. Then, for any
$\epsilon>0$,

$\operatorname{Prob}\left(\max_{i,j}\left|e_{i}^{T}HSUe_{j}\right|\geq\sqrt{\frac{2}{nd}\log\left(\frac{2n^{2}}{\epsilon}\right)}\right)\leq\epsilon$

and

$\operatorname{Prob}\left(\max_{i,j}\left|e_{i}^{T}FPUe_{j}\right|\geq\sqrt{\frac{2}{nd}\log\left(\frac{2n^{2}}{\epsilon}\right)}\right)\leq\epsilon.$

That is, with probability at least $1-\epsilon$, multiplying by either $HS$ or
$FP$ makes the resulting orthogonal matrix $\mu$-incoherent, where

$\mu_{H}=\sqrt{2\log\left(\frac{2n^{2}}{\epsilon}\right)}.$

###### Proof.

Setting $b=e_{i}$ and $x=Ue_{j}$ in Lemma A.2,

$\mathbf{P}\left(\left|e_{i}^{T}HSUe_{j}\right|\geq a\right)\leq
2\exp\left(-\frac{a^{2}nd}{2}\right).$

By the union bound,

$\mathbf{P}\left(\max_{i,j}\left|e_{i}^{T}HSUe_{j}\right|\geq a\right)\leq
2n^{2}\exp\left(-\frac{a^{2}nd}{2}\right).$

Setting

$a^{2}=\frac{2}{nd}\log\left(\frac{2n^{2}}{\epsilon}\right)$

proves the lemma. The FFT case is identical. ∎

######  Lemma A.4.

Let $H_{L}\in\mathbb{R}^{m\times m}$ be an orthogonal scaled Hadamard matrix
or $F\in\mathbb{R}^{m\times m}$ be an orthogonal FFT matrix (the FFT
understood as operating on a real vector space). Let
$S_{L}\in\mathbb{R}^{m\times m}$ be a random diagonal matrix with diagonal
elements supported on $\mathbb{R}^{m}$, and let $P\in\mathbb{R}^{m\times m}$
be a random 2-block-diagonal matrix with $2\times 2$ diagonal blocks supported
on $\operatorname{SO}(2)$. Let $H_{R}\in\mathbb{R}^{n\times n}$, $F_{R}$,
$S_{R}$, and $P_{R}$ be defined analogously over $n$-dimensional space. Let
$W\in\mathbb{R}^{m\times n}$ be any fixed matrix. Then, for any $\epsilon>0$,

$\mathbf{P}\left(\max_{i,j}\left|e_{i}^{T}H_{L}S_{L}WS_{R}^{T}H_{R}^{T}e_{j}\right|\geq\left\|W\right\|_{F}\sqrt{\frac{4}{mn}}\log\left(\frac{4mn}{\epsilon}\right)\right)\leq\epsilon.$

and

$\mathbf{P}\left(\max_{i,j}\left|e_{i}^{T}F_{L}P_{L}WP_{R}^{T}F_{R}^{T}e_{j}\right|\geq\left\|W\right\|_{F}\sqrt{\frac{4}{mn}}\log\left(\frac{4mn}{\epsilon}\right)\right)\leq\epsilon.$

That is, with probability at least $1-\epsilon$, multiplying on both sides by
a randomized Hadamard transform or a randomized FFT yields a weight matrix
that is $\mu_{W}$-incoherent, where

$\mu_{W}=2\log\left(\frac{4mn}{\epsilon}\right).$

###### Proof.

From Lemma A.2,

$\mathbf{P}\left(\left|b^{T}USx\right|\geq\left\|b\right\|\left\|x\right\|\sqrt{\frac{2}{n}\log\left(\frac{4mn}{\epsilon}\right)}\right)\leq\frac{\epsilon}{2mn}.$

By applying this once on each side to the rows and columns respectively, and
union bounding over the $mn$ entries, we get

$\mathbf{P}\left(\left|e_{i}^{T}H_{L}S_{L}WS_{R}^{T}H_{R}^{T}e_{j}\right|\geq\left\|W\right\|_{F}\sqrt{\frac{4}{mn}}\log\left(\frac{4mn}{\epsilon}\right)\right)\leq\epsilon.$

The proof in the FFT case is identical. ∎

*

###### Proof.

The incoherence of $H$ follows from the application of Lemma A.3. The
incoherence of $W$ follows from the application of Lemma A.4. ∎

###  A.2 Incoherence Processing with the Randomized Fast Fourier Transform
(RFFT)

Algorithm 4 Incoherence Processing with RFFT (IP-RFFT)

0: $W\in\mathbb{R}^{m\times n},H\in\mathbb{R}^{n\times n}$

Sample phase vectors $\theta_{V}\sim\mathcal{U}[0,2\pi]^{n/2}$,
$\theta_{U}\sim\mathcal{U}[0,2\pi]^{m/2}$
$S_{V}=\cos(\theta_{V})+i\sin(\theta_{V})$,
$S_{U}=\cos(\theta_{U})+i\sin(\theta_{U})$

$\hat{W}\leftarrow\texttt{FFT}(diag(S_{U})\texttt{FFT}(diag(S_{V})W^{T})^{T})$
where FFT is the Fast Fourier transform (Sec. A.2)

$\hat{H}\leftarrow\texttt{FFT}(diag(S_{V})\texttt{FFT}(diag(S_{V})H)^{T})$

$\hat{W},\hat{H},S_{U},S_{V}$

Here we described the Randomized Fast Fourier Transform (RFFT), $x\to VSx$
where $V\in\mathbb{C}^{n/2\times n/2}$ is the discrete Fourier transform
matrix, $S\in\mathbb{C}^{n/2}$ is a random complex phase vector, and
$x\in\mathbb{R}^{n}$. The discrete Fourier transform can be computed in
$O(n\log n)$ time via the fast Fourier transform. Here it is understood that
the FFT operates over the reals, in that a vector $x\in\mathbb{R}^{n}$ is
mapped to a complex representation $\mathbb{C}^{n/2}$, the RFFT is performed,
and the resulting vector mapped back to $\mathbb{R}^{n}$. Here the mapping
simply represents reshaping real-valued $x$ into dimension $(n/2,2)$, and
interpreting the corresponding 2-tuples as a complex number.

Incoherence processing via the RFFT achieves similar theoretical guarantees as
the RHT, see Lemmas A.3 and A.4. Ultimately the choice of the orthogonal
transformation is up to the user. A Fourier transform works almost as well as
a Hamard transform in practice (Table 1), so if a fast Hadamard implementation
is not available, the FFT is a good option.

##  Appendix B Block LDLQ

######  Lemma B.1.

Let $H\in\mathbb{R}^{nd\times nd}$ be a positive definite matrix with
$d$-block LDL decomposition $H=L^{T}DL$. Then

$\operatorname{tr}\left(D\right)\leq\operatorname{tr}\left(H^{1/2}\right)\cdot\left\|H^{1/2}\odot
M_{D}\right\|_{2},$

where $M_{D}=I\otimes\mathbf{1}_{d\times d}$ is the block diagonal mask. If,
in addition, $H$ is $\mu$-incoherent in the sense that its matrix of
eigenvectors $U$ has

$\|U_{ij}\|\leq\frac{\mu}{\sqrt{nd}},$

then

$\operatorname{tr}\left(D\right)\leq\frac{\mu^{2}}{n}\operatorname{tr}\left(H^{1/2}\right)^{2}.$

###### Proof.

Consider the optimization problem

minimize: $\displaystyle\operatorname{tr}\left(R^{T}HR\right)$ subject to:
$\displaystyle R\text{ unit block lower diagonal}.$

Observe that the derivative of the loss is

$\nabla f(R)=HR.$

If $R=L^{-1}$, then $HR=L^{T}D$. But this must be a block upper triangular
matrix, because it’s the product of a unit upper triangular matrix ($L^{T}$)
and a block diagonal matrix $D$. It follows that $\nabla f(L^{-1})$ is zero in
all the directions in which we could move $R$, since $R$ only varies in the
strictly lower triangular directions. Therefore, $R=L^{-1}$ is the solution to
this optimization problem, and for any $R$, $\nabla f(R)\geq\nabla
f(L^{-1})=\operatorname{tr}\left(D\right)$.

Now, let $M$ denote the strictly block lower triangular mask, and observe that
$M+M^{T}+M_{D}=\mathbf{1}_{nd\times nd}$. Set $\alpha=\left\|H^{1/2}\odot
M_{D}\right\|_{2}^{-1}$, and consider $R=\left(I+\alpha M\odot
H^{1/2}\right)^{-1}$. Observe that

$\displaystyle\left(I+\alpha M\odot H^{1/2}\right)^{T}\left(I+\alpha M\odot
H^{1/2}\right)$ $\displaystyle=I+\alpha M\odot H^{1/2}+\alpha M^{T}\odot
H^{1/2}+\alpha^{2}(M^{T}\odot H^{1/2})(M\odot H^{1/2})$ $\displaystyle\succeq
I+\alpha(M+M^{T})\odot H^{1/2}$ $\displaystyle\succeq\alpha M_{D}\odot
H^{1/2}+\alpha(M+M^{T})\odot H^{1/2}$ $\displaystyle\succeq\alpha H^{1/2}.$

It follows by inverting both sides that $RR^{T}\preceq\alpha^{-1}H^{-1/2}$.

So, for this $R$,

$\operatorname{tr}\left(R^{T}HR\right)=\operatorname{tr}\left(HRR^{T}\right)\leq\alpha^{-1}\operatorname{tr}\left(H^{1/2}\right).$

This proves the first part of the lemma. For the second part, observe that

$\displaystyle\left\|H^{1/2}\odot M_{D}\right\|_{2}$
$\displaystyle\leq\sum_{i=1}^{nd}\lambda_{i}^{1/2}\left\|(u_{i}u_{i}^{T})\odot
M_{D}\right\|_{2}$
$\displaystyle\leq\frac{\mu^{2}}{n}\operatorname{tr}\left(H^{1/2}\right).$

This proves the lemma. ∎

*

###### Proof.

First recall that from the description of block LDLQ,

$\hat{W}_{k}=\mathbf{Q}(W_{k}+(W_{:(k-1)}-\hat{W}_{:(k-1)})\mathbf{A}_{k}).$

We can also write this in matrix form in terms of the matrix $\mathbf{L}_{k}$
as

$\hat{W}=\mathbf{Q}(W+(W-\hat{W})(\mathbf{L}^{T}-I)).$

Here, $\mathbf{Q}$ is interpreted as operating independently block-wise. Let
$\eta$ denote the quantization error

$\eta=(W+(W-\hat{W})(\mathbf{L}^{T}-I))-\mathbf{Q}(W+(W-\hat{W})(\mathbf{L}^{T}-I)).$

Then

$\hat{W}=(W+(W-\hat{W})(\mathbf{L}^{T}-I))-\eta,$

which simplifies to

$(W-\hat{W})\mathbf{L}^{T}=\eta.$

This means that

$\mathbf{E}[\operatorname{tr}((\hat{W}-W)H(\hat{W}-W)^{T})]=\mathbf{E}[\operatorname{tr}((\hat{W}-W)\mathbf{L}^{T}\mathbf{D}\mathbf{L}(\hat{W}-W)^{T})]=\mathbf{E}[\operatorname{tr}(\eta^{T}\mathbf{D}\eta)].$

But by assumption, $\mathbf{E}[\eta\eta^{T}]\preceq m\sigma^{2}I$ (since each
block is just an independent application of $\mathbf{Q}$ and we sum over $m$
rows), so

$\mathbf{E}[\operatorname{tr}((\hat{W}-W)H(\hat{W}-W)^{T})]\leq
m\sigma^{2}\mathbf{E}[\operatorname{tr}(\mathbf{D})].$

Combining this with the result of Lemma B.1 proves the theorem. ∎

##  Appendix C E8P details

###  C.1 Constructing $S$

We use the following 29 elements of $\hat{D}_{8}$ with norm squared 12 to pad
$S$ to 256 entries.

       ([3, 1, 1, 1, 3, 3, 3, 3] [1, 3, 1, 1, 3, 3, 3, 3] [1, 1, 3, 1, 3, 3, 3, 3]
        [1, 1, 1, 3, 3, 3, 3, 3] [3, 3, 3, 1, 3, 3, 1, 1] [3, 3, 3, 1, 3, 1, 3, 1]
        [3, 3, 3, 1, 1, 3, 3, 1] [3, 3, 3, 1, 3, 1, 1, 3] [3, 3, 3, 1, 1, 3, 1, 3]
        [3, 3, 3, 1, 1, 1, 3, 3] [3, 3, 1, 3, 3, 3, 1, 1] [3, 3, 1, 3, 3, 1, 3, 1]
        [3, 3, 1, 3, 1, 3, 3, 1] [3, 3, 1, 3, 3, 1, 1, 3] [3, 3, 1, 3, 1, 3, 1, 3]
        [3, 3, 1, 3, 1, 1, 3, 3] [3, 1, 3, 3, 3, 3, 1, 1] [3, 1, 3, 3, 3, 1, 3, 1]
        [3, 1, 3, 3, 1, 3, 3, 1] [3, 1, 3, 3, 3, 1, 1, 3] [3, 1, 3, 3, 1, 3, 1, 3]
        [1, 3, 3, 3, 1, 1, 3, 3] [1, 3, 3, 3, 3, 3, 1, 1] [1, 3, 3, 3, 3, 1, 3, 1]
        [1, 3, 3, 3, 1, 3, 3, 1] [1, 3, 3, 3, 3, 1, 1, 3] [1, 3, 3, 3, 1, 3, 1, 3]
        [1, 1, 3, 3, 1, 3, 3, 3] [3, 3, 1, 1, 3, 3, 3, 1] ) / 2

###  C.2 Example Decoding with E8P

Here, we give an example of decoding with E8P. In this example, the first 8
bits of the codeword encode the entry in $S$, the next 7 bits encode the 7
right sign flips, and the last bit encodes whether or not we shift by
$\frac{1}{4}$. Let the codeword be 0001010110010111. The first 8 bits 00010101
= 21 would indicate that we start with the 21st entry in $S$. In this example,
let that be the vector

$s=\left\\{\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{3}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2}\right\\},$

which is not in $\hat{D_{8}}$. Thus, $s$ requires an odd number of sign flips
to get into $\hat{D_{8}}$. Then, the next 7 bits 1001011 would indicate that
we need to negate the 1st, 2nd, 4th, and 7th from right bits. Since we need an
odd number of sign flips, the 8th from right bit is also a sign flip. The
sign-decoded vector is then

$\left\\{-\frac{1}{2},-\frac{1}{2},\frac{1}{2},\frac{3}{2},-\frac{1}{2},\frac{1}{2},-\frac{1}{2},-\frac{1}{2}\right\\},$

which we can verify is in $E_{8}$. Finally, the last bit 1 indicates that we
need to add $\frac{1}{4}$, so the final decoded vector is

$\left\\{-\frac{1}{4},-\frac{3}{4},\frac{3}{4},\frac{7}{4},-\frac{1}{4},\frac{3}{4},-\frac{1}{4},-\frac{1}{4}\right\\},$

which is in $E_{8}+\frac{1}{4}$ as desired.

###  C.3 Why not K-Means?

A significant motivating factor behind E8P is that post-incoherence
processing, entries of $W$ are approximately Gaussian distributed. However,
E8P is uniformly distributed, which raises the question: why not use a K-means
based codebook? K-means based codebooks offer strong theoretical performance
but have a few issues. First, it is difficult to enforce symmetry in a
“learned” K-means codebook. This is crucial to be able to have a compressible
codebook. If we force sign symmetry by learning cluster centers on only the
positive orthant of a $n$-dimensional Gaussian, we can get around this but
sacrifice accuracy at the axis region. Second, using K-means requires storing
a codebook in fp16, whereas the entries of E8P can be stored as 4 bit
integers. This means that during inference, the source codebook for a 8
dimension K-means codebook will be 4 times larger than the source codebook of
E8P, running the risk of a cache eviction. Finally, we observe that
empirically, E8P actually outperforms K-means, which is somewhat interesting
and suggests that allocating more information to the edge of the distribution,
even after incoherence processing, is useful.

##  Appendix D Fine-Tuning During Quantization

In Algorithm 5 we describe our fine tuning procedure for QuIP$\\#$.

Algorithm 5 QuIP$\\#$ with Fine-Tuning

0: Unquantized Model $M$, Development Set $\mathcal{D}$, Quantization Order
$O$,

0: Quantized Model $M$

$X\leftarrow M_{\mbox{embedding}}(\mathcal{D})$

$C\leftarrow M(\mathcal{D})_{\mbox{logits}}$

for Decoder Block $D\in M$ do

$Y\leftarrow D(X)$

$X_{train},Y_{train},X_{valid},Y_{valid}\leftarrow\mbox{split}(X,Y)$

for Linear Layer $L\in D$ in order specified by $O$ do

$\hat{L}\leftarrow\mbox{QuIP$\\#$-NoFT}(L)$

Disable gradients for the weight matrix (but not $S_{U},S_{V})$ of $\hat{L}$.

Optimize $D$ to minimize $\mbox{MSE}(D(X_{train}),Y_{train})$ using
$X_{valid},Y_{valid}$ for early stopping.

end for

$X\leftarrow Y$

end for{At this point, the learnable parameters in $M$ are the layernorms, all
$S_{U}$ and $S_{V}$, and the language model head.}

$\mathcal{D}_{train},C_{train},\mathcal{D}_{valid},C_{valid}\leftarrow\mbox{split}(\mathcal{D},C)$

Optimize $M$ to minimize
$\mbox{CrossEntropy}(M(\mathcal{D}_{train}),C_{train})$ using
$\mathcal{D}_{valid},C_{valid}$ for early stopping.

##  Appendix E Additional Results

###  E.1 QuIP$\\#$ on Mixtral 8x7B (Jiang et al., 2024) and Falcon 180B
(Almazrouei et al., 2023)

Table 6: 2 bit QuIP$\\#$ without fine-tuning on Mixtral 8x7B, a mixture of experts (MoE), and Falcon 180B, a non-Llama-based model. QuIP$\\#$ scales to different architectures without issue. Model | Bits | Wiki2 | C4 | ArcC | ArcE | BoolQ | PiQA | Wino
---|---|---|---|---|---|---|---|---
Mixtral-8x7B | 16 | 3.45 | 6.85 | 0.56 | 0.74 | 0.85 | 0.84 | 0.75
Mixtral-8x7B | 2 | 4.69 | 8.25 | 0.49 | 0.68 | 0.81 | 0.80 | 0.73
Falcon-180B | 16 | 3.30 | 6.31 | 0.61 | 0.82 | 0.87 | 0.85 | 0.81
Falcon-180B | 2 | 4.18 | 7.06 | 0.58 | 0.81 | 0.84 | 0.84 | 0.81

###  E.2 Zeroshot performance for ablation on lattice codebooks and fine-
tuning

Table 7: Ablation on lattice codebooks and fine-tuning. QuIP$\\#$ no FT and $E_{8}$ uses the RHT to perform incoherence processing but does not use lattice codebooks or fine-tuning. QuIP$\\#$ No FT uses lattice codebooks but not fine-tuning. QuIP$\\#$ uses lattice codebooks and performs fine-tuning. Model | Method | Bits |  | ArcC
---
(acc_norm)
| ArcE
---
(acc_norm)
| BoolQ
---
(acc)
| PiQA
---
(acc_norm)
| Wino
---
(acc)
2-70 | Native | 16 | 48.0 | 59.7 | 76.6 | 80.9 | 76.8
2-70 | QuIP# no FT & no $E_{8}$ | 4 | 49.4 | 60.1 | 77.6 | 80.7 | 76.1
2-70 | QuIP# No FT | 4 | 48.3 | 60.1 | 78.4 | 80.6 | 76.2
2-70 | QuIP# | 4 | 48.3 | 59.4 | 77.4 | 80.7 | 77.1
2-70 |  QuIP# no FT & no $E_{8}$ | 3 | 47.4 | 59.1 | 75.8 | 80.9 | 77.5
2-70 | QuIP# No FT | 3 | 47.9 | 59.9 | 78.8 | 79.9 | 77.0
2-70 | QuIP# | 3 | 48.4 | 59.5 | 74.8 | 80.3 | 76.4
2-70 | QuIP# no FT & no $E_{8}$ | 2 | 43.5 | 56.2 | 75.1 | 78.1 | 76.0
2-70 | QuIP# No FT | 2 | 47.2 | 59.5 | 79.1 | 78.6 | 74.2
2-70 | QuIP# | 2 | 47.7 | 59.1 | 80.3 | 79.4 | 75.9
2-13 | Native | 16 | 44.3 | 58.0 | 69.0 | 79.0 | 69.9
2-13 | QuIP# no FT & no $E_{8}$ | 4 | 43.7 | 58.6 | 70.1 | 78.7 | 69.6
2-13 | QuIP# No FT | 4 | 42.9 | 56.4 | 67.8 | 78.9 | 69.9
2-13 | QuIP# | 4 | 44.2 | 57.7 | 69.7 | 78.9 | 69.9
2-13 |  QuIP# no FT & no $E_{8}$ | 3 | 42.1 | 55.2 | 70.0 | 77.8 | 69.5
2-13 | QuIP# No FT | 3 | 41.9 | 57.7 | 73.3 | 78.1 | 68.0
2-13 | QuIP# | 3 | 43.3 | 57.7 | 69.8 | 78.4 | 69.1
2-13 | QuIP# no FT & no $E_{8}$ | 2 | 36.3 | 50.8 | 67.4 | 73.4 | 63.1
2-13 | QuIP# No FT | 2 | 37.1 | 50.1 | 66.5 | 75.7 | 63.6
2-13 | QuIP# | 2 | 41.3 | 55.1 | 68.3 | 77.4 | 67.7
2-7 | Native | 16 | 40.6 | 53.5 | 71.0 | 76.9 | 67.0
2-7 | QuIP# no FT & no $E_{8}$ | 4 | 39.5 | 51.9 | 71.3 | 76.6 | 67.3
2-7 | QuIP# No FT | 4 | 40.4 | 53.7 | 68.5 | 77.2 | 67.5
2-7 | QuIP# | 4 | 40.1 | 53.4 | 69.9 | 76.5 | 67.6
2-7 |  QuIP# no FT & no $E_{8}$ | 3 | 38.1 | 52.6 | 65.2 | 76.1 | 65.1
2-7 | QuIP# No FT | 3 | 37.7 | 53.1 | 70.6 | 76.7 | 67.6
2-7 | QuIP# | 3 | 39.4 | 53.8 | 69.7 | 76.1 | 66.5
2-7 | QuIP# no FT & no $E_{8}$ | 2 | 29.2 | 42.5 | 63.3 | 68.0 | 59.0
2-7 | QuIP# No FT | 2 | 32.5 | 42.8 | 62.3 | 71.2 | 62.4
2-7 | QuIP# | 2 | 36.1 | 50.5 | 68.3 | 74.9 | 64.9

###  E.3 More Scaling Plots

Figure 5: QuIP$\\#$ scaling. (Top Left) Llama 2 Wikitext 2 perplexity vs AQLM.
Context length 4096. QuIP$\\#$ 2 and 3 bit scale better than AQLM 2 and 3 bit.
(Top Right) Llama 2 C4 Perplexity. Context length 4096. (Bottom) Llama 1 C4
Perplexity. Context length 2048.

##  Appendix F Implementation Details

This section contains implementation details for our Llama experiments. These
details also mostly apply to the Mixtral and Falcon numbers except we use the
Falcon dataset (Almazrouei et al., 2023) as it is publicly avaiable.

###  F.1 Hessian Generation

Hessian matrices $H$ were generated with 6144 sequences of a model’s native
context length (2048 for Llama 1, 4096 for Llama 2) from the RedPajama 1T
(Computer, 2023) dataset.

###  F.2 Hadamard Matrices

We use Hadamard matrices available at Neil Sloane’s website (Sloane, ).

###  F.3 Perplexity and Zeroshot Evaluation

We use the OPTQ (Frantar et al., 2023) “Wiktext2” and “C4” (not “C4 New”)
sampling functions to calculate perplexity for our experiments. We use LM Eval
(Gao et al., 2023) to calculate zeroshot numbers.

###  F.4 Fine Tuning

For the within-transformer block section of fine-tuning, we use the Adam
optimizer (Kingma & Ba, 2017), a learning rate of $5\times 10^{-5}$, batch
size of 8, and sequence length equal to the model’s native context length. We
train on small development dataset of 256 sequences from RedPajama 1T and
validate on 128 sequences. We train for 5 epochs (160 steps) and keep the best
model parameters based on the validation set. For the end to end tuning, we
use the Adam optimizer, a learning rate of $5\times 10^{-5}$, batch size of 1,
sequence length equal to the model’s context length (except for 70B, where we
had to use 3072 to avoid an OOM on our not very well optimized training
script), and the same dataset and epoch setup as before. We observe that
outside of using a low enough learning rate, the other hyperparameters did not
affect fine-tuning much. For the 2 bit models, we used a learning rate of
$5\times 10^{-4}$ for $S_{U}$ and $S_{V}$ ($5\times 10^{-5}$ for everything
else as above) for both the within-block and end to end fine tuning stages.

###  F.5 Hardware

All experiments were run on NVIDIA A100 GPUs except for the timing numbers,
which were measured on a NVIDIA RTX 4090 to see what was possible with the
current state-of-the-art NVIDIA consumer GPU. We find that we can quantize
Llama 2 70B without fine tuning in under 10 GPU-hours and with fine tuning in
around 100 GPU-hours. Both numbers do not include Hessian generation, which
can be done once for a model and reused across many different quantization
experiments.

###  F.6 Code and Prequantized Models

Our code is available at https://github.com/Cornell-RelaxML/quip-sharp and
prequantized QuIP$\\#$ models are available at https://huggingface.co/relaxml.

##  Appendix G Example Generation

Below are some example generations from Llama 2 70B chat quantized with
QuIP$\\#$ to 2 bits, truncated to 256 tokens.

Prompt: How much wood could a woodchuck chuck if a woodchuck could chuck wood?
QuIP$\\#$: The answer to this tongue-twister is a bit of a mystery.
Woodchucks, also known as groundhogs, are rodents that burrow in the ground
and are known for their ability to move large amounts of soil. However, there
is no scientific evidence to suggest that they can actually chuck wood. The
phrase “how much wood could a woodchuck chuck” was first used in a song called
“The Woodchuck’s Song” in the late 19th century. The song was popularized by
the singer and songwriter, Johnny Mercer, and it became a hit in the 1940s.
The song’s lyrics include the line “How much wood could a woodchuck chuck if a
woodchuck could chuck wood?” but they don’t provide an answer. In reality,
woodchucks don’t chuck wood, they dig burrows. They are able to move a lot of
soil and dirt as they dig their burrows, but they don’t have the ability to
move wood. So, the answer to the tongue-

Prompt: Write a song about large language models to the tune of Mariah Carey’s
“All I Want For Christmas Is You” QuIP$\\#$: Verse 1: I don’t want a lot for
Christmas There’s just one thing I’m wishing for A language model that’s large
and bright To help me with my writing, day and night Chorus: All I want for
Christmas is a language model A big, smart, AI that’s my ideal I’ll be happy
with just a few billion parameters All I want for Christmas is a language
model, yeah Verse 2: I’ll be good, I won’t be naughty I’ll use it for good,
not foraughty I’ll generate text that’s nice and neat And make my writing life
a treat Chorus: All I want for Christmas is a language model A big, smart, AI
that’s my ideal I’ll be happy with just a few billion parameters All I want
for Christmas is a language model, yeah Bridge: I’

Prompt: Write some CUDA code that does a matrix multiply QuIP$\\#$: Here is a
simple example of a matrix multiply using CUDA:

    #include <cuda.h>
    #include <cuda_runtime.h>

    __global__ void matrixMultiply(float *A, float *B, float *C, int rowsA, int co
    lsA, int rowsB, int colsB) {
      int i = blockIdx.x * blockDim.x + threadIdx.x;
      int j = blockIdx.y * blockDim.y + threadIdx.y;
      if (i < rowsA && j < colsB) {
        float sum = 0;
        for (int k = 0; k < rowsB; k++) {
          sum += A[i + k * colsA] * B[k + j * rowsB];
        }
        C[i + j * rowsB] = sum;
      }
    }

    int main() {
      int rowsA = 3;
      int colsA = 3;
      int rowsB = 3;