# Volume Optimality in Conformal Prediction with Structured Prediction Sets

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 23 Feb 2025.

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

- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [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)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Conformal Prediction with Large Language Models for Multi-Choice Question Answering](https://mlsanity.com/paper/2305.18404/) (2023)
- [Learning by Transduction](https://mlsanity.com/paper/1301.7375/) (2013)
- [Learning Optimal Conformal Classifiers](https://mlsanity.com/paper/2110.09192/) (2021)
- [Distributional conformal prediction](https://mlsanity.com/paper/1909.07889/) (2019)
- [Theoretical Foundations of Conformal Prediction](https://mlsanity.com/paper/2411.11824/) (2024)
- [Nested conformal prediction and quantile out-of-bag ensemble methods](https://mlsanity.com/paper/1910.10562/) (2019)
- [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)
- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Converting High-Dimensional Regression to High-Dimensional Conditional Density Estimation](https://mlsanity.com/paper/1704.08095/) (2017)
- [Boosted Conformal Prediction Intervals](https://mlsanity.com/paper/2406.07449/) (2024)

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

- [Online Conformal Prediction with Efficiency Guarantees](https://mlsanity.com/paper/2507.02496/) (2025)
- [Computing High-dimensional Confidence Sets for Arbitrary Distributions](https://mlsanity.com/paper/2504.02723/) (2025)
- [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)
- [Co-optimization for Adaptive Conformal Prediction](https://mlsanity.com/paper/2603.01719/) (2026)
- [On the Burden of Achieving Fairness in Conformal Prediction](https://mlsanity.com/paper/2605.14260/) (2026)
- [AdaptNC: Adaptive Nonconformity Scores for Conformal Prediction under Distribution Shift](https://mlsanity.com/paper/2602.01629/) (2026)
- [Compact Conformal Subgraphs](https://mlsanity.com/paper/2602.07530/) (2026)
- [Efficient Online Conformal Selection with Limited Feedback](https://mlsanity.com/paper/2605.14953/) (2026)
- [Robustly Reliable Learning for Regression](https://mlsanity.com/paper/2610.17381/) (2026)

## Abstract (arXiv)

Conformal Prediction is a widely studied technique to construct prediction sets of future observations. Most conformal prediction methods focus on achieving the necessary coverage guarantees, but do not provide formal guarantees on the size (volume) of the prediction sets. We first prove an impossibility of volume optimality where any distribution-free method can only find a trivial solution. We then introduce a new notion of volume optimality by restricting the prediction sets to belong to a set family (of finite VC-dimension), specifically a union of k-intervals. Our main contribution is an efficient distribution-free algorithm based on dynamic programming (DP) to find a union of k-intervals that is guaranteed for any distribution to have near-optimal volume among all unions of k-intervals satisfying the desired coverage property. By adopting the framework of distributional conformal prediction (Chernozhukov et al., 2021), the new DP based conformity score can also be applied to achieve approximate conditional coverage and conditional restricted volume optimality, as long as a reasonable estimator of the conditional CDF is available. While the theoretical results already establish volume-optimality guarantees, they are complemented by experiments that demonstrate that our method can significantly outperform existing methods in many settings.