caldera short = CALDERA, long = Calibration Aware Low-Precision DEcomposition
with Low-Rank Adaptation

# Compressing Large Language Models using Low Rank and Low Precision
Decomposition

Rajarshi Saha
Stanford University
<EMAIL_ADDRESS>
&Naomi Sagan
Stanford University
<EMAIL_ADDRESS>
&Varun Srivastava
Stanford University
<EMAIL_ADDRESS>
Andrea J. Goldsmith
Princeton University
<EMAIL_ADDRESS>
&Mert Pilanci
Stanford University
<EMAIL_ADDRESS>

###### Abstract

The prohibitive sizes of Large Language Models (LLMs) today make it difficult
to deploy them on memory-constrained edge devices. This work introduces
CALDERA – a new post-training LLM compression algorithm that harnesses the
inherent low-rank structure of a weight matrix $\mathbf{W}$ by approximating
it via a low-rank, low-precision decomposition as
$\mathbf{W}\approx\mathbf{Q}+\mathbf{L}\mathbf{R}$. Here, $\mathbf{L}$ and
$\mathbf{R}$ are low rank factors, and the entries of $\mathbf{Q}$,
$\mathbf{L}$ and $\mathbf{R}$ are quantized. The model is compressed by
substituting each layer with its $\mathbf{Q}+\mathbf{L}\mathbf{R}$
decomposition, and the zero-shot performance of the compressed model is
evaluated. Additionally, $\mathbf{L}$ and $\mathbf{R}$ are readily amenable to
low-rank adaptation, consequently enhancing the zero-shot performance. CALDERA
obtains this decomposition by formulating it as an optimization problem
$\min_{\mathbf{Q},\mathbf{L},\mathbf{R}}\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}$, where $\mathbf{X}$ is the calibration data, and
$\mathbf{Q},\mathbf{L},\mathbf{R}$ are constrained to be representable using
low-precision formats. Theoretical upper bounds on the approximation error of
CALDERA are established using a rank-constrained regression framework, and the
tradeoff between compression ratio and model performance is studied by
analyzing the impact of target rank and quantization bit budget. Results
illustrate that compressing LlaMa-$2$ $7$B/$70$B and LlaMa-$3$ $8$B models
using CALDERA outperforms existing post-training LLM compression techniques in
the regime of less than $2.5$ bits per parameter. The implementation is
available at: https://github.com/pilancilab/caldera.

##  1 Introduction

Large Language Models (LLMs) stand out due to their remarkable ability to
generate human-like text, thereby supporting a diverse range of applications
ranging from writing assistance to code generation. These models leverage vast
datasets and significant computational resources to achieve their impressive
functionality. The architecture of LLMs typically includes multiple layers,
each with weight matrices essential for encoding various aspects of the
training data – from simple syntactic patterns to complex semantic
relationships. However, the substantial size of these trained models leads to
high computational costs and considerable energy consumption during inference,
which can be challenging for deployment in resource-constrained environments.
As LLMs continue to expand in scale, compression techniques to reduce the
memory and computational requirements of the models are becoming crucial to
ensure their broad accessibility.

Due to the correlated nature of language syntax and semantics learned during
training, often, the weight matrices of LLMs exhibit redundancy, which
manifests as a low-rank structure. This redundancy suggests the potential for
compression without substantial loss in performance. This work introduces
CALDERA: caldera, which compresses LLMs by leveraging the approximate low rank
structure inherent in these weight matrices. Given a matrix
$\mathbf{W}\in\mathbb{R}^{n\times d}$, caldera approximates it as
$\mathbf{W}\approx\mathbf{Q}+\mathbf{L}\mathbf{R}$, where
$\mathbf{Q}\in\mathbb{R}^{n\times d}$, $\mathbf{L}\in\mathbb{R}^{n\times k}$
and $\mathbf{R}\in\mathbb{R}^{k\times d}$. Here, the left and right low rank
factors, respectively $\mathbf{L}$ and $\mathbf{R}$, are tall and wide
matrices, and $k$ is the target rank. Furthermore, the entries of
$\mathbf{Q}$, $\mathbf{L}$ and $\mathbf{R}$ are represented using low-
precision formats with $\mathrm{B}_{\rm Q}$, $\mathrm{B}_{\rm L}$ and
$\mathrm{B}_{\rm R}$ bits per entry, respectively.

Figure 1: Decaying spectrum of weight matrices (aka, "approximate low-rank")

Since the singular value profile (aka spectrum) of the weight matrices of an
LLM follow a decaying profile as shown in Fig. 1, the low-rank factors
$\mathbf{L}$ and $\mathbf{R}$ capture the effect of the large singular
components of $\mathbf{W}$ with high fidelity. Moreover, the backbone
$\mathbf{Q}$, which is quantized aggressively – for instance, using
$\mathrm{B}_{\rm Q}=2$ bits, coarsely captures the essence of the moderately
decaying and low singular components of $\mathbf{W}$. caldera substitutes each
weight matrix $\mathbf{W}$ in an LLM, with its approximate low-precision and
low-rank decomposition $\mathbf{Q}+\mathbf{L}\mathbf{R}$, resulting in a post-
training quantization strategy that delivers state-of-the-art zero-shot
performance. In addition, since usually $k\ll{\rm min}\\{n,d\\}$, implying
that the total number of parameters in $\mathbf{L}\mathbf{R}$ is much smaller
compared to the number of entries in $\mathbf{W}$ (i.e., $k(n+d)\ll nd$),
caldera can readily fine-tune (or "adapt") the low rank factors $\mathbf{L}$
and $\mathbf{R}$ in order to boost the zero-shot results.

###  1.1 Significance and Related Works

Recent efforts have explored various avenues for compression, including but
not limited to weight pruning, quantization, and the use of parameter-
efficient training methods – each approach offering distinct advantages and
tradeoffs. This section briefly reviews the current methodologies,
highlighting the contributions and limitations of some studies closely related
to this work.

LLM Compression and Outlier Mitigation: Recent studies like SmoothQuant [41],
OPTQ [8], QuIP [3], AQLM [7], and QuIP# [35] consider the challenging regime
of sub-$4$ bit post-training LLM quantization. These works collectively
emphasize the need to manage the impact of outliers, i.e., weights with
unusually high magnitudes. Accommodating outliers necessitates choosing the
dynamic range (or scale) of a quantizer to be high, consequently increasing
the quantization error. QuIP equalizes (and reduces) the weight matrices by
using a randomized matrix transform, and subsequently, QuIP# employs E8
lattice to make the weights more amenable to vector quantization. Both QuIP
and QuIP# use a refined variant of the column-wise quantization method
proposed in OPTQ, wherein error feedback from previously quantized columns of
a matrix is used to compensate for the error incurred while quantizing
subsequent columns. caldera utilizes this diverse arsenal of strategies and
builds on top of QuIP#, while capitalizing on the approximate low-rank
structure of LLM weight matrices. While it is possible to obtain even more
aggressively compressed LLMs [24], this approach requires training from
scratch, which is computationally demanding.

Parameter Efficient Fine-Tuning (PEFT): In a related yet distinct vein of
work, PEFT methods have gained significant momentum, aiming to adapt LLMs to
specific tasks without extensive computational overhead. Recent studies such
as QLoRA [5], LoftQ [22], and LQ-LoRA [13] have explored the intersection of
PEFT and quantization, demonstrating that fine-tuning through low-rank
updates, as originally proposed in LoRA [16], can mitigate the performance
losses due to quantization. Given that caldera yields a decomposition
$\mathbf{Q}+\mathbf{L}\mathbf{R}$, the low-rank components are particularly
suitable for fine-tuning with any existing PEFT methods, thereby enhancing the
zero-shot capabilities.

Low Rank Approximation: The rank-$k$ approximation of a matrix
$\mathbf{A}\in\mathbb{R}^{n\times d}$ can be represented by the factorization
$\mathbf{A}\approx\mathbf{L}\mathbf{R}$, with
$\mathbf{L}\in\mathbb{R}^{n\times k}$ and $\mathbf{R}\in\mathbb{R}^{k\times
d}$, where $k\leq{\rm min}\\{n,d\\}$. Known as the Burer-Monteiro
factorization, this method substantially decreases the number of parameters,
thus reducing computational demands. Recent studies such as LoRD [18], ASVD
[43], FWSVD [15], LASER [32], LQER [44], and ZeroQuant-V2 [42] have explored
the efficacy of low-rank structures in LLM weights, treating low-rank
factorization and quantization independently. In contrast, LPLR [30]
approaches this by uniquely formulating a joint optimization problem for
generic matrices, while simultaneously leveraging the equalization property of
randomized transforms, as in [3]. caldera formally leverages this inherent
low-rank structure for LLM compression alongside existing frameworks such as
QuIP# [35] and LoftQ [22], providing additional flexibility for compression.
Furthermore, rigorous theoretical guarantees are derived using a rank-
constrained regression framework for obtaining a low precision and low-rank
decomposition, thereby also analytically demonstrating its superiority over
rank-agnostic strategies.

##  2 Problem Formulation

In a neural network layer, a weight matrix $\mathbf{W}$ transforms an input
activation $\mathbf{x}$ into an output activation given by
$\mathbf{W}\mathbf{x}$. This transformation can be succinctly described using
the matrix’s singular value decomposition (SVD). For any matrix
$\mathbf{A}\in\mathbb{R}^{n\times d}$, the SVD is
$\mathbf{A}=\sum_{i}\sigma_{i}\mathbf{u}_{i}\mathbf{v}_{i}$, where
$\sigma_{i},\mathbf{u}_{i},\mathbf{v}_{i}$ are the $i^{\rm th}$ singular value
and the corresponding left and right singular vectors, respectively. The
impact of each singular component $\mathbf{u}_{i}\mathbf{v}_{i}$ on the
matrix’s transformation is determined by the magnitude of $\sigma_{i}$. Given
that weight matrices exhibit a decaying singular value profile (Fig. 1),
indicating an approximate low-rank structure, lesser contributing singular
components can be pruned with minimal impact on the functionality of the
matrix, ensuring minimal distortion in the output activations.

caldera approximates the weight matrix of a neural network, $\mathbf{W}$, as a
low-precision, low-rank decomposition,
$\mathbf{W}\approx\mathbf{Q}+\mathbf{L}\mathbf{R}$, with all components
$\mathbf{Q},\mathbf{L},\mathbf{R}$ in low-precision format. Unlike previous
works such as [13, 22, 44, 43], which represent the low-rank factors
$\mathbf{L}$ and $\mathbf{R}$ in high-precision (16 or 32-bit floating point),
this work extends their representation to low-precision. This further reduces
the memory footprint while preserving performance. Alternatively, for the same
memory footprint, it allows the target rank $k$ to be higher, thereby
capturing the low rank structure with higher fidelity by including more of the
higher singular value components. The following paragraph formalizes this as a
constrained optimization problem.

For a given quantizer, let $\mathbb{Q}$ denote the set of discrete
quantization points in $\mathbb{R}$. For $\mathrm{B}$-bit quantization, the
cardinality of $\mathbb{Q}$ satisfies
$\log_{2}\lvert\mathbb{Q}\rvert\leq\mathrm{B}$. Consider a matrix
$\mathbf{W}\in\mathbb{R}^{n\times d}$. The goal of this work is to obtain an
decomposition $\mathbf{W}\approx\mathbf{Q}+\mathbf{L}\mathbf{R}$ by
approximately solving the minimization problem

$\min_{\mathbf{Q},\mathbf{L},\mathbf{R}}\left\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\quad\text{subject to}\quad\mathbf{Q}\in\mathbb{Q}_{\mathrm{Q}}^{n\times
d},\;\mathbf{L}\in\mathbb{Q}_{\mathrm{L}}^{n\times k},\;\text{and
}\;\mathbf{R}\in\mathbb{Q}_{\mathrm{R}}^{k\times d}.$ (1)

Here, $\mathbb{Q}_{\mathrm{Q}}$, $\mathbb{Q}_{\mathrm{L}}$ and
$\mathbb{Q}_{\mathrm{R}}$ denote the lattice codebooks used to quantize
$\mathbf{Q}$, $\mathbf{L}$ and $\mathbf{R}$, using $\mathrm{B}_{\rm Q}$,
$\mathrm{B}_{\rm L}$ and $\mathrm{B}_{\rm R}$ bits, respectively. Furthermore,
$\mathbf{X}\in\mathbb{R}^{m\times d}$ is a calibration matrix that aims to
preserve the Frobenius norm error of the compressed layer output activations.
If $\mathbf{W}$ is the first layer’s weight matrix, $\mathbf{X}$ includes
input embeddings from a calibration dataset, such as a subset of RedPajama
[33], with the $i^{\rm th}$ row representing the $i^{\rm th}$ datapoint. For
intermediate layers, $\mathbf{X}$ contains the input activations, which are
the output activations of the preceding layer.

Using the Frobenius norm of the output of a layer as a proxy objective for
quantizing the weight matrices of an LLM is a popular strategy, and was used
in prior work of Nagel et al. [27] . This proxy objective function is
particularly useful for post-training quantization of LLMs because their large
size makes it difficult to apply sophisticated compression methods.

##  3 Proposed Algorithm: Calibration-Aware Low-Precision Decomposition with
Low Rank Adaptation

This section introduces caldera to approximately solve (1) and get a
$\mathbf{Q}+\mathbf{L}\mathbf{R}$ decomposition of a weight matrix
$\mathbf{W}$ using the calibration matrix $\mathbf{X}$. The pseudocode is
provided in Alg. 1. It consists of a nested loop for alternately optimizing
the variables $\mathbf{Q},\mathbf{L}$ and $\mathbf{R}$. Suppose
$\mathrm{Q}_{\rm Q}$, $\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$,
respectively, denote quantizers used for quantizing $\mathbf{Q}$, $\mathbf{L}$
and $\mathbf{R}$. For instance, they can refer to uniformly dithered scalar
quantizers, as described in App. G.2. Initially, the low-rank actors are set
to $\mathbf{0}$, and $\mathbf{W}$ is quantized using the LDLQ quantizer
proposed in [3, §3.1]. LDLQ is an adaptive quantization method that
iteratively quantizes [8] each column of $\mathbf{W}$ using $\mathrm{Q}_{\rm
Q}$ to get $\mathbf{Q}$ as

$\mathbf{Q}^{(k)}=\mathrm{Q}_{\rm
Q}(\mathbf{W}^{(k)}+(\mathbf{W}^{(1:k-1)}-\mathbf{Q}^{(1:k-1)})\mathbf{a}_{k}),$
(2)

where $\mathbf{Q}^{(k)},\mathbf{W}^{(k)}$ denote the $k^{\rm th}$ column,
$\mathbf{W}^{(1:k-1)}$ denotes the first $k$ columns, $\mathrm{Q}_{\rm Q}$ has
a bit-budget $\mathrm{B}_{\rm Q}$, and $\mathbf{a}_{k}\in\mathbb{R}^{k-1}$ is
a learnable sequence of vectors. Update Eq. (2) incorporates linear feedback
from already quantized columns, it can be seen that $\mathbf{Q}$ satisfies
$\mathbf{Q}=\mathrm{Q}_{\rm
Q}\left(\mathbf{W}+(\mathbf{W}-\mathbf{Q})\mathbf{M}\right)$, where the
feedback matrix $\mathbf{M}$ is a strictly upper triangular matrix with
columns $\mathbf{a}_{k}$. Defining
$\mathbf{H}\triangleq\frac{1}{m}\mathbf{X}^{\top}\mathbf{X}$ to be the
(scaled) Hessian of the least squares objective in (1), [3] show that the
optimal feedback matrix is the $\mathbf{M}$ obtained from the LDL
decomposition of $m\mathbf{H}$, given by
$m\mathbf{H}=(\mathbf{M}+\mathbf{I})\mathbf{D}(\mathbf{M}+\mathbf{I})^{\top}$.

Subsequently, $\mathbf{Q}$ is fixed and the Low-Precision Low-Rank (LPLR)
factorization of the residual, $(\mathbf{W}-\mathbf{Q})$, is computed. This is
done by the LPLRFactorize submodule (Alg. 2), which is a refined version of
the LPLR algorithm proposed in [30]. For a given matrix $\mathbf{A}$, Alg. 2
minimizes

$\min_{\mathbf{L},\mathbf{R}}\left\lVert(\mathbf{L}\mathbf{R}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\quad\text{subject to}\quad\mathbf{L}\in\mathbb{Q}_{\mathrm{L}}^{n\times
k},\;\text{and }\;\mathbf{R}\in\mathbb{Q}_{\mathrm{R}}^{k\times d},$ (3)

where $\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$ use $\mathrm{B}_{\rm L}$
and $\mathrm{B}_{\rm R}$ bits, respectively. In contrast to [30], the
objective in (3) is calibration-data aware. Therefore, the update equations
are derived using a rank-constrained regression framework, as described in
App. B. Moreover, lines $7$ to $14$ in LPLRFactorize iteratively refine the
estimates of $\mathbf{L}$ and $\mathbf{R}$, and can only yield a smaller
Frobenius norm error. The left and right low-rank factor update equations are
described as follows.

Initialization: In the absence of quantization constraints, a globally optimal
solution to the optimization problem (3) can be found as described later in
lemma 4.2. Consequently, the low-rank factors are initialized using rank-
constrained regression in lines $2$ – $4$. Since subsequent quantization
disrupts optimality of the solution, the factors are iteratively updated to
minimize this distortion.

Updating $\mathbf{L}$: To update the left factor $\mathbf{L}$, lines $5$ and
$9$ of Alg. 2 solves
$\min_{\mathbf{Z}}\lVert(\mathbf{Z}\mathbf{R}-\mathbf{A})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}$. For a fixed $\mathbf{R}$, this is a least squares minimization, whose
solution is available is closed form as
$\grave{\mathbf{L}}=\left(\mathbf{A}\mathbf{X}^{\top}\right)\left(\mathbf{R}\mathbf{X}^{\top}\right)^{\dagger}=\mathbf{A}\mathbf{H}\mathbf{R}^{\top}(\mathbf{R}\mathbf{H}\mathbf{R}^{\top})^{-1}$,
as derived in App. C.1.

Updating $\mathbf{R}$: Line $8$ of Alg. 2, updates the right factor
$\mathbf{R}$ by keeping $\mathbf{L}$ fixed and solving ${\rm
min}_{\mathbf{Z}}\lVert(\mathbf{L}\mathbf{Z}-\mathbf{A})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}$. As this is an under-determined linear system, there exist multiple
solutions for $\mathbf{Z}$, all attaining the same objective function value.
It is shown in App. C.1 that
$\grave{\mathbf{R}}=\mathbf{L}^{\dagger}\mathbf{A}\mathbf{H}\mathbf{H}^{\dagger}$
is a solution. The corresponding error is also obtained, which is used in the
derivation of Thm. 4.1.

Computational Complexity: A high-level calculation is provided here, and
detailed discussions can be found in App. D. It is worthwhile to note that the
closed form expressions of $\grave{\mathbf{L}}$ and $\grave{\mathbf{R}}$,
which are iteratively quantized, are functions of the Hessian
$\mathbf{H}=\frac{1}{m}\mathbf{X}^{\top}\mathbf{X}$. Therefore, $\mathbf{H}$
can be computed offline initially, per LLM, by doing a single forward pass,
and subsequently used for all model quantization experiments. For each layer,
this pre-processing includes computing $\mathbf{H}$ and its LDL decomposition,
along with computing $\mathbf{H}\mathbf{H}^{\dagger}$, requiring a total of
$\mathrm{O}(md^{2}+2d^{3})$ multiplications. Each outer iteration involves an
LDLQ quantization. Quantizing the $k^{\rm th}$ column has complexity
$\mathrm{O}(nk)$, since feedback from $k$ already quantized columns need to be
incorporated. Hence, quantizing a matrix in $\mathbb{R}^{n\times d}$ entails
$\mathrm{O}(n^{2}+3n)$ complexity. Moreover, LPLRFactorize requires
$\mathrm{O}(m^{2}(n+d))$ to initialize, and subsequently, each inner iteration
entails $\mathrm{O}(ndk)$. Assuming $n,d\geq m\gg k$, and keeping only the
dominant terms, the total complexity of caldera, not including the complexity
of the pre-processing discussed earlier, is $\mathrm{O}\left({\rm
T_{out}}\left(n^{2}+m^{2}(n+d)+ndk\;{\rm T_{in}}\right)\right)$.

