CS Paper Radar

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

Tetsuji Kuboyama

cs.LG stat.ML ·submitted 2026-09-16 13:10 UTC · v1
theory

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

Comment
22 pages, 13 figures, 3 tables. Includes proofs and experimental details in the main text

Closest papers

Nearest neighbours by meaning across the whole index.

Large Classification-Risk-Optional Label Acquisition

cs.LG stat.ML ·2026-09-06 ·F. Setoudehtanzangi, Geoffrey J. McLachlan
hot direction similarity 0.63
Abstract

We study how a limited labeling budget should be allocated to minimize multiclass zero-one classification risk. We consider parametric classification problems in which features are observed for all sampling units while class labels can be acquired selectively. By combining the Fisher information supplied by an acquired label with the local geometry of multiclass excess risk, we derive an acquisition criterion that minimizes the leading asymptotic coefficient of expected multiclass excess risk. The resulting rule values a label according to how strongly its information is aligned with parameter directions that perturb the active Bayes decision boundary, rather than according to posterior uncertainty or global parameter information alone. We characterize the oracle acquisition design, establish its threshold structure, and derive face-specific and cost-sensitive extensions. An analytic example shows that posterior uncertainty and classification value can produce different, and even reversed, acquisition rankings. We further develop a two-stage adaptive procedure that attains the oracle leading-risk criterion under regularity conditions and provide explicit results for Gaussian discriminant analysis. Three-class QDA experiments illustrate the resulting acquisition geometry, while an application to the six-class Statlog Landsat Satellite data shows that classification-risk acquisition can differ materially from both uncertainty-based acquisition and the complete-classification-information comparator. The adaptive classification-risk design attains lower mean error than this Fisher comparator across the labeling budgets considered, although it does not uniformly outperform entropy or margin sampling and differences among the targeted strategies become small as the labeling budget increases.

0.25

Risk-Controlled Selective LLM Answering by Pricing Label-Free Checks

cs.LG cs.AIcs.CL ·2026-09-27 ·Dongyub Jude Lee, Jungseob Lee, Chanjun Park, Hyeonseok Moon, Heuiseok Lim
code/datahot directionhighly cited similarity 0.62
Abstract · 29 pages, 6 figures, 24 tables. Dongyub Jude Lee and Jungseob Lee contributed equally

Serving an answer from a large language model requires deciding when to abstain, yet a verifier's ranking accuracy alone does not determine the error rate among served answers. We introduce PriceCheck, which builds a compact family of decision rules from label-free checks such as re-solving a problem. Each check has a price: its agreement rates on correct and incorrect answers and its cost per run. Prices fitted on a small, class-enriched labelled set compose into predictions of a schedule's coverage and cost, guiding which checks to run and when to stop. A calibration test then selects a schedule at a stated selective-risk target. In mathematics, the selected schedules serve 76.1% of answers on average and keep held-out selective risk below 1.5% on all 15 splits. Under the shared testing protocol, PriceCheck serves more answers at that target than reward models, a prompted judge, the generator's confidence and a trained correctness classifier. At matched coverage, it keeps the fewest wrong answers among these scorers. Across 118 diagnostic schedules, price-based coverage predictions have a rank correlation of 0.97 with observed coverage. These results show that choosing how checks are combined and stopped matters alongside how well a verifier ranks answers. Code is available at https://github.com/js-lee-AI/PriceCheck.

0.74

Hard or Mislabeled? Failure Screens Enrich Vision Benchmarks for Label Errors

cs.CV cs.AIcs.LG ·2026-11-14 ·Haolin Guo
benchmark similarity 0.62
Abstract · 28 pages, 5 figures, 16 tables

