COE 592Lecture 4.1Reference

Reference sheet

Pruning and sparsity I compressed onto one page: the definitions, formulas and numbers to have in your head before a quiz or exam.

The pruning pipeline

Pruning removes the synapses and neurons whose removal hurts performance least. It is a pipeline of one formulation and four decisions, split across two lectures. Part 01: Why prune

Decision	Question	Where it is taught
Formulate	What is pruning and how is it written down?	Part 01
Granularity	In what pattern should weights be removed?	Parts 03 and 04
Criterion	Which synapses or neurons should go?	Parts 05 and 06
Ratio	What target sparsity per layer?	Lecture 04-2
Fine-tune	How is the lost accuracy recovered?	Part 02 previews it; Lecture 04-2

Formulate, then four decisions

The memory energy wall

Horowitz ISSCC 2014, 45 nm at 0.9 V, via Han et al. 2015. Memory access is three orders of magnitude more expensive than arithmetic. Part 01: Why prune

Rough energy per 32-bit operation

32-bit int ADD: 0.1 pJ
32-bit float ADD: 0.9 pJ
32-bit register file: 1 pJ
32-bit int MULT: 3.1 pJ
32-bit float MULT: 3.7 pJ
32-bit SRAM cache: 5 pJ
32-bit DRAM memory: 640 pJ

Ratio	Value	Meaning
DRAM / int MULT	640 / 3.1 ≈ 206	About two hundred multiplies per fetch
DRAM / int MAC	640 / 3.2 = 200	The slide's 200x icon line
DRAM / int ADD	640 / 0.1 = 6400	Relative to the cheapest operation
DRAM / SRAM	640 / 5 = 128	The payoff of fitting the model on chip

The four ratios to quote

\frac{E_{\text{DRAM}}}{E_{\text{int MULT}}} = \frac{640\ \text{pJ}}{3.1\ \text{pJ}} \approx 206

One weight fetch buys about two hundred multiplies

Synapse versus neuron pruning

Six weights removed as synapses and six removed as a neuron count the same and look completely different to the hardware. A 3 × 4 layer feeding 2 × 3: prune neuron 2 and row 2 (4 weights) plus column 2 of the next layer (2 weights) vanish, leaving dense 2 × 4 and 2 × 2. Part 01: Why prune

Aspect	Synapse pruning	Neuron pruning
Unit	One weight w_ij	One node
What survives	Both endpoint neurons	Nothing of the node
Matrix effect	A zero inside a same-shape matrix	Row deleted here, column deleted in the next layer
Result	Sparse, needs indices	Smaller dense matrices
Granularity end	Fine-grained	Coarse-grained

Two units of removal

Pruning as constrained optimization

\underset{\mathbf{W}}{\arg\min}\; L(\mathbf{x};\, \mathbf{W})

Ordinary training

\underset{\mathbf{W}_P}{\arg\min}\; L(\mathbf{x};\, \mathbf{W}_P) \quad \text{s.t.} \quad \lVert \mathbf{W}_P \rVert_0 \le N

Pruning: the same loss, at most N nonzeros. Write less-or-equal, not the slide bullet's strict less-than

Every symbol

L: The training loss, unchanged from ordinary training
x: The input data the loss is evaluated on
W: The original dense weights
W_P: The pruned weights, the search variable
||W_P||_0: The count of nonzeros, the L0 pseudo-norm
N: The budget: target number of nonzeros

\text{sparsity} = 1 - \frac{N}{|\mathbf{W}|}

AlexNet: 1 - 6.7 / 61 = 0.89, so 89% sparsity and 9x fewer parameters

The brain prunes too (slide 6, illustrative values)

Newborn: about 2,500 synapses per neuron
2 to 4 years: peak, about 15,000
Adult: about 7,000
Eliminated: (15,000 - 7,000) / 15,000 ≈ 53%

Train, prune, retrain

Train the dense network to learn which connections matter, prune every weight below a magnitude threshold, retrain the survivors with the mask fixed. Retraining is the step the paper calls critical. Part 02: Prune, fine-tune, results

k = \frac{1}{1 - r} \qquad r = 1 - \frac{1}{k}

Reduction factor k from pruning ratio r (the axis counts what is removed)

Anchor points

50% pruned: 2x
67% pruned: 3x
75% pruned: 4x
80% pruned: 5x
87.5% pruned: 8x
88.9% pruned: 9x
90% pruned: 10x

