Compressing Large Language Models using Low Rank and Low Precision Decomposition

Rajarshi Saha; Naomi Sagan; Varun Srivastava; Andrea J. Goldsmith; Mert Pilanci

Source-linked AI summary

Compressing Large Language Models using Low Rank and Low Precision Decomposition

Rajarshi Saha, Naomi Sagan, Varun Srivastava, Andrea J. Goldsmith, Mert Pilanci

arXiv:2405.18886v2May 29, 2024cs.LGcs.AImath.OCstat.ML

TL;DR

Large language models’ size makes deployment in memory-constrained environments difficult. CALDERA compresses their weights with a calibration-aware, low-precision Q + LR decomposition. Across the reported models, rank-256 factors in 4-bit precision had the lowest perplexity and generally the highest accuracies.

Problem
Large language models’ substantial size creates high computational costs and energy consumption that challenge deployment in resource-constrained environments.
Source: §1 · p. 1
Method
CALDERA approximately decomposes each weight matrix as Q + LR, with the backbone and low-rank factors represented in low-precision formats.
Source: §1 · p. 2, §3 · p. 3
Results
Across all models, rank-256 CALDERA with 4-bit factors had the lowest perplexity and generally the highest accuracies.
Source: §5.1 · p. 7
Takeaways & Limitations
Quantizing the low-rank factors allows more singular components to be captured than half-precision factors at the same bit budget, and can regain performance compromised by a 2-bit backbone.
Source: §5.1 · pp. 7–8
The fine-tuning experiment was limited by computational constraints, used end-to-end fine-tuning only, and used sequence length 512 rather than 4096.
Source: §5.2 · p. 8

Abstract

from arXiv · show

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/$13B$/$70$B and LlaMa-$3$ $8$B models using $\rm CALDERA$ outperforms existing post-training LLM compression techniques in the regime of less than $2.5$ bits per parameter. The implementation is available at: https://github.com/pilancilab/caldera.

1 Introduction

LLM weight matrices often contain low-rank redundancy, motivating compression for resource-constrained deployment. CALDERA combines low-precision quantization with low-rank factors and adaptation, building on existing compression methods.

1 Introduction

Low-rank redundancy in LLM weights motivates compression intended to reduce memory and computational requirements for resource-constrained deployment.The introduction links this redundancy to correlated language syntax and semantics learned during training.Source: §1 · p. 1
CALDERA replaces each weight matrix with Q + LR, representing the backbone and both low-rank factors in low-precision formats.The factors capture large singular components, while Q coarsely represents less significant components.Source: §1 · p. 2
Low-rank factors L and R can be fine-tuned to boost zero-shot performance after the model is compressed.Their parameter count is k(n + d), much smaller than the matrix's nd entries when k ≪ min{n, d}.Source: §1 · p. 2

1.1 Significance and Related Works

CALDERA builds on QuIP# and related compression strategies while jointly leveraging LLM weight matrices’ approximate low-rank structure.Earlier approaches cited here either treat low-rank factorization and quantization independently or formulate joint optimization for generic matrices.Source: §1.1 · pp. 2–3
More aggressively compressed LLMs are possible, but the cited approach requires training from scratch and is computationally demanding.Source: §1.1 · p. 2

2 Problem Formulation

The formulation uses the weight matrix’s decaying singular-value spectrum to motivate a low-rank component, then optimizes a low-precision decomposition against calibration activations.

2 Problem Formulation

A decaying singular-value profile motivates retaining leading components while pruning less-contributing components with minimal output distortion.The layer’s weight matrix transforms input activations x into Wx; output Frobenius error is used as a proxy objective for quantization.Source: §2 · p. 3
CALDERA extends low-rank decomposition by quantizing Q, L, and R, reducing memory use or allowing a higher target rank at the same footprint.The passage contrasts this with prior methods that keep low-rank factors in 16- or 32-bit floating point.Source: §2 · p. 3
The optimization seeks Q + LR close to W while minimizing the Frobenius-norm error of the compressed layer’s outputs on calibration data.The calibration matrix contains input embeddings for the first layer or input activations for intermediate layers.Source: §2 · p. 3

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

CALDERA approximately solves the calibration-aware decomposition by alternating quantized updates to the backbone and low-rank factors. The factors can also be fine-tuned for task-specific adaptation.

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

