mlsanityData to 14 Oct 2026

When Do Early-Exit Networks Generalize? A PAC-Bayesian Theory of Adaptive Depth

arXiv 2604.15764 ↗First posted 17 Apr 2026cs.LG cs.AIcited by 0

On the map: Efficient LLM inference and serving → Early exit and edge inference

Abstract (arXiv)

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 mathbbE[D] rather than maximum depth K, with sample complexity O((mathbbE[D] · d + H(D))/ε2). (2) Explicit Constructive Constants: Our analysis yields the leading coefficient √2ln 2 ≈ 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%.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Early exit and edge inference, one of 12 directions in Efficient LLM inference and serving. Builds on 23 of its 33 references that are in the map. First posted on arXiv 17 Apr 2026.

Builds on

23 of 33 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Fast yet Safe: Early-Exiting with Risk Control31 May
  2. 2024LayerSkip: Enabling Early Exit Inference and Self-Speculative Decoding25 Apr
  3. 2022Confident Adaptive Language Modeling14 Jul

Other references · 20

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  2. 2019Contrastive Multiview Codingcited by 1,301
  3. 2017Spectrally-normalized margin bounds for neural networkscited by 686
  4. 2017BranchyNet: Fast Inference via Early Exiting from Deep Neural Networkscited by 596
  5. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 533
  6. 2021Dynamic Neural Networks: A Surveycited by 408
  7. 2020DeeBERT: Dynamic Early Exiting for Accelerating BERT Inferencecited by 332
  8. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 314
  9. 2018Stronger generalization bounds for deep nets via a compression approachcited by 307
  10. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  11. 2020BERT Loses Patience: Fast and Robust Inference with Early Exitcited by 273
  12. 2019Depth-Adaptive Transformercited by 236
8 more
  1. 2020FastBERT: a Self-distilling BERT with Adaptive Inference Timecited by 226
  2. 2020Reasoning About Generalization via Conditional Mutual Informationcited by 147
  3. 2023SkipDecode: Autoregressive Skip Decoding with Batching and Caching for Efficient LLM Inferencecited by 89
  4. 2023Fast and Robust Early-Exiting Framework for Autoregressive Language Models with Synchronized Parallel Decodingcited by 80
  5. 2020Why should we add early exits to neural networks?cited by 70
  6. 2023Tighter Information-Theoretic Generalization Bounds from Supersamplescited by 22
  7. 2024Information-Theoretic Generalization Bounds for Deep Neural Networkscited by 10
  8. 2021E2CM: Early Exit via Class Means for Efficient Supervised and Unsupervised Learningcited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Optimal Depth of Neural Networks
  2. 2021Adaptive Inference through Early-Exit Networks: Design, Challenges and Directions
  3. 2023Adaptive Depth Networks with Skippable Sub-Paths
  4. 2022PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization
  5. 2026Depth Laws for the Precision Floor of Trained Neural Networks: Amplification, Residual Scaling, and a Quantization-Aware Training Paradox
  6. 2026Scaling Adaptive Depth with Norm-Agnostic Residual Networks
  7. 2023Window-Based Early-Exit Cascades for Uncertainty Estimation: When Deep Ensembles are More Efficient than Single Models
  8. 2026ANCRe: Adaptive Neural Connection Reassignment for Efficient Depth Scaling