Pruning ratio	Prune only	Prune + fine-tune	Iterative
50% (2x)	0% (free lunch)	0%	not needed
80% (5x)	about -4%	0%	starting point
90% (10x)	off the chart	about -1.7%	about 0%
93% (14x)	off the chart	about -4%	about -1%

AlexNet top-5 accuracy loss, read from slides 8 to 10

t = \sigma \cdot z_r

Threshold for a Gaussian layer: z is the inverse-normal for the fraction r inside ±t. Han sets t as a quality parameter times the layer's std

Pruned	z	t
50%	0.674	0.020
80%	1.282	0.038
90%	1.645	0.049

Threshold for sigma = 0.03

D_r = D_o \sqrt{\frac{C_{ir}}{C_{io}}}

Retraining dropout: fc6 kept at 9% with D_o = 0.5 gives 0.5 × 0.3 = 0.15

Parameters versus MACs

Network	Before	After	Parameter reduction	MAC reduction	FC share of params
AlexNet	61 M	6.7 M	9x	3x	96.2%
VGG-16	138 M	10.3 M	12x (paper 13x)	5x	89.9%
GoogleNet	7 M	2.0 M	3.5x	5x	about 14%
ResNet-50	26 M	7.47 M	3.4x	6.3x	about 8%
SqueezeNet	1 M	0.38 M	3.2x	3.5x	0%

Slide 11 plus the FC share that explains it

Layers	Parameters	FLOPs	Kept after pruning
FC layers (fc6 to fc8)	58.6 M (96.2%)	117 M (8%)	9% to 25%
Conv layers (conv1 to conv5)	2.3 M (3.8%)	1.33 G (92%)	35% to 84%

AlexNet splits into two worlds

\text{FLOP\%} \approx \text{Weight\%} \times \text{Act\%}_{\text{in}}

A MAC survives only if both operands are nonzero. conv2: 0.38 × 0.88 = 33%. fc6: 0.09 × 0.34 = 3%

Sparsity needs hardware

A dense kernel multiplies zeros like any other value, so fc6 at 9% density still executes all 38 M MACs. Speed needs an engine built for sparse formats or a pattern commodity hardware knows. Part 02: Prune, fine-tune, results

System	Venue	What is sparse	Headline
EIE	ISCA 2016	Pruned FC weights and zero activations, model in SRAM	189x CPU, 13x GPU, 24000x energy vs CPU
ESE	FPGA 2017	Pruned LSTM weights for speech	43x Core i7, 3x Titan X, 282 GOPS
SpArch	HPCA 2020	Sparse matrix times sparse matrix	2.8x fewer DRAM accesses, 4x over OuterSPACE
SpAtten	HPCA 2021	Tokens and heads of attention	10x less DRAM traffic, 162x over Titan Xp
A100 Sparse Tensor Core	NVIDIA 2020	Any matrix in the 2:4 pattern	up to 2x peak, 1.3x to 1.6x measured on BERT-Large layers

Slide 13 hardware, headline from each abstract

Granularity: the trade

The unit you delete is the granularity. Small units give more masks to choose from, so higher sparsity at equal accuracy. Large units give a regular survivor that dense hardware runs. Coarse masks are a subset of fine masks, so structured pruning can tie but never beat unstructured at equal accuracy. Part 03: Granularity spectrum

Removing 24 of 64 weights, two ways

Weights removed: 24 of 64 (37.5%)
Fine-grained masks: C(64, 24) ≈ 2.5 x 10^17
Row-structured masks: C(8, 3) = 56
Survivor, fine-grained: 8 x 8 with 24 holes, one index per survivor
Survivor, row-structured: 5 x 8 dense, no indices

Network	Density kept	Fine-grained	Vector-level	Kernel-level
AlexNet	24.8%	80.41%	79.94%	79.20%
VGG-16	23.5%	90.56%	90.48%	89.70%
ResNet-50	40.0%	92.34%	92.26%	92.07%

Top-5 ImageNet accuracy at equal density (Mao et al. 2017, Table 1)

The convolution weight tensor

N = c_o \cdot c_i \cdot k_h \cdot k_w

Shape [c_o, c_i, k_h, k_w]; slide 17 has 3 × 2 × 3 × 3 = 54 weights, 3 filters and 6 kernels

Unit	Slice	Weights	Share of 54
Single weight	W[o, i, r, c]	1	1.9%
Row inside a kernel	W[o, i, r, :]	k_w = 3	5.6%
Kernel	W[o, i, :, :]	k_h x k_w = 9	16.7%
Filter (output channel)	W[o, :, :, :]	c_i x k_h x k_w = 18	33.3%
Input channel	W[:, i, :, :]	c_o x k_h x k_w = 27	50.0%