CALDERA approximately solves the calibration-aware decomposition through nested loops that alternately optimize Q, L, and R.It initializes the factors to zero and first quantizes W with LDLQ.Source: §3 · p. 3
After fixing Q, the algorithm factorizes the residual W − Q using calibration-aware low-precision low-rank factorization and iteratively refines L and R.The update equations use a rank-constrained regression framework; refinement can only reduce the Frobenius-norm error.Source: §3 · p. 4
The low-rank factors are initialized by rank-constrained regression before quantization, then updated to reduce the distortion introduced by quantization.Source: §3 · p. 4
After replacing layer weights with Q + LR, L and R can be fine-tuned on a small task-specific dataset to boost zero-shot performance.The fine-tuned factors use 16-bit BF16, slightly increasing memory footprint while yielding substantial performance gains.Source: §3 · p. 4

4 Approximation Error Analysis

CALDERA’s approximation error is bounded through rank-constrained regression, with the bound exposing a tradeoff between target rank and quantization bit budgets. The analysis also outlines how the regression solution and low-rank factorization are used to establish the bound.

4 Approximation Error Analysis

CALDERA approximates W as Q + LR using calibration data, with quantized Q and low-precision low-rank factors L and R.The analysis assumes Q’s quantizer has a sufficiently high dynamic range to remain unsaturated.Source: §4 · pp. 5–6
Theorem 4.1 bounds CALDERA’s approximation error while using an average budget of 1 bit per parameter for the low-rank factors when n≈d.The theorem’s conditions include a target rank and dynamic ranges for the quantizers.Source: §4 · p. 5
The upper bound can be made arbitrarily small by increasing backbone bit-budget BQ at fixed rank k or increasing k at fixed BQ.The bound’s two contributions are rank-constrained regression error, which depends on k, and additive quantization error, which depends on the L and R bit budgets.Source: §4 · pp. 5–6

4.1 Analysis Outline

The proof outline uses rank-constrained regression, whose non-convex problem can be solved globally via two SVDs.For analysis, Q is updated before L and R; in practice, the order can be swapped to whichever yields lower error.Source: §4.1 · p. 6
LPLRFACTORIZE’s error is upper-bounded by twice the sum of squared trailing singular values, with high quantizer dynamic ranges chosen to make saturation unlikely.The theorem proof also uses an LDL decomposition and a Marchenko-Pastur approximation to bound expected quantization-error eigenvalues.Source: §4.1 · p. 7

5 Numerical Simulations

The numerical simulations evaluate CALDERA across LLaMa models and compression settings, then examine RHT fine-tuning, low-rank adaptation, and autoregressive throughput. Results show rank-256 factors generally lead on zero-shot metrics, while fine-tuning and compressed-weight execution offer additional performance and speed trade-offs.

5 Numerical Simulations

The simulations cover LLaMa-2 7B, 13B, and 70B and LLaMa-3 8B, measuring perplexity and task-specific zero-shot accuracy against QuIP# baselines.CALDERA uses a 2-bit backbone; tested per-parameter budgets range from 2.1 to 2.4 bits.Source: §5 · p. 7, §5.1 · p. 7

5.1 Zero-shot Results

Across all models, rank-256 CALDERA with 4-bit factors had the lowest perplexity and generally the highest accuracies.The comparisons cover LLaMa-2 and LLaMa-3 8B with the backbone Q fixed at 2 bits.Source: §5.1 · p. 7, Table 1 · p. 8, Table 2 · p. 8
Zero-shot accuracies have inherent randomness and low-rank regularization effects, and LLaMa-3 8B is more affected by low-bit quantization than the LLaMa-2 models.The authors note that perplexity is a more direct indicator of quantization performance; LoRA fine-tuning can recover accuracy degradation.Source: §5.1 · p. 8

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

End-to-end RHT parameter fine-tuning substantially lowers perplexities, while rank-256 factors typically perform best except on RTE.This section is a proof of concept: due to computational limits it omits layer-by-layer tuning and uses sequence length 512 rather than 4096.Source: §5.2 · p. 8

5.3 Low Rank Adaptation (LoRA) Fine-tuning Results

Fine-tuning the top 64 singular components in BF16 on WikiText2, RTE, or WinoGrande can noticeably boost zero-shot accuracy.For available LLaMa-2 comparisons, CALDERA achieves better performance than LoftQ and LQ-LoRA at a lower bit budget.Source: §5.3 · p. 9

5.4 Autoregressive Generation Throughput

CALDERA throughput is slightly below QuIP# but significantly above the unquantized model, as compressed weights reduce GPU-SRAM data transfer.The throughput comparison uses an A10G GPU with batch size and sequence length both equal to 1, with Q at 2 bits.Source: §5.4 · p. 9, Table 6 · p. 10

6 Conclusions

CALDERA decomposes each LLM weight matrix into a quantized backbone and low-rank factors, capturing large singular components while coarsely compressing less significant ones. The conclusion highlights its theoretical error bound, empirical evaluation below 2.5 bits per parameter, and the option to fine-tune the factors.

6 Conclusions

