Pruning and sparsity I

Suppose you have a trained object detector that is accurate on your validation set but will not fit on the board you are targeting. Before you touch a single weight, four questions need answers, and the outline slide of this lecture is exactly that checklist. It reappears on slides 14 and 26 as a progress marker, so treat it as the map you return to as each section closes.

Pruning makes a network smaller by removing the synapses and neurons whose removal hurts performance least. That one sentence hides a sequence of design decisions. First you must formulate the problem: what exactly is being minimized, and under what budget. Then you choose the granularity, the pattern in which weights are removed, from single scattered weights up to whole channels. Then a criterion, the rule that scores which synapses or neurons are least important. Then a ratio, the target sparsity for each layer. Finally you fine-tune or retrain the pruned network so the accuracy you lost comes back.

This lecture, Pruning and Sparsity I, covers the formulation, the granularity and the criteria. The ratio and the fine-tuning belong to Pruning and Sparsity II, the next lecture. The split mirrors the two pruning lectures of the MIT course the deck is built on, and it explains why the outline slide is highlighted only at the top: the yellow marker moves down as the lecture proceeds.

Take one weight of a fully connected layer. It is fetched from off-chip DRAM and multiplied by an activation. The fetch costs 640 pJ. The 32-bit integer multiply costs 3.1 pJ. Divide them: 640 / 3.1 ≈ 206. Fetching the weight costs as much energy as about two hundred multiplies. That single ratio is the reason this lecture exists.

The numbers come from Mark Horowitz's ISSCC 2014 keynote, measured for a 45 nm process at 0.9 V, and reproduced in Han et al. (2015), which the slide follows. The full ladder is worth knowing by heart, because it is the quantitative case for every compression technique in this course. Read it top to bottom as an ordering of operations by cost, and notice that the four arithmetic rows and the register file all sit below 4 pJ while the two memory rows, SRAM and DRAM, close the table at 5 pJ and 640 pJ.

Han et al. summarize the ladder in one sentence: memory access is three orders of magnitude more energy expensive than simple arithmetic. Sze et al. make the same point in their survey: DRAM accesses require up to several orders of magnitude more energy than computation, and DRAM consumes two orders of magnitude more energy per access than a small on-chip memory of a few kilobytes. Measured against the rows of the ladder, one DRAM access costs as much as each of the following.

The slide's icon line, one DRAM stick equals 200 ×+, rounds the chart's arrow: that arrow runs from the DRAM bar to the 32-bit int MULT bar, so the 200 is 640 / 3.1 ≈ 206 rounded down. Pricing one MAC instead (3.1 + 0.1 = 3.2 pJ) gives 640 / 3.2 = 200. Either way the answer is about two hundred.

The chain from weights to watts

The slide states the consequence as a chain: data movement, more memory references, more energy. Every weight that does not fit on chip is a DRAM reference on every inference. A network with more weights moves more bytes, more bytes mean more DRAM references, and each reference costs 640 pJ. The compute, the MACs that the earlier lectures counted so carefully, turns out to be the cheap part. This is the memory access energy problem, and pruning attacks it at the root by reducing the number of weights that have to move at all.

There is a second payoff hiding in the ladder. Once a pruned model is small enough, its weights stop living in DRAM at all and sit in on-chip SRAM, where an access costs 5 pJ instead of 640 pJ. That is the argument of Deep Compression: pruning plus quantization shrinks both networks to a few megabytes, small enough to fit in on-chip SRAM cache rather than off-chip DRAM.

Separately, benchmarking the pruned fully connected layers on CPU, GPU and mobile GPU measured 3x to 7x less energy per layer. Fewer weights is the first win; crossing the SRAM boundary is the second.

The slide's before-and-after picture, taken from Han et al. (2015), is a small fully connected network with layers of 5, 4, 3 and 2 nodes. Count the edges: 5 × 4 + 4 × 3 + 3 × 2 = 20 + 12 + 6 = 38 synapses and 14 neurons. After pruning the layers read 5, 3, 2, 2. One hidden neuron is gone from the second layer, one from the third, and most of the remaining edges have vanished. Two different things were removed, and the slide labels them with two different arrows.

A synapse is one weight w_ij, one edge between neuron j of one layer and neuron i of the next. Synapse pruning sets that single entry to zero, and the neurons at both ends survive with one fewer connection. A neuron is a node. Neuron pruning removes the node and therefore every edge incident to it at once: all of its incoming weights and all of its outgoing weights. Nothing about the neuron remains, so nothing that fed it or read from it needs to exist either.

The matrix view makes the difference concrete. A linear layer holds its weights in a matrix W of shape [out, in], one row per output neuron and one column per input neuron. Synapse pruning zeroes scattered entries of that matrix, and the matrix keeps its shape; the result is a sparse matrix that must be stored with indices to say where the survivors are. Neuron pruning deletes a whole row of this layer's W(the neuron's inputs) and the matching column of the next layer's W (its outputs); both matrices become smaller dense matrices with no bookkeeping at all. This is the seed of the granularity spectrum in Part 03: fine-grained pruning lives at the synapse end and coarse-grained pruning at the neuron end.

Han et al. describe the effect of synapse pruning on a layer in one line: this pruning converts a dense, fully-connected layer to a sparse layer. They also stress that retraining the surviving weights is critical, because zeroing connections drops accuracy immediately. Part 02 shows that curve and how fine-tuning recovers it.

• Synapse pruning: unit is one weight, neurons survive, the matrix keeps its shape but becomes sparse.
• Neuron pruning: unit is one node, all incident weights go, a row and a column disappear, matrices stay dense.
• Both reduce the number of weights that must be fetched; only the second reduces it in a shape hardware likes.

Start with a weight vector small enough to see whole: W = [0.8, -0.05, 0.3, -0.01]. It has four nonzero entries. Give yourself a budget of two. One candidate is W_P = [0.8, 0, 0.3, 0], which has exactly two nonzeros. Is it the best candidate? That depends on the training loss it produces, and the pruning formulation on the slide is precisely the question: among all weight vectors with at most two nonzeros, which one makes the loss smallest?

