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

arXiv: https://arxiv.org/abs/2610.14996 · HTML: https://mlsanity.com/paper/2610.14996/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 10 Oct 2026.

## Builds on (most cited first, 15 of 15)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [ASlib: A Benchmark Library for Algorithm Selection](https://mlsanity.com/paper/1506.02465/) (2015)
- [Optimal Best-Arm Identification Methods for Tail-Risk Measures](https://mlsanity.com/paper/2008.07606/) (2020)
- [The Algorithm Selection Competitions 2015 and 2017](https://mlsanity.com/paper/1805.01214/) (2018)
- [Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty](https://mlsanity.com/paper/2206.15201/) (2022)
- [The minimum cost query problem on matroids with uncertainty areas](https://mlsanity.com/paper/1904.11668/) (2019)
- [Query-Competitive Sorting with Uncertainty](https://mlsanity.com/paper/2012.09475/) (2020)
- [Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid](https://mlsanity.com/paper/2512.17116/) (2025)
- [Combinatorial optimization problems with uncertain costs and the OWA criterion](https://mlsanity.com/paper/1305.5339/) (2013)
- [Set Selection under Explorable Stochastic Uncertainty via Covering Techniques](https://mlsanity.com/paper/2211.01097/) (2022)
- [Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds](https://mlsanity.com/paper/2404.17214/) (2024)
- [An extension of Ordered Weighted Averaging over intervals with application to optimization under risk](https://mlsanity.com/paper/2410.09786/) (2024)
- [On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms](https://mlsanity.com/paper/2507.02657/) (2025)

## Abstract (arXiv)

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.