How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction
cs.LG · stat.ML
Quick verdict
It derives an exact stopping test, covering-LP certificate benchmarks, and prelabel lower bounds for choosing models by AUGRC, and shows theoretically and empirically that selective comparisons can demand large label budgets; the framework is rigorous and reproducible, but headline constants rest on independence assumptions and acquisition stays far from certificates.
Summary
The paper quantifies how many evaluation labels are required to compare trained classifiers by AUGRC on a fixed pool, showing that identical predictions do not settle selective comparisons because confidence ranks weight the same errors differently. It contributes: (i) an exact interval stopping test (Theorem 1) that remains valid after adaptive queries; (ii) a covering LP (Theorem 2) bracketing the minimum certificate within K-1 labels; (iii) a prelabel lower bound (Theorem 3) computable before any label is read. Under independent uniform confidence orders and iid Bernoulli errors, the prelabel bound tends to n/4, a two-candidate certificate to n/2, yet every exact acquisition policy reads almost all n labels (Propositions 2-3). Empirically, across 108 feature-panel comparisons on nine tabular datasets, disagreement-label sets settle every accuracy choice but no AUGRC choice; a 20% budget is ruled out in 96/108 conditions; minimum certificates average 56-57% of the pool. On ten CIFAR conditions with pretrained image classifiers, exact score choice reads 68-91% of 10,000 labels, reduced to 50-67% at AUGRC tolerance 5e-4. Limitations: asymptotic independence assumptions that real confidence orders (mean pairwise Spearman 0.51) violate, a ~25-point gap between best acquisition and minimum certificate, and empirical scope limited to tabular panels plus two CIFAR test pools.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- An exact stopping test (Theorem 1) certifies the full-pool AUGRC winner over all unread label completions and stays valid after arbitrary adaptive queries.
- A covering LP (Theorem 2) brackets the minimum certificate within K-1 labels of optimal for any pool size, and a prelabel bound (Theorem 3) rules out insufficient budgets before any label is read.
- Under independent uniform confidence orders the prelabel bound tends to one quarter of the pool, while with iid Bernoulli errors a two-candidate certificate needs about half and every exact acquisition policy reads almost all labels (Propositions 2-3).
- Across 108 feature-panel comparisons on nine datasets, disagreement labels settle every accuracy choice but no AUGRC choice, 20% budgets are ruled out in 96/108 conditions, and minimum certificates average 56-57% of the pool.
- On ten pretrained CIFAR conditions, confidence-score choice requires 68-91% of 10,000 labels for exact selection, reduced to 50-67% at AUGRC tolerance 5e-4.
Strengths
Exact, worst-case guarantees rather than estimates
Theorem 1's interval test (L_jk >= 0 or > 0 per rival) certifies the full-pool winner under every unread completion with no approximation or independence assumptions, and the proof is pointwise in the observation history so it survives adaptive querying; Section 6.4 shows the shared test dominates separate intervals and midpoint centering (savings of 17.66 and 10.58 points on the original 36 conditions; 4.95 points on the added 72).
A computable hindsight benchmark that scales
Theorem 2's covering LP rounds to within K-1 labels of the true minimum certificate independent of pool size (z + K - 1), and Section 9 reports rational weak-dual bounds plus integer witness checks; on the CIFAR grid, 1,666,594 and 2,504,903 prefixes were independently audited, supporting the claimed enclosures.
Three-quantity theory that cleanly separates certificate from acquisition cost
Decision-relevant framing and honest accounting
Reproducibility infrastructure
Weaknesses
External validity of the headline constants
Acquisition remains expensive and unexplained
Narrow and partly idiosyncratic empirical scope
Guarantees require a frozen pool and binary or shared-multiclass predictions
Deep-model pool is development-contaminated
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
How many labels do you need to compare two models by AUGRC?
This paper shows the answer can be large even when the models make identical predictions, because confidence ranks weight early errors more. In an idealized model with independent random confidence orders, you can prove a budget of roughly a quarter of the pool is impossible to beat as a lower bound, a hindsight-optimal certificate needs about half the pool, but any practical labeling strategy that guarantees the exact winner must read almost every label. On real datasets and pretrained CIFAR classifiers, exact selection typically used 68-91% of a 10,000-label pool, dropping to 50-67% when a small AUGRC tolerance is allowed.
What is a certificate in model comparison?
A certificate is a set of evaluation examples whose revealed labels are enough to guarantee the winner: no matter what the labels of the unread examples turn out to be, the same model remains the full-pool AUGRC winner. The paper computes the smallest such set after labeling (via a covering linear program) and a lower bound on it before any label is read, so a proposed labeling budget can be ruled out in advance if it is below that bound.
What is AUGRC and how is it different from AURC?
AUGRC (area under the generalized risk-coverage curve) integrates the total accepted error mass over coverage, following Traub et al. (2024), whereas the classical AURC integrates the conditional error among accepted examples. In AUGRC, an error made on an example the model accepts early contributes more than one accepted late, so two classifiers with identical predictions can still differ once their confidence rankings differ.
Does this method actually save labels in practice?
Mostly it measures and certifies cost rather than promising savings. The exact stopping test can stop early when the winner is already certain, and allowing an AUGRC tolerance helps (for example, reading 50-67% instead of 68-91% on CIFAR pools at tolerance 5e-4), but even the best tested query order remained about 25 percentage points above the hindsight-optimal certificate, and the theory shows that under independence assumptions any exact strategy must eventually read almost all labels.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures are available only as captions in the extracted text, so visual claims (e.g., Figures 4, 7, 8, 10-13) could not be inspected directly.
- Proofs were assessed as presented; no line-by-line re-derivation of the permutation-statistics and martingale arguments was performed.
- Tables appear reflowed in the extraction; column-wise readings (e.g., Table 1's enclosure intervals) were cross-checked against the narrative text but minor parsing errors are possible.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.