Compressing Large Language Models using Low Rank and Low Precision Decomposition

Authors: rajarshi  saha
naomi  sagan
varun  srivastava
andrea j goldsmith
mert  pilanci
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:59:04

Abstract: The prohibitive sizes of Large Language Models (LLMs) today make it difficult to deploy them on memory-constrained edge devices. This work introduces $\rm 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. $\rm 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 $\rm 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/$13$B/$70$B and LlaMa-$3$ $8$B models obtained using $\rm CALDERA$ outperforms existing post-training LLM compression techniques in the regime of less than $2.5$ bits per parameter.

Main paper: 
 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: Calibration Aware Low-Precision DEcomposition with Low-Rank Adaptation, which compresses LLMs by leveraging the approximate low rank structure inherent in these weight matrices. Given a matrix W ∈ R n×d , CALDERA approximates it as W ≈ Q + LR, where Q ∈ R n×d , L ∈ R n×k and R ∈ R k×d . Here, the left and right low rank factors, respectively L and R, are tall and wide matrices, and k is the target rank. Furthermore, the entries of Q, L and R are represented using low-precision formats with B Q , B L and B R bits per entry, respectively. 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 L and R capture the effect of the large singular components of W with high fidelity. Moreover, the backbone Q, which is quantized aggressively -for instance, using B Q = 2 bits, coarsely captures the essence of the moderately decaying and low singular components of W. CALDERA substitutes each weight matrix W in an LLM, with its approximate low-precision and low-rank decomposition Q + LR, resulting in a post-training quantization strategy that delivers state-of-the-art zero-shot performance. In addition, since usually k ≪ min{n, d}, implying that the total number of parameters in LR is much smaller compared to the number of entries in W (i.e., k(n + d) ≪ nd), CALDERA can readily fine-tune (or "adapt") the low rank factors L and R in order to boost the zero-shot results.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.Recent studies like SmoothQuant [42] , OPTQ [8] , QuIP [3] , AQLM [7] , and QuIP# [36] 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 Q + LR, 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 A ∈ R n×d can be represented by the factorization A ≈ LR, with L ∈ R n×k and R ∈ R k×d , where k ≤ 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 [44] , FWSVD [15] , LASER [33] , LQER [45] , and ZeroQuant-V2 [43] have explored the efficacy of low-rank structures in LLM weights, treating low-rank factorization and quantization independently. In contrast, LPLR [31] 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# [36] 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. 