Fine tuning via Low-Rank Adaptation: Once the weight matrices of each layer
are replaced by its $\mathbf{Q}+\mathbf{L}\mathbf{R}$ approximation, the zero-
shot performance of (post-training) quantized model can be evaluated. §5 shows
that caldera quantized models outperform existing strategies. Additionally, if
desired, the low-rank factors $\mathbf{L}$ and $\mathbf{R}$ can be further
fine-tuned using low-rank adaptation [16, 22, 13] on a small task-specific
dataset. While the initialization of the fine-tuning step has quantized
$\mathbf{Q},\mathbf{L}$ and $\mathbf{R}$, the fine-tuned factors are
represented using $16$-bits ($\rm BF16$ format). Although this leads to a
slight increase in the memory footprint, the performance gains from fine-
tuning are substantial.

##  4 Approximation Error Analysis

The approximation error upper bounds are derived via a rank-constrained
regression framework. Thm. 4.1 below (formally stated and proved in App. C.4)
is an informal version of the main theoretical result of this paper, and
provides an upper bound on the Frobenius norm error when caldera approximates
a weight matrix $\mathbf{W}$ is as
$\mathbf{W}\approx\mathbf{Q}+\mathbf{L}\mathbf{R}$ by solving the optimization
problem (1) using Alg. 1. For convenience of analysis, it is assumed that the
dynamic range of $\mathrm{Q}_{\rm Q}$, denoted as $\mathrm{R}$, is chosen to
be high enough, ensuring it remains unsaturated. Consequently, for a scalar
input the quantization error from $\mathrm{Q}_{\rm Q}$ has zero mean and
bounded variance, given by
$\frac{\Delta^{2}}{4}=\frac{\mathrm{R}^{2}}{(2^{\mathrm{B}_{\rm Q}}-1)^{2}}$.

Input: Matrix: $\mathbf{W}\in\mathbb{R}^{n\times d}$, Target rank: $k$,
Calibration matrix: $\mathbf{X}\in\mathbb{R}^{m\times d}$, Outer and inner
iterations: $\rm T_{out}$, $\rm T_{in}$, Quantizers: $\mathrm{Q}_{\rm Q}$,
$\mathrm{Q}_{\rm L}$, $\mathrm{Q}_{\rm R}$, Flag: EnableLoRA, Fine-tune rank:
$r$

Output: LPLR decomposition: $\mathbf{Q}\in\mathbb{Q}_{\mathrm{Q}}^{n\times
d}$, $\mathbf{L}\in\mathbb{Q}_{\mathrm{L}}^{n\times k}$,
$\mathbf{R}\in\mathbb{Q}_{\mathrm{R}}^{k\times d}$ s.t.
$\mathbf{W}\mathbf{X}^{\top}\approx(\mathbf{Q}+\mathbf{L}\mathbf{R})\mathbf{X}^{\top}$

1

2 Initialize: _$t\leftarrow 0$ , $\mathbf{L}_{0}\leftarrow\mathbf{0}$,
$\mathbf{R}_{0}\leftarrow\mathbf{0}$,
${\color[rgb]{0.77,0.12,0.23}\definecolor[named]{pgfstrokecolor}{rgb}{0.77,0.12,0.23}{\rm
MinError}}\leftarrow\infty$_

3while  _$t <{\rm T_{out}}$_ do

4

5 Update $\mathbf{Q}$:
$\mathbf{Q}_{t+1}\leftarrow{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{\sc
LDLQ}}(\mathbf{W}-\mathbf{L}_{t}\mathbf{R}_{t},\mathrm{Q}_{\rm Q})$

6 Update low-rank factors:
$\mathbf{L}_{t+1},\mathbf{R}_{t+1}\leftarrow{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{\sc
LPLRFactorize}}(\mathbf{W}-\mathbf{Q}_{t+1},k,\mathbf{X},\mathrm{Q}_{\rm
L},\mathrm{Q}_{\rm R},{\rm T_{in}})$

7 if
_$\lVert(\mathbf{Q}_{t+1}+\mathbf{L}_{t+1}\mathbf{R}_{t+1}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}
<{\color[rgb]{0.77,0.12,0.23}\definecolor[named]{pgfstrokecolor}{rgb}{0.77,0.12,0.23}{\rm
MinError}}$_ then

8

9 $\mathbf{Q}_{\rm best}\leftarrow\mathbf{Q}_{t+1}$, $\mathbf{L}_{\rm
best}\leftarrow\mathbf{L}_{t+1}$, $\mathbf{R}_{\rm
best}\leftarrow\mathbf{R}_{t+1}$,
${\color[rgb]{0.77,0.12,0.23}\definecolor[named]{pgfstrokecolor}{rgb}{0.77,0.12,0.23}{\rm
MinError}}\leftarrow\lVert(\mathbf{Q}_{t+1}+\mathbf{L}_{t+1}\mathbf{R}_{t+1}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}$

10

11 end if

12

13 $t\leftarrow t+1$

14 end while

15

16if  _EnableLoRA is TRUE_ then

17 Further Fine-tune top-$r$ singular components of $\mathbf{L}_{\rm best}$
and $\mathbf{R}_{\rm best}$ to $16$-bit precision using Low-Rank Adaptation
(LoRA) (as in [16, 22, 13])

18 end if

19

20return _$\mathbf{Q}_{\rm best},\mathbf{L}_{\rm best},\mathbf{R}_{\rm best}$_

Algorithm 1 CALDERA: Calibration Aware Low-Precision DEcomposition with Low-
Rank Adaptation

######  Theorem 4.1.

Approximation error of caldera (Informal) Given
$\mathbf{W}\in\mathbb{R}^{n\times d}$ and $\mathbf{X}\in\mathbb{R}^{m\times
d}$ with $m\leq d$, let $\mathbf{D}$ be obtained from the LDL decomposition
$\mathbf{X}^{\top}\mathbf{X}=m\mathbf{H}=(\mathbf{M}+\mathbf{I})\mathbf{D}(\mathbf{M}+\mathbf{I})^{\top}$,
and $\lambda_{\rm max}$, $\lambda_{\rm min}$ denote the max and min
eigenvalues of $\mathbf{H}$. Additionally, let
$\mathbf{Q}\triangleq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{\sc
LDLQ}}(\mathbf{W},\mathrm{Q}_{\rm Q})$, where $\mathrm{Q}_{\rm Q}$ has dynamic
range $\mathrm{R}$ and bit-budget $\mathrm{B}_{\rm Q}$, the quantization error
be $\boldsymbol{\eta}\triangleq\mathrm{Q}_{\rm
Q}(\mathbf{Q}+(\mathbf{W}-\mathbf{Q})\mathbf{M})-(\mathbf{Q}+(\mathbf{W}-\mathbf{Q})\mathbf{M})$,
and $\sigma_{1}\geq\ldots\geq\sigma_{k}\ldots$ be the singular values of
$\mathbf{X}(\mathbf{W}-\mathbf{Q})^{\top}$. If the target rank $k$ satisfies
$0.25\lambda_{\rm min}^{1/2}(m\sigma_{1})^{-1}\lambda_{\rm
max}^{-3/2}\sum_{i>k}\sigma_{i}^{2}\leq k\leq m$, and the dynamic ranges of
$\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$ are set as $\mathrm{R}_{\rm
L}=\frac{2\sigma_{1}}{\sigma_{k}\sqrt{m\lambda_{\rm min}}}$ and
$\mathrm{R}_{\rm R}=\sigma_{1}$, then $\mathbf{Q},\mathbf{L}$ and $\mathbf{R}$
returned by Alg. 1 satisfy

$\frac{1}{nm}\;\mathbb{E}\left\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\leq\frac{1}{n}\sum_{i>k}\mathbb{E}\lambda_{i}(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top})+\epsilon\lesssim\frac{4\mathcolor{darkblue}{d}\lambda_{\rm
max}\mathrm{R}^{2}}{\pi\left(2^{\mathrm{B}_{\rm
Q}}-1\right)^{2}}\left(1-\frac{k}{2\mathcolor{darkblue}{n}}\right)^{2}+\epsilon,$

while utilizing an average budget of
$\frac{1}{2}\log_{2}\left(\frac{k\sigma_{1}^{3}}{\mathcolor{darkblue}{m}\epsilon\sigma_{k}}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}\sqrt{\mathcolor{darkblue}{d/n}}\right)$ bits per
parameter for the low-rank factors $\mathbf{L}$ and $\mathbf{R}$, when
$n\approx d$. Here, the expectation is over the stochasticity of the
quantizers.

An informal version of the main result is provided here, and the formal
version including specific constant values, along with the derivation, can be
found in App. C.4. The requirement $m\leq d$ is not restrictive, as
$\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}=\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{H}^{1/2}\rVert_{\rm
F}^{2}$, i.e., (1) can be rewritten to ensure $m=d$. The approximation error
upper bound given by Thm. 4.1 can be directly compared with the result of Chee
et al. [3, Thm. 1], which states that for vanilla LDLQ without LPLRFactorize,

$\mathbb{E}\left\lVert(\mathbf{Q}-\mathbf{W})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\leq\mathbb{E}\left[\textrm{Tr}\left(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top}\right)\right]=\sum_{i=1}^{n}\mathbb{E}\lambda_{i}(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top}).$
(4)

Evidently, Alg. 1 yields a smaller error provided,
$\sum_{i>k}\mathbb{E}\lambda_{i}(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top})<\sum_{i=1}^{k}\mathbb{E}\lambda_{i}(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top})-\epsilon$,
where $\epsilon$ can be chosen to be arbitrarily small. Furthermore, since the
expression in Thm. 4.1 consists of two terms, namely, the rank-constrained
regression error, which depends on the target rank $k$, and the additive
quantization error of $\epsilon$, which is dictated by the bit-budgets used
for $\mathbf{L}$ and $\mathbf{R}$, this upper bound can be made arbitrarily
small by ensuring that the two terms are approximately equal, i.e.,
$\mathbb{E}\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}$ is upper bounded by $2\epsilon$. This is apparent in the following
regimes:

  1. (i)

$\mathcolor{officegreen}{k\ll n}$: In this regime, $k$ is treated as a
constant as $n$ grows. Then, if the bit-budget $\mathrm{B}_{\rm Q}$ satisfies

$\mathrm{B}_{\rm
Q}\geq\log_{2}\left(2\mathrm{R}(\pi\epsilon)^{-1/2}\sqrt{\mathcolor{darkblue}{nmd}\;\lambda_{\rm
max}}+1\right),\quad\text{then}\quad\mathbb{E}\left\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\leq 2\epsilon.$

  2. (ii)

$\mathcolor{officegreen}{k=\mathrm{O}(n)}$: For a fixed $\mathrm{B}_{\rm Q}$,
if $k$ is allowed to grow with dimension $n$, then choosing $k$ to satisfy

$k\geq 2\mathcolor{darkblue}{n}-(2^{\mathrm{B}_{\rm
Q}}-1)\mathrm{R}^{-1}(\pi\epsilon)^{1/2}(\mathcolor{darkblue}{md}\lambda_{\rm
max}^{-1/2})\sqrt{\mathcolor{darkblue}{n}}\quad\text{ensures}\quad\mathbb{E}\left\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\leq 2\epsilon.$

This implies that the upper bound can be made arbitrarily small by either
$\rm(i)$ increasing the bit-budget of the backbone, i.e., $\mathrm{B}_{\rm
Q}$, for a fixed rank $k$, or $\rm(ii)$ increasing the rank $k$ for a fixed
$\mathrm{B}_{\rm Q}$, for example, $\mathrm{B}_{\rm Q}=2$. Alternatively
stated, this provides a tunable knob for controlling the error by trading off
the allocated bit-budget between the backbone $\mathbf{Q}$ and the low-rank
factors $\mathbf{L},\mathbf{R}$.

Input: Matrix: $\mathbf{A}\in\mathbb{R}^{n\times d}$, Target rank: $k$,
Calibration matrix: $\mathbf{X}\in\mathbb{R}^{m\times d}$, Iterations: ${\rm
T_{in}}$, Quantizers: $\mathrm{Q}_{\rm L}$, $\mathrm{Q}_{\rm R}$

Output: Low precision Low Rank factors: $\mathbf{L}\in\mathbb{Q}^{n\times k}$,
$\mathbf{R}\in\mathbb{Q}^{k\times d}$ s.t.
$\mathbf{A}\mathbf{X}^{\top}\approx\mathbf{L}\mathbf{R}\mathbf{X}^{\top}$

1

2 Initialize: _Iteration counter : $i\leftarrow 0$_

3Compute SVD of $\mathbf{X}$ as
$\mathbf{U}\widetilde{\boldsymbol{\Sigma}}\mathbf{V}^{\top}$.

4 Compute SVD of $\mathbf{U}^{\top}\mathbf{X}\mathbf{A}^{\top}$ as
$\grave{\mathbf{U}}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}$

5 Get right low-rank factor: $\mathbf{R}_{0}\leftarrow\mathrm{Q}_{\rm
R}(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top})$