Hard vision benchmarks often keep images that strong classifiers get wrong. Since a classifier is also marked wrong when the label is wrong, such failure screens may collect label errors. We measure this on ImageNet's twice-relabeled validation set with 103 classifiers. Among the 1,892 images that all 66 supervised classifiers get wrong, 61% have a wrong label, versus 11.1% overall. The fewer images a screen lets through, the more of them are mislabeled, along approximately one curve. Fit on one model family, this curve predicts the screens of two held-out model families with a mean error of 2.4 percentage points, and replays of ImageNet-D's and ImageNet-Hard's screens within 0.1 and 6.3 points. On new pools, ImageNet-V2 and CIFAR-10, enrichment at the strictest screens is stronger than the curve predicts: on ImageNet-V2, by human relabeling, 67% of the images that all 66 classifiers get wrong are mislabeled, against 46% predicted. Screens that let models choose among only some of the classes, as ImageNet-A's does (200 of 1,000), fall below the curve. By ReImageNet, 32% of ImageNet-Hard's ImageNet images have no correct label. ScreenAudit, which comprises an audit tool, a script that rebuilds corrected answer sets for the 5,464 decided ImageNet-Hard images (of 5,646) from ReImageNet's gated release, and per-image audits of 1,198 benchmark images, will be released later.

0.35

Train After You Measure: a Pre-Registered Learning Curve for Fine-Tuning Typed Decision Models on One User's Labels

cs.CL cs.LG ·2026-11-16 ·Federico Lucca
code/data similarity 0.61
Abstract · 9 pages, 1 figure, 6 tables. Companion to arXiv:2610.32955. Pre-registered study; code at https://github.com/federicolucca/foyer-measure (ta…

Fine-tuning a small typed decision model on one user's email labels did not clear the margin we pre-registered over a logistic regression trained on the same labels. In earlier work, about two hundred labels and a TF-IDF logistic regression had the highest point accuracy on this inbox, though not significantly above the best hosted model; we ask whether the same labels, given to a decision model, close the gap. A first registered study, on a generic 4B base with cross-validation and message type only, stayed below the baseline at every label budget (-1.8 to -7.3 points). The main study was registered before any fine-tuning run: a fixed test set of 135 emails never used for selection, LoRA adapters on the public Tev1-0.8B and Tev1-4B decision models, nested subsets of 50 to 587 labels, two seeds and five decision fields on a free T4 GPU. Four of its five hypotheses are refuted--two in the fine-tunes' favour--and one is confirmed for one model. On message type the 4B model misses the registered three-point margin at 400 labels (+2.6) and passes it with all 587 (+3.3); with all labels both models are above the baseline by +0.7 and +3.3 points, where one email is 0.74 points and a 95% interval is about 15 points wide, and the 4B model is clearly ahead in type macro-F1 (0.581 vs. 0.406). On the three action switches the baseline is ahead at every label budget for both models (0.931 vs. 0.904 and 0.899 mean accuracy with all labels), at under a millisecond per question against 306 and 1681 ms. The 0.8B type curve barely improves after 300 labels and then falls. The baseline never predicts the two rarest classes (7 offers and 8 spam in the training pool); the fine-tuned models find spam in some runs, not consistently across seeds. We list the explanations we did not test and say when a new attempt would be worth making. Scripts are public; weights and emails are not.

0.31

Cost-Aware Post-Hoc Deferral Under Calibration and Shift: An Environmental AI Case Study

cs.SE cs.LG ·2026-09-07 ·Haoran Yu, Lifei Liu, Danping Zhang
similarity 0.61
Abstract

Choosing a deferral policy for a frozen classifier requires more than ranking uncertain cases: confidence may be miscalibrated, errors have unequal costs, reviewers can err, and deployment data can leave calibration support. We study these interactions through EcoTrust, a post-hoc framework that compares automatic action with review using a six-group error-risk estimator, class-asymmetric costs, reviewer accuracy, and an optional support gate. On a Columbia River thermal-stress testbed, the learned estimator improves error-ranking area under the receiver operating characteristic curve from 0.869 to 0.889, but Chow's confidence rule has lower in-distribution cost (0.416 versus 0.567 per day). Across 12 off-the-shelf backends, learned risk and a calibration-matched, class-aware confidence estimator each beat raw Chow on six; a paired year-block bootstrap does not resolve their mean cost difference. In transfer to ten river stations, the gate flags every case and becomes an always-review fallback, attaining the lowest cost on eight stations only when review is perfect and unconstrained. These results characterize decision boundaries on one controlled task: richer risk signals do not reliably improve on calibrated confidence, and detected extrapolation does not imply transferable case-level ranking.

0.57

StepCOPS: Closed-Testing Lower-Tail Certificates for Language-Model Policy Selection

