Compressing Large Language Models using Low Rank and Low Precision Decomposition

If we allow $\mathbf{L}$ and $\mathbf{R}$ to be computed to full bit-precision, could the statement/result of Theorem 4.1 be simplified?

Yes, in Thm. $4.1$, the error from quantizing the low-rank factors is captured in the additive $\epsilon$ term. When $\mathrm{B_L} \to \infty, \mathrm{B_R} \to \infty$, this error $\epsilon \to 0$, and we get $\frac{1}{nm}\mathbb{E}\left\lVert\mathbf{(Q + LR - W)X}\right\rVert_F^2 \lesssim \frac{4d\lambda_{max}\mathrm{R}^2}{\pi(2^{\mathrm{B_Q}}-1)^2}\left(1 - \frac{k}{2n}\right)^2$. Here, the only source of error is the finite precision of the $\mathbf{Q}$ matrix, determined by $\mathrm{B_Q}$. Furthermore, if the low-rank factors $\mathbf{L, R}$ are not required to be quantized, CALDERA simplifies to LoftQ -- the only difference being CALDERA uses LDLQ quantizer, whereas LoftQ uses NF4 quantizer.

One potential direction for improvement is theoretically, the alternating minimization framework could possibly be sped up given, especially the rank-constrained regression

Thank you for pointing out this interesting work. We agree that solving rank-constrained regression can be sped up using sketching techniques from Gu et. al. [1]. A careful analysis is required to ensure that the error from sketching does not accumulate across the alternating iterations. A study of the efficacy of sketching in solving the non-convex optimization problem (1) is worth investigating.

[1] Gu et. al., Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time (ICLR, 2024).

wider range of LLMs

We have performed quantization experiments on the Mistral 7B model, which can be found in Table 2 of the global response PDF. The PPLs obtained using CALDERA are consistently lower than QuIP# (no RHT fine-tuning) for comparable average bits. For future work, with additional compute, we intend to continue quantizing more such models.

other compression approaches ... possible to combine CALDERA

Thank you for another interesting question. It is indeed possible to combine CALDERA with other existing model compression techniques. A primary motivation of CALDERA of is to jointly solve two popular approaches in LLM compression, namely, low-rank decomposition and quantization -- both of which are usually treated as independently in existing works. The same motivation can indeed be used if one wants to adapt CALDERA to incorporate other compression approaches, such as sparsity, quantization-aware training (QAT), knowledge distillation, etc. For instance, the quantized $\mathbf{Q}$ matrix can be additionally pruned, making it sparse in each CALDERA iteration, further compressing the model. Moreover, provided additional compute, the quantized entries of our CALDERA decomposition can also be subjected to QAT using a straight-through estimator. QAT can either be done for fine-tuning on downstream tasks. Alternatively, QAT can also be done by performing knowledge distillation with an uncompressed teacher model, similar to what is done in LLM-QAT (ref. [1] below).

[1] Liu et. al., LLM-QAT: Data-Free Quantization Aware Training for Large Language Models (arXiV 2023).

systematic way to determine the optimal values for these hyperparameters ... apply meta-learning here

Thank you for this very interesting question. Meta-learning can indeed be useful. For instance, each matrix decomposition problem along with a given calibration set, can be treated as a separate task. The objective would be to learn how to choose the target rank and bit budget for the decomposition. The input to the meta-learning algorithm could be input characteristics of the matrix, such as dimensions, dynamic range of the entries, spectrum of the matrix, etc. Furthermore, the measure of performance could be the Frobenius norm error, possibly regularized with some metrics for the computation time required for obtaining the decomposition, or inference time with the decomposed representation. This is a direction worth exploring!

iterative nature of CALDERA's optimization process may require more computational resources

Yes, we acknowledge this additional computational cost of compressing models iteratively. We will release open-source our compressed models, so that this one-time compression cost need not be incurred for someone who wishes to align or fine-tune our compressed models for downstream evaluations.