The left half of the slide figure is ordinary training: pick W to minimize L, with the whole dense network available. The right half adds one line. The search variable becomes W_P, the pruned weights, and a constraint limits how many of its entries may be nonzero. Everything else, the loss, the data, the architecture, is unchanged. Pruning is training with a budget.

Why the constraint needs heuristics

The L0 norm counts nonzeros, and despite its name it is not a norm at all. A norm must scale with its argument, so that doubling the vector doubles the norm. Doubling our example gives ||2W||_0 = 4 = ||W||_0, not 8. Worse, as a function of the weights it is piecewise constant: nudge any nonzero weight and the count does not change, so the gradient is zero almost everywhere and undefined exactly at zero. Louizos, Welling and Kingma state it plainly: the L0 norm of weights is non-differentiable, so it cannot be incorporated directly as a regularization term. Gradient descent, the only tool that scales to millions of weights, gets no signal from the constraint.

The constraint is also combinatorial. Choosing which N of the |W| entries survive is a subset selection. With 16 weights and a budget of 8 there are C(16, 8) = 12,870 masks to compare, each requiring a retrained loss to evaluate. With a million weights and a budget of a hundred thousand the count is astronomically large. Exact search is out of the question.

So the field replaces the exact problem by the pipeline of the first concept. A criterion assigns each weight or neuron an importance score, such as its magnitude |w|, and the least important are zeroed; that is a greedy stand-in for the search over masks. A ratio fixes N for each layer; that is the budget. Fine-tuning then re-minimizes L over the surviving entries, which is the only part gradient descent can do. The formulation is exact; everything after it is an approximation, and the quality of the approximation is what the rest of this lecture and the next are about.

From N to sparsity

In the tiny example, keeping 2 of 4 entries is 50% sparsity; the mask visual above keeps 8 of 24, which is 67%. The glossary defines the pruning ratio as the percentage of parameters pruned away, and when every zero comes from pruning the two quantities coincide.

A newborn's cortical neuron carries about 2,500 synapses. By the age of two to four the figure is near 15,000. An adult settles around 7,000. The brain grows to six times its newborn connection count, then removes more than half of that peak. Growth to a peak, then elimination: the curve on the slide is the shape of train-dense-then-prune, drawn by biology decades before anyone pruned a neural network.

This is synaptic pruning, and Han et al. invoke it in the introduction of the paper the slide follows: their method learns the network connectivity in addition to the weights, much as in the mammalian brain, where synapses are created in the first few months of a child's development, followed by gradual pruning of little-used connections, falling to typical adult values. The parallel to the pipeline is exact in shape. Overprovision (train a large dense network), score by use (the criterion), remove the weak connections (prune), and let the remaining ones strengthen (fine-tune).

Take AlexNet as Han, Pool, Tran and Dally trained it for their NeurIPS 2015 paper: 57.2% top-1 and 80.3% top-5 on ImageNet. Its first fully connected layer alone holds 38 million weights, and if you histogram them you get a narrow bell centered on zero, almost all of it inside [-0.015, 0.015] by the paper's own account. Now pick a threshold that removes the smallest half of every layer. Nothing happens to accuracy. Remove three quarters, and top-5 accuracy falls by about 2.2%. Remove four fifths, and it falls by about 4%. That single experiment is the whole of slides 7 and 8.

The rule behind it is a two-step recipe. Step one is ordinary training, but Han reads it differently: the dense network is not trained to learn final weights, it is trained to learn which connections are important. Step two removes every weight whose magnitude falls below a threshold, which the paper sets as a quality parameter times the standard deviation of that layer's weights. A dense layer becomes a sparse layer. This is Pruning at its simplest, Synapse pruning in the vocabulary of Part 01, and it is the plainest form of Magnitude-based pruning: importance is |w| and nothing else. Once connections are gone, some neurons are left with no surviving input or no surviving output. Those neurons contribute nothing and are removed too, so Neuron pruning falls out of synapse pruning for free.

The right-hand inset of slide 8 shows exactly that gap: the same bell with its center cut out, a hole of width 2t around zero, and nothing else changed. The paper's discussion of its Figure 7 describes the distribution as "centered around zero with tails dropping off quickly" before pruning, then "the center of the distribution" removed. The weights that survive have not moved. They will move in the next concept, and that movement is what retraining does.

Reading the prune-only curve

The chart on slide 8 plots top-5 accuracy loss against the Pruning ratio, the fraction of parameters pruned away, from 40% to 100% on the x axis and from +0.5% to -4.5% on the y axis. The dashed purple curve is what happens with no retraining. It sits at zero up to 50%, which the paper calls a "free lunch of reducing 2x the connections without losing accuracy even without retraining". It reaches about -1% at 67%, about -2.2% at 75%, about -4% at 80%, and leaves the chart just past 82%. Without retraining, the paper says, accuracy "begins dropping much sooner", once only a third of the connections remain.

The x axis counts what is removed, so you have to translate it into a reduction factor before you can compare with a table that reports "9x". Keeping a fraction 1 - r of the weights makes the model 1 / (1 - r) times smaller.

Where the threshold comes from

Because the criterion is magnitude, the threshold and the pruning ratio are two views of the same cut. If the weights of a layer are roughly Gaussian with standard deviation sigma, removing a fraction r means removing everything inside ±t where the Gaussian mass inside ±t equals r. That is an inverse normal lookup: t = sigma × z with z = 0.674 for 50%, z = 1.282 for 80% and z = 1.645 for 90%.

Return to the AlexNet that lost 4% at 80% pruned. Keep the mask fixed, so the removed weights stay at zero, and train the survivors again with a learning rate one hundredth of the original. The loss comes back to 0.0%. That run took 173 hours on a Titan X against 75 hours for the original training, which is why the paper says pruning is "not used when iteratively prototyping the model, but rather used for model reduction when the model is ready for deployment".

This is step three of the pipeline, and the paper is blunt about its status: retraining "learns the final weights for the remaining sparse connections. This step is critical. If the pruned network is used without retraining, accuracy is significantly impacted." The lecture calls it Fine-tuning. The green curve on slide 9 shows what it buys. It stays at zero, or a hair above, all the way to 80%, then bends: about -0.25% at 84%, about -0.9% at 88%, about -1.7% at 90%, about -4% at 93%. The paper summarizes the same curve as "with retraining we are able to reduce connections by 9x".