Units inside the 54-weight tensor

Granularity	Unit	Index cost	Runs efficiently on
Fine-grained	Any single weight (0-D)	One index per survivor	Custom engines: EIE, SCNN
Pattern-based	Fixed mask inside each kernel	One pattern id per kernel	Pattern-specialised compilers (PatDNN)
Vector-level	A row of a kernel (1-D)	One index per surviving row	1-D conv primitives (Eyeriss)
Kernel-level	A whole k_h x k_w kernel (2-D)	One index per surviving kernel	2-D conv primitives, Winograd
Channel-level	An input channel across all filters (3-D)	None: the tensor shrinks	Any dense CPU or GPU library

From irregular to regular (Mao et al. 2017)

N:M sparsity and the 2:4 pattern

NVIDIA convention: at most N nonzeros in every contiguous M weights. Two zeros in every four is 2:4, exactly 50% sparse, fine-grained inside each group (six possible masks) and rigidly structured across the matrix, so a survivor's address is computed, not looked up. Part 04: Fine, pattern, channel

s = 1 - \frac{N}{M}

Sparsity of an N:M pattern under the N-nonzero convention

Pattern	N nonzero per M (NVIDIA)	N pruned per M (slide)
2:4	50%	50%
1:4	75%	25%
2:8	75%	25%
4:8	50%	50%

The slide's wording inverts the convention

Item	FP16	INT8
Dense	1024 bits	512 bits
Kept values (half)	512 bits	256 bits
2-bit indices	64 bits	64 bits
Compressed total	576 bits	320 bits
Ratio	1.78x (43.75% saved)	1.6x (37.5% saved)
Index overhead on kept values	12.5%	25%

Compressing an 8 × 8 matrix to 2:4: half the values plus a 2-bit index per survivor

Network	Metric	Dense FP16	Sparse FP16
ResNet-50	ImageNet top-1	76.1	76.2
BERT-Large	SQuAD v1.1 F1	91.9	91.9
FairSeq Transformer	WMT'14 EN-DE BLEU	28.2	28.5
MaskRCNN-RN50	COCO 2017 bbAP	37.9	37.9

Train, magnitude-prune to 2:4, retrain with the same schedule (NVIDIA)

Fine-grained, 2:4 and channel pruning compared

Granularity	Compression	Speedup
Fine-grained	Largest (AlexNet 9x, VGG-16 13x)	None on dense GPU kernels; needs EIE-class hardware
2:4 pattern	Fixed at 50% (about 1.78x storage)	Up to 2x matmul on Ampere Sparse Tensor Cores
Channel	Smallest, weak weights survive with the channel	Direct on any hardware: a smaller dense network

Compression versus speed

Pruning the output channels of layer l also removes input columns of layer l+1, so layer l keeps (1 - s_(l-1)) × (1 - s_l) of its weights and the same fraction of its MACs.

Layer	Uniform 0.3	Uniform 0.4	Per-layer
Layer 0	0.70	0.60	0.50
Layers 1 to 4	0.49 each	0.36 each	0.35, 0.21, 0.24, 0.56
Total kept	53.2%	40.8%	37.2%

Five 64-channel conv layers: kept fraction under uniform shrink and the slide's per-layer set 0.5, 0.3, 0.7, 0.2, 0.3

Model	MMACs	Top-1	Latency	Speedup
MobileNet 1.0 (full width)	569	70.6%	123.3 ms	1.00x
MobileNet 0.75 (uniform shrink)	325	68.4%	72.3 ms	1.7x
AMC, 50% FLOPs budget	285	70.5%	68.3 ms	1.81x
AMC, 50% latency budget	272	70.2%	63.3 ms	1.95x

AMC versus uniform width multiplier, MobileNet on a Pixel 1 (AMC Table 4)

Choosing a granularity for a board

Ampere-class NVIDIA GPU (Jetson Orin, A100): Prune to 2:4: half the weights, about 2x on the matmuls, accuracy held by retraining.
Phone CPU, microcontroller, dense-only NPU: Channel pruning with searched per-layer ratios, AMC style. A smaller dense network is the only sparsity such hardware feels.
Sparse accelerator, or storage is the constraint: Fine-grained pruning for the largest compression ratio.

Magnitude criteria

A criterion estimates importance: how much the loss would change if this parameter or group were zeroed. The less important the removed parameters, the better the pruned network. Magnitude uses the absolute value, never the signed weight: -5 outranks 3. Part 05: Magnitude and scaling criteria

\text{Importance} = |W|

