PAC-Bayesian Theory Establishes Generalization Bounds for Early-Exit Neural Networks

A new theoretical framework addresses the lack of understanding about generalization in early-exit neural networks, which allow predictions to exit at intermediate layers for 2-8× inference speedup. The paper establishes unified PAC-Bayesian analysis with novel entropy-based bounds that depend on exit-depth entropy H(D) and expected depth 𝔼[D] rather than maximum depth K. Sample complexity is shown as 𝒪((𝔼[D]·d + H(D))/ε²). The analysis yields explicit constructive constants with leading coefficient √2ln2 ≈ 1.177 and complete derivation. Sufficient conditions are established under which adaptive-depth networks strictly outperform fixed-depth counterparts. The work fills a theoretical gap explicitly identified in recent surveys of the field.