LLM & VLM courseBlog
118Track 5: LLM inference and serving · session 41 of 65

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.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: IntermediateBefore this: Pruning basics (session 113), Unstructured and 2:4 pruning (session 114), basic linear algebra (matrix rank, SVD)

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 searchLow-rank factorization
What changesThe design choices: layers, width, heads, FFN size, even the type of each blockThe 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 modelVery high: each serious candidate is a pre-training runHours on one GPU (SVD-LLM: about 3.5 h on LLaMA-7B) [Certain]
Speed on GPUWhatever the found architecture gives; dense kernels, no special supportDense kernels too: two smaller matrix multiplications instead of one
Relation to pruningStructured pruning is a kind of NAS that starts from a trained modelRemoving 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\):

\[ a^\star = \argmin_{a \in \mathcal{A}} \; \mathcal{L}_{val}\big(a,\ w^\star(a)\big) \quad \text{s.t.} \quad \text{Lat}(a) \le T, \qquad w^\star(a) = \argmin_{w}\ \mathcal{L}_{train}(a, w) \tag{118.1} \]
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

\[ C_{search} \approx N_a \cdot C_{train}(a) \qquad \text{versus} \qquad C_{one\text{-}shot} \approx C_{supernet} + N_a \cdot C_{eval}(a) \tag{118.2} \]

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]

Algorithm 1: one-shot NAS with a supernet (NAS-BERT, HAT, AutoTinyBERT style)
  1. input: search space \(\mathcal{A}\), latency limit \(T\), target device
  2. build a supernet that contains every \(a \in \mathcal{A}\) as a sub-network (shared weights)
  3. repeat for many steps: sample a sub-network \(a\), train its weights on one batch // optionally distill from a teacher
  4. measure each operation on the device once; \(\text{Lat}(a) \approx \sum_{op \in a} \text{lat}(op)\) // lookup table
  5. population \(\leftarrow\) random architectures with \(\text{Lat}(a) \le T\)
  6. repeat for G generations: // evolutionary search
  7.   score each \(a\) with the supernet weights on a small validation set // no training
  8.   keep the best; create children by mutation (change one choice) and crossover; drop children with \(\text{Lat} \gt T\)
  9. \(a^\star \leftarrow\) best of the final population
  10. 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.

inside the budgettoo slowPareto frontbest choice
Figure 1. A toy hardware-aware search. Space: depth 2 to 24 (step 2), width \(d \in \{512, 768, 1024, 1280, 1536, 2048\}\), FFN size \(2d\) or \(4d\); non-embedding parameters \(N = L d^2 (4 + 2r)\). Proxy loss: \(1.69 + 406.4/N^{0.34} + 410.7/(20N)^{0.28}\) (the Chinchilla fit). Latency per token: \(2N\) bytes divided by the bandwidth, plus a fixed time per layer. The hardware numbers are assumptions for illustration, not measurements. Larger circles are deeper models.
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:

\[ W \approx W_k = U_k \Sigma_k V_k^\top = A B, \qquad A = U_k \Sigma_k^{1/2} \in \R^{m \times k}, \quad B = \Sigma_k^{1/2} V_k^\top \in \R^{k \times n} \tag{118.3} \]
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

\[ \rho = \frac{k\,(m+n)}{m\,n}, \qquad \rho \lt 1 \iff k \lt k_{be} = \frac{m\,n}{m+n} \tag{118.4} \]

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]