Two of the green points sit slightly above zero. The authors do not treat that as noise: "We believe this accuracy improvement is due to pruning finding the right capacity of the network and hence reducing overfitting." In other words, Pruning behaves like a regularizer, and an over-parameterized network can lose most of its weights and generalize a little better for it.

What retraining does to the weights

The third inset on slide 9 is the most informative picture in this part. After pruning, the histogram was a bell with a hole. After retraining it is two smooth lobes, one on each side of zero, and the whole distribution is wider. The paper's text on Figure 7 states the numbers: the original weights lived inside [-0.015, 0.015]; after retraining "the parameters form a bimodal distribution and become more spread across the x-axis, between [-0.025, 0.025]". The survivors have grown in magnitude to take over the work of the connections that were removed. Nothing has been restored; the mask still holds the pruned weights at zero.

Three rules the paper gives for retraining

• Keep the surviving weights; do not reinitialize them. The paper argues that networks contain "fragile co-adapted features" that gradient descent finds when the network is first trained but cannot find again from scratch on a sparse layout.
• Shrink dropout. Pruning has already removed capacity, so the retraining dropout D_r is scaled from the original D_o by the square root of the fraction of connections kept.
• Choose the regularizer for the stage. L1 pushes more weights toward zero and gives better accuracy straight after pruning, but L2 gives better accuracy once the survivors are retrained, so the paper uses L2 for the curves on these slides.

One more observation from the paper's sensitivity study (Figure 6) matters for your own experiments: convolutional layers are more sensitive to pruning than fully connected ones, and the first convolutional layer is the most sensitive of all, because its input has only three channels and there is little redundancy to remove. That is why the per-layer keep rates in the next concepts are so uneven.

Start from the retrained network at 80% pruned, the last green point still on the zero line, a 5x model with no loss. Now prune it again, using the retrained magnitudes, and fine-tune again. The paper describes what happens: "The leftmost dot on this curve corresponds to the point on the green line at 80% (5x pruning) pruned to 8x. There's no accuracy loss at 9x. Not until 10x does the accuracy begin to drop sharply." The red curve on slide 10 is that experiment: flat through 90%, about -0.5% at 92%, -1% at 93%, -2% at 94%, and about -4% between 95% and 96%.

This is Iterative pruning, and the paper states the rule and the payoff in one breath: "Pruning followed by a retraining is one iteration, after many such iterations the minimum number connections could be found. Without loss of accuracy, this method can boost pruning rate from 5x to 9x on AlexNet compared with single-step aggressive pruning." Each iteration is a greedy search. VGG-16 used five rounds; ResNet-50 in Han's thesis used three. The left side of slide 10 draws the loop: train connectivity, prune connections, train weights, and an arrow from train weights back to prune.

Why several small cuts beat one big cut

A single cut to 90% judges every weight by the magnitude it had in the dense network. But the previous concept showed that retraining changes those magnitudes: the survivors grow and the distribution becomes bimodal. Weights that looked expendable in the dense network may become load-bearing after the first round, and weights that looked important may shrink once their neighbours take over. Iterating lets each cut use the freshest evidence. Frankle and Carbin reach the same conclusion in a different setting: iterative pruning over n rounds, each removing p^(1/n) of what remains, "finds winning tickets that match the accuracy of the original network at smaller sizes than does one-shot pruning". The price, which they also state, is that repeated retraining is expensive.

Look at AlexNet layer by layer, as the paper's Table 4 does. Its first fully connected layer, fc6, holds 38 M weights but costs only 75 M FLOPs, because each weight is used once per image. Its second convolutional layer, conv2, holds 307 K weights but costs 448 M FLOPs, because each weight is reused at every spatial position. Add the layers up and the network splits into two worlds: the three FC layers hold 58.6 M of the 61 M parameters (96.2%, which the paper rounds to 59 M) but only about 117 M of 1.45 G FLOPs (8%), while the five conv layers hold 2.3 M parameters (3.8%) but 1.33 G FLOPs (92%).

