Pruning & Structured Sparsity

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Unstructured Pruning
5. Structured Pruning
6. The Lottery Ticket Hypothesis
7. SparseGPT: One-Shot LLM Pruning
8. Wanda: Pruning by Weights and Activations
9. N:M Sparsity (Hardware Support)
10. Common Pitfalls
11. Summary
12. Exercises

Learning Objectives

1. Distinguish unstructured and structured pruning and their hardware implications.
2. State the lottery ticket hypothesis and its implications.
3. Derive SparseGPT's one-shot pruning algorithm.
4. Explain N:M sparsity and NVIDIA's hardware support.
5. Analyze the sparsity-quality tradeoff for LLMs.

Notation

• $\mathbf{M} \in \{0, 1\}^{d \times k}$ — binary mask
• $s$ — sparsity level (fraction of zeros)
• $N:M$ — structured sparsity pattern ($N$ zeros per $M$ elements)

Core Intuition

Neural networks are massively over-parameterized — many weights contribute negligibly to the output. Pruning removes these redundant weights, creating a sparse model that's smaller and potentially faster. The challenge: identifying which weights to remove without degrading accuracy, and making the resulting sparsity pattern hardware-friendly.

Unstructured Pruning

Remove individual weights based on importance:

Magnitude pruning: Remove smallest-magnitude weights. Simple, effective baseline.

Movement pruning: Remove weights whose magnitude is DECREASING during training (they're being trained toward zero):

Limitation: Random sparsity patterns don't map to hardware acceleration. A 90% sparse matrix stored naively is just as large; need sparse formats (CSR, CSC) which have overhead.

Structured Pruning

Remove entire structural units:

• Neuron pruning: Remove entire rows/columns of weight matrices.
• Head pruning: Remove entire attention heads.
• Layer pruning: Remove entire transformer layers.
• Channel pruning: Remove feature map channels (for CNNs).

Advantage: Result is a smaller dense model — no special sparse hardware needed.

Disadvantage: Coarser granularity; can't achieve high sparsity without significant quality loss.

The Lottery Ticket Hypothesis

Frankle & Carlin (2019): A randomly-initialized dense network contains a sparse subnetwork (the "winning ticket") that, when trained in isolation from the same initialization, reaches comparable accuracy.

Implication: The full model is needed for finding the right architecture (which weights matter), but not for the final trained model.

Practical issue: Finding the winning ticket requires training the full model first (iterative pruning + rewinding), making it impractical for LLMs.

SparseGPT: One-Shot LLM Pruning

Problem: Prune a pre-trained LLM to 50-60% sparsity without any retraining.

Method (Frantar & Alistarh, 2023): Apply OBS-style (Optimal Brain Surgeon) reasoning column by column (same framework as GPTQ):

1. For each column: identify the weight to prune (smallest importance-weighted magnitude).
2. Set it to zero.
3. Compensate remaining weights using Hessian information:

Result: 50% unstructured sparsity on GPT-175B with negligible perplexity increase. 60% with minor degradation.

Wanda: Pruning by Weights and Activations

Simpler alternative (Sun et al., 2023): Importance = weight magnitude × input activation magnitude:

Prune weights with lowest score. No Hessian computation needed.

Key insight: A large weight on a channel that's always near-zero is unimportant. A small weight on a highly active channel matters more.

Quality: Comparable to SparseGPT at 50% sparsity; slightly worse at higher sparsity. Much faster to compute.

N:M Sparsity (Hardware Support)

NVIDIA Ampere/Hopper: Hardware support for 2:4 sparsity — exactly 2 zeros per group of 4 elements.

2:4 pattern: 50% sparsity with structured layout that maps to sparse tensor cores. 2x speedup with dedicated hardware.

Training with N:M:

1. Train dense model normally.
2. Apply 2:4 mask based on magnitude within each group of 4.
3. Fine-tune the remaining weights.

Result: Consistent 2x inference speedup with less than 1% accuracy loss for most models.

Common Pitfalls

Pitfall 1. Expecting unstructured sparsity to provide speedup without special hardware/software. Standard CUDA kernels don't benefit from random zeros; need sparse libraries (cuSPARSE) or N:M hardware.

Pitfall 2. Pruning uniformly across layers. Earlier layers (embeddings) and final layers (LM head) are much more sensitive. Use per-layer sparsity targets.

Pitfall 3. Pruning and quantization simultaneously without care. Both introduce error; naive combination can be catastrophic. Apply sequentially with compensation.

Summary

• Unstructured: Flexible, high sparsity possible, but needs sparse hardware.
• Structured: Dense result (any hardware), but coarser → lower achievable sparsity.
• Lottery Ticket: Sparse winning tickets exist but are expensive to find.
• SparseGPT/Wanda: One-shot LLM pruning to 50-60% without retraining.
• 2:4 sparsity: Hardware-supported 50% sparsity with 2x speedup on NVIDIA GPUs.

Exercises

Exercise 1. For a 7B model pruned to 50% unstructured sparsity: compute the model size in CSR format vs dense FP16.

Exercise 2. Derive the Wanda score for a weight $w=0.01$ with input activation norm 100 vs $w=0.5$ with activation norm 0.1. Which gets pruned?

Exercise 3. For 2:4 sparsity in a layer with 4096 input features: how many possible sparsity patterns exist per group?

Exercise 4. Explain why structured pruning (removing entire heads) often hurts less than expected (hint: redundancy across heads).

Exercise 5. Design a combined pruning + quantization pipeline for a 70B model targeting 4x size reduction with minimal quality loss.