PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tetsuji Kuboyama

arXiv:2609.18622v1cs.LGstat.ML

TL;DR

When predictions agree, confidence ranks can still make selective model comparisons depend on labels, making label budgets a central question. The paper develops bounds and an exact stopping test, and reports substantial label requirements across model comparisons.

  • Problem

    How many evaluation labels are needed to choose the full-pool selective-performance winner when fixed models can make identical predictions but rank examples differently?

    Source: §1 · p. 1

  • Method

    The paper derives a prelabel lower bound, an exact stopping test, and a covering-LP bound on the minimum labels sufficient to certify a winner.

    Source: §1 · pp. 1–2

  • Results

    Across 108 panel comparisons, a 20% budget is ruled out in 96 conditions and minimum certificates average 56–57% of the pool; pretrained-image comparisons require 68–91% of labels for exact choice.

    Source: §8 · p. 20

  • Takeaways & Limitations

    The current bounds can guarantee a candidate's minimum risk before the tie-breaking choice is fixed, separating a risk guarantee from a certified winner.

    Source: §5 · p. 11

    Guarantees assume fixed pools, candidates, and ranks, and do not cover retraining or transfer; experiments use K ≤8.

    Source: §8 · p. 20

Abstract

from arXiv · show

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\times10^{-4}$. An exact stopping test works with any acquisition order. Together, these results link confidence ranks to label budgets and certified model comparison.

1 Introduction

The paper asks how many labels are needed to compare fixed models when confidence ranks can make selective performance differ despite identical predictions. It develops bounds and a stopping test, then studies label requirements across theoretical settings and model comparisons.

1 Introduction

  • For selective prediction, a row on which candidates predict the same label can still decide the winner because earlier accepted errors count more in AUGRC.For accuracy, such a row cannot change their ordering.Source: §1 · p. 1
  • A certificate fixes the winner regardless of unread labels; the paper gives a prelabel lower bound, an acquisition-time detector, and a bound on minimum certificate size within K −1 labels.These measures separate required information from the cost of finding it.Source: §1 · p. 1
  • With identical predictions and independent uniform confidence orders, the prelabel bound tends to one quarter of the pool; with iid errors independent of ranks, exact policies read almost all labels asymptotically.In the latter setting, certificates need at least half the labels.Source: §1 · p. 2
  • Across nine datasets, the experiments examine when agreement-row labels are needed, which budgets are insufficient, and how requirements vary with tolerance and candidate sets.Pretrained multiclass classifiers are also used to demonstrate certified confidence-score choice.Source: §1 · p. 2

2 Setting

The setting measures selective performance with AUGRC, which integrates accepted-error mass over coverage. Its finite-pool definition uses trapezoidal interpolation and averages over confidence ties.

2 Setting

  • AUGRC integrates accepted-error mass over coverage rather than conditional error among accepted examples; for binary loss, 0 ≤ A ≤ 1/2.Source: §2 · p. 2
  • For a finite pool, accepted-error mass is linearly interpolated between consecutive coverage points, and the metric averages over all orders within a confidence tie.Source: §2 · p. 2
  • At zero-based rank r, an error receives trapezoidal weight (n − r − 1/2)/n^2; the right-endpoint sum instead adds 1/(2n^2) per error.Source: §2 · p. 3

3 Certifying a choice from partial labels

With fixed predictions and confidence ranks, the paper tests whether partial labels already determine the full-pool AUGRC winner. A shared-label stopping test certifies choices under arbitrary adaptive queries and can stop no later than separate risk intervals.

3 Certifying a choice from partial labels

  • For fixed classifier–confidence pairs, the target is the candidate with smallest full-pool AUGRC, with the smaller index breaking ties; querying a row reveals its label to all candidates.Source: §3 · p. 3
  • Exact lower and upper bounds on pairwise risk differences are attained by assigning each unread label according to its coefficient's sign.Source: §3 · p. 3
  • The exact stopping test certifies candidate k as the winner for every unread-label completion when its pairwise lower bounds satisfy the fixed tie rule, and it remains valid after arbitrary adaptive queries.Source: §3 · p. 3
  • In the four-row example, the test certifies B after all four labels, although the certificate LP shows that three labels suffice and row 4 is unnecessary for that labeling.Source: §3 · p. 3, Figure 2 · p. 4
  • The shared test never stops later than the separate-interval test because separate intervals can assign incompatible values to the same unread label, while shared labels preserve cancellation.Source: §3 · p. 4

