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

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.

Modern neural networks can be very accurate, but running every part of a large model for every input can be expensive. This paper asks when a model can safely use less computation without losing much accuracy. We study two common ways to do this: removing small weights from the model, and letting the model stop early when an intermediate prediction is already confident. Our main idea is to measure how well the cheaper computation stays aligned with the full computation. We prove mathematical results showing that, in high dimensions, one-shot pruning changes a neuron in a predictable way, and that this change can compound across layers depending on the activation function. We also show that early-exit systems can approach full-model accuracy quickly as the allowed computation increases, especially when early and final predictions are strongly aligned. Experiments on vision and language models support these predicted trends. The results explain why and when existing compute-saving methods can work, helping guide the design of faster neural networks for resource-limited settings.