Pruning basics: magnitude, OBD and OBS; structured vs unstructured
Pruning removes weights from a trained model. The simplest rule removes the smallest weights; better rules use the curvature of the loss (the Hessian) to choose which weights to remove and to move the remaining weights so the model keeps working. This session builds magnitude pruning, Optimal Brain Damage and Optimal Brain Surgeon step by step, and explains why removing single weights rarely makes a GPU faster while removing whole channels, heads or layers does.
What you will learn
- What pruning is: masks, sparsity, granularity, one-shot versus gradual pruning
- Magnitude pruning, the train-prune-retrain loop, and why it collapses on LLMs at 50% sparsity
- The second-order view: the Taylor expansion of the loss and the OBD saliency ½·H_qq·w_q²
- OBS: remove one weight and move all the others with the inverse Hessian, with a full derivation
- Why OBS needs the layer-wise form H = 2XXᵀ to scale, and how OBD then becomes the Wanda score
- Unstructured, N:M, channel, head and layer sparsity, and a simple memory model of real GPU speed-up
- Why structured pruning gives real speed-up but loses more accuracy, and how recovery training helps
Why this matters
A trained network has many weights that do almost nothing. Pruning removes them. If you remove the right ones, the model keeps its quality and becomes smaller. If you remove the wrong ones, or remove them in the wrong pattern, you get a model that is worse and not faster at all. This session gives you the tools to tell the two cases apart.
The quantization sessions (session 103 to session 112) kept every weight and stored it in fewer bits. In the last lab, GPTQ beat round-to-nearest at the same INT4 format only because it used the layer Hessian to correct errors. The same Hessian is the main tool of this session. Pruning is the other main way to compress weights: it keeps the bits but sets many weights to exactly zero. The efficient-inference survey puts both under “model compression” and splits pruning into two kinds by granularity (the size of the piece that is removed). [Certain, survey Section 5.2.2]
- Unstructured pruning removes single weights anywhere. It reaches high sparsity with little loss, but the zeros have no regular pattern, so memory access and computation are irregular and the real speed-up on hardware is limited.
- Structured pruning removes whole channels, attention heads or layers. What is left is a smaller dense model, so it runs faster on any hardware. But it usually costs more accuracy.
This session builds the ideas that every LLM pruning method is made of. First the simplest rule, magnitude pruning, and why it collapses on LLMs. Then the second-order view from 1990 and 1993: Optimal Brain Damage (OBD) and Optimal Brain Surgeon (OBS) use the curvature of the loss to choose which weights to remove, and OBS also moves the kept weights to repair the damage. You saw the same OBS update in session 106, where GPTQ uses it to fix rounding errors. Here it fixes removals. Finally we look at the hardware question: why 50% of zeros often gives no speed-up, and what 2:4, channel, head and layer sparsity change.
Interview questions on this topic: “Why does magnitude pruning fail on LLMs?”, “Derive the OBS update”, “Why is my 50% sparse model not faster?”, “Structured or unstructured: which would you ship?”. By the end you can answer each with a formula and a number. The next two sessions, session 114 and session 115, apply these tools to real LLMs.
What pruning is
Masks and sparsity
Take one weight matrix \(W\). Pruning chooses a mask \(M\) of the same shape with entries 0 or 1, and replaces \(W\) by the elementwise product. The sparsity is the fraction of zeros:
- Read the symbols
- \(M\)
- the mask: 1 means “keep this weight”, 0 means “remove it”
- \(\odot\)
- elementwise product
- \(\lVert M \rVert_0\)
- the number of non-zero entries of \(M\), so the number of kept weights
- \(N\)
- the total number of weights in \(W\)
- \(s\)
- sparsity. \(s = 0.5\) means half the weights are zero.
A pruning method answers three questions.
- Which weights? The score (also called saliency): a number per weight or per group; low score means “safe to remove”.
- In which pattern? The granularity: single weights, N:M groups, rows, columns, heads or whole layers. This decides the speed-up.
- What happens to the kept weights? Nothing, a closed-form update (OBS), or retraining (fine-tuning with the mask fixed).
And one question about time: one-shot pruning removes everything at once after training, usually with a small calibration set and no gradient steps. Gradual pruning removes weights a little at a time during (re)training. LLM pruning is mostly one-shot, because retraining a 70B model is very expensive.
The patterns
| Granularity | What is removed | Result | Runs faster on a GPU? |
|---|---|---|---|
| Unstructured | any single weight | same shape, irregular zeros | only with special kernels, mostly at high sparsity |
| Semi-structured N:M | N of every M consecutive weights (2:4: two of four) | same shape, regular zeros + small index | yes on sparse tensor cores (NVIDIA Ampere and later), up to 2× math |
| Channel / neuron | a whole row or column of a matrix | smaller dense matrices | yes, everywhere |
| Attention head | one head: its slices of \(W_Q, W_K, W_V, W_O\) | fewer heads | yes, everywhere |
| Layer (depth) | a whole transformer block | fewer blocks | yes, everywhere |
Magnitude pruning and its limits
The rule
The oldest and simplest score is the absolute value: remove the weights with the smallest \(|w|\). The idea is that a small weight changes the output little. Han et al. (2015) made it work at scale with a loop: train, prune the smallest weights, retrain the rest with the mask fixed, and repeat. They reduced AlexNet from 61 million to 6.7 million parameters (9×) and VGG-16 from 138 million to 10.3 million (13×) with no loss of accuracy on ImageNet. [Certain, paper abstract]
Zhu and Gupta (2017) made the loop smooth. Instead of a few big pruning steps, the sparsity grows during training along a cubic curve, fast at first (many weights are clearly useless) and slowly at the end:
- Read the symbols
- \(s_i, s_f\)
- initial and final sparsity (for example 0 and 0.9)
- \(t_0\)
- the training step where pruning starts
- \(\Delta t\)
- the number of steps between two pruning updates
- \(n\)
- the number of pruning updates
At each update the smallest weights are masked until the layer has sparsity \(s_t\); training continues in between, so the network adapts. They found that a large sparse model beats a small dense model with the same number of non-zero weights, with up to 10× fewer non-zero parameters at small accuracy loss. [Certain, paper abstract]
- input: a network, target sparsity \(s_f\), schedule \(t_0, \Delta t, n\)
- for each training step \(t\):
- if \(t = t_0 + j\Delta t\) for some \(j \le n\):
- compute \(s_t\) with (113.2)
- for each layer: set \(M = 0\) for the \(s_t N\) smallest \(|w|\), \(M = 1\) elsewhere
- take one optimizer step on the loss with \(\hat W = M \odot W\) // masked weights get no update
- return \(M \odot W\)
Where magnitude fails
Magnitude pruning looks only at the weight. But the output of a neuron is \(y = \sum_j w_j x_j\): what matters is the product \(w_j x_j\). Wanda’s paper gives the simplest case: if \(|w_1| \le |w_2|\) but \(|x_1| \gg |x_2|\), magnitude removes \(w_1\), which changes \(y\) much more than removing \(w_2\). [Certain, Wanda paper] In LLMs this is not a corner case. From about 6B parameters, a few hidden-state features are about 100× larger than the others (session 108, LLM.int8()). [Certain, as cited in the Wanda paper] The weights that read those features may be small and still very important.
The results on LLMs are clear:
- On OPT-175B, one-shot magnitude pruning keeps accuracy only up to about 10% sparsity and collapses beyond 30%. At 50% the WikiText-2 perplexity is \(4.3 \times 10^4\), against 8.35 for the dense model. SparseGPT, a second-order method, reaches 8.21 at 50%. [Certain, SparseGPT paper, Table and Figure 1]
- On LLaMA-7B at 50% unstructured sparsity: dense 5.68, magnitude 17.29, Wanda 7.26, SparseGPT 7.22 (WikiText perplexity). With 2:4 sparsity magnitude gives 42.13. [Certain, Wanda paper Table 3]
So retraining is what made magnitude pruning work on CNNs; without retraining, on an LLM, the score is simply not good enough. We need a score that knows how much the loss changes when a weight is removed.
The second-order view: OBD
The loss near a trained model
Let \(\mathbf{w}\) be all the weights of a trained model and \(L(\mathbf{w})\) the loss. Removing weights changes \(\mathbf{w}\) by some \(\delta\mathbf{w}\). The Taylor expansion of the change in loss is
- Read the symbols
- \(\mathbf{g}\)
- the gradient \(\partial L / \partial \mathbf{w}\). After training to a minimum it is close to zero, so the first term is dropped.
- \(H\)
- the Hessian, the matrix of second derivatives \(H_{ij} = \partial^2 L / \partial w_i \partial w_j\). It measures the curvature of the loss: a large \(H_{ii}\) means the loss rises fast when \(w_i\) moves.
- \(O(\cdot)\)
- higher-order terms, assumed small
Both OBD and OBS start from this quadratic model. They differ in how much of \(H\) they use.
Optimal Brain Damage
LeCun, Denker and Solla (1990) made one more simplification: keep only the diagonal of \(H\). Then removing weight \(q\) alone, \(\delta\mathbf{w} = -w_q \mathbf{e}_q\), changes the loss by
- Read the symbols
- \(\mathbf{e}_q\)
- the unit vector with a 1 at position \(q\)
- \(s_q^{\text{OBD}}\)
- the saliency of weight \(q\): the predicted rise of the loss when it is set to zero and nothing else moves
- \(H_{qq}\)
- the curvature in the direction of \(w_q\)
Note that for a single weight with all others fixed, (113.4) is the exact quadratic term: \(\tfrac12 \mathbf{e}_q^{\top} H \mathbf{e}_q\, w_q^2 = \tfrac12 H_{qq} w_q^2\). The diagonal assumption enters when we remove many weights and add their saliencies as if they did not interact. The paper states its assumptions: the loss is near a minimum (no gradient term), it is quadratic, and the change from removing several weights is the sum of the single changes (diagonal). [Certain, OBD paper] Magnitude pruning is the special case where all \(H_{qq}\) are equal. OBD then prunes, retrains, and repeats, like Han et al.
OBD has one weakness: it never moves the kept weights. If two weights do almost the same job (their inputs are correlated), removing one could be repaired by making the other larger. OBD cannot see this.
Optimal Brain Surgeon: remove one weight, move the others
The problem
Hassibi and Stork (1993) kept the full Hessian. They ask: if weight \(q\) must become zero, what is the best change \(\delta\mathbf{w}\) of all weights, and how much does the loss then rise?
The constraint says “the new value of weight \(q\) is zero”. Write the Lagrangian \(\mathcal{L} = \tfrac12 \delta\mathbf{w}^{\top} H \delta\mathbf{w} + \lambda(\mathbf{e}_q^{\top}\delta\mathbf{w} + w_q)\). Setting its gradient in \(\delta\mathbf{w}\) to zero gives \(H\delta\mathbf{w} + \lambda \mathbf{e}_q = 0\), so \(\delta\mathbf{w} = -\lambda H^{-1}\mathbf{e}_q\). Put this into the constraint: \(-\lambda [H^{-1}]_{qq} + w_q = 0\), so \(\lambda = w_q / [H^{-1}]_{qq}\). This gives the OBS update and the OBS saliency:
- Read the symbols
- \(H^{-1}\mathbf{e}_q\)
- column \(q\) of the inverse Hessian. It says in which direction the other weights should move to cover for \(w_q\).
- \([H^{-1}]_{qq}\)
- the diagonal entry \(q\) of the inverse Hessian (not \(1/H_{qq}\))
- \(s_q^{\text{OBS}}\)
- the loss rise after removing \(q\) and making the best correction: \(\tfrac12 \delta\mathbf{w}^{\top} H \delta\mathbf{w}\) at the optimum
Because \([H^{-1}]_{qq} \ge 1/H_{qq}\) for any positive definite \(H\), we always have \(s_q^{\text{OBS}} \le s_q^{\text{OBD}}\), with equality when weight \(q\) is not coupled to the others. [Certain, a standard matrix inequality] The OBS score is the more honest one: it is the cost of removing a weight after the best repair.
Take \(\mathbf{w} = (0.5,\ 0.9)\) and \(H = \begin{pmatrix} 4 & 1.8 \\ 1.8 & 1 \end{pmatrix}\). The two weights are strongly coupled: the correlation \(\rho = 1.8/\sqrt{4 \cdot 1} = 0.9\). We may remove one weight.
Magnitude: \(|0.5| \lt |0.9|\), so remove \(w_1\). The loss rises by \(\tfrac12 \cdot 4 \cdot 0.25 = 0.5\).
OBD: \(s_1 = \tfrac12 \cdot 4 \cdot 0.25 = 0.5\) and \(s_2 = \tfrac12 \cdot 1 \cdot 0.81 = 0.405\). Remove \(w_2\): loss \(+0.405\). Magnitude and OBD disagree, because the small weight sits on the steep direction.
OBS: \(\det H = 0.76\), \(H^{-1} = \begin{pmatrix} 1.316 & -2.368 \\ -2.368 & 5.263 \end{pmatrix}\). Then \(s_1 = 0.25/(2 \cdot 1.316) = 0.095\) and \(s_2 = 0.81/(2 \cdot 5.263) = 0.077\). Remove \(w_2\) and apply (113.6): \(\delta\mathbf{w} = (0.405,\ -0.9)\), so the new weights are \((0.905,\ 0)\). The loss rises by only 0.077, 5.3× less than OBD.
In two dimensions there is a neat check: \(s_2^{\text{OBS}} = s_2^{\text{OBD}} (1 - \rho^2) = 0.405 \times 0.19 = 0.077\). The stronger the coupling, the more the repair helps. [Certain, computed]
- start at the trained point \(\mathbf{w}^*\); one weight must go
- magnitude: \(q = \argmin_j |w_j|\); set \(w_q = 0\)
- OBD: \(s_j = \tfrac12 H_{jj} w_j^2\); remove \(\argmin_j s_j\) // (113.4)
- OBS: invert \(H\); \(s_j = w_j^2 / (2[H^{-1}]_{jj})\) // (113.6)
- OBS: \(\delta\mathbf{w} = -\tfrac{w_q}{[H^{-1}]_{qq}} H^{-1}\mathbf{e}_q\): move along column \(q\) of \(H^{-1}\)
- compare the loss rise \(\delta L = \tfrac12 \delta\mathbf{w}^{\top} H \delta\mathbf{w}\) of the three methods
How to read Figure 1
Press Play, or use Step and Back. The figure runs the three methods one line at a time, and the panel under the plot shows each formula with the live numbers. At line 5 the blue point slides from \(\mathbf{w}^*\) to the axis along column \(q\) of \(H^{-1}\): the removed weight goes to 0 and the other weight moves with it. The sliders work at every step. Start at \(\rho = 0.90\), \(H_{11} = 4\): this is the worked example. Magnitude removes \(w_1\) (loss 0.500), OBD removes \(w_2\) (0.405), and OBS removes \(w_2\) and moves \(w_1\) to 0.905 (0.077). The filled circle is where the line \(w_2 = 0\) touches the smallest ellipse. Now set \(\rho = 0\): the ellipses line up with the axes, the filled and open circles meet, and OBS equals OBD (0.405). Set \(H_{11} = 1\) with \(\rho = 0\): now all three methods remove \(w_1\) with loss 0.125, because equal curvature makes OBD the same as magnitude. Negative \(\rho\) gives the same losses but moves \(w_1\) the other way (to 0.095).
Removing many weights
OBS removes weights one at a time. After weight \(q\) is gone, the problem for the remaining weights has a Hessian without row and column \(q\). Its inverse does not need a new inversion: it is one rank-one update of the old inverse (Gaussian elimination of \(q\)):
- Read the symbols
- \(H^{-1}_{-q}\)
- the inverse of the Hessian of the remaining weights
- \((\cdot)_{-q,-q}\)
- drop row \(q\) and column \(q\). The rest of the matrix is the new inverse.
One update costs \(O(d^2)\) for \(d\) weights, much less than the \(O(d^3)\) of a new inversion. The original OBS paper used a different way to build \(H^{-1}\) (a recursive outer-product formula) and recomputed it between retraining rounds. [Likely] The rank-one form (113.7) is the one used by OBC and GPTQ (session 106).
- input: weights \(\mathbf{w} \in \R^{d}\), Hessian \(H\), number of weights to remove \(k\)
- \(H^{-1} \leftarrow \text{inverse}(H + \lambda I)\) // small dampening \(\lambda\) for stability
- repeat \(k\) times:
- for every kept weight \(j\): \(s_j \leftarrow w_j^2 / (2[H^{-1}]_{jj})\) // (113.6)
- \(q \leftarrow \argmin_j s_j\)
- \(\mathbf{w} \leftarrow \mathbf{w} - \dfrac{w_q}{[H^{-1}]_{qq}} H^{-1}\mathbf{e}_q\); set \(w_q \leftarrow 0\) exactly // move the others
- \(H^{-1} \leftarrow H^{-1} - H^{-1}\mathbf{e}_q\mathbf{e}_q^{\top}H^{-1} / [H^{-1}]_{qq}\); remove \(q\) from the kept set // (113.7)
- return \(\mathbf{w}\)
Hassibi and Stork showed on small networks that OBS removes more weights than magnitude pruning or OBD for the same error, and that OBD can remove the wrong weights. [Likely, OBS paper, qualitative claim]
Figure 2 runs Algorithm 2 line by line on one row of a tiny layer with six weights. You can watch each score being computed, the chosen weight going to zero, the other weights moving, and the inverse Hessian losing one row and column. The same run with the magnitude score or the OBD score (and no update) is one click away, so you can compare the error after every removal.
- \(H \leftarrow 2\Sigma\); \(H^{-1} \leftarrow \text{inverse}(H)\)
- repeat \(k\) times:
- score every kept weight \(j\): \(s_j\)
- \(q \leftarrow \argmin_j s_j\)
- \(\delta\mathbf{w} \leftarrow -\tfrac{w_q}{[H^{-1}]_{qq}} H^{-1}\mathbf{e}_q\) (OBS) or \(-w_q \mathbf{e}_q\) (others); \(\mathbf{w} \leftarrow \mathbf{w} + \delta\mathbf{w}\)
- \(H^{-1} \leftarrow H^{-1} - H^{-1}\mathbf{e}_q\mathbf{e}_q^{\top}H^{-1} / [H^{-1}]_{qq}\) // OBS only, (113.7)
- return \(\mathbf{w}\), error \(\tfrac12 (\mathbf{w}-\mathbf{w}^0)^{\top} H (\mathbf{w}-\mathbf{w}^0)\)
How to read Figure 2
Press Play, or use Step and Back. The highlighted line of the algorithm and the panel next to it show the formula with the live numbers. With OBS and \(\rho = 0.6\), the first step removes \(w_2\): its score \(0.4^2 / (2 \cdot 1.0625) = 0.0753\) is the smallest. The update moves \(w_1\) to 0.9765 and \(w_3\) to 0.3588, and the error becomes exactly 0.0753: the OBS score is the error that the step adds. After \(k = 3\) removals the error is 0.3377 for OBS, 0.6750 for OBD and 1.4058 for magnitude. For these inputs \(H^{-1}\) is tridiagonal (zero outside the first off-diagonals), so only the two neighbours of a removed weight move. Magnitude first removes \(w_3 = 0.3\), the small weight on the outlier channel, and pays 0.81 at once. Switch to \(\rho = 0\): \(H\) is diagonal, the update moves nothing, and OBS makes exactly the same choices as OBD (0.77 at \(k = 3\)). At \(\rho = 0.9\) the repair matters most: OBS reaches 0.1021 at \(k = 3\).
Making OBS fit an LLM: the layer-wise problem
The full Hessian is impossible
For a model with \(N\) weights, \(H\) has \(N^2\) entries. For \(N = 7 \times 10^9\), that is \(4.9 \times 10^{19}\) numbers, 196 exabytes in FP32. [Certain, computed] No version of (113.6) with the full Hessian can run.
The way out, used by OBC, SparseGPT and Wanda, is to prune one linear layer at a time and to change the objective. Instead of the model loss, keep the output of the layer close to the original on some calibration inputs:
- Read the symbols
- \(W \in \R^{d_{\text{row}} \times d_{\text{col}}}\)
- the weight matrix of the layer; row \(i\) is \(\mathbf{w}_i^{\top}\), the weights of output \(i\)
- \(X \in \R^{d_{\text{col}} \times n}\)
- \(n\) calibration inputs to this layer, one per column (for example 128 sequences of 2048 tokens)
- \(\lVert\cdot\rVert_F\)
- the Frobenius norm: the square root of the sum of all squared entries
- \(H\)
- the Hessian of this squared error with respect to one row. It is the same for every row and has size \(d_{\text{col}} \times d_{\text{col}}\).
This is the same objective as GPTQ in session 106. Three things make it practical. The objective is exactly quadratic, so the Taylor expansion (113.3) has no error. The Hessian is small: \(4096 \times 4096\) is 67 MB in FP32. And the problem splits into independent rows that share one \(H\). [Certain] The price: a layer-wise objective ignores how the error grows through later layers.
OBD on a layer is the Wanda score
With \(H = 2XX^{\top}\), the diagonal is \(H_{jj} = 2 \lVert \mathbf{x}_j \rVert^2\), where \(\mathbf{x}_j\) is row \(j\) of \(X\): all the values of input channel \(j\) over the calibration set. Put this into the OBD saliency (113.4):
The square root, \(|w_{ij}| \cdot \lVert \mathbf{x}_j \rVert_2\), is exactly the Wanda score: “the elementwise product between the weight magnitude and the norm of input activations”, compared within each output row. [Certain, Wanda paper; the link to OBD is algebra] So Wanda is layer-wise OBD: it uses the diagonal of the layer Hessian and does not update the kept weights. SparseGPT is layer-wise OBS made fast. Both are the topic of session 114.
The score also fixes the failure of magnitude pruning: a small weight on an outlier channel has a large \(\lVert \mathbf{x}_j \rVert\) and is kept. Figure 3 shows this on a toy layer.
How to read Figure 3
At 50% (16 of 32 per row) with outlier channels, magnitude has error 0.1433, OBD/Wanda 0.0280 and OBS 0.0050: the input scale gives a 5.1× gain and the OBS repair another 5.6×. Switch to equal input scales: magnitude (0.0921) and OBD (0.0852) are now almost the same, because all \(\lVert \mathbf{x}_j \rVert\) are similar; OBS is still 5× better (0.0163), because the inputs are correlated and the kept weights can take over. Move the slider: the gap between the curves grows with sparsity, and every method breaks down when few weights are left.
The cost of exact OBS on a layer
Greedy OBS per row costs \(O(d_{\text{col}}^2)\) per removed weight. A \(4096 \times 4096\) layer at 50% needs \(4096 \times 2048\) removals of \(4096^2\) each: about \(1.4 \times 10^{14}\) multiply-adds for one layer, and the rows cannot share their inverse because each row removes different weights. [Certain, computed] This is why exact OBS does not scale to LLMs, and why SparseGPT changes the order of work so that all rows can share one sequence of inverses (session 114).
Unstructured sparsity: why zeros are not free
The memory view
A zero still costs time if the kernel does not skip it. To skip it, the kernel must know where the non-zeros are, so a sparse matrix stores the values plus some metadata (indices). Recall from session 82 that decoding with a small batch is memory-bound: the time is set by the bytes of weights read per token, not by the math. So a simple model of the best possible decode speed-up is the ratio of bytes:
- Read the symbols
- \(b_{\text{dense}}\)
- bytes per weight in the dense format: 2 for FP16/BF16
- \(b_{\text{nz}}\)
- bytes per stored non-zero, value plus its index. CSR (compressed sparse row) with 16-bit column indices: \(2 + 2 = 4\).
- \(b_{\text{meta}}\)
- metadata per original weight that does not depend on \(s\). A bitmask (one bit per weight saying zero or not) costs \(1/8\) byte; then \(b_{\text{nz}} = 2\).
CSR at \(s = 0.5\): \(0.5 \times 4 = 2\) bytes per weight, exactly the dense size: speed-up 1.0×. CSR only wins above 50%. At 70%: 1.2 bytes, at best 1.67×. At 90%: 0.4 bytes, 5×.
Bitmask at \(s = 0.5\): \(0.5 \times 2 + 0.125 = 1.125\) bytes, at best 1.78×. At 70%: 0.725 bytes, 2.76×. It beats dense once \(s \gt 1/16 = 6.25\%\).
2:4: in every group of 4 weights, 2 values of 2 bytes and 2 indices of 2 bits each: 36 bits per 4 weights = 1.125 bytes per weight, at best 1.78× in memory. [Certain, computed]
These are upper bounds. Real sparse kernels lose part of this to irregular memory access: two neighbouring threads read non-zeros from far-apart places, and the GPU loads memory in large aligned chunks. The survey says that unstructured sparse patterns “lack high-level regularity”, which leads to irregular memory access and computation and limits the practical speed-up. [Certain, survey Section 5.2.2]
The compute view
In prefill or at large batch, the work is compute-bound and runs on tensor cores, which multiply dense tiles. An unstructured sparse tile is still a dense tile for the tensor core unless the zeros are removed first, and general sparse matrix kernels (cuSPARSE, Sputnik) run on the slower CUDA cores. Flash-LLM (2023) turns this around: “Load-as-Sparse and Compute-as-Dense”. It reads the weights from memory in a sparse format (saving bandwidth) and expands them to dense tiles in fast on-chip memory for the tensor cores. It reports an average 2.9× kernel speed-up over Sputnik and 1.5× over SparTA, and end-to-end up to 3.6× over FasterTransformer on OPT-30B/66B/175B (tokens per GPU-second). [Certain, Flash-LLM abstract] So unstructured sparsity can help, but through memory, and mostly at high sparsity.
The middle way: 2:4
NVIDIA sparse tensor cores (Ampere and later) support one fixed pattern: in every group of 4 consecutive weights along the reduction dimension, at most 2 are non-zero. The hardware stores the 2 values and 2-bit indices and skips the zeros in the math: twice the math throughput of the dense tensor core. [Certain, Mishra et al.] Measured gains are smaller. Wanda reports about 1.6× for the linear layers of LLaMA-65B (CUTLASS kernel, A6000, batch 1) and 1.24× end-to-end for LLaMA-7B (251 ms instead of 312 ms). [Certain, Wanda paper Table 5] The price is accuracy: the pattern forces exactly 50% in every group, even where all four weights matter. On LLaMA-7B, Wanda gives 7.26 perplexity at 50% unstructured but 11.53 at 2:4. [Certain, Wanda Table 3]
How to read Figure 4
At 50% in decode mode, CSR gives 1.00× (its index costs as much as the value), the bitmask and 2:4 give 1.78×, and the structured layer (simply a matrix with half the rows) gives 2.00×. Move the slider down to 30%: CSR drops to 0.71×, slower than dense. Move it up to 90%: CSR reaches 5.00× and the bitmask 6.15×; this is why unstructured kernels target high sparsity. Switch to prefill: only 2:4 and structured sparsity save math on tensor cores.
Structured sparsity: channels, heads and layers
What changes
Structured pruning removes a whole unit, and the result is a smaller dense model. No index, no special kernel: the normal dense GEMM on a smaller matrix. The speed-up follows the removed work directly, in both memory and compute, on any hardware. [Certain] The common units in a transformer:
- FFN neurons (channels). Removing hidden unit \(j\) of the FFN removes row \(j\) of the up (and gate) projection and column \(j\) of the down projection. Both matrices shrink.
- Attention heads. Removing a head removes its slices of \(W_Q, W_K, W_V\) and of \(W_O\), and its part of the KV cache. Michel et al. (2019) found that a large percentage of heads can be removed at test time without a significant drop, and some layers can be reduced to one head. [Certain, paper abstract]
- Hidden dimension. Removing an embedding channel shrinks every matrix that reads or writes the residual stream. SliceGPT does this after a rotation (session 115).
- Layers. ShortGPT measures how much each block changes its input with the Block Influence:
\[ \text{BI}_i = 1 - \E_{X,t}\, \frac{\mathbf{x}_{i,t}^{\top}\, \mathbf{x}_{i+1,t}}{\lVert \mathbf{x}_{i,t} \rVert_2\, \lVert \mathbf{x}_{i+1,t} \rVert_2} \tag{113.11} \]where \(\mathbf{x}_{i,t}\) is the hidden state of token \(t\) entering block \(i\). A block whose output points the same way as its input (cosine near 1) has a low BI and is removed. [Certain, ShortGPT Eq. 1] For LLaMA-2-7B it removes 9 of 32 layers (layers 27, 26, 25, 28, 24, 29, 23, 21, 22). [Certain, ShortGPT Table 9]
Second-order scores for whole structures
The OBS idea extends to groups. In the layer-wise problem (113.8), removing input channel \(j\) means setting column \(j\) of \(W\) to zero in every row. All rows share the same \(H\), so (113.6) applies to each row with the same \(q = j\), and the costs add up:
- Read the symbols
- \(W_{:,j}\)
- column \(j\) of \(W\): the weights that read input channel \(j\), one per output
- \(\Delta W\)
- the update of the whole matrix: an outer product, so every row moves along the same direction \(H^{-1}\mathbf{e}_j\)
Removing input channel \(j\) of one layer also removes output channel \(j\) of the layer before it (nobody reads it any more), so the previous layer shrinks too. Removing an output row of a layer is different: that output becomes zero and no change of the other weights of this layer can bring it back; only the next layer can adapt. This is why structured methods look at coupled groups of weights across layers (LLM-Pruner builds a dependency graph for this). [Certain, LLM-Pruner paper]
Why structured pruning loses more accuracy
A unit is chosen as a whole. A column of a 4096 × 4096 matrix has 4096 weights; some of them are important even if the column on average is not. Unstructured pruning can keep those weights and remove unimportant ones from other columns. So, at the same sparsity, the unstructured mask is always at least as good for the layer error: it has more freedom. [Certain, the structured masks are a subset of all masks] The survey puts it in words: structured pruning works directly on regular hardware but “often results in a more pronounced impact on model performance”. [Certain, survey Section 5.2.2] Figure 5 shows the four patterns on the same layer.
How to read Figure 5
With no update, the error grows with the size of the removed unit: unstructured 0.0280, 2:4 0.0316, input channels 0.0725, output channels 0.3300. With re-fit it falls to 0.0072, 0.0097 and 0.0220 for the first three; for output channels it stays at 0.3300, because a removed output cannot be repaired inside the layer. Look at the triangles under the outlier columns: unstructured masks keep most weights on those columns, and the channel score never removes them. The speed-up line moves the other way: irregular zeros give at best 1.78× in memory, a half-size dense matrix gives 2×.
Recovering the accuracy
Because structured pruning hurts more, it is almost always followed by training. Three common recipes, each covered later:
- Short fine-tuning with LoRA after pruning: LLM-Pruner. [Certain, survey] (session 57)
- Continued pre-training of the pruned model on many tokens: Sheared LLaMA prunes to a chosen target shape and then trains with dynamic batch loading. [Certain, survey]
- Knowledge distillation from the dense model: the Minitron work prunes width and depth and retrains with distillation. [Certain, paper title and method] (session 59, session 122)
The practical rule that follows: unstructured or 2:4 pruning is a one-shot, cheap compression with a small loss; structured pruning is a way to start training a smaller model from a big one.
A complete example in PyTorch
This script builds a toy layer with correlated and outlier input channels, prunes it with magnitude, OBD (Wanda), OBD with a least-squares re-fit, and greedy OBS, checks the one-weight OBS update against a brute-force fit, and then prunes whole input channels. It is deterministic and runs on a CPU in a few seconds.
import torch torch.manual_seed(0) torch.set_default_dtype(torch.float64) # 1) a toy linear layer: W is (d_row, d_col); X holds n calibration inputs as columns d_row, d_col, n, rho = 32, 128, 1024, 0.8 Z = torch.randn(d_col, n) X = torch.empty(d_col, n); X[0] = Z[0] for j in range(1, d_col): # neighbouring input channels are correlated X[j] = rho * X[j - 1] + (1 - rho**2) ** 0.5 * Z[j] X[::16] *= 8.0 # a few "outlier" input channels W = torch.randn(d_row, d_col) H = 2 * X @ X.T # layer Hessian, formula (113.8) H += 0.01 * torch.diag(H).mean() * torch.eye(d_col) # small dampening def rel_err(W, Wp): # ||WX - W'X||^2 / ||WX||^2 return (((W - Wp) @ X) ** 2).sum() / ((W @ X) ** 2).sum() def prune_by_score(W, score, sparsity): # zero the lowest scores in every row k = int(sparsity * W.shape[1]) idx = torch.argsort(score, dim=1)[:, :k] return W.clone().scatter_(1, idx, 0.0) def obs_row(w, Hinv, k): # greedy OBS on one row, formula (113.6) w, Hinv = w.clone(), Hinv.clone() alive = torch.ones_like(w, dtype=torch.bool) for _ in range(k): s = w**2 / torch.diag(Hinv) # saliency of every weight s[~alive] = float("inf") q = torch.argmin(s) w -= w[q] / Hinv[q, q] * Hinv[:, q] # remove q, move the others w[q] = 0.0; alive[q] = False Hinv -= torch.outer(Hinv[:, q], Hinv[q, :]) / Hinv[q, q] # formula (113.7) Hinv[q, :] = 0.0; Hinv[:, q] = 0.0; Hinv[q, q] = 1.0 # keep it invertible return w def refit(W, Wp): # best values for the kept weights (least squares) out = Wp.clone() for r in range(W.shape[0]): m = Wp[r] != 0 out[r, m] = torch.linalg.solve(H[m][:, m], H[m] @ W[r]) return out Hinv = torch.linalg.inv(H) for sp in (0.5, 0.7): k = int(sp * d_col) mag = prune_by_score(W, W.abs(), sp) obd = prune_by_score(W, W**2 * torch.diag(H), sp) # formula (113.9) obs = torch.stack([obs_row(W[r], Hinv, k) for r in range(d_row)]) print(f"{sp:.0%} unstructured magnitude {rel_err(W, mag):.4f} OBD {rel_err(W, obd):.4f}" f" OBD mask+refit {rel_err(W, refit(W, obd)):.4f} OBS {rel_err(W, obs):.4f}") # 2) check the one-weight OBS update against a brute-force least-squares fit q = 5 dw = -W[0, q] / Hinv[q, q] * Hinv[:, q] m = torch.arange(d_col) != q best = torch.zeros(d_col); best[m] = torch.linalg.solve(H[m][:, m], H[m] @ W[0]) print("OBS update equals least squares:", torch.allclose(W[0] + dw, best)) # 3) structured: remove 50% of the INPUT channels (whole columns of W) k = d_col // 2 col_norm = W.norm(dim=0) # magnitude score per column cut = torch.argsort(col_norm)[:k] Wm = W.clone(); Wm[:, cut] = 0.0 Wo, Hi = W.clone(), Hinv.clone(); alive = torch.ones(d_col, dtype=torch.bool) for _ in range(k): # OBS for whole columns, formula (113.12) s = (Wo**2).sum(0) / torch.diag(Hi); s[~alive] = float("inf") j = torch.argmin(s) Wo -= torch.outer(Wo[:, j] / Hi[j, j], Hi[:, j]) # all rows share H Wo[:, j] = 0.0; alive[j] = False Hi -= torch.outer(Hi[:, j], Hi[j, :]) / Hi[j, j] Hi[j, :] = 0.0; Hi[:, j] = 0.0; Hi[j, j] = 1.0 print(f"50% of input channels magnitude {rel_err(W, Wm):.4f} OBS {rel_err(W, Wo):.4f}") print("layer after channel pruning is dense:", tuple(Wo[:, alive].shape))
Output (PyTorch 2.8, CPU):
50% unstructured magnitude 0.0685 OBD 0.0151 OBD mask+refit 0.0048 OBS 0.0034 70% unstructured magnitude 0.1773 OBD 0.0423 OBD mask+refit 0.0193 OBS 0.0114 OBS update equals least squares: True 50% of input channels magnitude 0.4159 OBS 0.0178 layer after channel pruning is dense: (32, 64)
Read the results. (1) At 50%, the input-aware OBD score is 4.5× better than magnitude, re-fitting the kept weights is 3× better again, and greedy OBS, which also chooses the mask with the repair in mind, is best. (2) The closed-form OBS update (113.6) is exactly the least-squares fit of the other weights. (3) Removing half of the input channels by column norm is a disaster (0.4159), while channel OBS keeps the error at 0.0178: still about 5× more than unstructured OBS at the same sparsity (0.0034), but the result is a dense 32 × 64 matrix that any kernel runs at full speed.
Where this is used
| Setting | Pattern | Why |
|---|---|---|
| One-shot compression of a served LLM on Ampere or newer GPUs | 2:4 with SparseGPT or Wanda | sparse tensor cores give a real gain; no retraining. Accept some perplexity loss, especially for small models [Certain, Wanda Table 3] |
| Memory-bound decoding with custom kernels | unstructured 70–90% (Flash-LLM) | fewer bytes read per token; needs a kernel and high sparsity [Certain, Flash-LLM] |
| Building a family of smaller models from one large one | width and depth (Minitron, Sheared LLaMA) | pruning + distillation or continued training is cheaper than training each size from scratch [Likely] |
| Quick depth reduction for latency | layers (ShortGPT) | fewer blocks = fewer sequential steps in every token; no kernel work |
| Encoders (BERT-like) for search and classification | attention heads, FFN neurons | many heads are redundant [Certain, Michel et al.]; smaller dense encoders run on CPUs |
| MoE models | whole experts | the survey lists expert pruning methods (ExpertSparsity, SEER-MoE) [Certain, survey]; see session 29 |
| On-device video classification and action recognition | channel pruning of the vision backbone | phones and cameras have no sparse kernels; only smaller dense layers help real-time frame rates [Likely] |
| Video retrieval and fingerprinting embedders | structured pruning + distillation | billions of frames are embedded; a 2× smaller dense encoder halves the cost, and distillation keeps the embedding space close to the teacher [Speculation] |
| VLMs for video QA and Video-RAG | layers or heads of the language model; 2:4 on the vision encoder | long frame sequences make prefill compute-bound, where only structured or 2:4 sparsity saves math (Figure 4) [Speculation] |
Common mistakes
- Reporting sparsity as speed. “50% sparse” says nothing about latency. In CSR it is exactly as large as the dense matrix (Figure 4). Always state the pattern, the kernel and the measured time.
- Using magnitude pruning on an LLM without retraining. It collapses beyond about 30% on OPT-175B and gives 17.29 instead of 5.68 perplexity on LLaMA-7B at 50%. Use an input-aware score.
- Comparing scores over the whole layer instead of per output row. Wanda found that comparing per output is crucial for LLMs. [Certain, Wanda paper] Global comparison can empty some rows completely.
- Confusing \(1/H_{qq}\) with \([H^{-1}]_{qq}\). OBS needs the diagonal of the inverse; using \(1/H_{qq}\) gives back OBD.
- Forgetting dampening. \(XX^{\top}\) is often singular (dead channels, fewer samples than channels). Add \(\lambda I\) before inverting, as GPTQ does.
- Pruning output channels and expecting the layer to repair it. A removed output is zero; only the next layer (or training) can compensate (Figure 5).
- Removing structures one by one without updating the scores. After one head or layer is removed, the others change their importance. Recompute scores or prune gradually.
- Calibrating on the wrong data. \(H = 2XX^{\top}\) depends on the calibration inputs. Pruning a code model with English web text keeps the wrong channels. [Likely]
Interview questions
What is pruning, and what are the three design choices of a pruning method?basic
Magnitude pruning worked for AlexNet and VGG. Why does it fail for LLMs?core
Derive the OBD saliency. What are its assumptions?core
Derive the OBS update and saliency.advanced
When do OBD and OBS give the same answer? How big can the difference be?core
Why can you not run OBS on a 7B model directly? What do LLM methods do instead?advanced
Show that the Wanda score is OBD for the layer-wise problem.advanced
Your 50% unstructured sparse model is not faster. Why?core
What is 2:4 sparsity, and what speed-up does it give in practice?core
Structured or unstructured pruning: what is the trade-off, and how do you recover accuracy?core
Pruning or quantization first, for a memory-bound decode workload?advanced
Exercises
- Two weights \(\mathbf{w} = (0.2, -0.6)\) with a diagonal Hessian \(H = \operatorname{diag}(10, 1)\). Which weight does magnitude pruning remove? Which does OBD remove? What is the loss rise in each case?
- Take \(\mathbf{w} = (1, 1)\) and \(H = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}\). Compute the OBD and OBS saliencies of \(w_1\), and the new weights after the OBS removal of \(w_1\).
- A 4096 × 4096 FP16 matrix is pruned to 70% unstructured sparsity. How many MB does it take in dense form, in CSR with 16-bit indices, and as bitmask + values? What is the ideal decode speed-up of each sparse format?
- At what sparsity does a bitmask format start to use fewer bytes than dense FP16? And CSR with 16-bit indices?
- Llama-2-7B’s down projection reads \(d_{\text{col}} = 11{,}008\) inputs. How much memory does its layer Hessian \(H = 2XX^{\top}\) take in FP32?
- ShortGPT removes 9 of the 32 blocks of LLaMA-2-7B. Ignoring the embedding and output layers, what is the ideal decode speed-up?
- Prove that in two dimensions \(s_2^{\text{OBS}} = s_2^{\text{OBD}}(1 - \rho^2)\), with \(\rho = H_{12}/\sqrt{H_{11}H_{22}}\).
Answerscheck
Key takeaways
- Pruning = a mask \(M \odot W\) (113.1) plus three choices: the score, the granularity, and what happens to the kept weights.
- Magnitude pruning needs retraining. One-shot on LLMs it collapses: OPT-175B beyond about 30%, LLaMA-7B 17.29 vs 5.68 perplexity at 50%, because it ignores outlier input features.
- OBD: loss rise \(\tfrac12 H_{qq} w_q^2\) from a diagonal Hessian (113.4). OBS: remove \(q\) and move all others by \(-\frac{w_q}{[H^{-1}]_{qq}} H^{-1}\mathbf{e}_q\), loss \(\frac{w_q^2}{2[H^{-1}]_{qq}}\) (113.6). OBS is never worse; it helps most when weights are coupled.
- LLMs use the layer-wise problem with \(H = 2XX^{\top}\) (113.8): exact, small, shared by rows. OBD on it is the Wanda score \(|w_{ij}|\,\lVert\mathbf{x}_j\rVert\) (113.9); OBS on it leads to SparseGPT.
- Unstructured zeros save time only through fewer bytes and special kernels: CSR breaks even at 50%, a bitmask gives at most 1.78× at 50% (113.10). Tensor cores do not skip irregular zeros.
- 2:4 is the hardware middle way: up to 2× math, about 1.6× measured on linear layers, 1.24× end-to-end for LLaMA-7B, but more accuracy loss than unstructured.
- Structured pruning (channels, heads, layers) gives a smaller dense model and real speed-up everywhere, but loses more accuracy; recover it with LoRA, continued training or distillation.
Key formulas
References for this session
- Hassibi & Stork (1993). Second order derivatives for network pruning: Optimal Brain Surgeon
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
- LeCun, Denker & Solla (1990). Optimal Brain Damage
- Hassibi & Stork (1993). Second order derivatives for network pruning: Optimal Brain Surgeon
- Han, Pool, Tran & Dally (2015). Learning both Weights and Connections for Efficient Neural Networks
- Zhu & Gupta (2017). To prune, or not to prune: exploring the efficacy of pruning for model compression
- Frankle & Carbin (2018). The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
- Frantar & Alistarh (2023). SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot
- Sun et al. (2023). A Simple and Effective Pruning Approach for Large Language Models (Wanda)
- Frantar & Alistarh (2022). Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning
- Mishra et al. (2021). Accelerating Sparse Deep Neural Networks
- Xia, Zheng, Li et al. (2023). Flash-LLM: Enabling Cost-Effective and Highly-Efficient Large Generative Model Inference with Unstructured Sparsity
- Michel, Levy & Neubig (2019). Are Sixteen Heads Really Better than One?
- Men, Xu, Zhang et al. (2024). ShortGPT: Layers in Large Language Models are More Redundant Than You Expect
- Ashkboos et al. (2024). SliceGPT: Compress Large Language Models by Deleting Rows and Columns
- Ma et al. (2023). LLM-Pruner: On the Structural Pruning of Large Language Models
- Xia et al. (2023). Sheared LLaMA: Accelerating Language Model Pre-training via Structured Pruning
- Muralidharan et al. (2024). Compact Language Models via Pruning and Knowledge Distillation (Minitron)
- Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models