Provably Label-Efficient Conformal Prediction

Andrew Ilyas, Joonhyuk Ko, Jingwu Tang, Steven Wu, Jiahao Zhang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:49578-49597, 2026.

Abstract

Conformal prediction converts any black-box predictor into one with finite-sample, distribution-free coverage guarantees, outputting prediction sets $T(x)$ that contain the true label with probability at least $1-\alpha$. To construct these prediction sets, conformal prediction relies on a randomly sampled “calibration set” of labeled examples. In many applications, however, this labeled calibration set is costly to collect, creating a tradeoff between upfront labeling cost and downstream utility of the conformal predictor. In this work, we study conformal prediction with costly label queries, where unlabeled examples arrive i.i.d. and labels can be queried one at a time. After $m$ queries, we form a conformal predictor; the upfront cost of this predictor is the calibration set size $m$, and its efficiency is the expected prediction set size $\mathbb{E}|T_m(X)|$. We design an online stopping rule $\hat{m}$ that automatically balances the upfront cost against conformal efficiency while preserving the original conformal guarantee. Theoretically, we show that under mild regularity assumptions, the expected total cost of our stopping rule matches the best fixed calibration size in hindsight. Experimentally, we find that our stopping rule reduces cost compared to standard choices of $m$ from the literature by 40.6% $\pm$ 2.3%. Finally, we demonstrate a reduction from the probably approximately correct labeling problem of Candès et al. (2025) to CP, under which our stopping rule minimizes the total labeling cost.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-ilyas26a, title = {Provably Label-Efficient Conformal Prediction}, author = {Ilyas, Andrew and Ko, Joonhyuk and Tang, Jingwu and Wu, Steven and Zhang, Jiahao}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {49578--49597}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ilyas26a/ilyas26a.pdf}, url = {https://proceedings.mlr.press/v306/ilyas26a.html}, abstract = {Conformal prediction converts any black-box predictor into one with finite-sample, distribution-free coverage guarantees, outputting prediction sets $T(x)$ that contain the true label with probability at least $1-\alpha$. To construct these prediction sets, conformal prediction relies on a randomly sampled “calibration set” of labeled examples. In many applications, however, this labeled calibration set is costly to collect, creating a tradeoff between upfront labeling cost and downstream utility of the conformal predictor. In this work, we study conformal prediction with costly label queries, where unlabeled examples arrive i.i.d. and labels can be queried one at a time. After $m$ queries, we form a conformal predictor; the upfront cost of this predictor is the calibration set size $m$, and its efficiency is the expected prediction set size $\mathbb{E}|T_m(X)|$. We design an online stopping rule $\hat{m}$ that automatically balances the upfront cost against conformal efficiency while preserving the original conformal guarantee. Theoretically, we show that under mild regularity assumptions, the expected total cost of our stopping rule matches the best fixed calibration size in hindsight. Experimentally, we find that our stopping rule reduces cost compared to standard choices of $m$ from the literature by 40.6% $\pm$ 2.3%. Finally, we demonstrate a reduction from the probably approximately correct labeling problem of Candès et al. (2025) to CP, under which our stopping rule minimizes the total labeling cost.} }
Endnote
%0 Conference Paper %T Provably Label-Efficient Conformal Prediction %A Andrew Ilyas %A Joonhyuk Ko %A Jingwu Tang %A Steven Wu %A Jiahao Zhang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ilyas26a %I PMLR %P 49578--49597 %U https://proceedings.mlr.press/v306/ilyas26a.html %V 306 %X Conformal prediction converts any black-box predictor into one with finite-sample, distribution-free coverage guarantees, outputting prediction sets $T(x)$ that contain the true label with probability at least $1-\alpha$. To construct these prediction sets, conformal prediction relies on a randomly sampled “calibration set” of labeled examples. In many applications, however, this labeled calibration set is costly to collect, creating a tradeoff between upfront labeling cost and downstream utility of the conformal predictor. In this work, we study conformal prediction with costly label queries, where unlabeled examples arrive i.i.d. and labels can be queried one at a time. After $m$ queries, we form a conformal predictor; the upfront cost of this predictor is the calibration set size $m$, and its efficiency is the expected prediction set size $\mathbb{E}|T_m(X)|$. We design an online stopping rule $\hat{m}$ that automatically balances the upfront cost against conformal efficiency while preserving the original conformal guarantee. Theoretically, we show that under mild regularity assumptions, the expected total cost of our stopping rule matches the best fixed calibration size in hindsight. Experimentally, we find that our stopping rule reduces cost compared to standard choices of $m$ from the literature by 40.6% $\pm$ 2.3%. Finally, we demonstrate a reduction from the probably approximately correct labeling problem of Candès et al. (2025) to CP, under which our stopping rule minimizes the total labeling cost.
APA
Ilyas, A., Ko, J., Tang, J., Wu, S. & Zhang, J.. (2026). Provably Label-Efficient Conformal Prediction. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:49578-49597 Available from https://proceedings.mlr.press/v306/ilyas26a.html.

Related Material