LLM & VLM courseBlog
113Track 5: LLM inference and serving · session 36 of 65

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.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: IntermediateBefore this: Weight PTQ 1 (session 106), why inference is slow (session 82), basic linear algebra

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:

\[ \hat W = M \odot W, \qquad s = 1 - \frac{\lVert M \rVert_0}{N} \tag{113.1} \]
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.

  1. Which weights? The score (also called saliency): a number per weight or per group; low score means “safe to remove”.
  2. In which pattern? The granularity: single weights, N:M groups, rows, columns, heads or whole layers. This decides the speed-up.
  3. 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

GranularityWhat is removedResultRuns faster on a GPU?
Unstructuredany single weightsame shape, irregular zerosonly with special kernels, mostly at high sparsity
Semi-structured N:MN of every M consecutive weights (2:4: two of four)same shape, regular zeros + small indexyes on sparse tensor cores (NVIDIA Ampere and later), up to 2× math
Channel / neurona whole row or column of a matrixsmaller dense matricesyes, everywhere
Attention headone head: its slices of \(W_Q, W_K, W_V, W_O\)fewer headsyes, everywhere
Layer (depth)a whole transformer blockfewer blocksyes, 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:

\[ s_t = s_f + \big(s_i - s_f\big) \left(1 - \frac{t - t_0}{n\,\Delta t}\right)^{3}, \qquad t \in \{t_0,\ t_0 + \Delta t,\ \dots,\ t_0 + n\Delta t\} \tag{113.2} \]
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]

Algorithm 1: gradual magnitude pruning (Zhu and Gupta)
  1. input: a network, target sparsity \(s_f\), schedule \(t_0, \Delta t, n\)
  2. for each training step \(t\):
  3.   if \(t = t_0 + j\Delta t\) for some \(j \le n\):
  4.     compute \(s_t\) with (113.2)
  5.     for each layer: set \(M = 0\) for the \(s_t N\) smallest \(|w|\), \(M = 1\) elsewhere
  6.   take one optimizer step on the loss with \(\hat W = M \odot W\) // masked weights get no update
  7. 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

\[ \delta L = \underbrace{\mathbf{g}^{\top} \delta\mathbf{w}}_{\approx\, 0 \text{ at a minimum}} + \tfrac{1}{2}\, \delta\mathbf{w}^{\top} H\, \delta\mathbf{w} + O\big(\lVert \delta\mathbf{w} \rVert^{3}\big) \tag{113.3} \]
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

\[ s_q^{\text{OBD}} = \tfrac{1}{2}\, H_{qq}\, w_q^{2} \tag{113.4} \]
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?

\[ \min_{\delta\mathbf{w}}\ \tfrac{1}{2}\, \delta\mathbf{w}^{\top} H\, \delta\mathbf{w} \quad \text{subject to} \quad \mathbf{e}_q^{\top} \delta\mathbf{w} + w_q = 0 \tag{113.5} \]

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:

\[ \delta\mathbf{w} = -\frac{w_q}{[H^{-1}]_{qq}}\, H^{-1} \mathbf{e}_q, \qquad s_q^{\text{OBS}} = \frac{w_q^{2}}{2\,[H^{-1}]_{qq}} \tag{113.6} \]
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.

Worked example: two weights

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]

  1. start at the trained point \(\mathbf{w}^*\); one weight must go
  2. magnitude: \(q = \argmin_j |w_j|\); set \(w_q = 0\)
  3. OBD: \(s_j = \tfrac12 H_{jj} w_j^2\); remove \(\argmin_j s_j\) // (113.4)
  4. OBS: invert \(H\); \(s_j = w_j^2 / (2[H^{-1}]_{jj})\) // (113.6)
  5. OBS: \(\delta\mathbf{w} = -\tfrac{w_q}{[H^{-1}]_{qq}} H^{-1}\mathbf{e}_q\): move along column \(q\) of \(H^{-1}\)
  6. compare the loss rise \(\delta L = \tfrac12 \delta\mathbf{w}^{\top} H \delta\mathbf{w}\) of the three methods
