Early-exit networks save compute by attaching small classifiers ("exits") partway through a network and stopping as soon as one of them is confident enough. Bayesian neural networks place a probability distribution over weights so the model can report what it does not know. The cheapest such distribution, mean-field, treats every weight as independent of every other weight. The usual defense of this shortcut is depth. Liberty or Depth proves that multiplying several independent random weight matrices yields correlated functions, so a deep mean-field network can match full-covariance posteriors. Early exiting removes exactly that depth. An input leaving at block 3 of a 16-block network has passed through only three stochastic layers. We predict that its mean-field uncertainty is distorted in a specific way: it underestimates the share of uncertainty that comes from the weights, which is the share that more computation could reduce. That share is the signal an exit rule needs.
The proposal makes two claims and tests both. The first is a measurement claim: the gap between mean-field and correlated (Kronecker-factored) posteriors is largest at shallow exits and shrinks with exit depth. The second is a design claim. Spending a fixed budget for covariance modelling unevenly, with correlated structure near shallow exits and mean-field deeper in, gives better halting decisions than a uniform posterior. "Better" here has a concrete meaning: the rule can separate inputs that more layers would fix from inputs no layer will fix. Uniform compute over inputs is the usual target of adaptive inference. Here we also question uniform posterior budget over depth, and the second choice turns out to set how well the first can be relaxed.
Core Claim
Write the predictive entropy at exit $k$ as $H_k = A_k + I_k$. Here $A_k$ is the expected entropy under sampled weights, which is noise the model cannot resolve. $I_k$ is the mutual information between the prediction and the weights, the part that reflects weight uncertainty. Deeper computation can plausibly shrink $I_k$ but not $A_k$.
Rethinking Calibration for Early-Exit Neural Networks shows that confidence-based exits waste compute on "futile samples," inputs that no later layer solves. Its fix is a deterministic meta-classifier over softmax trajectories. We claim the decomposition does this separation more directly. High $I_k$ means "continue." High $A_k$ with low $I_k$ means "stop now, even if wrong."
This only works if $I_k$ is faithful at shallow exits. The Product Effect argument suggests mean-field $I_k$ is least faithful there. The independence assumption also has known costs. Pitas shows it makes PAC-Bayes bounds vacuous because diagonal Gaussians cannot follow correlated valleys of the loss surface. Jin et al. show that trained weights are strongly correlated and that accounting for this improves generalization prediction.
The novel, falsifiable part is the depth dependence. We expect the mean-field deficit in $I_k$, relative to a correlated reference, to decay with the number of stochastic layers $k$. If it does not, the design claim collapses, and we would report that.
Research Program
The method side reuses existing machinery. Correlated posteriors come from the Kronecker-factored Laplace approximation of Ritter et al.. It fits post hoc around trained weights, approximates each layer's curvature as a Kronecker product of two small matrices, and is known to beat diagonal Laplace and MC Dropout on out-of-distribution entropy. Mean-field posteriors come from diagonal Laplace and from diagonal variational training in the style of Graves. The matrix-Gaussian variational posterior of Louizos & Welling is a second correlated reference at small scale.
Backbones are multi-exit ResNets and ViTs trained with self-distillation as in EENet. Because Laplace is post hoc, the backbone and exit heads stay fixed across all posterior variants. Differences in halting therefore come only from the uncertainty estimate.
Stage one is the measurement. On small MLPs (Iris, UCI regression, the $y=x^3+\epsilon$ toy used by Ritter et al.), we can run Hamiltonian Monte Carlo (an exact but expensive sampler) as ground truth. We then plot, per exit, the divergence of mean-field and KFAC predictives from the sampler, and the ratio of their $I_k$. On CIFAR-100 and ImageNet, where sampling is infeasible, we use KFAC as the reference and track per-exit expected calibration error, negative log-likelihood, and out-of-distribution AUROC from $I_k$.
Stage two is allocation. We fix a covariance memory budget of $B$ extra parameters, and we compare four ways to spend it: uniform diagonal, uniform KFAC on the last block before each exit, depth-matched, and inverted. Depth-matched places full Kronecker factors on blocks feeding shallow exits and diagonal elsewhere. Inverted, the reverse, is a control.
Stage three is halting. At exit $k$, the rule stops when $I_k$ falls below a threshold $\tau_k$ or when $A_k$ exceeds a futility threshold $\phi_k$. Thresholds are tuned on validation data under a FLOPs budget. We also run a with-recall variant following Hold That Exit. That paper shows any no-recall rule can be arbitrarily far from optimal, so the uncertainty signal is tested both inside a naive rule and inside a near-optimal one.
Language-model reasoning is explicitly out of scope. Thought Calibration and ODAR operate on generated tokens, not layer depth, and a clean result on vision is a prerequisite.
Baselines
The naive reference is a fixed-depth backbone plus a max-softmax exit threshold on the same multi-exit network. Every method must beat this on the accuracy-versus-FLOPs curve to matter.
The strongest existing deterministic competitor is EEFP from Rethinking Calibration for Early-Exit Neural Networks. It is a 2-layer MLP over top-$k$ confidences and exit history, built specifically for the futile-sample problem we target, and it costs about 0.001% extra compute. It is evaluated on CIFAR-100, ImageNet-1k, TinyImageNet and DomainNet, but the file contains no raw accuracy numbers: no reported result found on Lacuna for EEFP accuracy at matched FLOPs. We will re-run it on our backbones with its own feature set and the same validation split and tuning budget as our thresholds.
The strongest learned scheduler is EENet. It reports accuracy gains of up to 1.95% on image tasks over BranchyNet, MSDNet, PABEE and MAML-stop as budgets tighten, and 93.45% on AgNews at 100ms/sample. We train its scheduler on the same backbone.
A further uncertainty baseline is the variance across exits computed so far, adapted from Early Exit Ensembles, which reports up to 2x better calibration and negative log-likelihood than MC Dropout and Deep Ensembles. For a sense of scale on the correlated posterior itself, Ritter et al. report about 79% CIFAR-100 accuracy for a Wide ResNet under KFAC Laplace.
Beating these means a lower FLOPs-to-accuracy curve at matched validation tuning. It also means higher futile-sample AUROC than EEFP on DomainNet shifts. The key ablation isolates the ingredient: same budget $B$, same rule, depth-matched versus uniform versus inverted allocation.
Why not just…?
Why not just use mean-field everywhere, since Liberty or Depth shows depth fixes it? That result is stated for full-depth evaluation, which is the regime early exits leave. Stage one tests whether it extends to shallow exits. If mean-field $I_k$ matches the correlated reference at every exit, the reviewer is right, and we would report the negative result rather than push the method.
Why not just put a Laplace posterior on each exit head alone? This is the most serious threat. Last-layer Laplace is cheap, and it captures correlation within the head, which may be where most of the useful uncertainty lives. The allocation ablation includes "head-only KFAC" at equal budget. If it matches depth-matched allocation, we narrow the claim to "correlated heads at shallow exits." That would still be a usable finding about where posterior structure must live, but it would be a smaller one.
Why not just use MC Dropout or the spread across exits? MC Dropout needs 10–50 passes per Early Exit Ensembles, which defeats the purpose of early exiting, and Ritter et al. find it underestimates out-of-distribution uncertainty. The spread across exits is free, but at the first exits only one or two predictions exist, so it has the least information exactly where we need it. Both run as baselines at matched FLOPs.
Why not just a better deterministic meta-classifier? EEFP already is one. Our claim is that under shift its softmax inputs degrade while $I_k$ does not. The DomainNet and TinyImageNet comparison settles this directly.
Decisive Checks
Three results decide the project.
First, on the small models with sampler ground truth, the per-exit mean-field deficit in $I_k$ must decrease with $k$. A flat curve refutes the premise.
Second, on CIFAR-100 and ImageNet with ViT and ResNet backbones, depth-matched allocation must beat uniform and inverted allocation at equal budget $B$, on both the accuracy-versus-FLOPs curve and futile-sample AUROC. It must also beat head-only KFAC; otherwise the claim narrows as described above.
Third, under DomainNet domain shift, the $A_k$/$I_k$ rule must keep more of its in-distribution compute savings than EEFP and EENet, measured as the fraction of FLOPs saved at a fixed accuracy drop. Without this, the extra machinery is not justified over deterministic schedulers.
References
- Liberty or Depth: Deep Bayesian Neural Nets Do Not Need Complex Weight Posterior Approximations
- Rethinking Calibration for Early-Exit Neural Networks
- Dissecting Non-Vacuous Generalization Bounds based on the Mean-Field Approximation
- How does Weight Correlation Affect Generalisation Ability of Deep Neural Networks?
- A Scalable Laplace Approximation for Neural Networks
- Practical Variational Inference for Neural Networks
- Structured and Efficient Variational Deep Learning with Matrix Gaussian Posteriors
- EENet: Learning to Early Exit for Adaptive Inference
- Hold That Exit: Near Optimal Early-Exit Inference via Recall
- Early Exit Ensembles for Uncertainty Quantification