6 Get left low-rank factor: $\mathbf{L}_{0}\triangleq\mathrm{Q}_{\rm
L}(\grave{\mathbf{L}}_{0})$, where $\grave{\mathbf{L}}_{0}=\mathop{\rm
arg\hskip 2.84526ptmin}_{\mathbf{Z}\in\mathbb{R}^{k\times
d}}\left\lVert(\mathbf{Z}\mathbf{R}_{0}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$

7 $\mathbf{L}_{\rm best}\leftarrow\mathbf{L}_{0}$, $\mathbf{R}_{\rm
best}\leftarrow\mathbf{R}_{0}$,
${\color[rgb]{0.77,0.12,0.23}\definecolor[named]{pgfstrokecolor}{rgb}{0.77,0.12,0.23}{\rm
MinError}}\leftarrow\left\lVert(\mathbf{L}_{0}\mathbf{R}_{0}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$.

8while  _$i <{\rm T_{in}}$_ do

9 Update right: $\mathbf{R}_{i+1}\leftarrow\mathrm{Q}_{\rm
R}(\grave{\mathbf{R}}_{i+1})$, where $\grave{\mathbf{R}}_{i+1}=\mathop{\rm
arg\hskip 2.84526ptmin}_{\mathbf{Z}\in\mathbb{R}^{k\times
d}}\left\lVert\left(\mathbf{L}_{i}\mathbf{Z}-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$

10 Update left: $\mathbf{L}_{i+1}\leftarrow\mathrm{Q}_{\rm
L}(\grave{\mathbf{L}}_{i+1})$, where $\grave{\mathbf{L}}_{i+1}=\mathop{\rm
arg\hskip 2.84526ptmin}_{\mathbf{Z}\in\mathbb{R}^{n\times
k}}\left\lVert\left(\mathbf{Z}\mathbf{R}_{i}-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$

11

12 if
_$\left\lVert(\mathbf{L}_{i+1}\mathbf{R}_{i+1}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}
<{\color[rgb]{0.77,0.12,0.23}\definecolor[named]{pgfstrokecolor}{rgb}{0.77,0.12,0.23}{\rm
MinError}}$_ then

13 $\mathbf{L}_{\rm best}\leftarrow\mathbf{L}_{i+1}$, $\mathbf{R}_{\rm
best}\leftarrow\mathbf{R}_{i+1}$,
${\color[rgb]{0.77,0.12,0.23}\definecolor[named]{pgfstrokecolor}{rgb}{0.77,0.12,0.23}{\rm
MinError}}\leftarrow\left\lVert(\mathbf{L}_{i+1}\mathbf{R}_{i+1}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$

14

15 end if

16

17 $i\leftarrow i+1$

18 end while

19

return _$\mathbf{L}_{\rm best},\mathbf{R}_{\rm best}$_

Algorithm 2 LPLRFactorize$(\mathbf{A},k,\mathbf{X},\mathrm{Q}_{\rm
L},\mathrm{Q}_{\rm R},T_{\rm in})$: LPLR factorization submodule

###  4.1 Analysis Outline

In this section, a brief proof sketch is presented, highlighting the major
challenges in the proof and how they are addressed. For analysis, $\mathbf{Q}$
is assumed to be updated prior to $\mathbf{L},\mathbf{R}$ in Alg. 1. However,
in practice, the update order is inconsequential, and can be swapped,
depending on whichever yields a smaller error. The complete derivation of the
approximation error is provided in App. C. A key ingredient of the proof is
the solution of the rank-constrained regression problem, defined as,

$\min_{{\rm rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm F}^{2}.$ (5)

Although this problem is non-convex, it can be solved to global optimality via
two SVDs [40]. The following lemma characterizes the solution to the
optimization problem in (5).

######  Lemma 4.2.

Given $\mathbf{Y}\in\mathbb{R}^{m\times n}$, and full rank
$\mathbf{X}\in\mathbb{R}^{m\times d}$, where $m\leq d$. Let
$\mathbf{X}=\mathbf{U}\widetilde{\boldsymbol{\Sigma}}\mathbf{V}^{\top}$ and
$\mathbf{U}^{\top}\mathbf{Y}=\grave{\mathbf{U}}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}$
denote full SVDs of $\mathbf{X}$ and $\mathbf{U}^{\top}\mathbf{Y}$. Then, for
$k\leq m$, the solution of (5) is

$\mathbf{Z}_{*}\triangleq\mathop{\rm arg\hskip 2.84526ptmin}_{{\rm
rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm
F}^{2}=\left(\mathbf{V}\mathbf{I}_{m}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right),$

where
$\boldsymbol{\Sigma}:=\widetilde{\boldsymbol{\Sigma}}\mathbf{I}_{m}\in\mathbb{R}^{m\times
m}$ is a diagonal matrix consisting of the non-zero singular values of
$\mathbf{X}$. Moreover, denoting the non-zero singular values of $\mathbf{Y}$
as $\\{\sigma_{i}(\mathbf{Y})\\}_{i=1}^{m}$, the optimal value of (7) is

$\min_{{\rm rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm
F}^{2}=\left\lVert\mathbf{X}\mathbf{Z}_{*}-\mathbf{Y}\right\rVert_{\rm
F}^{2}=\sum_{i=k+1}^{m}\sigma_{i}^{2}\left(\mathbf{Y}\right).$ (6)

The complete lemma (with the case $m>d$), and the derivation, are provided in
App. B. Using lemma 4.2, the approximation error of LPLRFactorize is analyzed
in App. C.3. Specifically, lemma C.3 shows that for any input matrix
$\mathbf{A}$, Alg. 2 with suitably chosen $\mathrm{B}_{\rm L}$ and
$\mathrm{B}_{\rm R}$, ensures that
$\mathbb{E}\left\lVert(\mathbf{L}\mathbf{R}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$, as in (3), can be upper bounded by twice the sum of squared trailing
singular values, (ref. (6)). While proving lemma C.3, it is assumed that if
$\mathrm{Q}_{\rm L}$ or $\mathrm{Q}_{\rm R}$ gets saturated, a trivial output
of $\mathbf{L}=\mathbf{0},\mathbf{R}=\mathbf{0}$ is returned. Therefore,
lemmas C.1 and C.2 specify choosing the dynamic ranges $\mathrm{R}_{\rm R}$
and $\mathrm{R}_{\rm L}$ to be sufficiently high so that saturation happens
with a very low probability. The proof of Thm. 4.1 is completed by using the
LDL decomposition of $m\mathbf{H}$ as proposed in [3], along with an
application of Marchenko-Pastur approximation to bound the expected
eigenvalues of the quantization error, i.e.,
$\mathbb{E}\lambda_{i}\left(\boldsymbol{\eta}\boldsymbol{\eta}^{\top}\right)$,
yielding the final inequality.

##  5 Numerical Simulations

The efficacy of caldera is assessed by using it to compress three popular open
source LLMs from Meta AI, namely, LLaMa-2 7B, LLaMa-2 70B [34] and LLaMa-3 8B
[26]. The framework is built in PyTorch on top of the QuIP# [35] and LoftQ
[22], and is available at https://github.com/pilancilab/caldera.

Baselines. The full-rank matrix $\mathbf{Q}$, also referred to as the
backbone, is quantized to 2-bits using the LDLQ procedure from QuIP [3, 35],
employing an E8 lattice quantizer [38]. For caldera, which allows even the
low-rank factors, $\mathbf{L}$ and $\mathbf{R}$, to be represented in low-
precision, the quantization is also performed with an E8 lattice. Prior to
running Alg. 1, a randomized Hadamard transform (RHT) is applied to the left
and the right of the input weight matrix, as the incoherence pre-processing
step, to equalize the magnitude of the entries making them more robust to
quantization. In other words, caldera decomposition is performed on
$\widetilde{\mathbf{W}}\triangleq\mathbf{H}_{\rm
L}^{\top}\mathbf{W}\mathbf{H}_{\rm R}$, where $\mathbf{H}_{\rm L}$ and
$\mathbf{H}_{\rm R}$ are Hadamard matrices, right-multiplied by a diagonal
matrix with i.i.id. $\\{\pm 1\\}$ entries. In addition, the Hessian matrix
obtained from the calibration data is substituted by
$\widetilde{\mathbf{H}}\triangleq\mathbf{H}_{\rm
R}^{\top}\mathbf{H}\mathbf{H}_{\rm R}$. As described in [3], this improves the
quantization error incurred by LDLQ. Further details are provided in App. E.2.

Metrics. The performance of caldera is evaluated using perplexity on the test
splits of the Wikitext2 [25] and C4 [6] datasets, as well as task-specific
goodness-of-fit metrics such as zero-shot accuracy for sequence
classification. Specifically, zero-shot accuracy was measured on the
Winogrande [19], RTE [1, 39], PiQA [2], ARC-Easy, and ARC-Challenge [4] tasks.
App. E.3 provides more details regarding these benchmarks. Perplexity was
measured using a sequence length equal to the model’s maximum context length,
i.e., 4096 for LLaMa-2, and 8192 for LLaMa-3. Zero-shot experiments were
performed using EleutherAI’s Language Model Evaluation Harness [9].

###  5.1 Zero-shot Results

Tables 1 and 2 report the perplexities and accuracies for caldera with varying
target rank $(k)$ of $\mathbf{L}$ and $\mathbf{R}$. A smaller value is better
for perplexity, which is defined as the $\exp(\cdot)$ of the training
objective, while zero-shot accuracies are reported as percentages. Per-
parameter bit budgets range from $2.1$ (e.g., rank-$64$ factors in $4$-bit
precision) to $2.4$ bits (e.g., rank-$64$ factors in half precision or
rank-$256$ factors in 4-bit precision). For comparison, the
$\mathbf{Q}+\mathbf{L}\mathbf{R}$ decomposition of weight matrices found in
the QuIP# codebase was performed on each model. For the sake of direct
comparison, fine-tuning of the diagonal matrices in RHT was omitted. As QuIP#
does not support quantized factors, $\mathbf{L}$ and $\mathbf{R}$ are rank-64
in order to ensure that the per-parameter bit-budget remains in the $2-2.4$
range. As another baseline comparison, each model is quantized using QuIP#
without any low-rank factors. Results for the unquantized LLaMa-2 7B, LLaMa-2
70B, and LLaMa-3 8B models are also provided.

Table 1: Zero-shot perplexities (denoted by $\downarrow$) and accuracies ($\uparrow$) for LLaMa-$2$. $\mathrm{B}_{\rm Q}=2$ bits throughout. Method | Rank | $\mathrm{B}_{\rm L}(=\mathrm{B}_{\rm R})$ | Avg Bits |  Wiki2 $\downarrow$ |  C4 $\downarrow$ |  Wino $\uparrow$ |  RTE $\uparrow$ |  PiQA $\uparrow$ |  ArcE $\uparrow$ |  ArcC $\uparrow$
---|---|---|---|---|---|---|---|---|---|---
caldera (7B) | 64 | 16 | 2.4 | 7.36 | 9.47 | 64.6 | 66.4 | 73.7 | 60.8 | 31.7
caldera (7B) | 64 | 4 | 2.1 | 7.37 | 9.74 | 63.7 | 62.1 | 72.3 | 60.9 | 31.7
caldera (7B) | 128 | 4 | 2.2 | 6.76 | 8.83 | 63.8 | 59.9 | 75.1 | 65.1 | 34.6
caldera (7B) | 256 | 4 | 2.4 | 6.19 | 8.14 | 66.0 | 60.6 | 75.6 | 63.6 | 34.0
QuIP# (7B, No FT) | 64 | 16 | 2.4 | 7.73 | 10.0 | 63.1 | 66.8 | 71.7 | 63.2 | 31.7
QuIP# (7B, No FT) | 0 | — | 2 | 8.23 | 10.8 | 61.7 | 57.8 | 69.6 | 61.2 | 29.9
caldera (70B) | 64 | 16 | 2.2 | 4.50 | 6.38 | 75.4 | 71.7 | 79.2 | 71.8 | 43.9
caldera (70B) | 128 | 4 | 2.1 | 5.07 | 7.10 | 72.9 | 62.1 | 78.0 | 73.2 | 43.9
QuIP# (70B, No FT) | 0 | — | 2 | 5.37 | 7.51 | 72.3 | 47.6 | 77.7 | 68.8 | 40.9
Unquantized (7B) | 0 | — | 16 | 5.12 | 6.63 | 67.3 | 63.2 | 78.5 | 69.3 | 40.0
Unquantized (70B) | 0 | — | 16 | 3.12 | 4.97 | 77.0 | 67.9 | 81.1 | 77.7 | 51.1
Table 2: Zero-shot perplexities (denoted by $\downarrow$) and accuracies ($\uparrow$) for LLaMa-$3$ $8$B. $\mathrm{B}_{\rm Q}=2$ bits throughout. Method | Rank | $\mathrm{B}_{\rm L}(=\mathrm{B}_{\rm R})$ | Avg Bits |  Wiki2 $\downarrow$ |  C4 $\downarrow$ |  Wino $\uparrow$ |  RTE $\uparrow$ |  PiQA $\uparrow$ |  ArcE $\uparrow$ |  ArcC $\uparrow$
---|---|---|---|---|---|---|---|---|---|---
caldera | 64 | 16 | 2.4 | 9.22 | 10.5 | 68.9 | 63.9 | 72.9 | 69.9 | 36.5
caldera | 64 | 4 | 2.1 | 10.6 | 11.8 | 66.9 | 58.5 | 71.8 | 68.2 | 34.3
caldera | 128 | 4 | 2.2 | 9.21 | 10.5 | 67.6 | 69.7 | 74.4 | 71.8 | 36.3
caldera | 256 | 4 | 2.4 | 8.22 | 9.56 | 69.7 | 65.0 | 75.1 | 73.2 | 40.0
QuIP# (No FT) | 64 | 16 | 2.4 | 10.9 | 11.8 | 66.5 | 57.0 | 69.6 | 63.8 | 31.0
QuIP# (No FT) | 0 | — | 2 | 13.8 | 15.6 | 63.2 | 52.7 | 67.6 | 57.6 | 28.2
Unquantized | 0 | — | 16 | 5.54 | 7.01 | 73.5 | 68.6 | 79.7 | 80.1 | 50.2

For all but the LLaMa-2 70B model, the rank-$256$ caldera decomposition with
$4$-bit factors had the lowest perplexity and highest accuracy. As caldera
supports quantizing low-rank factors with minimal performance loss, more
singular components can be captured compared to using half-precision factors
while employing the same number of bits. Consequently, the low-rank factors
can regain the performance that was compromised when the backbone $\mathbf{Q}$
was quantized to $2$ bits. Since zero-shot experiments have some inherent
randomness and low-rank regularization effects [32], the zero-shot accuracies
reported here are not as directly indicative of quantization performance as
the perplexity results. In addition, §5.3, demonstrates that degradation in
zero-shot accuracy can be recovered via LoRA fine-tuning. It is worthwhile to
note these results substantiate the claims of [17], which report that low-bit
quantization of LLaMa-$3$ $8$B, significantly deteriorates model performance
across various post-training quantization techniques, more so than with the
LLaMa-$2$ series.

###  5.2 Fine-tuning of Randomized Hadamard Transform (RHT) Parameters

As caldera presents a general optimization framework for matrix decompositions
of the form $\mathbf{Q}+\mathbf{L}\mathbf{R}$, it can easily be extended with
additional heuristics to improve performance. This section serves as a proof
of concept, by examining one such heuristic: Fine-tuning of randomized
Hadamard transform parameters. This technique, proposed in QuIP# [35],
involves fine-tuning the diagonal Rademacher matrices with $\pm 1$ entries in
the RHT to minimize the cross-entropy loss between the output of the original
and quantized models on the calibration dataset. Subsequently, RHT fine-tuning
is performed on the models quantized using caldera in §5.1.111 Since this is
primarily a proof of concept, the fine-tuning is not as extensive as in [35]
due to computational limits. While [35] performs fine-tuning layer-by-layer
prior to doing so on he end-to-end objective, experiments in this section only
include the end-to-end fine-tuning. Furthermore, the fine-tuning is performed
with a sequence length of $512$, as opposed to $4096$ as in [35]. As such, the
QuIP# numbers reported here are different from [35]. Details on specific fine-
tuning hyperparameters can be found in App. E.4.

Table 3: Zero-shot perplexities and accuracies for LLaMa-2 7B, with end-to-end fine-tuning of randomized Hadamard transform parameters. $\mathrm{B}_{\rm Q}=2$ bits throughout. *See Footnote 1.  Method | Rank | $\mathrm{B}_{\rm L}(=\mathrm{B}_{\rm R})$ | Avg Bits |  Wiki2 $\downarrow$ |  C4 $\downarrow$ |  Wino $\uparrow$ |  RTE $\uparrow$ |  PiQA $\uparrow$ |  ArcE $\uparrow$ |  ArcC $\uparrow$
---|---|---|---|---|---|---|---|---|---|---
caldera | 64 | 16 | 2.4 | 6.22 | 8.23 | 64.2 | 63.2 | 76.1 | 63.4 | 34.7
caldera | 64 | 4 | 2.1 | 6.30 | 8.32 | 64.6 | 65.7 | 75.4 | 63.3 | 35.4
caldera | 128 | 4 | 2.2 | 6.09 | 8.06 | 65.1 | 61.0 | 76.5 | 65.1 | 35.6
caldera | 256 | 4 | 2.4 | 5.84 | 7.75 | 65.7 | 60.6 | 76.5 | 64.6 | 35.9
QuIP#* | 64 | 16 | 2.4 | 6.32 | 8.31 | 64.9 | 66.4 | 75.0 | 65.2 | 34.5
QuIP#* | 0 | — | 2 | 6.58 | 8.62 | 64.4 | 53.4 | 75.0 | 64.8 | 34.0
Table 4: Zero-shot perplexities and accuracies for LLaMa-3 8B, with end-to-end fine-tuning of randomized Hadamard transform parameters. $\mathrm{B}_{\rm Q}=2$ bits throughout. *See Footnote 1.  Method | Rank | $\mathrm{B}_{\rm L}(=\mathrm{B}_{\rm R})$ | Avg Bits |  Wiki2 $\downarrow$ |  C4 $\downarrow$ |  Wino $\uparrow$ |  RTE $\uparrow$ |  PiQA $\uparrow$ |  ArcE $\uparrow$ |  ArcC $\uparrow$
---|---|---|---|---|---|---|---|---|---|---
caldera | 64 | 16 | 2.4 | 7.63 | 8.9 | 70.3 | 70.8 | 75.4 | 72.4 | 39.0
caldera | 64 | 4 | 2.1 | 8.06 | 9.34 | 69.5 | 64.3 | 76.0 | 71.5 | 40.0
caldera | 128 | 4 | 2.2 | 7.76 | 9.02 | 69.4 | 63.9 | 76.0 | 73.7 | 41.8
caldera | 256 | 4 | 2.4 | 7.34 | 8.68 | 70.3 | 70.4 | 76.5 | 73.6 | 42.3
QuIP#* | 64 | 16 | 2.4 | 7.92 | 9.15 | 68.4 | 58.1 | 74.9 | 72.3 | 40.4
QuIP#* | 0 | — | 2 | 8.44 | 9.75 | 67.5 | 57.8 | 72.9 | 67.6 | 37.3

Perplexity and zero-shot results in Tables 3 and 4 match the trends in §5.1,
i.e., caldera with rank-$256$ factors typically performs best, with the
exception of RTE. In addition, perplexities are substantially lower than
without the fine-tuning of randomized Hadamard transform parameters.

###  5.3 Low Rank Adaptation (LoRA) Fine-tuning Results

Once the $\mathbf{Q}+\mathbf{L}\mathbf{R}$ decomposition with target rank $k$
is obtained, and $k$ takes values $64,128$ and $256$, fine-tuning the top
$r\;(\leq k)$ singular components on a task-specific dataset can recover the
performance lost due to quantization. Throughout all experiments in Table 5,
$r=64$ is chosen and those singular components are fine-tuned to $16$-bit
precision, i.e., $\rm BF16$ format. In other words, the approximation is
written as
$\mathbf{W}\approx\mathbf{Q}+\mathbf{L}_{1}\mathbf{R}_{1}+\mathbf{L}_{2}\mathbf{R}_{2}$,
where $\mathbf{L}_{1}\in\mathbb{R}^{n\times r}$,
$\mathbf{L}_{2}\in\mathbb{R}^{n\times(k-r)}$,
$\mathbf{R}_{1}\in\mathbb{R}^{r\times d}$,
$\mathbf{R}_{2}\in\mathbb{R}^{(k-r)\times d}$,
$\mathbf{L}=[\mathbf{L}_{1}\mid\mathbf{L}_{2}]$,
$\mathbf{R}^{\top}=[\mathbf{R}_{1}^{\top}\mid\mathbf{R}_{2}^{\top}]$. The
value of $r$ is set to $64$ and $\mathbf{L}_{2},\mathbf{R}_{2}$ are fined-
tuned to $\mathbf{L}_{\rm bf16},\mathbf{R}_{\rm bf16}$ using low-rank
adaptation similar to [16, 22, 13]. Doing this significantly on a small task-
specific dataset like WikiText2, RTE, or Winogrande, can noticeably boost the
zero-shot accuracy, as can be seen from Table 5.222There is an element of
stochasticity in fine-tuning, so the final accuracies listed in Table 5 for
different caldera parameters are not directly indicative of the smaller error
(i.e.,
$\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}$) of the initialization. Rather, they show that low-rank adaptation can
recover accuracy degradation from quantization.

Table 5: caldera fine-tuning results for LLaMa-2 7B and LLaMa-3 8B. $\mathrm{B}_{\rm L}$, $\mathrm{B}_{\rm R}$ are the bit-budgets of $\mathbf{L}$ and $\mathbf{R}$ for the low-rank initialization. Rank-$64$ fine-tuned factors are represented in $\rm BF16$ precision. | LLaMa-2 7B | LLaMa-3 8B
---|---|---
Method | Rank | $\mathrm{B}_{\rm Q}$ | $\mathrm{B}_{\rm L}(=\mathrm{B}_{\rm R})$ | RHT FT | Avg Bits |  Wiki2 $\downarrow$ |  RTE $\uparrow$ |  Wino $\uparrow$ |  Wiki2 $\downarrow$ |  RTE $\uparrow$ |  Wino $\uparrow$
caldera | 64 | 2 | 16 | No | 2.4 | 6.06 | 82.31 | 84.06 | 7.91 | 84.48 | 85.56
caldera | 64 | 2 | 16 | Yes | 2.4 | 5.89 | 85.19 | 85.32 | 7.88 | 86.28 | 88.16
caldera | 64 | 2 | 4 | No | 2.4 | 6.01 | 81.23 | 84.06 | 8.33 | 85.56 | 88.40
caldera | 64 | 2 | 4 | Yes | 2.4 | 5.91 | 85.56 | 83.42 | 7.96 | 87.00 | 88.40
caldera | 128 | 2 | 4 | No | 2.5 | 5.84 | 83.75 | 85.32 | 7.84 | 84.84 | 88.63
caldera | 128 | 2 | 4 | Yes | 2.5 | 5.77 | 84.12 | 85.00 | 7.68 | 86.64 | 88.00
caldera | 256 | 2 | 4 | No | 2.7 | 5.61 | 83.75 | 85.4 | 7.44 | 86.28 | 88.08
caldera | 256 | 2 | 4 | Yes | 2.7 | 5.55 | 86.28 | 84.93 | 7.44 | 85.20 | 89.19
LoftQ | 64 | 2 | 16 | — | 2.4 | 7.85 | — | — | — | — | —
LoftQ | 64 | 2.5 | 16 | — | 2.9 | 5.78 | — | — | — | — | —
LQ-LoRA | 64 | 2.75 | 8 | — | 2.95 | 5.67 | — | 72.4 | — | — | —

Experimental details can be found in App. E.4. For each dataset, ten
checkpoints are saved during the course of fine-tuning, and the best test
performance is reported in Table 5. For datasets where test labels are not
available, evaluation performance is reported instead.

For comparison, results from the LoftQ [22] and LQ-LoRA [13] papers are also
reported, where available. As these papers were published before the release
of LLaMa-3, only LLaMa-2 results are available.333Some LLaMa-3 results for
LoftQ are present on its GitHub repository, but none for the tasks evaluated
here. In each case, caldera achieves better performance at a lower bit budget.

##  6 Conclusions

In this work, the problem of obtaining a low-precision and low-rank
decomposition of an LLM weight matrix was considered. A
$\mathbf{Q}+\mathbf{L}\mathbf{R}$ decomposition efficiently captures the high
singular components of the weight matrix with sufficient fidelity, while
coarsely compressing the less significant moderate-to-low singular components.
An optimization-theoretically motivated algorithm was proposed to obtain this
decomposition, which iteratively optimized the quantized backbone $\mathbf{Q}$
and the low-rank factors $\mathbf{L},\mathbf{R}$. Additionally, it was shown
that $\mathbf{L}$ and $\mathbf{R}$ can be efficiently fine-tuned using low-
rank adaptation to boost the zero-shot performance of the quantized model. By
utilizing a rank-constrained regression framework, an upper bound was
established on the approximation error of the algorithm, and it was shown that
this upper bound can be significantly smaller than prior bounds in the
literature. Finally, the proposed method was empirically evaluated by
compressing the LlaMA family of LLMs in the challenging sub-$2.5$ bits per
parameter regime. The proposed approach can also be used to complement
existing compression strategies; thereby making it efficient to distribute
compressed LLMs and deploy them on regular consumer hardware, making them more
accessible to researchers.

## Acknowledgements

This work was supported in part by the National Science Foundation (NSF) under
Grant DMS-2134248; in part by the NSF CAREER Award under Grant CCF-2236829; in
part by the U.S. Army Research Office Early Career Award under Grant
W911NF-21-1-0242; and in part by the Office of Naval Research under Grant
N00014-24-1-2164.

## References

  * Bentivogli et al. [2009] L. Bentivogli, I. Dagan, H. T. Dang, D. Giampiccolo, and B. Magnini.  The Fifth PASCAL Recognizing Textual Entailment Challenge, 2009.
  * Bisk et al. [2020] Y. Bisk, R. Zellers, R. L. Bras, J. Gao, and Y. Choi.  PIQA: Reasoning about Physical Commonsense in Natural Language.  In _Thirty-Fourth AAAI Conference on Artificial Intelligence_ , 2020.
  * Chee et al. [2023] J. Chee, Y. Cai, V. Kuleshov, and C. D. Sa.  QuIP: 2-Bit Quantization of Large Language Models With Guarantees.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * Clark et al. [2018] P. Clark, I. Cowhey, O. Etzioni, T. Khot, A. Sabharwal, C. Schoenick, and O. Tafjord.  Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge.  _arXiv:1803.05457v1_ , 2018.
  * Dettmers et al. [2023] T. Dettmers, A. Pagnoni, A. Holtzman, and L. Zettlemoyer.  QLoRA: Efficient Finetuning of Quantized LLMs.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=OUIFPHEgJU.
  * Dodge et al. [2021] J. Dodge, M. Sap, A. Marasović, W. Agnew, G. Ilharco, D. Groeneveld, M. Mitchell, and M. Gardner.  Documenting Large Webtext Corpora: A Case Study on the Colossal Clean Crawled Corpus, 2021.
  * Egiazarian et al. [2024] V. Egiazarian, A. Panferov, D. Kuznedelev, E. Frantar, A. Babenko, and D. Alistarh.  Extreme Compression of Large Language Models via Additive Quantization, 2024.  URL https://arxiv.org/abs/2401.06118.
  * Frantar et al. [2023] E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh.  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] L. Gao, J. Tow, B. Abbasi, S. Biderman, S. Black, A. DiPofi, C. Foster, L. Golding, J. Hsu, A. Le Noac’h, H. Li, K. McDonell, N. Muennighoff, C. Ociepa, J. Phang, L. Reynolds, H. Schoelkopf, A. Skowron, L. Sutawika, E. Tang, A. Thite, B. Wang, K. Wang, and A. Zou.  A framework for few-shot language model evaluation, 12 2023.  URL https://zenodo.org/records/10256836.
  * Golub and van Loan [2013] G. H. Golub and C. F. van Loan.  _Matrix Computations_.  JHU Press, fourth edition, 2013.  ISBN 1421407949 9781421407944.  URL http://www.cs.cornell.edu/cv/GVL4/golubandvanloan.htm.
  * Gray and Stockham [1993] R. Gray and T. Stockham.  Dithered quantizers.  _IEEE Transactions on Information Theory_ , 39(3):805–812, 1993.  doi: 10.1109/18.256489.
  * Gugger et al. [2022] S. Gugger, L. Debut, T. Wolf, P. Schmid, Z. Mueller, S. Mangrulkar, M. Sun, and B. Bossan.  Accelerate: Training and inference at scale made simple, efficient and adaptable.  https://github.com/huggingface/accelerate, 2022.
  * Guo et al. [2023] H. Guo, P. Greengard, E. P. Xing, and Y. Kim.  LQ-LoRA: Low-rank Plus Quantized Matrix Decomposition for Efficient Language Model Finetuning.  arxiv:2311.12023, 2023.  URL https://arxiv.org/abs/2311.12023.
  * Halko et al. [2011] N. Halko, P. G. Martinsson, and J. A. Tropp.  Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.  _SIAM Review_ , 53(2):217–288, 2011.  doi: 10.1137/090771806.  URL https://doi.org/10.1137/090771806.
  * Hsu et al. [2022] Y.-C. Hsu, T. Hua, S. Chang, Q. Lou, Y. Shen, and H. Jin.  Language model compression with weighted low-rank factorization.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=uPv9Y3gmAI5.
  * Hu et al. [2022] E. J. Hu, yelong shen, P. Wallis, Z. Allen-Zhu, Y. Li, S. Wang, L. Wang, and W. Chen.  LoRA: Low-Rank Adaptation of Large Language Models.  In _International Conference on Learning Representations_ , 2022.  URL https://openreview.net/forum?id=nZeVKeeFYf9.
  * Huang et al. [2024] W. Huang, X. Ma, H. Qin, X. Zheng, C. Lv, H. Chen, J. Luo, X. Qi, X. Liu, and M. Magno.  How Good Are Low-bit Quantized LLaMA3 Models? An Empirical Study, 2024.
  * Kaushal et al. [2023] A. Kaushal, T. Vaidhya, and I. Rish.  LORD: Low Rank Decomposition Of Monolingual Code LLMs For One-Shot Compression, 2023.
  * Keisuke et al. [2019] S. Keisuke, L. B. Ronan, B. Chandra, and C. Yejin.  WinoGrande: An Adversarial Winograd Schema Challenge at Scale, 2019.
  * Krishnamoorthy and Menon [2013] A. Krishnamoorthy and D. Menon.  Matrix inversion using cholesky decomposition.  In _2013 Signal Processing: Algorithms, Architectures, Arrangements, and Applications (SPA)_ , pages 70–72, 2013.
  * Levesque et al. [2012] H. J. Levesque, E. Davis, and L. Morgenstern.  The winograd schema challenge.  In _Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning_ , KR’12, page 552–561. AAAI Press, 2012.  ISBN 9781577355601.
  * Li et al. [2023] Y. Li, Y. Yu, C. Liang, P. He, N. Karampatziakis, W. Chen, and T. Zhao.  LoftQ: LoRA-Fine-Tuning-Aware Quantization for Large Language Models.  arxiv:2310.08659, 2023.  URL https://arxiv.org/abs/2310.08659.
  * Liu et al. [2024] S.-Y. Liu, C.-Y. Wang, H. Yin, P. Molchanov, Y.-C. F. Wang, K.-T. Cheng, and M.-H. Chen.  Dora: Weight-decomposed low-rank adaptation, 2024.
  * Ma et al. [2024] S. Ma, H. Wang, L. Ma, L. Wang, W. Wang, S. Huang, L. Dong, R. Wang, J. Xue, and F. Wei.  The era of 1-bit llms: All large language models are in 1.58 bits, 2024.
  * Merity et al. [2016] S. Merity, C. Xiong, J. Bradbury, and R. Socher.  Pointer Sentinel Mixture Models, 2016.
  * Meta AI [2024] Meta AI.  Introducing Meta Llama 3: The most capable openly available LLM to date.  https://ai.meta.com/blog/meta-llama-3/, 2024.  Accessed: 2024-05-07.
  * Nagel et al. [2020] M. Nagel, R. A. Amjad, M. Van Baalen, C. Louizos, and T. Blankevoort.  Up or Down? Adaptive Rounding for Post-Training Quantization.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119, pages 7197–7206, 2020.
  * Rajbhandari et al. [2020] S. Rajbhandari, J. Rasley, O. Ruwase, and Y. He.  Zero: Memory optimizations toward training trillion parameter models, 2020.
  * Rasley et al. [2020] J. Rasley, S. Rajbhandari, O. Ruwase, and Y. He.  Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, KDD ’20, page 3505–3506, New York, NY, USA, 2020. Association for Computing Machinery.  ISBN 9781450379984.  doi: 10.1145/3394486.3406703.  URL https://doi.org/10.1145/3394486.3406703.
  * Saha et al. [2023] R. Saha, V. Srivastava, and M. Pilanci.  Matrix Compression via Randomized Low Rank and Low Precision Factorization.  In _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.  URL https://openreview.net/forum?id=rxsCTtkqA9.
  * Schuchman [1964] L. Schuchman.  Dither Signals and Their Effect on Quantization Noise.  _IEEE Transactions on Communication Technology_ , 12(4):162–165, 1964.  doi: 10.1109/TCOM.1964.1088973.
  * Sharma et al. [2023] P. Sharma, J. T. Ash, and D. Misra.  The Truth is in There: Improving Reasoning in Language Models with Layer-Selective Rank Reduction, 2023.
  * Together Computer [2023] Together Computer.  Redpajama: an open dataset for training large language models, October 2023.  URL https://github.com/togethercomputer/RedPajama-Data.
  * Touvron et al. [2023] H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, D. Bikel, L. Blecher, C. C. Ferrer, M. Chen, G. Cucurull, D. Esiobu, J. Fernandes, J. Fu, W. Fu, B. Fuller, C. Gao, V. Goswami, N. Goyal, A. Hartshorn, S. Hosseini, R. Hou, H. Inan, M. Kardas, V. Kerkez, M. Khabsa, I. Kloumann, A. Korenev, P. S. Koura, M.-A. Lachaux, T. Lavril, J. Lee, D. Liskovich, Y. Lu, Y. Mao, X. Martinet, T. Mihaylov, P. Mishra, I. Molybog, Y. Nie, A. Poulton, J. Reizenstein, R. Rungta, K. Saladi, A. Schelten, R. Silva, E. M. Smith, R. Subramanian, X. E. Tan, B. Tang, R. Taylor, A. Williams, J. X. Kuan, P. Xu, Z. Yan, I. Zarov, Y. Zhang, A. Fan, M. Kambadur, S. Narang, A. Rodriguez, R. Stojnic, S. Edunov, and T. Scialom.  Llama 2: Open Foundation and Fine-Tuned Chat Models, 2023.
  * Tseng et al. [2024] A. Tseng, J. Chee, Q. Sun, V. Kuleshov, and C. D. Sa.  QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks, 2024.
  * Udell and Townsend [2019] M. Udell and A. Townsend.  Why are big data matrices approximately low rank?  _SIAM Journal on Mathematics of Data Science_ , 1(1):144–160, 2019.  doi: 10.1137/18M1183480.  URL https://doi.org/10.1137/18M1183480.
  * Vershynin [2018] R. Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.  doi: 10.1017/9781108231596.
  * Viazovska [2017] M. Viazovska.  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.
  * Wang et al. [2019] A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and S. R. Bowman.  GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding, 2019.  In the Proceedings of ICLR.
  * Xiang et al. [2012] S. Xiang, Y. Zhu, X. Shen, and J. Ye.  Optimal exact least squares rank minimization.  In _Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’12, page 480–488, New York, NY, USA, 2012. Association for Computing Machinery.  ISBN 9781450314626.  doi: 10.1145/2339530.2339609.  URL https://doi.org/10.1145/2339530.2339609.
  * Xiao et al. [2023] G. Xiao, J. Lin, M. Seznec, H. Wu, J. Demouth, and S. Han.  SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models.  In _Proceedings of the 40th International Conference on Machine Learning_ , 2023.
  * Yao et al. [2023] Z. Yao, X. Wu, C. Li, S. Youn, and Y. He.  ZeroQuant-V2: Exploring Post-training Quantization in LLMs from Comprehensive Study to Low Rank Compensation, 2023.
  * Yuan et al. [2023] Z. Yuan, Y. Shang, Y. Song, Q. Wu, Y. Yan, and G. Sun.  ASVD: Activation-aware Singular Value Decomposition for Compressing Large Language Models, 2023.
  * Zhang et al. [2024] C. Zhang, J. Cheng, G. A. Constantinides, and Y. Zhao.  LQER: Low-Rank Quantization Error Reconstruction for LLMs, 2024.

###### Contents

  1. 1 Introduction
    1. 1.1 Significance and Related Works
  2. 2 Problem Formulation
  3. 3 Proposed Algorithm: Calibration-Aware Low-Precision Decomposition with Low Rank Adaptation
  4. 4 Approximation Error Analysis
    1. 4.1 Analysis Outline
  5. 5 Numerical Simulations
    1. 5.1 Zero-shot Results
    2. 5.2 Fine-tuning of Randomized Hadamard Transform (RHT) Parameters
    3. 5.3 Low Rank Adaptation (LoRA) Fine-tuning Results
  6. 6 Conclusions
  7. A Notations
  8. B Rank-constrained Regression
  9. C Derivations for Calibration-Aware Low-Precision and Low-Rank Decomposition: caldera
    1. C.1 Update Equations for Low-Rank Factors in LPLRFactorize submodule
    2. C.2 Dynamic Ranges of Quantizers
    3. C.3 Proof of Lemma C.3: Approximation Error Upper Bound for LPLRFactorize
    4. C.4 Proof of Thm. 4.1: Approximation Error Upper Bound for caldera
  10. D Computational Complexity of caldera
  11. E Additional Experimental Details
    1. E.1 System Details
    2. E.2 Parameters of caldera Quantization
    3. E.3 Details about Goodness-of-Fit Metrics
    4. E.4 Fine-tuning Parameter Details
    5. E.5 Computation of Average Bit Budget Per-Parameter
    6. E.6 Additional Notes on Numerical Simulations
  12. F Additional Numerical Simulations
    1. F.1 Ablation Study of caldera Parameters with respect to Frobenius Norm Error
  13. G Auxiliary Results
    1. G.1 Useful Results from Linear Algebra and Probability
    2. G.2 Uniformly dithered scalar quantizer
  14. H Limitations and Further Discussions

##  Appendix A Notations

This section begins by outlining key notations used in both linear algebra and
probability theory. Boldface uppercase and lowercase letters, such as
$\mathbf{A}$ and $\mathbf{a}$, represent matrices and vectors respectively.
$\mathbf{I}$ denotes the identity matrix, and its dimension is assumed to be
imminent from the context. The first $k$ columns of the identity matrix
$\mathbf{I}$ as $\mathbf{I}_{k}$, and let $\overline{\mathbf{I}}_{k}$ be the
submatrix formed by the last $k$ columns. The singular values of $\mathbf{A}$
are denoted by $\sigma_{\rm
max}(\mathbf{A})=\sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{r}=\sigma_{\rm
min}(\mathbf{A})$, where $r={\rm rank}(\mathbf{A})$. Similarly, the
eigenvalues are denoted as
$\lambda_{1}(\mathbf{A}),\ldots,\lambda_{r}(\mathbf{A})$. The max-norm of
$\mathbf{A}$ is defined as $\left\lVert A\right\rVert_{\rm max}={\rm
max}_{i,j}|A_{ij}|$, the spectral norm of $\mathbf{A}$ is defined as
$\left\lVert\mathbf{A}\right\rVert_{2}=\sup_{\left\lVert\mathbf{x}\right\rVert=1}\left\lVert\mathbf{A}\mathbf{x}\right\rVert=\sigma_{\rm
max}(\mathbf{A})$, and the Frobenius norm is
$\left\lVert\mathbf{A}\right\rVert_{\rm
F}=\left(\sum_{i,j}A_{ij}^{2}\right)^{1/2}=\textrm{Tr}\left(\mathbf{A}^{\top}\mathbf{A}\right)=\left(\sum_{k\in[r]}\sigma_{k}^{2}\right)^{1/2}$.
For any matrix $\mathbf{X}$, its Moore-Penrose pseudo-inverse is denoted by
$\mathbf{X}^{\dagger}$. The notations $\approx$, $\lesssim$ and $\gtrsim$ are
used to denote approximate equality and inequalities that hold asymptotically
in the limit when dimensions grow to infinity. In other words, for any two
functions $A(n)$ and $B(n)$,

$A(n)\lesssim
B(n)\quad\text{iff}\quad\lim_{n\to\infty}A(n)\leq\lim_{n\to\infty}B(n).$

Notations $\approx$ and $\gtrsim$ are defined analogously. Wherever relevant,
dimension-dependent terms are highlighted blue.

Table 6: Notations used in this paper Notation |  Description |  Remarks
---|---|---
$\mathbf{W}$ |  LLM weight matrix of any layer |  $\mathbf{W}\in\mathbb{R}^{n\times d}$
$\mathbf{Q}$, $\mathbf{L}$, $\mathbf{R}$ |  Backbone, left and right low rank factors |  $\mathbf{Q}\in\mathbb{R}^{n\times d}$, $\mathbf{L}\in\mathbb{R}^{n\times k}$, and $\mathbf{R}\in\mathbb{R}^{k\times d}$ are represented using $\mathrm{B}_{\rm Q}$, $\mathrm{B}_{\rm L}$, and $\mathrm{B}_{\rm R}$ bits, respectively. Approximation: $\mathbf{W}\approx\mathbf{Q}+\mathbf{L}\mathbf{R}$
$\mathbf{X}$ |  Calibration data matrix |  $\mathbf{X}\in\mathbb{R}^{m\times d}$. Input activation for each layer. Computed once offline for each LLM.
$\mathbf{H}$ |  $\mathbf{H}\triangleq\frac{1}{m}\mathbf{X}^{\top}\mathbf{X}$ |  (Scaled) Hessian of least-squares objectives (1) and (3). Computed offline once.
$k$ |  Target rank for low-rank factors |  $k=64,128,256$ in our expts.
$\mathrm{Q}_{\rm Q},\mathrm{B}_{\rm Q},\mathrm{R}$ |  Quantizer, bit-budget and dynamic range for the backbone |  Operates on matrices in $\mathbb{R}^{n\times d}$.
$\mathrm{Q}_{\rm L},\mathrm{B}_{\rm L},\mathrm{R}_{\rm L}$ |  Quantizer, bit-budget and dynamic range for the left low-rank factor |  Operates on matrices in $\mathbb{R}^{n\times k}$.
$\mathrm{Q}_{\rm R},\mathrm{B}_{\rm R},\mathrm{R}_{\rm R}$ |  Quantizer, bit-budget and dynamic range for the right low-rank factor |  Operates on matrices in $\mathbb{R}^{k\times d}$.
$\mathbf{M}$ |  Strictly upper triangular matrix from the LDL decomposition of $m\mathbf{H}$ |  $m\mathbf{H}=(\mathbf{M}+\mathbf{I})\mathbf{D}(\mathbf{M}+\mathbf{I})^{\top}$
$\mathbf{D}$ |  Diagonal matrix obtained from the LDL decomposition of $m\mathbf{H}$ |  $m\mathbf{H}=(\mathbf{M}+\mathbf{I})\mathbf{D}(\mathbf{M}+\mathbf{I})^{\top}$
$\boldsymbol{\eta}$ |  Quantization error of LDLQ, given by $\boldsymbol{\eta}\triangleq\mathrm{Q}_{\rm Q}(\mathbf{Q}+(\mathbf{W}-\mathbf{Q})\mathbf{M})-(\mathbf{Q}+(\mathbf{W}-\mathbf{Q})\mathbf{M})$ |  $\boldsymbol{\eta}\in\mathbb{R}^{n\times d}$ is assumed to consist of i.i.d. entries for analytical tractability.
$\mathbf{E}_{\rm L},\mathbf{E}_{\rm R}$ |  Quantization error matrices from quantizing left and right factors |  $\mathbf{E}_{\rm L}\in\mathbb{R}^{n\times k}$ and $\mathbf{E}_{\rm R}\in\mathbb{R}^{k\times d}$ consists of zero-mean random variables with bounded variance.

##  Appendix B Rank-constrained Regression

Recall that the submatrix formed by the first $m$ columns of the identity
matrix $\mathbf{I}$ is denoted as $\mathbf{I}_{m}$, and let
$\overline{\mathbf{I}}_{m}$ be the submatrix formed by the last $m$ columns.
The dimension of $\mathbf{I}$ is inferred depending on context. Consider the
following:

$\min_{{\rm rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm F}^{2}.$ (7)

Although this problem is non-convex, it can be solved to global optimality via
two SVDs. The following lemma characterizes the solution the rank-constrained
regression in (5).

######  Lemma B.1.

(Global optimality of rank-constrained regression) Suppose
$\mathbf{Y}\in\mathbb{R}^{m\times n}$ is given, and suppose
$\mathbf{X}\in\mathbb{R}^{m\times d}$ is full rank, i.e., ${\rm
rank}(\mathbf{X})=\min\\{m,d\\}$, with SVD,
$\mathbf{X}=\mathbf{U}\widetilde{\boldsymbol{\Sigma}}\mathbf{V}^{\top}$.
Furthermore, let
$\grave{\mathbf{U}}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}$
denote the full SVD of $\mathbf{U}^{\top}\mathbf{Y}$ if $m\leq d$, or the full
SVD of $\left(\mathbf{U}\mathbf{I}_{d}\right)^{\top}\mathbf{Y}$ if $m>d$.
Then, for $k\leq m$, the solution of (5) is given by

$\mathbf{Z}_{*}:=\mathop{\rm arg\hskip 2.84526ptmin}_{{\rm
rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm
F}^{2}=\begin{cases}\left(\mathbf{V}\mathbf{I}_{m}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)\quad\text{if}\quad
m\leq d,\\\
\left(\mathbf{V}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\mathbf{V}^{\top}\right)\hskip
2.15277pt\qquad\text{otherwise.}\end{cases}$ (8)

Here, $\boldsymbol{\Sigma}$ is a diagonal matrix of the non-zero singular
values of $\mathbf{X}$, defined as
$\boldsymbol{\Sigma}:=\widetilde{\boldsymbol{\Sigma}}\mathbf{I}_{m}\in\mathbb{R}^{m\times
m}$ when $m\leq d$, and
$\boldsymbol{\Sigma}:=\mathbf{I}_{d}^{\top}\widetilde{\boldsymbol{\Sigma}}\in\mathbb{R}^{d\times
d}$ when $d<m$. Additionally, the optimal value is

$\displaystyle\min_{{\rm rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm F}^{2}$
$\displaystyle\qquad=\left\lVert\mathbf{X}\mathbf{Z}_{*}-\mathbf{Y}\right\rVert_{\rm
F}^{2}=\begin{cases}\qquad\qquad\qquad\sum_{i=k+1}^{m}\sigma_{i}^{2}\left(\mathbf{Y}\right),\quad\hskip
58.12482pt\text{if}\quad m\leq d,\\\
\sum_{i=k+1}^{m}\sigma_{i}^{2}\left((\mathbf{U}\mathbf{I}_{d})^{\top}\mathbf{Y}\right)+\left\lVert(\mathbf{U}\overline{\mathbf{I}}_{m-d})^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2},\quad\;\text{otherwise.}\end{cases}$ (9)

###### Proof.

Case $\mathbf{m\leq d}$:  Since the full SVD of
$\mathbf{X}\in\mathbb{R}^{m\times d}$ is
$\mathbf{X}=\mathbf{U}\widetilde{\boldsymbol{\Sigma}}\mathbf{V}^{\top}$, where
$\mathbf{U}\in\mathbb{R}^{m\times m}$,
$\widetilde{\boldsymbol{\Sigma}}\in\mathbb{R}^{m\times d}$, and
$\mathbf{V}\in\mathbb{R}^{d\times d}$, the last $(d-m)$ columns of
$\widetilde{\boldsymbol{\Sigma}}$ will be zero, i.e.,
$\widetilde{\boldsymbol{\Sigma}}\overline{\mathbf{I}}_{m-d}=\mathbf{0}$. Let
$\mathbf{Z}^{\prime}:=\mathbf{V}^{\top}\mathbf{Z}\in\mathbb{R}^{d\times n}$ be
the transformed optimization variable. Since $\mathbf{V}$ is a unitary matrix,
${\rm rank}(\mathbf{Z})\leq k$ if and only if ${\rm
rank}(\mathbf{Z}^{\prime})\leq k$. Splitting
$\mathbf{Z}^{\prime}\in\mathbb{R}^{d\times n}$ into
$\mathbf{Z}^{\prime\prime}:=\mathbf{I}_{m}^{\top}\mathbf{Z}^{\prime}\in\mathbb{R}^{m\times
n}$ and
$\overline{\mathbf{Z}}^{\prime\prime}:=\overline{\mathbf{I}}_{d-m}^{\top}\mathbf{Z}^{\prime}\in\mathbb{R}^{(d-m)\times
n}$, it can be seen that
$\widetilde{\boldsymbol{\Sigma}}\mathbf{Z}^{\prime}=\widetilde{\boldsymbol{\Sigma}}\mathbf{I}_{d}\mathbf{Z}^{\prime\prime}+\widetilde{\boldsymbol{\Sigma}}\overline{\mathbf{I}}_{m-d}\overline{\mathbf{Z}}^{\prime\prime}=\boldsymbol{\Sigma}\mathbf{Z}^{\prime\prime}$,
where
$\boldsymbol{\Sigma}:=\widetilde{\boldsymbol{\Sigma}}\mathbf{I}_{m}\in\mathbb{R}^{m\times
m}$ is a diagonal matrix comprised of the non-zero singular values of
$\mathbf{X}$. Then,

$\displaystyle\min_{{\rm rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm
F}^{2}\equiv\min_{{\rm rank}(\mathbf{Z}^{\prime})\leq
k}\left\lVert\widetilde{\boldsymbol{\Sigma}}\mathbf{Z}^{\prime}-\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}\equiv\min_{{\rm rank}(\mathbf{Z}^{\prime})\leq
k}\left\lVert\boldsymbol{\Sigma}\mathbf{Z}^{\prime\prime}-\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}.$ (10)

Note that the objective function value is independent of
$\overline{\mathbf{Z}}^{\prime\prime}$, as
$\overline{\mathbf{Z}}^{\prime\prime}$ lies in the null space of
$\mathbf{X}^{\top}$. Since $\mathbf{X}$ is full rank, $\boldsymbol{\Sigma}$ is
invertible, and the minimization in (10) is equivalent to

$\min_{\rm rank(\widetilde{\mathbf{Z}})\leq
k}\left\lVert\widetilde{\mathbf{Z}}-\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}=\sum_{i=k+1}^{m}\sigma_{i}^{2}\left(\mathbf{Y}\right),$ (11)

where
$\widetilde{\mathbf{Z}}:=\boldsymbol{\Sigma}\mathbf{Z}^{\prime\prime}\in\mathbb{R}^{m\times
n}$. The equality in (11) follows as a consequence of Eckart-Young-Mirsky
theorem (lemma G.1), which states that
$\lVert\widetilde{\mathbf{Z}}-\mathbf{U}^{\top}\mathbf{Y}\rVert_{\rm F}^{2}$
is minimized by taking the best rank-$k$ approximation of
$\mathbf{U}^{\top}\mathbf{Y}$, and the fact that the singular values of
$\mathbf{U}^{\top}\mathbf{Y}$ and $\mathbf{Y}$ are the same as $\mathbf{U}$ is
unitary. Moreover, as the SVD of $\mathbf{U}^{\top}\mathbf{Y}$ is
$\grave{\mathbf{U}}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}$,

$\displaystyle\widetilde{\mathbf{Z}}_{*}:=\mathop{\rm arg\hskip
2.84526ptmin}_{\rm rank(\widetilde{\mathbf{Z}})\leq
k}\left\lVert\widetilde{\mathbf{Z}}-\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}=\left(\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)$
and,
$\displaystyle\mathbf{Z}^{\prime\prime}_{*}:=\boldsymbol{\Sigma}^{-1}\widetilde{\mathbf{Z}}_{*}=\left(\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right).$
(12)

In other words, if $\mathbf{Z}^{\prime}_{*}$ denotes the solution of the
middle optimization problem in (10),
$\mathbf{I}_{m}^{\top}\mathbf{Z}_{*}=\mathbf{Z}^{\prime\prime}_{*}$.
Furthermore, note that setting
$\overline{\mathbf{I}}_{d-m}^{\top}\widetilde{\mathbf{Z}}_{*}=\mathbf{0}$
ensures ${\rm rank}(\mathbf{Z}^{\prime}_{*})={\rm
rank}(\mathbf{Z}^{\prime\prime}_{*})\leq k$, while keeping the objective value
in (10) unchanged. Hence, an optimal solution is given by

$\mathbf{Z}^{\prime}_{*}=\begin{bmatrix}\left(\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)\\\
\mathbf{0}_{(d-m)\times n}\end{bmatrix}\quad\text{and,
}\quad\mathbf{Z}_{*}=\mathbf{V}\mathbf{Z}^{\prime}_{*}=\left(\mathbf{V}\mathbf{I}_{m}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right).$
(13)

Case $\mathbf{m>d}$: Recalling that the full SVD of
$\mathbf{X}\in\mathbb{R}^{m\times d}$ is
$\mathbf{X}=\mathbf{U}\widetilde{\boldsymbol{\Sigma}}\mathbf{V}^{\top}$, where
$\mathbf{U}\in\mathbb{R}^{m\times m}$,
$\widetilde{\boldsymbol{\Sigma}}\in\mathbb{R}^{m\times d}$, and
$\mathbf{V}\in\mathbb{R}^{d\times d}$, in this case, the last $m-d$ rows of
$\widetilde{\boldsymbol{\Sigma}}$ will be zero, i.e.,
$\overline{\mathbf{I}}_{m-d}^{\top}\widetilde{\boldsymbol{\Sigma}}=\mathbf{0}$.
Denote $\mathbf{Z}^{\prime}:=\mathbf{V}^{\top}\mathbf{Z}$. This time, as
$\boldsymbol{\Sigma}:=\mathbf{I}_{d}^{\top}\widetilde{\boldsymbol{\Sigma}}$,

$\displaystyle\min_{{\rm rank}(\mathbf{Z})\leq
k}\left\lVert\mathbf{X}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm F}^{2}$
$\displaystyle\equiv\min_{{\rm rank}(\mathbf{Z}^{\prime})\leq
k}\left\lVert\widetilde{\boldsymbol{\Sigma}}\mathbf{Z}^{\prime}-\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}$ $\displaystyle\equiv\min_{{\rm rank}(\mathbf{Z}^{\prime})\leq
k}\left\lVert\boldsymbol{\Sigma}\mathbf{Z}^{\prime}-\mathbf{I}_{d}^{\top}\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}+\left\lVert\overline{\mathbf{I}}_{m-d}^{\top}\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}$ $\displaystyle\equiv\min_{{\rm rank}(\mathbf{Z}^{\prime\prime})\leq
k}\left\lVert\mathbf{Z}^{\prime\prime}-\mathbf{I}_{d}^{\top}\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}+\left\lVert\overline{\mathbf{I}}_{m-d}^{\top}\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{=}}\sum_{i=k+1}^{m}\sigma_{i}^{2}\left((\mathbf{U}\mathbf{I}_{d})^{\top}\mathbf{Y}\right)+\left\lVert(\mathbf{U}\overline{\mathbf{I}}_{m-d})^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2},$ (14)