Figure 1. A quadratic loss \(\tfrac12 (\mathbf{w}-\mathbf{w}^*)^{\top} H (\mathbf{w}-\mathbf{w}^*)\) over two weights, with \(\mathbf{w}^* = (0.5, 0.9)\) and \(H_{22} = 1\). The ellipses are contours of equal loss. Pruning must land on one of the two axes: the vertical line (\(w_1 = 0\)) or the horizontal line (\(w_2 = 0\)). Open circles: set one weight to zero and keep the other (magnitude, OBD). Filled circles: the OBS point, the lowest loss on that axis. The table on the right gives the three scores and the choice of each method; it fills in as the animation reaches each method.
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\)):

\[ H^{-1}_{-q} = \Big( H^{-1} - \frac{H^{-1}\mathbf{e}_q\, \mathbf{e}_q^{\top} H^{-1}}{[H^{-1}]_{qq}} \Big)_{-q,\,-q} \tag{113.7} \]
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).

Algorithm 2: greedy OBS on a weight vector
  1. input: weights \(\mathbf{w} \in \R^{d}\), Hessian \(H\), number of weights to remove \(k\)
  2. \(H^{-1} \leftarrow \text{inverse}(H + \lambda I)\) // small dampening \(\lambda\) for stability
  3. repeat \(k\) times:
  4.   for every kept weight \(j\): \(s_j \leftarrow w_j^2 / (2[H^{-1}]_{jj})\) // (113.6)
  5.   \(q \leftarrow \argmin_j s_j\)
  6.   \(\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
  7.   \(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)
  8. 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.

  1. \(H \leftarrow 2\Sigma\); \(H^{-1} \leftarrow \text{inverse}(H)\)
  2. repeat \(k\) times:
  3.   score every kept weight \(j\): \(s_j\)
  4.   \(q \leftarrow \argmin_j s_j\)
  5.   \(\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}\)
  6.   \(H^{-1} \leftarrow H^{-1} - H^{-1}\mathbf{e}_q\mathbf{e}_q^{\top}H^{-1} / [H^{-1}]_{qq}\) // OBS only, (113.7)
  7. return \(\mathbf{w}\), error \(\tfrac12 (\mathbf{w}-\mathbf{w}^0)^{\top} H (\mathbf{w}-\mathbf{w}^0)\)
Figure 2. Greedy pruning of one row \(\mathbf{w}^0 = (0.8,\ 0.4,\ 0.3,\ 0.6,\ 0.7,\ -0.5)\) of a linear layer, computed in your browser. The inputs have scales \(\sigma = (1, 1, 3, 1, 1, 1)\) (channel 3 is an outlier channel) and neighbouring channels have correlation \(\rho\), so the input covariance is \(\Sigma_{ij} = \sigma_i \sigma_j \rho^{|i-j|}\) and the layer Hessian is \(H = 2\Sigma\), the per-input form of (113.8). The error \(\tfrac12 \delta\mathbf{w}^{\top} H \delta\mathbf{w} = \E[(\delta\mathbf{w}^{\top}\mathbf{x})^2]\) is the mean squared change of the output. Top left: the weights (outline = original value). Bottom left: the score of every kept weight for the chosen method; red marks the smallest. Top right: \(H^{-1}\) for OBS (blue positive, orange negative), or \(H\) for OBD, whose diagonal is all it uses. Bottom right: the error after each removal for all three methods; the chosen method is drawn bold up to the current step.
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:

\[ \min_{\hat W}\ \big\lVert W X - \hat W X \big\rVert_F^{2} = \sum_{i} (\hat{\mathbf{w}}_i - \mathbf{w}_i)^{\top} \big(X X^{\top}\big) (\hat{\mathbf{w}}_i - \mathbf{w}_i), \qquad H = 2\, X X^{\top} \tag{113.8} \]
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):

\[ s_{ij}^{\text{OBD}} = \tfrac{1}{2} \cdot 2 \lVert \mathbf{x}_j \rVert^{2}\, w_{ij}^{2} = \big( |w_{ij}| \cdot \lVert \mathbf{x}_j \rVert_2 \big)^{2} \tag{113.9} \]

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.

