Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations

Yuhe Sui; Yingzhi Tang

cs.AIOct 10, 2026

Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations

Authors: Yuhe Sui, Yingzhi Tang

Organizations: Quantitative Research Society, Singapore · Nanyang Technological University, Singapore · The Chinese University of Hong Kong, Shenzhen, China

Abstract

Choosing a few robust algorithms or schedules can require evaluating every candidate under many adverse scenarios, even though an agent only needs to identify the winners. A predictor may suggest those winners, but cannot rule out a surprise in an unevaluated scenario. We introduce Certified Adaptive Selection (CAS), which returns the exact top- $k$ set as soon as remaining uncertainty cannot change it. CAS keeps guaranteed lower and upper bounds on Expected Shortfall (ES), the average loss in the worst scenarios. Its stopping test compares the worst admissible selected candidate with the best admissible excluded one; for information-disjoint Cartesian intervals this one-cut test is necessary and sufficient. Prediction has a separate role: selecting the next outcome to evaluate, never authorizing the decision. For empirical ES with exact unit-cost queries, we compute in polynomial time the fewest evaluations that could have proved the realized decision in hindsight. Our prediction-guided agent CAS-PG is exact for every predictor, including adversarial ones. On two public algorithm-selection matrices, CAS-PG certifies the exact top three after 630 of 3150 and 981 of 2200 replayed queries, or $1.14$ and $1.18$ times that hindsight minimum. Without historical outcomes, its transcript-only variant requires $1.28$ and $1.37$ times the minimum, outperforming the tested non-predictive certified policies. Separately, a prediction-free CAS policy avoids $93.0\%$ of exact recourse solves in synthetic energy scheduling. One certificate thus supports several acquisition policies and separately proved risk/cost extensions: prediction changes the work, not the justified choice.

Figures & tables

Panel of Figure 1 — Figure 1: CAS is a shared certificate loop with distinct branches , not a collection of independently certified predictors. The red S3 branch contains the main agent CAS-PG and alternative query policies; dashed branches handle risk and query-price theory in S0–S1. All core policies use the same S2 stopping rule. Finance changes both S0 and S4, falls outside the core model and has separately established correctness.

Panel of Figure 2 — Figure 2: Exact evaluations bought before the decision certificate closes (ES top-3); in parentheses, the multiple of the hindsight optimum $C_{\mathrm{cert}}^{\star}$ (dotted line). Every method returns the exact full-information set, so the bars differ only through the order of purchases. Red bars: CAS-PG-T uses transcript information only, whereas CAS-PG additionally uses historical outcomes from other instances. Grey bars use no predictor. Uniform baselines are medians over 30 seeds.

	OPENML-WEKA		CSP-Minizinc
Method	evals	$\times C_{\mathrm{cert}}^{\star}$	evals	$\times C_{\mathrm{cert}}^{\star}$
Full exact ( $mS$ )	3150	5.69	2200	2.64
$\circ$ Uniform over all cells †	3144	5.68	2169	2.60
$\circ$ CAS-W	3074	5.55	1966	2.36
$\circ$ CAS-F	3039	5.49	2191	2.63
$\circ$ Uniform in witness †	2006	3.62	1661.5	1.99

Table 1: Exact evaluations until certification (ES top-3) and their multiple of

C_{\mathrm{cert}}^{\star}

. All methods return the exact full-information set.

\circ

: no historical side information.

\dagger

: median over 30 seeds.

\ddagger

: control run by the independent audit.

	OPENML-WEKA		CSP-Minizinc
Row group	$C_{\mathrm{cert}}^{\star}$	CAS-PG	$C_{\mathrm{cert}}^{\star}$	CAS-PG
Three selected rows	314	315	217	296
Excluded rows (27 / 19)	240	315	617	685
Prior given to CAS-PG	evals		evals
Other predictor seeds	634 / 622		981 / 988
Random fold assignments	631 / 635		1034 / 1032

Table 2: Where queries are spent and how historical priors change cost. Top: row groups, hindsight versus CAS-PG . Bottom: two audit draws per prior; every output remains exact.