where
$\mathbf{Z}^{\prime\prime}:=\boldsymbol{\Sigma}\mathbf{Z}^{\prime}=\boldsymbol{\Sigma}\mathbf{V}^{\top}\mathbf{Z}$.
Note that the term
$\left\lVert(\mathbf{U}\overline{\mathbf{I}}_{m-d})^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}$ is the irreducible error, and $\rm(i)$ is, once again, a consequence
of the fact that
$\left\lVert\mathbf{Z}^{\prime}-\mathbf{I}_{d}^{\top}\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}$ is minimized by taking the best rank-$k$ approximation of
$\mathbf{I}_{d}^{\top}\mathbf{U}^{\top}\mathbf{Y}$. Moreover, since the SVD of
$\mathbf{I}_{d}^{\top}\mathbf{U}^{\top}\mathbf{Y}$ is
$\grave{\mathbf{U}}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}$,

$\displaystyle\mathbf{Z}^{\prime\prime}_{*}:=\mathop{\rm arg\hskip
2.84526ptmin}_{{\rm rank}(\mathbf{Z}^{\prime\prime})\leq
k}\left\lVert\mathbf{Z}^{\prime\prime}-\mathbf{I}_{d}^{\top}\mathbf{U}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}=\left(\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\mathbf{V}^{\top}\right),$
and
$\displaystyle\mathbf{Z}_{*}=\mathbf{V}\boldsymbol{\Sigma}^{-1}\mathbf{Z}^{\prime\prime}_{*}=\left(\mathbf{V}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\right)\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\mathbf{V}^{\top}\right).$
(15)

