Structure optimization: NAS and low-rank factorization
Pruning and quantization keep the shape of the model and change its numbers. This session changes the shape itself, in two ways. Neural architecture search (NAS) looks for a smaller architecture, and we will see why it is so expensive for LLMs. Low-rank factorization replaces each big weight matrix with two thin ones; plain SVD breaks LLMs, while activation-aware versions (ASVD, SVD-LLM) work, and they combine well with quantization.
What you will learn
- What neural architecture search is (search space, search strategy, evaluation), and how supernets with weight sharing made it cheap enough for BERT-size models
- Why NAS is very hard to apply to LLMs, with real cost numbers, and what training-free proxies (LiteTransformerSearch) and hardware-aware search (HAT) change
- Low-rank factorization with the SVD: the Eckart–Young theorem, the parameter count k(m+n), the break-even rank, and when it gives real speed
- Why plain SVD destroys LLMs: weight error is not output error, and activation outliers decide which directions matter
- ASVD (diagonal activation scaling) and SVD-LLM (Cholesky whitening): the formulas, the proof that whitening makes truncation optimal, and the measured perplexities
- How factorization mixes with quantization and pruning: factor then quantize, low-rank error correction (LoRC), low-rank plus sparse (LoSparse), and low-rank KV caches
Why this matters
Quantization stores each weight with fewer bits. Pruning sets some weights to zero. Both keep the shape of the model: the same layers, the same matrices. This session changes the shape. We ask two questions. Is there a smaller architecture that does the same job? And can each big weight matrix be replaced by two thin matrices whose product is almost the same?
The efficient-inference survey (Zhou et al., 2024, section 5.2.3) calls this structure optimization and names two tools for it. [Certain]
- Neural architecture search (NAS): let an algorithm choose the number of layers, the hidden size, the number of heads and so on, under a latency or size limit. NAS gave good small BERT models (NAS-BERT, AutoTinyBERT) and fast translation models (HAT). But it must judge many candidate architectures, and for LLMs even one candidate is expensive. The survey says these techniques are "challenging to apply to LLMs". [Certain]
- Low-rank factorization (LRF): write a weight matrix \(W \in \R^{m \times n}\) as a product \(AB\) of an \(m \times k\) and a \(k \times n\) matrix with a small rank \(k\). Fewer parameters means less memory and, in memory-bound decoding, fewer bytes to read per token. The classic tool is the singular value decomposition (SVD). Applied naively to an LLM, it destroys the model: in the SVD-LLM paper, plain SVD that removes 20% of the parameters of LLaMA-7B raises its WikiText-2 perplexity from 5.68 to 20,061. [Certain] Activation-aware methods remove the same 20% and get 7.73 (SVD-LLM). [Certain]
The ideas connect to many other sessions. The activation-aware view is the same one as in session 114 (Wanda and SparseGPT) and session 106 (GPTQ): what matters is the layer output \(WX\), not the weights alone. Low rank also appears in LoRA (session 57), in MLA's compressed KV cache (session 97), in Linformer (session 98, where the attention matrix, not the weight matrix, is low rank) and in ALBERT's factorized embedding (session 94). SliceGPT in session 115 is a close relative: it projects with PCA and deletes whole rows and columns. After this session, session 119 trains a small model from a big one, which is the other way to get a smaller architecture.
Two ways to change the structure
Think of a transformer as a list of design choices (depth \(L\), width \(d\), FFN size, heads) plus the weights inside each matrix. The two tools work at different levels.
| Neural architecture search | Low-rank factorization | |
|---|---|---|
| What changes | The design choices: layers, width, heads, FFN size, even the type of each block | The inner shape of each linear layer: one \(m \times n\) matrix becomes \(m \times k\) and \(k \times n\) |
| Needs training? | Yes: the new architecture needs weights (from scratch, from a supernet, or by distillation) | No for the basic step (post-training, a small calibration set); a short fine-tune helps |
| Cost for a 7B model | Very high: each serious candidate is a pre-training run | Hours on one GPU (SVD-LLM: about 3.5 h on LLaMA-7B) [Certain] |
| Speed on GPU | Whatever the found architecture gives; dense kernels, no special support | Dense kernels too: two smaller matrix multiplications instead of one |
| Relation to pruning | Structured pruning is a kind of NAS that starts from a trained model | Removing singular values is like pruning in a rotated basis |
Both give dense smaller models. This is their main advantage over unstructured pruning: no sparse format and no special kernel are needed, so the saving is real on every GPU and CPU.
Neural architecture search for transformers
A NAS method has three parts. The search space is the set of allowed architectures. The search strategy decides which candidates to try (random sampling, evolution, reinforcement learning, gradient-based relaxation). The evaluation tells how good a candidate is. Formally, with a latency limit \(T\):
- Read the symbols
- \(\mathcal{A}\)
- the search space: all architectures the method may pick
- \(a\)
- one candidate architecture (for example "12 layers, width 768, 8 heads, FFN 3072")
- \(w^\star(a)\)
- the weights of \(a\) after training; NAS needs them to judge \(a\), and this inner problem is the expensive part
- \(\mathcal{L}_{val}\)
- the validation loss (or minus an accuracy) of the trained candidate
- \(\text{Lat}(a)\), \(T\)
- the measured or predicted latency of \(a\) on the target hardware, and its limit; it can also be a parameter or memory limit
The difficulty is the inner \(\argmin\): every candidate must be trained before it can be judged. If a search judges \(N_a\) candidates, each trained separately, the cost is roughly
The right side is the one-shot (weight-sharing) idea: train one big supernet once, whose sub-networks are the candidates and share its weights. Then judging a candidate means cutting it out of the supernet and evaluating it, with no training. \(C_{eval}\) is a forward pass over a validation set, millions of times cheaper than \(C_{train}\).
How expensive it was: the Evolved Transformer
The Evolved Transformer (So, Liang and Le, 2019) searched transformer blocks with evolution and trained many candidates for real. Strubell et al. (2019) estimated the cost of that search, for the big model, at 274,120 hours on 8-GPU P100 machines, about 626,155 lbs of CO₂ and USD 942,973 to 3,201,722 of cloud compute. [Certain, as the paper's estimate] That was for a translation model of about 200 million parameters. [Likely] HAT (Hardware-Aware Transformers, Wang et al., 2020) used a weight-sharing supernet and reports a 12,041 times lower search cost than the Evolved Transformer, and models 3 times faster and 3.7 times smaller than the base Transformer on a Raspberry Pi 4, with no loss of quality. [Certain]
NAS-BERT: a supernet for compressing BERT
NAS-BERT (Xu et al., 2021) is the NAS paper cited by the survey. Its goal: from one search, get many compressed BERT models of different sizes (5M to 60M parameters) that work for any downstream task. [Certain]
- Search space. A chain of 24 layers. Each layer picks one of 26 operations: multi-head attention with 2 to 8 heads, a feed-forward network with inner size 512 to 2048, a separable convolution with kernel 3, 5 or 7, or identity (skip the layer), in hidden sizes 128 to 512. That is \(26^{24} \approx 9.1 \times 10^{33}\) paths. [Certain for the space; the number is \(26^{24}\)]
- Block-wise training. The supernet is cut into 4 blocks of 6 layers. Each block is trained to imitate the matching block of a trained BERT-base (knowledge distillation on the hidden states), so the blocks can be trained separately. [Certain]
- Progressive shrinking. Architectures are grouped into 10 size bins. Each epoch samples 2,000 per bin, ranks them by validation loss and removes the worse half, until 10 remain per bin. [Certain]
- Performance approximation. The latency of a model is the sum of per-operation latencies from a lookup table measured on the device, and its loss is approximated by the sum of the block-wise distillation losses. [Certain]
Training the supernet took about 3 days on 32 NVIDIA P40 GPUs. [Certain] The 60M model reached an average GLUE dev score of 84.2 against 83.5 for a hand-designed BERT of the same size with distillation, with a 2.2× speed-up over BERT-base. [Certain] AutoTinyBERT (Yin et al., 2021) does a similar one-shot search over the hyper-parameters of tiny pre-trained models and selects sub-models with an evolutionary algorithm. [Certain]
- input: search space \(\mathcal{A}\), latency limit \(T\), target device
- build a supernet that contains every \(a \in \mathcal{A}\) as a sub-network (shared weights)
- repeat for many steps: sample a sub-network \(a\), train its weights on one batch // optionally distill from a teacher
- measure each operation on the device once; \(\text{Lat}(a) \approx \sum_{op \in a} \text{lat}(op)\) // lookup table
- population \(\leftarrow\) random architectures with \(\text{Lat}(a) \le T\)
- repeat for G generations: // evolutionary search
- score each \(a\) with the supernet weights on a small validation set // no training
- keep the best; create children by mutation (change one choice) and crossover; drop children with \(\text{Lat} \gt T\)
- \(a^\star \leftarrow\) best of the final population
- train \(a^\star\) further (from the supernet weights or from scratch, often with distillation) // the final model
Why NAS is costly for LLMs
Each step that makes NAS cheap for BERT gets harder at LLM scale.
- The supernet is itself an LLM pre-training run. A supernet that contains 7B-size candidates has at least 7B parameters and must see a large share of the trillions of tokens a real LLM sees. Its cost is like training the biggest candidate, or more. [Likely]
- Shared weights rank candidates badly. A sub-network cut out of a supernet is not as good as the same architecture trained alone, and the ranking of candidates by supernet score can differ from their real ranking. This "ranking gap" is a known problem of one-shot NAS. [Likely] For LLMs, small differences in loss matter, so a noisy ranking is a real problem.
- Short training does not predict long training. NAS evaluates after little training, but which shape wins can change with the amount of data. [Likely]
- The search space is already understood. session 35 show that, inside a wide range of shapes, the loss depends mainly on the parameter count and the data, and only weakly on depth or width. [Likely] So there is less to gain from searching, and more from choosing the size well.
LiteTransformerSearch (LTS, Javaheripi et al., 2022) uses the last point. It found that, for autoregressive transformers, the number of decoder parameters has a high rank correlation with the perplexity after training, across many shapes. So LTS uses the parameter count as a training-free proxy for the loss and measures only the latency and memory on the device. It finds a Pareto front in under 3 hours on a laptop, with no GPU. [Certain] The survey also lists AutoDistil (few-shot, task-agnostic NAS) and NAS-based structured pruning. [Certain] In practice, today's LLM families pick their shapes with scaling-law fits and small ablations, not with NAS. [Likely]
Figure 1 shows the core of hardware-aware NAS on a toy space of 144 decoder shapes. The loss is a proxy (the Chinchilla scaling-law fit for the parameter count, as if each shape were trained compute-optimally), so, as in LTS, the shape matters only through its size. The latency is a simple model of decoding one token: read all FP16 weights, plus a fixed cost per layer for kernel launches.
How to read Figure 1
Each circle is one architecture. Filled circles fit the latency budget (the shaded area left of the dashed line). The orange line is the Pareto front: no other architecture is both faster and better. The ringed point is the best architecture inside the budget. On the GPU, the fixed per-layer cost is large compared with reading the weights, so deep models are slow: the front first makes the model wider and adds depth only when the width is at its maximum (2048). Switch to the edge CPU: there, reading the weights dominates, latency follows the parameter count, and many shapes have almost the same speed. The same search space gives different answers on different hardware; that is the point of hardware-aware NAS. The readout also shows how many times the cost of the largest model it would take to train every candidate.
Read the last line of the readout: even in this tiny space, training all 144 candidates compute-optimally costs about 10 times the training of the largest one (each run costs about \(6 N D = 120 N^2\) FLOPs with \(D = 20N\)). For a real LLM, that factor is in units of full pre-training runs. That is the cost problem in one number.
Low-rank factorization with the SVD
Every matrix \(W \in \R^{m \times n}\) has a singular value decomposition \(W = U \Sigma V^\top\). The columns of \(U\) (\(m\)-dimensional) and \(V\) (\(n\)-dimensional) are orthonormal directions, and \(\Sigma\) is diagonal with the singular values \(\sigma_1 \ge \sigma_2 \ge \dots \ge 0\). So \(W = \sum_i \sigma_i \mathbf{u}_i \mathbf{v}_i^\top\): a sum of rank-1 pieces, sorted by size. Keep the first \(k\) pieces and drop the rest:
- Read the symbols
- \(U_k, V_k\)
- the first \(k\) columns of \(U\) and \(V\): the \(k\) most important output and input directions
- \(\Sigma_k\)
- the diagonal matrix of the \(k\) largest singular values
- \(A, B\)
- the two factors that are stored; splitting \(\Sigma_k\) as \(\Sigma_k^{1/2}\Sigma_k^{1/2}\) gives both factors a similar scale, which helps if they are quantized later (ASVD paper) [Certain]
- \(k\)
- the rank: the width of the "bottleneck" between \(B\) and \(A\)
The layer \(\mathbf{y} = W\mathbf{x}\) becomes \(\mathbf{y} = A(B\mathbf{x})\): first project the input down to \(k\) numbers, then back up. Storage and compute go from \(mn\) to \(k(m+n)\). The parameter ratio and the break-even rank are
For a square matrix, \(k_{be} = n/2\): a rank-\(n/2\) factorization of a \(4096 \times 4096\) matrix saves nothing, even though it throws away half of the singular values. To remove 20% of the parameters of a \(4096 \times 4096\) projection, the rank must be \(0.8 \cdot 4096^2 / 8192 \approx 1638\), so 60% of the 4096 directions are dropped. This is the first reason low-rank compression of LLMs is hard: small savings already need deep cuts in rank.
Which rank-\(k\) matrix is closest to \(W\)? The Eckart–Young theorem (1936) answers it: the truncated SVD, and the error is set by the dropped singular values. [Certain]
So the shape of the spectrum decides everything. If the \(\sigma_i\) fall fast, a small rank keeps almost all of \(W\). If they fall slowly, no small rank is good. Figure 2 compares three spectra of a \(64 \times 64\) matrix.
How to read Figure 2
Purple bars are kept, grey bars are dropped. The orange curve rises to 100% of the energy \(\sum \sigma_i^2\). The dashed line at \(k = 32\) is the break-even rank: right of it, the two factors are larger than \(W\). With "Fast decay", rank 15 already gives 10% error and saves 53% of the parameters. With "Random", 10% error needs rank 50, which is far past break-even: such a matrix cannot be compressed by SVD at all. Trained LLM weight matrices are much closer to the random and slow cases than to the fast one, which is why plain SVD fails on them. [Likely]
LLaMA-2-7B has \(d = 4096\), FFN size 11,008 and 32 layers. Each layer has 4 attention projections of \(4096 \times 4096\) and 3 FFN matrices of \(4096 \times 11{,}008\), so the linear layers hold \(32 \times (4 \cdot 4096^2 + 3 \cdot 4096 \cdot 11008) = 6.476 \times 10^9\) weights, 12.95 GB in FP16.
Break-even ranks. Square projections: \(4096^2 / 8192 = 2048\). FFN matrices: \(4096 \cdot 11008 / 15104 \approx 2985\).
20% fewer parameters (\(\rho = 0.8\)): rank 1638 for the projections and \(0.8 \cdot 2985.2 \approx 2388\) for the FFN matrices. 40% fewer (\(\rho = 0.6\)): ranks 1229 and 1791.
Memory and speed. At \(\rho = 0.6\) the linear layers need \(0.6 \times 12.95 = 7.77\) GB. In batch-1 decoding, which reads all weights for every token, the upper limit of the speed-up of these layers is \(1/\rho = 1.67\times\). The real gain is lower: two smaller matrix multiplications have more launch overhead, and attention and the KV cache are not touched.
When does factorization give real speed?
Per token, \(W\mathbf{x}\) costs \(2mn\) FLOPs and \(A(B\mathbf{x})\) costs \(2k(m+n)\), the same ratio \(\rho\). The weights read from memory also shrink by \(\rho\). So unlike unstructured sparsity, the saving is real on any hardware with dense kernels. Three things reduce it in practice:
- Two kernels instead of one. At small batch, kernel launch and synchronization costs add up (the per-layer cost in Figure 1). [Likely]
- Awkward ranks. Tensor cores are fastest when matrix sizes are multiples of 64 or 128. A rank of 1638 should be rounded to 1664 or 1600. [Likely]
- Prefill is compute-bound with large tiles. The FLOP saving is the same, but thin \(k\) dimensions use the hardware less well. [Likely]
Why plain SVD fails on LLMs
Formula (118.5) minimizes the error of the weights. But we care about the error of the outputs on real inputs. Stack calibration inputs of the layer as columns of \(X \in \R^{n \times N}\) (one column per token). The right objective is the one used by GPTQ, SparseGPT and Wanda:
The two objectives differ when the inputs are not uniform. LLMs have outlier features: a few input channels whose values are 10 to 100 times larger than the others (session 107). A small piece of \(W\) that touches an outlier channel can carry a large part of the output. Plain SVD ranks directions by \(\sigma_i\) of \(W\) alone, does not see the inputs, and may drop exactly those directions.
Take \(W = \operatorname{diag}(2, 1)\) and rank \(k = 1\). Input channel 1 has root-mean-square value 1, channel 2 has 5, and they are uncorrelated. Per token, the output energy is \(2^2 \cdot 1 + 1^2 \cdot 25 = 29\).
Plain SVD keeps the larger singular value, \(\sigma = 2\) on channel 1, and drops channel 2. Weight error \(= 1\). Output error energy \(= 1^2 \cdot 25 = 25\): 86.2% of the output is lost.
Activation-aware: first scale each input direction by its size, \(WS = \operatorname{diag}(2 \cdot 1,\ 1 \cdot 5) = \operatorname{diag}(2, 5)\). Now channel 2 has the larger singular value and is kept. Weight error \(= 2\), larger. Output error energy \(= 2^2 \cdot 1 = 4\): only 13.8% is lost. The method with the larger weight error has 6 times less output error.
ASVD: scale by the activations, then factor
ASVD (Yuan et al., 2023) puts this idea into a formula. It inserts a diagonal scaling \(S\) and its inverse, which changes nothing, factors the scaled matrix and moves \(S^{-1}\) into the right factor: [Certain]
- Read the symbols
- \(s_j\)
- the scale of input channel \(j\): its mean absolute value over the \(N\) calibration tokens, to the power \(\alpha\)
- \(\alpha\)
- how strongly to follow the activations; the paper uses \(\alpha = 0.5\). The mean worked better than the maximum. [Certain]
- \([WS]_k\)
- the rank-\(k\) truncated SVD of the scaled matrix, \(U_k \Sigma_k V_k^\top\)
- \(W'\)
- the compressed layer, stored as \(A = U_k\Sigma_k^{1/2}\) and \(B = \Sigma_k^{1/2} V_k^\top S^{-1}\)
Channels with large activations are made "louder" before the SVD, so their directions get larger singular values and survive the truncation. This is the same trick as AWQ's per-channel scaling (session 107) and it is the diagonal approximation to the exact answer below, just as Wanda is a diagonal SparseGPT.
Different layers, different ranks
The second idea of ASVD is that layers differ in how much rank they can lose. Sensitivity-based truncation rank searching (STRS) measures it directly. For each linear layer and each candidate parameter ratio in \(\{0.1, 0.2, \dots, 0.9\}\), it compresses only that layer and records the perplexity on the calibration set. Then a binary search over these sensitivities picks a ratio for each layer so that the whole model meets the target. [Certain for the measurements; the details of the search are in the paper] The calibration set is small: 32 sequences of 2,048 tokens from WikiText. [Certain] The paper reports that ASVD can remove about 10% to 30% of the parameters, and that the same idea applied to the key and value projections shrinks the KV cache (below). [Certain]
SVD-LLM: whitening makes truncation optimal
ASVD's diagonal \(S\) ignores correlations between input channels. SVD-LLM (Wang et al., 2024) uses a full matrix: the Cholesky factor of the input second-moment matrix. [Certain]
- Read the symbols
- \(S\)
- lower triangular, from the Cholesky decomposition of \(XX^\top\) (\(n \times n\), summed over all calibration tokens)
- \(\sigma_i\)
- the singular values of the whitened matrix \(WS\), not of \(W\)
- \(W'\)
- stored as two factors, \(U_k \Sigma_k^{1/2}\) and \(\Sigma_k^{1/2} V_k^\top S^{-1}\)
- last equality
- the paper's theorem: the output loss is exactly given by the dropped singular values of \(WS\), so "drop the smallest" is the right rule [Certain]
Why is the last equality true? Write \(X = S (S^{-1} X)\). The matrix \(Q = S^{-1}X\) has orthonormal rows, because \(QQ^\top = S^{-1} XX^\top S^{-\top} = S^{-1} S S^\top S^{-\top} = I\). Multiplying by a matrix with orthonormal rows from the right does not change the Frobenius norm, so for any \(W'\):
Problem (118.6) in \(W'\) is now an ordinary low-rank problem in \(M = W'S\): find the rank-\(k\) \(M\) closest to \(WS\). By Eckart–Young (118.5), it is the truncated SVD of \(WS\), and \(W' = M S^{-1}\). So SVD-LLM's truncation is the exact optimum of (118.6) when \(XX^\top\) is invertible. [Certain, linear algebra] A tiny dampening \(\lambda I\) added to \(XX^\top\) keeps it invertible, as in GPTQ. The ASVD paper also has a variant, ASVD+, that uses this Cholesky factor. [Certain]
- input: model, calibration set (256 sequences from WikiText-2 in the paper), target parameter ratio \(\rho\)
- for each transformer block, in order:
- run the calibration tokens through the block; for each linear layer accumulate \(H \leftarrow H + X X^\top\) // \(n \times n\), never store \(X\)
- for each linear layer \(W \in \R^{m \times n}\):
- \(S \leftarrow \operatorname{Cholesky}(H + \lambda I)\) // formula (118.8)
- \(U, \Sigma, V \leftarrow \operatorname{SVD}(W S)\); \(k \leftarrow \lfloor \rho\, m n / (m+n) \rfloor\) // formula (118.4)
- \(A \leftarrow U_k \Sigma_k^{1/2}\), \(B \leftarrow \Sigma_k^{1/2} V_k^\top S^{-1}\); replace the layer by \(\mathbf{x} \mapsto A(B\mathbf{x})\)
- feed the outputs of the compressed block to the next block
- optional: recover with LoRA on the factors: first train an adapter on \(A\) with \(B\) frozen, then on \(B\) with \(A\) frozen; merge // keeps the rank-\(k\) shape
- return the compressed model
About the last step: the current version of the SVD-LLM paper (v5) updates the two factors with LoRA one after the other, on 50K Alpaca samples, because tuning both at once does not guarantee a lower loss. [Certain] The survey describes an earlier version that used a layer-wise closed-form update instead. [Likely] The table below separates "whitening only" from the full method.
Figure 3 runs all three methods on one small layer (16 outputs, 24 inputs, 192 calibration tokens). Inputs 3 and 17 are outlier channels whose size you control, and inputs 5 and 6 are correlated.
How to read Figure 3
At the default (rank 6, outliers 10× larger), plain SVD loses about a third of the output (0.337), ASVD 0.032 and SVD-LLM 0.028. Select SVD-LLM and look left: whitening makes the spectrum fall fast, because the outlier channels now produce a few dominant directions; this is why a small rank works. Move the outlier size to 1: all inputs are similar, the three methods are close, and none is good at rank 6 (about 0.26 to 0.27), because a random matrix has a flat spectrum. SVD-LLM is never worse than the others: it is the exact optimum of (118.6) for every rank.
What the papers measured
Both papers use WikiText-2 perplexity on LLaMA-7B (dense: 5.68). ASVD reports by the parameter ratio kept; SVD-LLM by the fraction of parameters removed. [Certain]
| ASVD paper (kept ratio) | 0.95 | 0.90 | 0.85 | 0.80 |
|---|---|---|---|---|
| Plain SVD | 2800 | not reported | ||
| FWSVD + STRS (Fisher-weighted, needs gradients) | 5.86 | 6.32 | 7.48 | 10.70 |
| ASVD | 5.78 | 6.09 | 6.80 | 8.89 |
| SVD-LLM paper (removed) | 20% | 40% | 60% | 80% |
|---|---|---|---|---|
| Plain SVD | 20061 | 52489 | 105474 | 687291 |
| FWSVD | 1727 | 18156 | 32194 | 96872 |
| ASVD | 11.14 | 1407 | 57057 | 80425 |
| SVD-LLM, whitening only | 7.94 | 13.73 | 66.62 | 1349 |
| SVD-LLM (with the LoRA update) | 7.73 | 9.27 | 15.00 | 31.79 |
Four lessons. (1) Plain SVD is useless on LLMs at any ratio. (2) Activation awareness is what makes factorization work. (3) Whitening is clearly better than diagonal scaling at the same ratio: 7.94 against 11.14 at 20% in the SVD-LLM paper. (4) Even the best method loses a lot at 40% and more; at 20% removed, SVD-LLM's 7.73 is still worse than 50% unstructured pruning with Wanda (7.26, previous session) or 4-bit GPTQ on the same model. [Likely for the GPTQ comparison] Note also that the two papers measure ASVD at a similar point differently (8.89 at kept 0.80 against 11.14 at 20% removed): setups, rank allocation and calibration differ. Compare methods inside one paper. The SVD-LLM paper's compression of LLaMA-7B at 20% took about 3.5 hours, against 5.5 hours for ASVD. [Certain]
How to read Figure 4
In the ASVD view, all bars are near the dense line until 0.85, then grow. Switch to the SVD-LLM view: the grey (SVD) and green (FWSVD) bars are thousands or more at every ratio; only SVD-LLM stays below 32 even at 80% removed. Hover a bar to see its exact value.
Mixing factorization with quantization and pruning
Factorization changes the shape; quantization changes the bits; pruning adds zeros. They act on different things, so they can be stacked. Four patterns appear in the papers.
1. Factor, then quantize the factors
The factors \(A\) and \(B\) are ordinary dense matrices, so any weight quantizer can be applied to them. With \(b\)-bit factors, ignoring scales:
ASVD tested this on LLaMA-2-7B: at kept ratio 0.9, FP16 gives 5.93 and INT8 (RTN) 5.94, so 8 bits cost nothing; NF4 gives 6.2. [Certain] SVD-LLM went further: remove 40%, then quantize to 2 bits with QuIP#. The result, 9.83 perplexity at 1.3 GB of weights, is better than the trained 1-bit method OneBit (10.20 at 1.3 GB) and much better than post-training binarization (BiLLM, 47.67 at 1.5 GB). [Certain] Balancing \(\Sigma^{1/2}\) between the two factors matters here: ASVD's ablation on OPT-125m at INT6 gives 37.58 when \(\Sigma\) is split, against 39.67 and 40.62 when it is put into one factor only. [Certain]
2. Quantize, then fix the error with a low-rank term (LoRC)
ZeroQuant-V2 (Yao et al., 2023) turns the order around. Quantize \(W\) to \(\hat W = Q(W)\), compute the error \(E = W - \hat W\), and add back its best rank-\(r\) approximation: [Certain]
A tiny rank is enough: the paper finds gains flatten after \(r = 4\) to 8, the factors can be stored in INT8, and for a standard transformer the extra parameters are about \(3r/(2h)\) of the model (\(h\) = hidden size), at most about 1.6% for \(r = 8\), \(h \ge 768\). [Certain] Low-rank correction helps only as far as the error \(E\) has structure; pure rounding noise has a flat spectrum. The same idea, a quantized base plus a low-rank term, is used by LoftQ for fine-tuning (session 111).
3. Low rank plus sparse (LoSparse)
LoSparse (Li et al., 2023) writes each matrix as a low-rank part plus a sparse part, \(W \approx AB + S_{sp}\). [Certain] The low-rank part captures the shared, "smooth" structure; the sparse part keeps the few large individual entries that a low rank cannot express. Pruning alone may remove neurons that carry such shared structure; the low-rank part protects it. [Certain, as the paper's motivation] The survey also lists DSFormer (a sparse matrix times a small dense matrix) and LPLR (joint low-rank and low-precision factors). [Certain]
4. Low-rank KV cache
If the key projection is factored, \(W_K = AB\), the model can cache the \(k\)-dimensional vector \(\mathbf{c}_t = B\mathbf{x}_t\) instead of the \(d\)-dimensional key \(A\mathbf{c}_t\):
The product \(A^\top\mathbf{q}\) is computed once per step, so the cached keys never need to be expanded. This is the "weight absorption" trick of MLA (session 97), applied after training. ASVD applies it to LLaMA-2-7B: at a KV-cache ratio of 0.5 the WikiText-2 perplexity moves from 5.47 to 5.67, and at 0.6 to 5.55. [Certain]
Use Figure 5 to compare the memory of patterns 1 and 2 on LLaMA-2-7B shapes.
How to read Figure 5
Default: remove 40% (\(\rho = 0.6\)) and store the factors in 4 bits: 2.4 bits per original weight, 1.94 GB instead of 12.95 GB. Switch to "Quantize + LoRC": at 4 bits and rank 8, the correction adds only 0.31% parameters, so the memory is almost that of plain 4-bit quantization (4.02 bits per weight). The two patterns spend memory in different places: pattern 1 trades rank for bits; pattern 2 spends a little memory to repair the quantizer.
When to factor at all? With today's methods, 4-bit quantization of a 7B model usually loses less than removing 20% of its parameters by SVD, at a 4 times smaller size. [Likely] Factorization is most useful as an extra axis on top of quantization, at very low memory budgets (the 2-bit result above), or to shrink the KV cache. LoRD (Kaushal et al., 2023) shows a good case: the linear layers of a 16B code model (StarCoder) can lose rank so that the model shrinks to 13.2B with no drop in HumanEval pass@1, or to 12.3B with a small drop, in under 10 minutes on one A100. [Certain]
Low-rank compression in PyTorch
The code builds one layer of \(384 \times 512\) random weights (a flat spectrum, like many LLM weights), with 4,096 calibration tokens, 8 outlier channels and one correlated pair. It compresses the layer to \(\rho \approx 0.6\) with plain SVD, ASVD and SVD-LLM, checks the theorem (118.8) numerically, and wraps the factors in a module. It runs on CPU in about 1 second; we ran it with PyTorch 2.8.
import torch torch.manual_seed(0) torch.set_default_dtype(torch.float64) d_out, d_in, n_tok = 384, 512, 4096 W = torch.randn(d_out, d_in) / d_in ** 0.5 # flat spectrum, like many LLM weights X = torch.randn(d_in, n_tok) X[torch.randperm(d_in)[:8]] *= 20.0 # 8 outlier input channels X[1] = 0.9 * X[0] + 0.1 * X[1] # two correlated channels def rel_err(Wp): return ((W @ X - Wp @ X).norm() ** 2 / (W @ X).norm() ** 2).item() def rank_for(ratio, m, n): # rank k so that k(m+n) = ratio * m * n (formula 118.4) return int(ratio * m * n / (m + n)) def svd_trunc(M, k): U, S, Vh = torch.linalg.svd(M, full_matrices=False) A = U[:, :k] * S[:k].sqrt() # split Sigma evenly (ASVD trick) B = S[:k].sqrt()[:, None] * Vh[:k] return A, B, S def plain_svd(W, X, k): A, B, _ = svd_trunc(W, k) return A, B def asvd(W, X, k, alpha=0.5): s = X.abs().mean(dim=1) ** alpha # formula (118.7) A, B, _ = svd_trunc(W * s[None, :], k) return A, B / s[None, :] # fold S^-1 into the right factor def svd_llm(W, X, k): H = X @ X.T H += 1e-6 * H.diagonal().mean() * torch.eye(H.shape[0]) S = torch.linalg.cholesky(H) # S S^T = X X^T (formula 118.8) A, B, sig = svd_trunc(W @ S, k) B = B @ torch.linalg.inv(S) # W' = A B S^-1 return A, B, sig ratio = 0.6 k = rank_for(ratio, d_out, d_in) print(f"rank k = {k}, params {k * (d_out + d_in)} vs {d_out * d_in}") for name, f in [("svd", plain_svd), ("asvd", asvd), ("svd_llm", svd_llm)]: A, B = f(W, X, k)[:2] print(f"{name:8s} relative output error: {rel_err(A @ B):.4f}") # Theorem check: the output loss of SVD-LLM equals the dropped singular values of W S A, B, sig = svd_llm(W, X, k) loss = (W @ X - A @ B @ X).norm().item() print(f"loss {loss:.2f} sqrt(sum of dropped sigma^2) {sig[k:].pow(2).sum().sqrt().item():.2f}") class FactorizedLinear(torch.nn.Module): """y = A (B x): two small matmuls instead of one big one.""" def __init__(self, A, B): super().__init__() self.B = torch.nn.Linear(B.shape[1], B.shape[0], bias=False) self.A = torch.nn.Linear(A.shape[1], A.shape[0], bias=False) self.B.weight.data.copy_(B); self.A.weight.data.copy_(A) def forward(self, x): return self.A(self.B(x)) layer = FactorizedLinear(A, B) x = X[:, :5].T print("max diff to A@B:", (layer(x) - x @ (A @ B).T).abs().max().item() < 1e-9, " params:", sum(p.numel() for p in layer.parameters())) # Output (PyTorch 2.8, CPU): # rank k = 131, params 117376 vs 196608 # svd relative output error: 0.3240 # asvd relative output error: 0.0466 # svd_llm relative output error: 0.0428 # loss 677.70 sqrt(sum of dropped sigma^2) 677.70 # max diff to A@B: True params: 117376
The pattern matches the paper tables: plain SVD loses a third of the output, the activation-aware methods lose about 4 to 5%, and SVD-LLM is the best because it also uses the correlation between channels 1 and 2. The theorem check prints the same number twice (the tiny dampening makes the last digits differ slightly). In a real model, run this per linear layer on the inputs collected with forward hooks, block by block, and replace each nn.Linear by a FactorizedLinear.
Where this is used
| Setting | Typical use | Why |
|---|---|---|
| Small BERT-size encoders for search and classification | One-shot NAS (NAS-BERT, AutoTinyBERT) with distillation from a large teacher | Many sizes from one search; the candidates are small enough to train |
| On-device translation and speech | Hardware-aware NAS (HAT) with a latency table of the target phone or board | The best shape depends on the hardware (Figure 1) |
| Choosing a new LLM family's shapes | Scaling-law fits and small ablations; training-free proxies (LTS) for edge variants [Likely] | Full NAS at LLM scale is too costly |
| Extra compression on top of 2- to 4-bit quantization | SVD-LLM or ASVD, then quantize the factors | A further 20% to 40% fewer parameters with dense kernels |
| Repairing low-bit quantization | LoRC: rank 4 to 8 correction of the quantization error | About 0.3% extra parameters on LLaMA-2-7B shapes |
| Long-context serving | Low-rank K/V projections with a \(k\)-dimensional cache (ASVD, MLA-style absorption) | The KV cache, not the weights, dominates memory at long context |
| Video-LLMs and Video-RAG | Factorize the language model, or the K/V projections, of a VLM that reads many frame tokens | Thousands of visual tokens per clip make the KV cache very large |
| Video classification and action recognition on edge devices | NAS over video transformer depth/width, or SVD of the backbone's FFN layers with in-domain calibration clips | Latency budgets per frame are strict; activation-aware SVD uses real video token statistics |
| Video fingerprinting and retrieval | Low-rank projection heads (a learned \(k\)-dimensional embedding) [Likely] | Smaller vectors mean cheaper storage and nearest-neighbor search |
Common mistakes
- Forgetting the break-even rank. A rank-\(k\) factorization of an \(m \times n\) matrix saves memory only if \(k \lt mn/(m+n)\); for a square matrix that is half its size. "Rank 3000 of a \(4096 \times 4096\) matrix" is larger than the original.
- Minimizing the weight error. Plain SVD minimizes \(\lVert W - W'\rVert\), which ignores outlier channels. Use the output error (118.6): scale (ASVD) or whiten (SVD-LLM) with calibration data.
- Using the same rank for every layer. Layers have very different sensitivity; allocate ranks per layer (ASVD's STRS) and keep sensitive layers less compressed.
- Calibrating every layer on the dense model's inputs. Process blocks in order and feed each block the outputs of the already compressed blocks, as in GPTQ and SparseGPT.
- Putting all of \(\Sigma\) into one factor before quantizing. Split \(\Sigma^{1/2}\) between \(A\) and \(B\) so both have similar ranges.
- Comparing perplexities across papers. ASVD at a similar ratio is 8.89 in its own paper and 11.14 in the SVD-LLM paper. Compare methods inside one setup.
- Expecting the full \(1/\rho\) speed-up. Two kernels, awkward ranks and untouched attention reduce it; round \(k\) to a multiple of 64 or 128 and measure.
- Trusting supernet scores as final. In one-shot NAS, a sub-network's supernet score is only an estimate; retrain or fine-tune the chosen architecture and check its real accuracy.
Interview questions
How many parameters does a rank-\(k\) factorization of an \(m \times n\) matrix have, and when does it save memory?basic
State the Eckart–Young theorem and explain what it does not tell you for LLMs.basic
Why does plain SVD fail on LLM weights?core
Derive the SVD-LLM truncation and prove it is optimal for the output error.advanced
How is ASVD related to SVD-LLM? Compare with Wanda and SparseGPT.core
Why is NAS rarely used to design LLMs?core
What is a supernet, and what are the main tricks NAS-BERT uses?advanced
Does low-rank factorization give real speed on a GPU? When does it not?core
How can factorization be combined with quantization? Give two designs.core
How can a low-rank key projection shrink the KV cache without slowing attention?advanced
You have a 7B model and must fit it in 2 GB of weight memory. How do you think about pruning, quantization and factorization?advanced
Exercises
- What rank \(k\) of a \(4096 \times 11{,}008\) FFN matrix removes 50% of its parameters? Check your answer.
- A matrix has singular values \((4, 2, 1, 1)\). What is the relative Frobenius error of the best rank-2 approximation, and how much energy is kept?
- For LLaMA-2-7B shapes, how many extra parameters (in %) does LoRC with rank 8 add to the linear layers? How many bits per weight does 4-bit quantization plus INT8 correction factors cost?
- Remove 40% of the parameters of the linear layers of LLaMA-2-7B by factorization, then store the factors in 2 bits. How many GB do these layers need?
- Repeat the second worked example with input sizes 1 and 3 instead of 1 and 5. Which channel does each method keep, and what fraction of the output energy does each lose?
- HAT reports a search cost 12,041 times lower than the Evolved Transformer. Using the estimate of 274,120 machine-hours, how many machine-hours is that?
Answerscheck
Key takeaways
- Structure optimization changes the shape of the model: NAS changes the architecture, low-rank factorization changes each matrix into two thin ones. Both give dense, smaller models that run fast without special kernels.
- NAS (118.1) needs trained weights to judge each candidate (118.2). Supernets made it practical for BERT-size models (NAS-BERT, HAT: 12,041× cheaper search), but for LLMs the supernet is a pre-training run and the ranking is noisy; LLM shapes come from scaling laws, and training-free proxies (LTS) serve edge models.
- A rank-\(k\) factorization stores \(k(m+n)\) numbers (118.4) and saves memory only below \(k = mn/(m+n)\); Eckart–Young (118.5) gives the best weight approximation.
- Plain SVD fails on LLMs (20,061 perplexity at 20% removed on LLaMA-7B) because weight error is not output error. The right objective is \(\lVert WX - W'X\rVert\) (118.6).
- ASVD scales channels by activation size (118.7) and allocates ranks per layer; SVD-LLM whitens with the Cholesky factor (118.8) and is provably optimal for the output error (118.9): 7.73 at 20% removed.
- Factorization stacks with quantization (\(\rho b\) bits, 118.10; LoRC error correction, 118.11), with sparsity (LoSparse) and with the KV cache (118.12).
Key formulas
References for this session
- Xu et al. (2021). NAS-BERT: Task-Agnostic and Adaptive-Size BERT Compression with Neural Architecture Search
- Yuan et al. (2023). ASVD: Activation-aware Singular Value Decomposition for Compressing Large Language Models
- Wang et al. (2024). SVD-LLM: Truncation-aware Singular Value Decomposition for Large Language Model Compression
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Xu et al. (2021). NAS-BERT: Task-Agnostic and Adaptive-Size BERT Compression with Neural Architecture Search
- Yuan et al. (2023). ASVD: Activation-aware Singular Value Decomposition for Compressing Large Language Models
- Wang et al. (2024). SVD-LLM: Truncation-aware Singular Value Decomposition for Large Language Model Compression
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- Wang, Wu, Liu, Cai, Zhu, Gan and Han (2020). HAT: Hardware-Aware Transformers for Efficient Natural Language Processing
- So, Liang and Le (2019). The Evolved Transformer
- Strubell, Ganesh and McCallum (2019). Energy and Policy Considerations for Deep Learning in NLP
- Yin et al. (2021). AutoTinyBERT: Automatic Hyper-parameter Optimization for Efficient Pre-trained Language Models
- Javaheripi et al. (2022). LiteTransformerSearch: Training-free Neural Architecture Search for Efficient Language Models
- Hsu et al. (2022). Language model compression with weighted low-rank factorization (FWSVD)
- Yao, Wu, Li, Youn and He (2023). ZeroQuant-V2: Exploring Post-training Quantization in LLMs from Comprehensive Study to Low Rank Compensation
- Li et al. (2023). LoSparse: Structured Compression of Large Language Models based on Low-Rank and Sparse Approximation
- Kaushal, Vaidhya and Rish (2023). LORD: Low Rank Decomposition of Monolingual Code LLMs for One-Shot Compression
- Eckart and Young (1936). The approximation of one matrix by another of lower rank (Psychometrika)
- Hoffmann et al. (2022). Training Compute-Optimal Large Language Models
- Tseng et al. (2024). QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks
- Ashkboos et al. (2024). SliceGPT: Compress Large Language Models by Deleting Rows and Columns
- Hu et al. (2021). LoRA: Low-Rank Adaptation of Large Language Models