\[ \min_{\operatorname{rank}(W') \le k} \lVert W - W' \rVert_F = \lVert W - W_k \rVert_F = \sqrt{\textstyle\sum_{i \gt k} \sigma_i^2} \tag{118.5} \]

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.

kept \(\sigma_i\)dropped \(\sigma_i\)cumulative energy \(\sum_{j \le i}\sigma_j^2\)
Figure 2. Singular values of a \(64 \times 64\) matrix and the error of the best rank-\(k\) approximation (formula 118.5). "Random" is the exact spectrum of a seeded Gaussian matrix, computed in your browser with a Jacobi SVD. The two other profiles are formulas, chosen for illustration.
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]

Worked example: ranks and memory for LLaMA-2-7B shapes

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:

\[ \min_{\operatorname{rank}(W') \le k} \; \big\lVert W X - W' X \big\rVert_F \tag{118.6} \]

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.

Worked example: weight error is not output error

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]

\[ W = (W S)\, S^{-1}, \qquad S = \operatorname{diag}(s_1, \dots, s_n), \quad s_j = \Big(\frac{1}{N}\sum_{t=1}^{N} |x_{jt}|\Big)^{\alpha}, \qquad W' = \big[\,WS\,\big]_k\, S^{-1} \tag{118.7} \]
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]

\[ S S^\top = X X^\top, \qquad W S = U \Sigma V^\top, \qquad W' = U_k \Sigma_k V_k^\top S^{-1}, \qquad \lVert W X - W' X \rVert_F = \sqrt{\textstyle\sum_{i \gt k} \sigma_i^2} \tag{118.8} \]
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'\):

\[ \lVert (W - W') X \rVert_F = \lVert (W - W') S\, Q \rVert_F = \lVert W S - W' S \rVert_F \tag{118.9} \]

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]

Algorithm 2: SVD-LLM style compression of a model (whitening + truncation)
  1. input: model, calibration set (256 sequences from WikiText-2 in the paper), target parameter ratio \(\rho\)
  2. for each transformer block, in order:
  3.   run the calibration tokens through the block; for each linear layer accumulate \(H \leftarrow H + X X^\top\) // \(n \times n\), never store \(X\)
  4.   for each linear layer \(W \in \R^{m \times n}\):
  5.     \(S \leftarrow \operatorname{Cholesky}(H + \lambda I)\) // formula (118.8)
  6.     \(U, \Sigma, V \leftarrow \operatorname{SVD}(W S)\); \(k \leftarrow \lfloor \rho\, m n / (m+n) \rfloor\) // formula (118.4)
  7.     \(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})\)
  8.   feed the outputs of the compressed block to the next block
  9. 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
  10. 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.

Figure 3. Plain SVD, ASVD (formula 118.7, \(\alpha = 0.5\)) and SVD-LLM (formula 118.8) on a \(16 \times 24\) random layer. Left: the singular values of the matrix the selected method truncates (\(W\), or \(WS\)). Right: the relative output error \(\lVert WX - W'X\rVert^2/\lVert WX\rVert^2\) of all three. Fixed seed; everything is computed in your browser.
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.950.900.850.80
Plain SVD2800not reported
FWSVD + STRS (Fisher-weighted, needs gradients)5.866.327.4810.70
ASVD5.786.096.808.89
SVD-LLM paper (removed)20%40%60%80%
Plain SVD2006152489105474687291
FWSVD1727181563219496872
ASVD11.1414075705780425
SVD-LLM, whitening only7.9413.7366.621349
SVD-LLM (with the LoRA update)7.739.2715.0031.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]

Figure 4. The two tables above as bars on a log scale. The dashed line is the dense model (5.68). The ASVD view uses a narrow scale (4 to 12); the SVD-LLM view needs six orders of magnitude.
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:

\[ \text{bits per original weight} = \rho \cdot b \tag{118.10} \]

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]

\[ W \approx \hat W + U_r \Sigma_r V_r^\top, \qquad E = W - Q(W), \qquad \text{extra parameters} = \frac{r\,(m+n)}{m\,n} \tag{118.11} \]

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\):

\[ \mathbf{q}^\top \mathbf{k}_t = \mathbf{q}^\top A\, \mathbf{c}_t = (A^\top \mathbf{q})^\top \mathbf{c}_t, \qquad \text{cache per token: } k \text{ numbers instead of } d \tag{118.12} \]

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.

Figure 5. Weight memory of the linear layers of LLaMA-2-7B (\(6.476 \times 10^9\) weights) for formula (118.10) and formula (118.11) with INT8 correction factors. Memory only: the accuracy of each setting must be measured.
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

