Backward Conformal Prediction
Etienne Gauthier, Francis Bach, Michael I. Jordan · 2025
Read Backward Conformal Prediction by Etienne Gauthier, Francis Bach, Michael I. Jordan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13732.txt.
Introduction
Etienne Gauthier, Francis Bach, and Michael Jordan introduce Backward Conformal Prediction in a 2025 paper. Standard conformal prediction fixes a coverage target, say ninety percent, and lets the prediction set swell or shrink as the data demand. In fields like medical diagnosis, a huge set is useless even when it is honest, so size control matters as much as coverage.
Their method flips the bargain: a rule caps how set sizes may behave, and the coverage level adapts to fit. It rests on recent post-hoc validity results built on e-values, plus a leave-one-out estimate of the average miss rate that keeps the promise computable in practice. Theory and experiments back the approach.
Catalog record
| CREATOR | Etienne Gauthier, Francis Bach, Michael I. Jordan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-13732
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Backward Conformal Prediction Etienne Gauthier, Francis Bach, Michael I. Jordan Abstract We introduce Backward Conformal Prediction , a method that guarantees conformal coverage while providing flexible control over the size of prediction sets. Unlike standard conformal prediction, which fixes the coverage level and allows the conformal set size to vary, our approach defines a rule that constrains how prediction set sizes behave based on the observed data, and adapts the coverage level accordingly. Our method builds on two key foundations: (i) recent results by Gauthier et al. (2025) on post-hoc validity using e-values, which ensure marginal coverage of the form ℙ ( Y test ∈ C ^ n α ~ ( X test ) ) ≥ 1 − 𝔼 [ α ~ ] \mathbb{P}(Y_{\rm test}\in\hat{C}_{n}^{\tilde{\alpha}}(X_{\rm test}))\geq 1-\mathbb{E}[\tilde{\alpha}] up to a first-order Taylor approximation for any data-dependent miscoverage α ~ \tilde{\alpha} , and (ii) a novel leave-one-out estimator α ^ LOO \hat{\alpha}^{\rm LOO} of the marginal miscoverage 𝔼 [ α ~ ] \mathbb{E}[\tilde{\alpha}] based on the calibration set, ensuring that the theoretical guarantees remain computable in practice. This approach is particularly useful in applications where large prediction sets are impractical such as medical diagnosis. We provide theoretical results and empirical evidence supporting the validity of our method, demonstrating that it maintains computable coverage guarantees while ensuring interpretable, well-controlled prediction set sizes. 1 Introduction Conformal prediction ( Vovk et al., 2005 ) is a widely used framework for uncertainty quantification in machine learning. It produces set-valued predictions that are guaranteed to contain the true label with high probability, regardless of the underlying data distribution. Given a calibration set of n labeled examples \{(X_{i},Y_{i})\}_{i=1}^{n} and a test point (X_{\rm test},Y_{\rm test}) , all assumed to be drawn from the same unknown distribution over \mathcal{X}\times\mathcal{Y} , conformal prediction constructs a prediction set \hat{C}_{n}^{\alpha}(X_{\rm test}) such that \mathbb{P}(Y_{\rm test}\in\hat{C}_{n}^{\alpha}(X_{\rm test}))\geq 1-\alpha, (1) where the target miscoverage \alpha\in(0,1) is fixed by the practitioner. The probability is taken over both the calibration data and the test point, and the guarantee holds under the assumption that all n+1 points are exchangeable, 1 1 1 Exchangeable random variables are a sequence of random variables whose joint distribution is invariant under any permutation of their indices. a generalization of the independent and identically distributed (i.i.d.) setting. The method uses a score function S:\mathcal{X}\times\mathcal{Y}\to\mathbb{R}_{+} , 2 2 2 In the conformal prediction literature, scores can also be negative. In this work, we explicitly assume nonnegativity to simplify the construction of e-variables like ( 3 ). typically derived from a pre-trained model f , to evaluate how well the model’s prediction f(x) at input x aligns with a candidate label y . In this paper, we assume that the scores are negatively oriented, meaning that a lower score indicates a better fit. The basic idea of conformal prediction is that, under exchangeability, the test score should behave like a typical calibration score: it should not stand out as unusually large. For a new input X_{\rm test} , the conformal set includes all labels y such that the test score S(X_{\rm test},y) is not excessively large compared to the scores from the calibration set. Standard methods rely on comparing score ranks, which can be interpreted in terms of p-values. We refer the reader to Angelopoulos and Bates (2023) ; Angelopoulos et al. (2024) for a recent overview of conformal prediction. Our work focuses on classification with a finite set of labels \mathcal{Y} , a setting that has been the focus of extensive research in conformal prediction ( Lei, 2014 ; Sadinle et al., 2019 ; Hechtlinger et al., 2019 ; Romano et al., 2020 ; Angelopoulos et al., 2021 ; Cauchois et al., 2021 ; Podkopaev and Ramdas, 2021 ; Guan and Tibshirani, 2022 ; Kumar et al., 2023 ) . A key limitation of conformal prediction is that the size of the conformal set is entirely data-driven and cannot be controlled in advance . In many applications, this lack of control can be problematic: overly large prediction sets may be too ambiguous to be useful , especially in high-stakes or resource-constrained settings. This has motivated a growing body of work aiming to reduce the size of conformal sets while maintaining valid coverage guarantees ( Stutz et al., 2022 ; Ghosh et al., 2023 ; Dhillon et al., 2024 ; Kiyani et al., 2024 ; Noorani et al., 2024 ; Yan et al., 2024 ; Braun et al., 2025 ) . In this work, we take a different perspective. Rather than fixing a desired coverage level 1-\alpha , we fix a size constraint rule \mathcal{T} that flexibly determines, based on the observed calibration data \{(X_{i},Y_{i})\}_{i=1}^{n} and the test feature X_{\rm test} , the maximum allowable size of the prediction set. Formally: Definition 1.1 (Size constraint rule) . A size constraint rule is a function \mathcal{T}:\left(\{(X_{i},Y_{i})\}_{i=1}^{n},X_{\rm test}\right)\mapsto\mathcal{T}\left(\{(X_{i},Y_{i})\}_{i=1}^{n},X_{\rm test}\right)\in\{1,\dots,\left\lvert\mathcal{Y}\right\rvert\}, where \left\lvert\mathcal{Y}\right\rvert denotes the size of the label space. Given the observed calibration data \{(X_{i},Y_{i})\}_{i=1}^{n} and test feature X_{\rm test} , the rule \mathcal{T} determines the maximum allowable size of the conformal set for X_{\rm test} . An example of a size constraint rule is the constant size constraint rule, which corresponds to fixing a conformal set size independent from the observed data. In this case, \mathcal{T} is a constant function, and by abuse of notation, we will also denote by \mathcal{T}\in\{1,\dots,\left\lvert\mathcal{Y}\right\rvert\} the constant value it returns. The miscoverage level \tilde{\alpha} is then chosen adaptively to satisfy this constraint. This gives rise to a new method, Backward Conformal Prediction , which ensures that the conformal set \hat{C}_{n}^{\tilde{\alpha}}(X_{\rm test}) has size at most \mathcal{T}\left(\{(X_{i},Y_{i})\}_{i=1}^{n},X_{\rm test}\right) , and provides marginal coverage guarantees of the form: \mathbb{P}(Y_{\rm test}\in\hat{C}_{n}^{\tilde{\alpha}}(X_{\rm test}))\geq 1-\mathbb{E}[\tilde{\alpha}], (2) where the probability is taken over both the calibration set and the test point. The guarantee above, valid up to a first-order Taylor approximation, was established by Gauthier et al. (2025) by constructing conformal sets with e-values, a method known as conformal e-prediction ( Vovk, 2025 ) . In Appendix D , we further derive a guarantee in the same spirit as ( 2 ), but obtained more directly, without relying on a Taylor approximation, and fully estimable from the calibration data. This paper then introduces a practical component: a novel leave-one-out estimator \hat{\alpha}^{\rm LOO} of the marginal miscoverage \mathbb{E}[\tilde{\alpha}] , computed from the calibration set. This allows practitioners to estimate the coverage guarantee in practice and make informed decisions about whether or not to trust the conformal set. The Backward Conformal Prediction procedure is illustrated in Figure 1 . Figure 1 : Overview of Backward Conformal Prediction. The procedure first fixes a (potentially data-dependent) size constraint rule \mathcal{T} , then constructs a conformal set \hat{C}_{n}^{\tilde{\alpha}}(X_{\rm test}) using an adaptive miscoverage level \tilde{\alpha} chosen to respect the size constraint. A leave-one-out estimator \hat{\alpha}^{\rm LOO} is computed on the calibration set to estimate the marginal miscoverage \mathbb{E}[\tilde{\alpha}] , enabling practitioners to decide whether to trust or reject the resulting conformal set based on the estimated coverage. In traditional conformal prediction, the miscoverage level \alpha is fixed in advance. Then, a conformal set satisfying marginal coverage guarantees ( 1 ) is constructed based on the calibration set. However, the size of the resulting conformal set is