# Early Time Classification with Accumulated Accuracy Gap Control

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 47 references that are in the map.
- First posted on arXiv 1 Feb 2024.

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

- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Confident Adaptive Language Modeling](https://mlsanity.com/paper/2207.07061/) (2022)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [QuALITY: Question Answering with Long Input Texts, Yes!](https://mlsanity.com/paper/2112.08608/) (2021)
- [Robust Validation: Confident Predictions Even When Distributions Shift](https://mlsanity.com/paper/2008.04267/) (2020)
- [Consistent Accelerated Inference via Confident Adaptive Transformers](https://mlsanity.com/paper/2104.08803/) (2021)
- [FrameExit: Conditional Early Exiting for Efficient Video Recognition](https://mlsanity.com/paper/2104.13400/) (2021)
- [Approaches and Applications of Early Classification of Time Series: A Review](https://mlsanity.com/paper/2005.02595/) (2020)
- [Achieving Risk Control in Online Learning Settings](https://mlsanity.com/paper/2205.09095/) (2022)
- [Calibrated Selective Classification](https://mlsanity.com/paper/2208.12084/) (2022)
- [T-Cal: An optimal test for the calibration of predictive models](https://mlsanity.com/paper/2203.01850/) (2022)
- [Efficiently Controlling Multiple Risks with Pareto Testing](https://mlsanity.com/paper/2210.07913/) (2022)
- [Reliable Prediction Intervals with Regression Neural Networks](https://mlsanity.com/paper/2312.09606/) (2023)
- [Stop&Hop: Early Classification of Irregular Time Series](https://mlsanity.com/paper/2208.09795/) (2022)
- [Conformal Prediction Intervals with Temporal Dependence](https://mlsanity.com/paper/2205.12940/) (2022)
- [Benefit-aware Early Prediction of Health Outcomes on Multivariate EEG Time Series](https://mlsanity.com/paper/2111.06032/) (2021)
- [Risk-Controlling Model Selection via Guided Bayesian Optimization](https://mlsanity.com/paper/2312.01692/) (2023)
- [Temporal Early Exits for Efficient Video Object Detection](https://mlsanity.com/paper/2106.11208/) (2021)
- [Learned, uncertainty-driven adaptive acquisition for photon-efficient scanning microscopy](https://mlsanity.com/paper/2310.16102/) (2023)

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

- [Fast yet Safe: Early-Exiting with Risk Control](https://mlsanity.com/paper/2405.20915/) (2024)
- [Semi-Supervised Risk Control via Prediction-Powered Inference](https://mlsanity.com/paper/2412.11174/) (2024)
- [Conformal Thinking: Risk Control for Reasoning on a Compute Budget](https://mlsanity.com/paper/2602.03814/) (2026)
- [Early Classification of Time Series: A Survey and Benchmark](https://mlsanity.com/paper/2406.18332/) (2024)
- [Streamlining Conformal Information Retrieval via Score Refinement](https://mlsanity.com/paper/2410.02914/) (2024)
- [Confident magnitude-based neural network pruning](https://mlsanity.com/paper/2408.04759/) (2024)
- [Temporal Difference Calibration in Sequential Tasks: Application to Vision-Language-Action Models](https://mlsanity.com/paper/2604.20472/) (2026)
- [Revelation Control](https://mlsanity.com/paper/2608.23860/) (2026)
- [Safe to Stop? Risk-Constrained Stopping for Sequential Clinical Diagnosis Agents](https://mlsanity.com/paper/2609.09678/) (2026)
- [CC-AOS: Cost- and Horizon-Conditioned Amortized Backward Induction for Finite-Horizon Optimal Stopping](https://mlsanity.com/paper/2607.22774/) (2026)
- [From Uncertainty to Clinical Risk: Severity-Aware Conformal Planning for Interactive Medical Diagnosis](https://mlsanity.com/paper/2608.27847/) (2026)

## Abstract (arXiv)

Early time classification algorithms aim to label a stream of features without processing the full input stream, while maintaining accuracy comparable to that achieved by applying the classifier to the entire input. In this paper, we introduce a statistical framework that can be applied to any sequential classifier, formulating a calibrated stopping rule. This data-driven rule attains finite-sample, distribution-free control of the accuracy gap between full and early-time classification. We start by presenting a novel method that builds on the Learn-then-Test calibration framework to control this gap marginally, on average over i.i.d. instances. As this algorithm tends to yield an excessively high accuracy gap for early halt times, our main contribution is the proposal of a framework that controls a stronger notion of error, where the accuracy gap is controlled conditionally on the accumulated halt times. Numerical experiments demonstrate the effectiveness, applicability, and usefulness of our method. We show that our proposed early stopping mechanism reduces up to 94% of timesteps used for classification while achieving rigorous accuracy gap control.