# Early-Exit Neural Networks with Nested Prediction Sets

arXiv: https://arxiv.org/abs/2311.05931 · HTML: https://mlsanity.com/paper/2311.05931/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 10 Nov 2023.

## Builds on (most cited first, 23 of 23)

- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Neural Ordinary Differential Equations](https://mlsanity.com/paper/1806.07366/) (2018)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Evidential Deep Learning to Quantify Classification Uncertainty](https://mlsanity.com/paper/1806.01768/) (2018)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [Predictive Uncertainty Estimation via Prior Networks](https://mlsanity.com/paper/1802.10501/) (2018)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [BERT Loses Patience: Fast and Robust Inference with Early Exit](https://mlsanity.com/paper/2006.04152/) (2020)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Multiscale Deep Equilibrium Models](https://mlsanity.com/paper/2006.08656/) (2020)
- [The Right Tool for the Job: Matching Model and Instance Complexities](https://mlsanity.com/paper/2004.07453/) (2020)
- [Adaptive Inference through Early-Exit Networks: Design, Challenges and Directions](https://mlsanity.com/paper/2106.05022/) (2021)
- [Consistent Accelerated Inference via Confident Adaptive Transformers](https://mlsanity.com/paper/2104.08803/) (2021)
- [Improved Techniques for Training Adaptive Deep Networks](https://mlsanity.com/paper/1908.06294/) (2019)
- [Depth Uncertainty in Neural Networks](https://mlsanity.com/paper/2006.08437/) (2020)
- [Admissible anytime-valid sequential inference must rely on nonnegative martingales](https://mlsanity.com/paper/2009.03167/) (2020)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [A Survey on Dynamic Neural Networks for Natural Language Processing](https://mlsanity.com/paper/2202.07101/) (2022)
- [Confidence sequences for sampling without replacement](https://mlsanity.com/paper/2006.04347/) (2020)
- [Fixing Overconfidence in Dynamic Neural Networks](https://mlsanity.com/paper/2302.06359/) (2023)
- [Towards Anytime Classification in Early-Exit Architectures by Enforcing Conditional Monotonicity](https://mlsanity.com/paper/2306.02652/) (2023)
- [Jointly-Learned Exit and Inference for a Dynamic Neural Network : JEI-DNN](https://mlsanity.com/paper/2310.09163/) (2023)
- [Uncertainty quantification using martingales for misspecified Gaussian processes](https://mlsanity.com/paper/2006.07368/) (2020)

## Built on by (most cited first, 6 of 6)

- [Fast yet Safe: Early-Exiting with Risk Control](https://mlsanity.com/paper/2405.20915/) (2024)
- [Uncertainty Is Not Enough: Value-of-Information Routing for Mixtures of LoRA Experts](https://mlsanity.com/paper/2608.02528/) (2026)
- [Adaptive Spiking with Plasticity for Energy Aware Neuromorphic Systems](https://mlsanity.com/paper/2508.11689/) (2025)
- [Rethinking Calibration for Early-Exit Neural Networks](https://mlsanity.com/paper/2508.21495/) (2025)
- [Networking-Aware Energy Efficiency in Agentic AI Inference: A Survey](https://mlsanity.com/paper/2604.07857/) (2026)
- [Theoretical Guarantees for One-Shot Magnitude Pruning and Compute-Adaptive Early Exit](https://mlsanity.com/paper/2609.12337/) (2026)

## Abstract (arXiv)

Early-exit neural networks (EENNs) enable adaptive and efficient inference by providing predictions at multiple stages during the forward pass. In safety-critical applications, these predictions are meaningful only when accompanied by reliable uncertainty estimates. A popular method for quantifying the uncertainty of predictive models is the use of prediction sets. However, we demonstrate that standard techniques such as conformal prediction and Bayesian credible sets are not suitable for EENNs. They tend to generate non-nested sets across exits, meaning that labels deemed improbable at one exit may reappear in the prediction set of a subsequent exit. To address this issue, we investigate anytime-valid confidence sequences (AVCSs), an extension of traditional confidence intervals tailored for data-streaming scenarios. These sequences are inherently nested and thus well-suited for an EENN's sequential predictions. We explore the theoretical and practical challenges of using AVCSs in EENNs and show that they indeed yield nested sets across exits. Thus our work presents a promising approach towards fast, yet still safe, predictive modeling