problem formulation: 
 In a neural network layer, a weight matrix W transforms an input activation x into an output activation given by Wx. This transformation can be succinctly described using the matrix's singular value decomposition (SVD). For any matrix A ∈ R n×d , the SVD is A = i σ i u i v i , where σ i , u i , v i are the i th singular value and the corresponding left and right singular vectors, respectively. The impact of each singular component u i v i on the matrix's transformation is determined by the magnitude of σ 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, W, as a low-precision, low-rank decomposition, W ≈ Q + LR, with all components Q, L, R in low-precision format. Unlike previous works such as [13, 22, 44, 45] , which represent the low-rank factors L and R in highprecision (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 Q denote the set of discrete quantization points in R. For B-bit quantization, the cardinality of Q satisfies log 2 |Q| ≤ B. Consider a matrix W ∈ R n×d . The goal of this work is to obtain an decomposition W ≈ Q + LR by approximately solving the minimization problem minEQUATIONHere, Q Q , Q L and Q R denote the lattice codebooks used to quantize Q, L and R, using B Q , B L and B R bits, respectively. Furthermore, X ∈ R m×d is a calibration matrix that aims to preserve the Frobenius norm error of the compressed layer output activations. If W is the first layer's weight matrix, X includes input embeddings from a calibration dataset, such as a subset of RedPajama [34] , with the i th row representing the i th datapoint. For intermediate layers, 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.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: Limitations are discussed explicitly in Appendix Sec. H. Assumptions made with regard to theory are stated in the theorem statement. These assumptions hold in practice as our algorithm is seen to perform well in numerical simulations. Extensive experimentation were performed on as many setups as allowed within our computational budget. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: Broader societal impacts are discussed in App. H Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
proposed algorithm: calibration-aware low-precision decomposition with low rank adaptation: 
 This section introduces CALDERA to approximately solve (1) and get a Q + LR decomposition of a weight matrix W using the calibration matrix X. The pseudocode is provided in Alg. 1. It consists of a nested loop for alternately optimizing the variables Q, L and R. Suppose Q Q , Q L and Q R , respectively, denote quantizers used for quantizing Q, L and R. For instance, they can refer to uniformly dithered scalar quantizers, as described in App. G.2. Initially, the low-rank factors are set to 0, and 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 W usingEQUATIONwhere Q (k) , W (k) denote the k th column, W (1:k-1) denotes the first k columns, Q Q has a bit-budget B Q , and a k ∈ R k-1 is a learnable sequence of vectors. Update Eq. ( 2) incorporates linear feedback from already quantized columns, it can be seen thatQ satisfies Q = Q Q (W + (W -Q)M), where the feedback matrix M is a strictly upper triangular matrix with columns a k . Defining H ≜ 1 m X ⊤ X to be the (scaled) Hessian of the least squares objective in (1), [3] show that the optimal feedback matrix is the M obtained from the LDL decomposition of mH, given by mH = (M + I)D(M + I) ⊤ . Subsequently, Q is fixed and the Low-Precision Low-Rank (LPLR) factorization of the residual, (W -Q), is computed. This is done by the LPLRFACTORIZE submodule (Alg. 2), which is a refined version of the LPLR algorithm proposed in [31] . For a given matrix A, Alg. 2 minimizes minEQUATIONwhere Q L and Q R use B L and B R bits, respectively. In contrast to [31] , 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 L and 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 L: To update the left factor L, lines 5 and 9 of Alg. 2 solves min Z ∥(ZR -A)X ⊤ ∥ 2 F . For a fixed R, this is a least squares minimization, whose solution is available is closed form asL = AX ⊤ RX ⊤ † = AHR ⊤ (RHR ⊤ ) -1 , as derived in App. C.1.Updating R: Line 8 of Alg. 2, updates the right factor R by keeping L fixed and solving min Z ∥(LZ -A)X ⊤ ∥ 2 F . As this is an under-determined linear system, there exist multiple solutions for Z, all attaining the same objective function value. It is shown in App. C.1 that R = L † AHH † 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 L and R, which are iteratively quantized, are functions of the Hessian H = 1 m X ⊤ X. Therefore, 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 H and its LDL decomposition, along with computing HH † , requiring a total of O(md 2 + 2d 3 ) multiplications. Each outer iteration involves an LDLQ quantization. Quantizing the k th column has complexity O(nk), since feedback from k already quantized columns need to be incorporated. Hence, quantizing a matrix in R n×d entails O(n 2 + 3n) complexity. Moreover, LPLRFACTORIZE requires O(m 2 (n + d)) to initialize, and subsequently, each inner iteration entails O(ndk). Assuming n, d ≥ m ≫ k, and keeping only the dominant terms, the total complexity of CALDERA, not including the complexity of the pre-processing discussed earlier, isO T out n 2 + m 2 (n + d) + ndk T in .Fine tuning via Low-Rank Adaptation: Once the weight matrices of each layer are replaced by its Q + LR 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 L and R can be further fine-tuned using low-rank adaptation [13, 16, 22] on a small task-specific dataset. While the initialization of the fine-tuning step has quantized Q, L and R, the fine-tuned factors are represented using 16-bits (BF16 format). Although this leads to a slight increase in the memory footprint, the performance gains from fine-tuning are substantial. 
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 W is as W ≈ Q + LR by solving the optimization problem (1) using Alg. 1. For convenience of analysis, it is assumed that the dynamic range of Q Q , denoted as R, is chosen to be high enough, ensuring it remains unsaturated. Consequently, for a scalar input the quantization error from Q Q has zero mean and bounded variance, given by ∆2 4 = R 2 (2 B Q -1) 2 .Theorem 4.1. Approximation error of CALDERA (Informal) Given W ∈ R n×d and X ∈ R m×d with m ≤ d, let D be obtained from the LDL decomposition X ⊤ X = mH = (M + I)D(M + I) ⊤ , and λ max , λ min denote the max and min eigenvalues ofH. Additionally, let Q ≜ LDLQ(W, Q Q ),where Q Q has dynamic range R and bit-budget B Q , the quantization error be η≜ Q Q (Q + (W - Q)M) -(Q + (W -Q)M), and σ 1 ≥ . . . ≥ σ k . . . be the singular values of X(W -Q) ⊤ . If the target rank k satisfies 0.25λ 1/2 min (mσ 1 ) -1 λ -3/2 max i>k σ 2 i ≤ k ≤ m, and the dynamic ranges of Q L and Q R are set as R L = 2σ1 σ k √ mλmin and R R = σ 1 , then Q, L and R returned by Alg. 1 satisfy 1 nm E (Q + LR -W)X ⊤ 2 F ≤ 1 n i>k Eλ i (ηDη ⊤ ) + ϵ ≲ 4dλ max R 2 π (2 BQ -1) 2 1 - k 2n 2 + ϵ,while utilizing an average budget of 1 2 log 2 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 ≤ d is not restrictive, because when H is positive definite, (1) can be rewritten as∥(Q + LR -W)X ⊤ ∥ 2 F = ∥(Q + LR -W)H 1/2 ∥ 2F , ensuring m = d. This is detailed further in App. C.5. 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,EQUATIONEvidently, Alg. 1 yields a smaller error provided, i>k Eλ i (ηDη ⊤ ) < k i=1 Eλ i (ηDη ⊤ )ϵ, where ϵ 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 ϵ, which is dictated by the bit-budgets used for L and R, this upper Algorithm 1: CALDERA: Calibration Aware Low-Precision DEcomposition with Low-Rank Adaptation Input: Matrix: W ∈ R n×d , Target rank: k, Calibration matrix: X ∈ R m×d , Outer and inner iterations:T out , T in , Quantizers: Q Q , Q L , Q R , Flag: EnableLoRA, Fine-tune rank: r Output: LPLR decomposition: Q ∈ Q n×d Q , L ∈ Q n×k L , R ∈ Q k×d R s.t. WX ⊤ ≈ (Q + LR)X ⊤ Initialize: t ← 0, L 0 ← 0, R 0 ← 0, MinError ← ∞ while t < T out do Update Q: Q t+1 ← LDLQ(W -L t R t , Q Q ) Update low-rank factors: L t+1 , R t+1 ← LPLRFACTORIZE(W -Q t+1 , k, X, Q L , Q R , T in ) if ∥(Q t+1 + L t+1 R t+1 -W)X ⊤ ∥ 2 F < MinError then Q best ← Q t+1 , L best ← L t+1 , R best ← R t+1 , MinError ← ∥(Q t+1 + L t+1 R t+1 -W)X ⊤ ∥ 2 F end t ← t + 1 end if EnableLoRA is TRUE thenFurther Fine-tune top-r singular components of L best and R best to 16-bit precision using Low-Rank Adaptation (LoRA) (as in [13, 16, 22] ) end return Q best , L best , R bestInput: Matrix: A ∈ R n×d , Target rank: k, Calibration matrix: X ∈ R m×d , Iterations: T in , Quantizers: Q L , Q R Output: Low precision Low Rank factors: L ∈ Q n×k , R ∈ Q k×d s.t. AX ⊤ ≈ LRX ⊤ Initialize: Iteration counter: i ← 0 Compute SVD of X as U ΣV ⊤ . Compute SVD of U ⊤ XA ⊤ as Ù Σ V⊤ Get right low-rank factor: R 0 ← Q R (I ⊤ k Σ V⊤ )Get left low-rank factor:L 0 ≜ Q L ( L0 ), where L0 = arg min Z∈R k×d (ZR 0 -A)X ⊤ 2 F L best ← L 0 , R best ← R 0 , MinError ← (L 0 R 0 -A)X ⊤ 2 F . while i < T in do Update right: R i+1 ← Q R ( Ri+1 ), where Ri+1 = arg min Z∈R k×d (L i Z -A) X ⊤ 2 F Update left: L i+1 ← Q L ( Li+1 ), where Li+1 = arg min Z∈R n×k (ZR i -A) X ⊤ 2 F if (L i+1 R i+1 -A)X ⊤ 2 F < MinError then L best ← L i+1 , R best ← R i+1 , MinError ← (L i+1 R i+1 -A)X ⊤ 2 F end i ← i + 1 end return L best , R bestbound can be made arbitrarily small by ensuring that the two terms are approximately equal, i.e.,E∥(Q + LR -W)X ⊤ ∥ 2F is upper bounded by 2ϵ. This is apparent in the following regimes: (i) k ≪ n: In this regime, k is treated as a constant as n grows. Then, if the bit-budget B Q satisfiesB Q ≥ log 2 2R(πϵ) -1/2 nmd λ max + 1 , then E (Q + LR -W)X ⊤ 2 F ≤ 2ϵ.(ii) k = O(n): For a fixed B Q , if k is allowed to grow with dimension n, then choosing k to satisfyk ≥ 2n -(2 BQ -1)R -1 (πϵ) 1/2 (mdλ -1/2 max ) √ n ensures E (Q + LR -W)X ⊤ 2 F ≤ 2ϵ.This implies that the upper bound can be made arbitrarily small by either (i) increasing the bit-budget of the backbone, i.e., B Q , for a fixed rank k, or (ii) increasing the rank k for a fixed B Q , for example, B Q = 2. Alternatively stated, this provides a tunable knob for controlling the error by trading off the allocated bit-budget between the backbone Q and the low-rank factors L, R.In this section, a brief proof sketch is presented, highlighting the major challenges in the proof and how they are addressed. For analysis, Q is assumed to be updated prior to L, 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, which is defined as, minEQUATIONAlthough this problem is non-convex, it can be solved to global optimality via two SVDs [41] . The following lemma characterizes the solution to the optimization problem in (5) .Lemma 4.2. Given Y ∈ R m×n , and full rank X ∈ R m×d , where m ≤ d. Let X = U ΣV ⊤ and U ⊤ Y = Ù Σ V⊤ denote full SVDs of X and U ⊤ Y. Then, for k ≤ m, the solution of (5) is given byZ * ≜ arg min rank(Z)≤k ∥XZ -Y∥ 2 F = VI m Σ -1 ÙI k I ⊤ k Σ V⊤ ,where Σ := ΣI m ∈ R m×m is a diagonal matrix consisting of the non-zero singular values of X. Moreover, denoting the non-zero singular values of Y as {σ i (Y)} m i=1 , the optimal value of (7) isEQUATIONThe 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 A, Alg. 2 with suitably chosen B L and B R , ensures that E (LR -A)X ⊤ 2 F , 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 Q L or Q R gets saturated, a trivial output of L = 0, R = 0 is returned. Therefore, lemmas C.1 and C.2 specify choosing the dynamic ranges R R and R 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 mH as proposed in [3] , along with an application of Marchenko-Pastur approximation to bound the expected eigenvalues of the quantization error, i.e., Eλ i ηη ⊤ , yielding the final inequality. 
numerical simulations: 
 The efficacy of CALDERA is assessed by using it to compress four popular open source LLMs from Meta AI, namely, LLaMa-2 7B, LLaMa-2 13B, LLaMa-2 70B [35] and LLaMa-3 8B [26] . The framework is built in PyTorch on top of the QuIP# [36] and LoftQ [22] , and is available at https://github.com/pilancilab/caldera.Baselines. The full-rank matrix Q, also referred to as the backbone, is quantized to 2-bits using the LDLQ procedure from QuIP [3, 36] , employing an E8 lattice quantizer [39] . For CALDERA, which allows even the low-rank factors, L and 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 W ≜ H ⊤ L WH R , where H L and H R are Hadamard matrices, right-multiplied by a diagonal matrix with i.i.id. {±1} entries. In addition, the Hessian matrix obtained from the calibration data is substituted by H ≜ H ⊤ R HH 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 zeroshot accuracy for sequence classification. Specifically, zero-shot accuracy was measured on the Winogrande [19] , RTE [1, 40] , 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] .Tables 1 and 2 report the perplexities and accuracies for CALDERA with varying target rank (k) of L and R. A smaller value is better for perplexity, which is defined as the exp(•) 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 Q + LR 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, L and 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 models are also provided. For all models, the rank-256 CALDERA decomposition with 4-bit factors had the lowest perplexity and generally had the highest accuracies. 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 Table 1 : Zero-shot perplexities (denoted by ↓) and accuracies (↑) for LLaMa-2. BQ = 2 bits throughout.Rank can regain the performance that was compromised when the backbone Q was quantized to 2 bits. Since zero-shot experiments have some inherent randomness and low-rank regularization effects [33] , 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 8B, significantly deteriorates model performance across various post-training quantization techniques, more so than with the LLaMa-2 series.B L (= B R ) Avg Bits Wiki2 ↓ C4 ↓ Wino ↑ RTE ↑ PiQA ↑ ArcE ↑ ArcC ↑ CALDERA (As CALDERA presents a general optimization framework for matrix decompositions of the form Q + LR, 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# [36] , involves fine-tuning the diagonal Rademacher matrices with ±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.1 Details on specific fine-tuning hyperparameters can be found in App. E.4.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. In addition to RHT FT as described above, once the Q + LR decomposition with target rank k is obtained, and k takes values 64, 128 and 256, fine-tuning the top r (≤ k) singular components on a specific downstream datasets can recover the performance lost due to quantization. We consider three such tasks -(i) language modeling on Wikitext (Wiki2), (ii) recognizing textual entailment (RTE), and (iii) commonsense reasoning (WinoGrande). Throughout all experiments in Table 5 , r = 64 is chosen and those singular components are fine-tuned to 16-bit precision, i.e., BF16 format. The tasks (ii) and (iii) are sequence classification tasks, and the pre-trained LLaMa model is augmented with a linear classification head, which is fine-tuned along with the low-rank factors [29] . In other words, the approximation is written asW ≈ Q + L 1 R 1 + L 2 R 2 , where L 1 ∈ R n×r , L 2 ∈ R n×(k-r) , R 1 ∈ R r×d , R 2 ∈ R (k-r)×d , L = [L 1 | L 2 ], R ⊤ = [R ⊤ 1 | R ⊤ 2 ].The value of r is set to 64 and L 2 , R 2 are fined-tuned to L bf16 , R bf16 using low-rank adaptation similar to [13, 16, 22] . 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 . 2 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. 3 In each case, CALDERA achieves better performance at a lower bit budget.The low-rank (LR) component in CALDERA can recover some of the accuracy lost due to the aggressive 2-bit quantization of Q. However, CALDERA also needs to dequantize and multiply the low-rank factors, which results in a slight (albeit, acceptable) throughput degradation compared to QuIP# (shown in Table 6 ). Nevertheless, CALDERA's throughput is significantly higher than that of the unquantized model. This is because compressing weight matrices results in a smaller volume of data transfer from and to the GPU's SRAM, speeding up forward passes. It is worthwhile to note that 2 There 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., ∥(Q + LR -W)X ⊤ ∥ 2 F ) of the initialization. Rather, they show that low-rank adaptation can recover accuracy degradation from quantization.3 Some LLaMa-3 results for LoftQ are present on its GitHub repository, but none for the tasks evaluated here. Notably, the throughput is higher when the LR factors are in 16-bit compared to when they are in 4-bit. This is because CALDERA used QuIP#'s lattice dequantizers for the low-rank factors as well, adding to the compute overhead. Moreover, QuIP# also used fused kernels, and CALDERA's throughput can be improved by leveraging such optimizations. Since this work is primarily motivated with the goal of closing the gap with respect to uncompressed models in the 2 to 2.5 bits per parameter regime, throughput improvement using custom kernels, paged attention, etc., is left for future work. We discuss the broader impacts of our work along with limitations in App. H. 
conclusions: 
 In this work, the problem of obtaining a low-precision and low-rank decomposition of an LLM weight matrix was considered. A Q + LR decomposition efficiently captures the high singular components of the weight matrix with sufficient fidelity, while coarsely compressing the less significant moderateto-low singular components. An optimization-theoretically motivated algorithm was proposed to obtain this decomposition, which iteratively optimized the quantized backbone Q and the low-rank factors L, R. Additionally, it was shown that L and 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.  
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [No] Justification: No new datasets are used in this work. All datasets are already publicly open-sourced. Models compressed using CALDERA will be open-sourced. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: This paper does not involve crowd-sourcing or research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: This section begins by outlining key notations used in both linear algebra and probability theory. Boldface uppercase and lowercase letters, such as A and a, represent matrices and vectors respectively. I denotes the identity matrix, and its dimension is assumed to be imminent from the context. The first k columns of the identity matrix I as I k , and let I k be the submatrix formed by the last k columns. The singular values of A are denoted by σ max (A) = σ 1 ≥ σ 2 ≥ . . . ≥ σ r = σ min (A), where r = rank(A). Similarly, the eigenvalues are denoted as λ 1 (A), . . . , λ r (A). The max-norm of A is defined as ∥A∥ max = max i,j |A ij |, the spectral norm of A is defined as ∥A∥ 2 = sup ∥x∥=1 ∥Ax∥ = σ max (A), and the Frobenius norm is∥A∥ F = i,j A 2 ij 1/2 = Tr A ⊤ A = k∈[r] σ 2 k 1/2 .For any matrix X, its Moore-Penrose pseudo-inverse is denoted by X † . The notations ≈, ≲ and ≳ 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) ≲ B(n) iff lim n→∞ A(n) ≤ lim n→∞ B(n).Notations ≈ and ≳ are defined analogously. Wherever relevant, dimension-dependent terms are highlighted blue. W ∈ R n×d Q, L, RBackbone, left and right low rank factors Q ∈ R n×d , L ∈ R n×k ,≜ QQ(Q + (W -Q)M) - (Q + (W -Q)M) η ∈ R n×d is assumed to consist of i.i.d.entries for analytical tractability.Quantization error matrices from quantizing left and right factors EL ∈ R n×k and ER ∈ R k×d consists of zero-mean random variables with bounded variance.Recall that the submatrix formed by the first m columns of the identity matrix I is denoted as I m , and let I m be the submatrix formed by the last m columns. The dimension of I is inferred depending on context. Consider the following:EQUATIONAlthough 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 Y ∈ R m×n is given, and suppose X ∈ R m×d is full rank, i.e., rank(X) = min{m, d}, with SVD,X = U ΣV ⊤ . Furthermore, let Ù Σ V⊤ denote the full SVD of U ⊤ Y if m ≤ d, or the full SVD of (UI d ) ⊤ Y if m > d.Then, for k ≤ m, the solution of (5) is given byEQUATIONHere, Σ is a diagonal matrix of the non-zero singular values of X, defined as Σ := ΣI m ∈ R m×m when m ≤ d, andΣ := I ⊤ d Σ ∈ R d×d when d < m.Additionally, the optimal value is minEQUATIONProof. Case m ≤ d: Since the full SVD of X ∈ R m×d is X = U ΣV ⊤ , where U ∈ R m×m , Σ ∈ R m×d , and V ∈ R d×d , the last (dm) columns of Σ will be zero, i.e., ΣI m-d = 0.Let Z ′ := V ⊤ Z ∈ R d×n be the transformed optimization variable. Since V is a unitary matrix, rank(Z) ≤ k if and only if rank(Z ′ ) ≤ k. Splitting Z ′ ∈ R d×n into Z ′′ := I ⊤ m Z ′ ∈ R m×n and Z ′′ := I ⊤ d-m Z ′ ∈ R (d-m)×n , it can be seen that ΣZ ′ = ΣI d Z ′′ + ΣI m-d Z ′′ = ΣZ ′′ ,whereEQUATIONNote that the objective function value is independent of Z ′′ , as Z ′′ lies in the null space of X ⊤ , and rank(Z ′′ ) ≤ k follows from the fact that rank of a submatrix cannot exceed the full matrix. Since X is full rank, Σ is invertible, and the minimization in (10) is equivalent toEQUATIONwhere Z := ΣZ ′′ ∈ R m×n . The equality in (11) follows as a consequence of Eckart-Young-Mirsky theorem (lemma G.1), which states that ∥ Z -U ⊤ Y∥ 2 F is minimized by taking the best rank-k approximation of U ⊤ Y, and the fact that the singular values of U ⊤ Y and Y are the same as U is unitary. Moreover, as the SVD ofEQUATIONIn other words, if Z ′ * denotes the solution of the middle optimization problem in (10) ,I ⊤ m Z * = Z ′′ * . Furthermore, note that setting I ⊤ d-m Z * = 0 ensures rank(Z ′ * ) = rank(Z ′′ * )≤ k, while keeping the objective value in (10) unchanged. Hence, an optimal solution is given byEQUATION)Case m > d: Recalling that the full SVD of X ∈ R m×d is X = U ΣV ⊤ , where U ∈ R m×m , Σ ∈ R m×d , and V ∈ R d×d , in this case, the last md rows of Σ will be zero, i.e.,EQUATIONwhereZ ′′ := ΣZ ′ = ΣV ⊤ Z. Note that the term (UI m-d ) ⊤ Y 2 Fis the irreducible error, and (i) is, once again, a consequence of the fact thatZ ′ -I ⊤ d U ⊤ Y 2 F is minimized by taking the best rank-k approximation of I ⊤ d U ⊤ Y. Moreover, since the SVD of I ⊤ d U ⊤ Y is Ù Σ V⊤ , Z ′′ * := arg min rank(Z ′′ )≤k Z ′′ -I ⊤ d U ⊤ Y 2 F = ÙI k I ⊤ k ΣV ⊤ ,andEQUATION)Remark: It is not necessary for X to be full rank. An equivalent result can be derived with Σ -1 replaced by Σ † .Computational complexity of rank-constrained regression: Arriving at the globally optimal solution in lemma B.1 requires computing two SVDs, namely X ∈ R m×d , which entails a complexity of O(dm 2 ), and U ⊤ Y ∈ R m×n , with a complexity of O(nm 2 ). Hence, the total computational complexity is O(m 2 (n + d)). 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 ( 17)) -which consists of an additive and irreducible error term.Updating L with fixed R: For a fixed R ∈ R k×d , the left low rank factor is computed in lines 5 and 9 of Alg. 2 by solving minEQUATION)Let XR ⊤ = U XR Σ XR V ⊤ XR be the full SVD of XR ⊤ , where U XR ∈ R m×m , Σ XR ∈ R m×kEQUATION)The last term of ( 17) is minimized by settingZ ′ ← Z ′ * := Σ -1 XR (U XR I k ) ⊤ Y. Since Z ′ * = V ⊤ XR Z * = V ⊤L⊤ , this yields the left low rank factor to beEQUATIONwhere (i) follows from the explicit expression for the pseudoinverse of the wide matrix RX ⊤ ∈ R k×d .Proof. In Line 5 of Alg. 2, the input to Q L is L0 = WX ⊤ R 0 X ⊤ † . In the rest of the proof, the subscript 0 in L0 and R0 is dropped for brevity. Recall the notation for the full SVD of XR ⊤ , i.e., XR ⊤ = U XR Σ XR V XR , where U XR ∈ R m×m , Σ XR ∈ R m×k , and V XR ∈ R k×k . From Eq. ( 18), L can be expressed as L = V XR Σ † XR (U XR I k ) ⊤ XA ⊤ . Consequently, ∥ L∥ max is upper bounded asEQUATIONHere, (i) holds because V XR is a unitary matrix, (ii) follows from submultiplicativity of spectral norm, and (iii) follows from the fact that (U XR I k ) (U XR I k ) ⊤ ≼ I and lemma G.4. Furthermore,EQUATIONwhere σ min (Σ XR ) is the smallest non-zero singular value of XR ⊤ , (i) follows from lemma G.4 and (ii) follows from lemma G.5. Here, E R ∈ R k×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 Σ contains the singular values of U ⊤ XA ⊤ ,EQUATIONwhere (i) and (ii) follow because V and U are unitary matrices. Substituting ( 27) in ( 26) and ( 26) in (25) ,EQUATIONLemma C.1 suggests choosing the dynamic range of Q R to be ∥XA ⊤ ∥ 2 to ensure that Q R remains unsaturated. As a result,EQUATION)where ∥•∥ ψ2 denotes the subgaussian norm (refer to lemma G.2). Subsequently, lemma G.2 yields that for some absolute constant C,EQUATION)Setting t = logEQUATIONwith probability exceeding 1 -EQUATIONthen ∥E R ∥ 2 ≤ σ k /2. Consequently, from (28) ,EQUATION)This completes the proof.C. σ 2 i ≤ k ≤ m,the dynamic ranges of quantizers Q L and Q R are respectively set asR L = 2σ 1 σ k √ mλ min and R R = σ 1 ,and for some absolute constant C and arbitrarily small ϵ that satisfies 0 < ϵ ≤ 4mkλ 2 max λ -1 min σ 1 , suppose the bit-budgets of Q L and Q R satisfyB L ≥ log 2 4 σ 2 1 σ k nk ϵ λ max λ min + 1 , and B R ≥ max{B 1 , B 2 }, where B 1 := log 2 2σ 1 kd ϵ λ max λ min + 1 ,andB 2 := log 2 4Cσ 1 σ k log 2 √ d + √ k + log 8 i σ 2 i ϵ .Then, the factors L, R returned by Alg. 1 satisfy E (LR -A)X ⊤ 2 F ≤ i>k σ 2 i + ϵ, where the expectation is over the stochasticity of quantizers Q L and Q R .Proof. Firstly, note that upper bounding the error E∥(A -L 0 R 0 )X ⊤ ∥ 2 F suffices, since the lines 7 to 13 in Alg. 1 refine the estimates of L and R and can only yield a smaller Frobenius norm error.EQUATIONdenote the quantization error matrices. Furthermore, let ξ * ≜ min rank(Z)≤kEQUATION)denote the optimal value of the unquantized rank-constrained regression problem. Since the dynamic ranges of quantizers Q R and Q L are chosen according to lemmas C.1 and C.2 respectively, the entries of E L and E R are unbiased random variables with bounded variance as in lemma G.6. Let ∆ R := 2R R /(2 BR -1), and ∆ L := 2R L /(2 BL -1) denote the quantization resolutions. Conditioned on the event that the left quantizer Q L is unsaturated, the error matrix satisfies EE L = 0. This yields,EQUATIONwhere (i) follows from the fact that the error matrix is unbiased.Since L0 = arg min Z∈R k×d (ZR 0 -A)X ⊤ 2 F , term T 1 can be upper bounded asEQUATIONwhere inequality (i) is obtained by replacing the minimizer L0 with a different, but appropriately chosen matrix. Here, Σ is the diagonal matrix containing the non-zero singular values of X.Since κ 2 := λ max /λ min , the second term in ( 37) isEQUATION)Here, (i) follows since V is a unitary matrix, (ii) follows from lemma G.4, (iii) follows from the cyclic property of trace, (iv) follows as Ù is unitary, and (v) follows since I ⊤ k I k = I as k ≤ m. Moreover, since EE R = 0, term T 2 can be upper bounded asE E L Q R I ⊤ k Σ V⊤ X ⊤ 2 F = E E L I ⊤ k Σ V⊤ + E R X ⊤ 2 F = E E L I ⊤ k Σ V⊤ X ⊤ 2 F + E E L E R X ⊤ 2 F (39)The first term in (39) isEQUATIONwhere (i) and (ii) follow from lemma G.4 and the fact that V is a unitary matrix. Similarly, the second term of ( 39) isEQUATIONHere, (i)EQUATIONAs a consequence of (37) to ( 41),EQUATIONSince R R = σ 1 , the second term of (43) does not exceed 0.25ϵ ifEQUATIONThis needs to be considered in conjunction with the lower bound on B R in lemma C.1, which yields the maximum of two quantities in the theorem statement. Since R L = 2σ1 σ k √ mλmin , the third term of (43) does not exceed 0.25ϵ ifEQUATIONprovided Q L stays unsaturated. Furthermore, if ϵ ≤ 4kmλ 2 max λ -1 min σ 1 , choosing B R and B L as above ensures that the third term of ( 43) is also upper bounded by 0.25ϵ.The approximation error upper bound in (43) holds conditioned on the event that Q L was unsaturated, which according to lemma C.2, is ensured with probability exceeding 1 -0.25ϵ XA ⊤ -2 F . For analysis purposes, it is assumed that when Q L gets saturated, Alg. 1 returns L = 0 and R = 0, as a result of which, the approximation error is upper bounded by ∥XA ⊤ ∥ 2 F . 4 Then, sincePr (Q L is unsat.) ≥ 1 -0.25 ϵ ∥XA ⊤ ∥ 2F , using Cauchy-Schwarz inequality for expectations,EQUATION)This completes the proof. ≜ LDLQ(W, Q Q ),where Q Q has dynamic range R and bit-budget B Q , the quantization error be η ≜ Q Q (Q + (W - Q)M) -(Q + (W -Q)M),4mσ 1 λ 3/2 max i>k σ 2 i ≤ k ≤ m,the dynamic ranges of Q L and Q R are set asR L = 2σ 1 σ k √ mλ min and, R R = σ 1 ,and for some absolute constant C and arbitrarily small ϵ that satisfies 0 < ϵ ≤ 4mkλ 2 max λ -1 min σ 1 , suppose the bit-budgets of Q L and Q R are set so that they satisfyEQUATIONB 2 := log 2 4Cσ 1 σ k log 2 √ d + √ k + log 8 i σ 2 i ϵ ,then Q, L and R returned by CALDERA (Alg. 1) satisfyE (Q + LR -W)X ⊤ 2 F ≤ m i>k Eλ i (ηDη ⊤ ) + ϵ ≲ 4mdλ max R 2 π(2 BQ -1) 2 1 - k n n - k 2 + ϵ,where the expectation is over the stochasticity of the quantizersQ Q , Q L and Q R .Proof. As in §C.3, an upper bound is obtained onE (Q 0 + L 0 R 0 -W)X ⊤ 2F , since after the first iteration, the alternating steps 3 and 4 in Alg. 2 simply refine the estimates of Q, L and R, and can only yield a smaller error. For convenience of notation, in what follows, the subscript 0 is omitted.Since L, R is obtained after applying LPLRFACTORIZE submodule to (W-Q), lemma C.3 suggests that if R L , R R , B L , and B R are chosen appropriately,EQUATION)where the expectation in the upper bound on the right hand side is over the randomness in Q due to the stochasticity in quantizerQ Q . Since Q = LDLQ(W, Q Q )is the LDLQ quantizer of Chee et al. [3] (or, BLOCKLDLQ quantizer of Tseng et al. [36] , which is a successor of LDLQ proposed by Chee et al. [3] ), it is shown thatQ = Q Q (Q + (W -Q)M), where 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, ifEQUATIONwhere (i) follows from (48). From (47),EQUATION)Since ηDη ⊤ = d j=1 D jj η j η ⊤ j , where D jj denotes the j th diagonal entry of D and η j is the j th column of η ∈ R n×d ,EQUATIONNote that η consists of quantization errors, which, for uniformly dithered scalar quantization, are zero mean random variables with bounded variance upper bounded by∆ 2 4 = R 2 (2 B 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 [11, 32] , this results in a uniform error distribution in the interval -∆ 2 , ∆ 2 . Therefore, assuming quantization errors are independent and identically distributed, for large dimensions d, the eigenvalues of 1 d d j=1 η j η ⊤ j are distributed according to the Marchenko-Pastur distribution, given by f mp (x) := 2dEQUATION)Complexity of pre-preprocessing: For a given calibration dataset/activation X ∈ R m×d , the Hessian is computed as H = 1 m X ⊤ X, which requires O(md 2 ) compute. Subsequently, the LDL decomposition of H is computed, which entails O(d 3 ) complexity [20] . Moreover, HH † , which is used in the update equation of R is also computed beforehand, with a complexity of O(d 3 ). therefore, the total complexity of pre-processing is O(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 × d iteratively. From (2), updating the k th column requires multiplying a matrix (of already quantized columns) in R n×(k-1) with a vector in R k-1 , implying a complexity of O(n(k -1)). Subsequently, if Q Q is uniform scalar quantization, quantizing the (feedback incorporated) k th column entails O(n) compute, implying a total of O(nk) compute for the k th column. Hence, quantizing all columns from k = 1, . . . , n would require O (nn k=1 k) = O n 2 2 + 3n 2 = O(n 2 ) compute.Complexity of LPLRFACTORIZE: Every iteration of CALDERA invokes a call to LPLRFACTORIZE, which itself consists of 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 O m 2 (n + d) . Subsequently, for any matrix A, the left low rank factor as L = AHR ⊤ (RHR ⊤ ) -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 A HR ⊤ requires O (dk(n + d)), computing (RHR ⊤ ) -1 entails O dk(k + d) + k 3 , and multiplying them together requires O nk 2 . Keeping the dominant term, the aggregated computational complexity for computing the left low-rank factor in each inner iteration is O (ndk).Additionally, the left low-rank factor can be computed as R = L † A(HH † ), where computing L † A is O (ndk). Since HH † is already computed beforehand, multiplying L † A and HH † entails O kd 2 . Once again, keeping the dominant term, the complexity is O (ndk). Hence, the total complexity of each inner iteration of LPLRFACTORIZE is O (ndk).Remark: Compared to the two-stage LPLR algorithm proposed in [31] , 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] .The code for this paper is available at https://github.com/pilancilab/caldera. The framework is built in PyTorch on top of the QuIP# [36] 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, 30] . 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/.For all CALDERA decompositions, the number of alternating iterations between updating Q and L, R (i.e., T out in Alg. 1) is 15. For decompositions with quantized low-rank factors, the number of LPLR iterations (i.e., 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 [36] .An additional heuristic applied during the CALDERA decomposition is an update to the Hessian matrix based on the subspace spanned by LR:EQUATIONWhere H = MM ⊤ is the LDL decomposition of the Hessian and LRM = UΣV ⊤ is the singular value decomposition of the product LRM. The updated 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.In addition to perplexity on the WikiText2 and C4 datasets, CALDERA was evaluated using zero-shot accuracy on the following sequence classification tasks: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. RTE [1] : Recognizing Text Entailment is a task in the General Language Understanding Evaluation (GLUE) benchmark [40] . Given two statements, the model must classify whether or not the second follows from the first. 3. PiQA [2] : Physical Interaction: Question Answering is a question-answering task that requires understanding about physical relationships between objects. 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. 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 [36] 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.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 split. RHT fine-tuning was performed for 5 epochs with a learning rate of 10 -3 . The epoch with the lowest evaluation loss was used for further zero-shot and fine-tuning experiments.Parameters for low-rank adaptation experiments can be found in Table 8 . Overall, the number of epochs and therefore number of training steps, was determined empirically based on when the evaluation accuracy plateaued.For the comparison of CALDERA to LQ-LoRA in Winogrande accuracy, the LQ-LoRA result reported in [13] did not involve fine-tuning directly on the Winogrande dataset, but rather on a subset of C4 and Wikitext2. Assume that the dimensions of the seven weight matrices in each transformer layer have dimensions n i × d i , where i ∈ {1, . . . , 7}. Also, for the models we consider, each transformer layer has matrices of the same dimensions. In general, if the full-rank matrix Q has a bit budget of B Q , the factors L and R both have a bit budget of B LR , and the rank of the factors is k, the average number of bits per parameter is7 i=1 (B Q n i d i + kB LR (n i + d i )) 7 i=1 n i d i .For In §5.3, r = 64 of the k factors are fine-tuned in 16-bit precision. This results in the following number of bits per parameter:7 i=1 (B Q n i d i + (k -r)B LR (n i + d i ) + 16r(n i + d i )) 7 i=1 n i d i .For LLaMa-2 70B, the zero-shot perplexities and accuracies reported in the QuIP# paper [36] could not be replicated. As such, the QuIP# performance reported in this paper are based on recreations of those experiments.The per-iteration relative Frobenius norm error of CALDERA, for a few selected weight matrices of LLaMa-2 7B, is plotted in Figure 3 . The data-aware relative Frobenius norm error is defined as(Q + LR -W)X ⊤ F ∥WX ⊤ ∥ F ,where W is the unquantized weight matrix, X is the calibration data, and Q + LR is the CALDERA decomposition. The following ablations of CALDERA decomposition parameters are considered:1. 16-Bit Factors: Q is quantized to 2 bits via LDLQ. The low-rank factors are kept in half precision, so no LPLR iterations are required after rank-constrained regression is performed. The randomized Hadamard transform is performed on the W and H matrices are prior to quantization. 2. 4-Bit Factors: The low-rank factors are quantized to 4 bits of precision using an E8 lattice quantizer, and 10 iterations of LPLRFACTORIZE (Alg. 2) are run for each update of the factors (i.e., T in = 10 in Alg. 1). Otherwise, the decompostion parameters are the same as in 16-Bit Factors. To demonstrate the convergence of LPLRFACTORIZE (Alg. 2), the per-iteration relative data-aware error of LPLRFACTORIZE for the factorization W ≈ LR is plotted in Figure 4 . For all curves plotted, the randomized Hadamard transform is performed on W and H before the factorization is computed, and both factors are quantized to 4 bits of precision via an E8 lattice quantizer.In both cases, the alternating minimization iterations reduce the error. For the Up projection matrix, this reduction is nominal, whereas, for the Key projection matrix, the alternating iterations result in a significant improvement.Perplexity and language modeling benchmark accuracy results for quantizing Mistral 7B via CALDERA and QuIP# are in Table 9 . Results are consistent with those in Section 5.1. This section states some useful linear algebra results as lemmas. Some of them are stated without proof, which can be easily proved or found in a linear algebra textbook such as [10] .Lemma G.1. (Eckart-Young-Mirsky theorem) For any matrix A with SVD given by A = UΣV ⊤ , the solution of A k := arg min rank( A)≤k ∥A -A∥ 2 F is given by [38, Thm 4.4.5] ) Let X be a d × m random matrix whose entries X ij are independent, zero-mean, subgaussian random variables. Then, for any t > 0, ∥X∥ 2 ≤ CK √ d + √ m + t with probability exceeding 1 -2e -t 2 , where K = max i,j ∥A ij ∥ ψ2 , and ∥•∥ ψ2 denotes the subgaussian norm, and C is an absolute constant.A k = UΣ 1/2 I k I ⊤ k Σ 1/2 V ⊤ , and ∥A -A k ∥ 2 F = i>k σ 2 i (A). Lemma G.2. (VershyninRemark: Lemma G.2 states a high probability upper bound on the spectral norm of a random matrix in terms of the subgaussian norm of the entries of the matrix. The subgaussian norm of a subgaussian random variable X is defined as ∥X∥ ψ2 ≜ inf{t ≥ 0 | E[e X 2 /t 2 ] ≤ 2}. It can be shown that any bounded random variable X is subgaussian, and satisfies ∥X∥ ψ2 ≤ ∥X∥ ∞ log 2 . Lemma G.3. Suppose the LDL decomposition of a matrix H ∈ R d×d is given by H = (M + I)D(M + I) ⊤ , where M is strictly upper triangular and D is diagonal. Then, max j D jj ≤ λ max , where λ max denotes the largest eigenvalue of H.Proof. Let e j denote the j th canonical basis vector. Then, e ⊤ j He j = e ⊤ j (M + I)D(M + I) ⊤ e j (i)EQUATIONMoreover, from properties of eigenvalues, e ⊤ j He j ≤ λ max . Therefore, for any j, D jj ≤ D jj + i>j M 2 ji ≤ λ max . Since it holds true for all j, this completes the proof. Lemma G.4. (Loewner ordering for matrix products) For any matrix A and B, σ 2 min (A) B ⊤ B ≼ B ⊤ A ⊤ AB ≼ σ 2 max (A) B ⊤ B. Lemma G.Let us consider quantizing a scalar x with |x| ≤ R. Given B bits, the scalar quantizer with dynamic range R is described by first specifying the M = 2 B quantization pointsq 1 = -R, q 2 = -R + ∆, q 3 = -R + 2∆, . . . , q M = -R + (M -1)∆, where ∆ = 2RM -1 is the resolution. The quantizer operation is defined as:EQUATION= q k+1 with probability r, q k with probability 1r,where k = arg max j {q j ≤ x}, i.e., x ∈ [q k , q k+1 ), and r = x-q k ∆ . As shown in the following lemma G.6, such a quantizer satisfiesEQUATIONi.e., it is unbiased and the error variance depends on R and B. Here, the E(•) is over the randomness from dithering in (59). If the input x to the quantizer falls outside this range, i.e., x > R or x < -R, the quantizer is said to be saturated. To quantize any matrix X, Q R,B (X) is obtained by quantizing each entry independently, i.e.,[Q R,B (X)] ij ≜ Q R,B (X ij ).Lemma G.6. For scalar x with |x| ≤ R, denote the quantization error of uniformly dithered B-bit scalar quantizer as ϵ = Q R,B (x)x. Then, E[ϵ] = 0 and Var (ϵ) ≤ R 2 (2 B -1) 2 , where the expectation E is over the randomness due to dithering in the quantizer operation.Proof. Suppose x ∈ [q k , q k+1 ) and q k+1 = q k + ∆, where ∆ = 2R 2 B -1 . Then,E Q R,B (x) = q k+1 x -q k ∆ + q k 1 - x -q k ∆ = (q k + ∆) (x -q k ) + q k (∆ -x + q k ) ∆ = x.Furthermore, the variance can be upper bounded asVar (Q R,B (x) -x) 2 = (q k+1 -x) 2 (x -q k ) ∆ + (q k -x) 2 1 - x -q k ∆ ≤ (q k+1 -x) (x -q k ) ≤ sup x∈[q k ,q k+1 ) (q k+1 -x) (x -q k ) = q k+1 - q k + q k+1 2 q k + q k+1 2 -q k = ∆ 2 4 = R 2 (2 B -1) 2 .When the input x to the quantizer exceeds R, the quantizer is said to be saturated, causing the quantization error to deviate from zero mean and bounded variance. Thus, it is crucial to ensure that the quantizer operates within the unsaturated regime with high probability.Our proposed algorithm CALDERA exploits low-rank structure in weight matrices of LLMs, and is seen to boost the performance of existing methods in the literature of LLM compression. It does so by providing an additional degree of freedom to control the compression ratio -namely, the target rank (k). Theoretical guarantees show improved performance over existing benchmarks, when the matrix being compressed is inherently low-rank to begin with -something that is observed in LLMs. This also implies that CALDERA can be used for any other application scenarios that require matrix compression, as discussed in [31] . Its effectiveness largely depends on the presence of an inherent approximate low-rank structure, which is seen in many real-world matrices [37] .Despite attaining a lower loss for LLM compression, since CALDERA is designed to tackle an optimization problem through an iterative process, it requires slightly more computational resources.For instance, compressing Llama-2 7B or Mistral-7B models (with rank-256) took approximately 34 GPU-hours (on NVIDIA A10G GPUs provisioned from an AWS G5 instance), and compressing Llama-2 13B took 59 GPU-hours (on a locally hosted NVIDIA A6000 GPU). Moreover, LLaMa-2 70B can be quantized via CALDERA with rank-256 factors in approximately 90 GPU hours (on an H100 from Lambda labs), which is on par with QuIP# (with RHT finetuning), which reports 100 GPU hours (on A100). It should be noted that these wallclock times can be reasonably afforded, and are not prohibitively large. Furthermore, since the compression of an LLM is a one-time computational expense, this cost becomes highly amortized considering the frequent use of LLMs for inference following the deployment of the compressed model.Although CALDERA often achieves perplexities and accuracies similar to unquantized models, a gap remains, as shown in Tables 1 and 2 . This indicates there is potential for enhancing quantization strategies. For example, the target rank (k) can be treated as a hyper-parameter, and adjusted across different layers. Sharma et al. [33] demonstrate that such a layer-specific rank reduction can improve generalization capabilities. Additionally, improved fine-tuning strategies such as those proposed by Liu et al. [23] , which reduce the gap between LoRA and full fine-tuning, can be incorporated with the low-rank adaptation step of CALDERA. Detailed investigations are left for future work.Broader Impacts: Compressing models enables their deployment in resource-constrained settings, facilitating educational and technological advancements with limited infrastructure. Deploying on edge devices for inference also enhances privacy by reducing the need for data to be sent to centralized servers for inference, thereby enhancing user privacy and data security. Additionally, lower computational requirements of inference using compressed models is a step towards adoption of environment-friendly AI strategies.On the other hand, as the compression is often not always lossless, any technique may result in reduced accuracy or loss of nuanced understanding, potentially impacting the reliability of the models in critical applications. Conseuqently, due diligence should be exercised when deploying these models. From a broader perspective, LLMs are quite powerful, and their easier deployment can possibly lead to misuse, such as the spread of misinformation or automated generation of harmful content. Consequently, robust regulatory frameworks are necessary, as LLMs continue becoming more accessible to the general audience.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The abstract proposes an algorithm for compression large language models (LLMs) using low-precision and low-rank approximation. The algorithm, named CALDERA, presented in this work achieves that goal. The performance of CALDERA is studied theoretically by deriving explicit approximation error guarantees, as well as numerically by compressing Llama and Mistral families of models for a variety of tasks, and shows improved performance over existing benchmarks that don't take into account low-rankness of the weight matrices. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Since this is primarily a proof of concept, the fine-tuning is not as extensive as in[36] due to computational limits. While[36] performs fine-tuning layer-by-layer prior to doing so on the 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[36]. As such, the QuIP# numbers reported here are different from[36].In practice, it can be easily checked if QL was saturated, and if so, Alg. 1 is repeated with a fresh realization of the stochastic quantizer QR. Since lemma C.2 guarantees that the saturation probability is low, it implies that "few" realizations suffice. 