∎

Remark: It is not necessary for $\mathbf{X}$ to be full rank. An equivalent
result can be derived with $\boldsymbol{\Sigma}^{-1}$ replaced by
$\boldsymbol{\Sigma}^{\dagger}$.

Computational complexity of rank-constrained regression: Arriving at the
globally optimal solution in lemma B.1 requires computing two SVDs, namely
$\mathbf{X}\in\mathbb{R}^{m\times d}$, which entails a complexity of
$\mathrm{O}(\mathcolor{darkblue}{dm^{2}})$, and
$\mathbf{U}^{\top}\mathbf{Y}\in\mathbb{R}^{m\times n}$, with a complexity of
$\mathrm{O}(\mathcolor{darkblue}{nm^{2}})$. Hence, the total computational
complexity is $\mathrm{O}(\mathcolor{darkblue}{m^{2}(n+d)})$.

##  Appendix C Derivations for Calibration-Aware Low-Precision and Low-Rank
Decomposition: caldera

###  C.1 Update Equations for Low-Rank Factors in LPLRFactorize submodule

As discussed in §3, the left and right low-rank factors in the LPLRFactorize
sub-module (Alg. 2) are found by solving least squares minimization problem.
The closed form expressions can be obtained by solving the normal equations
directly. In what follows, the same expressions are also derived explicitly
via the singular value decomposition, as it gives an expression for the error
(for example, refer to (C.1)) – which consists of an additive and irreducible
error term.

Updating $\mathbf{L}$ with fixed $\mathbf{R}$: For a fixed
$\mathbf{R}\in\mathbb{R}^{k\times d}$, the left low rank factor is computed in
lines $5$ and $9$ of Alg. 2 by solving

$\min_{\mathbf{Z}\in\mathbb{R}^{k\times
n}}\left\lVert\mathbf{X}\mathbf{R}^{\top}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm
F}^{2},\;\text{where}\;\mathbf{Y}:=\mathbf{X}\mathbf{A}^{\top}\in\mathbb{R}^{m\times
n}.$ (16)

Let $\mathbf{X}\mathbf{R}^{\top}=\mathbf{U}_{\rm
XR}\widetilde{\boldsymbol{\Sigma}}_{\rm XR}\mathbf{V}_{\rm XR}^{\top}$ be the
full SVD of $\mathbf{X}\mathbf{R}^{\top}$, where $\mathbf{U}_{\rm
XR}\in\mathbb{R}^{m\times m}$, $\widetilde{\boldsymbol{\Sigma}}_{\rm
XR}\in\mathbb{R}^{m\times k}$, and $\mathbf{V}_{\rm XR}\in\mathbb{R}^{k\times
k}$. Recall from App. B that $\mathbf{I}$ denotes the submatrix formed by the
first $m$ columns of the identity matrix $\mathbf{I}_{m}$, and
$\overline{\mathbf{I}}_{m}$ is the submatrix formed by the last $m$ columns.
Denoting $\boldsymbol{\Sigma}_{\rm
XR}:=\mathbf{I}_{k}^{\top}\widetilde{\boldsymbol{\Sigma}}_{\rm XR}$ and
$\mathbf{Z}^{\prime}:=\mathbf{V}_{\rm XR}^{\top}\mathbf{Z}$, since
$\overline{\mathbf{I}}_{m-k}^{\top}\widetilde{\boldsymbol{\Sigma}}_{\rm
XR}=\mathbf{0}$, it can be seen that

$\displaystyle\min_{\mathbf{Z}\in\mathbb{R}^{k\times
n}}\left\lVert\mathbf{U}_{\rm XR}\widetilde{\boldsymbol{\Sigma}}_{\rm
XR}\mathbf{V}_{\rm XR}^{\top}\mathbf{Z}-\mathbf{Y}\right\rVert_{\rm F}^{2}$
$\displaystyle=\min_{\mathbf{X}\in\mathbb{R}^{k\times
n}}\left\lVert\widetilde{\boldsymbol{\Sigma}}_{\rm XR}\mathbf{V}_{\rm
XR}^{\top}\mathbf{Z}-\mathbf{U}_{\rm XR}^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}$ $\displaystyle=\left\lVert(\mathbf{U}_{\rm
XR}\overline{\mathbf{I}}_{m-k})^{\top}\mathbf{Y}\right\rVert_{\rm
F}^{2}+\min_{\mathbf{Z}^{\prime}\in\mathbb{R}^{k\times
n}}\left\lVert\boldsymbol{\Sigma}_{\rm XR}\mathbf{Z}^{\prime}-(\mathbf{U}_{\rm
XR}\mathbf{I}_{k})^{\top}\mathbf{Y}\right\rVert_{\rm F}^{2}.$ (17)

The last term of (C.1) is minimized by setting
$\mathbf{Z}^{\prime}\leftarrow\mathbf{Z}^{\prime}_{*}:=\boldsymbol{\Sigma}_{\rm
XR}^{-1}(\mathbf{U}_{\rm XR}\mathbf{I}_{k})^{\top}\mathbf{Y}$. Since
$\mathbf{Z}_{*}^{\prime}=\mathbf{V}_{\rm
XR}^{\top}\mathbf{Z}_{*}=\mathbf{V}_{\rm XR}^{\top}\grave{\mathbf{L}}^{\top}$,
this yields the left low rank factor to be

$\grave{\mathbf{L}}^{\top}=\mathbf{V}_{\rm XR}\boldsymbol{\Sigma}_{\rm
XR}^{-1}(\mathbf{U}_{\rm
XR}\mathbf{I}_{k})^{\top}\mathbf{X}\mathbf{A}^{\top}\implies\grave{\mathbf{L}}=(\mathbf{A}\mathbf{X}^{\top})(\mathbf{R}\mathbf{X}^{\top})^{\dagger}\stackrel{{\scriptstyle\rm(i)}}{{=}}\mathbf{A}\mathbf{H}\mathbf{R}^{\top}(\mathbf{R}\mathbf{H}\mathbf{R}^{\top})^{-1},$
(18)

where $\rm(i)$ follows from the explicit expression for the pseudoinverse of
the wide matrix $\mathbf{R}\mathbf{X}^{\top}\in\mathbb{R}^{k\times d}$.

Updating $\mathbf{R}$ with fixed $\mathbf{L}$: For a fixed
$\mathbf{L}\in\mathbb{R}^{n\times k}$, the right low-rank factor is computed
in lines $4$ and $8$ of Alg. 2 by solving

$\min_{\mathbf{Z}\in\mathbb{R}^{d\times
k}}\lVert\mathbf{X}\mathbf{Z}\mathbf{L}^{\top}-\mathbf{Y}\rVert_{\rm
F}^{2},\;\text{where}\;\mathbf{Y}:=\mathbf{X}\mathbf{A}^{\top}\in\mathbb{R}^{m\times
n}.$ (19)

Let $\mathbf{X}=\mathbf{U}_{\rm X}\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\mathbf{V}_{\rm X}^{\top}$ be the full SVD of
$\mathbf{X}\in\mathbb{R}^{m\times d}$, where $\mathbf{U}_{\rm
X}\in\mathbb{R}^{m\times m}$, $\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\in\mathbb{R}^{m\times d}$, and $\mathbf{V}_{\rm X}\in\mathbb{R}^{d\times
d}$. Then, denoting $\mathbf{Z}^{\prime}:=\mathbf{Z}\mathbf{L}^{\top}$, the
minimization (19) is equivalent to

$\displaystyle\min_{\mathbf{Z}^{\prime}\in\mathbb{R}^{d\times
n}}\lVert\widetilde{\boldsymbol{\Sigma}}_{\rm X}\mathbf{V}_{\rm
X}^{\top}\mathbf{Z}^{\prime}-\mathbf{U}_{\rm X}^{\top}\mathbf{Y}\rVert_{\rm
F}^{2}\equiv\min_{\mathbf{Z}^{\prime\prime}\in\mathbb{R}^{d\times
n}}\lVert\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\mathbf{Z}^{\prime\prime}-\mathbf{U}_{\rm X}^{\top}\mathbf{Y}\rVert_{\rm
F}^{2},\;\text{where}\;\mathbf{Z}^{\prime\prime}:=\mathbf{V}_{\rm
X}^{\top}\mathbf{Z}^{\prime}.$ (20)

