📋 KEY INSIGHTS
- Sparsity in deep learning refers to architectures or training procedures that produce models where the vast majority of weights, activations, or attention entries are zero ā enabling dramatic reductions in memory, compute, and communication costs with minimal accuracy loss. Sparsity operates at three levels: weight sparsity (most model parameters are zero, enabling compressed storage and sparse matrix operations), activation sparsity (most neurons output zero for a given input, enabling skipping of computations), and attention sparsity (most attention weights are negligible, enabling linear-time Transformers).
- The Lottery Ticket Hypothesis (Frankle & Carlin, 2019) states that a dense, randomly-initialised neural network contains sparse subnetworks (“winning tickets”) that, when trained in isolation from their original initialisation, match the full network’s accuracy in the same number of training steps. Identifying these subnetworks ā by iteratively magnitude-pruning the smallest weights and rewinding remaining weights to their initial values ā reveals that effective sparse networks exist but are very difficult to find by training sparse networks from scratch.
- Magnitude-based unstructured pruning removes individual weights below a threshold, producing sparse weight tensors that require specialised sparse matrix libraries (NVIDIA cuSPARSE, PyTorch sparse tensors) for efficient inference ā standard dense matrix operations do not benefit from weight-level sparsity because hardware is optimised for regular memory access patterns. Structured pruning removes entire channels, filters, or attention heads, producing dense but smaller weight tensors that run efficiently on standard hardware without sparse kernels.
- Sparse attention mechanisms address the O(nĀ²) memory and compute cost of full self-attention for long sequences. Sliding window attention (Longformer) restricts each token to attend only to a local window of w neighbours; global tokens attend to all positions. Strided/dilated attention (BigBird) combines local, global, and random attention patterns to achieve O(n) complexity with near-full attention expressiveness. Flash Attention achieves I/O-efficient exact attention (not approximation) by tiling computation to fit in SRAM, reducing wall-clock time by 2-4Ć vs naive implementation.
- Dynamic sparsity ā sparsity patterns that change with each input rather than being fixed at training time ā is the principle behind Mixture of Experts (MoE) models: only the top-k experts (typically k=2 out of 64-128) are activated for each token, keeping compute per forward pass constant as total parameter count grows. The connection to our MoE guide is direct: sparse expert activation is the defining characteristic of MoE scaling, enabling models with trillions of parameters to run at the cost of much smaller dense models.
- Sparse training ā training with sparsity enforced throughout (rather than pruning a trained dense model) ā enables both memory and compute savings during training, not just inference. RigL (Evci et al., 2020) maintains a fixed sparsity budget by periodically updating the sparsity pattern: drop the smallest-magnitude active weights, grow new connections where the gradient magnitude is largest. This dynamic update step allows sparse networks to explore the weight space and achieve significantly better accuracy than fixed-mask sparse training at the same sparsity level.
As neural networks grow from millions to trillions of parameters, the compute and memory costs of dense matrix operations become prohibitive ā both for training at scale and for inference at low latency. Sparsity is the primary mechanism by which the field has addressed this: by exploiting the empirical observation that most neural network weights, activations, and attention patterns contribute negligibly to model outputs, we can skip their computation without significantly affecting model quality. This guide covers the Lottery Ticket Hypothesis and iterative magnitude pruning, structured vs unstructured weight sparsity, sparse attention mechanisms for long-sequence Transformers (Longformer, BigBird, Flash Attention), dynamic activation sparsity (ReLU networks, dynamic sparse training with RigL), and the practical tooling for deploying sparse models in production.
The Lottery Ticket Hypothesis and Weight Pruning
The Lottery Ticket Hypothesis (Frankle & Carlin, 2019) overturned the conventional wisdom that sparse networks are harder to train than dense networks. The finding: inside a randomly-initialised dense network, sparse subnetworks exist whose initial weights, if trained in isolation, achieve accuracy matching the full network in the same number of steps. These subnetworks (“winning tickets”) are identified by iterative magnitude pruning: (1) train the dense network to convergence; (2) prune the p% of weights with the smallest absolute magnitude, setting them to zero; (3) rewind the remaining weights to their values at initialisation (not at training end); (4) retrain the sparse subnetwork from these rewound initialisations. Repeating this cycle produces progressively sparser networks that match dense accuracy until a critical sparsity threshold is crossed, beyond which accuracy degrades. The rewinding step is crucial ā initialising the sparse network from random values (not the original initialisations) fails to find winning tickets, suggesting that the initialisation values, not just the connectivity pattern, are essential to the lottery ticket phenomenon. The connection to our regularisation guide is direct: L1 regularisation and dropout both implicitly encourage sparsity during training, and iterative magnitude pruning is an explicit post-training sparsification that achieves much higher sparsity rates (90%+) than L1 alone.
| Pruning Method | Sparsity Type | HW Speedup? | Accuracy-Sparsity | Best For |
|---|---|---|---|---|
| Magnitude pruning (unstructured) | Individual weights | Only with sparse kernels | 90%+ with <1% loss | Compression, storage |
| Structured (channel/filter) | Entire channels/heads | Yes (dense smaller tensor) | 50-70% with 1-3% loss | Mobile/edge deployment |
| Block sparsity (2:4 NVIDIA) | 2 zeros per 4 weights | Yes (Ampere+ 2Ć speedup) | 50% with ~1% loss | NVIDIA GPU inference |
| RigL (dynamic sparse) | Individual weights (dynamic) | Only with sparse kernels | Better than static at same sparsity | Sparse training from scratch |
| Lottery ticket pruning | Unstructured + rewind | Only with sparse kernels | Best accuracy at high sparsity | Research; finding sparse subnetworks |
Sparse Attention and Flash Attention for Long Sequences
Standard Transformer self-attention has O(nĀ²) memory and O(nĀ²) compute in the sequence length n ā catastrophic for long documents (10,000+ tokens), long time series, or high-resolution images. Sparse attention restricts each token to attend to a small subset of other tokens, reducing complexity to O(n Ć k) where k is the attention span per token. Longformer (Beltagy et al., 2020) uses sliding window attention (each token attends to w/2 tokens on each side) plus global tokens (e.g., the [CLS] token) that attend to and are attended to by all positions. This produces O(n Ć w) attention cost ā linear in sequence length for fixed window size ā while global tokens maintain the ability to aggregate information from the full sequence. BigBird (Zaheer et al., 2020) proves that sparse attention with random + local + global components is a universal approximator of full attention and is Turing complete, providing theoretical justification for sparse attention’s expressiveness. The connection to our Transformers guide is direct: sparse attention is the primary architectural mechanism for extending Transformers beyond 512-2048 token sequences to 10,000-100,000 token contexts, enabling document-level understanding, long-horizon time series forecasting (our time series deep learning guide), and high-resolution image processing.
Flash Attention (Dao et al., 2022) achieves a different kind of efficiency: exact (not approximate) attention computation that is 2-4Ć faster in wall-clock time by exploiting GPU memory hierarchy. Standard attention materialises the full nĆn attention matrix in HBM (high bandwidth memory), causing memory I/O to dominate compute time. Flash Attention tiles the Q, K, V matrices into blocks that fit in SRAM (fast on-chip memory), computes attention incrementally with online softmax normalisation, and writes back only the final output ā never materialising the full attention matrix. This reduces HBM reads/writes from O(nĀ²) to O(n), enabling the same mathematical result with dramatically less memory I/O. Flash Attention 2 and 3 further improve parallelism and achieve near-theoretical peak FLOPs utilisation on A100/H100 GPUs. The connection to our LLM fine-tuning guide is direct: Flash Attention is the standard attention implementation in all production LLM training and fine-tuning frameworks (Hugging Face Transformers, DeepSpeed, Megatron-LM) because it enables training with 2-4Ć longer sequences for the same GPU memory budget.
Dynamic Sparsity, RigL and Sparse MoE
Static sparse training (training a fixed-topology sparse network from scratch) consistently underperforms iterative pruning of a dense network at the same sparsity level ā the sparse topology found by magnitude pruning is better than a randomly chosen sparse topology of the same density. RigL (Evci et al., 2020) bridges this gap by allowing the sparsity pattern to evolve during training: every T iterations, drop the active weights with the smallest gradient magnitudes (not weight magnitudes ā gradient magnitude identifies weights that would benefit most from being active) and grow new connections where the gradient magnitude of currently zero weights is largest. This dynamic update lets the sparse network explore connectivity space during training, discovering sparse topologies that match the accuracy of iterative pruning without requiring a dense model training phase. The connection to our backpropagation guide is direct: RigL’s growth criterion uses gradient magnitudes computed by standard backpropagation, extended to compute gradients with respect to currently zero weights by treating them as if they were momentarily unmasked. The Mixture of Experts guide covers dynamic sparsity at a different level ā sparse expert activation ā which achieves a complementary form of computational efficiency by activating only a fraction of model capacity per input, enabling trillion-parameter models to run at dense-model inference costs.
✦ SUMMARIZE THIS ARTICLE WITH AI
ChatGPTModel compression (pruning, quantisation, distillation) as the broader efficiency toolkit is in our Model Compression guide. Mixture of Experts and sparse expert activation are in our MoE and Sparse Models guide. Transformers and the attention mechanism that sparse attention modifies are in our Transformers guide. LLM fine-tuning with memory-efficient techniques (Flash Attention, LoRA) is in our LLM Fine-Tuning guide. NAS for automated architecture design including sparse architectures is in our Neural Architecture Search guide. Regularisation including L1 sparsity penalties is in our Regularisation guide.
