acceptodds
Under review as a conference paper at ICLR 2027

Certified Stopping for Active Model Selection

Abstract

Active model selection reduces labeling cost by querying items on which candidate models disagree. For large language models with cached predictions on a fixed pool, one gold label evaluates every candidate. A preset budget, however, does not determine whether enough labels have been collected to identify the winner. We characterize completion certificates: observed labels that guarantee the same unique winner for every assignment of the remaining labels. For categorical predictions and shared nonnegative item weights fixed before labeling, a candidate is certified exactly when its observed lead over each rival exceeds their remaining disagreement weight. This gives the earliest safe stop along any fixed query path and identifies which candidates can still win. Extending the bounds to model choices across deployment cost caps gives an integer covering formulation over shared labels. We use the surviving candidates to guide two acquisition rules: FrontierCut selects items separating the most surviving pairs, and CertSELECT restricts and renormalizes SELECT-style weights over survivors. Under the same exact stopping rule on 353 LLM organization panels, their respective panel-median paired label savings are 9.39% and 10.50% over adapted SELECT, and 26.66% and 30.19% over a deployable Model Selector. On 19 binary and multiclass panels, FrontierCut saves a run-level median paired 18.18% over its static disagreement-ranking ablation. For JudgeTuning's full deployment map, hindsight certificate bounds span 57.29%–62.46% of the pool across one- and two-percentage-point accuracy tolerances. On the LLM organization panels, the panel-median ratios of labels used to the hindsight lower bound are 1.63 for CertSELECT and 1.66 for FrontierCut, compared with 1.85 for adapted SELECT. Thus, tracking unresolved disagreements reduces labeling cost while certifying the fixed-pool winner.

Primary area:
datasets and benchmarks
Keywords:
model selection, label-efficient evaluation, LLM evaluation, active testing, optimal stopping, NP-hardness, LLM-as-a-judge

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ULvyOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper introduces certified stopping for active model selection. Given a budget in model selection it is not clear whether enough labels have been collected to identify the winner. Because of that the paper characterized completion certificates, that is, observed labels that give a guarantee of the unique best model for the remaining labels. The paper shows 9.39% and 10.50% label savings over SELECT, and 26.66% and 30.19% over Model Selector.

Critical strengths
  • The paper is well motivated, and the use case is real and relevant
  • Along empirical results the paper provides theoretical results
Critical weaknesses
  • Missing baseline comparisons: The paper should compare against uniform random sampling and a recent method such as CODA.

  • Unclear scope and evaluation: The paper does not clearly explain which tasks and evaluation metrics the method supports or what assumptions it requires.

Questions for authors

Clarity

What are the limitations in the general setting? Does the method apply only to classification, or does it also support open-ended classification? Are there any assumptions about the metric function used to evaluate the outputs?

What is a panel? The writing does not clearly explain this term.

The paper consistently references figures and tables in the appendix and presents their numbers as if the results were included in the main paper.

Soundness

