The Lottery Ticket Hypothesis in Large Language Models: How Sparse Subnetworks and Iterative Magnitude Pruning Retain Transformer Capacity

Modern large language models operate under extreme overparameterization. Frontier architectures allocate tens or hundreds of billions of parameters to achieve low perplexity and robust generalization across reasoning, code generation, and factual retrieval. Yet empirical pruning consistently demonstrates that post-training models can lose 30% to 50% of their weights with negligible performance degradation.

This tension introduces a fundamental puzzle in deep learning: if a compact subnetwork can match the performance of a dense model, why cannot engineers train that compact subnetwork directly from scratch?

In 2018, Jonathan Frankle and Michael Carbin proposed an explanation that reshaped neural network optimization theory: the Lottery Ticket Hypothesis. The hypothesis asserts that a dense, randomly-initialized feed-forward network contains a sparse subnetwork (a "winning ticket") that, when trained in isolation from initialization, can match the test accuracy of the original dense network in a comparable number of iterations.

Understanding the mechanics of the Lottery Ticket Hypothesis, its extension to deep Transformers, and its theoretical descendants reveals why massive overparameterization is essential during optimization and how sparse structures govern modern foundation models.

The Core Formulation and Iterative Magnitude Pruning

Consider a dense neural network parameterized by $\theta \in \mathbb{R}^d$ initialized at $\theta_0 \sim \mathcal{D}_\theta$. When optimized with stochastic gradient descent (SGD) on an objective $\mathcal{L}$ over $T$ iterations, the model achieves minimum validation loss $\mathcal{L}(f(x; \theta_T))$ with test accuracy $\mathcal{A}$.

A subnetwork is defined by applying a binary mask $m \in \{0, 1\}^d$ to the parameters, yielding an effective parameter vector $m \odot \theta$, where $\odot$ denotes the element-wise Hadamard product. The sparsity of the subnetwork is defined as $1 - \|m\|_0 / d$.

The Lottery Ticket Hypothesis posits that there exists a mask $m$ such that optimizing $m \odot \theta_0$ in isolation achieves test accuracy $\mathcal{A}' \ge \mathcal{A}$ within $T' \le T$ iterations.

The IMP-WR Algorithm

To discover these winning tickets empirically, Frankle and Carbin designed Iterative Magnitude Pruning (IMP). While one-shot pruning removes weights once at the end of training, iterative pruning alternates between optimization and parameter elimination:

1. Initialization: Set the binary mask $m = \mathbf{1}^d$ and sample initial parameters $\theta_0$.
2. Dense Training: Train the unmasked or partially masked model $m \odot \theta$ for $T$ iterations to obtain converged weights $\theta_T$.
3. Magnitude Selection: Compute the magnitude of each active parameter $|\theta_{T, i}|$. Prune the lowest $p\%$ (typically $p = 20\%$) of active weights across each layer or globally, updating the mask $m$ by setting corresponding indices to 0.
4. Weight Rewinding: Reset the remaining unpruned parameters back to their original initialization values $\theta_0$ (or to an early training checkpoint $\theta_k$ where $k \ll T$).
5. Iteration: Repeat steps 2 through 4 until reaching the target sparsity ratio $S = 1 - (1 - p/100)^N$.

The Breakdown on Deep Networks and the Rewinding Solution

When applied to shallow architectures (e.g., LeNet and small convolutional networks on CIFAR-10), standard IMP rewinding to $\theta_0$ consistently yields winning tickets at 80% to 90% sparsity. However, when researchers attempted to scale standard IMP to deeper architectures such as ResNet-50 and Transformers, the hypothesis broke down: subnetworks reset to $\theta_0$ failed to train effectively and underperformed the dense baseline.

In follow-up work, Frankle, Dziugaite, Roy, and Carbin (2020) identified the failure mode: deep networks are highly sensitive to SGD gradient noise during early iterations. To stabilize subnetwork identification, they introduced Iterative Magnitude Pruning with Weight Rewinding (IMP-WR):

$$\theta_{\text{subnetwork}} = m \odot \theta_k \quad \text{where } k > 0$$

Instead of resetting parameters to step 0, parameters are rewound to step $k$ (typically 0.1% to 5% of total training iterations). At iteration $k$, the network has traversed the initial chaotic optimization phase and entered a stable basin of attraction. Under IMP-WR, matching subnetworks consistently emerge in deep vision models and large language models.

Theoretical Foundations: Linear Mode Connectivity and Supermasks

The empirical success of IMP-WR prompted mathematical inquiries into why sparse subnetworks require dense initialization or early rewinding.

1. Linear Mode Connectivity

A key theoretical breakthrough connecting the Lottery Ticket Hypothesis to loss surface geometry came from Frankle et al. (2020) and subsequent studies on Linear Mode Connectivity.

Two parameter configurations $\theta_A$ and $\theta_B$ are linearly mode connected if the loss along the linear interpolation path between them does not exceed the loss of the endpoints:

$$\mathcal{R}(\theta_A, \theta_B) = \sup_{\alpha \in [0, 1]} \left[ \mathcal{L}((1 - \alpha)\theta_A + \alpha \theta_B) - \frac{1}{2}\left(\mathcal{L}(\theta_A) + \mathcal{L}(\theta_B)\right) \right] \le \epsilon$$

When a dense network is trained with two different SGD noise seeds starting from step 0, the resulting solutions $\theta_A$ and $\theta_B$ end up in distinct basins separated by high loss barriers ($\mathcal{R} > 0$). However, if training branches at step $k$, the solutions become linearly mode connected ($\mathcal{R} \approx 0$).

Paul, Ganguli, and Dziugaite (2022) showed that IMP masks extract the subspace that intersects this linearly connected mode. The winning ticket mask acts as an inductive constraint that forces optimization along low-curvature valley paths, filtering out directions susceptible to gradient noise.

2. The Strong Lottery Ticket Hypothesis and Supermasks

An even more radical extension was formalized by Ramanujan et al. (2020) and proven mathematically by Malach, Yehudai, Shalev-Shwartz, and Shamir (2020): the Strong Lottery Ticket Hypothesis.

The strong hypothesis conjectures that a sufficiently overparameterized, randomly-initialized neural network contains a subnetwork that achieves competitive accuracy on a target task without updating a single weight parameter.

$$f(x; m^* \odot \theta_0) \approx f(x; \theta^*) \quad \text{where } \theta_0 \sim \mathcal{D}_\theta \text{ is completely frozen}$$

Using algorithms such as Edge-Popup, researchers optimize continuous scores assigned to each edge to learn binary masks over frozen random weights. Malach et al. (2020) proved that any target network of depth $l$ and width $d$ can be approximated with high probability by pruning a random network whose depth and width are logarithmic factors larger than the target. Overparameterization acts as an expansive combinatorial pool where random projections contain exact function approximations by selection alone.

The Lottery Ticket Hypothesis in Pre-Trained Transformers and LLMs

As foundation models became the standard paradigm in natural language processing, researchers examined how the Lottery Ticket Hypothesis operates in self-attention mechanisms and multi-layer perceptron (MLP) blocks.

Universal Winning Tickets in Pre-Trained BERT

In a seminal study, Chen, Frankle, Chang, Liu, Zhang, Wang, and Carbin (2020) evaluated whether pre-trained language models like BERT contain winning tickets for downstream fine-tuning tasks.

Key empirical findings from Chen et al. demonstrated:

1. High Sparsity Tolerances: Subnetworks isolated from pre-trained BERT at 40% to 70% sparsity matched full-model performance across the GLUE benchmark suite (e.g., MNLI, QQP, SST-2, QNLI).
2. Universal Transferability: A subnetwork identified via IMP during masked language modeling (MLM) pre-training served as a universal winning ticket. The same sparse mask transferred directly to diverse downstream classification and question-answering tasks without re-running IMP on each task.
3. Failure of Random Topology: Randomly pruned masks or shuffled pre-trained weights at identical sparsity ratios suffered severe performance collapse, demonstrating that pre-training embeds structural alignment between specific attention heads and parameter magnitudes.

| Sparsity Ratio | Standard BERT Accuracy (GLUE Avg) | IMP Universal Ticket (Pre-Trained Mask) | Random Pruned Baseline | | :--- | :--- | :--- | :--- | | 0% (Dense) | 81.4% | 81.4% | 81.4% | | 40% Sparse | - | 81.6% | 79.1% | | 60% Sparse | - | 81.2% | 75.8% | | 80% Sparse | - | 78.4% | 68.2% |

Redundancy and Structured Subnetworks

Concurrently, Prasanna, Rogers, and Rumshisky (2020) analyzed subnetwork dynamics in BERT across individual attention heads and layers. They observed that while individual winning tickets exist, BERT exhibits massive head redundancy: multiple distinct subnetwork combinations can achieve comparable downstream accuracy, suggesting that pre-trained Transformers contain an ensemble of overlapping winning tickets.

In generative autoregressive architectures (such as GPT and LLaMA variants), Yu et al. (2020) confirmed that Transformer decoders preserve lottery ticket dynamics. Self-attention projection matrices ($W_Q, W_K, W_V, W_O$) and feed-forward up/down projections ($W_{\text{gate}}, W_{\text{up}}, W_{\text{down}}$) exhibit distinct pruning tolerances:

• MLP Layers: Can sustain higher sparsity levels (up to 70-80%) before perplexity degrades, reflecting parametric memory redundancy.
• Attention Projections: More sensitive to pruning below 50% sparsity, as multi-head routing patterns require dense connectivity for sequence context assembly.

From IMP to Modern Post-Training Pruning in Frontier LLMs

While IMP-WR provides profound theoretical insights, running multiple iterations of full pre-training or fine-tuning across hundreds of billions of tokens is computationally prohibitive for frontier LLMs. Modern LLM pruning architectures bridge this gap by translating lottery ticket insights into one-shot post-training algorithms.

1. Second-Order One-Shot Pruning: SparseGPT and Wanda