4 How confidence ranks require labels

Confidence ranks can make labels necessary even when predictions agree, because they weight shared errors differently. The section separates labels needed to certify a winner from labels an acquisition policy must read to find a certificate.

4.1 Minimum certificates and their computation

  • Rounding an optimal covering-LP solution gives a certificate of size at most z + K − 1, where z is the relaxation value.The certificate is the smallest set of observed rows and labels that fixes the winner under every completion; for two candidates, sorting gains gives an exact minimum certificate.Source: §4.1 · pp. 4–6

4.2 A bound before labels are read

  • Before labeling, sorting each rival comparison’s potential gains gives a lower bound on certificate size that depends only on predictions and confidence ranks.In the rank-only example, C(0) = n − 1 although accuracy ties under every completion and needs zero labels.Source: §4.2 · p. 6

4.3 Independent confidence orders

  • For fixed K and identical predictions with independent uniform confidence orders, the prelabel bound and certificate size approach one quarter and at least one half of the pool, respectively.For two candidates, the certificate fraction converges to 1/2 under iid Bernoulli errors independent of the orders.Source: §4.3 · pp. 7–8

4.4 The cost of finding a certificate

  • Under identical predictions, independent uniform confidence orders, and independent Bernoulli errors, every exact policy reads almost all labels asymptotically, although a two-candidate certificate needs half.For fixed K, the acquisition fraction converges to 1 uniformly over eligible policies; the two-candidate certificate fraction converges to 1/2.Source: §4.3 · p. 7, §4.4 · pp. 9–10

4.5 Tolerance, multiclass predictions and other objectives

  • With tolerance τ, the certificate can certify a candidate within τ of minimum AUGRC under every completion, and the K − 1 rounding bound still applies.The framework also covers shared multiclass predictions through a common error-bit representation and other scores that sum binary losses with fixed nonnegative weights.Source: §4.5 · p. 10

5 Using the information bounds

Section 5 turns the information bounds into budget checks and query-time stopping rules. It also distinguishes labels read from the minimum certificate size.

5 Using the information bounds

  • If the budget B is below C, no acquisition policy can certify the full-pool choice within budget for any label vector; B ≥ C is not sufficient to guarantee certification.The pair bounds can be computed by sorting in O(K^2 n log n).Source: §5 · p. 10
  • When a budget is ruled out, changing only the query policy cannot help; the proposed alternatives are increasing the budget, setting a risk tolerance, or revising the candidate set.Recompute the bound after changing the evaluation design, before collecting labels.Source: §5 · p. 10
  • Static query orders prioritize rows by their largest pairwise-width contribution or summed pairwise contribution, while adaptive versions recompute scores after eliminating candidates that lose under every completion.A query can shrink a pairwise width without raising a lower bound; initialization costs O(K^2 n) and updates cost O(K^2), apart from choosing the next row.Source: §5 · pp. 10–11
  • The comparison loop reads each label at most once and stops when every unread completion agrees; any policy for choosing unread rows is valid.The paper compares several such policies in Section 6.Source: Figure 6 · p. 11
  • A candidate’s exact worst-case excess AUGRC over unread completions is computed from current bounds; a zero gap guarantees minimum risk, but not necessarily the tie-breaking winner.In the example, one query makes B optimal under either remaining label, while another label can still produce a tie won by A.Source: §5 · p. 11
  • After labeling, bounds on C(y) and the number read, Nread, bound how many extra labels the policy used, because finding a minimum certificate may itself require queries.Proposition 3 quantifies this distinction in the independent-order model.Source: §5 · p. 11

6 Experiments

The experiments compare label requirements across feature-panel and pretrained-image-model choices, showing that agreement rows can settle accuracy but not AUGRC choices. Certified exact selection often requires most of the evaluation pool, while tolerance reduces the required labels.

6.1 Candidates and datasets

  • Candidates were fixed before evaluation labels; 108 feature-panel conditions used four or eight candidates across nine datasets and three stratified train/evaluation splits.The six-dataset extension was fixed before downloading tables, while the pretrained-model extension was fixed before inference or evaluation.Source: §6 · pp. 11–12, §6.1 · p. 12