Element-wise. The removed term is really |w_i| |x_i|, so compare within a layer, never across layers

\big\lVert W^{(S)} \big\rVert_p = \Big(\sum_{i \in S} |w_i|^p\Big)^{1/p}

Lp norm of a structural set S. p = 1 sums absolute values (Li et al.), p = 2 is the Euclidean length (Wen et al. group Lasso)

Criterion	Row 0 score	Row 1 score	Row pruned	Pruned matrix
Element-wise \|w\|	not a row score	not a row score	none (two smallest elements)	[[3, 0], [0, -5]]
Row-wise L1	5	6	row 0	[[0, 0], [1, -5]]
Row-wise L2	sqrt(13) = 3.61	sqrt(26) = 5.10	row 0	[[0, 0], [1, -5]]

[[3, -2], [1, -5]] at 50% sparsity

Row	L1	L2
[3, 3]	6	sqrt(18) = 4.24
[0, 5]	5	5
Row kept	[3, 3]	[0, 5]

When the norm changes the answer

Scaling-based pruning and batch norm gamma

L = \sum_{(x, y)} \ell\big(f(x, W), y\big) + \lambda \sum_{\gamma \in \Gamma} |\gamma|

Network slimming: an L1 penalty pushes every channel factor toward zero; prune small |gamma| below a global percentile

z_o = \gamma \, \frac{z_i - \mu_{\mathcal{B}}}{\sqrt{\sigma^2_{\mathcal{B}} + \epsilon}} + \beta

Batch normalization already supplies one gamma per channel, free

Network slimming (Liu et al. 2017)

Penalty: lambda = 1e-4 (VGGNet), 1e-5 (ResNet, DenseNet) on CIFAR
Threshold: One global percentile over every gamma in the network; per-layer ratios fall out automatically
VGGNet CIFAR-10, 70% channels pruned: error 6.34% to 6.20%, params 20.04 M to 2.30 M, FLOPs 7.97e8 to 3.91e8
Why gamma: Already there, one per channel, no new parameters; BN fixes the activation scale so gamma alone measures the channel

Second-order pruning: OBD

Pruning is a perturbation δW with δw_i = w_i at the pruned position. Price it with a local quadratic model instead of re-running the network. Part 06: Loss, activation and regression criteria

\delta L = \sum_i g_i\,\delta w_i + \frac{1}{2}\sum_i h_{ii}\,\delta w_i^2 + \frac{1}{2}\sum_{i \neq j} h_{ij}\,\delta w_i\,\delta w_j + O\!\left(\lVert \delta W \rVert^3\right)

g_i = ∂L/∂w_i, h_ij = ∂²L/(∂w_i ∂w_j). Full Hessian has n² entries: 6.5 million for 2578 parameters

OBD name	Slide wording	Term removed
Quadratic	L is nearly quadratic	O(\|\|δW\|\|³)
Extremal	Training has converged	Σ gᵢ δwᵢ (and makes every hᵢᵢ ≥ 0)
Diagonal	Deletion errors are independent	½ Σ hᵢⱼ δwᵢ δwⱼ

Three assumptions, three crossings

\text{importance}_{w_i} = \lvert \delta L_i \rvert = \frac{1}{2} h_{ii} w_i^2

OBD saliency; delete the smallest first. With every h_ii equal this is magnitude ranking

Weight	wᵢ	hᵢᵢ	½ hᵢᵢ wᵢ²	Magnitude	OBD
A	1.5	0.2	0.225	keep	prune
B	1.0	1.0	0.5	keep	keep
C	-0.6	4.0	0.72	keep	keep
D	0.5	8.0	1.0	prune	keep
E	0.2	2.0	0.04	prune	prune

Prune two of five: magnitude and OBD disagree

APoZ and Network Trimming

\mathrm{APoZ}_c = \frac{\sum_{k=1}^{N}\sum_{j=1}^{M} f\!\left(O_{c,j}(k) = 0\right)}{N \times M}

Zeros divided by batch × H × W. Smaller APoZ means more important; prune the largest

Slide 40 example: batch 2, three channels, 4 × 4 maps

Channel 0: 5 + 6 = 11 zeros, 11/32 = 34.4%
Channel 1: 5 + 7 = 12 zeros, 12/32 = 37.5%
Channel 2: 6 + 8 = 14 zeros, 14/32 = 43.8%, pruned
Denominator: batch 2 × height 4 × width 4 = 32
Operating rule: Trim neurons more than one standard deviation above the layer mean, about 16% of a layer; retrain from the pre-trim weights