Decision: This paper introduces a new method for compressing LLM's by taking advantage of both quantization and low-rank approximation of weight matrices. In contrast to prior work, they take advantage of recent approaches for *jointly* optimizing a quantized, low-rank approximation, which surprisingly performs quite a bit better than treating the problems separately from each other (e.g., finding a low-rank approximation first, then quantizing the factors). There were some concerns with the paper's experimental setup, but my feeling is that the concerns were sufficiently addressed during the response period. Without a clear benchmark for LLM compression, decisions have to be made in terms of exactly how to conduct the experiments and which ones to conduct, and the paper's choices seem reasonable enough. For the experiments they do run, the results show a clear improvement over prior approaches that treat low-rank approximation and quantization as separate steps in the compression process. For this reason, we recommend accepting the paper.

Reviews: review: paper_summary: paper_summary: This work proposes a new decomposition procedure to achieve low-precision and low-rank compression of large language model (LLM) weight matrices. Such a new method could capture high singular components accurately while compressing less significant ones. An efficient algorithm is proposed to optimize the quantized backbone and low-rank factors, which can be fine-tuned to enhance the model performance. The work also provides a tighter approximation error bound and is validated by compressing the LlaMA LLMs to below 2.5 bits per parameter.
strength_weakness: strength_weakness: I think the presented experiment study is limited. I mainly have the following suggestions. 
1. It would be better to supplement the experiments with LoftQ and LQ-LoRA, and add a set of experiments with full parameter fine-tuning as a baseline. 
2. Please provide an experimental comparison of model size. 
3. It would be better to add some experiments on evaluating the computation cost of the proposed CALDERA.
questions: questions: 1. Since the CALDERA method requires many time-consuming operations like SVD and matrix inversion, can this be improved in future work?
2. Are there any efficient ways to improve the selection strategy of the hyperparameter rank?
limitations: limitations: In my opinion, how to efficiently tune the  hyperparameter rank is the main limitation of the proposed method.
paper_summary: paper_summary: The article introduces CALDERA, a post-training compression algorithm for large language models (LLMs) that leverages the low-rank structure of weight matrices to achieve significant compression. CALDERA approximates a weight matrix $W$ using a low-rank, low-precision decomposition $W \approx Q + LR$, where $Q$, $L$ and $R$ are quantized. The method aims to reduce the memory and computational footprint of LLMs, facilitating their deployment on memory-constrained edge devices.
strength_weakness: strength_weakness: Complexity: The algorithm involves a nested optimization process, which may introduce significant computational overhead during the compression phase.