6.2 Which labels are needed

  • Disagreement labels settled all 108 accuracy choices but none of the AUGRC choices; certifying the actual AUGRC winner still required agreement-row labels equal to 41–42% of the pool.Disagreement rows averaged 20.91% of a pool, with dataset values from 13.5–36.5%.Source: §6.2 · p. 12
  • A 20% budget was ruled out in 96/108 conditions, while minimum certificates averaged 56.37–57.16% of the pool across nine datasets.At an 80% budget, static range certified 30/108 exact choices and 76/108 with tolerance .005.Source: §6.2 · p. 12, Figure 7 · p. 13

6.3 Confidence choice for deep models

  • Across four original pretrained-model conditions, exact confidence-score choices read 68.07–90.95% of labels, versus 50.23–59.66% at τ = .0005.All four exact choices matched their full-pool winners, and each score won somewhere.Source: §6.3 · p. 14

6.3.1 Protocol and verification

  • Six architecture-family follow-up conditions read 69.85–87.02% for exact selection and 57.04–67.13% at τ = .0005.All six exact choices matched their full-pool winners; the original and follow-up protocols share two test pools.Source: §6.3 · p. 14, §6.3.1 · p. 15
  • The image-model comparison used three confidence scores on identical predictions, with hashed scores and rank weights before label access; all 176 acquisition paths and 1,666,594 prefixes were independently checked.The original checkpoints had used test-split validation during development, and training costs were excluded from evaluation-label savings.Source: §6.3.1 · p. 15

6.4 Stopping rule versus acquisition order

The experiments separate savings from the stopping rule from savings due to acquisition order. The shared certificate test and adaptive pair-sum order reduce labels, but acquisition remains substantially above the minimum certificate.

6.4 Stopping rule versus acquisition order

  • On the 72 added conditions, separate intervals, centered intervals, and the shared test read 99.43%, 90.15%, and 85.21% of the pool, respectively.The shared test saved 4.95 percentage points over centering, was earlier in 56/72 conditions, tied in 16, and was never later.Source: Figure 9 · p. 15, §6.4 · p. 16
  • The shared test saved 17.66 points over separate intervals and 10.58 over centering on the original 36 conditions.Exact duplicate candidates were merged for all three stopping rules.Source: §6.4 · p. 16, Table 2 · p. 16
  • On six added datasets, adaptive pair-sum read 80.45% of the pool versus 85.21% for static range, yet remained 25.07–25.84 points above the certificate.The saving was 4.76 points on average; Nemenyi comparisons separated adaptive pair-sum from random, VMA, and Model Selector, but not the other heuristics.Source: §6.4 · p. 16, Table 3 · p. 16, Figure 11 · p. 17
  • For the Ionosphere split-731 example, the prelabel lower bound was 16 labels, while the first strictly positive stopping bounds occurred at 73, 77, and 106 labels under shared, centered, and separate tests.At 72 labels the shared bound was zero; hindsight bracketed the minimum at 49–50 labels.Source: Figure 10 · p. 17

6.5 Tolerance and candidate-set sensitivity

Tolerance reduces certificate requirements and can change the selected candidate within the allowed risk gap. Matched-pool and second-generator analyses find substantial certificate sizes, while finite simulations qualify what can be inferred about rank dependence.

6.5 Tolerance and candidate-set sensitivity

  • At τ = .005, minimum certificates averaged 44.83–45.69% and adaptive acquisition read 69.74%, while the returned candidate changed in 28/108 conditions, always within tolerance.Moving from zero tolerance to .005 reduced mean minimum certificate size by 10.67–12.33 percentage points.Source: §6.5 · pp. 17–18, Figure 12 · p. 18

6.6 Matched pools and a second candidate generator

  • The 3,600 matched pools had mean certificate bounds of 60.15–61.15%, versus 56.37–57.16% for fitted panels.Predictions were identical in the matched model; only pool size and candidate count were matched to real collections.Source: §6.6 · p. 18, Figure 13 · p. 19
  • With the second panel generator, minimum certificates averaged 45.81–46.27% and adaptive acquisition 70.72%; disagreement labels left 53/54 choices unresolved.Adaptive acquisition remained 24.45–24.91 percentage points above the minimum certificate.Source: §6.6 · pp. 18–19, Figure 13 · p. 19