Note that (20) is an undetermined linear system with multiple solutions. In
particular, since $\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\in\mathbb{R}^{m\times d}$, the last $(d-m)$ columns of
$\widetilde{\boldsymbol{\Sigma}}_{\rm X}$ consist of zeros, i.e.,
$\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\overline{\mathbf{I}}_{d-m}=\mathbf{0}$. Therefore, a solution of this
system is given by

$\displaystyle\mathbf{Z}_{*}^{\prime\prime}=\grave{\boldsymbol{\Sigma}}^{\dagger}\mathbf{U}_{\rm
X}^{\top}\mathbf{Y}\quad\text{or,}\quad\mathbf{V}_{\rm
X}^{\top}\mathbf{Z}_{*}^{\prime}=\widetilde{\boldsymbol{\Sigma}}_{\rm
X}^{\dagger}\mathbf{U}_{\rm X}^{\top}\mathbf{Y}$
$\displaystyle\quad\text{or,}\quad\mathbf{Z}_{*}^{\prime}=\mathbf{V}_{\rm
X}\widetilde{\boldsymbol{\Sigma}}_{\rm X}^{\dagger}\mathbf{U}_{\rm
X}^{\top}\mathbf{Y}$
$\displaystyle\quad\text{or,}\quad\mathbf{Z}_{*}=\mathbf{V}_{\rm
X}\widetilde{\boldsymbol{\Sigma}}_{\rm X}^{\dagger}\mathbf{U}_{\rm
X}^{\top}\mathbf{Y}(\mathbf{L}^{\top})^{\dagger}.$ (21)

This implies
$\grave{\mathbf{R}}=\mathbf{L}^{\dagger}\mathbf{A}\mathbf{X}^{\top}\mathbf{U}_{\rm
X}(\widetilde{\boldsymbol{\Sigma}}_{\rm X}^{\dagger})^{\top}\mathbf{V}_{\rm
X}$.

The proof is completed by noting that $\mathbf{X}^{\top}\mathbf{U}_{\rm
X}(\widetilde{\boldsymbol{\Sigma}}_{\rm X}^{\dagger})^{\top}\mathbf{V}_{\rm
X}=\mathbf{H}\mathbf{H}^{\dagger}$, because,

$\displaystyle\mathbf{H}\mathbf{H}^{\dagger}=\mathbf{X}^{\top}\mathbf{X}\left(\mathbf{X}^{\top}\mathbf{X}\right)^{\dagger}$
$\displaystyle=\mathbf{X}^{\top}\mathbf{U}_{\rm
X}\widetilde{\boldsymbol{\Sigma}}_{\rm X}\mathbf{V}_{\rm
X}^{\top}\left(\mathbf{V}_{\rm X}\widetilde{\boldsymbol{\Sigma}}_{\rm
X}^{\top}\mathbf{U}_{\rm X}^{\top}\mathbf{U}_{\rm
X}\widetilde{\boldsymbol{\Sigma}}_{\rm X}\mathbf{V}_{\rm
X}^{\top}\right)^{\dagger}$ $\displaystyle=\mathbf{X}^{\top}\mathbf{U}_{\rm
X}\widetilde{\boldsymbol{\Sigma}}_{\rm X}\mathbf{V}_{\rm
X}^{\top}\left(\mathbf{V}_{\rm X}\widetilde{\boldsymbol{\Sigma}}_{\rm
X}^{\top}\widetilde{\boldsymbol{\Sigma}}_{\rm X}\mathbf{V}_{\rm
X}^{\top}\right)^{\dagger}$ $\displaystyle=\mathbf{X}^{\top}\mathbf{U}_{\rm
X}\widetilde{\boldsymbol{\Sigma}}_{\rm X}\mathbf{V}_{\rm
X}^{\top}\mathbf{V}_{\rm X}\left(\widetilde{\boldsymbol{\Sigma}}_{\rm
X}^{\top}\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\right)^{\dagger}\mathbf{V}_{\rm X}^{\top}$
$\displaystyle=\mathbf{X}^{\top}\mathbf{U}_{\rm
X}\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\left(\widetilde{\boldsymbol{\Sigma}}_{\rm
X}^{\top}\widetilde{\boldsymbol{\Sigma}}_{\rm
X}\right)^{\dagger}\mathbf{V}_{\rm X}^{\top}=\mathbf{U}_{\rm
X}\left(\widetilde{\boldsymbol{\Sigma}}_{\rm
X}^{\dagger}\right)^{\top}\mathbf{V}_{\rm X}^{\top}.$ (22)

###  C.2 Dynamic Ranges of Quantizers

Lemmas C.1 and C.2, stated in this section provide sufficient conditions to
ensure that the quantizers $\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$, used
to quantize the left and right low-rank factors in the LPLRFactorize
submodule, remain unsaturated.

######  Lemma C.1.

(Dynamic range of right quantizer) Given matrices
$\mathbf{A}\in\mathbb{R}^{n\times d}$ and $\mathbf{X}\in\mathbb{R}^{m\times
d}$, let $\sigma_{\rm max}$ denote the maximum singular value of
$\mathbf{X}\mathbf{A}^{\top}$. Then, the quantizer $\mathrm{Q}_{\rm R}$
remains unsaturated if the dynamic range is chosen to be $\mathrm{R}_{\rm
R}=\sigma_{\rm max}$.

###### Proof.

Note that the input to the right quantizer $\mathrm{Q}_{\rm R}$, i.e.,
$\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}$ satisfies
$\lVert\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\rVert_{\rm
max}\leq\lVert\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\rVert_{2}=\lVert\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\rVert_{2}=\lVert\grave{\boldsymbol{\Sigma}}\rVert_{2}=\lVert\mathbf{U}^{\top}\mathbf{X}\mathbf{A}^{\top}\rVert_{2}=\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{2}$.
This completes the proof. ∎

Since the input to $\mathrm{Q}_{\rm L}$ is dependent on the output of
$\mathrm{Q}_{\rm R}$, the following lemma C.2 provides an upper bound on the
input to $\mathrm{Q}_{\rm L}$, provided that $\mathrm{Q}_{\rm R}$ was
unsaturated.

######  Lemma C.2.

(Dynamic range of left quantizer) Given matrices
$\mathbf{A}\in\mathbb{R}^{n\times d}$ and $\mathbf{X}\in\mathbb{R}^{m\times
n}$, let $\lambda_{\rm min}$ denote the smallest eigenvalue of
$\mathbf{H}=\frac{1}{m}\mathbf{X}^{\top}\mathbf{X}$, and let $\sigma_{\rm
max}$ and $\sigma_{k}$ denote the largest and the $k^{\rm th}$ singular values
of $\mathbf{X}\mathbf{A}^{\top}$, respectively. For some small $\epsilon>0$
and an absolute constant $C$, suppose the number of bits for the right
quantizer $\mathrm{Q}_{\rm R}$ satisfies

$\mathrm{B}_{\rm R}\geq\log_{2}\left(\frac{4C\sigma_{\rm max}}{\sigma_{k}\log
2}\left(\sqrt{d}+\sqrt{k}+\sqrt{\log\left(\frac{8\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{\rm
F}^{2}}{\epsilon}\right)}\right)\right).$ (23)

Then, if the dynamic range of $\mathrm{Q}_{\rm L}$ is chosen to be

$\mathrm{R}_{\rm L}=\frac{2\sigma_{\rm max}}{\sigma_{k}\sqrt{m\lambda_{\rm
min}}},$ (24)

then $\mathrm{Q}_{\rm L}$ remains unsaturated with probability exceeding
$1-0.25\;\epsilon\left\lVert\mathbf{X}\mathbf{A}^{\top}\right\rVert_{\rm
F}^{-2}$.

###### Proof.

In Line $5$ of Alg. 2, the input to $\mathrm{Q}_{\rm L}$ is
$\grave{\mathbf{L}}_{0}=\left(\mathbf{W}\mathbf{X}^{\top}\right)\left(\mathbf{R}_{0}\mathbf{X}^{\top}\right)^{\dagger}$.
In the rest of the proof, the subscript $0$ in $\grave{\mathbf{L}}_{0}$ and
$\grave{\mathbf{R}}_{0}$ is dropped for brevity. Recall the notation for the
full SVD of $\mathbf{X}\mathbf{R}^{\top}$, i.e.,
$\mathbf{X}\mathbf{R}^{\top}=\mathbf{U}_{\rm
XR}\widetilde{\boldsymbol{\Sigma}}_{\rm XR}\mathbf{V}_{\rm XR}$, where
$\mathbf{U}_{\rm XR}\in\mathbb{R}^{m\times m}$,
$\widetilde{\boldsymbol{\Sigma}}_{\rm XR}\in\mathbb{R}^{m\times k}$, and
$\mathbf{V}_{\rm XR}\in\mathbb{R}^{k\times k}$. From Eq. (18),
$\grave{\mathbf{L}}$ can be expressed as $\grave{\mathbf{L}}=\mathbf{V}_{\rm
XR}\boldsymbol{\Sigma}_{\rm XR}^{\dagger}(\mathbf{U}_{\rm
XR}\mathbf{I}_{k})^{\top}\mathbf{X}\mathbf{A}^{\top}$. Consequently,
$\lVert\grave{\mathbf{L}}\rVert_{\rm max}$ is upper bounded as

$\displaystyle\lVert\grave{\mathbf{L}}\rVert_{\rm
max}\leq\lVert\grave{\mathbf{L}}\rVert_{2}\stackrel{{\scriptstyle\rm(i)}}{{=}}\left\lVert\boldsymbol{\Sigma}_{\rm
XR}^{\dagger}\left(\mathbf{U}_{\rm
XR}\mathbf{I}_{k}\right)^{\top}\mathbf{X}\mathbf{A}^{\top}\right\rVert_{2}$
$\displaystyle\stackrel{{\scriptstyle\rm(ii)}}{{\leq}}\left\lVert\boldsymbol{\Sigma}_{\rm
XR}^{\dagger}\right\rVert_{2}\left\lVert\left(\mathbf{U}_{\rm
XR}\mathbf{I}_{k}\right)^{\top}\mathbf{X}\mathbf{A}^{\top}\right\rVert_{2}$
$\displaystyle\stackrel{{\scriptstyle\rm(iii)}}{{\leq}}\left\lVert\boldsymbol{\Sigma}_{\rm
XR}^{\dagger}\right\rVert_{2}\left\lVert\mathbf{X}\mathbf{A}^{\top}\right\rVert_{2}.$
(25)

Here, $\rm(i)$ holds because $\mathbf{V}_{\rm XR}$ is a unitary matrix,
$\rm(ii)$ follows from submultiplicativity of spectral norm, and $\rm(iii)$
follows from the fact that $\left(\mathbf{U}_{\rm
XR}\mathbf{I}_{k}\right)\left(\mathbf{U}_{\rm
XR}\mathbf{I}_{k}\right)^{\top}\preccurlyeq\mathbf{I}$ and lemma G.4.
Furthermore,

$\displaystyle\left\lVert\boldsymbol{\Sigma}_{\rm
XR}^{\dagger}\right\rVert_{2}=\sigma^{-1}_{\rm min}(\boldsymbol{\Sigma}_{\rm
XR})$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}\left(\left(m\lambda_{\rm
min}\right)^{1/2}\sigma_{\rm min}(\mathbf{R})\right)^{-1}$
$\displaystyle\stackrel{{\scriptstyle\rm(ii)}}{{\leq}}(m\lambda_{\rm
min})^{-1/2}\left(\sigma_{\rm
min}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\left\lVert\mathbf{E}_{\rm
R}\right\rVert_{2}\right)^{-1},$ (26)

where $\sigma_{\rm min}(\boldsymbol{\Sigma}_{\rm XR})$ is the smallest non-
zero singular value of $\mathbf{X}\mathbf{R}^{\top}$, $\rm(i)$ follows from
lemma G.4 and $\rm(ii)$ follows from lemma G.5. Here, $\mathbf{E}_{\rm
R}\in\mathbb{R}^{k\times d}$ is the quantization error from quantizing right
low-rank factor, and consist of unbiased random variables with bounded
variance, as described in lemma G.6. Since $\grave{\boldsymbol{\Sigma}}$
contains the singular values of
$\mathbf{U}^{\top}\mathbf{X}\mathbf{A}^{\top}$,

$\displaystyle\sigma_{\rm
min}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)\stackrel{{\scriptstyle\rm(i)}}{{=}}\sigma_{\rm
min}(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}})=\sigma_{k}(\grave{\boldsymbol{\Sigma}})=\sigma_{k}\left(\mathbf{U}^{\top}\mathbf{X}\mathbf{A}^{\top}\right)\stackrel{{\scriptstyle\rm(ii)}}{{=}}\sigma_{k}\left(\mathbf{X}\mathbf{A}^{\top}\right)$
(27)

where $\rm(i)$ and $\rm(ii)$ follow because $\grave{\mathbf{V}}$ and
$\mathbf{U}$ are unitary matrices. Substituting (27) in (C.2) and (C.2) in
(C.2),

$\displaystyle\lVert\grave{\mathbf{L}}\rVert_{\rm
max}\leq\left\lVert\boldsymbol{\Sigma}_{\rm
XR}^{\dagger}\right\rVert_{2}\left\lVert\mathbf{X}\mathbf{A}^{\top}\right\rVert_{2}\leq(m\lambda_{\rm
min})^{-1/2}\left(\sigma_{k}\left(\mathbf{X}\mathbf{A}^{\top}\right)-\left\lVert\mathbf{E}_{\rm
R}\right\rVert_{2}\right)^{-1}\left\lVert\mathbf{X}\mathbf{A}^{\top}\right\rVert_{2}$
(28)

Lemma C.1 suggests choosing the dynamic range of $\mathrm{Q}_{\rm R}$ to be
$\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{2}$ to ensure that $\mathrm{Q}_{\rm
R}$ remains unsaturated. As a result,

$\left\lVert\mathbf{E}_{\rm R}\right\rVert_{\rm max}\leq\Delta_{\rm
R}:=\frac{2\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{2}}{2^{\mathrm{B}_{\rm
R}}-1}\implies\left\lVert\mathbf{E}_{\rm
R}\right\rVert_{\psi_{2}}\leq\frac{2\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{2}}{\left(2^{\mathrm{B}_{\rm
R}}-1\right)\log 2},$ (29)

where $\left\lVert\cdot\right\rVert_{\psi_{2}}$ denotes the subgaussian norm
(refer to lemma G.2). Subsequently, lemma G.2 yields that for some absolute
constant $C$,

$\left\lVert\mathbf{E}_{\rm
R}\right\rVert_{2}\leq\frac{2C\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{2}}{\left(2^{\mathrm{B}_{\rm
R}}-1\right)\log 2}\left(\sqrt{d}+\sqrt{k}+t\right)\quad\text{with probability
exceeding }1-2e^{-t^{2}}.$ (30)

Setting $t=\sqrt{\log\left(\frac{8\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{\rm
F}^{2}}{\epsilon}\right)}$ yields

$\left\lVert\mathbf{E}_{\rm
R}\right\rVert_{2}\leq\frac{2C\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{2}}{\left(2^{\mathrm{B}_{\rm
R}}-1\right)\log
2}\left(\sqrt{d}+\sqrt{k}+\sqrt{\log\left(\frac{8\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{\rm
F}^{2}}{\epsilon}\right)}\right),$ (31)

with probability exceeding
$1-\frac{\epsilon}{4\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{\rm F}^{2}}$.
Note that if the bit budget $\mathrm{B}_{\rm R}$ is chosen to satisfy

$\mathrm{B}_{\rm R}\geq\log_{2}\left(\frac{4C\sigma_{1}}{\sigma_{k}\log
2}\left(\sqrt{d}+\sqrt{k}+\sqrt{\log\left(\frac{8\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{\rm
F}^{2}}{\epsilon}\right)}\right)\right),$ (32)

then $\lVert\mathbf{E}_{\rm R}\rVert_{2}\leq\sigma_{k}/2$. Consequently, from
(28),

$\displaystyle\lVert\grave{\mathbf{L}}\rVert_{\rm
max}\leq\frac{2\sigma_{1}}{\sigma_{k}\sqrt{m\lambda_{\rm min}}}.$ (33)

This completes the proof. ∎

###  C.3 Proof of Lemma C.3: Approximation Error Upper Bound for LPLRFactorize

######  Lemma C.3.

(Approximation error of LPLRFactorize) Given $\mathbf{A}\in\mathbb{R}^{n\times
d}$ and $\mathbf{X}\in\mathbb{R}^{m\times d}$ with $m\leq d$, let
$\lambda_{\rm max}$ and $\lambda_{\rm min}$ denote the maximum and minimum
eigenvalues of $\mathbf{H}=\frac{1}{m}\mathbf{X}^{\top}\mathbf{X}$, and let
$\sigma_{1}\geq\ldots\geq\sigma_{k}$ denote the singular values of
$\mathbf{X}\mathbf{A}^{\top}$. Suppose the target rank $k$ satisfies

$\frac{\lambda_{\rm min}^{1/2}}{4m\sigma_{1}\lambda_{\rm
max}^{3/2}}\sum_{i>k}\sigma_{i}^{2}\leq k\leq m,$

the dynamic ranges of quantizers $\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$
are respectively set as

$\quad\mathrm{R}_{\rm L}=\frac{2\sigma_{1}}{\sigma_{k}\sqrt{m\lambda_{\rm
min}}}\quad\text{and }\quad\mathrm{R}_{\rm R}=\sigma_{1},$

and for some absolute constant $C$ and arbitrarily small $\epsilon$ that
satisfies $0<\epsilon\leq 4mk\lambda^{2}_{\rm max}\;\lambda_{\rm
min}^{-1}\;\sigma_{1}$, suppose the bit-budgets of $\mathrm{Q}_{\rm L}$ and
$\mathrm{Q}_{\rm R}$ satisfy

$\displaystyle\mathrm{B}_{\rm
L}\geq\log_{2}\left(4\frac{\sigma_{1}^{2}}{\sigma_{k}}\sqrt{\frac{nk}{\epsilon}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}}+1\right),$ and $\displaystyle\mathrm{B}_{\rm
R}\geq\max\\{\mathrm{B}_{1},\mathrm{B}_{2}\\},\quad\text{where
}\mathrm{B}_{1}:=\log_{2}\left(2\sigma_{1}\sqrt{\frac{kd}{\epsilon}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}}+1\right),$ and
$\displaystyle\mathrm{B}_{2}:=\log_{2}\left(\frac{4C\sigma_{1}}{\sigma_{k}\log
2}\left(\sqrt{d}+\sqrt{k}+\sqrt{\log\left(\frac{8\sum_{i}\sigma_{i}^{2}}{\epsilon}\right)}\right)\right).$

Then, the factors $\mathbf{L},\mathbf{R}$ returned by Alg. 1 satisfy
$\mathbb{E}\left\lVert(\mathbf{L}\mathbf{R}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\leq\sum_{i>k}\sigma_{i}^{2}+\epsilon$, where the expectation is over
the stochasticity of quantizers $\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$.

###### Proof.

Firstly, note that upper bounding the error
$\mathbb{E}\lVert(\mathbf{A}-\mathbf{L}_{0}\mathbf{R}_{0})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}$ suffices, since the lines $7$ to $13$ in Alg. 1 refine the estimates
of $\mathbf{L}$ and $\mathbf{R}$ and can only yield a smaller Frobenius norm
error. Consider the quantized low rank factorization
$\mathbf{A}\approx\mathrm{Q}_{\rm
L}\left(\grave{\mathbf{L}}_{0}\right)\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)$.
Let

$\displaystyle\mathbf{E}_{\rm L}:=\mathrm{Q}_{\rm
L}\left(\grave{\mathbf{L}}_{0}\right)-\grave{\mathbf{L}}_{0},\quad\text{and}\quad\mathbf{E}_{\rm
R}:=\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}$
(34)

