# How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 16 Sep 2026.

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

- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Active Testing: Sample-Efficient Model Evaluation](https://mlsanity.com/paper/2103.05331/) (2021)
- [Optimal strategies for reject option classifiers](https://mlsanity.com/paper/2101.12523/) (2021)
- [Overcoming Common Flaws in the Evaluation of Selective Classification Systems](https://mlsanity.com/paper/2407.01032/) (2024)
- [Structured Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1706.05198/) (2017)
- [Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover](https://mlsanity.com/paper/1303.0726/) (2013)
- [All models are wrong, some are useful: Model Selection with Limited Labels](https://mlsanity.com/paper/2410.13609/) (2024)
- [Consensus-Driven Active Model Selection](https://mlsanity.com/paper/2507.23771/) (2025)

## Abstract (arXiv)

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.