Dependency on Calibration Data: The performance of CALDERA relies on the availability and quality of calibration data, which may not always be accessible or representative.

Limited Empirical Comparisons: While the article claims superiority over existing methods, the empirical comparisons might be limited in scope, potentially omitting some relevant state-of-the-art techniques.

Potential Issues

Quantization Artifacts: Aggressive quantization, especially at very low bit budgets, might introduce artifacts that could degrade model performance in specific scenarios.

Generalization: The effectiveness of the method across a diverse range of LLMs and tasks needs thorough validation, as it might not generalize well beyond the tested models and datasets.

Optimization Stability: The iterative nature of the optimization process might lead to stability issues, particularly for large models with highly non-convex loss landscapes.
questions: questions: See Weaknesses
limitations: limitations: Yes
paper_summary: paper_summary: This paper introduces CALDERA, a novel post-training method that combines quantization and low-rank decomposition techniques for compressing large language models. The primary contribution lies in the design of a combined pipeline and the application of low-rank decomposition. Experimental results demonstrate that integrating the designed low-rank decomposition technique enhances compression performance compared to using quantization alone.
strength_weakness: strength_weakness: 1. **Missing Experimental Results:** The experiments conducted in this paper are inadequate. Many critical experiments conducted in previous works have not been included. For instance:

- Evaluation of throughput for LLaMA models compressed by CALDERA and QuIP# under the same average bits with the same batch size and sequence length. It's crucial to assess whether combining low-rank decomposition with quantization compromises efficiency compared to uncompressed LLMs.
- Evaluation results on LLMs with different architectures from LLaMA and on generation datasets.
- Evaluation of time consumption between CALDERA and QuIP# for compressing LLMs.
- Evaluation of compression performance using different calibration sets and varying numbers of calibration data.
2. **Lack of Novelty:** The novelty of this paper is limited. The primary contributions are the design of a combination framework and a low-rank decomposition algorithm, both of which appear simplistic and resemble iterative weight compression methods with minor losses. The use of the existing quantization method LDLQ for combination and the effectiveness of the designed low-rank decomposition method in achieving minimal compression loss are questionable. Replacing it with established work like data whitening method in SVD-LLM[1] might yield better performance, given SVD-LLM's theoretical proof of achieving global optimality through data whitening.

*[1] Wang, X., Zheng, Y., Wan, Z., & Zhang, M. (2024). SVD-LLM: Truncation-aware Singular Value Decomposition for Large Language Model Compression. https://arxiv.org/abs/2403.07378*

3. **Intuitive Experimental Results:** While it's intuitive that combining low-rank decomposition with quantization can improve performance over quantization-only methods, existing works such as SVD-LLM already demonstrate this. To add value to the proposed methods, it's crucial to include experimental results where the average bits are equal to or less than 1-bit, demonstrating capabilities that quantization-only methods cannot achieve.
questions: questions: See above.
limitations: limitations: N.A.
paper_summary: paper_summary: This paper introduces CALDERA, a new post-training compression algorithm for large language models (LLMs). CALDERA uses the inherent low-rank structure of LLM weight matrices by approximating them via a low-rank, low-precision decomposition $W \approx Q + LR$, where $L$ and $R$ are low-rank factors with quantized entries. CALDERA provides an effective way to compress large language models by exploiting their low-rank structure, enabling efficient distribution and deployment of LLMs on resource-constrained hardware while maintaining strong performance.
strength_weakness: strength_weakness: This paper is generally well-written. Here are some minor weaknesses:

1. The performance of CALDERA depends on the choice of target rank and quantization bit budget. The paper does not provide a systematic way to determine the optimal values for these hyperparameters. Is it possible to apply meta-learning here to decide the optimal values?

2. The experiments focus on compressing LLaMa models. It would be valuable to see how CALDERA performs on a wider range of LLMs to assess its generalizability.

3. As mentioned by the authors, the iterative nature of CALDERA's optimization process may require more computational resources compared to simpler compression methods, although this is a one-time cost.
questions: questions: How does CALDERA perform compared to other compression approaches? Is it possible to combine CALDERA with these techniques?
limitations: limitations: Please see weaknesses.
paper_summary: paper_summary: This paper proposes a framework that combines quantization and low-rank approximation. Given a neural net weight matrix $W\in \mathbb{R}^{n\times d}$, it considers the following decomposition: $W=Q+LR$, where $Q$ is a quantized sketch of $W$ with very few bits (2 or 4 in their experiments), and $L\in \mathbb{R}^{n\times k}, R\in \mathbb{R}^{k\times d}$ are low-rank factors that serve as a "correction" to the quantization sketch $Q$. They are usually quantized with more bits (4 or 16). To compute respective $Q, L, R$, the authors propose an alternating minimization framework: starts with $L, R=0$, update $Q$ as $Q_t=Q_Q(W-L_{t-1}R_{t-1})$, then solve for $L_t, R_t$ by solving the rank-constrained regression against $W-Q_t$ and $X\in \mathbb{R}^{m\times d}$, where $X$ is the calibration dataset. They further show their algorithm could be used in conjunction with LoRA and fine-tuning the randomized Hadamard transform. Extensive experiments show that their proposed algorithm gives low perplexities and high accuracies when compared against earlier algorithms.
strength_weakness: strength_weakness: Overall, I don't see big weaknesses of this paper. One potential direction for improvement is theoretically, the alternating minimization framework could possibly be sped up given $k\ll n, d$, especially the rank-constrained regression, see [1]. On the other hand, it is not clear how to integrate these possible algorithmic pieces into post-processing a model weight, so I think the approach and runtime analysis of this paper are fair.