Mean APoZ on VGG-16 rises with depth: CONV1-1 47.07%, CONV4-3 87.30%, CONV5-3 93.19%, FC6 75.26%; 631 neurons were zero more than 90% of the time. Neuron pruning is coarse-grained weight pruning: a row W[o, :] of a linear layer or a filter W[o, :, :, :] of a conv layer, plus the next layer's matching input column or kernels.

Regression-based channel pruning

Z = X W^{T} = \sum_{c=0}^{c_i - 1} X_c W_c^{T}

Layer output as a sum of per-input-channel contributions; removing channel c removes one term

\underset{W,\,\beta}{\arg\min}\ \Bigl\lVert Z - \sum_{c=0}^{c_i - 1} \beta_c\, X_c W_c^{T} \Bigr\rVert_F^2 \quad \text{s.t.} \quad \lVert \beta \rVert_0 \le N_c

beta has length c_i and switches input channels; N_c is how many survive; Z keeps its b × c_o shape

Step	Fixed	Solved	Solver	Output
1	W	β	LASSO (L1-relaxed selection)	Which input channels survive
2	β	W	Least squares (closed form)	Weights that best rebuild Z

The L0 constraint is NP-hard, so relax to λ||β||₁ and alternate

||W_c||_F = 1 per channel stops shrinking β while inflating W. In practice raise λ until ||β||₀ hits the target, then reconstruct once.
Results: VGG-16 4x speedup at 1.0% extra top-5 error, ResNet-50 2x at 1.4%; 5000 images × 10 positions; fine-tune 10 epochs.

Criteria compared

Criterion	Reads	Cost	Granularity	Score	Paper
Magnitude	Weight values only	None	Any	\|w\|, Lp norm of a set	Han et al. 2015
Scaling factor	Trained gamma per channel	Training with L1 penalty	Channel	\|γ\|	Liu et al. 2017
OBD	Weights and hᵢᵢ	One second backward pass	Weight	½ hᵢᵢ wᵢ²	LeCun et al. 1989
APoZ	ReLU outputs on validation data	One forward pass over N images	Neuron or channel	Fraction of zeros (smaller is more important)	Hu et al. 2016
Regression	Sampled layer inputs and outputs	LASSO plus least squares per layer	Input channel	Reconstruction error of Z	He, Zhang, Sun 2017

What each criterion reads, what it costs and what it scores

Slide errata

Answer with the corrected fact, and name the slide version if a question depends on it.

What the slides get wrong

Slide 5: The bullet writes ||W_p||_0 < N; the figure and the correct form use ≤ N. Lowercase and uppercase P both mean the pruned weights. Inherited from the MIT deck.
Slide 6: "Drachman, Neurology 2004" gives the page as the year. The editorial is Neurology 2005, vol. 64(12), pages 2004 to 2005.
Slides 9, 10: Legend reads "Finetuing". Read "Finetuning". The chart is AlexNet top-5 loss with L2 regularization; the paper's L1 curves are omitted.
Slide 11: VGG-16 12x on the slide, 13x in the paper abstract (138 / 10.3 = 13.4). SqueezeNet is 1.2 M, not 1 M (1.2 / 0.38 = 3.2x). ResNet-50 is 25.5 M, MAC reduction 6.25x.
Slide 12: The 95% soccer caption comes from the MIT deck; the thesis figure shows four 90% examples including a white bird whose caption does not change.
Slide 13: "1.5X measured BERT speedup" is not in the Ampere whitepaper (which says up to 2x); cuSPARSELt measures 1.3x to 1.6x per BERT-Large layer.
Slide 20: Same table as slide 11: VGG-16 12x versus 13x in both NIPS 2015 and thesis Table 3.1. The MIT source names EIE as the custom hardware example; this copy dropped it.
Slide 21: "N of them is pruned" inverts NVIDIA's convention, where N is the number kept. Only symmetric 2:4 survives the swap; 1:4 is 75% sparse, not 25%.
Slide 34: With δL = L(W) - L(W_P) and W_P = W - δW, the second-order terms should carry a minus sign. The paper defines the change as new minus old, which is what the right-hand side follows.
Slide 36: Writes h_ii = ∂²L / (∂w_i ∂w_j). The diagonal entry is ∂²L / ∂w_i².
Slide 37: "Cited by 7712" is a snapshot. Quote the venue (NIPS 1989) and year, not the count.
Slides 39, 40: Network Trimming is arXiv 1607.03250, dated 12 July 2016, not 2017. Slide 40 reads "the more importance the neuron has"; it should read "the more important the neuron is".