Figure 3. A toy linear layer with \(W\) of size 8 × 32 and 256 calibration inputs (seeded, computed in your browser). Neighbouring input channels are correlated (\(\rho = 0.8\)); in the first setting, input channels 1, 9, 17 and 25 are 6× larger, like LLM outlier features. Each curve prunes the same number of weights in every row with one score: magnitude \(|w_{ij}|\), OBD/Wanda (113.9), or greedy OBS (Algorithm 2 with \(H = 2XX^{\top}\)), and plots \(\lVert WX - \hat W X\rVert^2 / \lVert WX \rVert^2\) on a log scale.
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:

\[ \text{speed-up}_{\text{decode}} \le \frac{b_{\text{dense}}}{(1 - s)\, b_{\text{nz}} + b_{\text{meta}}} \tag{113.10} \]
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\).
Worked example: bytes of a 50% and a 70% sparse FP16 matrix

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]

Figure 4. An ideal model of the speed of one FP16 linear layer, from formula (113.10). Decode: speed-up = 2 bytes ÷ bytes read per original weight. Prefill: speed-up = reduction of the math that the hardware can really skip; unstructured formats are drawn at 1× (compute as dense), 2:4 at its hardware maximum of 2×, structured at \(1/(1-s)\). These are bounds from a simple model, not measurements; the 2:4 bar always assumes 50%.
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:

\[ s_j^{\text{col}} = \frac{\lVert W_{:,j} \rVert^{2}}{2\, [H^{-1}]_{jj}}, \qquad \Delta W = -\frac{W_{:,j}\, \big(H^{-1}\mathbf{e}_j\big)^{\top}}{[H^{-1}]_{jj}} \tag{113.12} \]
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.

Figure 5. The layer of Figure 3 (with outlier channels), always at 50% sparsity. Filled cells are kept weights, darker for a larger Wanda score \(|w_{ij}|\lVert\mathbf{x}_j\rVert\); empty frames are removed weights. Unstructured and 2:4 use the Wanda score within each row; input channels use the column score \(\lVert W_{:,j}\rVert \lVert \mathbf{x}_j \rVert\); output channels use \(\lVert \mathbf{w}_i^{\top} X \rVert\). “Re-fit” solves the least-squares problem (113.8) for the kept weights of every row, which is what a complete sequence of OBS updates reaches for a fixed mask.
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