Panel of Figure 3 — Figure 3: Controlled quadratic stress tasks: exact evaluations before certification (bar labels) as a share of the exhaustive denominator (4480; 4224 for small margin). Certified cost grows from 2% to 17% as the margin shrinks and curvature loosens the bounds, and the returned set stays exact. Candidate-only and full evaluation use the full reference budget.

Study	Paid unit / denominator	What the evidence establishes
ASlib replay	algorithm–instance value; $mS$ and $C_{\mathrm{cert}}^{\star}$	CAS-PG , CAS-PG-T and certified controls: exact membership and query cost
Native energy	exact recourse solve; $AS$	CAS-PD : exact schedule and solve avoidance, not runtime
Quadratic stress	distinct candidate–scenario primitive; full exact	CAS-W , CAS-F , CAS-CI : certificate or exact fallback
Financial pricing	distinct leg–scenario primitive; fresh pricer calls	exact membership and shared-cache accounting; no certified latency gain

Table 3: Paid units and claim scope across experimental studies.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure S1: Status map of the recorded comparison runs, grouped by method and regime. Black diamonds: full exact evaluation; filled circles: deterministic certificates; open triangles: exact fallback; open squares: both certification and exact fallback occur in the same method–regime group under different recorded settings (five cells); open circles: predictive outputs that happen to match the reference; crosses: predictive errors; light dots: combinations not run. Grouping does not imply every configuration has the displayed status.

Figure S2: Predictive baselines on Merton regimes: aggregate top-

k

spectral-risk regret (S.42). The shaded strip marks zero regret. This is a predictive-accuracy comparison, not an exact-work comparison; none of these methods carries a certificate.

Decision-Making under Uncertainty

Decision-making under uncertainty studies how to choose actions when outcomes, states, or models are imperfectly known.

See all 200 papers

Jul 16, 2026

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from

\tilde O(\varepsilon^{-2}\log K)

samples (

K

the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread

R

, none below

Ω(R/\varepsilon^2)

. Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to

26%

of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.

Haifeng Li, Mo Hai

School of Information, Central University of Finance and Economics Beijing 102206, China

Combinatorial Optimization Learning-Augmented Algorithms PAC Learning Approximation Algorithms Statistical Learning Theory

Ask PDF

Aug 26, 2026

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

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.

Ibne Farabi Shihab, Sanjeda Akter, Anuj Sharma

Department of Computer Science, Iowa State University · Department of Civil, Construction & Environmental Engineering, Iowa State University

Language Model Safety Evaluation Multiple Hypothesis Testing

Ask PDF

Oct 19, 2026

Selecting the Best Few with Human Evaluators: Adaptively Combining Ratings and Pairwise Comparisons

This paper considers a decision-maker tasked with identifying the

k

best items from a large pool of candidates, such as job applicants, LLMs, award nominees, or new product ideas. The decision-maker learns about the items' quality by soliciting human evaluations. Each evaluation can be costly, so the decision-maker aims to use the limited evaluation budget efficiently by allocating evaluations adaptively. A key consideration is the form of evaluation to solicit, which should be something evaluators are comfortable providing. Two popular forms are ratings and pairwise comparisons, and we allow for both, as they may be especially useful in combination given the limited budget. Ratings can be used early on to get a coarse picture of which items are good and which are not. As that picture forms, comparisons can refine the ordering of the good items, narrowing in on the ultimate top-

k

selection. To solve the allocation problem, we develop an adaptive algorithm built from two allocation policies. The first, our primary contribution, is based on a surrogate objective that is naturally forward-looking, valuing evaluations that help inform what to evaluate in future rounds, not just those that directly improve the selection decision. The decision rule is interpretable, and we prove that it is asymptotically consistent. Late in the evaluation process, when being forward-looking is less productive, we construct a myopic policy and a criterion for switching to it. In simulation, the method gives insight into how to combine these two types of evaluations, and beats the (limited) existing benchmarks.

Motti Goldberger, Nils Rudi

Yale School of Management

Human-in-the-Loop Evaluation Preference Elicitation Adaptive Rank Allocation

Ask PDF

Abstract

Decision-Making under Uncertainty

Explore similar work

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

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

Selecting the Best Few with Human Evaluators: Adaptively Combining Ratings and Pairwise Comparisons