6.7 Finite-pool simulations and correlated orders

  • For two candidates under independent uniform orders, simulated mean certificate fractions rose from .37 at n = 50 to .46 at n = 5706; the prelabel bound rounded to .25 from n = 500.These are finite-pool observations, and the certificate limit for K > 2 is left open.Source: §6.7 · p. 19
  • Estimated rank-bound limits across Gaussian-copula correlations ρ = 0, .3, .6, .9, .99 were .250, .237, .223, .209, .204; at ρ = 1, coincident orders require zero.The passage cautions that this finite grid is not a bound for the whole family and that correlation alone does not determine the bound.Source: §6.7 · p. 19

7 Related work

Prior work studies selective prediction, candidate construction, label-efficient evaluation, and certificate complexity. This paper frames selective comparison as fixing a full-pool winner under every unread-label completion and quantifies the resulting label requirements.

7 Related work

  • Selective prediction orders acceptance by confidence or conditional risk, while this work fixes candidate models before acquiring evaluation labels.The paper uses AUGRC as defined by Traub et al. (2024).Source: §7 · p. 19
  • Label-efficient evaluation includes sampling and selection methods such as Active Testing (Kossen et al., 2021), loss-difference sampling, Model Selector (Okanovic et al., 2025), and CODA (Kay et al., 2025).The comparison here evaluates acquisition orders under a common guarantee: fixing the selective comparison under every unread completion.Source: §7 · pp. 19–20
  • Certificate complexity measures the size of the smallest sufficient label set, and the paper quantifies rank-based requirements, including a 1/4 prelabel limit.For two candidates, certificates need asymptotically n/2 labels under the stated model, although every exact policy reads almost all n; for fixed K, the covering formulation bounds minimum certificate size within K −1 labels.Source: §7 · p. 20

8 Discussion

Across the 108 panel comparisons, a 20% budget is ruled out in 96, while minimum certificates average 56–57% of the pool. The bounds distinguish budgets ruled out before labeling from acquisition costs benchmarked against certificates, under stated scope and assumptions.

8 Discussion

  • A 20% budget is ruled out in 96 of 108 panel comparisons, and minimum certificates average 56–57% of the pool.For ten pretrained image-classifier comparisons, exact choice reads 68–91% of evaluation labels; an AUGRC tolerance of 5 × 10−4 reduces this to 50–67%.Source: §8 · p. 20
  • The bounds rule out budgets below C before labeling and benchmark acquisition cost against C(y) afterwards.In the independent-order model, even optimal acquisition reads almost all labels, so certificate size is not a promised query cost; tolerance can reduce both costs.Source: §8 · p. 20
  • Guarantees require fixed pools, candidates, and ranks, and do not cover retraining or transfer; experiments use K ≤8.Asymptotic results assume independent uniform orders, while certificate and acquisition limits also assume iid errors independent of ranks; no general acquisition bound for fitted data follows.Source: §8 · p. 20

9 Implementation and reproducibility

The implementation uses specified software and computational settings, reports certificate-LP runtime for six MAGIC conditions, and provides protocols and reproduction materials in an archive.

9 Implementation and reproducibility

  • For n = 5,706 and K = 8, the certificate LP pipeline took 22–26 ms across all six MAGIC conditions.The reported range is based on seven-run medians after one warm-up, excluding input loading.Source: §9 · p. 20
  • Experiments use row-level splits for Breast Cancer, Wine, and Digits, while MAGIC contains simulated events.Selected indicators can share an original variable, so their count is not a measurement cost; training labels are not counted as saved.Source: §9 · p. 20
  • The companion source-and-evidence archive includes frozen protocols, outputs, verification code, and reproduction commands.The accompanying LaTeX source contains every plotted coordinate and can be rebuilt without downloading datasets or checkpoints.Source: §9 · p. 20

AI Use Statement

Generative AI assisted with mathematical analysis, experiments, and manuscript preparation; the author reports checking proofs and numerical results and taking responsibility for the final content.

AI Use Statement

  • Generative AI tools assisted with mathematical analysis, experimental work, and manuscript preparation.The author set the research questions and scope, checked proofs, crosschecked numerical results against saved outputs using independent verification code, and takes responsibility for the final content.Source: AI Use Statement · p. 21
  • The author reports setting the research questions and scope and checking the proofs.The statement also reports crosschecking numerical results against saved outputs using independent verification code.Source: AI Use Statement · p. 21
  • The author states responsibility for the final content.The statement accompanies the reported verification of numerical results against saved outputs.Source: AI Use Statement · p. 21
Loading 2609.18622v1…