Towards an Optimal Control Foundation of Early Exits - Turnpikes and ResNets
Authors: Jens Püttschneider, Simon Heilig, Asja Fischer, Timm Faulwasser
Organizations: Institute of Control Systems, Hamburg University of Technology, Hamburg, Germany · Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany
The feed-forward propagation through neural networks is crucial for training and inference. To trade off efficiency and accuracy, it has been proposed to consider intermediate outputs of hidden states as data-dependent regularization during training and, ultimately, as early-exits during inference. In this work, we analyze the joint optimization of loss functions computed for the output layer and intermediate layers using optimal control theory. We prove that ResNets trained in this joint fashion exhibit the so-called turnpike phenomenon, this implies that the number of layers required to reach a prescribed loss level is bounded from above independently of the overall network depth. This induces a similarity property across the internal representations of early-exiting networks of varying depths. We connect the turnpike to the overthinking phenomenon, and provide theoretical insights into the success of early-exit criteria derived from softmax probabilities, specifically entropy and max-probability. In a range of experiments, we demonstrate the existence and effect of turnpikes and the resulting similarity in the early-exit performance for ResNets of varying depths.
Figures & tables
Figure 1: Illustration of a ResNet with early-exits (EE), the joint training formulation induces the turnpike phenomenon from optimal control, which implies that early-exiting ResNets of different depths have similar trajectories of the early-exit losses along the network depth.
Figure 2: Example of optimal trajectories of the OCP ( 2 ) for varying horizons N=5,10,…,40 . The red dashed lines indicate the turnpike (xs⋆,ws⋆)=(1,−1) .
Figure 3: The fundamental connection between early-exiting joint training formulation and training as an optimal control problem.
Figure 4: Accuracies on CIFAR-10 for ResNets with residual blocks N∈{18,36,54} with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 5: Training and test loss trajectories across network depth, conditioned on the final prediction outcome on CIFAR-10 with ResNet N=54 and early exits placed at every block ( M=1 ).
Figure 6: Cardinality of the turnpike set #Q^ε and fitted curves A/γ+B in dashed over the stage cost loss weight γ for fixed loss thresholds ε . Results are for CIFAR-10, ResNet with N=54 residual blocks and exits at every block ( M=1 ).
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: (a) Loss and (b) Accuracy trajectories for CIFAR-10 for the homogeneous ResNet architecture over the depth in terms of residual blocks obtained for ResNets with residual blocks N∈{18,36,54} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 8: (a) Loss and (b) Accuracy trajectories for CIFAR-100 for the standard ResNet architecture over the depth in terms of residual blocks obtained for ResNets with residual blocks N∈{18,36,54} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 9: (a) Loss and (b) Accuracy trajectories for CIFAR-100 for the homogeneous ResNet architecture over the depth in terms of residual blocks obtained for ResNets with residual blocks N∈{18,36,54} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 10: (a) Loss and (b) Accuracy trajectories for TinyImageNet for ResNet over the depth in terms of residual blocks obtained for ResNets with residual blocks N∈{18,36,54} and with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 11: (a) Entropy and (b) SDN confusion for training and test data across network depth, conditioned on the final prediction outcome on CIFAR-10 with ResNet N=54,M=1 .
Figure 12: Early-exiting results with the max softmax probability complement as exiting criterion on CIFAR-10 for ResNets with residual blocks N∈{18,36,54} with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 13: Early-exiting results with the entropy as exiting criterion on CIFAR-10 for ResNets with residual blocks N∈{18,36,54} with two levels of early-exit supervision: every residual block ( M=1 ) and every sixth ( M=6 ).
Figure 14: (a) Loss and (b) Accuracy trajectories for CIFAR-10 for the standard ResNet architecture with shared early-exit parameters over the depth in terms of residual blocks obtained for ResNets with residual blocks N∈{18,36,54} and early-exits at every residual block ( M=1 ).
Figure 15: (a) Loss and (b) Accuracy trajectories for CIFAR-10 for the ResNet over the depth in terms of residual blocks obtained for ResNets with N=54 residual blocks trained with varying stage-cost weights and early-exits at every residual block ( M=1 ).
Figure 16: Illustration of a ResNet-v2 architecture while training with our proposed stage cost regularizer penalizing intermediate outputs. We propose to forward the hidden states through the network’s non-trivial skip connections to account for dimensionality projections.
Figure 17: Overview of the main theoretical contributions.
Figure 18: Illustration construction of the infinite-depth ResNet that ensures exponential decay of the cross-entropy loss. First, Theorem E.3 guarantees that all hidden states can be moved to the illustrated configuration in finite depth, where the state of each data point corresponds to the unity vector of its label. Then, the infinite-depth ResNet causes the hidden states to diverge exponentially along the axes of their label thereby ensuring an exponential decay of the cross-entropy loss.
Early-exit neural networks stop processing inputs at intermediate layers when predictions are sufficiently reliable, trading accuracy for lower latency and energy.
We study the early training dynamics of nonlinear residual networks with blocks of zero hidden layers as a model of more general residual networks. We analyze networks in a sequential limit where first width and depth diverge, then the number of training data points diverges, and finally the input dimension diverges. This is a more refined setup compared to the typical mean-field theory analysis in which depth and width diverge but the number of training datapoints and input dimension are fixed. Our main technical result is a diagrammatic computation of both the network output and the hidden representations after the few steps of gradient descent in terms of the statistics of inner products of inputs from the training set. One of our principle conceptual findings is a negative result: in the limit of large input dimension the network output can learn only a linear function of its inputs early in training since higher learned monomials are more and more suppressed in the input dimension and vanish in the large dimension limit. This suggests that mean-field limits of ResNets are surprisingly rigid in the regime of high input dimension and may not be sufficient toy models for understanding feature learning. Finally, we investigate how to ensure hyperparameter transfer for the learning rate as a function of dataset size and input dimension. We test our predictions numerically and find excellent agreement with our theory.
Vladimir Narovlansky, Boris Hanin
ORFE Department, Princeton University, Princeton, NJ 08544, USA · Racah Institute of Physics, The Hebrew University of Jerusalem, Jerusalem 91904, Israel
Early-exit neural networks enable adaptive computation by allowing confident predictions to exit at intermediate layers, achieving 2-8× inference speedup. Despite widespread deployment, their generalization properties lack theoretical understanding -- a gap explicitly identified in recent surveys. This paper establishes a unified PAC-Bayesian framework for adaptive-depth networks. (1) Novel Entropy-Based Bounds: We prove the first generalization bounds depending on exit-depth entropy H(D) and expected depth E[D] rather than maximum depth K, with sample complexity O((E[D]⋅d+H(D))/ε2). (2) Explicit Constructive Constants: Our analysis yields the leading coefficient 2ln2≈1.177 with complete derivation. (3) Provable Early-Exit Advantages: We establish sufficient conditions under which adaptive-depth networks strictly outperform fixed-depth counterparts. (4) Extension to Approximate Label Independence: We relax the label-independence assumption to ε-approximate policies, broadening applicability to learned routing. (5) Comprehensive Validation: Experiments across 6 architectures on 7 benchmarks demonstrate tightness ratios of 1.52-3.87× (all p<0.001) versus >100× for classical bounds. Bound-guided threshold selection matches validation-tuned performance within 0.1-0.3%.
Dongxin Guo, Jikun Wu, Siu Ming Yiu
The University of Hong Kong, Hong Kong, China · Brain Investing Limited, Hong Kong, China
This article offers an overview of recent developments in deep learning from a control vantage point. It reviews several classes of models including feedforward and residual neural networks, transformers, large-language models, and selective state space models while explaining how control theory plays an important role in understanding their training, properties, or architecture design. The article explains how residual neural networks can be interpreted as the discretization of a continuous-time control system thereby enabling the use of control theoretic techniques for its analysis. To illustrate the power of this bridge between control and deep learning, two technical results are discussed: 1) the ability of a residual neural network to approximate arbitrary continuous functions is a non-standard controllability problem that can be solved using geometric nonlinear control and 2) transformers, the key architectural component of most large language-models, can be seen the discretization of a consensus algorithm and thus large language-models exhibit consensus. Another point of contact between control theory and deep learning is the connection between backpropagation, the algorithm used to train neural networks, and optimal control. The article addresses how the older connection between these problems, established in the 80's using discrete-time models can be reconciled with the more recent approach using continuous-time models. Several open problems and directions for future research are discussed, including selective state-space models, a recent class of models inspired by the models used in control.
Álvaro Rodríguez Abella, João Pedro Silvestre, Bahman Gharesifard +1