Exploring the Regularity of Sparse Structure in Convolutional Neural Networks

In plain words

Pruning removes the parts of a neural network that matter least, so the network gets smaller and can skip some work. The usual approach removes single weights. That is precise, but the surviving weights end up scattered at random positions, and hardware handles scattered zeros poorly.

This paper asks what happens when you remove bigger, regular blocks instead: small vectors inside a convolution kernel, whole kernels, or whole filters. It compares these block sizes under the same pruning method and the same training setup, so that only the block size changes. The finding is that bigger blocks tend to cost more accuracy at the same sparsity, but they are cheaper to store and to move through memory. At the same accuracy, that can make them the better choice for a custom chip.

TL;DR

Magnitude pruning of five ImageNet CNNs (AlexNet, VGG-16, GoogLeNet, ResNet-50, DenseNet-121) at four granularities, compared at equal density §4 tab. 1. Coarser blocks lose more accuracy at equal density, but at the baseline accuracy they need less storage because their indices are shared §5 tab. 2. In a simulated SCNN-style dataflow on VGG-16 convolution layers, vector (1-D) pruning saves 30-35% of output memory references compared with fine-grained pruning §6 tab. 3. Results are author-reported. No official code was found.

Problem

Pruning reduces parameters and computation, but fine-grained (per-weight) pruning leaves an irregular sparsity pattern that is hard to accelerate §1. Structured pruning, such as removing whole filters, is easier to run on general hardware, but the paper reports that it costs more accuracy than pruning individual weights §1. The open questions are the trade-off between regularity and accuracy, whether an intermediate granularity offers a useful middle point, and how that point helps hardware §1. The study assumes that all granularities are pruned with the same method and settings, so that the comparison isolates granularity §1 §3.2 §4.

Method

The paper compares four granularities. The grain is the atomic element that is pruned together §3.2:

• Fine-grained (0-D): single scalar weights.
• Vector (1-D): sub-kernel vectors of size S §4.
• Kernel (2-D): kernels of shape R x S §3.2.
• Filter (3-D): filters of shape K x R x S §3.2.

Notation: a convolution layer's weights form a tensor of shape C x K x R x S, with C output and K input feature maps §3.1.

Pruning criterion. Each grain G_i gets a salience equal to the sum of the absolute values of its weights, which is the L1 norm §3.3 eq. 1. Pruning removes the lowest-salience grains until the target sparsity is reached §3.3. The paper uses the iterative pruning procedure from Han et al. §3.3. The sparsity used at each stage is set by a sensitivity analysis: each layer is pruned alone and its accuracy loss is measured on the training data §3.3.

# Magnitude pruning of one layer at a chosen grain size  [§3.3] [eq. 1]
# Input:  weights (C, K, R, S); grain in {0-D, 1-D, 2-D, 3-D};
#         target_sparsity in [0, 1)
# Output: mask of the same shape as weights (1 = keep, 0 = prune)

def prune_layer(weights, grain, target_sparsity):
    # Split the layer into grains of the chosen size: scalars (0-D),
    # sub-kernel vectors of length S (1-D), kernels R x S (2-D),
    # filters K x R x S (3-D)  [§3.1] [§3.2]
    grains = split_into_grains(weights, grain)
    # Salience S_i of a grain is the sum of absolute weight values  [eq. 1]
    saliencies = [sum(abs(w) for w in g) for g in grains]
    # Delete the lowest-salience grains until the target sparsity is met
    # [§3.3]; the exact wording is ambiguous, see Pitfalls
    num_pruned = round(target_sparsity * len(grains))
    pruned_ids = argsort(saliencies)[:num_pruned]
    return build_mask(grains, pruned_ids)

S_i = \sum_{w \in G_i} |w| eq. 1

Accuracy comparison. All granularities are compared at equal sparsity, with the same pruning method and the same training schedule, on ImageNet with Caffe §4. Only convolution layers count toward the reported sparsity, but fully-connected layers are pruned too, and only at fine granularity §4. The accuracy-density curves are in fig. 3, and the top-5 comparison at matched density is in tab. 1.

Storage. Weights are stored as 8-bit values, and the distances between non-zeros are stored as 4-bit indices, following Deep Compression §5. The paper's storage ratio is the pruned model size divided by the dense 8-bit model size §5. Coarse grains share indices across the weights of a kernel, so they need fewer of them §5 fig. 4. Because accuracy at the exact baseline is hard to hit, the paper interpolates linearly to find the density and storage ratio at the baseline accuracy §5 tab. 2. The paper also plots accuracy against weight bit width for each granularity, and reports that the sparsity structure has negligible influence on quantization §5 fig. 5.

Accuracy against storage. The accuracy-storage curves for AlexNet show the index-saving effect for each granularity §5 fig. 6.

