Deep neural networks are notoriously over-parameterized, containing far more parameters than necessary to represent their target functions. The discovery of the Lottery Ticket Hypothesis by Jonathan Frankle in The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks formalized this observation: within dense networks exist sparse subnetworks ("winning tickets") capable of matching full-model performance when trained in isolation from early initializations.
However, a fundamental economic paradox underlies this discovery. While sparse models drastically reduce the computational footprint of inference, the process of finding them is incredibly inefficient. To isolate an optimal subnetwork, researchers typically rely on Iterative Magnitude Pruning (IMP), which requires training a dense model, removing a fraction of the smallest weights, rewinding the remaining weights, and repeating the cycle multiple times. As noted by Jonathan Frankle in Linear Mode Connectivity and the Lottery Ticket Hypothesis, this multi-stage training process creates a massive computational barrier, preventing the immediate realization of training efficiency gains on resource-constrained hardware.
Why One-Shot Pruning Fails and Iteration Costs So Much
To understand why this overhead is so severe, we must look at why simpler methods fail. If we prune a model in a single step (one-shot pruning) by simply cutting out the bottom 80% of weights by magnitude, the sudden loss of parameters causes a "quality crash." The network's internal pathways cannot instantly compensate for the missing information, destroying its performance.
To avoid this crash, state-of-the-art methods rely on gradual or optimization-based pruning. For instance, Wan et al. demonstrate in Pruning for Sparse Diffusion Models based on Gradient Flow that progressive soft pruning preserves image generation quality but demands significantly more training iterations and compute time than one-shot alternatives.
Every iteration introduces multiple layers of overhead:
- Repeated Training Cycles: As highlighted by Yu et al. in Playing the lottery with rewards and multiple languages: lottery tickets in RL and NLP, the requirement for multiple full training and pruning cycles prevents sparsity from reducing the resource costs of the initial training phase.
- Layer-wise and Submodule Evaluations: Modern architectures require complex, dynamic assessments to determine which components are redundant. Sandri et al. point out in 2SSP: A Two-Stage Framework for Structured Pruning of LLMs that iteratively evaluating submodules introduces a computational bottleneck that scales directly with the total number of blocks in the architecture. Similarly, Liao et al. show in Till the Layers Collapse: Compressing a Deep Neural Network Through the Lenses of Batch Normalization Layers that iterative importance ranking for layer removal scales poorly with network depth due to the high cost of repeated validation cycles.
The Mathematical and Optimization Burden
The overhead is not merely a matter of running more forward passes; it is deeply tied to the optimization landscape. When we treat pruning as an optimization problem, the mathematical machinery itself becomes expensive.
For example, Kübler et al. explore this in A Proximal Operator for Inducing 2:4-Sparsity, noting that optimization-based pruning methods relying on iterative proximal operators require hours of additional GPU processing compared to simple heuristics. When moving beyond linear approximations to account for non-linearities like the attention mechanism's Softmax function, Liang demonstrates in Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrix that optimizing masks via gradient descent introduces significant pre-processing overhead compared to analytical, one-shot solutions.
Even when the underlying weights remain frozen, finding the optimal binary masks ("supermasks") still requires a standard training phase using backpropagation, as shown by Shen et al. in What's Hidden in a One-layer Randomly Weighted Transformer?. The search space is simply too vast to navigate without gradient-based optimization or complex population simulations, such as the thermodynamic mask particle evolution proposed by Mo in Probabilistic Neural Pruning via Sparsity Evolutionary Fokker-Planck-Kolmogorov Equation, which incurs substantial computational complexity over one-pass heuristics.
Amortizing and Escaping the Search Cost
Given that the upfront cost of subnetwork discovery is so high, researchers have pursued two primary avenues to make the process viable: transferability and algorithmic acceleration.
Transferability as Amortization
If discovering a winning ticket is a massive sunk cost, we can amortize that cost by reusing the discovered masks across different tasks or domains. Morcos et al. in One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers showed that winning tickets contain generic inductive biases that allow them to generalize across datasets and optimizers.
Building on this, Sabatelli et al. demonstrated in On the Transferability of Winning Tickets in Non-Natural Image Datasets that these pre-identified tickets can be transferred to highly specialized domains like digital pathology. While this makes downstream deployment highly efficient, the authors emphasize that the high initial cost of discovering the source tickets remains a significant barrier to practical scalability.
Algorithmic Acceleration
To bypass the iterative bottleneck entirely, recent work focuses on developing smarter, one-shot, or closed-form alternatives. For instance, Wen et al. in An Efficient Pruner for Large Language Model with Theoretical Guarantee propose a one-shot pruner that bridges the gap between heuristic shortcuts and rigorous optimization, aiming to avoid the heavy compute time and memory footprint of iterative gradient-based pruning.
Similarly, in the context of concept erasure, Belrose et al. introduce LEACE in LEACE: Perfect linear concept erasure in closed form, showing that a closed-form analytical solution can run orders of magnitude faster than traditional iterative techniques that rely on gradient-based optimization.