That split explains the table on slide 11 before you read it. Pruning fc6 to 9% deletes 34.6 M parameters but only 68 M FLOPs by weight count (73 M once zero activations are skipped as well, which is how Han counts). Pruning conv2 to 38% deletes only 190 K parameters but 278 M FLOPs by weight count (300 M by Han's count). Parameter reduction is a story about FC layers; MAC reduction is a story about conv layers, and the two are pruned to very different depths.

Why the over-parameterized nets compress more

AlexNet and VGG-16 get 9x and 12x; GoogleNet, ResNet-50 and SqueezeNet get about 3.2x to 3.5x. The extra column is the reason. VGG-16's fc6 alone holds 103 M of its 138 M weights, and the paper prunes fc6 and fc7 to 4% of their size while conv layers keep 22% to 58%. GoogleNet has one FC layer of about 1 M in 7 M, ResNet-50 one of about 2 M in 25.5 M, and SqueezeNet has none at all, ending in global average pooling. Han's thesis says it directly: the pruning ratio of GoogleNet is smaller than AlexNet and VGG-16 "because convolutional layers dominate GoogleNet, and convolutional layers are much more efficient than fully connected layers". The three conv-dominated networks land in the same place, about 30% of parameters nonzero (GoogleNet 29%, SqueezeNet 31%, ResNet 29%), which is the 3.4x in the table. Their FC rows, where Neuron pruning would delete whole rows of a weight matrix, are too small to matter.

Why MAC reduction is not parameter reduction

Two mechanisms separate the two columns. The first is the split above: parameters concentrate in FC layers, which are pruned hardest, and MACs concentrate in conv layers, which are pruned least. That is how AlexNet gets 9x on parameters but 3x on MACs, and VGG-16 12x against 5x. The second is how Han counts. A multiply-accumulate is only counted as saved when it is really skipped, and it is skipped when either the weight or the input activation is zero. ReLU produces plenty of zero activations, so the FLOP column in Table 4 is roughly the weight density times the density of the layer's input activations.

Even where MACs barely fall, the parameter count is worth cutting. A 6.7 M parameter AlexNet fits in on-chip SRAM, and the paper's point from Part 01 stands: at 640 pJ per DRAM access, the energy of fetching weights dominates the energy of multiplying them.

Everything so far was an image classifier with a huge fully connected tail. NeuralTalk, Karpathy and Fei-Fei's image captioner, is a different animal: a CNN feature extractor feeding an LSTM that writes a sentence one word at a time. Han froze the CNN, pruned every LSTM weight matrix except the word-embedding table to 10% nonzeros, retrained with the original weight decay and batch size, and measured BLEU-1 to BLEU-4 on Flickr-8K. The thesis reports: "Not until pruning away 90% of the parameters does the BLEU score begin to drop sharply."

The recipe did not change. Train, cut the small weights, retrain the survivors: the same three steps, the same knee near 90%, and the same dependence on Fine-tuning, which the thesis says "plays a very important role" when it compares the retrained curve with the one that skips retraining. Slide 12 shows the qualitative check that a BLEU number cannot: the captions themselves.

At 90% the pruned model "sometimes produces the same caption, sometimes produces a different word to describe the same thing", and sometimes describes the scene differently but still correctly. Replacing "ball" with "basketball" is arguably an improvement. The fourth image is the warning. At 95% pruned, a 20x model, the sentence starts to stutter: "a red shirt and black and white black shirt" repeats a phrase and loses the word "soccer". That is what crossing the knee of the Pruning ratio curve looks like in a language model: not silence, but drift.

Take fc6 of AlexNet pruned to 9% and run it with an ordinary dense matrix kernel on a GPU. The kernel does not know the zeros are zeros. It multiplies all 38 M weight-activation pairs, 34.6 M of them by zero, and finishes in exactly the time the dense layer took. Nine times fewer parameters, zero speedup. The reduction table of two concepts ago counted what could be skipped; it did not promise that anything would be. Skipping needs either a custom engine that understands sparse formats or a sparsity pattern that commodity hardware is built for. Slide 13 shows both.

The commodity route: NVIDIA A100 and 2:4

The Ampere whitepaper defines 2:4 sparsity as a structure "that allows two non-zero values in every four-entry vector". Every group of four contiguous weights along a row keeps at most two, so the matrix is exactly half zeros, stored as the nonzero values plus a 2-bit index per survivor. That compression cuts storage and bandwidth "by almost 2x", and the Sparse Tensor Core has a matrix multiply instruction that reads the indices, gathers only the matching activations, and finishes a tile in N/2 cycles instead of N: "a 2x speedup". This is the special case N = 2, M = 4 of N:M sparsity.

How does a model get into that pattern? The whitepaper's recipe is the pipeline of this part with one constraint added: the network is "first trained using dense weights, then fine-grained structured pruning is applied, and finally the remaining non-zero weights are fine-tuned". NVIDIA's developer blog reports BERT-Large keeping its SQuAD F1 of 91.9 dense and sparse. The magnitude criterion, the mask and the retraining are all Han's; the only change is that the two smallest of every four are cut instead of the smallest 50% of the layer.

The gap between 2x and 1.5x is the gap between a peak instruction rate and a whole layer. The whitepaper says "up to 2x". NVIDIA's cuSPARSELt measurements on BERT-Large GEMM layers on an A100 give 1.3x for the projection, 1.4x for QKV and FC1, and 1.6x for FC2 over dense cuBLAS, because memory traffic for activations, the non-GEMM parts of the layer and kernel launch costs do not halve. The slide's "1.5X measured BERT speedup" is Han's summary of those numbers. Treat 1.5x as the realistic middle and 2x as the ceiling.

The custom route: engines built to skip zeros

Before 2:4 existed, the way to profit from unstructured sparsity was to build the hardware yourself. The four papers cited on slide 13 are all from Han and his students, and each makes a different thing sparse. EIE, the Efficient Inference Engine, holds the compressed model in on-chip SRAM, so the 640 pJ DRAM access from Part 01 disappears, and it skips both zero weights and the zero activations that ReLU produces, which its authors say "saves another 3x". ESE moves the same idea onto an FPGA for pruned speech-recognition LSTMs, the same recipe the previous concept applied to NeuralTalk. SpArch accelerates multiplying two sparse matrices, and SpAtten prunes tokens and attention heads at run time instead of weights.

Take a weight matrix with eight rows and eight columns, 64 weights in all, and decide to remove 24 of them. One way is to cross out rows 3, 4 and 7 completely. Another is to cross out 24 individual entries wherever the magnitude criterion of part 05 says they matter least. Both leave 40 weights and both reach a Sparsity of 24 / 64 = 37.5%. Everything else about them is different.

The unit you delete is the Pruning granularity. Deleting single weights is fine-grained, or unstructured, pruning. Deleting whole rows, columns, kernels or channels is coarse-grained, or structured, pruning. Two consequences pull in opposite directions as the unit grows. The number of masks you may choose from falls, which costs accuracy at a given Pruning ratio. The regularity of what survives rises, which is what lets ordinary hardware run the pruned layer faster.

Counting the choices

The slide calls fine-grained pruning "more flexible" and coarse-grained pruning "a subset of the fine-grained case". Both statements can be made exact by counting masks. A mask is the set of positions you zero, and the pruning problem of part 01 searches over masks for the one with the lowest loss.

Why irregular means hard to accelerate

Multiply a vector by the 5 x 8 survivor and nothing special happens. It is just a smaller dense matrix, and every BLAS routine, every tensor core and every microcontroller loop handles it at full speed. That is the slide's "easy to accelerate (just a smaller matrix!)". Now multiply by the 8 x 8 matrix with 24 holes. A dense routine still performs all 64 multiplies, 24 of them by zero, and gains nothing. To gain, you must store the 40 surviving values together with their positions, in a compressed sparse format, and let the hardware skip the zeros one by one. Mao et al. draw the same line: fine-grained sparsity scatters the tensor into isolated weights and needs custom accelerators such as EIE or SCNN to exploit it, while filter and channel sparsity is simple to accelerate on general-purpose processors because it "is equivalent to obtaining a smaller dense model" (Mao et al., 2017, section 2).

The gap is measurable. Wen et al. trained AlexNet with structured sparsity and reported average layer-wise speedups of the convolutional layers of 5.1x on CPU and 3.1x on GPU with off-the-shelf libraries, against 3.0x and 0.9x for non-structured l1 sparsity (Wen et al., 2016, Table 4). The fine-grained model had more zeros. The structured model ran faster.

What the accuracy price looks like

Because coarse units search a smaller space, they lose a little accuracy at the same density (the fraction of weights kept). Mao et al. measured this on ImageNet with the same pipeline at every granularity. The differences are small between fine and vector grains and grow as the grain reaches whole kernels; pruning entire filters "loses nearly 1% validation accuracy at the very first pruning stage" on AlexNet (Mao et al., 2017).

A linear layer's weight is a matrix, so its only structured units are rows and columns. A convolution weight is richer. Slide 17 draws one: three rows of kernels stacked vertically, two columns of kernels side by side, and each kernel a 3 x 3 grid. Count the cells and you get 3 x 2 x 3 x 3 = 54 weights.

Those four factors are the four dimensions of a convolution weight. The tensor has shape [c_o, c_i, k_h, k_w]: c_o output channels, also called filters; c_i input channels; and a kernel of height k_h and width k_w. Goodfellow, Bengio and Courville write the same object as a 4-D kernel tensor K whose element K[i, j, k, l] is the connection strength between output channel i and input channel j at a row offset of k and a column offset of l (Goodfellow et al., 2016, section 9.5). PyTorch stores Conv2d.weight with exactly the slide's ordering, (out_channels, in_channels / groups, kernel_size[0], kernel_size[1]) (PyTorch documentation).

Slicing the tensor into units

The reason the lecture stops to name the dimensions is that each way of slicing the tensor is a candidate pruning unit. Mao et al. name the slices with array notation, and reading them that way makes the counts automatic. Fix the output channel and you have a filter, a 3-D slab. Fix the output and input channel and you have one kernel, a 2-D grid. Fix a row inside that kernel and you have a 1-D vector. Fix everything and you have a single scalar weight (Mao et al., 2017, section 3.2).

Two formulas do all the work. A filter holds c_i · k_h · k_w weights, because it has one kernel per input channel. An input channel holds c_o · k_h · k_w weights, because every filter has a kernel that reads it. In the slide these are 18 and 27, and it is easy to mix them up, so picture the grid: a filter is a row of kernels, an input channel is a column of kernels.

The same counts at a realistic scale

Slide 17 is a toy so the picture fits. A VGG-style layer with 64 input and 64 output channels and 3 x 3 kernels has 64 x 64 x 9 = 36,864 weights, and the same slicing rules apply.

Removing a whole filter has a second effect that Li et al. spell out. The filter's output feature map disappears, so the next layer no longer receives that channel, and the corresponding kernels in the next layer's weight tensor disappear too. Pruning m of the n filters of a layer removes m / n of the compute in that layer and in the one after it (Li et al., 2017).

Put the two previous ideas together and the lecture's central figure appears. Slide 18 takes the same 54-weight tensor and prunes it five times, once per unit, arranging the results on an axis from irregular to regular. Read from left to right, the holes grow from single cells, to fixed shapes inside kernels, to whole rows, to whole kernels, to an entire column of kernels.

Every panel can be counted, and counting them shows something the picture hides: every panel removes between a third and two thirds of the weights, so the real difference between them is not how much Sparsity they reach but how the zeros are arranged. The fine-grained panel keeps 23 scattered weights. The pattern-based panel keeps exactly four cells in every kernel, and each kept shape is a Tetris piece (a T or an L of four cells). The vector-level panel keeps seven of the eighteen kernel rows. The kernel-level panel drops the first filter's right kernel and the second filter's left kernel. The channel-level panel drops the whole second input channel across all three filters, and what survives is a dense [3, 1, 3, 3] tensor.

The ladder, rung by rung

Mao et al. organise four grains (fine, vector, kernel, filter) by how many dimensions each unit spans. The slide keeps their order, inserts pattern-based pruning between fine-grained and vector-level, and shows the 3-D rung as an input channel instead of Mao's filter (Mao et al., 2017, section 3.2). At the bottom, fine-grained pruning removes 0-D scalars anywhere. Pattern-based pruning keeps a small catalogue of fixed shapes inside each kernel, which the slide calls "like Tetris": the hardware knows the finite set of masks in advance instead of facing arbitrary holes. Niu et al. describe it as "fine-grained pruning patterns inside the coarse-grained structures" and, by compiling specialised code per pattern, ran networks on mobile CPUs and GPUs up to 44.5x faster than TensorFlow Lite and up to 11.4x faster than TVM with no accuracy loss (Niu et al., 2020). Vector-level pruning removes 1-D rows, W[o, i, r, :], of a kernel. Kernel-level pruning removes 2-D kernels, W[o, i, :, :]. At the top, channel pruning removes a 3-D slab: on the slide, an input channel W[:, i, :, :] across every filter.

The right-hand column is the practical half of the story. Only the channel and filter rungs run faster on unmodified dense libraries, because the tensor simply shrinks. Kernel and vector sparsity line up with 2-D and 1-D convolution primitives (Winograd, Eyeriss-style 1-D units), which makes custom hardware simpler, but Mao et al. note they are still hard to accelerate on general-purpose processors. Pattern-based pruning needs compiler support (PatDNN) or dedicated support such as NVIDIA's 2:4 sparse tensor cores, and fine-grained sparsity needs accelerators such as EIE (Mao et al., 2017, section 6).

Try every rung on one tensor

The simulator below holds a random [3, 2, 3, 3] tensor and lets you prune it with any of the six units, including the filter unit that Mao et al. list alongside channels. It groups the weights by the chosen unit, scores each group with the L1 or L2 magnitude that part 05 develops, zeros the weakest groups until the target is met, and reports what survives. Watch three things as you switch units: the achieved sparsity snaps to coarser steps, the index count collapses as units grow, and only the channel and filter units ever produce a smaller dense tensor.

The energy argument from part 01 also runs along this axis. Mao et al. simulated the SCNN sparse accelerator on VGG-16 and found that, at the same density, vector-level sparsity needs 30 to 35% fewer output memory references than fine-grained sparsity. Neighbouring surviving weights in a row write to the same output address, so SCNN can skip the repeated read and write of that address (Mao et al., 2017, section 6 and Table 4). Since a DRAM access costs about two hundred times a multiply, fewer memory references is where the energy goes, not fewer multiplies.

Go back to the very first picture of this lecture: a network before and after pruning, with individual synapses cut out while every neuron stays. That picture is fine-grained pruning, the synapse pruning of slide 4 seen through the lens of granularity. Slides 19 and 20 bring it back only to attach numbers to it, so treat them as a short callback rather than new material.

The numbers are the ones from part 02. Han et al. pruned AlexNet from 61 M to 6.7 M parameters and VGG-16 from 138 M to 10.3 M without losing accuracy, a pruning ratio of roughly 89% and 93% (Han, Pool, Tran and Dally, NIPS 2015). Those results are only possible because the method may zero any single weight, wherever it sits in the tensor. The slide calls this "flexible pruning indices": the set of surviving positions is unconstrained, so the algorithm can find redundant weights anywhere and usually reaches the largest compression ratio of all granularities.

Why flexibility is expensive at run time

Now look at what the flexibility leaves behind. After fine-grained pruning the weight tensor still has its original shape; it is simply riddled with zeros at irregular positions. A dense matrix multiply on a GPU does not know the zeros are there and multiplies them anyway, so the work is unchanged. To skip them you must store the weights in a sparse format such as CSR, CSC or COO, where every surviving value carries an index saying where it belongs. Mishra et al. note that these formats make memory accesses data dependent and that the index metadata can cost up to 200% of the weight storage when the weights are 8-bit (Mishra et al., 2021). Zhou et al. summarize the situation in one line: fine-grained sparsity "can achieve a high compression ratio but is not hardware friendly and hence receives limited speed gains" (Zhou et al., ICLR 2021).

That is why the red line on slide 20 matters more than the table. Speedup from fine-grained sparsity needs hardware built around indices. Han's own EIE accelerator is the example the MIT source deck names: by reading compressed weights and skipping zero activations, it ran fully-connected layers 189x faster than a CPU and 13x faster than a GPU running the uncompressed network (Han et al., ISCA 2016). With sparse kernels the picture depends on batch size: in EIE's own measurements cuSPARSE ran pruned FC layers 4x to 9x faster than dense at batch 1 on a Titan X, but slower at batch 64, which is why the slide says "not GPU (easily)". On an ordinary GPU with dense kernels, the same pruned network runs at roughly dense speed.

Take one row of eight FP16 weights and split it into two groups of four. In each group keep the two largest magnitudes and zero the other two. Every group now has exactly two zeros and two nonzeros, so the row is 50% sparse, and so is every other row treated the same way. That is 2:4 sparsity, the classic case of N:M sparsity and the reason the lecture lists pattern-based pruning as its own step on the granularity spectrum.

The general rule needs one careful sentence, because the slide's sentence is ambiguous. In NVIDIA's definition, which is the one hardware implements, an N:M pattern allows at most N nonzero values in every contiguous group of M. The Ampere whitepaper describes 2:4 as a matrix "that allows two non-zero values in every four-entry vector", and Mishra et al. write of "the 2 nonzero values in each group of 4" (NVIDIA, 2020; Mishra et al., 2021). Slide 21 instead says that "N of them is pruned". For 2:4 the two readings agree, since two kept and two pruned are the same thing. For any other pattern they do not.

Why a pattern is the middle of the spectrum

Inside each group of four the pattern is still fine-grained: any two of the four positions may survive, six possible masks, chosen by magnitude. Across the matrix it is rigidly structured: every group holds exactly two values, no more and no fewer. Mishra et al. point out what this buys: because the sparsity is constant across the matrix, "there is no indirection required; a nonzero value's position in memory can be determined from the compression rate directly" (Mishra et al., 2021). The hardware always knows that group g starts at value slot 2g. That is the difference between a lookup and an address calculation, and it is what makes fine-grained-in-the-small, structured-in-the-large worth a place of its own.

The compressed format

The rule also fixes the storage layout, which is the right-hand panel of slide 21. An R by C dense matrix becomes an R by C/2 block of nonzero values plus an R by C/2 block of 2-bit indices, where each index records the position, 0 to 3, of a kept value inside its group of four. Two bits are enough because a group has only four positions. One corner case keeps the format regular: if a group happens to have three or four zeros after training, two values are stored anyway, padded with zeros as needed (Mishra et al., 2021).

The two tables carry an insight that matters when you combine pruning with the quantization lectures: the index costs two bits whatever the value width, so the narrower the value type the more the index costs relatively. Mishra et al. give the same figures, about 44% saved for 16-bit and about 38% for 8-bit weights, which is why NVIDIA says the format cuts storage and bandwidth by "almost" 2x rather than exactly 2x (Mishra et al., 2021; NVIDIA, 2020).

Where the 2x speedup comes from

Storage is only half of the payoff. The Ampere A100 added Sparse Tensor Core instructions that take a 2:4 compressed operand and, in the whitepaper's words, "skip the compute on entries that have zero values, resulting in a doubling of the Tensor Core compute throughput": a 16 x 8 x 16 matrix multiply instruction completes in half the cycles of its dense counterpart (NVIDIA, 2020). Software reaches it through TensorRT 8 and cuSPARSELt; the slide's link covers the TensorRT 8.0 path. Zhou et al. restate the same about 2x for the A100, citing NVIDIA rather than measuring it themselves (Zhou et al., ICLR 2021).

Try the pattern yourself below. Switch the convention from "N nonzero" to "N pruned" at 2:4 and nothing changes; switch it at 1:4 and the sparsity flips from 75% to 25%, which is exactly the ambiguity flagged above. Then toggle FP16 to INT8 and watch the index overhead double.

A format that halves storage and doubles matmul throughput is worth nothing if the network gets worse. So look at one row first: ResNet-50 on ImageNet scores 76.1% top-1 dense in FP16 and 76.2% after 2:4 pruning. Half the weights are gone and the accuracy is unchanged; the extra 0.1 is run-to-run noise, not a gain.

The rule that produced that row is NVIDIA's three-step recipe. Train the dense network as usual. Prune it to 2:4 by keeping the two largest magnitudes in every group of four, which fixes the mask. Then retrain with the mask held fixed, using the original schedule and hyperparameters, so the survivors absorb the job of the pruned weights. That last step is the fine-tuning loop of part 02 applied under a structural constraint, and the whitepaper reports "virtually no loss in inferencing accuracy" across dozens of networks with it (NVIDIA, 2020). The choice of mask by magnitude inside each group previews the magnitude criterion of part 05.

Read the table across, never down. The seven rows use four different metrics (top-1 accuracy, box AP, BLEU and F1), so the only meaningful comparison is dense versus sparse within one row. Read that way the evidence is unusually broad: image classification, object detection, instance segmentation, translation and question answering, spanning convolutional networks and Transformers, and not one row lost measurable accuracy. The whitepaper's explanation is that after training "only a subset of weights have acquired a meaningful purpose", and the retraining step lets the network re-adapt around the fixed mask (NVIDIA, 2020).

Now the coarse end of the spectrum. A convolution layer with 64 output channels is pruned at sparsity 0.5: thirty-two whole filters are deleted and the layer becomes a 32-channel layer. Nothing about the result is sparse. Its weight tensor, in the [c_o, c_i, k_h, k_w] layout of part 03, is simply smaller in the c_o dimension, and the next layer, which consumed those channels, is smaller in its c_i dimension.

That is the whole argument for channel pruning, and both sides of the slide's trade-off follow from it. Pro: direct speedup on any hardware, because a network with fewer channels does less work in every dense library that exists. Li et al. put it precisely: removing whole filters "does not result in sparse connectivity patterns", so it "does not need the support of sparse convolution libraries and can work with existing efficient BLAS libraries" (Li et al., ICLR 2017). He, Zhang and Sun report a 5x speedup on VGG-16 for a 0.3% increase in error and 2x on ResNet for 1.4% (He, Zhang and Sun, ICCV 2017). Con: a smaller compression ratio, because a channel is a much coarser unit than a weight. Keeping a channel means keeping all of its weights, including the weak ones that fine-grained pruning would have dropped, so you cannot reach the 9x to 13x of slide 20.

Pruning one layer shrinks two

The example above hid a compounding effect that the slide's bar chart depends on. Pruning the output channels of layer l removes rows from its own weight tensor and columns from layer l+1, because the input channels of l+1 are the output channels of l. The per-layer sparsity values on slide 24 therefore do not add up the way they look; they multiply through the chain.

Uniform shrink versus channel prune

The inequality on slide 24, "Uniform Shrink < Channel Prune", compares accuracy at a comparable budget. Uniform shrink applies one ratio to every layer, which is what a MobileNet width multiplier does. It ignores the fact that layers differ in how much redundancy they carry: some tolerate 70% removal and others only 20%. Channel pruning proper starts from the trained wide network, chooses a ratio per layer, deletes the least useful channels in each, and fine-tunes. Under the same latency or MAC budget, spending the cuts where they hurt least keeps more accuracy. Slide 24 defers the obvious question, how to find those ratios; the sensitivity analysis of lecture 04-2 (Pruning ratios, fine-tuning and sparse hardware) and the AMC search of the next concept are the answers.

On a Google Pixel 1, the full-width MobileNet takes 123.3 ms per image and scores 70.6% ImageNet top-1. Shrinking it uniformly with the 0.75 width multiplier brings the latency down to 72.3 ms but the accuracy down to 68.4%. The channel-pruned model found by AMC runs in 68.3 ms at 70.5%: as fast as the shrunken model, 2.1 points more accurate, and only 0.1 below the full model at 1.81x its speed (He et al., ECCV 2018).

AMC (AutoML for Model Compression) is the method behind the red curve on slide 25. It treats the per-layer sparsity ratios as actions for a reinforcement-learning agent, which walks the network layer by layer, proposes a ratio for each, and is rewarded by the accuracy the pruned model reaches under a FLOPs or latency constraint. The pruned model is then fine-tuned. The baseline is the easiest thing one could do instead, which the paper states plainly: "the easiest way to reduce the channels of a model is to use uniform channel shrinkage, i.e. use a width multiplier", and the result is that AMC "consistently outperforms the uniform baselines" (He et al., ECCV 2018).

The chart on the slide is AMC's Figure 5b. The four table rows above are exact; the remaining points in the table below are read off the figure and are approximate. Either way the shape is the same. At equal latency the searched ratios are about 1.5 to 2 points better. At similar accuracy they are much faster: the 50% latency-budget model keeps 70.2% at 63.3 ms, 1.95x faster than the 123.3 ms full model at 70.6%, only 0.4 points higher.

Choosing a granularity for a real board

This is where the part comes together for your project. The granularity you pick is a hardware decision, not a compression decision:

• Target is an Ampere-class or newer NVIDIA GPU (a Jetson Orin, an A100): prune to 2:4. Half the weights, about 2x on the matmuls, accuracy held by retraining.
• Target is a phone CPU, a microcontroller or an NPU with dense kernels only: channel pruning with searched per-layer ratios, AMC style. A smaller dense network is the safest choice, since it needs no special kernels. Some mobile runtimes (XNNPACK) do accelerate high unstructured sparsity in 1x1 convolutions, so check what your runtime supports.
• Target has a sparse accelerator such as EIE, or the constraint is storage and not latency: fine-grained pruning, for the largest compression ratio.

Start with one neuron and three inputs. Its output is y = ReLU(10 x_0 - 8 x_1 + 0.1 x_2), and the budget says one of the three connections has to go. Removing the 10 changes the pre-activation by up to 10 |x_0|. Removing the -8 changes it by up to 8 |x_1|. Removing the 0.1 changes it by at most 0.1 |x_2|. If the three inputs are of similar size, the third cut is a hundred times gentler than the first, and that is the one to make.

That small decision contains the whole idea of a Pruning criterion. Pruning asks the network to give up parameters, and the principle the lecture states is simple: the less important the parameters being removed are, the better the performance of the pruned network is. Every criterion in this lecture is a different way of estimating importance, and importance always means the same thing underneath: how much the loss would change if this parameter, or this group, were set to zero. Magnitude, the subject of this part, is the cheapest such estimate. Second-order methods in the next part spend far more compute to estimate the same quantity more carefully (Second-order pruning).

Notice what the example needed to make the decision: nothing but the weights. No data, no gradients, no second run through the training set. That is the appeal of magnitude criteria and also their limit. They answer the Pruning formulation only approximately, because the formulation asks for the smallest increase in loss under a budget on nonzeros, and magnitude is a proxy for loss, not the loss itself. The next three sections make the proxy precise for single weights, for rows, and for whole channels.

Now scale the neuron up to a weight matrix. Take W = [[3, -2], [1, -5]] and a budget of 50 percent Sparsity, which on four weights means exactly two zeros. Write the absolute value of every entry, keep the two largest, zero the rest. The importances are [[3, 2], [1, 5]], the survivors are 3 and -5, and the pruned matrix is [[3, 0], [0, -5]].

This is Magnitude-based pruning at its finest granularity, the fine-grained case from part 03, and it is the criterion of the paper the slides cite. Han, Pool, Tran and Dally train a network, prune every connection whose weight falls below a threshold, and retrain the survivors. Done once, that took AlexNet to 5x fewer parameters; done iteratively, prune then retrain then prune again, it reached 9x on AlexNet (61M to 6.7M) and 13x on VGG-16 (138M to 10.3M) with no loss of accuracy. They also tried the obvious alternative, removing weights at random with probability tied to their magnitude, and report that it gave worse results. Hard thresholding on |w| won.

In code, this is one call. PyTorch's prune.l1_unstructured(module, name, amount) prunes a tensor by removing the units with the lowest L1 norm, and amount can be a fraction such as 0.5 or an absolute count. The name is exact: on a single element the L1 norm is just its absolute value, so element-wise L1 and |W| are the same criterion, and the slide's label "L1-norm, element-wise" is the same statement as Importance = |W|. Any other p would give the same ranking on single elements, which is why the choice of norm only starts to matter in the next section.

Keep the same matrix, [[3, -2], [1, -5]], but change the unit of removal. Instead of two individual entries, remove one whole row. A row of a linear layer's weight matrix is one output neuron's incoming connections, so deleting it is Neuron pruning, and the result is a smaller dense matrix that any library runs faster (Coarse-grained (structured) pruning). The question is how to score a row when it holds several weights of different sizes and signs.

The lecture's answer is to treat the row as a Structural set, written W^(S) for the set S of parameters it contains, and to collapse its absolute values into one number. Two collapses are standard. Add them: the L1-norm importance. Or square them, add, and take the root: the L2-norm importance. Row 0 scores |3| + |-2| = 5 under L1 and sqrt(9 + 4) = sqrt(13) = 3.61 under L2. Row 1 scores |1| + |-5| = 6 and sqrt(1 + 25) = sqrt(26) = 5.10. Both norms rank row 1 higher, so both prune row 0, and the pruned matrix is [[0, 0], [1, -5]].

One formula for every p

L1 and L2 are two settings of one dial. Goodfellow, Bengio and Courville define the Lp norm of a vector for any p ≥ 1 as the p-th root of the sum of p-th powers of the absolute values. Set p = 1 and the root and the power vanish, leaving slide 29. Set p = 2 and you get the Euclidean length of slide 30. Slide 31 is the same example under the general formula, not a new method.

When the norm changes the answer

On the slide's matrix L1 and L2 agree, and it is tempting to file the norm as a cosmetic choice. It is not. Compare a row [3, 3] with a row [0, 5] competing for the last surviving slot. L1 scores them 6 against 5 and keeps [3, 3]. L2 scores them sqrt(18) = 4.24 against 5 and keeps [0, 5]. Squaring amplifies the single largest entry, so L2 rewards a row with one dominant weight. Summing treats every unit of magnitude the same, so L1 rewards a row with many moderate weights. Goodfellow et al. describe the same contrast in general terms: the L1 norm grows at the same rate in all locations, while the squared L2 norm increases very slowly near the origin.

Try it yourself. The explorer below scores an editable matrix element-wise or row-wise, always computes both row norms so a disagreement is visible without toggling, and ships with the slide's example and the [3, 3] against [0, 5] case as presets. Change a single entry and watch which row the two norms fight over.

Where the row-wise criteria come from

The L1 row score is the criterion of Li et al. Their filter importance is the sum of the absolute kernel weights of a filter, which they describe as an expectation of the magnitude of the output feature map. They remove the m filters with the smallest sums, delete the matching input channels from the next layer, and show that pruning the smallest works better than pruning at random or pruning the largest. On CIFAR-10 this cut inference cost by up to 34 percent for VGG-16 and 38 percent for ResNet-110 with retraining recovering the accuracy. Because a filter is a structural set, this filter pruning is Channel pruning from part 04 with an explicit score attached.

The L2 row score is what Wen et al. put inside training. Their structured sparsity learning adds a group Lasso regularizer to the loss, a sum over groups of sqrt(sum of squared weights in the group), which is exactly the L2 norm of each structural set. The optimizer is then rewarded for driving whole filters, channels, filter shapes or even layers to zero, and they report 5.1x CPU and 3.1x GPU speedups on AlexNet's convolutional layers, and a ResNet on CIFAR-10 shrunk from 20 to 18 layers with accuracy moving from 91.25 to 92.60 percent, still above the original 32-layer ResNet. The difference between the two papers is when the norm is used: Li et al. score a trained network after the fact, Wen et al. shape the network during training so the sets to remove are already near zero.

PyTorch exposes the post-hoc version directly. prune.ln_structured(module, name, amount, n, dim) removes the channels with the lowest Ln norm along the specified dimension; n = 1 or 2 picks the norm, and dim = 0 on a weight of shape [c_o, c_i, k_h, k_w] scores whole filters. Finer structural sets such as a row inside a kernel (Vector-level pruning) use the same formula on a smaller S.