Hardware. The paper uses the SCNN dataflow as its model: weights and activations are both stored sparse, and each product is scatter-added to an output address §6 fig. 7. A coarse-grained weight set is more likely to hit the same output address, so a shortcut can skip some reads and writes §6. The paper simulates VGG-16 on the ImageNet validation set and counts output memory references for each granularity §6 tab. 3. Section 7 repeats the count for AlexNet and compares it with earlier pruning results §7 tab. 4.

Hyperparameters

Results

Author-reported. Setup: five ImageNet CNNs trained in Caffe §4; top-5 accuracy. Baseline accuracies for the matched-density comparison in tab. 1 are not stated.

Top-5 accuracy at matched density tab. 1:

Storage at the baseline accuracy tab. 2. Storage ratio is relative to the dense 8-bit model, and densities come from linear interpolation to the baseline accuracy. The paper bolds the lowest storage ratio per model: fine-grained for AlexNet and DenseNet-121, vector for VGG-16, GoogLeNet and ResNet-50.

Output memory references for VGG-16, convolution layers only tab. 3:

AlexNet, layer by layer, with earlier fine-grained results tab. 4. The NIPS'15 and NIPS'16 columns are the earlier published numbers, which the paper cites §7. The paper bolds the best value per row:

Other reported results:

• Filter-level pruning has no table. The text says AlexNet loses nearly 1% validation accuracy at the first pruning stage §4 fig. 3.
• The accuracy-storage figure caption states that vector pruning adds 1.5% and kernel pruning adds 6.7% storage relative to the fine-grained curve fig. 6.
• Vector pruning, against the fine-grained AlexNet baseline, reduces convolution storage by 23% and memory references by 43% §7 tab. 4.
• The conclusion states that coarse-grained sparsity saves about 2x output memory accesses compared with fine-grained sparsity and about 3x compared with dense §8.

Paper vs code

No official code. The paper has no code link, arXiv metadata has no code link, and no project page is linked. GitHub searches with the title words "sparse structure regularity cnn", "sparsity granularity pruning" and "coarse-grained sparsity" (including an org search under mit-han-lab) returned no repositories.

Pitfalls

• Ambiguous pruning sentence. §3.3 says that for 30% zero weights, "the grains with the smallest 70% L1-norm are deleted". Taken literally, that removes 70% of the grains, not 30%. The intended reading is almost certainly to delete the smallest 30% (the target sparsity). Confirm this before implementing.
• Per-stage schedule not stated. The paper says each stage's sparsity comes from sensitivity analysis on the training data §3.3, but it does not give the number of stages, the per-layer sparsities, the retraining length or the learning rate. The "smoother pruning process" that gives better AlexNet results than Han et al. §4 §7 is not described in this paper. The full details are not stated.
• Vector grain size. The notation section says sub-kernel vectors have length R or S §3.1, but the Method and Results use size S §3.2 §4. Use S, as the results do.
• Matched density is not baseline accuracy. tab. 1 has no baseline accuracies. tab. 2 uses densities interpolated to baseline accuracy §5. These densities differ from tab. 1 (for AlexNet, 22.1% to 37.8% in tab. 2 against 24.8% in tab. 1), so the two tables should not be combined.
• "No loss of accuracy" needs qualifying. The abstract says coarse-grained pruning can reach a sparsity similar to unstructured pruning without loss of accuracy. tab. 1 shows that kernel pruning trails fine-grained pruning by 0.27 to 1.21 top-5 points, and vector pruning by 0.08 to 0.47 points.
• The "2x" memory-reference headline depends on the comparison. tab. 4 gives 60.5% (fine) against 34.6% (vector) of the dense AlexNet references, which is about 1.75x. tab. 3 (VGG-16 convolution layers) gives 30-35% savings, which is about 1.4-1.5x. Use the table numbers, not the rounded headline.
• Fully-connected layers. They are pruned at fine grain only §4. This is why their rows in tab. 4 are identical across the three grain columns.
• Index overflow. The 4-bit index stores the distance to the next non-zero §5. How gaps longer than 15 are encoded (padding or other handling) is not stated here.
• Quantization. fig. 5 is shown only qualitatively, with no numbers. The quantization procedure itself is referred to Deep Compression and is not described in this paper §5.
• Energy is not measured. The paper says memory references are much more expensive than arithmetic §5 §6, but it counts references and does not report energy or cycles.
• Simulator parameters. The memory-reference simulator's hardware parameters and dataflow details are not stated beyond the SCNN-style description §6 fig. 7.
• Figure numbering. Figure numbers here are derived from the order of the LaTeX source, not checked against the compiled PDF. In particular, fig. 4 and fig. 5 share one float environment.
• Missing run details. Seeds, number of runs, batch size and hardware are not stated.

Lineage

• Builds on: iterative magnitude pruning from Han et al. (2015), which the paper uses as its pruning method and its storage encoding follows Deep Compression §3.3 §5.
• Compared against: Han et al. (2015) and Guo et al. (2016) for AlexNet, using their published numbers §7 tab. 4. Filter and channel pruning are discussed as earlier work §1 §2.
• Superseded by: not known from content in this wiki.