Provably Label-Efficient Conformal Prediction

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.

Machine-learning systems often need to say when they are unsure, for example by returning a small set of possible labels rather than a single answer. A common way to make these uncertainty sets reliable is to reserve some labeled examples for calibration, but high-quality labels can be expensive to collect. If we use too few labels, the uncertainty sets may become large and unhelpful; if we use too many, we waste annotation effort. Our work studies how to decide, automatically and on the fly, when to stop collecting calibration labels. We design a rule that checks how much each additional label is expected to improve future predictions, while preserving the reliability guarantees of conformal prediction. Under natural conditions, the rule performs nearly as well as the best fixed number of labels chosen in hindsight. We also show that the same idea can reduce expert labeling cost in a dataset-labeling task where a model labels easy examples and humans label uncertain ones. Experiments on image classification and text-labeling tasks show that our method can save many labels while keeping predictions reliable.