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

arXiv:2604.15764v1 Announce Type: cross Abstract: Early-exit neural networks enable adaptive computation by allowing confident predictions to exit at intermediate layers, achieving 2-8imes 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] dot d + H(D))/epsilon^2). (2) Explicit Constructive Constants: Our analysis yields the leading coefficient sqrt{2ln 2} approx 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 epsilon-approximate policies, broadening applicability to learned routing. (5) Comprehensive Validation: Experiments across 6 architectures on 7 benchmarks demonstrate tightness ratios of 1.52-3.87imes (all p 100imes for classical bounds. Bound-guided threshold selection matches validation-tuned performance within 0.1-0.3%.

Related

• SpecBound: Adaptive Bounded Self-Speculation with Layer-wise Confidence Calibration
• A-IO: Adaptive Inference Orchestration for Memory-Bound NPUs
• Pyramid MoA: A Probabilistic Framework for Cost-Optimized Anytime Inference

Source: arXiv cs.AI | 2026-04-20