SettingTypical useWhy
Small BERT-size encoders for search and classificationOne-shot NAS (NAS-BERT, AutoTinyBERT) with distillation from a large teacherMany sizes from one search; the candidates are small enough to train
On-device translation and speechHardware-aware NAS (HAT) with a latency table of the target phone or boardThe best shape depends on the hardware (Figure 1)
Choosing a new LLM family's shapesScaling-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 quantizationSVD-LLM or ASVD, then quantize the factorsA further 20% to 40% fewer parameters with dense kernels
Repairing low-bit quantizationLoRC: rank 4 to 8 correction of the quantization errorAbout 0.3% extra parameters on LLaMA-2-7B shapes
Long-context servingLow-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-RAGFactorize the language model, or the K/V projections, of a VLM that reads many frame tokensThousands of visual tokens per clip make the KV cache very large
Video classification and action recognition on edge devicesNAS over video transformer depth/width, or SVD of the backbone's FFN layers with in-domain calibration clipsLatency budgets per frame are strict; activation-aware SVD uses real video token statistics
Video fingerprinting and retrievalLow-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
\(W \approx AB\) with \(A \in \R^{m \times k}\), \(B \in \R^{k \times n}\): \(k(m+n)\) parameters instead of \(mn\). It saves memory only if \(k \lt mn/(m+n)\). For \(4096 \times 4096\) the break-even rank is 2048; for \(4096 \times 11{,}008\) it is about 2985. Removing 20% of a \(4096 \times 4096\) matrix needs \(k \approx 1638\), so 60% of the singular directions are dropped. FLOPs per token scale the same way, \(2k(m+n)\) instead of \(2mn\).
State the Eckart–Young theorem and explain what it does not tell you for LLMs.basic
Among all matrices of rank at most \(k\), the truncated SVD \(W_k\) is closest to \(W\) in Frobenius (and spectral) norm, with error \(\sqrt{\sum_{i \gt k}\sigma_i^2}\). It is about the weight error. For a network we need the output error \(\lVert WX - W'X\rVert\) on real inputs, and with outlier activation channels the two objectives choose different directions. That is why plain SVD gives LLaMA-7B a perplexity of 20,061 at 20% compression while activation-aware SVD gives under 8.
Why does plain SVD fail on LLM weights?core
Two reasons. First, trained LLM weight matrices do not have fast-decaying spectra, so a rank that saves memory (below \(mn/(m+n)\)) drops a large share of the energy. [Likely for the spectrum claim] Second, and more important, plain SVD does not see the inputs. LLMs have outlier features: a few channels with values 10 to 100 times larger. Small singular directions of \(W\) that touch those channels carry a large part of the output, and SVD drops them. The fix is to minimize \(\lVert (W - W')X\rVert\) instead.
Derive the SVD-LLM truncation and prove it is optimal for the output error.advanced
Let \(SS^\top = XX^\top\) (Cholesky). Then \(Q = S^{-1}X\) has orthonormal rows: \(QQ^\top = S^{-1}XX^\top S^{-\top} = I\). So \(\lVert (W - W')X\rVert_F = \lVert (W-W')SQ\rVert_F = \lVert WS - W'S\rVert_F\). Minimizing over rank-\(k\) \(W'\) is the same as finding the rank-\(k\) \(M = W'S\) closest to \(WS\); by Eckart–Young that is the truncated SVD \(U_k\Sigma_kV_k^\top\) of \(WS\), so \(W' = U_k\Sigma_kV_k^\top S^{-1}\) and the loss is \(\sqrt{\sum_{i \gt k}\sigma_i(WS)^2}\). It needs \(XX^\top\) invertible; add a small \(\lambda I\).
How is ASVD related to SVD-LLM? Compare with Wanda and SparseGPT.core
ASVD scales input channel \(j\) by \(s_j = (\text{mean}|x_j|)^{0.5}\), a diagonal \(S\); SVD-LLM uses the full Cholesky factor of \(XX^\top\), which also accounts for correlations between channels. If the channels were uncorrelated and \(s_j\) were the RMS (\(\alpha = 1\) with RMS instead of mean absolute value), the two would coincide. This mirrors pruning: Wanda is OBS with a diagonal Hessian, SparseGPT uses the full Hessian \(2XX^\top\). Measured: at 20% removed on LLaMA-7B, ASVD 11.14 and SVD-LLM (whitening only) 7.94 in the SVD-LLM paper.
Why is NAS rarely used to design LLMs?core
NAS must judge many architectures, and judging means training. Classic NAS trains each candidate: the Evolved Transformer search was estimated at 274,120 hours on 8-GPU machines for a translation model. One-shot NAS trains a supernet once, but for LLMs the supernet is itself a huge pre-training run, shared-weight scores rank candidates imperfectly, and short training does not predict which shape wins after trillions of tokens. Scaling laws also show the loss depends mainly on size and data, weakly on shape, so the gain from search is small. LLM shapes are chosen with scaling-law fits and ablations; NAS survives in training-free (LTS) and hardware-aware (HAT) forms for small models.
What is a supernet, and what are the main tricks NAS-BERT uses?advanced
A supernet contains every candidate architecture as a sub-network with shared weights, so it is trained once and candidates are scored without training. NAS-BERT: 24 layers, 26 candidate operations per layer (attention, FFN, separable convolution, identity, in several sizes), about \(10^{34}\) paths. It trains 4 blocks of 6 layers separately by distilling the matching BERT-base block, progressively removes the worse half of sampled architectures per size bin, predicts latency from a per-operation lookup table, and approximates loss by the sum of block losses. Supernet training took about 3 days on 32 P40 GPUs.
Does low-rank factorization give real speed on a GPU? When does it not?core
Yes, more reliably than unstructured sparsity: the factors are dense, so FLOPs and bytes both shrink by \(\rho = k(m+n)/(mn)\), and memory-bound decoding has an upper limit of \(1/\rho\). The gain shrinks because one kernel becomes two (launch and sync overhead at small batch), ranks that are not multiples of 64 or 128 use tensor cores badly, and attention, normalization and the KV cache are unchanged. Measure end to end.
How can factorization be combined with quantization? Give two designs.core
(1) Factor, then quantize the factors: bits per original weight \(= \rho b\). SVD-LLM at 40% removed plus 2-bit QuIP# gives LLaMA-7B perplexity 9.83 at 1.3 GB, better than 1-bit methods at similar size. Split \(\Sigma^{1/2}\) between the factors to balance their ranges. (2) Quantize, then correct: LoRC adds a rank-\(r\) SVD of the quantization error \(W - Q(W)\), with \(r = 4\) to 8 and INT8 factors, about \(3r/(2h)\) extra parameters (under 2%). LoftQ uses a related quantized-base-plus-low-rank form for fine-tuning.
How can a low-rank key projection shrink the KV cache without slowing attention?advanced
With \(W_K = AB\), cache \(\mathbf{c}_t = B\mathbf{x}_t \in \R^k\) instead of \(\mathbf{k}_t = A\mathbf{c}_t \in \R^d\). The score is \(\mathbf{q}^\top A\mathbf{c}_t = (A^\top\mathbf{q})^\top\mathbf{c}_t\), so compute \(A^\top\mathbf{q}\) once per step and use the small cached vectors directly; values work the same way by folding \(A_V\) into the output projection. This is MLA's weight absorption. ASVD measures LLaMA-2-7B at KV ratio 0.5 with perplexity 5.67 against 5.47 dense. (With RoPE, the rotation sits between \(A\) and the score, which complicates absorption; MLA uses a separate small RoPE part.) [Likely for the RoPE remark]
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
The 6.48B linear-layer weights at 2 GB means about 2.5 bits per weight (embeddings extra). Pure 2- to 3-bit quantization (GPTQ, QuIP#, AWQ) is the first option: dense kernels exist and quality is the best known per bit. Factorization adds a second axis: remove 20% to 40% with SVD-LLM, then quantize the factors to 3 to 4 bits (\(\rho b = 0.6 \times 4 = 2.4\) bits). 2:4 sparsity at 4 bits gives 3 bits per weight but costs accuracy and needs sparse kernels. Decide by measuring task accuracy (not only perplexity) for each candidate at the same byte budget, and consider a short recovery fine-tune or distillation. [Likely as a recommendation]

Exercises

  1. What rank \(k\) of a \(4096 \times 11{,}008\) FFN matrix removes 50% of its parameters? Check your answer.
  2. 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?
  3. 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?
  4. 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?
  5. 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?
  6. 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
1. \(k = 0.5 \cdot 4096 \cdot 11008 / 15104 \approx 1492.6\), so \(k = 1492\): \(1492 \cdot 15104 / (4096 \cdot 11008) = 0.4998\). 2. Dropped energy \(1 + 1 = 2\) of \(16 + 4 + 1 + 1 = 22\): relative error \(\sqrt{2/22} = 0.302\), kept energy \(20/22 = 90.9\%\). 3. Per layer \(8 \cdot (4 \cdot 8192 + 3 \cdot 15104)\) extra against \(4 \cdot 4096^2 + 3 \cdot 4096 \cdot 11008\): 0.309%. Bits: \(4 + 8 \times 0.00309 = 4.025\) per weight. 4. \(\rho b = 0.6 \times 2 = 1.2\) bits per weight; \(6.476 \times 10^9 \times 1.2 / 8 = 0.97\) GB (plus scales, embeddings and the output layer). 5. Output energy \(4 \cdot 1 + 1 \cdot 9 = 13\). Plain SVD keeps channel 1 (\(\sigma = 2\)) and loses \(9/13 = 69.2\%\). Whitening gives \(WS = \operatorname{diag}(2, 3)\), keeps channel 2 and loses \(4/13 = 30.8\%\). 6. \(274120 / 12041 \approx 22.8\) machine-hours, if both are measured the same way (HAT's own baseline may differ from Strubell's estimate).

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

\[ \rho = \frac{k(m+n)}{mn}, \qquad \min_{\operatorname{rank} \le k}\lVert W - W'\rVert_F = \sqrt{\textstyle\sum_{i \gt k}\sigma_i^2} \]
\[ \text{ASVD: } W' = [WS]_k S^{-1},\ s_j = (\overline{|x_j|})^{\alpha}; \qquad \text{SVD-LLM: } SS^\top = XX^\top,\ \lVert (W - W')X\rVert_F = \lVert WS - W'S \rVert_F \]
\[ \text{factor + quantize: } \rho\, b \text{ bits}; \qquad \text{LoRC: } W \approx Q(W) + [W - Q(W)]_r \]

References for this session

  1. Xu et al. (2021). NAS-BERT: Task-Agnostic and Adaptive-Size BERT Compression with Neural Architecture Search
  2. Yuan et al. (2023). ASVD: Activation-aware Singular Value Decomposition for Compressing Large Language Models
  3. Wang et al. (2024). SVD-LLM: Truncation-aware Singular Value Decomposition for Large Language Model Compression
  4. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  5. Xu et al. (2021). NAS-BERT: Task-Agnostic and Adaptive-Size BERT Compression with Neural Architecture Search
  6. Yuan et al. (2023). ASVD: Activation-aware Singular Value Decomposition for Compressing Large Language Models
  7. Wang et al. (2024). SVD-LLM: Truncation-aware Singular Value Decomposition for Large Language Model Compression
  8. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  9. Wang, Wu, Liu, Cai, Zhu, Gan and Han (2020). HAT: Hardware-Aware Transformers for Efficient Natural Language Processing
  10. So, Liang and Le (2019). The Evolved Transformer
  11. Strubell, Ganesh and McCallum (2019). Energy and Policy Considerations for Deep Learning in NLP
  12. Yin et al. (2021). AutoTinyBERT: Automatic Hyper-parameter Optimization for Efficient Pre-trained Language Models
  13. Javaheripi et al. (2022). LiteTransformerSearch: Training-free Neural Architecture Search for Efficient Language Models
  14. Hsu et al. (2022). Language model compression with weighted low-rank factorization (FWSVD)
  15. Yao, Wu, Li, Youn and He (2023). ZeroQuant-V2: Exploring Post-training Quantization in LLMs from Comprehensive Study to Low Rank Compensation
  16. Li et al. (2023). LoSparse: Structured Compression of Large Language Models based on Low-Rank and Sparse Approximation
  17. Kaushal, Vaidhya and Rish (2023). LORD: Low Rank Decomposition of Monolingual Code LLMs for One-Shot Compression
  18. Eckart and Young (1936). The approximation of one matrix by another of lower rank (Psychometrika)
  19. Hoffmann et al. (2022). Training Compute-Optimal Large Language Models
  20. Tseng et al. (2024). QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks
  21. Ashkboos et al. (2024). SliceGPT: Compress Large Language Models by Deleting Rows and Columns
  22. Hu et al. (2021). LoRA: Low-Rank Adaptation of Large Language Models