cs.CL ·2026-08-26 ·Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma
benchmark similarity 0.60
Abstract

Post-training pipelines must select one language-model policy from many checkpoints, prompts, and decoding rules. Mean evaluator scores can conceal rare failures, whereas simultaneous candidate-wise confidence bounds can be unnecessarily conservative. We introduce StepCOPS, which uses an independent proposal split to nominate one lower-tail floor per candidate, exact binomial tests on a fresh certification split, and Holm's step-down procedure to certify a set of floors. With probability at least $1-δ$, every certified floor, including the largest floor used for policy selection, is below its candidate's population lower $α$-quantile. This guarantee assumes i.i.d. evaluation units while allowing arbitrary within-unit dependence across candidates. Across 24 predeclared configurations and 11 benchmarks, StepCOPS obtains 96.4% selected-policy coverage over 500 paired trials, raises the certified floor by 1.5 points over both proposal-Bonferroni and exact COPS, remains 0.6 points below the large-reference jury oracle, and abstains in 2.4% of trials. Shadow-judge, benchmark-native, artifact, and leave-one-judge-out audits characterize the proxy boundary: the guarantee applies to the fixed jury score, not directly to human safety.

0.47

Predicted Class Correction: Conformal Thresholds for Classes with No Calibration Data

cs.LG cs.CV ·2026-10-18 ·One Octadion, Novanto Yudistira, Yuta Nakashima
similarity 0.60
Abstract · 23 pages including supplementary material, 4 figures

Class-conditional conformal prediction calibrates a separate score threshold for every class and therefore requires labelled calibration examples of every class. In long-tailed deployments these are exactly what is missing: rare classes are left with few or no held-out examples, and existing methods are either undefined for them or fall back to the shared marginal threshold. We ask whether the per-class correction can instead be predicted from descriptors of the class that require no labels at all. We propose Predicted Class Correction (PCC), which regresses the offset between the per-class and the marginal conformal quantile on geometric descriptors of the classifier head, shrinks the prediction by a scalar selected on the labelled classes, and refits a single marginal offset. The descriptors depend only on the model's weights, so a class with zero calibration examples still receives its own threshold, and since only one scalar is calibrated, split conformal's marginal guarantee is retained. On ImageNet, PCC improves worst-class coverage on such classes by 0.058 [0.006, 0.110] at matched average set size, 42% of an oracle that sees the test labels. Of eight baselines on the same splits, six change the statistic by exactly zero and the best reaches 0.016 with an interval containing zero, so PCC is the only one distinguishable from no improvement; the gain persists with only 100 labelled classes out of 1000. A second finding concerns evaluation: worst-class coverage becomes unmeasurable before it becomes unachievable. Below roughly 35 test examples per class no improvement can be shown even for an oracle, so a null result there reflects the evaluation set, not the method. Restricting evaluation above this depth recovers a significant improvement on Pl@ntNet-300K, where the effect had appeared absent.

0.17

Performative Prediction with Selective Labels

cs.LG ·2026-10-06 ·Giovani Valdrighi, Isabel Valera, Marcos Medeiros Raimundo
top venue similarity 0.60
Abstract · Accepted at NeurIPS 2026. Camera-ready version

Many social applications of machine learning exhibit performative effects: population behavior changes in response to deployed models. Performative prediction studies this interaction through a distribution map that relates each model to the population distribution it induces. One of the main results in this framework showed that repeated risk minimization (RRM), which updates models by retraining on the most recent data, can converge to a stable model that minimizes risk on its own induced distribution. However, existing analyses typically assume access to the complete distributions of features and labels after model deployment, ignoring the possibility of selective labels: observing labels only for the accepted subset of the population. In this work, we formalize performative prediction with selective labels and show that retraining only on observed data can misguide the retraining procedure and undermine the guarantees of convergence to a stable solution. We then propose a worst-case objective based on knowledge of a confidence interval on the probability of a positive label. Applying RRM to this objective permits us to remain within a bounded distance to the true stable point. Under a sensitivity assumption on the conditional label distribution, we further show how previously accepted data can tighten these confidence intervals over time. Experiments in a lending application with fairness regularization show that our robust optimization approach closely matches the performance of RRM with complete label access.

0.46