Compressing Llama-2 7B or Mistral-7B models (with rank-256) took approximately 34 GPU-hours, when done on NVIDIA A10G GPUs provisioned from a G5 instance on AWS. Additionally, compressing Llama-2 13B took 59 GPU-hours, when done on NVIDIA A6000 GPUs. As noted in the paper, CALDERA is expected to take more time that QuIP# (without RHT finetuning) as it is an iterative algorithm. However, as seen above, the wallclock times are not prohibitively large. Furthermore, LLaMa-2 70B can be quantized via CALDERA with rank-256 factors in about 90 GPU hours on an H100 cluster, which is on par with QuIP# (with RHT finetuning), which reports 100 GPU hours. CALDERA is also faster than some other state-of-the-art methods such as AQLM, which reports a range between 192 to 384 GPU hours, and LLM-QAT, which requires 960 GPU hours. It should be kept in mind that the cost of compressing a model is a one-time cost, and it can be reasonably afforded as long as it is not prohibitively huge.

Novelty

We propose an idea which is simple in its execution; that does not mean it lacks novelty. CALDERA is the first work that combines quantization with a low-rank decomposition -- both of which are usually treated independently in existing works on LLM compression. Additionally, a significant contribution of this work lies in the novel theoretical guarantees bounding the expected approximation error with respect to the bit budget. The quantization of the low-rank factors, as well as the complexity of the LDLQ quantization method, make these bounds challenging to obtain. Thank you for pointing us out to the nice work, SVD-LLM. Specifically, our work is different in the following aspects:

1. For a given weight matrix $\bf A$, SVD-LLM considers solving the rank-constrained regression problem, ${\rm min}_{\bf L,R}|| {\bf (LR-Z)X} ||_F^2$ to global optimality. This is a known result (ref. [1] below). We use an equivalent whitening process in Lemma 4.2 of our paper. Additionally, our theoretical guarantees upper bounds the perturbation error to this optimal solution due to the joint quantization constraints on $\bf L$ and $\bf R$ -- something not considered in the SVD-LLM paper. Quantization of low-rank factors in SVD-LLM is done independent to the low-rank decomposition, (i.e., one after the other) in Sec. 4.4, which is suboptimal compared to the joint decomposition of our LPLRFactorize module. This is reflected in the numerical results, where SVD-LLM reports a perplexity of 13.29 (Table 8 for SVD-LLM + GPTQ-4bit), which is significantly higher that our reported PPLs in Table 1 (for example, 6.19 for CALDERA Rank-256, $B_L = B_R = 4$).

2. Moreover, CALDERA considers a $\bf Q + LR$ decomposition. This additive matrix $\bf Q$ (not considered in SVD-LLM), coarsely captures the effect of trailing singular values, which are entirely truncated in SVD-LLM. The $\bf Q$ matrix enables CALDERA to achieve PPLs close to the unquantized model in the extreme compression regime considered.

[1] Xiang, et. al., Optimal exact least squares rank minimization (ACM SIGKDD, 2012)

Intuitive Experimental Results

One of the core motivations of post-training quantization of LLMs is to ensure minimal loss in PPLs or accuracies compared to the uncompressed model. Current methods that compress an LLM in the regime of 2 to 2.5 bits per parameter, fail to close the gap to uncompressed performance. While contemporary works like BiLLM (Huang et. al, 2024) do consider the lower ~1 bit per parameter regime, the associated PPLs are relatively high compared to the uncompressed model. In contrast, our work is motivated with closing the gap with respect to uncompressed models in the 2 to 2.5 bits per parameter regime.

While it is indeed intuitive that low-rank + quantization is expected to perform better than quantization only methods, our work rigorously formalizes this intuition with theoretical backing and experimental results. Although both SVD-LLM and our work explore the benefits of combining quantization with low-rank decomposition, SVD-LLM directly applies LLM quantization methods to the low-rank factors in an orthogonal fashion (which is suboptimal), whereas CALDERA additively combines a full-rank, aggressively-quantized matrix with a quantized low-rank correction (which is obtained by treating the quantization and low-rank constraints jointly).

Evaluation of throughput

We agree that it is important to ensure CALDERA does not degrade generation throughput. We have performed some throughput experiments, which can be found in Table 1 of the global response PDF. CALDERA achieves a slightly lower throughput than QuIP#, as it requires dequantization of 3 matrices -- $\bf Q, L$ and $\bf R$ (instead of just one in the case of QuIP#), and perform additional matrix multiplications during inference. Despite this, it is worthwhile to note that the throughput is quite higher than the uncompressed model. Furthermore, it should be kept in mind that designing specialized CUDA kernels that are aware of the $\bf Q + LR$ decomposition can improve the throughput even further -- for example, by computing $\bf Qx$ and $\bf LRx$ in parallel. Writing custom kernels is left for future work.