[1] Gu, Song, Yin and Zhang. Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time. ICLR'24.
questions: questions: If we allow $L$ and $R$ to be computed to full bit-precision, could the statement / result of Theorem 4.1 be simplified?
limitations: limitations: Yes.

Comments: title: Keep my rating
Response to more concerns and abnormal results
Abnormal Results in Table 5
Further clarifications
More concerns
Further clarifications
Further clarifications
comment: Thanks for the authors' response. However, the response does not address my concerns:
1. **The author is confusing the fine-tuning of LLMs with the fine-tuning of BERT.** LLMs are designed to handle a wide range of tasks, including text generation, translation, summarization, and more. Fine-tuning an LLM often involves adapting the model to perform well on diverse tasks rather than focusing on a single, narrowly defined task like classification. In contrast, BERT is often fine-tuned for specific tasks such as classification, question answering, and named entity recognition.  I highly recommend that the authors add evaluations on several generation tasks. As mentioned before, I deeply suspect that the LLM is overfitting on fine-tuned classification datasets such as RTE and will show much poorer generation ability.
2. **The author does not follow the literature to fine-tune the LLM.** To the best of our knowledge, none of the existing LLM compression works fine-tune their compressed LLM on classification datasets. Common datasets for fine-tuning include language modeling datasets such as WikiText-2 and C4, or instruction tuning datasets such as Alpaca. The paper [1] mentioned by the authors in their response also follows this trend. For instance, the authors fine-tune RoBERTa-Large on classification datasets but fine-tune models like LLaMA-2 on C4 and OpenAssistant datasets. We recommend the authors follow the literature to design the LoRA fine-tuning experiments.
3. **The author does not address the poor time cost for compression and the poor throughput for inference.** Even though CALDERA achieves slightly better PPL than QuIP#, its poor time cost for compression and inferior throughput for inference make it less attractive. For example, when the goal is to compress the LLM to reduce its inference latency on a server where memory is not the main concern, CALDERA is even less appealing than some 3-bit quantization algorithms, as these algorithms guarantee lower latency and similar or even better accuracy.
4. **The author should use the default configuration to fully RHT-FT QuIP# and update the evaluation results on Table 3 and Table 4.** It is insufficient to only use PPL to compare the accuracy of the compressed LLMs, especially when the PPL values from two compressed LLMs are so close. The authors should update the evaluation results of LLMs compressed by QuIP# with fully RHT-FT in both Table 3 and Table 4 in the submission.