CALDERA combines a quantized backbone with low-rank factors, establishes an approximation-error upper bound, and is evaluated on LLaMA models below 2.5 bits per parameter.Fine-tuning the factors can further boost zero-shot performance; the method may also complement existing compression strategies.Source: §6 · p. 10

B Rank-constrained Regression

The rank-constrained regression problem is non-convex but can be solved globally using two singular value decompositions.The stated complexity is O(m^2(n + d)).Source: B Rank-constrained Regression · pp. 16–17

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

LPLRFACTORIZE computes each low-rank factor by solving a least-squares minimization problem with the other factor fixed.The section derives update expressions for both L and R.Source: §C.1 · pp. 17–18

C.2 Dynamic Ranges of Quantizers

The right quantizer remains unsaturated when its dynamic range is set to the largest singular value of XA⊤.The left quantizer's input bound depends on the right quantizer remaining unsaturated.Source: §C.2 · p. 18

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

This proof section establishes an approximation-error upper bound for LPLRFACTORIZE. The analysis conditions the bound on quantizer saturation behavior and the selection of rank and bit budgets.

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

Lemma C.3 gives an approximation-error upper bound for LPLRFACTORIZE, with the returned factors satisfying a bound in expectation over quantizer randomness.The supplied theorem statements identify rank and quantizer bit budgets among the bound's conditions.Source: §C.3 · pp. 19–20
The bound is conditioned on the left quantizer QL being unsaturated, an event the analysis says occurs with probability at least 1 − 0.25ϵ.For the saturated case, the proof assumes the algorithm returns L = 0 and R = 0.Source: §C.3 · p. 22

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

The section presents an approximation-error upper bound for CALDERA and discusses a closed-form rank-constrained regression solution under positive-definite Hessians. It also records computational and quantization settings, including calibration data and an empirical convergence heuristic.

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

Theorem C.4 bounds CALDERA's approximation error in expectation under stated rank and bit-budget conditions.The expectation covers stochasticity in the quantizers for Q, L, and R.Source: §C.4 · pp. 22–23

C.5 A simplification for positive definite Hessians

For a positive-definite Hessian, the rank-constrained regression problem has a closed-form optimal solution based on the SVD of Y.The section notes that adding a small scaled identity can ensure positive definiteness in practice.Source: §C.5 · p. 24

D Computational Complexity of CALDERA

For a given calibration dataset/activation X in R^{m×d}, preprocessing costs O(md^2 + 2d^3): computing H takes O(md^2), LDL decomposition O(d^3), and beforehand computing HH† adds O(d^3).Source: D Computational Complexity of CALDERA · p. 25

E.2 Parameters of CALDERA Quantization

The reported setup uses 256 RedPajama calibration samples, and an updated Hessian heuristic was found to empirically speed CALDERA's convergence.For LLaMA-2 70B, quantization SVD steps were replaced with randomized SVD for computational speedup.Source: §E.2 · p. 26

E.3 Details about Goodness-of-Fit Metrics

This appendix describes the evaluation metrics and selected experimental settings. It also notes that one reported LQ-LoRA comparison used fine-tuning data different from the evaluated task, and that QuIP# results for LLaMA-2 70B were recreated after published results could not be replicated.

E.3 Details about Goodness-of-Fit Metrics

In addition to perplexity on the WikiText2 and C4 datasets, CALDERA was evaluated using zero-shot accuracy on sequence classification tasks.Source: §E.3 · p. 26

E.4 Fine-tuning Parameter Details

The LQ-LoRA Winogrande result cited for comparison was fine-tuned on subsets of C4 and WikiText2, not directly on Winogrande.This qualifies the data-setting match for that comparison.Source: §E.4 · p. 26

E.5 Computation of Average Bit Budget Per-Parameter

The per-parameter bit-budget calculation depends on matrix dimensions, backbone and factor bit budgets, and factor rank.The section separately notes that rank-64 factors are fine-tuned in 16-bit precision.Source: §E.5 · p. 27

E.6 Additional Notes on Numerical Simulations

For LLaMA-2 70B, the paper reports recreated QuIP# results because the published zero-shot perplexities and accuracies could not be replicated.The CALDERA-versus-QuIP# comparison for that model therefore uses those recreations.Source: §E.6 · p. 27

F.1 Ablation Study of CALDERA Parameters with respect to Frobenius Norm Error

The ablations compare CALDERA’s factor precision and quantization and update choices, while tracking data-aware error across iterations. CALDERA with 16-bit factors consistently has lower error than QuIP#, and alternating factor updates benefit the Key projection more than the Up projection.

F.1 Ablation Study of CALDERA Parameters with respect to Frobenius Norm Error