How does the metric evaluated here compare to the one used in the Model Selector paper (https://arxiv.org/abs/2410.13609)? Is it the same as identification probability? Could you clarify this with an example?

Could you also provide a comparison against a Random baseline (just randomly sampling data points from a uniform distribution)?

Could you provide a comparison with a more recent baseline, such as CODA (https://arxiv.org/pdf/2507.23771v1)?

2 comments

Thank you for your careful review. We completed the Random and CODA comparisons under the same exact stopping rule: FrontierCut has lower median label counts than uniform Random across all 19 pools and official CODA acquisition on the three prespecified tasks. To interpret this saving, we distinguish certifying the fixed-pool winner from identifying it correctly in repeated trials.

1. Random and CODA under the same guarantee

FrontierCut's median certification cost is lower than Random's on all 19 pools and CODA's on the three specified tasks. Random uniformly samples unqueried disagreement items without replacement, giving it the same free exclusion of items on which all candidates agree. Across 19 pools with eight runs each, FrontierCut saves a median 40.6% of labels, taking the paired median within each pool and then across pools. All 19 pool-level effects favor FrontierCut. This Random baseline is the explicitly named version of the original “quotient uniform” control.

For CODA (Kay et al., 2025), we used the official acquisition implementation with default parameters and retained every original model and item when initializing its consensus prior. Hard predictions were encoded as one-hot vectors, matching the information available in our cached data. CODA's own prefilter selects query candidates, and the common certificate determines stopping and the returned prediction-equivalence group. The two smallest binary pools and smallest multiclass pool were selected before these comparisons. Median label counts are:

TaskRandomCODA + certificateSELECTCertSELECTFrontierCut
WNLI7070666665
RTE222229205169176
Emotion871890775.5561.5591

As the table shows, FrontierCut reaches the same certificate with 7.1%, 23.1%, and 33.6% fewer labels than CODA acquisition on WNLI, RTE, and Emotion, respectively. These are certification costs on these three tasks. Each has eight seeded runs, although WNLI and RTE each produce only one distinct CODA query path. Thus repeated identical paths are not additional independent evidence.

2. Supported tasks, metrics, and assumptions

The guarantee applies to finite categorical predictions scored by shared, preset nonnegative item weights: Sa=∑iwi1[pia=yi]S_a=\sum_i w_i\mathbf{1}[p_{ia}=y_i]. Unit weights recover accuracy. Acquiring one gold label evaluates every candidate on that item, and acquired labels are treated as final. The main stopping experiment requires a unique full-pool winner. Item independence and calibrated probabilities are unnecessary because the guarantee holds for every remaining label assignment.

This includes binary and multiclass classification and LLM tasks whose outputs have a fixed categorical interpretation, such as multiple-choice answers. Unrestricted open-ended generation with semantic similarity or a non-additive metric requires a different score model. For multiclass predictions, the gold answer may match neither of two candidates. Its pairwise contribution is then zero, which our certificate handles explicitly.

3. Relationship to MODEL SELECTOR's identification probability

The metrics answer different questions: we measure labels needed for exact certification, whereas MODEL SELECTOR, Section 4.3.2 measures the fraction of trials identifying the true winner at a fixed budget. For example, selecting the true winner in 95 of 100 runs gives 95% identification probability. In a particular run, however, a lead of three correct answers with five unseen disagreements still permits a reversal. A lead of six with five such disagreements certifies the winner against that rival. Our criterion requires this condition against every rival, and we measure how many labels each acquisition rule needs to reach it.

4. Meaning of “panel” and result presentation

A panel is one candidate collection evaluated on the same fixed item pool, with its cached prediction matrix. An organization panel groups models from one organization. Each reported label count therefore refers to one candidate collection reaching the common certificate on its pool.

The explanation above connects the decision target to its exact certificate and then to label savings, stating the comparisons directly. This makes the argument self-contained. Supplementary tables supply further detail.

Thank you for the rebuttal and additional experiments. I appreciate the new baseline comparisons and clarifications. However, I remain concerned about the presentation: even after these exchanges, I still find the formulation, and evaluation difficult to follow. While the rebuttal addresses several of my questions, it does not sufficiently resolve my concerns to support acceptance. I therefore maintain my rating.

Reviewer_ArKAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies active model selection on a fixed evaluation pool, where model predictions are available and gold labels are acquired sequentially. It characterizes exact stopping and the set of possible winners under shared item weights, and develops two acquisition rules, FrontierCut and CertSelect, that use this survivor information. It also formulates joint certification across deployment cost constraints as an integer covering problem. Experiments evaluate label savings under a common exact stopping rule and provide offline bounds on certificate size.

Critical strengths
  • The paper connects exact stopping with the identification of candidates that can still win. Restricting acquisition to these surviving candidates provides a natural mechanism for avoiding queries that only distinguish models already ruled out. This strategy is intuitively sensible.

  • The experimental evaluation is a strong aspect of the paper. The reported label savings, together with the additional categorical-prediction experiments, offer useful evidence that survivor information can improve acquisition efficiency.

Critical weaknesses
  1. The manuscript presents exact stopping, survivor characterization, certificate minimization, hardness results, and two acquisition rules, but does not sufficiently explain how these components collectively support the proposed methodology. The current discussion makes it difficult to identify what each theoretical result contributes to the practical method. The theory provides limited guidance on which method to use for a new task. It remains unclear when the additional weighting is beneficial enough to justify calibration, which properties of the candidate pool favor either method, and whether one should be the default.

  2. The exact stopping condition follows directly from worst-case bounds on the remaining pairwise score differences. CertSelect is a relatively modest modification of SELECT.

  3. The earliest-stopping result applies only to a fixed query path. It does not establish that FrontierCut or CertSelect identifies the winner using close to the minimum number of labels achievable by an online acquisition policy.

  4. Requiring the selected model to remain optimal under every completion of the unobserved labels is a strong guarantee and can entail substantial additional annotation. The paper does not yet convincingly establish when this additional cost is justified relative to allowing a small probability of selecting an inferior model. A concrete application that explains the consequences of selection errors and the cost of annotation would help clarify the value of the proposed guarantee.

Questions for authors

Q1. Could the authors explicitly map the main theoretical results to the algorithms and use cases they support, and explain how these components form a unified methodological framework? In particular, beyond the presence or absence of temperature calibration, what observable properties of an evaluation task favor FrontierCut or CertSelect, and what evidence supports that recommendation?

Q2. The arXiv record for Kuboyama (2026) lists a v1 submission date of September 16, 2026, coinciding with the ICLR submission deadline. Could the authors clarify the relationship between these concurrent works?

Kuboyama, T. (2026). How Many Labels Does Model Choice Need? Certificates and Budgets for Selective Prediction. arXiv:2609.18622.

Q3. What, if any, theoretical guarantees characterize the label efficiency of FrontierCut and CertSelect across query policies, beyond earliest stopping on a fixed path? Could the authors clarify how the offline certificate bounds inform the performance of these online acquisition rules?

Q4. Could the authors describe a concrete application in which exact certification is worth its additional annotation cost? How should a practitioner weigh that cost against the consequences of accepting a small probability of selecting a suboptimal model?

2 comments

Thank you for your thoughtful comments and suggestions. We clarify that exact candidate elimination changes which queries matter: restricting SELECT to surviving candidates saves 10.5% of labels under the same stopping rule. We then relate these savings to hindsight certificate bounds and the measured cost of certainty.

1. How the theory supports the algorithms, and which rule to use

The theory connects stopping, survivor-based querying, and certification across deployment cost caps. First, attainable pairwise score bounds give an exact stopping condition. Second, shared item weights make the possible-winner set exact: assigning every unread label to candidate aa's prediction simultaneously maximizes its margin against every rival. Third, acquisition focuses on this set. FrontierCut counts pairs of surviving candidates separated by a query, whereas CertSELECT retains SELECT's correctness-based weights and renormalizes them over survivors. Thus the CertSELECT comparison isolates the value of eliminating impossible winners.

FrontierCut is the practical default when calibration is undesirable. CertSELECT is attractive when response-only calibration is affordable and accumulated correctness usefully differentiates surviving candidates. On 353 organization panels, CertSELECT saves an additional median 2.1% over FrontierCut, while the latter wins on 144 panels. Five-fold organization-disjoint calibration preserves the saving over SELECT at 10.5%. Observable candidate count and disagreement structure indicate where pruning can help: FrontierCut's savings over uniform disagreement sampling increase from 13.8% to 36.8% across candidate-count quartiles. This supports FrontierCut as the default and CertSELECT as a calibrated alternative.

2. Contribution relative to Kuboyama (2026)

The overlap with Kuboyama (2026) is the binary stopping test and adaptive pair-sum ordering in the shared-weight setting. Its v1 appeared on September 16, 2026, the submission date noted in your review. Its analysis concerns selective risk with candidate-specific confidence-rank weights, including identical multiclass predictions represented by a common binary error.

Our exact survivor characterization instead supports differing categorical predictions with shared weights. This difference matters because pairwise feasibility under candidate-specific weights need not have one jointly feasible completion. Under shared weights, the favorable completion above satisfies all comparisons simultaneously. In addition, our joint cost-map cover reuses each acquired label across different cost-feasible candidate sets, and the hardness result covers fixed-map and any-output certification. The acquisition experiments then quantify the benefit of using exact survivors within an existing selector. These are the contributions beyond the common binary stopping argument.

3. What is guaranteed across query policies?

Across policies, the guarantee is safe certification. Earliest stopping is pathwise, while cross-policy label efficiency is assessed empirically against hindsight certificates, rather than through an online approximation guarantee. For a completed run with label count LL and hindsight optimum C∗C^*, the LP and feasible greedy cover give LP≤C∗≤G\mathrm{LP}\leq C^*\leq G, so L/G≤L/C∗≤L/LPL/G\leq L/C^*\leq L/\mathrm{LP}. This brackets the realized excess above the smallest certificate without equating hindsight information with what an online policy knows.

On the 353 panels, median labels/LP are 1.66 for FrontierCut, 1.63 for CertSELECT, and 1.86 for SELECT. Consequently, both survivor-based rules move closer to the same evidence requirement. The logarithmic greedy guarantee applies to the full-label covering problem, not to these online acquisition rules.

4. When is exact certification worth the annotation cost?

Exact certification is valuable when a final fixed-pool decision must survive every remaining label, such as a published benchmark winner or a judge choice reused across deployments. With responses cached, one expert annotation serves every candidate. For exploratory selection, the acceptable probability and consequence of an incorrect choice can instead justify statistical stopping.

Our measured tradeoff makes this choice concrete: at a retrospective 478-label cutoff on the 706 SELECT paths, 99.0% of choices are correct, while 49.9% remain uncertified. Certification therefore purchases certainty about this fixed pool beyond a high empirical success rate. A practitioner can compare the additional annotation cost with the consequence of an erroneous final decision, or predeclare an accuracy tolerance. For deployment maps, the same framework certifies that tolerance simultaneously at every specified cost cap.

Thank you for the clarifications. I now have a better understanding of the roles of FrontierCut and CertSELECT and how the paper relates to Kuboyama (2026). However, I still have some concerns about the overall methodological and theoretical novelty, as some contributions appear to be extensions or modifications of existing approaches. I also feel that the theoretical support for the proposed acquisition methods could be stronger. After considering the responses, I have decided to maintain my original rating.

Reviewer_VNHDOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The authors pose an active testing problem: when can the winning candidate model be identified with certainty, regardless of the labels on the unlabeled portion of the test set. They present a theorem showing when a candidate model's lead can not be overtaken by any other candidate model; an optimization problem for finding the smallest number of data points needed to guarantee a winner subject to accuracy thresholds and model cost caps; and two acquisition strategies for identifying new labels to query.

Critical strengths
  • None
Critical weaknesses
  • Paper is written poorly: it is very hard to follow because of confusing writing style and word choices
  • The paper does not argue for the importance of the chosen problem formulation, "cached predictions on a fixed evaluation pool"
  • Much of the content appears trivially true (for example, Theorem 3 in Section 3.2, and the optimization problem in Section 4)
  • Method only applies to multi-class problems, but in general LLMs generate diverse outputs
  • In an active testing setting of n >> m where the number of possible test points n is much larger than our labeling budget m, the proposed formulation of identifying a model that remains the winner — under any possible assignment of labels to the unobserved test point — appears of doubtful utility, and this scenario is not discussed in the paper
  • Experimental results are confusingly presented, with a mismatch between the methods mentioned in Section 6.1 and the legend in Figure 2; broadly, there is little discussion of the experimental results, nor of their significance
Questions for authors
  • None
2 comments

Thank you for your review. We explain how fixed-pool certification finalizes a benchmark decision that no remaining label can change. To obtain that assurance efficiently, acquisition uses exact candidate elimination: restricting SELECT to survivors saves 10.5% of labels on 353 organization panels under the same certificate.

1. Why cached predictions on a fixed pool matter

This setting matches a benchmark owner comparing submitted models or a team choosing among cached judge configurations before paying for expert annotation. One item label evaluates every candidate. The fixed pool specifies the decision being finalized and makes its remaining uncertainty computable. A “panel” is one candidate collection evaluated on one common pool.

2. What goes beyond the elementary stopping inequality?

The key step is exact possible-winner characterization. Under shared weights, assigning unread labels to one candidate's predictions simultaneously maximizes its lead over every rival. Thus pairwise feasibility identifies exactly the candidates that can still win, including ties. With candidate-specific weights, different rivals can require incompatible favorable completions.

This characterization guides acquisition: FrontierCut recomputes disagreement among possible winners, and CertSELECT removes impossible winners from SELECT's weights. The 10.5% saving holds while SELECT's update, temperature, and stopping rule remain fixed, directly showing the benefit of exact elimination within an established query objective.

For deployment cost caps, the optimization in Section 4 identifies the smallest shared label set that certifies the choice at every cost cap. One label can satisfy several rival comparisons, whose evidence coefficients are 0, 1, or 2 for categorical answers. The NP-hardness reduction explains why exact minimization is difficult, while the LP lower bound and feasible greedy cover locate the required label count. On JudgeTuning, the greedy certificate is within 4% of the fixed-map LP bound. These results give the formulation a quantitative role beyond simply stating an optimization objective.

3. Applicability to diverse LLM outputs

The theorem covers binary and multiclass answers with shared, preset nonnegative weights and final gold labels. It therefore applies to LLM evaluation when outputs map to fixed categorical answers, including multiple-choice tasks. With three or more labels, an answer can match neither candidate and contribute zero to their observed score difference. We explicitly handle this case and evaluate 11 naturally multiclass pools. Unrestricted free-form generation evaluated by semantic or non-additive scores calls for a different scoring model.

4. Can exact selection help when the label budget is much smaller than the pool?

A small budget can suffice when candidates agree on most items, because only their remaining disagreements can change the winner. For example, the Emotion pool contains 5,509 items, of which 902 have any candidate disagreement. FrontierCut certifies the winner after a median 591 labels, compared with 871 for uniform disagreement sampling and 890 for official CODA acquisition under the same certificate. Thus a certificate can be substantially smaller than the full pool.

Close candidates with widespread disagreement can require a larger budget. The practical choice is whether the final fixed-pool decision requires exact certification or permits a stated error risk. In the 706 SELECT paths, a retrospective 478-label cutoff selects the correct winner in 99.0% of runs, although 49.9% remain uncertified. This quantifies the extra assurance purchased by certification. The cost-map formulation also permits a predeclared accuracy tolerance, providing a less demanding decision target when exact identity is unnecessary.

5. Writing, method names, and interpretation of Figure 2

The explanation above now follows “decision target → remaining possible winners → next useful label → stopping,” defining terms before formulas. To clarify the Figure 2 legend, “SELECT” means all-candidate acquisition, “CertSELECT” its survivor-restricted version, and “Model Selector oracle” the best completed run in its parameter grid. This oracle reference is distinct from the deployable pseudo-label-tuned Model Selector comparison.

Figure 2(a) reports median label counts: 477.5 for SELECT, 417.5 for FrontierCut, and 401 for CertSELECT. As these values show, both survivor-based rules reach the identical exact decision with fewer labels. Figure 2(b) separately divides online label counts by the hindsight LP lower bound. Its ratios describe proximity to the minimum evidence requirement, not an online optimality guarantee. This distinction connects the figure's two measurements to acquisition efficiency and its hindsight reference.

Thank you for your response. In particular, I appreciate the clarification on the label budget regime the paper tackles. Overall, I remain unconvinced of the novelty or significance of the paper's contributions, and the concerns around presentation have only been addressed perfunctorily. I thus maintain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.