SettingPatternWhy
One-shot compression of a served LLM on Ampere or newer GPUs2:4 with SparseGPT or Wandasparse 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 kernelsunstructured 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 onewidth and depth (Minitron, Sheared LLaMA)pruning + distillation or continued training is cheaper than training each size from scratch [Likely]
Quick depth reduction for latencylayers (ShortGPT)fewer blocks = fewer sequential steps in every token; no kernel work
Encoders (BERT-like) for search and classificationattention heads, FFN neuronsmany heads are redundant [Certain, Michel et al.]; smaller dense encoders run on CPUs
MoE modelswhole expertsthe survey lists expert pruning methods (ExpertSparsity, SEER-MoE) [Certain, survey]; see session 29
On-device video classification and action recognitionchannel pruning of the vision backbonephones and cameras have no sparse kernels; only smaller dense layers help real-time frame rates [Likely]
Video retrieval and fingerprinting embeddersstructured pruning + distillationbillions 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-RAGlayers or heads of the language model; 2:4 on the vision encoderlong 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
Pruning sets a subset of weights to zero with a mask, \(\hat W = M \odot W\) (113.1). A method chooses (1) a score that says which weights are safe to remove (magnitude, OBD, OBS, Wanda), (2) a granularity, from single weights to N:M groups, channels, heads and layers, which decides the speed-up, and (3) what happens to the kept weights: nothing, a closed-form update (OBS), or retraining. It also chooses one-shot or gradual. LLM methods are mostly one-shot with a small calibration set.
Magnitude pruning worked for AlexNet and VGG. Why does it fail for LLMs?core
Two reasons. First, the CNN results used train–prune–retrain loops: retraining repaired the damage (Han et al.: 9× and 13× fewer parameters). One-shot LLM pruning has no retraining. Second, the score ignores the input: the output is \(\sum_j w_j x_j\), and LLMs have a few input features about 100× larger than the others, so small weights on those features matter a lot. Numbers: OPT-175B collapses beyond 30% sparsity with magnitude (perplexity \(4.3 \times 10^4\) at 50% vs 8.35 dense); LLaMA-7B at 50% gives 17.29 vs 7.26 for Wanda, which adds \(\lVert \mathbf{x}_j \rVert\) to the score.
Derive the OBD saliency. What are its assumptions?core
Expand the loss around the trained weights: \(\delta L = \mathbf{g}^{\top}\delta\mathbf{w} + \tfrac12 \delta\mathbf{w}^{\top}H\delta\mathbf{w} + \dots\) (113.3). Assume a minimum (\(\mathbf{g} \approx 0\)), a quadratic loss (drop higher terms), and a diagonal Hessian (removals do not interact). Removing weight \(q\) is \(\delta\mathbf{w} = -w_q\mathbf{e}_q\), so \(\delta L = \tfrac12 H_{qq} w_q^2\) (113.4). With equal \(H_{qq}\) this is magnitude pruning. For a single removal with all else fixed the quadratic term is exact; the diagonal assumption matters when many weights are removed and their saliencies are added.
Derive the OBS update and saliency.advanced
Minimize \(\tfrac12\delta\mathbf{w}^{\top}H\delta\mathbf{w}\) subject to \(\mathbf{e}_q^{\top}\delta\mathbf{w} + w_q = 0\) (113.5). The Lagrangian gives \(H\delta\mathbf{w} = -\lambda\mathbf{e}_q\), so \(\delta\mathbf{w} = -\lambda H^{-1}\mathbf{e}_q\). The constraint gives \(\lambda = w_q/[H^{-1}]_{qq}\). Hence \(\delta\mathbf{w} = -\frac{w_q}{[H^{-1}]_{qq}}H^{-1}\mathbf{e}_q\) and \(\delta L = \tfrac12\lambda^2 [H^{-1}]_{qq} = \frac{w_q^2}{2[H^{-1}]_{qq}}\) (113.6). To remove many weights, repeat greedily and update the inverse with the rank-one formula (113.7) instead of inverting again.
When do OBD and OBS give the same answer? How big can the difference be?core
They agree when weight \(q\) is not coupled to the others (\(H\) diagonal in that row and column), because then \([H^{-1}]_{qq} = 1/H_{qq}\) and the OBS update moves nothing. In general \([H^{-1}]_{qq} \ge 1/H_{qq}\), so OBS saliency ≤ OBD saliency. In two dimensions, \(s^{\text{OBS}} = s^{\text{OBD}}(1-\rho^2)\), where \(\rho\) is the correlation implied by \(H\): with \(\rho = 0.9\) OBS loses 5.3× less (worked example: 0.077 vs 0.405). Strongly correlated inputs, common in LLM layers, make the repair worth a lot.
Why can you not run OBS on a 7B model directly? What do LLM methods do instead?advanced
The full Hessian has \(N^2 = 4.9 \times 10^{19}\) entries (196 EB in FP32), and the loss Hessian is not even available cheaply. LLM methods prune one linear layer at a time and minimize the layer output error \(\lVert WX - \hat W X\rVert_F^2\) on calibration inputs (113.8). Then \(H = 2XX^{\top}\) is exact, small (\(d_{\text{col}}^2\), 67 MB in FP32 for 4096) and shared by all rows. Even so, exact greedy OBS costs about \(1.4 \times 10^{14}\) multiply-adds for one 4096 × 4096 layer at 50%, because each row needs its own sequence of inverses; SparseGPT reorders the work so the rows share one sequence.
Show that the Wanda score is OBD for the layer-wise problem.advanced
With \(H = 2XX^{\top}\), \(H_{jj} = 2\lVert\mathbf{x}_j\rVert^2\), where \(\mathbf{x}_j\) holds the values of input channel \(j\) over the calibration set. The OBD saliency is \(\tfrac12 H_{jj} w_{ij}^2 = (|w_{ij}|\,\lVert\mathbf{x}_j\rVert_2)^2\) (113.9). Its square root is the Wanda score \(|W| \cdot \lVert X \rVert_2\), compared within each output row. Like OBD, Wanda does not update the kept weights. That is why it needs one forward pass and seconds, while SparseGPT (OBS-like) takes minutes to hours.
Your 50% unstructured sparse model is not faster. Why?core
Dense kernels do not skip zeros, so nothing changes unless you store the matrix in a sparse format and use a sparse kernel. In decode (memory-bound) the gain is the ratio of bytes (113.10): CSR with 16-bit indices needs 4 bytes per non-zero, so at 50% it is exactly the dense size (1.0×); a bitmask gives at most 1.78×. Irregular access lowers this further. In prefill (compute-bound) tensor cores multiply dense tiles, so unstructured zeros save no math. Real gains need high sparsity with a kernel like Flash-LLM, or a hardware pattern like 2:4, or structured pruning.
What is 2:4 sparsity, and what speed-up does it give in practice?core
In every group of 4 consecutive weights, at most 2 are non-zero. NVIDIA sparse tensor cores (Ampere and later) store the 2 values plus 2-bit indices (1.125 bytes per weight in FP16) and skip the zeros: twice the dense math throughput. Measured: about 1.6× for LLaMA-65B linear layers and 1.24× end-to-end for LLaMA-7B (Wanda paper). The cost is accuracy, because the pattern is forced in every group: LLaMA-7B Wanda perplexity 7.26 at 50% unstructured but 11.53 at 2:4.
Structured or unstructured pruning: what is the trade-off, and how do you recover accuracy?core
Structured pruning (channels, heads, layers) gives a smaller dense model, so the speed-up is real on any hardware and in both memory and compute. But it removes important weights together with unimportant ones in the same unit, so at the same sparsity it loses more (structured masks are a subset of all masks). In Figure 5 the error at 50% is 0.0280 unstructured vs 0.0725 for input channels without update. Recovery: LoRA fine-tuning (LLM-Pruner), continued pre-training (Sheared LLaMA), or distillation from the dense model (Minitron). Use structured pruning as a starting point for training a smaller model; use unstructured or 2:4 for cheap one-shot compression.
Pruning or quantization first, for a memory-bound decode workload?advanced
Compare bytes. 4-bit weight quantization cuts the bytes 4× (plus small scale overhead) with a mature kernel ecosystem and small loss at 7B and above. 50% unstructured sparsity cuts them at most 1.78× with a bitmask and needs special kernels; 2:4 gives 1.78× in memory with more loss. So for bytes, quantization is usually the first step. [Likely, standard practice] They compose: the zeros can stay zeros after quantization, and SparseGPT showed that joint pruning and quantization runs in one pass. Structured pruning is the one that also cuts compute, which matters for prefill-heavy or batch-heavy workloads.