Figure 3 tracks per-iteration relative data-aware Frobenius error for selected LLaMa-2 7B layer-25 matrices, using 2-bit Q and the Section 5 calibration data.The error is defined using the calibration matrix X and the difference between the CALDERA decomposition and unquantized weight matrix.Source: §F.1 · p. 27, Figure 3 · p. 28
Ablations vary factor precision, RHT, LDLQ, and Hessian updates across ranks 64, 128, and 256, against same-size QuIP# factors using the same calibration data.The 16-bit-factor setup uses half-precision factors; the 4-bit setup uses E8 lattice quantization and 10 LPLRFACTORIZE iterations per factor update.Source: §F.1 · pp. 27–28
CALDERA with 16-bit factors consistently achieves lower error than QuIP#; 4-bit factors incur only minor degradation, while replacing LDLQ with a lattice quantizer significantly degrades Frobenius-norm error.Source: §F.1 · p. 28
Alternating minimization reduces LPLRFACTORIZE error for both matrices, nominally for the Up projection and significantly for the Key projection.Figure 4 plots per-iteration relative data-aware error for two layer-25 matrices, with both factors quantized to 4 bits using an E8 lattice quantizer after the randomized Hadamard transform.Source: §F.1 · p. 29, Figure 4 · p. 29

F.2 Experiments on Mistral-7B

Mistral-7B results are reported as consistent with Section 5.1. Table 9 evaluates perplexity and benchmark accuracy under the stated quantization settings.

F.2 Experiments on Mistral-7B

The Mistral-7B results are described as consistent with those in Section 5.1.No specific comparison or numerical outcome is provided in the passage.Source: §F.2 · p. 29
Table 9 reports Wikitext2 and C4 perplexities and percent accuracies on common language-modeling benchmarks for CALDERA-compressed Mistral 7B.The supplied passage does not state individual table values.Source: Table 9 · p. 29
All quantizations use 2-bit Q; when factors are present, L and R use 4 bits, and the reported QuIP# comparison excludes RHT fine-tuning.The calibration datasets are those released on Huggingface by the QuIP# authors.Source: Table 9 · p. 29

G.1 Useful Results from Linear Algebra and Probability

The appendix collects linear-algebra and probability results, then describes a uniformly dithered scalar quantizer and its behavior within the unsaturated range.

G.1 Useful Results from Linear Algebra and Probability

G.1 collects standard results, including the Eckart–Young–Mirsky best rank-k approximation theorem and a high-probability spectral-norm bound for random matrices with subgaussian entries.The spectral-norm bound is expressed in terms of the entries’ subgaussian norm.Source: §G.1 · pp. 29–30
For an LDL decomposition H = (M + I)D(M + I)⊤, each diagonal entry D_jj is at most λmax, the largest eigenvalue of H.Source: §G.1 · p. 30
G.1 also lists a Loewner-ordering result for matrix products and the bound σmin(A+B) ≥ σmin(A) − ∥B∥2.Source: §G.1 · p. 30

G.2 Uniformly dithered scalar quantizer

The scalar quantizer uses 2^B evenly spaced points from −R to R, with resolution Δ = 2R/(2^B−1).Source: §G.2 · p. 30
For inputs within ±R, the uniformly dithered scalar quantizer is unbiased with variance bounded in terms of range and bit depth; saturation falls outside this guarantee.Matrices are quantized entrywise; inputs outside the range are saturated.Source: §G.2 · pp. 30–31

H Limitations and Further Discussions

CALDERA’s compression gains depend on approximate low-rank structure, and its rank offers another compression control. The discussion notes added optimization compute, a remaining gap to unquantized performance, and broader deployment benefits and risks.

H Limitations and Further Discussions

CALDERA’s effectiveness depends on approximate low-rank structure, a property the authors report for many real-world matrices, and it may apply beyond LLM compression.The authors state that theoretical guarantees improve over existing benchmarks when the compressed matrix is inherently low-rank.Source: H Limitations and Further Discussions · p. 31
34 GPU-hours for rank-256 Llama-2 7B or Mistral-7B compression and 59 for Llama-2 13B; Llama-2 70B takes approximately 90 GPU-hours.The authors report the 70B time as on par with QuIP#’s reported 100 GPU-hours, using different GPUs; compression is a one-time cost.Source: H Limitations and Further Discussions · p. 31
A gap from unquantized-model perplexities and accuracies remains; layer-specific ranks and improved adaptation are proposed as future directions.The authors leave detailed investigation of these approaches for future work.Source: H Limitations and Further Discussions · p. 31
Compressed deployment may support resource-constrained settings and privacy, but accuracy loss may affect reliability in critical applications.The discussion also flags easier access as a possible avenue for misinformation or harmful content.Source: H Limitations and Further Discussions · p. 31