Certified Stopping for Active Model Selection

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.