The Price of Hard Coverage Constraints in Online Conformal Prediction
Organizations: Department of Computer Science, George Mason University
Abstract
Conformal prediction provides distribution-free uncertainty quantification, but in sequential deployment, standard coverage guarantees can still allow substantial fluctuations in the number of miscoverages over time. We study an online setting in which prediction sets are produced one round at a time and the cumulative number of miscoverages must stay within a prescribed budget throughout deployment.Such a hard coverage guarantee can be enforced by enlarging prediction sets, but how much additional prediction-set size is fundamentally necessary remains unclear. We characterize this unavoidable efficiency cost over prediction rounds. Remarkably, the cost persists even with i.i.d.\ data, a known score distribution, and perfect knowledge of the population-optimal prediction set. Under suitable regularity conditions relating coverage and prediction-set size, we determine the minimum cumulative excess prediction-set size required by any online method satisfying the hard coverage constraint. This minimum cost is for expected cost at a fixed time known in advance, for the largest expected cost over all fixed times up to , and for the expected worst realized cost when the evaluation time is chosen in hindsight. We further show that these rates can be attained using past scores, without knowing the score distribution. Thus, even perfect statistical knowledge does not make sequential reliability free.
Figures & tables
| Criterion minimized over feasible policies | Construction | Optimal price |
|---|---|---|
| (i) Terminal: | Counting (Algorithm 1 ) | |
| (ii) Expected prefixes: | Barrier (Algorithm 2 ) | |
| (ii ′ ) Adaptive stopping: | Barrier (Algorithm 2 ) | |
| (iii) Retrospective: | Barrier (Algorithm 2 ) |
| Algorithm 1 Counting | Algorithm 2 Barrier | Algorithm 3 Empirical ranks |
| Parameters: miscoverage level , horizon . Round input: , cumulative miscoverage count . Output: requested miscoverage probability . | Parameter: miscoverage level . No horizon is required. Round input: , miscoverage slack . Output: requested miscoverage probability . | Parameter: fixed nonconformity score . Round input: , sorted scores . Output: prediction set , miscoverage indicator , updated scores. |
| 1. Compute counts once. Set all , then . For and , set 2. Read counts. Set 3. Return . | 1. Set the barrier. Let . Set for , and otherwise. 2. Compute weights. 3. Return . | 1. Set and . 2. Draw an independent and set . 3. Set to the empty-set map if , the full-set map if , and otherwise with threshold . 4. Observe and issue . Observe , store , and return . |
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
| Method | |||
|---|---|---|---|
| 0.05 | Barrier | 42.67 | |
| 0.05 | Sine variant | 42.56 | |
| 0.05 | Quota guard | ||
| 0.10 | Barrier | 43.90 | |
| 0.10 | Sine variant | 43.76 | |
| 0.10 | Quota guard |
| Decaying ACI | Selected fixed-step ACI | Width variant | |
|---|---|---|---|
| 160 | 2.617 (0.024) | 2.691 | 3.986 |
| 640 | 3.699 (0.023) | 3.246 | 4.898 |
| 2,560 | 5.664 (0.028) | 5.114 | 6.335 |
| 10,240 | 9.228 (0.039) | 8.627 | 9.639 |
| 16,380 | 11.116 (0.039) | 10.158 | 11.484 |
| 65,536 | 20.100 (0.040) | 17.008 | 20.308 |
| Ridge | Extra Trees | |||
|---|---|---|---|---|
| Split | Gap | Percentile range | Gap | Percentile range |
| 1 | 0.000 | [0.000, 5.657] | 1.728 | [0.063, 3.996] |
| 2 | 1.457 | [0.000, 3.261] | 0.033 | [0.052, 3.916] |
| 3 | 2.932 | [0.030, 6.563] | 1.832 | [0.017, 7.021] |
| 4 | 0.904 | [0.094, 4.198] | 0.214 | [0.170, 4.804] |
| 5 | 2.902 | [0.035, 5.313] | 0.492 | [0.005, 2.328] |
| Predictor | Method | Length | Full | Empty | Difference [95% interval] | |
|---|---|---|---|---|---|---|
| Ridge | Original ACI | 0.3644 | 9.84 | 1.68 | 0.0000 | |
| Ridge | ACI + ranks | 0.3657 | 9.84 | 1.94 | 0.0000 | — |
| Ridge | Barrier | 0.3595 | 9.79 | 0.46 | 0.0013 | |
| Extra Trees | Original ACI | 0.2910 | 9.84 | 1.69 | 0.0000 | |
| Extra Trees | ACI + ranks | 0.2921 | 9.84 | 1.89 | 0.0000 | — |
| Extra Trees | Barrier | 0.2856 | 9.79 | 0.52 | 0.0024 |
| Predictor | Method | Length | (%) | Violations (%) | Max excess |
|---|---|---|---|---|---|
| Ridge | ACI | 0.3542 | 10.00 | 100.0 | 12 |
| Ridge | ACI + guard | 0.3644 | 9.84 | 0.0 | 0 |
| Ridge | Barrier | 0.3595 | 9.79 | 0.0 | 0 |
| Extra Trees | ACI | 0.2795 | 10.00 | 100.0 | 12 |
| Extra Trees | ACI + guard | 0.2910 | 9.84 | 0.0 | 0 |
| Extra Trees | Barrier | 0.2856 | 9.79 | 0.0 | 0 |
| Predictor | Method | Length | (%) | Mean peak | Max peak | Full (%) | Empty (%) |
|---|---|---|---|---|---|---|---|
| Ridge | ACI | 0.3542 | 10.00 | 8.16 | 12 | 0.02 | 0.0000 |
| Ridge | ACI + guard | 0.3644 | 9.84 | 0.00 | 0 | 1.68 | 0.0000 |
| Ridge | ACI + ranks | 0.3544 | 10.00 | 8.06 | 12 | 0.09 | 0.0016 |
| Ridge | ACI + ranks + guard | 0.3657 | 9.84 | 0.00 | 0 | 1.94 | 0.0000 |
| Ridge | Barrier | 0.3595 | 9.79 | 0.00 | 0 | 0.46 | 0.0013 |
| Extra Trees | ACI | 0.2795 | 10.00 | 8.41 | 12 | 0.02 | 0.0000 |
| Work | Constraint and decision information | Comparator and time objective |
|---|---|---|
| Berry and Gallager (2002) , Propositions 4.2, 4.5 | Nonnegative queue. Current channel and buffer observed. Stationary policies under its regularity assumptions. | Long-run average power above the unconstrained power–rate frontier, with an inverse-square gap as average delay grows. |
| Chen and Wang (2025) , Theorem 3.1 | Fixed initial inventory. Current reward and demand observed. Distribution and horizon known. | Expected terminal reward gap to a hindsight linear program. Rates depend on the request distribution. |
| Chen et al. (2026) , Theorems 5.3, 5.8 | Inventory nonnegative at every prefix. Current reward, demand and replenishment observed. Unknown distribution. | Expected terminal reward gap to a prefix-feasible hindsight integer program. Logarithmic and square-root regimes on different instance classes. |
| McMahan and Zhu (2024) , Theorem 3 | Almost-sure prefix budgets. Action precedes realized cost. Policies may use cumulative cost history. | Optimal expected total reward among feasible policies over a finite horizon. State augmentation supports planning and learning. |
| Training size per group | Mean | Standard error | |
|---|---|---|---|
| 64 | 0.35 | ||
| 256 | 0.32 | ||
| 1,024 | 0.30 | ||
| 4,096 | 0.31 | ||
| 16,384 | 0.34 |
Conformal Prediction
Conformal prediction wraps predictive models with calibrated sets or intervals that provide statistical coverage guarantees.
See all 395 papers