denote the quantization error matrices. Furthermore, let

$\xi_{*}\triangleq\min_{{\rm rank}(\mathbf{Z})\leq
k}\lVert(\mathbf{A}-\mathbf{Z})\mathbf{X}^{\top}\rVert_{\rm F}^{2}$ (35)

denote the optimal value of the unquantized rank-constrained regression
problem. Since the dynamic ranges of quantizers $\mathrm{Q}_{\rm R}$ and
$\mathrm{Q}_{\rm L}$ are chosen according to lemmas C.1 and C.2 respectively,
the entries of $\mathbf{E}_{\rm L}$ and $\mathbf{E}_{\rm R}$ are unbiased
random variables with bounded variance as in lemma G.6. Let $\Delta_{\rm
R}:=2\mathrm{R}_{\rm R}/(2^{\mathrm{B}_{\rm R}}-1)$, and $\Delta_{\rm
L}:=2\mathrm{R}_{\rm L}/(2^{\mathrm{B}_{\rm L}}-1)$ denote the quantization
resolutions. Conditioned on the event that the left quantizer $\mathrm{Q}_{\rm
L}$ is unsaturated, the error matrix satisfies $\mathbb{E}\mathbf{E}_{\rm
L}=\mathbf{0}$. This yields,

$\displaystyle\mathbb{E}\left\lVert\left(\mathrm{Q}_{\rm
L}\left(\grave{\mathbf{L}}_{0}\right)\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$
$\displaystyle=\mathbb{E}\left\lVert\left(\left(\grave{\mathbf{L}}_{0}+\mathbf{E}_{\rm
L}\right)\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{=}}\underbrace{\mathbb{E}\left\lVert\left(\grave{\mathbf{L}}_{0}\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}}_{\rm T_{1}}+\underbrace{\mathbb{E}\left\lVert\mathbf{E}_{\rm
L}\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}}_{\rm T_{2}},$ (36)

where (i) follows from the fact that the error matrix is unbiased.

Since $\grave{\mathbf{L}}_{0}=\mathop{\rm arg\hskip
2.84526ptmin}_{\mathbf{Z}\in\mathbb{R}^{k\times
d}}\left\lVert(\mathbf{Z}\mathbf{R}_{0}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$, term $\rm T_{1}$ can be upper bounded as

$\displaystyle\mathbb{E}\left\lVert\left(\grave{\mathbf{L}}_{0}\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}\mathbb{E}\left\lVert\left(\mathbf{V}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$
$\displaystyle=\mathbb{E}\left\lVert\left(\mathbf{V}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}+\mathbf{E}_{\rm
R}\right)-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm F}^{2}$
$\displaystyle=\underbrace{\left\lVert\left(\mathbf{V}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}}_{=\xi_{*}}+\mathbb{E}\left\lVert\mathbf{V}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\mathbf{E}_{\rm
R}\mathbf{X}^{\top}\right\rVert_{\rm F}^{2},$ (37)

where inequality $\rm(i)$ is obtained by replacing the minimizer
$\grave{\mathbf{L}}_{0}$ with a different, but appropriately chosen matrix.
Here, $\boldsymbol{\Sigma}$ is the diagonal matrix containing the non-zero
singular values of $\mathbf{X}$.

Since $\kappa^{2}:=\lambda_{\rm max}/\lambda_{\rm min}$, the second term in
(C.3) is

$\displaystyle\mathbb{E}\left\lVert\mathbf{V}\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\mathbf{E}_{\rm
R}\mathbf{X}^{\top}\right\rVert_{\rm F}^{2}$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{=}}\mathbb{E}\left\lVert\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\mathbf{E}_{\rm
R}\mathbf{X}^{\top}\right\rVert_{\rm F}^{2}$
$\displaystyle=\mathbb{E}\left[\textrm{Tr}\left(\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\mathbf{E}_{\rm
R}\mathbf{X}^{\top}\mathbf{X}\mathbf{E}_{\rm
R}^{\top}\mathbf{I}_{k}^{\top}\grave{\mathbf{U}}^{\top}\boldsymbol{\Sigma}^{-1}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle\rm(ii)}}{{\leq}}m\lambda_{\rm
max}\;\mathbb{E}\left[\textrm{Tr}\left(\boldsymbol{\Sigma}^{-1}\grave{\mathbf{U}}\mathbf{I}_{k}\mathbf{E}_{\rm
R}\mathbf{E}_{\rm
R}^{\top}\mathbf{I}_{k}^{\top}\grave{\mathbf{U}}^{\top}\boldsymbol{\Sigma}^{-1}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle\rm(iii)}}{{=}}m\lambda_{\rm
max}\;\mathbb{E}\left[\textrm{Tr}\left(\boldsymbol{\Sigma}^{-2}\grave{\mathbf{U}}\mathbf{I}_{k}\mathbf{E}_{\rm
R}\mathbf{E}_{\rm
R}^{\top}\mathbf{I}_{k}^{\top}\grave{\mathbf{U}}^{\top}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle\rm(iv)}}{{\leq}}\kappa^{2}\;\mathbb{E}\left[\textrm{Tr}\left(\mathbf{I}_{k}\mathbf{E}_{\rm
R}\mathbf{E}_{\rm R}^{\top}\mathbf{I}_{k}^{\top}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle\rm(v)}}{{=}}\kappa^{2}\;\mathbb{E}\left[\textrm{Tr}\left(\mathbf{E}_{\rm
R}\mathbf{E}_{\rm
R}^{\top}\right)\right]=\kappa^{2}\;\mathbb{E}\left\lVert\mathbf{E}_{\rm
R}\right\rVert_{\rm F}^{2}\leq kd\;\frac{\Delta_{\rm R}^{2}}{4}\;\kappa^{2}.$
(38)

Here, $\rm(i)$ follows since $\mathbf{V}$ is a unitary matrix, $\rm(ii)$
follows from lemma G.4, $\rm(iii)$ follows from the cyclic property of trace,
$\rm(iv)$ follows as $\grave{\mathbf{U}}$ is unitary, and $\rm(v)$ follows
since $\mathbf{I}_{k}^{\top}\mathbf{I}_{k}=\mathbf{I}$ as $k\leq m$.

Moreover, since $\mathbb{E}\mathbf{E}_{\rm R}=\mathbf{0}$, term $\rm T_{2}$
can be upper bounded as

$\displaystyle\mathbb{E}\left\lVert\mathbf{E}_{\rm L}\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$ $\displaystyle=\mathbb{E}\left\lVert\mathbf{E}_{\rm
L}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}+\mathbf{E}_{\rm
R}\right)\mathbf{X}^{\top}\right\rVert_{\rm F}^{2}$
$\displaystyle=\mathbb{E}\left\lVert\mathbf{E}_{\rm
L}\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}+\mathbb{E}\left\lVert\mathbf{E}_{\rm L}\mathbf{E}_{\rm
R}\mathbf{X}^{\top}\right\rVert_{\rm F}^{2}$ (39)

The first term in (C.3) is

$\displaystyle\mathbb{E}\left\lVert\mathbf{E}_{\rm
L}\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$ $\displaystyle=\textrm{Tr}\left(\mathbf{E}_{\rm
L}\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\mathbf{X}^{\top}\mathbf{X}\grave{\mathbf{V}}\grave{\boldsymbol{\Sigma}}^{\top}\mathbf{I}_{k}\mathbf{E}_{\rm
L}^{\top}\right)$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}m\lambda_{\rm
max}\;\textrm{Tr}\left(\mathbf{E}_{\rm
L}\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\boldsymbol{\Sigma}}^{\top}\mathbf{I}_{k}\mathbf{E}_{\rm
L}^{\top}\right)$
$\displaystyle\stackrel{{\scriptstyle\rm(ii)}}{{\leq}}m\lambda_{\rm
max}\;\sigma_{1}^{2}\;\textrm{Tr}\left(\mathbf{E}_{\rm L}\mathbf{E}_{\rm
L}^{\top}\right)\leq nk\;\frac{\Delta_{\rm L}^{2}}{4}\;m\lambda_{\rm
max}\;\sigma_{1}^{2},$ (40)

where $\rm(i)$ and $\rm(ii)$ follow from lemma G.4 and the fact that
$\grave{\mathbf{V}}$ is a unitary matrix. Similarly, the second term of (C.3)
is

$\displaystyle\mathbb{E}\left\lVert\mathbf{E}_{\rm L}\mathbf{E}_{\rm
R}\mathbf{X}^{\top}\right\rVert_{\rm F}^{2}$
$\displaystyle=\mathbb{E}\left[\textrm{Tr}\left(\mathbf{E}_{\rm
L}\mathbf{E}_{\rm R}\mathbf{X}^{\top}\mathbf{X}\mathbf{E}_{\rm
R}^{\top}\mathbf{E}_{\rm L}^{\top}\right)\right]$ $\displaystyle\leq
m\lambda_{\rm max}\;\mathbb{E}\left[\textrm{Tr}\left(\mathbf{E}_{\rm
R}\mathbf{E}_{\rm R}^{\top}\mathbf{E}_{\rm L}^{\top}\mathbf{E}_{\rm
L}\right)\right]$ $\displaystyle=m\lambda_{\rm
max}\;\mathbb{E}\left[\sum_{i=1}^{k}\left(\mathbf{E}_{\rm R}\mathbf{E}_{\rm
R}^{\top}\right)_{ii}\left(\mathbb{E}\left[\mathbf{E}_{\rm L}\mathbf{E}_{\rm
L}^{\top}\right]\right)_{ii}\right]$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}m\lambda_{\rm
max}\;\frac{n\Delta_{\rm
L}^{2}}{4}\;\mathbb{E}\left[\sum_{i=1}^{k}\left(\mathbf{E}_{\rm
R}\mathbf{E}_{\rm R}^{\top}\right)_{ii}\right]$ $\displaystyle=m\lambda_{\rm
max}\;\frac{n\Delta_{\rm L}^{2}}{4}\;\mathbb{E}\left\lVert\mathbf{E}_{\rm
R}\right\rVert_{\rm F}^{2}\leq k\;\frac{n\Delta_{\rm
L}^{2}}{4}\;\frac{d\Delta_{\rm R}^{2}}{4}\;m\lambda_{\rm max}.$ (41)

Here, $\rm(i)$ follows because $\mathbb{E}\left[\mathbf{E}_{\rm
L}^{\top}\mathbf{E}_{\rm L}\right]$ is a diagonal matrix since

$\displaystyle\left(\mathbb{E}\left[\mathbf{E}_{\rm L}^{\top}\mathbf{E}_{\rm
L}\right]\right)_{ij}=\sum_{l=1}^{n}\mathbb{E}\left[E_{li}E_{lj}\right]=\begin{cases}n\;\textrm{Var}\left(E_{li}^{2}\right)\leq\frac{n\Delta_{\rm
L}^{2}}{4}\quad\text{for }i=j,\\\
\sum_{l=1}^{n}\mathbb{E}\left[E_{li}\right]\;\mathbb{E}\left[E_{lj}\right]=0\quad\text{for
}i\neq j.\end{cases}$ (42)

As a consequence of (C.3) to (C.3),

$\displaystyle\mathbb{E}\left\lVert\left(\mathrm{Q}_{\rm
L}\left(\grave{\mathbf{L}}_{0}\right)\mathrm{Q}_{\rm
R}\left(\mathbf{I}_{k}^{\top}\grave{\boldsymbol{\Sigma}}\grave{\mathbf{V}}^{\top}\right)-\mathbf{A}\right)\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$ $\displaystyle\hskip 28.45274pt\leq\xi_{*}+kd\;\frac{\Delta_{\rm
R}^{2}}{4}\kappa^{2}+nk\;\frac{\Delta_{\rm L}^{2}}{4}\;m\lambda_{\rm
max}\;\sigma_{1}^{2}+k\;\frac{n\Delta_{\rm L}^{2}}{4}\;\frac{d\Delta_{\rm
R}^{2}}{4}\;m\lambda_{\rm max}.$ (43)

Since $\mathrm{R}_{\rm R}=\sigma_{1}$, the second term of (C.3) does not
exceed $0.25\epsilon$ if

$\mathrm{B}_{\rm
R}\geq\log_{2}\left(2\sigma_{1}\kappa\sqrt{\frac{kd}{\epsilon}}+1\right).$
(44)

This needs to be considered in conjunction with the lower bound on
$\mathrm{B}_{\rm R}$ in lemma C.1, which yields the maximum of two quantities
in the theorem statement. Since $\mathrm{R}_{\rm
L}=\frac{2\sigma_{1}}{\sigma_{k}\sqrt{m\lambda_{\rm min}}}$, the third term of
(C.3) does not exceed $0.25\epsilon$ if

$\mathrm{B}_{\rm
L}\geq\log_{2}\left(4\frac{\sigma_{1}^{2}}{\sigma_{k}}\sqrt{\frac{nk}{\epsilon}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}}+1\right),$ (45)

provided $\mathrm{Q}_{\rm L}$ stays unsaturated. Furthermore, if $\epsilon\leq
4km\lambda^{2}_{\rm max}\;\lambda_{\rm min}^{-1}\;\sigma_{1}$, choosing
$\mathrm{B}_{\rm R}$ and $\mathrm{B}_{\rm L}$ as above ensures that the third
term of (C.3) is also upper bounded by $0.25\epsilon$.

The approximation error upper bound in (C.3) holds conditioned on the event
that $\mathrm{Q}_{\rm L}$ was unsaturated, which according to lemma C.2, is
ensured with probability exceeding
$1-0.25\epsilon\left\lVert\mathbf{X}\mathbf{A}^{\top}\right\rVert_{\rm
F}^{-2}$. For analysis purposes, it is assumed that when $\mathrm{Q}_{\rm L}$
gets saturated, Alg. 1 returns $\mathbf{L}=\mathbf{0}$ and
$\mathbf{R}=\mathbf{0}$, as a result of which, the approximation error is
upper bounded by $\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{\rm F}^{2}$.444In
practice, it can be easily checked if $\mathrm{Q}_{\rm L}$ was saturated, and
if so, Alg. 1 is repeated with a fresh realization of the stochastic quantizer
$\mathrm{Q}_{\rm R}$. Since lemma C.2 guarantees that the saturation
probability is low, it implies that ”few” realizations suffice. Then, since
$\Pr\left(\mathrm{Q}_{\rm L}\text{ is unsat.}\right)\geq
1-0.25\;\epsilon\;\lVert\mathbf{X}\mathbf{A}^{\top}\rVert_{\rm F}^{2}$, using
Cauchy-Schwarz inequality for expectations,

$\displaystyle\mathbb{E}\left\lVert(\mathbf{L}\mathbf{R}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$
$\displaystyle=\mathbb{E}\left[\left\lVert(\mathbf{L}\mathbf{R}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\;\Big{|}\;\mathrm{Q}_{\rm L}\text{ is
unsat.}\right]+\mathbb{E}\left[\left\lVert(\mathbf{0}-\mathbf{A})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\;\Big{|}\;\mathrm{Q}_{\rm L}\text{ is sat.}\right]$
$\displaystyle\leq\xi_{*}+\frac{3\epsilon}{4}+\Pr\left(\mathrm{Q}_{\rm
L}\text{ is sat.}\right)\sum_{i}\sigma_{i}^{2}\;\;\leq\;\;\xi_{*}+\epsilon.$
(46)

This completes the proof. ∎

###  C.4 Proof of Thm. 4.1: Approximation Error Upper Bound for caldera

######  Theorem C.4.

Approximation error of caldera (Formal) Given
$\mathbf{W}\in\mathbb{R}^{n\times d}$ and $\mathbf{X}\in\mathbb{R}^{m\times
d}$ with $m\leq d$, let $\mathbf{D}$ be obtained from the LDL decomposition
$\mathbf{X}^{\top}\mathbf{X}=m\mathbf{H}=(\mathbf{M}+\mathbf{I})\mathbf{D}(\mathbf{M}+\mathbf{I})^{\top}$,
and $\lambda_{\rm max}$, $\lambda_{\rm min}$ denote the max and min
eigenvalues of $\mathbf{H}$. Additionally, let
$\mathbf{Q}\triangleq{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{\sc
LDLQ}}(\mathbf{W},\mathrm{Q}_{\rm Q})$, where $\mathrm{Q}_{\rm Q}$ has dynamic
range $\mathrm{R}$ and bit-budget $\mathrm{B}_{\rm Q}$, the quantization error
be $\boldsymbol{\eta}\triangleq\mathrm{Q}_{\rm
Q}(\mathbf{Q}+(\mathbf{W}-\mathbf{Q})\mathbf{M})-(\mathbf{Q}+(\mathbf{W}-\mathbf{Q})\mathbf{M})$,
and $\sigma_{1}\geq\ldots\geq\sigma_{k}\ldots$ be the singular values of
$\mathbf{X}(\mathbf{W}-\mathbf{Q})^{\top}$. If the target rank $k$ satisfies

$\frac{\lambda_{\rm min}^{1/2}}{4m\sigma_{1}\lambda_{\rm
max}^{3/2}}\sum_{i>k}\sigma_{i}^{2}\leq k\leq m,$

the dynamic ranges of $\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$ are set as

$\mathrm{R}_{\rm L}=\frac{2\sigma_{1}}{\sigma_{k}\sqrt{m\lambda_{\rm
min}}}\quad\text{and, }\quad\mathrm{R}_{\rm R}=\sigma_{1},$

and for some absolute constant $C$ and arbitrarily small $\epsilon$ that
satisfies $0<\epsilon\leq 4mk\lambda^{2}_{\rm max}\;\lambda_{\rm
min}^{-1}\;\sigma_{1}$, suppose the bit-budgets of $\mathrm{Q}_{\rm L}$ and
$\mathrm{Q}_{\rm R}$ are set so that they satisfy

$\displaystyle\mathrm{B}_{\rm
L}\geq\log_{2}\left(4\frac{\sigma_{1}^{2}}{\sigma_{k}}\sqrt{\frac{nk}{\epsilon}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}}+1\right),$ and $\displaystyle\mathrm{B}_{\rm
R}\geq\max\\{\mathrm{B}_{1},\mathrm{B}_{2}\\},\quad\text{where
}\mathrm{B}_{1}:=\log_{2}\left(2\sigma_{1}\sqrt{\frac{kd}{\epsilon}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}}+1\right),$ and
$\displaystyle\mathrm{B}_{2}:=\log_{2}\left(\frac{4C\sigma_{1}}{\sigma_{k}\log
2}\left(\sqrt{d}+\sqrt{k}+\sqrt{\log\left(\frac{8\sum_{i}\sigma_{i}^{2}}{\epsilon}\right)}\right)\right),$

then $\mathbf{Q}$, $\mathbf{L}$ and $\mathbf{R}$ returned by caldera (Alg. 1)
satisfy

$\mathbb{E}\left\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}\leq
m\sum_{i>k}\mathbb{E}\lambda_{i}(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top})+\epsilon\lesssim\frac{4md\lambda_{\rm
max}\mathrm{R}^{2}}{\pi(2^{\mathrm{B}_{\rm
Q}}-1)^{2}}\left(1-\frac{k}{n}\right)\left(n-\frac{k}{2}\right)+\epsilon,$

where the expectation is over the stochasticity of the quantizers
$\mathrm{Q}_{\rm Q}$, $\mathrm{Q}_{\rm L}$ and $\mathrm{Q}_{\rm R}$.

###### Proof.

As in §C.3, an upper bound is obtained on
$\mathbb{E}\left\lVert(\mathbf{Q}_{0}+\mathbf{L}_{0}\mathbf{R}_{0}-\mathbf{W})\mathbf{X}^{\top}\right\rVert_{\rm
F}^{2}$, since after the first iteration, the alternating steps $3$ and $4$ in
Alg. 2 simply refine the estimates of $\mathbf{Q}$, $\mathbf{L}$ and
$\mathbf{R}$, and can only yield a smaller error. For convenience of notation,
in what follows, the subscript $0$ is omitted.