Evaluation ... different calibration sets

Our choice of sampling from RedPajama to get our calibration dataset is motivated from the fact that OpenLlama uses it to pre-train the model from scratch, and it is important to ensure that the calibration data is from the same distribution as the pre-training data. While ablations over calibration datasets is worthwhile to explore, we have decided to prioritize other experiments (cf. global response PDF) within our current computational budget.

different architectures

We have performed additional experiments (specifically, we compressed Llama-2 13B and Mistral-7B), which can be found in Table 2 of the global response PDF.

Evaluation ... time consumption

While a comprehensive evaluations would require more time, we report some numbers here. Compressing Llama-2 7B or Mistral-7B models (with rank-256) took approximately 34 GPU-hours, when done on NVIDIA A10G GPUs provisioned from a G5 instance on AWS. Additionally, compressing Llama-2 13B took 59 GPU-hours, when done on NVIDIA A6000 GPUs.

CALDERA is expected to take more time that QuIP# (no RHT finetuning) as it is an iterative algorithm. However, as seen above, the wallclock times are not prohibitively large. Also, LLaMa-2 70B can be quantized via CALDERA with rank-256 factors in ~90 GPU hours on an H100 cluster, which is on par with QuIP# (with RHT finetuning), which reports 100 GPU hours. CALDERA is also faster than some other state-of-the-art methods such as AQLM, which reports a range between 192 to 384 GPU hours, and LLM-QAT, which requires 960 GPU hours. It should be kept in mind that the cost of compressing a model is a one-time cost, and it can be reasonably afforded as long as it is not prohibitively huge.

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#.

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 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.

experimental comparison of model size

We have performed ablations over multiple sizes of the Llama-2 family. Please refer to Table 2 of the global response. The PPLs obtained using CALDERA are consistently better than QuIP# (without fine-tuning) for comparable average bits.

evaluating the computation cost

Thank you for this suggestion. While a comprehensive evaluations would require more time, we report (and compare) some numbers here. Compressing Llama-2 7B or Mistral-7B models (with rank-256) took approximately 34 GPU-hours, when done on NVIDIA A10G GPUs provisioned from a G5 instance on AWS. Additionally, compressing Llama-2 13B took 59 GPU-hours, when done on NVIDIA A6000 GPUs.

As noted in the paper, CALDERA is expected to take more time that QuIP# (without RHT finetuning) as it is an iterative algorithm. However, as seen above, the wallclock times are not prohibitively large. Furthermore, LLaMa-2 70B can be quantized via CALDERA with rank-256 factors in about 90 GPU hours on an H100 cluster, which is on par with QuIP# (with RHT finetuning), which reports 100 GPU hours. CALDERA is also faster than some other state-of-the-art methods such as AQLM, which reports 192 to 384 GPU hours, and LLM-QAT, which requires 960 GPU hours. Additionally, each layer is quantized independent of other layers -- hence, the wallclock time for CALDERA can be reduced by processing the layers in parallel (i.e., scaling horizontally by using more GPUs). Moreover, it should be kept in mind that the cost of compressing a model is a one-time cost, and it can be reasonably afforded as long as it is not prohibitively huge.

time-consuming operations like SVD and matrix inversion, can this be improved in future work?

Thank you for raising this question. It is indeed possible to reduce the computational complexity of CALDERA. For instance, the SVD computation in the LPLRFactorize submodule can be replaced with randomized LPLR submodule from (ref [30] in the paper), which leverages Gaussian sketching matrices to reduce the complexity from $O(nd^2)$ to $O(ndm)$, where $m \ll \mathrm{min}\\{n,d\\}$ is the sketch size.

Furthermore, we would like to clarify that matrix inversion is not necessary to obtain the left and right low-rank factors. These factors can be obtained by directly solving the corresponding least-squares minimization problem (in lines 8 and 9 of Alg. 2) using a conjugate gradient descent based solver, which will be significantly faster. The closed form expressions in our paper are used to facilitate analysis and derive Thm 4.1.