Therefore, I would still like to keep my rating.
Dear Reviewer 32tN, we believe you have made two major misunderstandings. Please allow us to clarify them.

Firstly, we believe there has been a misunderstanding as to what is referred to as fine-tuning in our paper. In LoRA fine-tuning, the model is adapted or fine-tuned using a **smaller, task-specific dataset**. Please note that Randomized Hadamard Transform fine-tuning (RHT-FT) and LoRA fine-tuning are two separate components, and independent of each other. RHT-FT is a step of the quantization process in QuIP# -- it is done on the calibration set, and is meant to decrease the PPL (or increase the accuracy) across all tasks generally. In contrast, LoRA fine-tuning is task-specific, and is done on a *specific dataset* like Wino or RTE. For instance, an accuracy of 84.93\% for Wino and 86.28\% for RTE, is a consequence of fine-tuning the LLM using LoRA on Wino and RTE, respectively. The uncompressed models have **NOT** been fine-tuned to these task specific datasets, which is why CALDERA + Fine-tuning performs better than the uncompressed model. This is very natural to expect as a consequence of fine-tuning, and not abnormal at all. It is observed in other prior works as well -- for example, see Fig. 2 of LQ-LoRA [1]. Hence, it is **not a fair comparison** to compare *CALDERA-quantized models fine-tuned for a specific downstream task* with *non fine-tuned uncompressed models*.

[1] Guo et. al, LQ-LoRA: Low-rank Plus Quantized Matrix Decomposition for Efficient Language Model Finetuning, ICLR 2024.

Secondly, we believe there has been a misunderstanding on your end regarding performance of our compressed models and prior works like QuIP#. We agree that if the metric of performance is purely quantization time or generation throughput, QuIP# achieves higher performance *with respect to those metrics*. However, that has never been the primary thesis of our work, i.e., we do not claim that compressing LLMs with CALDERA is faster than QuIP#. A central thesis of our work is that CALDERA **does** perform better than QuIP\# in the sense that that it consistently achieves lower perplexities than QuIP# -- when comparing *QuIP# without RHT-FT to CALDERA without RHT-FT*, or *QuIP# with RHT-FT to CALDERA with RHT-FT*. As RHT-FT is an optimization that applies to both QuIP# and CALDERA, it is unfair to compare accuracies and PPLs achieved by QuIP# with RHT-FT to CALDERA without RHT-FT. For a fair comparison, please refer to Table 3 where we have compared CALDERA with RHT-FT and QuIP# with RHT-FT, for 7B models. It is evident from Table 5 that CALDERA consistently has lower PPL than QuIP#. Furthermore, if you look at Table 4 of QuIP#, they report PPLs of 6.19 (Wiki) and 8.16 (C4), which are still higher than 5.84 (Wiki) and 7.75 (C4) (highlighted numbers on Table 5).

We have not done RHT-FT on the 70B model because of limited rebuttal duration. But our original submission **does report** extensive comparisons with RHT-FT for 7B models. Doing such extensive comparisons with the 70B model within the rebuttal window is infeasible. We report wallclock time for quantization, just to show that it *not prohibitively high* when compared to QuIP#. Additionally, doing RHT-FT on the CALDERA quantized 70B would take the same amount of time as the RHT-FT step in QuIP# does, which is once again, *not prohibitively slow*, given this is a one-time cost.

Regarding throughput, our global response simply shows that it is not degraded much compared to QuIP# due to the low-rank component. It should be noted that it is still significantly higher than the unquantized model (even without custom CUDA kernels for the low-rank component).

We reiterate that our work is motivated with closing the gap with respect to uncompressed models in the 2 to 2.5 bits per parameter regime. And, it is clear that we are able to get lower perplexities than QuIP# when the comparison is fair, i.e., either with or without RHT-FT in both cases.
I think the authors have addressed my comments. I shall change my rating to 7.
When comparing the accuracy of uncompressed LLaMA 2-7B and LLaMA 2-70B in Table 1 in the submission with LLaMA 2-7B compressed by CALDERA with LoRA fine-tuning in Table 5, I found that the accuracy of compressed LLaMA 2-7B is much higher than that of the uncompressed LLaMA 2-7B  and even uncompressed LLaMA 2-70B, as shown below.
|                                          | Bits | Wino  | RTE   |
|------------------------------------------|------|-------|-------|
| Uncompressed LLaMA 2-7B                  | 16   | 67.3  | 63.2  |
| Uncompressed LLaMA 2-70B                 | 16   | 77.0  | 67.9  |
| LLaMA 2-7B compressed by CALDERA with FT | 2.4  | 84.93 | 86.28 | 

This is **abnormal**, as the compressed LLM shows a significant improvement in accuracy despite an extensive compression ratio (the weight memory of LLaMA 2-70B 16bit is about 80 times larger than that of LLaMA 2-7B 2bit). The reasonable explanations I can think of are either the failure to use the optimal parameter configuration during inference, or the overfitting of the fine-tuned LLM on these three datasets. Therefore, the results in table 5 are **NOT convincing**.
Dear Reviewer xRtR,

Please let us know if your queries have been addressed satisfactorily. As mentioned in our response, we've thoroughly incorporated your feedback, along with suggestions from the other reviewers. We hope that our response has positively influenced your perception of our work.

If you require further clarifications to potentially reconsider your score, we are enthusiastic about engaging in further discussion. Please do not hesitate to contact us. We highly value the generous contribution of your time to review our paper.
Thank the authors for the detailed response and clarification. After reading the global response given by the authors. I have two more concerns.
1. **The compression time cost of CALDERA is much higher than QuIP#.** In Appendix F.7 of QuIP#'s paper, the authors claim that "All experiments were run on NVIDIA A100 GPUs ... We find that we can quantize Llama2 70B without fine-tuning in under 10 GPU-hours and with fine-tuning in around 100 GPU-hours." Therefore, the comparison of time costs in the global response is **NOT fair**. Based on the GPU hours for running CALDERA and QuIP#, I made the following table. The time cost of CALDERA without fine-tuning is already higher than QuIP# with fine-tuning. However, the perplexity (PPL) of the LLM compressed by CALDERA without fine-tuning is not as good as that compressed by QuIP# with fine-tuning, as reported in [1]. Therefore, given the same compute budget for compression, CALDERA is **less competitive** than QuIP#. Also, since QuIP# requires less time than CALDERA for compression, the explanation in the footnote of page 8 in the submission for using the LLM compressed by QuIP# but **WITHOUT** being fully fine-tuned is **NOT convincing**, and the all results reported in Section 5.2 are also **NOT convincing**. Therefore, it is still **questionable** whether the designed algorithm CALDERA is better than the baseline method QuIP#.

|         | w/o Fine-tuning    | w/ fine-tuning    |
|---------|-------------------|--------------------|
| CALDERA | 90 H100 GPU-hours | Unknown            |
| QuIP#   | 10 A100 GPU-hours | 100 A100 GPU-hours |

2. **The reported generation throughput is poor.** In Table 1 shown in the global response, the throughput of LLM compressed by CALDERA with its best configuration (Rank=256, $B_L = B_R = 4$) is 45 tok/sec, which is much worse than that of QuIP#, which is 76 tok/sec. Therefore, if throughput is the primary target, CALDERA is still **less competitive** than QuIP#.

Based on the concerns above, I have decided to temporarily adjust my score to reject and I hope more clarifications on these two concerns. 

Thank you.

[1] Albert Tseng et al., QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks. ICML, 2024
Dear Reviewer ZG6L,

Please let us know if your queries have been addressed satisfactorily. As mentioned in our response, we've thoroughly incorporated your feedback, along with suggestions from the other reviewers. We hope that our response has positively influenced your perception of our work.

If you require further clarifications to potentially reconsider your score, we are enthusiastic about engaging in further discussion. Please do not hesitate to contact us. We highly value the generous contribution of your time to review our paper.
Dear Reviewer 32tN,

Please let us know if your queries have been addressed satisfactorily. As mentioned in our response, we've thoroughly incorporated your feedback, along with suggestions from the other reviewers. We hope that our response has positively influenced your perception of our work.

If you require further clarifications to potentially reconsider your score, we are enthusiastic about engaging in further discussion. Please do not hesitate to contact us. We highly value the generous contribution of your time to review our paper.
Thank you very much for your detailed response. I will keep my original score.
I thank the authors for answering my questions and including additional experiments. I'll keep my score as is.