How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction
Abstract
Classifiers can make identical predictions yet require labels to compare their selective performance: confidence ranks weight the same errors differently. We quantify this requirement for the area under the generalized risk-coverage curve (AUGRC). A prelabel lower bound rules out insufficient budgets. With all labels known, a covering linear program bounds the minimum number of labels sufficient to fix the winner (the certificate size) within K−1 labels for K candidates. For fixed K, independent uniform orders and identical predictions, the prelabel bound approaches one quarter of the pool. With iid Bernoulli errors independent of the orders, every exact acquisition policy reads almost all labels asymptotically, although a two-candidate certificate needs only half. Across 108 feature-panel comparisons on nine datasets, disagreement labels settle every accuracy choice but no AUGRC choice. A 20% budget is ruled out in 96 conditions; certificates need 56-57% on average. On ten conditions with pretrained image classifiers, confidence-score choice reads 68-91% of 10,000 labels for exact selection and 50-67% with AUGRC tolerance 5×10−4. An exact stopping test works with any acquisition order. Together, these results link confidence ranks to label budgets and certified model comparison.
Related
- SafeRestore: Detector-Relative Risk Certificates for Selective Industrial Image Restoration
- How Synthetic Labels Improve Conformal Prediction: A Perspective on Conditional Coverage
- Semantic Prior Smoothing for Conformal Prediction in Multiple-Choice Question Answering with API-Only Large Language Models
- Non-Invariance in Nested Prediction Models under Selective Predictor Availability
- Abstention Spends Its Budget on Local Label Variance More Than on Novelty: Auditing Conformal Calibration and Selective Prediction under Molecular Scaffold Shift
BibTeX
@misc{kuboyama2026many,
title = {{How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction}},
author = {Tetsuji Kuboyama},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18622},
eprint = {2609.18622},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18622},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction
AU - Tetsuji Kuboyama
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18622
UR - https://arxiv.org/abs/2609.18622
AB - Classifiers can make identical predictions yet require labels to compare their selective performance: confidence ranks weight the same errors differently. We quantify this requirement for the area under the generalized risk-coverage curve (AUGRC). A prelabel lower bound rules out insufficient budgets. With all labels known, a covering linear program bounds the minimum number of labels sufficient to fix the winner (the certificate size) within K−1 labels for K candidates. For fixed K, independent uniform orders and identical predictions, the prelabel bound approaches one quarter of the pool. With iid Bernoulli errors independent of the orders, every exact acquisition policy reads almost all labels asymptotically, although a two-candidate certificate needs only half. Across 108 feature-panel comparisons on nine datasets, disagreement labels settle every accuracy choice but no AUGRC choice. A 20% budget is ruled out in 96 conditions; certificates need 56-57% on average. On ten conditions with pretrained image classifiers, confidence-score choice reads 68-91% of 10,000 labels for exact selection and 50-67% with AUGRC tolerance 5×10^−4. An exact stopping test works with any acquisition order. Together, these results link confidence ranks to label budgets and certified model comparison.
ER -