More generally, the constrained optimization problem (1) is NP-hard, and designing efficient algorithms to solve it is an interesting research avenue, with applications much broader than LLM compression.

selection strategy of the hyperparameter rank?

Thank you for this very interesting question! At a high level, it is possible to adaptively select the rank of each layer during fine-tuning using a strategy similar to AdaLoRa [1]. The initial rank can be chosen to be high, for instance 256. Subsequently, during fine-tuning for a downstream task, the singular values of the low-rank component can be analyzed such that smaller singular values can be truncated to adaptively reduce the rank of each layer. Finding efficient and optimal ways to do this warrants a deeper investigation.

[1] Zhang et. al., Adaptive Budget Allocation for Parameter-Efficient Fine-Tuning (ICLR, 2023)

experiments with LoftQ and LQ-LoRA ... full parameter fine-tuning as a baseline.

The results of LoftQ and LQ-LoRa are restated in Table 5 (copied from respective papers). Fine-tuning the low-rank factors obtained from CALDERA shows that we get lower PPLs for fewer average number of bits when compared to LoftQ or LQ-LoRA.

LoftQ and LQ-LoRA report PPLs that are at par or better than vanilla LoRA on WikiText2 PPLs. Moreover, it is know that for several tasks, LoRA performs at par with full fine-tuning. Therefore, we have prioritized utilizing our limited computational budget for other ablation experiments on CALDERA (please refer to the global response).

Quantization Artifacts

We agree that compression introduces artifacts. However, PPLs on language modeling datasets like Wikitext and C4 are generally considered to be reasonably good indicators of the performance of an LLM, as can be seen in the existing literature. A comprehensive evaluation over the complete spectrum of LLM evaluation tasks is beyond the scope of our computational budget. In addition, we have performed additional model quantization experiments on different sizes of LLaMa-2 model, as well as Mistral 7B, for which CALDERA generalizes well. These results can be found in Table 2 in the global response PDF.

Limited Empirical Comparisons

Please refer to additional experiments in the global response PDF.

Optimization Stability

While it is possible that the iterative nature of our algorithm may oscillate, it is not a cause of concern as Algs. 1 and 2 keep track of (and return) the best matrices $\mathbf{Q}$, $\mathbf{L}$ and $\mathbf{R}$ seen across all the iterations. Moreover, as can be seen from our Frobenius norm vs. iteration plots in Appendix G, the convergence of our algorithm is pretty well-behaved when decomposing LLM weight matrices. Furthermore, our theoretical guarantee in Thm 4.1 serves as an assurance that stability is not a cause of concern.

Complexity

We have discussed the computational complexity of CALDERA in Appendix D, and acknowledge it as a price paid for the improved error guarantees (as stated in Thm 4.1, as well as our numerical evaluations).

Additionally, we report (and compare) some numbers here. Compressing Llama-2 7B or Mistral-7B models (with rank-256) took approximately 34 GPU-hours, when done on NVIDIA A10G GPUs provisioned from a G5 instance on AWS. Additionally, compressing Llama-2 13B took 59 GPU-hours, when done on NVIDIA A6000 GPUs.

As noted in the paper, CALDERA is expected to take more time that QuIP# (without RHT finetuning) as it is an iterative algorithm. However, as seen above, the wallclock times are not prohibitively large. Furthermore, LLaMa-2 70B can be quantized via CALDERA with rank-256 factors in about 90 GPU hours on an H100 cluster, which is on par with QuIP# (with RHT finetuning), which reports 100 GPU hours. CALDERA is also faster than some other state-of-the-art methods such as AQLM, which reports a range between 192 to 384 GPU hours, and LLM-QAT, which requires 960 GPU hours. It should be kept in mind that the cost of compressing a model is a one-time cost, and it can be reasonably afforded as long as it is not prohibitively huge.

Dependency on Calibration Data

While this is true, the availability of good quality data is a central premise for the success of any data-centric algorithm. It is possible to derive an entirely data-agnostic variant of CALDERA, by simply replacing the calibration data matrix $\mathbf{X}$ by an identity matrix, $\mathbf{I}$. However, using a data-aware version yields better results as validated by ours, as well as several prior works, including QuIP# and LQ-LORA.