Theoretical Guarantees for One-Shot Magnitude Pruning and Compute-Adaptive Early Exit

Erdem KoyuncuICML 2026 · OpenReview

Large-scale neural networks are powerful but computationally expensive. To mitigate these costs, practitioners frequently employ two primary strategies: one-shot magnitude pruning (permanently removing the smallest weights) and early exit (halting computation early when the model is sufficiently confident). While highly effective in practice, these methods have historically lacked a rigorous theoretical foundation to precisely quantify the tradeoff between computational savings and accuracy degradation.

This paper provides a unified mathematical framework that treats both pruning and early exit as a choice between "partial" and "full" computation. By doing so, it derives explicit scaling laws that predict performance across both single neurons and deep architectures, offering a theoretical "rulebook" for compute reduction.

The Alignment Problem in the One-Shot Regime

Most existing theoretical work focuses on complex "prune-then-train" pipelines. This paper isolates the one-shot regime—evaluating the network immediately after pruning or exiting early, without any subsequent fine-tuning.

The core challenge addressed is the "alignment problem": determining how similar the "cheap" partial computation is to the "expensive" full computation, and understanding how this similarity (or lack thereof) propagates through dozens of layers in a deep network.

Single-Neuron Pruning and Directional Stability

The foundation of the theory begins with a single-neuron model. Using the mathematics of order statistics for Gamma random variables, the author proves a concentration theorem demonstrating that in high-dimensional spaces, one-shot magnitude pruning induces surprisingly little directional distortion.

For instance, retaining only 60% of a neuron's weights yields a pruned weight vector that remains approximately 98% aligned (an angle of roughly 10.8°) with the original unpruned vector. This high-dimensional concentration rate of $O(n^{-1/2})$ explains why naive magnitude pruning performs remarkably well: as the number of parameters ($n$) grows, the behavior of the pruned model becomes highly predictable and directionally stable.

Early Exit and the Conditional Perceptron

To model adaptive computation, the paper introduces the Conditional Perceptron. In this regime, the system decides whether to exit early based on a confidence threshold.

The theory reveals a fundamental power-law relationship: the "excess generalization error" (the additional mistakes incurred by exiting early) decays as a power of the compute gap, following a curve of $O(\epsilon^A)$. Crucially, the exponent $A$ is dictated by the alignment (correlation) between the intermediate partial computation and the final full computation. Higher correlation yields a steeper tradeoff curve, meaning massive compute savings can be achieved with almost zero loss in accuracy.

Extension to Deep Networks

Transitioning from single neurons to deep architectures, the author leverages the Neural Network Gaussian Process (NNGP) limit. By assuming an infinite-width network, the theory uses recursive kernels to track how misalignment at early layers compounds as it propagates deeper into the network.

This analysis yields a closed-form recursion that predicts the final Mean Squared Error (MSE) based on the chosen activation function and pruning rate, without requiring a single simulation. Notably, the choice of activation function plays a critical role in depth recursion:

  • Sign-based networks are "fragile" and accumulate pruning distortion rapidly.
  • ReLU networks demonstrate much greater stability, preserving alignment across many layers.

Empirical Validation

The theoretical predictions were rigorously tested against standard benchmarks, including CIFAR-10 (VGGNet7, MobileNetV2), CIFAR-100 (ViT-Base), and SST-2 (DistilBERT).

The empirical results closely mirrored the theoretical scaling laws. For example, in the DistilBERT early-exit experiments, the theoretical exponent for the deepest exit (Layer 5) was calculated at ~11.0, while the empirical measurement was ~11.75—a striking validation of the framework's applicability to complex transformers.

Limitations and Future Directions

While comprehensive, the framework establishes a baseline that leaves room for future expansion:

  • Infinite Width Assumption: The deep network analysis relies on the NNGP limit. Real-world "narrow" networks might exhibit divergent stochastic behaviors not captured here.
  • One-Shot Only: The theory focuses strictly on the one-shot regime. It does not account for post-pruning fine-tuning or retraining, which are standard industry practices.
  • Frozen Backbones: The early-exit analysis assumes the model's backbone is frozen and uses distillation. Future research could explore end-to-end trained early exits optimized specifically for this tradeoff.
  • Multi-Class Complexity: The transition from binary to multi-class classification suggests that a "multi-class correction" may be necessary to perfectly align the theoretical exponents in highly complex categorization tasks.

Summary updated

Abstract

We study compute reduction in neural networks through a unified partial versus full computation view, captured by one-shot magnitude pruning in the static regime and early exit in the adaptive regime. In an asymptotic single-neuron model, we prove a concentration theorem for one-shot magnitude pruning with explicit rates. We also introduce the conditional perceptron for early exit and show that its excess generalization error decays as a power of the compute gap, with an exponent that grows to infinity as the alignment between partial and full computations tends to one. We then extend the analysis to deep networks, characterizing how pruning-induced distortions accumulate with depth and deriving a corresponding compute–accuracy tradeoff for frozen-backbone early exit under a neural network Gaussian process model. Numerical simulations corroborate the predicted scaling laws.
BibTeX
@inproceedings{koyuncu2026theoretical,
  author = {Erdem Koyuncu},
  title = {{Theoretical Guarantees for One-Shot Magnitude Pruning and Compute-Adaptive Early Exit}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=W7gIiS2y1x},
}
Figure