Why prune: energy, definition and formulation

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).