Exercises

  1. 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?
  2. 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\).
  3. 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?
  4. At what sparsity does a bitmask format start to use fewer bytes than dense FP16? And CSR with 16-bit indices?
  5. 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?
  6. ShortGPT removes 9 of the 32 blocks of LLaMA-2-7B. Ignoring the embedding and output layers, what is the ideal decode speed-up?
  7. 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
1. Magnitude removes \(w_1\) (\(0.2 \lt 0.6\)): loss rise \(\tfrac12 \cdot 10 \cdot 0.04 = 0.2\). OBD compares 0.2 with \(\tfrac12 \cdot 1 \cdot 0.36 = 0.18\) and removes \(w_2\): loss rise 0.18. With a diagonal \(H\), OBS gives the same as OBD. 2. \(H^{-1} = \tfrac13 \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}\), \([H^{-1}]_{11} = 2/3\). OBD: \(\tfrac12 \cdot 2 \cdot 1 = 1\). OBS: \(1/(2 \cdot 2/3) = 0.75\). Update: \(\delta\mathbf{w} = -\tfrac{1}{2/3} \cdot (2/3, -1/3) = (-1, 0.5)\), new weights \((0, 1.5)\), loss rise 0.75. 3. Dense: \(4096^2 \times 2 = 33.55\) MB. CSR: \(0.3 \times 4 = 1.2\) bytes per weight, 20.13 MB, at best 1.67×. Bitmask: \(0.3 \times 2 + 0.125 = 0.725\) bytes, 12.16 MB, at best 2.76×. 4. Bitmask: \(2(1-s) + 1/8 \lt 2\) when \(s \gt 1/16 = 6.25\%\). CSR: \(4(1-s) \lt 2\) when \(s \gt 50\%\). 5. \(11{,}008^2 \times 4 = 484.7\) MB (242.4 MB in FP16): still small compared with the model, and computed once per layer. 6. \(32/23 = 1.39\times\) at best, since each block reads the same number of weight bytes. 7. In 2D, \([H^{-1}]_{22} = H_{11}/\det H = H_{11}/(H_{11}H_{22} - H_{12}^2)\). So \(s_2^{\text{OBS}} = \frac{w_2^2 (H_{11}H_{22} - H_{12}^2)}{2H_{11}} = \tfrac12 H_{22} w_2^2 \big(1 - \frac{H_{12}^2}{H_{11}H_{22}}\big) = s_2^{\text{OBD}}(1-\rho^2)\).

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

