# Online Conformal Prediction with Efficiency Guarantees

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 28 references that are in the map.
- First posted on arXiv 3 Jul 2025.

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

- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Least Ambiguous Set-Valued Classifiers with Bounded Error Levels](https://mlsanity.com/paper/1609.00451/) (2016)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Conformal PID Control for Time Series Prediction](https://mlsanity.com/paper/2307.16895/) (2023)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [CD-split and HPD-split: efficient conformal regions in high dimensions](https://mlsanity.com/paper/2007.12778/) (2020)
- [Flexible distribution-free conditional predictive bands using density estimators](https://mlsanity.com/paper/1910.05575/) (2019)
- [Online conformal prediction with decaying step sizes](https://mlsanity.com/paper/2402.01139/) (2024)
- [Achieving Risk Control in Online Learning Settings](https://mlsanity.com/paper/2205.09095/) (2022)
- [Conformal Validity Guarantees Exist for Any Data Distribution (and How to Find Them)](https://mlsanity.com/paper/2405.06627/) (2024)
- [Volume Optimality in Conformal Prediction with Structured Prediction Sets](https://mlsanity.com/paper/2502.16658/) (2025)

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

- [Non-Asymptotic Analysis of Efficiency in Conformalized Regression](https://mlsanity.com/paper/2510.07093/) (2025)
- [Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery](https://mlsanity.com/paper/2512.16875/) (2025)
- [Elements of Conformal Prediction](https://mlsanity.com/paper/2603.23923/) (2026)
- [Efficient Online Conformal Selection with Limited Feedback](https://mlsanity.com/paper/2605.14953/) (2026)
- [Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction](https://mlsanity.com/paper/2607.26577/) (2026)

## Abstract (arXiv)

We study the problem of conformal prediction in a novel online framework that directly optimizes efficiency. In our problem, we are given a target miscoverage rate α > 0, and a time horizon T. On each day t ≤ T an algorithm must output an interval It subseteq [0, 1], then a point yt ∈ [0, 1] is revealed. The goal of the algorithm is to achieve coverage, that is, yt ∈ It on (close to) a (1 - α)-fraction of days, while maintaining efficiency, that is, minimizing the average volume (length) of the intervals played. This problem is an online analogue to the problem of constructing efficient confidence intervals. We study this problem over arbitrary and exchangeable (random order) input sequences. For exchangeable sequences, we show that it is possible to construct intervals that achieve coverage (1 - α) - o(1), while having length upper bounded by the best fixed interval that achieves coverage in hindsight. For arbitrary sequences however, we show that any algorithm that achieves a μ-approximation in average length compared to the best fixed interval achieving coverage in hindsight, must make a multiplicative factor more mistakes than α T, where the multiplicative factor depends on μ and the aspect ratio of the problem. Our main algorithmic result is a matching algorithm that can recover all Pareto-optimal settings of μ and number of mistakes. Furthermore, our algorithm is deterministic and therefore robust to an adaptive adversary. This gap between the exchangeable and arbitrary settings is in contrast to the classical online learning problem. In fact, we show that no single algorithm can simultaneously be Pareto-optimal for arbitrary sequences and optimal for exchangeable sequences. On the algorithmic side, we give an algorithm that achieves the near-optimal tradeoff between the two cases.