SVD-LLM: Truncation-aware Singular Value Decomposition for Large Language Model Compression

Background and Motivation

SVD作为一种模型压缩方法，不需要硬件依赖或者模型再训练。现有的一些SVD方法，如ASVD以及FWSVD被提出。但是这些方法当模型的压缩率高时，这些方法的性能会有很大的下降。主要原因是

imprecise data preposcessing. 尽管ASVD考虑了activation的outliers,但是并没有建立奇异值和模型压缩损失的关系.
忽视SVD截断之后的模型参数更新. 为了补偿截断产生的额误差,需要更新剩余的参数。但是现在基于SVD的方法都没有考虑参数更新，当压缩率高时，并没有去处理准确度的问题。

Main Contributions

truncation-aware data whitening技术. 通过理论证明，SVD-LLM 可以将奇异值直接映射到模型压缩损失。这种技术可以识别哪些损失值被截断时，模型压缩的损失是最小的。
layer-wise closed-form model parameter update. 为了补偿高压缩率下的准确度降低，SVD-LLM可以逐层更新压缩的权重。

Theoretical Framework/Algorithm

SVD-LLM的流程为：使用sentence的随机集合作为校准集来生成activation，以实现truncation-aware whitening 以及 layer-wise closed-form update。SVD-LLM使用cholesky decomposition来洗白activation，对权重矩阵执行svd。

truncation-aware data whitening

受制于input activation的高方差，使用原始SVD来进行LLM压缩会产生严重的accuracy degradation。为了解决这个问题，ASVD将LLM 压缩问题转换成了如下的优化问题：

$O=\min (L:=\|WX-W'X\|_F)$

其中W是LLM的原始权重，X是给定输入的W的激活值,L是压缩损失。ASVD从X中提取一个对角矩阵，将$WX$ 转换为 $(WS_0)S^{-1}_0X)$，ASVD对$WS_0$执行截断SVD。尽管这种normalizing activation可以提高性能，ASVD并不能直接建立起奇异值和压缩损失的直接关系。如下是两个直接的例子来说明这样的关系。在图2(a)中，只截断一个奇异值时，若是最小的奇异值0.1被截断时，产生的loss为1.1.而截断第二最小的奇异值0.0时，产生的损失值为0.7。当截断两个奇异值时，截断最小的两个奇异值反而比截断2.4和0.1产生的损失值更大。因此截断最小的奇异值并不会产生最小的损失值。

SVD LLMs的关键思想是结合一种感知截断的数据白化技术，以确保奇异值和压缩损失之间的直接映射。
为了实现这个技术，SVD-LLM将激活值转变为正交矩阵，激活值变为$S^{-1}X$，此时$(S^{-1}X)(S^{-1}X)^T=I$。其中$S$来自$XX^T$的Cholesky分解。我们对$WS$执行SVD来获取$U,\Sigma,V$，最后对奇异值进行截断，得到 $W’=U\times Trunc(\Sigma)\times V^T\times S^{-1}$. 图2(b)展现了本文的效果。当只有一个奇异值被截断是，compression loss等于被截断的奇异值本身。截断多个奇异值的压缩损失等于它们的平方和的平方根。因此，在所提出的感知截断的数据白化技术下，截断最小的奇异值导致最小的压缩损失。

以下是通过理论证明为什么这种技术可以在奇异值和压缩损失之间建立一个直接的关系。

根据Lemma 3.1，当截断$S^{-1}X$的$i$-th奇异值获得压缩损失

$\begin{align} L_i &= \|(W-W')X\|_F=\|(W-U\times Trunc(\Sigma)\times V^T\times S^{-1})X\|_F \\ &= \|(WS-U\times Trunc(\Sigma)\times V^T)S^{-1}X\|_F \\ &= \|(U\times \Sigma\times V^T-U\times Trunc(\Sigma)\times V^T)S^{-1}X\| \\ &= \|\sigma_iu_iv_i^TS^{-1}X\|_F \end{align}$

layer-wise closed-form update

随着压缩率的提高，$W$需要截断更多的奇异值。有必要设计一个更新策略来最小化$|WX’-W’X’|_F$

为了更新layer $i$，以及不破坏$W_i’$的低秩结构，SVD-LLM只更新$U_i$而固定$Trunc.(\Sigma)_i, V_i$，有

Experimental Design and Results

Baseline

vanilla SVD, FWSVD, ASVD

Models and Datasets

8个model：LLaMA-7B,13B,30B,65B, LLaMA2-7B, OPT-6.7B, Vivuna-7B, Mistral-7B
10个datasets: 3个language modeling datasets(WikiText-2, PTB, C4) 和 7个 classification datasets(OpenbookQA, WinoGrande, HellaSwag, PIQA, MathQA, ARC-e, ARC-c) in zero-shot setting with LM-Evaluation-Harness framework.

Implementation Details

为了确保公平的比较，我们遵循ASVD[28]随机选择来自WikiText-2的256个样本作为校准数据。由于逐层闭合形式更新旨在缓解较高压缩比下的精度下降，因此我们仅在压缩比为40%及以上时应用它。我们所有的实验都是在Nvidia A100 GPU上进行的。

overall performance

我们从四个方面来进行测试

执行不同的压缩率
执行不同的LLMs
执行更大规模的LLMs
与LoRA fine-tuning一起执行

Comparative Analysis

Discussion and Limitations

Conclusion

为了实现这个技术，SVD-LLM将激活值转变为正交矩阵，激活值变为$S^{-1}X$，此时$(S^{-1}X)(S^{-1}X)^T=I$。其中$S$来自Cholesky分解。我们对$WS$执行SVD来获取$U,\Sigma,V$，最后对奇异值进行截断，得到 $W’=U\times Trunc(\Sigma)\times V^T\times S^{-1}$. 图2(b)展现了本文的效果。当只有一个奇异值被截断是，compression loss等于被截断的奇异值本身。截断多个奇异值的压缩损失等于它们的平方和的平方根。因此，在所提出的感知截断的数据白化技术下，截断最小的奇异值导致最小的压缩损失。

upupwords

Paper-Analysis-SVD-LLM: Truncation-aware Singular Value Decomposition for Large Language Model Compression