\[ \hat W = M \odot W, \quad s = 1 - \frac{\lVert M\rVert_0}{N}, \qquad \delta L \approx \tfrac12\, \delta\mathbf{w}^{\top} H\, \delta\mathbf{w} \]
\[ s_q^{\text{OBD}} = \tfrac12 H_{qq} w_q^2, \qquad s_q^{\text{OBS}} = \frac{w_q^2}{2[H^{-1}]_{qq}}, \qquad \delta\mathbf{w} = -\frac{w_q}{[H^{-1}]_{qq}} H^{-1}\mathbf{e}_q \]
\[ H = 2XX^{\top}, \qquad s_{ij}^{\text{Wanda}} = |w_{ij}|\,\lVert\mathbf{x}_j\rVert_2, \qquad \text{speed-up}_{\text{decode}} \le \frac{b_{\text{dense}}}{(1-s)\,b_{\text{nz}} + b_{\text{meta}}} \]

References for this session

  1. Hassibi & Stork (1993). Second order derivatives for network pruning: Optimal Brain Surgeon
  2. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models
  3. LeCun, Denker & Solla (1990). Optimal Brain Damage
  4. Hassibi & Stork (1993). Second order derivatives for network pruning: Optimal Brain Surgeon
  5. Han, Pool, Tran & Dally (2015). Learning both Weights and Connections for Efficient Neural Networks
  6. Zhu & Gupta (2017). To prune, or not to prune: exploring the efficacy of pruning for model compression
  7. Frankle & Carbin (2018). The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks
  8. Frantar & Alistarh (2023). SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot
  9. Sun et al. (2023). A Simple and Effective Pruning Approach for Large Language Models (Wanda)
  10. Frantar & Alistarh (2022). Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning
  11. Mishra et al. (2021). Accelerating Sparse Deep Neural Networks
  12. Xia, Zheng, Li et al. (2023). Flash-LLM: Enabling Cost-Effective and Highly-Efficient Large Generative Model Inference with Unstructured Sparsity
  13. Michel, Levy & Neubig (2019). Are Sixteen Heads Really Better than One?
  14. Men, Xu, Zhang et al. (2024). ShortGPT: Layers in Large Language Models are More Redundant Than You Expect
  15. Ashkboos et al. (2024). SliceGPT: Compress Large Language Models by Deleting Rows and Columns
  16. Ma et al. (2023). LLM-Pruner: On the Structural Pruning of Large Language Models
  17. Xia et al. (2023). Sheared LLaMA: Accelerating Language Model Pre-training via Structured Pruning
  18. Muralidharan et al. (2024). Compact Language Models via Pruning and Knowledge Distillation (Minitron)
  19. Zhou, Ning, Hong et al. (2024). A Survey on Efficient Inference for Large Language Models