Since $\mathbf{L},\mathbf{R}$ is obtained after applying LPLRFactorize
submodule to $(\mathbf{W}-\mathbf{Q})$, lemma C.3 suggests that if
$\mathrm{R}_{\rm L}$, $\mathrm{R}_{\rm R}$, $\mathrm{B}_{\rm L}$, and
$\mathrm{B}_{\rm R}$ are chosen appropriately,

$\mathbb{E}\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}=\mathbb{E}\lVert(\mathbf{L}\mathbf{R}-(\mathbf{W}-\mathbf{Q}))\mathbf{X}^{\top}\rVert_{\rm
F}^{2}\leq\sum_{i>k}\mathbb{E}\sigma_{i}^{2}\left((\mathbf{Q}-\mathbf{W})\mathbf{X}^{\top}\right)+\epsilon,$
(47)

where the expectation in the upper bound on the right hand side is over the
randomness in $\mathbf{Q}$ due to the stochasticity in quantizer
$\mathrm{Q}_{\rm Q}$. Since
$\mathbf{Q}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{\sc
LDLQ}}(\mathbf{W},\mathrm{Q}_{\rm Q})$ is the LDLQ quantizer of Chee et al.
[3] (or, BlockLDLQ quantizer of Tseng et al. [35], which is a successor of
LDLQ proposed by Chee et al. [3]), it is shown that

$\mathbf{Q}=\mathrm{Q}_{\rm Q}(\mathbf{Q}+(\mathbf{W}-\mathbf{Q})\mathbf{M}),$

where $\mathbf{M}$ is a strictly upper triangular matrix. This is a
consequence of the fact that LDLQ quantizes one column at a time, while
simultaneously incorporating a linear feedback from the already quantized
columns. Moreover, if $\boldsymbol{\eta}=\mathrm{Q}_{\rm
Q}(\mathbf{W}+(\mathbf{W}-\mathbf{Q})\mathbf{M})-(\mathbf{W}+(\mathbf{W}-\mathbf{Q})\mathbf{M})$
denotes the quantization error, then it can be seen that

$\mathbf{Q}-\mathbf{W}=\boldsymbol{\eta}(\mathbf{M}+\mathbf{I})^{-1}$ (48)

Moreover, since
$m\mathbf{H}=\mathbf{X}^{\top}\mathbf{X}=(\mathbf{M}+\mathbf{I})\mathbf{D}(\mathbf{M}+\mathbf{I})^{\top}$,

$\displaystyle\mathbb{E}\sigma_{i}^{2}\left((\mathbf{Q}-\mathbf{W})\mathbf{X}^{\top}\right)$
$\displaystyle=\mathbb{E}\lambda_{i}\left((\mathbf{Q}-\mathbf{W})\mathbf{H}(\mathbf{Q}-\mathbf{W})^{\top}\right)$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{=}}\mathbb{E}\lambda_{i}\left(\boldsymbol{\eta}(\mathbf{M}+\mathbf{I})^{-1}(\mathbf{M}+\mathbf{I})\mathbf{D}(\mathbf{M}+\mathbf{I})^{\top}(\mathbf{M}+\mathbf{I})^{-\top}\boldsymbol{\eta}^{\top}\right)$
$\displaystyle=\mathbb{E}\lambda_{i}(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top}),$
(49)

where $\rm(i)$ follows from (48). From (47),

$\displaystyle\mathbb{E}\lVert(\mathbf{Q}+\mathbf{L}\mathbf{R}-\mathbf{W})\mathbf{X}^{\top}\rVert_{\rm
F}^{2}\leq\sum_{i>k}\mathbb{E}\lambda_{i}(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top})+\epsilon.$
(50)

Since
$\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top}=\sum_{j=1}^{d}D_{jj}\boldsymbol{\eta}_{j}\boldsymbol{\eta}_{j}^{\top}$,
where $D_{jj}$ denotes the $j^{\rm th}$ diagonal entry of $\mathbf{D}$ and
$\eta_{j}$ is the $j^{\rm th}$ column of
$\boldsymbol{\eta}\in\mathbb{R}^{n\times d}$,

$\lambda_{i}\left(\boldsymbol{\eta}\mathbf{D}\boldsymbol{\eta}^{\top}\right)=\lambda_{i}\left(\sum_{j=1}^{d}D_{jj}\boldsymbol{\eta}_{j}\boldsymbol{\eta}_{j}^{\top}\right)\leq
d\;\left({\rm
max}_{j}D_{jj}\right)\;\lambda_{i}\left(\frac{1}{d}\sum_{j=1}^{d}\boldsymbol{\eta}_{j}\boldsymbol{\eta}_{j}^{\top}\right).$
(51)

Note that $\boldsymbol{\eta}$ consists of quantization errors, which, for
uniformly dithered scalar quantization, are zero mean random variables with
bounded variance upper bounded by
$\frac{\Delta^{2}}{4}=\frac{\mathrm{R}^{2}}{(2^{\mathrm{B}_{\rm Q}}-1)^{2}}$.
As the exact error distribution for non-subtractively dithered quantization
(which is commonly used in practice), is not fully understood, a
simplification is made for easier analysis, assuming the quantizer is
subtractively dithered. For subtractively dithered quantizers, if Schuchman’s
conditions are met [31, 11], this results in a uniform error distribution in
the interval $\left[-\frac{\Delta}{2},\frac{\Delta}{2}\right]$. Therefore,
assuming quantization errors are independent and identically distributed, for
large dimensions $d$, the eigenvalues of
$\frac{1}{d}\sum_{j=1}^{d}\boldsymbol{\eta}_{j}\boldsymbol{\eta}_{j}^{\top}$
are distributed according to the Marchenko-Pastur distribution, given by ${\rm
f}_{\rm mp}(x):=\frac{2d}{\pi
n\Delta^{2}x}\sqrt{\left(\lambda_{+}-x\right)\left(x-\lambda_{-}\right)}$,
where
$\lambda_{\pm}:=\frac{\Delta^{2}}{4}\left(1\pm\sqrt{\frac{n}{d}}\right)^{2}$.
Furthermore, denoting $q:=\mathrm{F}_{\rm mp}^{-1}\left(1-\frac{k}{n}\right)$,
where $\mathrm{F}_{mp}^{-1}$ is the inverse cumulative distribution function
(CDF) of ${\rm f}_{\rm mp}(x)$, it can be seen that

$\displaystyle\sum_{i>k}\mathbb{E}\lambda_{i}\left(\frac{1}{d}\sum_{j}\boldsymbol{\eta}_{j}\boldsymbol{\eta}_{j}^{\top}\right)$
$\displaystyle\approx(n-k)\int_{\lambda_{-}}^{q}\frac{x}{2\pi(n/d)(\Delta^{2}/4)}\frac{\sqrt{\left(\lambda_{+}-x\right)\left(x-\lambda_{-}\right)}}{x}dx$
$\displaystyle\stackrel{{\scriptstyle\rm(i)}}{{\leq}}\frac{\sqrt{nd}}{\pi}\left(1-\frac{k}{n}\right)\left(\mathrm{F}_{\rm
mp}^{-1}\left(1-\frac{k}{n}\right)-\lambda_{-}\right)$
$\displaystyle\stackrel{{\scriptstyle\rm(ii)}}{{\leq}}\frac{\Delta^{2}}{\pi}\left(1-\frac{k}{n}\right)\left(n-\frac{k}{2}\right).$
(52)

Here, $\approx$ denotes that the equaility holds asymptotically, $\rm(i)$
follows from upper bounding the integral using the fact that
$\left(\lambda_{+}-x\right)\left(x-\lambda_{-}\right)$ is maximized at
$x=\frac{\lambda_{+}+\lambda_{-}}{2}$. Furthermore, $\rm(ii)$ follows after
substituting the values of $\lambda_{\pm}$ and using the following linear
upper bound on the inverse CDF of Marchenko-Pastur distribution,

$\mathrm{F}_{\rm
mp}^{-1}(x)\leq\lambda_{+}-\left(\frac{\lambda_{+}-\lambda_{-}}{2}\right)(1-x).$
(53)

It can be verified by inspection that $\mathrm{F}_{\rm mp}(x)$ is lower
bounded by
$\left(\frac{\lambda_{+}-\lambda_{-}}{2}\right)x-\left(\frac{\lambda_{+}^{2}-\lambda_{-}^{2}}{4}\right)$,
and inequality (53) is a consequence of this fact. Furthermore, from lemma
G.3, ${\rm max}_{j}D_{jj}\leq\lambda_{\rm max}$. Substituting (C.4) in (51),
and substituting $\Delta^{2}=\frac{4\mathrm{R}^{2}}{(2^{\mathrm{B}_{\rm
Q}}-1)^{2}}$, completes the proof. ∎

Informal version of Thm. C.4: Consider $n\approx d$. From Thm. C.4, a
(simplified) asymptotic dependence on the bit-budgets $\mathrm{B}_{\rm L}$ and
$\mathrm{B}_{\rm R}$ can be obtained. In what follows, constant factors inside
the $\log_{2}\left(\cdot\right)$ have been ignored. Comparing the expressions
for $\mathrm{B}_{1}$ and $\mathrm{B}_{2}$, it can be seen that the desired
bit-budgets are

$\mathrm{B}_{\rm
L}\geq\log_{2}\left(4\frac{\sigma_{1}^{2}}{\sigma_{k}}\sqrt{\frac{nk}{\epsilon}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}}\right)\quad\text{and, }\quad\mathrm{B}_{\rm
R}\geq\log_{2}\left(2\sigma_{2}\sqrt{\frac{kd}{\epsilon}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}}\right).$

For $n\approx d$, this yields an average bit-budget of

$\frac{1}{2}\left(\mathrm{B}_{\rm L}+\mathrm{B}_{\rm
R}\right)=\frac{1}{2}\log_{2}\left(\frac{8k}{\epsilon}\frac{\sigma_{1}^{3}}{\sigma_{k}}\frac{\lambda_{\rm
max}}{\lambda_{\rm min}}\sqrt{nd}\right)\;\text{bits per parameter.}$

##  Appendix D Computational Complexity of caldera

Complexity of pre-preprocessing: For a given calibration dataset/activation
$\mathbf{X}\in\mathbb{R}^{m\times d}$, the Hessian is computed as
$\mathbf{H}=\frac{1}{m}\mathbf{X}^{\top}\mathbf{X}$, which requires
$\mathrm{O}(\mathcolor{darkblue}{md^{2}})$ compute. Subsequently, the LDL
decomposition of $\mathbf{H}$ is computed, which entails
$\mathrm{O}(\mathcolor{darkblue}{d^{3}})$ complexity [20]. Moreover,
$\mathbf{H}\mathbf{H}^{\dagger}$, which is used in the update equation of
$\grave{\mathbf{R}}$ is also computed beforehand, with a complexity of
$\mathrm{O}(\mathcolor{darkblue}{d^{3}})$. therefore, the total complexity of
pre-processing is $\mathrm{O}(\mathcolor{darkblue}{md^{2}+2d^{3}})$.

Complexity of LDLQ: Each iteration of caldera invokes a single call to LDLQ.
An LDLQ call involves updating each column of an $n\times d$ iteratively. From
(2), updating the $k^{\rm th}$ column requires multiplying a matrix (of
already quantized columns) in $\mathbb{R}^{n\times(k-1)}$ with a vector in
$\mathbb{R}^{k-1}$, implying a complexity of
$\mathrm{O}(\mathcolor{darkblue}{n(k-1)})$. Subsequently, if $\mathrm{Q}_{\rm
Q}$ is uniform scalar quantization, quantizing the (feedback incorporated)
$k^{\rm th}$ column entails $\mathrm{O}(\mathcolor{darkblue}{n})$ compute,
implying a total of $\mathrm{O}(nk)$ compute for the $k^{\rm th}$ column.
Hence, quantizing all columns from $k=1,\ldots,n$ would require
$\mathrm{O}\left(n\sum_{k=1}^{n}k\right)=\mathrm{O}\left(\frac{n^{2}}{2}+\frac{3n}{2}\right)=\mathrm{O}(\mathcolor{darkblue}{n^{2}})$
compute.

Complexity of LPLRFactorize: Every iteration of caldera invokes a call to
LPLRFactorize, which itself consists of $\rm T_{in}$ inner iterations. Each
inner iteration of LPLRFactorize, consists of initializing the left and right
low rank factors using rank-constrained regression. As seen in §B, it has a
computational complexity of
$\mathrm{O}\left(\mathcolor{darkblue}{m^{2}(n+d)}\right)$. Subsequently, for
any matrix $\mathbf{A}$, the left low rank factor as
$\grave{\mathbf{L}}=\mathbf{A}\mathbf{H}\mathbf{R}^{\top}(\mathbf{R}\mathbf{H}\mathbf{R}^{\top})^{-1}$
can be found using successive matrix multiplications. While a gradient descent
based algorithm can possibly speed up this computation, in implementation,
closed form expressions are computed directly as they are computationally
affordable for the hidden dimensions of the LLMs considered. Computing
$\mathbf{A}\left(\mathbf{H}\mathbf{R}^{\top}\right)$ requires
$\mathrm{O}\left(\mathcolor{darkblue}{dk(n+d)}\right)$, computing
$(\mathbf{R}\mathbf{H}\mathbf{R}^{\top})^{-1}$ entails
$\mathrm{O}\left(\mathcolor{darkblue}{dk(k+d)+k^{3}}\right)$, and multiplying
them together requires $\mathrm{O}\left(\mathcolor{darkblue}{nk^{2}}\right)$.
Keeping the dominant term, the aggregated computational complexity for
computing the left low-rank factor in each inner iteration is
$\mathrm{O}\left(\mathcolor{darkblue}{ndk}\right)$.

Additionally, the left low-rank factor can be computed as
$\grave{\mathbf{R}}=\mathbf{L}^{\dagger}\mathbf{A}(\mathbf{H}\mathbf{H}^{\dagger})$,
where computing $\mathbf{L}^{\dagger}\mathbf{A}$ is
$\mathrm{O}\left(\mathcolor{darkblue}{ndk}\right)$. Since
$\mathbf{H}\mathbf{H}^{\dagger}$ is already computed beforehand, multiplying
$\mathbf{L}^{\dagger}\mathbf{A}$ and $\mathbf{H}\mathbf{H}^{\dagger}$ entails
$\mathrm{O}\left(\mathcolor{darkblue}{kd^{2}}\right)$. Once again, keeping the
dominant term, the complexity is
$\mathrm{O}\left(\mathcolor{darkblue}{ndk}\right)$. Hence, the total
complexity of each inner iteration of LPLRFactorize is
$\mathrm{O}\left(\mathcolor{darkblue}{ndk}\right)$.

Remark: Compared to the two-stage LPLR algorithm proposed in [30], the left
and right low-rank factors are iteratively refined in Alg. 2 since this
additional compute can be afforded for quantizing LLM weight matrices.
Moreover, SVD computations can be sped up with randomized SVD [14].

##  Appendix E Additional Experimental Details

###  E.1 System Details

The code for this paper is available at https://github.com/pilancilab/caldera.
The framework is built in PyTorch on top of the QuIP# [35] and LoftQ [22]
repositories, and utilizes HuggingFace implementations of all datasets and
LLMs. Experiments were performed on either NVIDIA RTX A6000, NVIDIA A10G, or
NVIDIA H100 GPUs. Hessian computation for all but LLaMa-2 70B was performed on
four NVIDIA A10 GPUs (provisioned as Amazon AWS EC2 instances), parallelized
by distributing different layers to different GPUs. Hessian computation for
LLaMa-2 70B was performed on a single H100 GPU. Model quantization was
performed on four NVIDIA RTX A6000 GPUs, parallelized in the same manner as
Hessian computation All zero-shot and fine-tuning experiments were also run on
A6000 GPUs, except for LLaMa-2 70B zero-shot experiments, which were run on an
H100 GPU. Low-rank adaptation experiments were parallelized across four GPUs
via HuggingFace Accelerate [12], with DeepSpeed ZeRO Level 2 [28, 29]. The use
of Llama family of LLMs for research is guided by a community license that can
be founded at https://llama.meta.com/license/ and
https://llama.meta.com/llama3/license/.

###  E.2 Parameters of caldera Quantization

For all caldera decompositions, the number of alternating iterations between
updating $\mathbf{Q}$ and $\mathbf{L}$, $\mathbf{R}$ (i.e., $\rm T_{out}$ in
Alg. 1) is $15$. For decompositions with quantized low-rank factors, the
number of LPLR iterations (i.e., $\rm T_{in}$ in Alg. 2) is $10$.

For both caldera and QuIP# decompositions, the calibration dataset consists of
$256$ random samples from the RedPajama dataset. The number of tokens in each
calibration data point is equal to the context length of the corresponding
model, i.e., $4096$ for LLaMa-2 7B and $8192$ for LLaMa-3 8B. Note that this
calibration dataset is significantly smaller than the $6144$ datapoints used
in [35].

An additional heuristic applied during the caldera decomposition is an update
to the Hessian matrix based on the subspace spanned by $\mathbf{L}\mathbf{R}$:

$\widetilde{\mathbf{H}}\triangleq\mathbf{H}-\mathbf{M}\mathbf{V}\mathbf{V}^{\top}\mathbf{M}^{\top},$
(54)

Where $\mathbf{H}=\mathbf{M}\mathbf{M}^{\top}$ is the LDL decomposition of the
Hessian and
$\mathbf{L}\mathbf{R}\mathbf{M}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^{\top}$
is the singular value decomposition of the product
$\mathbf{L}\mathbf{R}\mathbf{M}$. The updated $\widetilde{\mathbf{H}}$ is used
in all LPLR updates, and the original Hessian is used for updating the low-
rank factors via Alg. 2. This heuristic was found in the QuIP# codebase, and
empirically speeds up convergence of caldera, as is discussed in App. F.1.
Additionally, the SVD steps while quantizing 70B models was replaced by
randomized SVD [14] for computational speedup.

###  E.3 Details about Goodness-of-Fit Metrics

In addition to perplexity on the WikiText2 and C4 datasets, caldera was
evaluated using zero-shot accuracy on the following sequence classification
tasks:

  1. 1.

Winogrande [19]: a collection of 44k problems problems inspired by the
Winograd Schema Challenge [21], specifically designed to be robust to learned
biases in model training datasets. Specifically, Winogrande is a two-choice
fill-in-the-blank task that requires significant commonsense reasoning.

  2. 2.

RTE [1]: Recognizing Text Entailment is a task in the General Language
Understanding Evaluation (GLUE) benchmark [39]. Given two statements, the
model must classify whether or not the second follows from the first.

  3. 3.

PiQA [2]: Physical Interaction: Question Answering is a question-answering
task that requires understanding about physical relationships between objects.

  4. 4.

ArcE [4]: In general, the AI2 Reasoning Challenge is a set of multiple-choice
questions that require a grade-school level of knowledge. ArcE is the subset
that is labeled Easy.

  5. 5.

ArcC [4]: The ARC-Challenge problems are in the same format as ARC-Easy, but
the dataset only includes problems that were answered incorrectly by selected
algorithms.

The unquantized ($16$-bit) numbers mentioned in Tabs. 1 and 2 are either
copied from [35] for the tasks available reported therein. For some ones that
could not be easily found, inference was performed directly on the $16$-bit
model downloaded from HuggingFace.

###  E.4 Fine-tuning Parameter Details

Fine-tuning of the diagonal Rademacher matrices in the RHT was performed over
a calibration dataset sampled from the training split of RedPajama. Due to
computational constraints, each sample contains $512$ tokens, rather than the
full context length of the model. The calibration dataset is $256$ samples in
total, with $192$ data points in the training split and $64$ in the evaluation