To prune modern 70B+ parameter models without expensive iterative retraining:

• SparseGPT (Frantar & Alistarh, 2023): Formulates pruning as a layer-wise generalized Optimal Brain Surgeon (OBS) problem. By inverting the Hessian matrix $H = 2 X X^T + \lambda I$ computed on a small calibration set, SparseGPT identifies and updates remaining weights in closed form to compensate for pruned connections, achieving 50% unstructured sparsity in a single pass.
• Wanda (Sun et al., 2023): Discovers that weight magnitude alone is insufficient in modern LLMs due to emergent outlier activations. Wanda computes parameter importance via the product of weight magnitude and input activation norm:

$$I_{ij} = |W_{ij}| \cdot \|X_j\|_2$$ This matches second-order pruning quality without requiring explicit Hessian matrix inversion.

2. Hardware Alignment: Unstructured vs. 2:4 Semi-Structured Sparsity

A primary engineering constraint of traditional lottery tickets is that arbitrary unstructured sparsity ($m \in \{0, 1\}^d$) does not yield speedups on standard GPU systolic arrays due to irregular memory access patterns.

Modern foundation model deployment relies instead on 2:4 Semi-Structured Sparsity, supported natively by NVIDIA Ampere, Hopper, and Blackwell Tensor Cores. In this regime, exactly 2 out of every 4 consecutive values in each weight matrix row must be zero. Pruning algorithms adapted to the 2:4 constraint recover near-dense perplexity while unlocking a 2x theoretical throughput gain in dense GEMM operations.

Dense 4-element block:     [ 0.82,  0.14, -0.65,  0.03 ]
2:4 Structured Pruning:   [ 0.82,  0.00, -0.65,  0.00 ]  (Retains top 2 magnitudes)
Compressed Storage:        [ 0.82, -0.65 ] + 2-bit index mask (00, 10)

3. Relation to Parameter-Efficient Fine-Tuning (LoRA)

The Lottery Ticket Hypothesis also provides a theoretical foundation for Low-Rank Adaptation (LoRA). If a pre-trained model contains sparse, low-dimensional functional manifolds (winning tickets) for specific capabilities, fine-tuning does not require shifting millions of independent weight coordinates.

Instead, factorizing weight updates into low-rank matrices $\Delta W = B \cdot A$ (where $B \in \mathbb{R}^{d \times r}, A \in \mathbb{R}^{r \times k}$ and $r \ll d$) projects gradient dynamics directly onto the intrinsic low-dimensional subspace identified by the lottery ticket literature.

Key Architectural Takeaways

1. Overparameterization as Combinatorial Search: Large parameter counts are necessary during training not because the final task requires billions of active connections, but because random initialization requires a sufficiently dense pool of potential subnetwork combinations to guarantee the existence of trainable gradient paths.
2. Rewinding Resolves Optimization Chaos: Deep Transformers cannot be trained from arbitrary sparse initializations at step 0 due to early SGD noise. Rewinding weights to an early checkpoint $\theta_k$ preserves the low-curvature basin of attraction while shedding redundant parameters.
3. Pre-Training Generates Universal Tickets: Winning tickets extracted from large-scale pre-training transfer seamlessly across disparate downstream NLP benchmarks, proving that foundation models learn universal structural representations rather than narrow task-specific heuristics.
4. Weight Magnitude Must Be Scaled by Activation Norms: In generative models with emergent outlier features, evaluating subnetwork quality requires factoring in input activation magnitudes ($|W| \cdot \|X\|_2$) rather than raw parameter values in isolation.

Sources

• Frankle, J., & Carbin, M. (2018). The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. ICLR 2019.
• Frankle, J., Dziugaite, G. K., Roy, D., & Carbin, M. (2020). Linear Mode Connectivity and the Lottery Ticket Hypothesis. ICML 2020.
• Chen, T., Frankle, J., Chang, S., Liu, S., Zhang, Y., Wang, Z., & Carbin, M. (2020). The Lottery Ticket Hypothesis for Pre-trained BERT Networks. NeurIPS 2020.
• Malach, E., Yehudai, G., Shalev-Shwartz, S., & Shamir, O. (2020). Proving the Lottery Ticket Hypothesis: Pruning is All You Need. ICML 2020.
• Ramanujan, V., Wortsman, M., Kembhavi, A., Farhadi, A., & Rastegari, M. (2020). What's Hidden in a Randomly Weighted Neural Network? CVPR 2020.
• Prasanna, S., Rogers, A., & Rumshisky, A. (2020). When BERT Plays the Lottery, All Tickets Are Winning. EMNLP 2020.
• Frantar, E., & Alistarh, D. (2023). SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot. ICML 2023.
• Sun, M., Liu, Z., Yao, Z., Dou, Z., Hou, L., & Keutzer, K. (2023). A Simple and Effective Pruning Approach for Large Language Models (Wanda). ICLR 2024.
• Paul, M., Ganguli, S., & Dziugaite, G. K. (2022). Deep Learning Through a Pruning Lens: Insights into Neural Architecture and Training Dynamics. arXiv:2210.03044.