Paper deep dive
Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations
Yuhe Sui, Yingzhi Tang
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.14996v1
- Canonical: https://arxiv.org/abs/2610.14996v1
Trouble viewing inline? Open PDF directly →
Full Text
114,576 characters extracted from source content.
Expand or collapse full text
Certify the Decision, Not Every Score: Exact Top-k Selection from Few Evaluations Yuhe Sui Affiliation: Quantitative Research Society, Singapore Affiliation: Nanyang Technological University, Singapore Affiliation: ORCID: 0009-0002-7456-0804 Yingzhi Tang Affiliation: Quantitative Research Society, Singapore Affiliation: The Chinese University of Hong Kong, Shenzhen, China Affiliation: ORCID: 0009-0004-7571-0100 October 2026 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.141.14 and 1.181.18 times that hindsight minimum. Without historical outcomes, its transcript-only variant requires 1.281.28 and 1.371.37 times the minimum, outperforming the tested non-predictive certified policies. Separately, a prediction-free CAS policy avoids 93.0%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. Keywords: certified selection; learning-augmented agents; costly information acquisition; Expected Shortfall; explorable uncertainty. Contents 1 Introduction 2 When is the selected set already certain? 3 The least information needed in hindsight 4 CAS-PG: prediction buys information, not authority 5 Public benchmarks: exact decisions from fewer queries 6 What the certificate layer establishes elsewhere 7 Extensions and limits of the certified model 8 Related work 9 Conclusion References A Exact-query model and one-cut composition B Exact empirical-ES row frontiers C CAS-PG: exactness, protocol and audit D Decision-preserving spectral coarsening E Arbitrary-spectrum coherent lower frontier F Structural arbitrary-spectrum upper algorithms G Few-price-class certificate-cost PTAS H Online versus hindsight information I Reproducibility and denominator specification J Certified nonlinear Merton enclosure K Claim boundary summary 1 Introduction An agent must retain a small set of candidates, but each candidate is judged across many possible adverse scenarios. The objective may be to keep the three algorithms with the smallest worst-case-average loss across benchmark instances, or to choose a few schedules with the lowest tail cost across service conditions. In such tasks, one candidate–scenario evaluation can be a solver run or an exact recourse optimization. A financial hedge screen poses a related question when every market shock requires nonlinear repricing. The number of evaluations grows as the number of candidates times the number of scenarios, even though the agent ultimately needs a set of winners, not a complete matrix of scores. There is a sharp distinction between predicting that a candidate is good and knowing that no unevaluated outcome could change the choice. Exhaustive evaluation resolves the second question but is expensive. A learned surrogate may resolve the first cheaply yet fail at the selection boundary. Accurate average predictions do not certify which candidate is ranked k rather than k+1k+1. Our answer is to give information acquisition and decision authority separate jobs. Certified Adaptive Selection (CAS) maintains a valid interval for each candidate’s tail-risk score. It stops only after the largest possible score of a selected candidate is smaller than the smallest possible score of every excluded candidate (with a fixed rule for ties). For example, if the prospective winner’s risk lies in [0.20,0.40][0.20,0.40] and its nearest competitor’s in [0.46,0.70][0.46,0.70], further score evaluations cannot change their ordering. A predictor may help the agent reach that separation sooner, but it cannot authorize the stop. Thus the agent certifies membership, not every individual score. This separation makes efficiency measurable. On a fully specified realization we can ask for the smallest collection of outcomes whose revelation already forces the right top-k set. We call its cost the hindsight certificate optimum, Ccert⋆C_cert . It is not an online policy: its query set may exploit information hidden from the agent. Our one-cut characterization is necessary and sufficient when compatible losses of different candidates can vary jointly; for empirical Expected Shortfall (ES), we show how to compute Ccert⋆C_cert and an attaining query set in polynomial time. This supplies an exact instance-specific yardstick, rather than only comparison with evaluating every candidate–scenario outcome. The online policy CAS-PG then asks which observation should be bought next. It works on the candidates currently blocking the certificate and prioritizes scenarios predicted to contribute to the tail. Predictions may come from a historical model, from values already revealed during the run, or from both. The proof of exactness is unchanged if these predictions are unhelpful: the policy always checks the same deterministic certificate before returning a decision. A worst-case guarantee of being close to Ccert⋆C_cert is impossible for zero-error online acquisition without further information; the empirical question is whether prediction closes the observed gap. On two public ASlib matrices, CAS-PG takes 630 of 3150 and 981 of 2200 exact-value queries, respectively: 1.14×1.14× and 1.18×Ccert⋆1.18× C_cert . A like-for-like variant using no historical outcomes needs 709 and 1144, versus at least 1872 and 1699 for the tested deterministic non-predictive certified schedulers. These are query counts in a replay oracle, not measured reductions in algorithm-running time. A separate synthetic energy study tests genuine recourse solves with a non-predictive CAS scheduler; it avoids 93.0%93.0\% of the full solve count. Neither result transfers the observed public-benchmark cost ratios to shared-primitive financial pricing or to interval-valued oracles. Contributions and scope. The central contribution is exact risk-sensitive selection with prediction restricted to acquisition. Its theoretical foundation is a necessary-and-sufficient decision certificate and a computable empirical-ES hindsight benchmark (Sections 2 and 3). Its algorithmic realization is CAS-PG, whose exactness is independent of its predictor and whose query cost is assessed against that benchmark (Sections 4 and 5). Native recourse solves and controlled stress tasks test what the certificate layer achieves under other conditions (Sections 6 and 6.2). We separately state extensions to general spectral risk and priced certificates, and the distinct assumptions of the motivating financial setting (Section 7). The complete proofs, protocol specifications, diagnostic figures, and evidence boundaries are provided in the appendices, allowing this version to be read and checked without a separate supplement. Guide to the extended version. The main text establishes the decision problem, the certificate, the hindsight optimum, the online policy, and the experiments in that order. Appendices A, B, C and H provide technical verification of the central results; Appendices D, E, F and G contain the general-risk and priced-certificate theory; and Appendices I and J document the application-specific evidence and the nonlinear pricing enclosure. These appendices are part of this paper, not separate claims of production FRTB speedup. 2 When is the selected set already certain? 2.1 From intervals to a decision Consider selecting the single lowest-risk candidate from three candidates. Suppose their current certified risk ranges are [0.20,0.40][0.20,0.40], [0.46,0.70][0.46,0.70] and [0.80,0.91][0.80,0.91]. The first candidate is already certain to win, although none of its scenario losses need be known exactly. By contrast, if its upper bound were 0.550.55, the first two ranges would overlap. Their current bounds alone would not settle which candidate wins. This is the distinction on which CAS acts: uncertainty about scores is acceptable until it can change the chosen set. In general, let m candidates have S losses each. The loss vector of candidate j is xj=(xj1,…,xjS)x_j=(x_j1,…,x_jS). Before evaluation, each loss lies in a certified public interval, giving the Cartesian box Bj0=∏s=1S[ℓjs0,ujs0]B_j^0= _s=1^S[ ^0_js,u^0_js]. A query of (j,s)(j,s) returns xjsx_js exactly and replaces that coordinate’s interval by a point. Unless stated otherwise, each query costs one unit. The theorem model is information-disjoint: rows share no queryable primitive, and every combination of compatible row values is feasible. This is a property of the uncertainty set, not a claim of stochastic independence. We compare candidates by a tail-risk score: larger adverse losses count more. Empirical Expected Shortfall with tail mass t∈(0,S]t∈(0,S] averages the worst t scenario losses, with fractional weight on the boundary loss when t is noninteger (Acerbi and Tasche, 2002; Rockafellar and Uryasev, 2002). More generally, for descending losses y(1)≥⋯≥y(S)y_(1)≥·s≥ y_(S), a coherent spectral score is (Artzner et al., 1999; Acerbi, 2002) ρλ(y)=∑r=1Sλry(r),λ1≥⋯≥λS≥0,∑rλr=1. _λ(y)= _r=1^S _ry_(r), _1≥·s≥ _S≥ 0, _r _r=1. (1) ES is the particular spectrum that gives weight 1/t1/t to the worst t losses (and the appropriate fractional boundary weight). Smaller scores are better. Fixed distinct candidate IDs break ties: (ρλ(xj),idj)( _λ(x_j),id_j) is compared lexicographically, denoted ≺ , and Dk(x)D_k(x) is the set of the k smallest such keys. Definition 1 (Decision certificate). For a set Q of evaluated candidate–scenario primitives, let BQ(x)B_Q(x) be the original Cartesian box restricted to completions agreeing with the realized losses x on Q. The query set Q certifies the decision when Dk(v)=Dk(x)D_k(v)=D_k(x) for every v∈BQ(x)v∈ B_Q(x). The definition requires invariance over all compatible completions. No error probability or assumed predictor calibration is involved. Because spectral risk is coordinatewise monotone, the smallest and largest compatible risk scores of row j are attained at its current lower and upper corners. After queries QjQ_j in that row, write these exact bounds as Lj(Qj)=ρλ(ℓj0[Qj←xj])L_j(Q_j)= _λ( _j^0[Q_j← x_j]) and Uj(Qj)=ρλ(uj0[Qj←xj])U_j(Q_j)= _λ(u_j^0[Q_j← x_j]). 2.2 A necessary and sufficient stopping test The illustrated non-overlap condition extends to any k: each selected candidate’s worst compatible key must precede each excluded candidate’s best compatible key. Under the Cartesian model this is not just sufficient, but necessary. Theorem 2 (One-cut exact composition). Assume Cartesian, information-disjoint rows with additive query costs, attained exact extrema and fixed ID ties. Write A=Dk(x)A=D_k(x). An allocation certifies A exactly when maxi∈A(Ui,idi)≺minj∉A(Lj,idj). _i∈ A(U_i,id_i) _j∉ A(L_j,id_j). Equivalently, one lexicographic cut separates the upper keys of all selected rows from the lower keys of all excluded rows. For unit costs, polynomial row frontiers compose by scanning such cuts and summing the least row budgets that cross each cut. Proof. If the cut holds, every completion gives each selected candidate a key no larger than its upper key, and each excluded candidate a key no smaller than its lower key. The set A is therefore the top-k set in every completion. For necessity, suppose the cut fails. Then some i∈Ai∈ A and j∉Aj∉ A have (Ui,idi)⊀(Lj,idj)(U_i,id_i) (L_j,id_j). The row-upper and row-lower corners attain these endpoints. Information-disjointness permits a joint completion realizing the upper corner of i and the lower corner of j. There, j precedes i under the fixed ID tie rule, contradicting invariance of A. For the unit-cost composition statement, let Ui⋆(q)U_i (q) and Lj⋆(q)L_j (q) be the attained row frontiers defined in Section 3. Any certificate can replace each row query set by an attaining frontier set at no larger cardinality, weakly improving the separating inequalities. For every proposed selected upper-key cut, the cheapest row budgets can therefore be chosen independently; enumerating the finitely many selected frontier keys and summing these budgets yields an optimal original-coordinate certificate. ∎ Thus the cut is both a precise online stopping rule and the basis for the offline minimum-information calculation. Without information-disjointness, the necessity argument using jointly realizable corners need not apply. One certificate, several branches. The five stages in Figure 1 separate assumptions from agent choices. In the core loop, certified bounds and the one-cut test determine whether to stop; the S3 policy determines what to buy next. CAS-PG, CAS-PG-T, CAS-PG-H, CAS-PG-U, CAS-PD, CAS-W, CAS-F and CAS-CI are online query policies. By contrast, CAS-SC, CAS-SV and CAS-PT provide risk-side bounds, structural verification or hindsight price optimization under separate assumptions; they are not alternative online acquisition policies. Native energy changes the evaluation oracle; financial pricing changes both the oracle and the information model. Results from these branches are not interchangeable. S0 Information public loss boxes; query and cost model S1 Exact bounds compute lower / upper ES endpoints S2 Certificate selected upper ≺ excluded lower? S3 Acquisition choose unresolved row and scenario S4 Evaluation buy response; update public intervals noyes: exact top-k CAS-PT: few price classes Offline certificate-cost PTAS (separate theory) CAS-SC: coarsen spectrum CAS-SV: verify structure Spectral-risk theory One-cut stopping authority Exact for every query ordering Ccert⋆C_cert : offline benchmark CAS-PG, CAS-PG-T CAS-PG-H, CAS-PG-U CAS-PD, CAS-W, CAS-F, CAS-CI First two lines use prediction ASlib: value replay Energy: exact recourse Finance: intervals + shared Core: disjoint rows, exact point queries, unit costs. Dashed: theory; red: query policies; dotted: oracle settings. 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. 3 The least information needed in hindsight 3.1 An exact denominator for query cost A policy can be correct yet purchase far more observations than necessary for a particular realized matrix. To distinguish useful acquisitions from wasted ones, we compare its query count C with the cheapest certifying query set on that same matrix. Using the certificate of Definition 1, define Ccert⋆(x)=minQc(Q):Q certifies Dk(x).C_cert (x)= _Q \c(Q):Q certifies D_k(x) \. (2) The minimum knows the realized losses before choosing queries. It is therefore a hindsight information benchmark, not an implementable online lower-bound policy. Every zero-error agent that terminates with a certificate must pay at least Ccert⋆(x)C_cert (x); the ratio C/Ccert⋆C/C_cert measures its excess acquisition cost relative to this instance-specific baseline. For candidate j, the upper frontier is the smallest upper score obtainable by revealing at most q realized losses; the lower frontier is the largest lower score obtainable with that budget: Uj⋆(q) U_j (q) =min|Qj|≤qUj(Qj), = _|Q_j|≤ qU_j(Q_j), Lj⋆(q) L_j (q) =max|Qj|≤qLj(Qj). = _|Q_j|≤ qL_j(Q_j). These offline constructions use the realized values. Theorem 2 means that once these frontiers are known, the global optimum can be found by checking separating cuts and adding the smallest budget needed in each row. The computation optimizes evidence for membership, rather than the precision of all risk scores. For a proposed cut, each selected candidate must spend just enough queries to move its upper bound below that cut; each excluded candidate must spend just enough to lift its lower bound above it. Since different rows share no primitive, these row budgets can be added. The global optimum chooses the cheapest cut and combines the attaining row query sets. 3.2 Why the ES frontiers are tractable For empirical ES, the useful variational form is ESt(y)=minzz+1t∑s(ys−z)+.ES_t(y)= _z \z+ 1t _s(y_s-z)_+ \. (3) Consider the upper frontier. For a fixed threshold z, revealing coordinate s reduces the positive-part sum by gs(z)=(us−z)+−(xs−z)+g_s(z)=(u_s-z)_+-(x_s-z)_+. The best q queries at that threshold therefore have the q largest gains. Their order changes only at O(S2)O(S^2) rational breakpoints, which can be enumerated. For the lower frontier, choosing revelations can change which observations enter the tail. A rank-selection dynamic program handles that switching; when t is fractional, it also enumerates the coordinate receiving the boundary weight. Full constructions and bit-complexity arguments appear in Appendix B. Corollary 3 (Exact empirical-ES verification). For rational information-disjoint empirical-ES rows with unit exact-query costs, the complete upper and lower row frontiers, an attaining query set for every budget, and the hindsight optimum Ccert⋆C_cert with an attaining certificate are computable in polynomial bit complexity, including instances in which revelation changes tail membership. The distinction between upper and lower frontiers matters. Revealing a large loss raises a lower bound, helping reject a candidate; revealing a small loss lowers an upper bound, helping retain one. ES can switch which scenarios occupy its worst tail after a revelation, so neither frontier is obtained safely by freezing the original tail. The exact algorithms account for this switching. The corollary makes a nontrivial empirical comparison possible: the denominator is a computed minimum, not a heuristic lower bound or the cost of full evaluation. It does not imply that a policy can identify the optimal queries without knowing the hidden values. 3.3 Why hindsight cannot be matched uniformly online Proposition 4 (Online boundary). There are instances with n unresolved primitives and Ccert⋆=1C_cert =1 on which every deterministic zero-error online policy makes n evaluations on some realization, and every randomized zero-error policy incurs expected cost at least (n+1)/2(n+1)/2 on some realization. The obstruction is a one-hot search problem: one hidden coordinate determines the comparison with a known row, and the public intervals do not distinguish its position. A hindsight verifier queries that coordinate immediately, but a zero-error online agent can find it last. This is the familiar closed-interval search phenomenon in explorable uncertainty (Erlebach and Hoffmann, 2015). It explains why we do not claim a universal competitive ratio against Ccert⋆C_cert . Instead, the purpose of prediction is to guide acquisition on actual instances without weakening exactness. 4 CAS-PG: prediction buys information, not authority CAS turns the exact stopping criterion into an agent by adding an acquisition policy. At every iteration, the agent computes the current risk bounds and tentatively selects the k candidates with the smallest lower keys. Two rows witness the unresolved boundary: the selected row with the largest upper key, and the excluded row with the smallest lower key. If these two keys are ordered correctly, the whole set is certified. Otherwise the agent needs another exact observation. Figure 1 also distinguishes online query policies from separate risk/cost theory branches. The certificate evaluates actual returned values and valid intervals. The query policy may use arbitrary predictions to decide which observation to buy; its provisional predictions are never substituted for oracle responses. 4.1 Which observation comes next? CAS-PG uses a fixed row rule and a predicted within-row ordering (Algorithm 1). It first works on the selected boundary row while that row has unresolved coordinates; otherwise it works on the excluded boundary row. Within that row, it imagines revealing each unresolved loss at its predicted value and scores the resulting increase in the row’s lower ES bound. It purchases the coordinate with the largest such increase. The pseudo-revelations are only scores for acquisition, not certified updates. On a common [0,1][0,1] box, this ranks high predicted losses first: those are most likely to enter the ES tail. The upper ES endpoint often cannot decrease after one revelation while at least t upper-bound coordinates remain, which motivates using the lower-endpoint effect. An optional prior pjs0p^0_js predicts losses from historical instance features. The agent can also adjust that prior using the evaluations already in its transcript. If RsR_s is the set of rows queried in scenario s, the correction is es=∑j′∈Rs(xj′s−pj′s0)/(|Rs|+1)e_s= _j ∈ R_s(x_j s-p^0_j s)/(|R_s|+1), with a fixed shrinkage constant of one; the prediction used for ranking is p^js=clip(pjs0+es,[ℓjs,ujs]) p_js=clip(p^0_js+e_s,[ _js,u_js]). The correction shares evidence that scenario s was unexpectedly costly for other candidates. The default CAS-PG uses both sources. CAS-PG-T uses the interval midpoint as its prior and learns only from the transcript; CAS-PG-H uses history but no transcript correction. The transcript-only variant is essential for comparing policies that begin with the same public information. 4.2 Exactness does not depend on predictive quality Proposition 5 (Prediction-independent exactness). In the model of Theorem 2 with empirical-ES rows, let the prior p0p^0 be arbitrary (any function of public information, possibly adversarial). For every realization x in the public box, CAS-PG (i) terminates after at most mSmS evaluations; (i) returns Dk(x)D_k(x); (i) stops at the first prefix of its own query sequence that certifies the decision. Consequently Ccert⋆(x)≤CCAS-PG(x)≤mSC_cert (x)≤ C_ CAS-PG(x)≤ mS. Proof. At every iteration the current box contains the realized matrix x: a coordinate is replaced by a singleton only after the exact oracle reveals it. The invariant does not depend on the prior or the transcript-based prediction. If the stopping test passes for the tentative set A of k smallest lower keys, then for every compatible completion v, each selected risk key lies below its upper key, and each excluded risk key lies above its lower key. The one-cut test therefore gives Dk(v)=AD_k(v)=A, in particular A=Dk(x)A=D_k(x). Conversely, suppose the current transcript already certifies the realized membership set A′=Dk(x)A =D_k(x). By Theorem 2, all selected upper keys precede all excluded lower keys. Selected lower keys are at most their upper keys, so the k smallest current lower keys are exactly A′A . The algorithm consequently chooses A=A′A=A and its stopping test passes. As the test precedes each query, this is the first certifying prefix of the chosen query sequence. Finally, if the stopping test fails, both boundary rows cannot already be fully evaluated. Otherwise their exact lower and upper keys would respect the strict lexicographic order separating the tentative selected set from its complement, so the test would pass. The selected boundary row, if unresolved, or otherwise the excluded boundary row therefore has a new cell to query. Each iteration buys a distinct cell and there are only mSmS cells. Termination, exactness, earliest-prefix stopping, and the defining lower bound Ccert⋆(x)≤CCAS-PG(x)C_cert (x)≤ C_ CAS-PG(x) follow. ∎ The guarantee is about the decision, not the query budget. The interval [Ccert⋆,mS][C_cert ,mS] is the general cost bound; Proposition 4 rules out an online bound close to hindsight on every instance. Predictive quality enters only the empirical question of acquisition efficiency. Algorithm 1 CAS-PG for ES top-k under exact unit-cost evaluation 1: public boxes [ℓjs,ujs][ _js,u_js]; k; tail mass t; evaluation oracle; optional prior pjs0p^0_js (default: interval midpoint) 2: the exact top-k set Dk(x)D_k(x) 3: loop 4: compute exact endpoints Lj,UjL_j,U_j of every row (rational arithmetic) 5: A←A← the k smallest keys (Lj,idj)(L_j,id_j) 6: i⋆←argmaxi∈A(Ui,idi)i ← _i∈ A(U_i,id_i); j⋆←argminj∉A(Lj,idj)j ← _j∉ A(L_j,id_j) 7: if (Ui⋆,idi⋆)≺(Lj⋆,idj⋆)(U_i ,id_i ) (L_j ,id_j ) then return A 8: r←i⋆r← i if row i⋆i has an unevaluated cell, else j⋆j 9: p^rs←clip(prs0+es,[ℓrs,urs]) p_rs (p^0_rs+e_s,\,[ _rs,u_rs] ) for unevaluated s 10: s⋆←argmaxs[Lr(ℓrs←p^rs)−Lr]s ← _s [L_r( _rs\!←\! p_rs)-L_r ] (ties: larger p^rs p_rs, then ID) 11: evaluate (r,s⋆)(r,s ); set ℓrs⋆=urs⋆=xrs⋆ _rs =u_rs =x_rs 12: update the scenario effect es⋆e_s from the residual xrs⋆−prs⋆0x_rs -p^0_rs 13: end loop 5 Public benchmarks: exact decisions from fewer queries 001,0001,0002,0002,0003,0003,000Full exact (mSmS)Uniform over all cellsCAS-WCAS-FUniform in witnessCAS-PDCAS-PG-T (no history)CAS-PGHindsight Ccert⋆C_cert 3150 (5.69×5.69×)3144 (5.68×5.68×)3074 (5.55×5.55×)3039 (5.49×5.49×)2006 (3.62×3.62×)1872 (3.38×3.38×)709 (1.28×1.28×)630 (1.14×1.14×)554 (1.00×1.00×)OPENML-WEKA-2017 (30×10530× 105)005005001,0001,0001,5001,5002,0002,0002200 (2.64×2.64×)2169 (2.60×2.60×)1966 (2.36×2.36×)2191 (2.63×2.63×)1661.5 (1.99×1.99×)1699 (2.04×2.04×)1144 (1.37×1.37×)981 (1.18×1.18×)834 (1.00×1.00×)CSP-Minizinc-Obj-2016 (22×10022× 100) Figure 2: Exact evaluations bought before the decision certificate closes (ES top-3); in parentheses, the multiple of the hindsight optimum Ccert⋆C_cert (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. 5.1 What the experiments measure We evaluate one fixed risk-sensitive selection task on each of two public ASlib algorithm-selection matrices (Bischl et al., 2016). A candidate is an algorithm, a scenario is a benchmark instance, and a cell contains published performance of that algorithm on that instance. The agent must identify the three algorithms with smallest ES across instances. This differs from ordinary algorithm selection, which chooses one algorithm separately for each instance. The complete matrices sit behind a hidden-value replay oracle. Revealing a cell counts as one exact algorithm–instance evaluation, but does not execute a new algorithm run. Thus our measured costs are exact-value query counts, not observed savings in training or solver wall time. We use OPENML-WEKA-2017 (30 classifiers, 105 datasets, loss 1−1-accuracy, ES level 0.100.10, tail mass 10.510.5) and CSP-Minizinc-Obj-2016 (22 solvers, 100 instances, published normalized objective, timeouts as 1, ES level 0.500.50, tail mass 50). In both, k=3k=3, the public unevaluated boxes are [0,1][0,1], query costs are one, and there is no decision-cut tie. Published decimal strings are parsed into exact rationals; floating point is used only for deciding the query order. Equal-information comparison. Our primary baseline comparison uses CAS-PG-T, which has only the public boxes and its own query transcript. The non-predictive policies have exactly those sources too. They share the same certificate but select queries differently: CAS-W targets the widest row bound, CAS-F uses frontier distance, and CAS-PD raises dual weight on a universal witness before buying a tight primitive. Random controls query either any unresolved cell or a cell within the current frontier witness. An additional control uses CAS-PG’s row rule but orders cells uniformly at random within that row. Historical-data comparison. The full CAS-PG also uses a regression prior trained on public instance meta-features and complete outcomes from other instance folds. For each ASlib ten-fold holdout, ridge regression or a 300-tree random forest is selected using inner cross-validation on the training folds, with no outcome from the held-out instance. The historical outcome collection and the one-off predictor fit are uncharged by the replay. This is extra side information, so its improvement is reported separately rather than treated as an equal-information gain. The task matrices, policy family, comparison set and acceptance thresholds (C≤1.50Ccert⋆C≤ 1.50\,C_cert on OPENML and C≤1.75Ccert⋆C≤ 1.75\,C_cert on MiniZinc) were recorded in a protocol file before the first CAS-PG run. The policy family had been developed after pilot values of Ccert⋆C_cert on the matrices were known, with no policy parameter tuned on them; file times alone cannot independently establish the claimed pre-run ordering. All non-random policy runs are deterministic. The full protocol and audit qualifications appear in Appendix C. 5.2 How much does ordering save? The offline minima are Ccert⋆=554C_cert =554 cells on OPENML and 834 on MiniZinc, respectively 17.6%17.6\% and 37.9%37.9\% of their full matrices. CAS-PG-T buys 709 and 1144 cells (1.28×1.28× and 1.37×Ccert⋆1.37× C_cert ). By comparison, the best tested deterministic non-predictive certified schedulers buy 1872 and 1699 cells. The randomized within-row control has medians of 1905.5 and 1641.5 over 30 seeds. This is the equal-information result: information learned during acquisition orders subsequent queries sufficiently well to approach the hindsight minimum on both matrices. Adding the cross-fitted historical prior reduces the default CAS-PG counts to 630 of 3150 on OPENML and 981 of 2200 on MiniZinc (Figures 2 and 1). These are 20.0%20.0\% and 44.6%44.6\% of exhaustive evaluation, or 1.14×1.14× and 1.18×Ccert⋆1.18× C_cert . Both satisfy the pre-declared thresholds. CAS-PG has the lowest exact-query cost among the methods compared in Table 1 on the MiniZinc task; on OPENML, the pre-declared variants CAS-PG-H (623) and CAS-PG-U (626) each use slightly fewer queries than the default (630). The main effect is that learning influences when the certificate can close, not which candidates it accepts. 5.3 What explains the remaining gap? Replacing the within-row prediction by a uniform order raises the median query count to 1905.5 on OPENML and 1641.5 on MiniZinc, close to the uniform-in-witness control. The benefit on these matrices is therefore driven by which scenarios are evaluated within a blocking row. With history alone, CAS-PG-H takes 623 and 1043 queries; the transcript correction reduces MiniZinc to 981 but increases OPENML from 623 to 630. This separates a large benefit from predictive ordering from the mixed incremental benefit of combining two prediction sources. The queries not saved also have an identifiable structure (Table 2). On OPENML, the three selected rows cost 315 queries versus 314 in hindsight; much of the remaining gap comes from the seventh-ranked excluded row, where the policy spends 69 queries against the hindsight minimum of 10 because its predicted worst scenarios differ from the realized tail. On MiniZinc, the selected rows cost 296 versus 217. The hindsight set can leave 23–31 cells of each selected row unevaluated when their realized losses sit at or near the public upper endpoint 1. The policy lacks a general rule for safely skipping such predicted-saturated cells. Two alternative predictor seeds and two fold assignments produce 622–635 queries on OPENML and 981–1034 on MiniZinc for the default policy. Permuting the historical predictions across scenarios or candidates raises its cost to between 1.171.17 and 1.43×Ccert⋆1.43× C_cert , but never changes the certified answer. The predicted-top-k row-rule variant CAS-PG-U is less robust under these perturbations (up to about 2.1×Ccert⋆2.1× C_cert on OPENML). The historical model is not being claimed as a state-of-the-art algorithm selector. As a plain per-instance selector on the challenge split (Lindauer et al., 2019), the same pipeline is slightly worse than the single best algorithm on OPENML. Its value here is to order queries, not to act as a final selector. Independent audit. An independently implemented verifier reproduced both matrices, every reported evaluation count, the exact top-three sets, and Ccert⋆=554/834C_cert =554/834. It checked that 18 deterministic and 120 random transcripts first certify at their last query. Across 576 hidden-truth perturbation tests, the next query remained unchanged when unevaluated values were altered. Compute and evidence scope. The chooser uses 0.2–0.3 CPU seconds per run, with complete certification taking about 2 seconds on one thread; fitting the predictor once takes 21–28 seconds. These are overhead measurements on replayed data. The empirical claim still consists of two matrices, one deterministic run per method, one ES level each, unit costs and [0,1][0,1] boxes. In MiniZinc, 1528 of 2200 values are exactly 0 or 1, so saturation affects certificate behavior. Table 1: Exact evaluations until certification (ES top-3) and their multiple of Ccert⋆C_cert . All methods return the exact full-information set. ∘ : no historical side information. † : median over 30 seeds. ‡ : control run by the independent audit. OPENML-WEKA CSP-Minizinc Method evals ×Ccert⋆× C_cert evals ×Ccert⋆× C_cert Full exact (mSmS) 3150 5.69 2200 2.64 ∘ Uniform over all cells† 3144 5.68 2169 2.60 ∘ CAS-W 3074 5.55 1966 2.36 ∘ CAS-F 3039 5.49 2191 2.63 ∘ Uniform in witness† 2006 3.62 1661.5 1.99 ∘ Row rule, uniform order†‡ 1905.5 3.44 1641.5 1.97 ∘ CAS-PD 1872 3.38 1699 2.04 ∘ CAS-PG-U, transcript only 792 1.43 1126 1.35 ∘ CAS-PG-T 709 1.28 1144 1.37 CAS-PG-H 623 1.12 1043 1.25 CAS-PG-U 626 1.13 989 1.19 CAS-PG 630 1.14 981 1.18 Hindsight Ccert⋆C_cert (offline) 554 1.00 834 1.00 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. OPENML-WEKA CSP-Minizinc Row group Ccert⋆C_cert CAS-PG Ccert⋆C_cert 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 Permuted across instances 753 / 647 1177 / 1177 Permuted across candidates 738 / 743 1171 / 1195 6 What the certificate layer establishes elsewhere The benchmark experiment tests how prediction orders queries inside the core model. The next two studies instead test the certificate layer with non-predictive schedulers. They are separate sources of evidence and use different paid units; neither is an empirical evaluation of CAS-PG on a new oracle. 6.1 Exact recourse solves in energy scheduling The synthetic energy problem chooses k of A generation schedules using ES over the worst third of S service scenarios. Here one queried action–scenario outcome is a genuine exact finite-horizon battery-recourse dynamic-program solve. Without requesting that solve, the public upper bound is the no-battery objective and the lower bound is a per-step relaxation ignoring stock coupling. The non-predictive CAS-PD policy buys queries until the same membership certificate closes. Model-equivalence check. Before charging one unit for each query, we verified that (i) one first-time query makes one exact recourse solve; (i) an independent DP reproduces the paid value; (i) public bounds are derived without hidden responses; (iv) each primitive costs one solve; and (v) full revelation matches direct exact schedule selection. All five checks pass. This justifies comparing the certificate loop against ASAS exact solves on this oracle, rather than assuming the point-query model applies automatically. Across A∈8,16,32A∈\8,16,32\, S∈32,64,128S∈\32,64,128\, k∈1,2k∈\1,2\ and eight seeds (144 scale-grid cells), the certificate avoids 93.0% of the sum of exhaustive exact recourse solves. The median and mean cell avoid 92.9%92.9\% and 91.2%91.2\%; the nine (A,S)(A,S) families have median avoidance of 82.882.8–96.0%96.0\%, and the worst cell avoids 71.0%71.0\%. Across 148 completed energy rows, including four small exact-ratio cells, there are zero decision errors. A separately attempted scale-grid exact-ratio run timed out and contributes no certificate fields. On the four small cells (S=16S=16), CAS-PD takes between 2 and 11 times Ccert⋆C_cert : large solve avoidance is not evidence of near-optimal acquisition. The 93.0%93.0\% measure excludes public-bound construction and total runtime. 6.2 Stress tests: smaller margins and looser bounds Three controlled quadratic tasks (12 candidates, 64 scenarios, k=3k=3, one fixed instance per regime) vary the decision margin and curvature while retaining certified loss intervals. This asks whether an acquisition policy continues to certify or falls back safely as screening becomes less informative. The policies are CAS-W, CAS-F and CAS-CI (certificate-impact ordering), not CAS-PG. The paid unit is one distinct candidate–scenario primitive in the full-exact reference, so the denominators are 4480 for benign/high curvature and 4224 for small margin, not simply mSmS. On the benign task CAS-W and CAS-F require 99 and 128 exact queries, versus 250 for scenario-only screening and 4480 for candidate-only or full evaluation. At a small margin their counts rise to 191 and 192 against 257 and 4224. Under high curvature CAS-F, CAS-CI and CAS-W use 576, 640 and 760 of 4480 queries; one-sided baselines were not run in that regime (Figure 3). The invariant is the exact answer, not a uniformly small budget: weaker bounds can require more exact work or the full fallback, but never justify an uncertified decision. Separate diagnostic tests in Appendix I assess low-rank initialization. PCA and randomized SVD (Halko et al., 2011) can help produce initial certified intervals; the interval certificate, not PCA/SVD, settles two benign geometry cells without queries. A hand-built rank-one PCA case retains 99.990001%99.990001\% of variance yet misses the decisive candidate (regret 5 in aggregate risk-score units). Predictive methods also lack stopping authority. In controlled Merton regimes (Merton, 1976), delta, second-order, XGBoost (Chen and Guestrin, 2016) and MLP surrogates yield outputs that may be correct or incorrect but have no certificate. These tests support the separation of prediction from stopping, not a claim that a particular surrogate is uniformly inferior. 005510101515Benign: CAS-WCAS-CICAS-Fscenario-onlySmall margin: CAS-WCAS-Fscenario-onlyHigh curvature: CAS-FCAS-CICAS-W99125128191192576640760250257share of exhaustive exact evaluations (%) 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. 7 Extensions and limits of the certified model The stopping test of Theorem 2 depends on valid, attained row endpoints, not on the particular tail-risk spectrum. For spectra other than ES, however, finding the cheapest query set that tightens those endpoints can be harder. We state three distinct routes below to show what the certificate framework permits. The full statements, algorithms, assumptions and proofs are in Appendices D, E, F and G. These are extensions of the offline certificate theory, not performance results for CAS-PG. 7.1 Three routes beyond unit-cost empirical ES Certify a coarsened spectrum (CAS-SC). A spectrum can be replaced by its block-average weights on K contiguous ranks. Instead of assuming that this approximation preserves the choice, CAS-SC encloses its error over the entire current candidate box. For a contiguous partition P the spectral residual Ω(y)=ρλ(y)−ρλ~(y) _P(y)= _λ(y)- _ λ^P(y) satisfies 0≤α^j,≤Ω(y)≤βj,(y∈Bj).0≤ α_j,P≤ _P(y)≤ _j,P (y∈ B_j). The rational block corrections, including the strengthened lower bound, are proved in Theorem D.1. Optimal candidate-specific partitions take O(S2logS+KS2)O(S^2 S+KS^2) rational operations after sorting, and K=SK=S returns the original spectrum exactly. The least block count that this procedure needs to certify a decision, Kdec♯K_ dec , can equal S; it is not an intrinsic information dimension. A sufficient current-box condition is (wi+wj)hK<γij(w_i+w_j)h_K< _ij, where w is maximum coordinate width, hKh_K the best K-block half-ℓ1 _1 error and γij _ij the exact endpoint margin. On the computed compression population at relative width 1/21/2, median Kdec♯K_ dec is 2 for geometric spectra at S=32,64,128S=32,64,128 and 1 for linear spectra at those sizes and irregular spectra at S=32,64S=32,64. With K=2K=2, candidate-aware segmentation certifies 73%73\% of 200 matched cells, versus 35%35\% for uniform ranks and 26%26\% for each of two static spectrum-only rules. At S=128S=128, coverage is incomplete following memory pressure (62.5%,37.5%,0%62.5\%,37.5\%,0\% across families); these are conditional certificate statistics, not measured runtime acceleration. Exploit row structure (CAS-SV). For any explicit rational coherent spectrum, the lower row frontier under unit query budgets is computable in polynomial time. The upper frontier has a fixed-band SO(K)S^O(K) algorithm, which is XP in the number of spectral bands. Exact full verification is also available when each selected row’s mutable intervals split into value-separated common-anchor components (an O(S4)O(S^4) all-budget algorithm), or when the row has depd_ ep distinct endpoint pairs (an O((dep+1)2depS2logS)O((d_ ep+1)2^d_ epS^2 S) algorithm, FPT in depd_ ep). One-cut composition then returns the exact hindsight certificate and a witness. Small-scale independent oracle checks at S≤8S≤ 8 have zero mismatches. These are structural algorithms, not a general complexity classification. The unrestricted coherent-spectral upper frontier, unrestricted exact verifier and FPT versus XP in spectral band count remain Open; general polyhedral-risk hardness does not settle the spectral case. Price queries without changing the decision (CAS-PT). With information-disjoint exact point queries, explicit rational coherent spectra, fixed ID ties and strictly positive rational prices drawn from at most a fixed c classes, an offline approximation scheme returns an original-coordinate certificate satisfying Ccert⋆≤Calg≤(1+ε)Ccert⋆C_cert ≤ C_ alg≤(1+ )C_cert for fixed rational 0<ε<10< <1 in bit complexity (S+1)O(c/ε)poly(m,L)(S+1)^O(c/ )poly(m,L). This is a PTAS for fixed c and only XP jointly in (c,1/ε)(c,1/ ): it is not FPT, EPTAS or FPTAS. Free primitives are preprocessed. The approximation concerns certificate price; membership remains exact. At S=1S=1 the problem reduces to minimum-weight-basis verification on a uniform matroid (Diwan et al., 2026). The scheme is a hindsight result, not a cost guarantee for an online predictor. 7.2 Shared primitives and interval-valued financial oracles FRTB-inspired hedge screening asks for candidates hjh_j that maximize the reduction in scenario-based portfolio risk K(P)−K(P+hj)K(P)-K(P+h_j) (Basel Committee, 2019). Our controlled financial workload is not a production Basel FRTB calculation. It differs from the core point-query model in two decisive ways: hedge packages share leg–scenario pricing primitives, and the nonlinear Merton pricer (Merton, 1976) returns certified intervals rather than atomic exact losses. We therefore verify correctness directly using interval containment and an exact fail-closed fallback. We do not transfer Ccert⋆C_cert , the online ratios, or the priced certificate PTAS to this workload, and CAS-PG was not run on it. On nine cells (S∈32,64,128S∈\32,64,128\ and 12, 24 or 48 hedge candidates), the second-order Taylor, certified mixture-truncation and outward-rounded Merton enclosure produces the same selected membership as full evaluation. Naive package–shock calls divided by distinct shared primitives are 2.80×2.80×, 7.60×7.60× and 17.20×17.20× for the three candidate counts (9.2×9.2× pooled). Reusing one cache across candidate-count cells at fixed S requires exactly 3.00×3.00× fewer fresh calls than independent caches. These are opportunities available to any caching evaluator, not certificate-caused savings. Repeated cold-cache timings of three scaled cells show no per-cell wall-clock speedup (each paired lower 95% confidence limit is below one); one earlier small cell has a marginal 1.05×1.05× ratio. A cross-cell sharing timing test is still missing. Scope summary. The public-query efficiency ratios concern two exact, disjoint, unit-cost empirical-ES replay tasks. Energy and quadratic experiments use non-predictive query ordering; the general-risk and price results require their own assumptions; finance uses a different shared, interval-query information model. Their work-count denominators cannot be pooled (Section 7.3). A prediction-error-dependent online cost guarantee and a safe policy for skipping endpoint-saturated scenarios remain open. 7.3 Evidence units and denominators The studies measure different forms of expensive work. The reported reductions below are not combined into a single speedup. Table 3: Paid units and claim scope across experimental studies. Study Paid unit / denominator What the evidence establishes ASlib replay algorithm–instance value; mSmS and Ccert⋆C_cert CAS-PG, CAS-PG-T and certified controls: exact membership and query cost Native energy exact recourse solve; ASAS 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 8 Related work Paid information under uncertainty. Explorable uncertainty studies what to reveal when values lie in known intervals (Feder et al., 2003; Erlebach and Hoffmann, 2015; Halldórsson and de Lima, 2021). Merino and Soto analyze non-adaptive universal query sets (Merino and Soto, 2019); Diwan et al. optimize realized minimum-weight-basis verification (Diwan et al., 2026); and Dür et al. study inclusion/exclusion thresholds under a different quantifier structure (Dür et al., 2024). Megow and Schlöter examine uncertain set selection with additive values (Megow and Schlöter, 2023), whereas Schlöter’s resource augmentation relaxes solution quality (Schlöter, 2025). Here the value of a single selectable candidate is an ordered aggregate of many hidden scenario outcomes, and membership must remain exact. Algorithms with predictions. Learning-augmented algorithms seek cost or performance guarantees that improve with good predictions while remaining robust to poor ones (Lykouris and Vassilvitskii, 2021; Mitzenmacher and Vassilvitskii, 2022). Prediction-guided query policies have also been studied for uncertain minimum spanning trees (Erlebach et al., 2022). Our invariant is zero-error membership for every prediction; the measured ratio to a computable realized hindsight certificate is not a consistency–robustness bound in prediction error. Algorithm identification and tail risk. Classical algorithm selection predicts which algorithm to use on each instance (Rice, 1976; Bischl et al., 2016; Lindauer et al., 2019). We instead select one set of algorithms ranked by tail loss across all instances. Stochastic best-arm and top-k identification, including tail-risk objectives, yield probabilistic sampling guarantees (Agrawal et al., 2021; Kalyanakrishnan et al., 2012); ES simulation likewise supports statistical confidence intervals (Lan et al., 2010). Our uncertainty sets are deterministic and require invariance under every feasible completion. Ordered risk aggregation. OWA and spectral risk are established aggregation frameworks (Yager, 1988; Acerbi, 2002; Kasperski and Zieliński, 2015). Chassein et al. approximate OWA-based optimization by aggregating scenarios with quality loss (Chassein et al., 2020); Baak et al. extend OWA to interval-supported coefficients (Baak et al., 2024). Our coarsening extension retains a certified residual interval for the original risk rule; more centrally, CAS combines query costs, ordered risk, exact membership certificates and predicted acquisition in one agent. 9 Conclusion A costly selection task need not determine every candidate’s risk score to know its exact best set. Under the specified disjoint exact-query model, one cut between selected upper and excluded lower keys certifies top-k membership; for empirical ES, the least certifying information in hindsight can itself be computed exactly. CAS-PG uses prediction to approach that information benchmark while leaving the certificate in full control of stopping. Its two public-matrix results and the separate energy recourse study show why this division is practically meaningful, while the spectral, priced and financial extensions delineate where distinct proofs or information models are needed. The general principle is simple: predict what to evaluate, but certify what to choose. References Acerbi (2002) C. Acerbi. Spectral measures of risk: A coherent representation of subjective risk aversion. Journal of Banking & Finance, 26(7):1505–1518, 2002. Acerbi and Tasche (2002) C. Acerbi and D. Tasche. On the coherence of Expected Shortfall. Journal of Banking & Finance, 26(7):1487–1503, 2002. Agrawal et al. (2021) S. Agrawal, W. M. Koolen, and S. Juneja. Optimal best-arm identification methods for tail-risk measures. In Advances in Neural Information Processing Systems, volume 34, 2021. Artzner et al. (1999) P. Artzner, F. Delbaen, J.-M. Eber, and D. Heath. Coherent measures of risk. Mathematical Finance, 9(3):203–228, 1999. Baak et al. (2024) W. Baak, M. Goerigk, A. Kasperski, and P. Zieliński. An extension of Ordered Weighted Averaging over intervals with application to optimization under risk. arXiv:2410.09786, 2024 (revised 2026). Basel Committee (2019) Basel Committee on Banking Supervision. Minimum capital requirements for market risk. Bank for International Settlements, January 2019 (rev. February 2019). Bischl et al. (2016) B. Bischl, P. Kerschke, L. Kotthoff, M. Lindauer, Y. Malitsky, A. Fréchette, H. Hoos, F. Hutter, K. Leyton-Brown, K. Tierney, and J. Vanschoren. ASlib: A benchmark library for algorithm selection. Artificial Intelligence, 237:41–58, 2016. Chassein et al. (2020) A. Chassein, M. Goerigk, A. Kasperski, and P. Zieliński. Approximating combinatorial optimization problems with the ordered weighted averaging criterion. European Journal of Operational Research, 286(3):828–838, 2020. Chen and Guestrin (2016) T. Chen and C. Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–794, 2016. Diwan et al. (2026) H. Diwan, L. Hellerstein, N. Megow, and J. Schlöter. Optimal verification of a minimum-weight basis in an uncertainty matroid. In STACS 2026, LIPIcs 364, Art. 32, 2026. Dür et al. (2024) C. Dür, A. Merino, J. A. Soto, and J. Verschae. Set selection with uncertain weights: Non-adaptive queries and thresholds. arXiv:2404.17214, 2024. Erlebach and Hoffmann (2015) T. Erlebach and M. Hoffmann. Query-competitive algorithms for computing with uncertainty. Bulletin of the EATCS, 116, 2015. Erlebach et al. (2022) T. Erlebach, M. S. de Lima, N. Megow, and J. Schlöter. Learning-augmented query policies for minimum spanning tree with uncertainty. In ESA 2022, LIPIcs 244, pages 49:1–49:18, 2022. Feder et al. (2003) T. Feder, R. Motwani, R. Panigrahy, C. Olston, and J. Widom. Computing the median with uncertainty. SIAM Journal on Computing, 32(2):538–547, 2003. Halldórsson and de Lima (2021) M. M. Halldórsson and M. S. de Lima. Query-competitive sorting with uncertainty. Theoretical Computer Science, 867:50–67, 2021. Halko et al. (2011) N. Halko, P.-G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217–288, 2011. Kalyanakrishnan et al. (2012) S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. PAC subset selection in stochastic multi-armed bandits. In Proceedings of the 29th International Conference on Machine Learning, pages 655–662, 2012. Kasperski and Zieliński (2015) A. Kasperski and P. Zieliński. Combinatorial optimization problems with uncertain costs and the OWA criterion. Theoretical Computer Science, 565:102–112, 2015. Lan et al. (2010) H. Lan, B. L. Nelson, and J. Staum. A confidence interval procedure for Expected Shortfall risk measurement via two-level simulation. Operations Research, 58(5):1481–1490, 2010. Lindauer et al. (2019) M. Lindauer, J. N. van Rijn, and L. Kotthoff. The algorithm selection competitions 2015 and 2017. Artificial Intelligence, 272:86–100, 2019. Lykouris and Vassilvitskii (2021) T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM, 68(4):24:1–24:25, 2021. Megow and Schlöter (2023) N. Megow and J. Schlöter. Set selection under explorable stochastic uncertainty via covering techniques. In IPCO 2023, LNCS 13904, pages 319–333, 2023. Merino and Soto (2019) A. I. Merino and J. A. Soto. The Minimum Cost Query Problem on Matroids with Uncertainty Areas. In ICALP 2019, LIPIcs 132, pages 83:1–83:14, 2019. Merton (1976) R. C. Merton. Option pricing when underlying stock returns are discontinuous. Journal of Financial Economics, 3(1–2):125–144, 1976. Mitzenmacher and Vassilvitskii (2022) M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65(7):33–35, 2022. Rice (1976) J. R. Rice. The algorithm selection problem. Advances in Computers, 15:65–118, 1976. Rockafellar and Uryasev (2002) R. T. Rockafellar and S. Uryasev. Conditional value-at-risk for general loss distributions. Journal of Banking & Finance, 26(7):1443–1471, 2002. Schlöter (2025) J. Schlöter. On the complexity of knapsack under explorable uncertainty: Hardness and algorithms. In ESA 2025, LIPIcs 351, pages 6:1–6:15, 2025. Yager (1988) R. R. Yager. On ordered weighted averaging aggregation operators in multicriteria decisionmaking. IEEE Transactions on Systems, Man, and Cybernetics, 18(1):183–190, 1988. Extended proofs, protocols, and reproducibility evidence The appendices are integral to this manuscript. The core decision certificate, empirical-ES computation, and prediction-independent exactness are supported by the proofs below; the remaining appendices specify the boundaries of the spectral, priced, native-oracle, and nonlinear-pricing results. The displays labeled (S.1)–(S.46) retain the original supplement numbering for traceability. Purpose and scope. These appendices give complete mathematical arguments, protocol details, and reproducibility specifications behind the results in the main text. They do not add new claims beyond the assumptions, complexity classifications, negative boundaries, and empirical denominators stated above. Appendices A and B prove the certificate results that CAS-PG relies on. Appendix C proves that the answer of CAS-PG does not depend on its predictor and specifies the public-benchmark protocol, its ablations and its independent audit. Appendices D, E, F and G prove the extensions to general spectral risk and priced certificates. Appendix H proves the online boundary. Appendices I and J specify the energy, quadratic, compression and finance studies. Branch names. The online agents share the stopping certificate and differ in their acquisition rules (Figure 1). The theory extensions below instead modify the risk or cost model; they should not be interpreted as extra CAS-PG evaluations. Agents: CAS-PG (prediction-guided; history and transcript), CAS-PG-T (transcript only, no history), CAS-PG-H (history only), CAS-PG-U (predicted-top-k row rule), and the non-predictive CAS-PD (primal–dual), CAS-W (width), CAS-F (frontier) and CAS-CI (certificate impact). Theory branches: CAS-SC (spectral coarsening, Appendix D), CAS-SV (structural verification, Appendices E and F) and CAS-PT (priced certificates, Appendix G). Appendix A Exact-query model and one-cut composition There are m candidates and S scenario coordinates per candidate. A realized row xjx_j belongs to a closed Cartesian box Bj=∏s=1S[ℓjs,ujs]B_j= _s=1^S[ _js,u_js]. A query to coordinate (j,s)(j,s) reveals xjsx_js exactly and replaces its interval by the singleton xjs\x_js\. Rows are information-disjoint in the theorem model. The original spectrum is explicit, rational, and coherent, ρλ(y)=∑r=1Sλry(r),λ1≥⋯≥λS≥0,∑rλr=1, _λ(y)= _r=1^S _ry_(r), _1≥·s≥ _S≥ 0, _r _r=1, where order statistics are descending. Distinct fixed IDs resolve numerical ties. For a row query set Q, define residual endpoint rows usQ=xss∈Q,uss∉Q,ℓsQ=xss∈Q,ℓs∉Q.u_s^Q= casesx_s&s∈ Q,\\ u_s&s∉ Q, cases _s^Q= casesx_s&s∈ Q,\\ _s&s∉ Q. cases Coordinatewise monotonicity of every coherent spectrum gives exact attained row extrema U(Q)=ρλ(uQ),L(Q)=ρλ(ℓQ).U(Q)= _λ(u^Q), L(Q)= _λ( ^Q). Because the box is closed, the two corner rows in (S.2) themselves attain these extrema; no separate compactness assumption is needed. Theorem A.1 (One-cut characterization). Let A=Dk(x)A=D_k(x) be the realized ID-resolved top-k membership set. A row-wise query allocation (Qj)j(Q_j)_j certifies A if and only if maxi∈A(Ui(Qi),idi)<lexminj∉A(Lj(Qj),idj). _i∈ A(U_i(Q_i),id_i)<_ lex _j∉ A(L_j(Q_j),id_j). For unit costs, exact row frontiers therefore compose through a finite scan of selected-row upper frontier keys. Proof. If (S.4) holds, every compatible selected key is no larger than its row upper key and every excluded key is no smaller than its row lower key, so selected and excluded membership cannot cross. Conversely, if (S.4) fails, there is a selected i and excluded j whose upper/lower keys are reversed or whose equality is owned by the excluded ID. Cartesian row independence permits simultaneous realization of row i at its upper corner and row j at its lower corner. At that completion j precedes i, contradicting invariant top-k membership. For composition, define Uj⋆(q)=min|Q|≤qUj(Q),Lj⋆(q)=max|Q|≤qLj(Q).U_j (q)= _|Q|≤ qU_j(Q), L_j (q)= _|Q|≤ qL_j(Q). Replace each row of any certificate by an attaining same-budget frontier set; all separating inequalities weakly improve. The largest selected upper key is one of the k(S+1)k(S+1) selected-row frontier keys. Scanning such a key d and summing, row by row, the least budget placing selected upper keys at most d and excluded lower keys strictly above d yields the optimum. The frontier witnesses concatenate into an original-coordinate certificate. ∎ Appendix B Exact empirical-ES row frontiers Let the empirical ES tail mass be τ∈(0,S]τ∈(0,S]. The finite-sample variational identity is ESτ(y)=minz∈ℝ[z+1τ∑s=1S(ys−z)+].ES_τ(y)= _z [z+ 1τ _s=1^S(y_s-z)_+ ]. For integer τ this is the mean of the largest τ coordinates; for noninteger τ the boundary observation receives the usual fractional mass. B.1 Upper frontier For a fixed threshold z, revealing upper coordinate s reduces the hinge objective by gs(z)=(us−z)+−(xs−z)+≥0.g_s(z)=(u_s-z)_+-(x_s-z)_+≥ 0. Thus, for fixed z and budget q, the optimal query set is the q largest gs(z)g_s(z). Each gain is a plateau below xsx_s, a ramp of slope −1-1 on [xs,us][x_s,u_s], and zero above usu_s. Two ramp pieces have equal slope and cannot exchange order in their interiors. Hence gain ordering changes only at endpoints or plateau–ramp intersections. There are O(S2)O(S^2) such rational breakpoints. Between consecutive breakpoints the set of q largest gains is fixed and the ES objective is affine in z, so a minimum occurs at a breakpoint. Exact rational evaluation of every breakpoint therefore yields U⋆(q)U (q) and an attaining query set for every q. Ties are resolved with deterministic coordinate IDs and do not change the risk value. B.2 Lower frontier For integer tail size r, maximizing the ES lower endpoint is equivalent to maximizing the sum of the r largest values in the vector whose coordinate s is either ℓs _s or xsx_s. Sort the endpoint events and use a dynamic program whose state records the number of coordinates processed, the number of tail slots filled, and the number of queries used. At coordinate s the three feasible transitions are: omit it from the tail; use ℓs _s in the tail; or query and use xsx_s in the tail. A standard endpoint-order DP (or, equivalently, a rank-selection DP that enforces the chosen tail entries are the largest entries) gives the exact maximum for each budget. Revelation changes which coordinates occupy the tail, so this calculation does not freeze the initially active tail. If τ=r+δτ=r+δ with 0<δ<10<δ<1, enumerate the coordinate occupying the fractional (r+1)(r+1)st tail position and whether it is queried. The remaining r full-weight positions are solved by the integer DP subject to the pivot threshold. There are O(S)O(S) pivots and polynomially many states per pivot. All quantities are rational combinations of input endpoints; numerator and denominator bit lengths remain polynomial. Consequently both ES frontiers, attaining query sets, and their one-cut composition have polynomial bit complexity. Appendix C CAS-PG: exactness, protocol and audit C.1 Prediction-independent exactness Work in the model of Appendix A with empirical-ES rows and unit costs. At each iteration CAS-PG holds, for every row, the current box (public bounds with evaluated cells replaced by their exact values) and the exact rational endpoints Lj,UjL_j,U_j of (S.3). Let A be the set of the k smallest keys (Lj,idj)(L_j,id_j), i⋆=argmaxi∈A(Ui,idi)i = _i∈ A(U_i,id_i) and j⋆=argminj∉A(Lj,idj)j = _j∉ A(L_j,id_j). The run stops and returns A when (Ui⋆,idi⋆)<lex(Lj⋆,idj⋆)(U_i ,id_i )<_ lex(L_j ,id_j ). Otherwise it evaluates one unevaluated cell of row i⋆i if there is one, else of row j⋆j ; which cell is decided by a score that may depend on an arbitrary prior p0p^0 and on the transcript. Proposition C.1 (Prediction-independent exactness). For every realization x in the public box and every prior p0p^0, CAS-PG (i) terminates after at most mSmS evaluations, (i) returns Dk(x)D_k(x), and (i) stops at the first prefix of its own query sequence that certifies the decision. Hence Ccert⋆(x)≤CCAS-PG(x)≤mSC_cert (x)≤ C_ CAS-PG(x)≤ mS. Proof. Invariant. A box coordinate changes only when the oracle returns its exact value, so x lies in the current box at every iteration, whatever p0p^0 is. The prior enters only the choice among unevaluated cells of an already chosen row. Soundness of the stop. Suppose the test holds for A. For every completion v of the current box and every i∈Ai∈ A, j∉Aj∉ A, (ρ(vi),idi)≤(Ui,idi)≤(Ui⋆,idi⋆)<(Lj⋆,idj⋆)≤(Lj,idj)≤(ρ(vj),idj)(ρ(v_i),id_i)≤(U_i,id_i)≤(U_i ,id_i )<(L_j ,id_j )≤(L_j,id_j)≤(ρ(v_j),id_j). So Dk(v)=AD_k(v)=A for every completion, in particular A=Dk(x)A=D_k(x). No late stop. Suppose the current transcript certifies Dk(x)D_k(x). By Theorem A.1, (S.4) holds with A′=Dk(x)A =D_k(x). Every selected lower key is at most the corresponding upper key, which precedes every excluded lower key; hence the k smallest lower keys are exactly A′A , so A=A′A=A and the test fires at this iteration. The test is evaluated before every query, so the run stops at the first certifying prefix. This gives (i) and (i). Progress. Suppose the test fails and both rows i⋆i and j⋆j are fully evaluated. Then Ui⋆=Li⋆U_i =L_i and (Li⋆,idi⋆)<(Lj⋆,idj⋆)(L_i ,id_i )<(L_j ,id_j ) because i⋆∈Ai ∈ A, j⋆∉Aj ∉ A and IDs are distinct, so the test holds, a contradiction. Therefore a failed test always leaves an unevaluated cell in row i⋆i or j⋆j ; each iteration evaluates a new cell, and there are mSmS cells. This is (i). The lower bound Ccert⋆≤CCAS-PGC_cert ≤ C_ CAS-PG is the definition of Ccert⋆C_cert applied to the certifying set of evaluated cells. ∎ The proposition bounds nothing about cost beyond [Ccert⋆,mS][C_cert ,mS]; by Appendix H no zero-error online policy has a worst-case ratio. The same argument applies to every chooser plugged into the same loop (the random baselines and CAS-PG-U included): the loop, not the chooser, owns the certificate. C.2 Score and predictor Inside the chosen row r the score of an unevaluated cell s is the exact one-step change of the row’s lower ES endpoint when the cell is pseudo-revealed at its clipped predicted value p^rs p_rs; ties are broken by the larger prediction, then by primitive ID. The pseudo-value is discarded. On a [0,1][0,1] box this is the order of decreasing predicted loss. The one-step change of the upper endpoint is not used: on such a box it is zero until fewer than t cells of the row remain. The prediction is p^js=clip(pjs0+es) p_js=clip(p^0_js+e_s) with es=∑j′∈Rs(xj′s−pj′s0)/(|Rs|+1)e_s= _j ∈ R_s(x_j s-p^0_j s)/(|R_s|+1), where RsR_s is the set of rows already evaluated in scenario s. The shrinkage constant 11 is fixed. The historical prior p0p^0 is cross-fitted by scenario over the ten folds published in the benchmark’s cross-validation file (repetition 1). Inputs are the public instance meta-features (median-imputed, signed-log transformed, standardized; all fitted on training folds), with one output per candidate. The model is ridge regression with 13 penalties in [10−2,104][10^-2,10^4] or a 300-tree random forest, chosen per outer fold by five-fold inner cross-validation on that fold’s training instances; one fixed seed, one thread. The proxy for an instance therefore never uses any outcome on that instance. It does use complete outcome columns of the other nine folds, which the replay does not charge. CAS-PG-T (no history) replaces p0p^0 by the interval midpoint 1/21/2; CAS-PG-H (history only) switches the correction ese_s off. CAS-PG-U scores the unevaluated cells of every unresolved row that the predicted completion ranks in the top k; when no such row has an unevaluated cell it applies the CAS-PG rule. C.3 Tasks, data and validity rules Data: the public ASlib repository at a fixed commit, verified file by file against recorded SHA-256 digests. Every published value is parsed from its decimal string into an exact rational. OPENML-WEKA-2017 CSP-Minizinc-Obj-2016 performance column predictive accuracy (maximize) objective (minimize) loss 1−1-accuracy objective, unchanged candidates × scenarios 30×10530× 105 22×10022× 100 records / duplicates / missing 3150 / 0 / 0 2200 / 0 / 0 run status 3150 ok 1822 ok, 378 timeout loss range [0,159/160][0,159/160] [0,1][0,1] cells equal to 0 / 1 141 / 0 923 / 605 ES level, tail mass 0.10, 21/221/2 0.50, 50 k, cost 3, one per cell 3, one per cell acceptance threshold C≤1.50Ccert⋆C≤ 1.50\,C_cert C≤1.75Ccert⋆C≤ 1.75\,C_cert All candidates and scenarios are retained. The MiniZinc scenario documents its objective as normalized to [0,1][0,1] with timeouts recorded as 1, and all 378 timeout cells carry the value 1; the published value is used as the loss. The public interval of every unevaluated cell is [0,1][0,1]. Ties are owned by the lexicographic order of stable candidate IDs. The full-information top-3 have ES 0.5773,0.5895,0.60110.5773,0.5895,0.6011 (fourth: 0.62700.6270) on OPENML and 0.5651,0.6019,0.62990.5651,0.6019,0.6299 (fourth: 0.65260.6526) on MiniZinc; there is no tie at either cut. A run is valid only if the returned set equals the independently computed full-information set, the final transcript re-certifies, the transcript one query shorter does not certify, and no primitive is charged twice. All reported runs are valid, with zero certificate violations. C.4 Complete results OPENML-WEKA-2017 CSP-Minizinc-Obj-2016 method evals /mS/mS /Ccert⋆/C_cert evals /mS/mS /Ccert⋆/C_cert full exact mSmS 3150 1.000 5.686 2200 1.000 2.638 hindsight Ccert⋆C_cert (offline) 554 0.176 1.000 834 0.379 1.000 CAS-W (width) 3074 0.976 5.549 1966 0.894 2.357 CAS-F (frontier) 3039 0.965 5.486 2191 0.996 2.627 CAS-PD (primal–dual) 1872 0.594 3.379 1699 0.772 2.037 uniform over all cells (median) 3144 0.998 5.675 2169 0.986 2.601 uniform in witness (median) 2006 0.637 3.621 1661.5 0.755 1.992 CAS-PG 630 0.200 1.137 981 0.446 1.176 CAS-PG-U 626 0.199 1.130 989 0.450 1.186 CAS-PG-T (no history) 709 0.225 1.280 1144 0.520 1.372 CAS-PG-U, transcript only 792 0.251 1.430 1126 0.512 1.350 CAS-PG-H (history only) 623 0.198 1.125 1043 0.474 1.251 CAS-PG-U, history only 623 0.198 1.125 1047 0.476 1.255 Random baselines use seeds 0–29. Interquartile ranges and ranges: random, all cells 3139.5–3145.75 (3118–3150) and 2153.5–2180.5 (2134–2195); random in witness 1975–2036.25 (1910–2132) and 1650.25–1668.75 (1615–1698). The no-history and history-only rows were declared in the protocol as diagnostics of the two prediction inputs, not as additional variants for the acceptance thresholds. The reported numbers are those of the first execution; a second execution produced byte-identical transcripts. Where the gap to Ccert⋆C_cert lies (evaluations by row group). hindsight CAS-PG CAS-PG-U OPENML, three selected rows 314 315 315 OPENML, 27 excluded rows 240 315 311 MiniZinc, three selected rows 217 296 300 MiniZinc, 19 excluded rows 617 685 689 On OPENML one near-cut row (seventh by ES, 0.6340.634 against the cut at 0.6010.601) takes 69 (CAS-PG) or 58 (CAS-PG-U) evaluations against a hindsight budget of 10; the median excluded row takes 10 (hindsight 7–10). On MiniZinc hindsight leaves 23–31 cells per selected row unevaluated because their true value is 1 or close to it; the policy evaluates 97–100 of 100. The remaining 68–72 extra evaluations are on excluded rows, mostly the fifth row by ES (57 or 58 against 33). Predictor sensitivity and controls (run by the independent audit). Evaluations, with the multiple of Ccert⋆C_cert where stated. OPENML-WEKA-2017 CSP-Minizinc-Obj-2016 prior CAS-PG CAS-PG-U CAS-PG CAS-PG-U protocol predictor 630 626 981 989 other predictor seeds (2) 634 / 622 626 / 623 981 / 988 988 / 996 random fold assignments (2) 631 / 635 631 / 633 1034 / 1032 1055 / 1056 permuted across scenarios (2) 753 / 647 670 / 616 1177 / 1177 1187 / 1183 permuted across candidates (2) 738 / 743 1184 / 1179 1171 / 1195 1263 / 1428 row rule, random in-row order (median, 30 seeds) 1905.5 1641.5 Under permuted priors CAS-PG stays within 1.171.17–1.43Ccert⋆1.43\,C_cert ; CAS-PG-U reaches about 2.1Ccert⋆2.1\,C_cert on OPENML and 1.71Ccert⋆1.71\,C_cert on MiniZinc. The row rule with a uniformly random in-row order and no model costs 3.44Ccert⋆3.44\,C_cert and 1.97Ccert⋆1.97\,C_cert , the same as random-in-witness, so the whole improvement is the predicted within-row order. Overhead. Chooser CPU per full run: 0.19–0.28 s (CAS-PG) and about 1.3 s (CAS-PG-U). Whole run including exact certification: 1.7–3.1 s, against 5–29 s for CAS-W, CAS-F and CAS-PD, whose receipts do not separate scheduler time; much of the difference is fewer certificate refreshes. Cross-fitted predictor fit, once per task: 21–28 s CPU on one thread. C.5 Independent audit A separate verifier, sharing no checker code with the implementation (own data reader, exact ES, certificate test and separator enumeration), reported the following. • Data. All source files match their digests; both matrices and their hashes were reconstructed independently, with no duplicates or missing cells. The fractional ES convention was checked by hand and against the variational form on all 52 rows. • Transcripts. For 18 deterministic and 120 random transcripts: query count equals reported cost; no primitive is charged twice; the run is never certified before its last query and is certified after it; the state one query earlier admits two explicit completions with different top-3 sets. • Hindsight optimum. The 554- and 834-cell sets certify, and removing any single cell breaks the certificate. A separate enumeration over lexicographic separators (36 and 97 candidates) gives the same minima; the next-best separators cost 557 and 835. Global optimality rests on an exchange argument that was not machine-checked beyond agreement with the exact solver. • Leakage. In 576 attacks that altered unevaluated values, the next query was unchanged in every case, while altering one evaluated value does change later queries. Flipping the outcomes of a held-out fold leaves that fold’s predictions bit-identical. A reachability search from the chooser object finds no reference to the hidden matrix, the oracle or the hindsight solver. Only exact rationals enter the certificate path. • Protocol hygiene. The record that fixes the protocol before the first run is a same-session hash file, not a version-control commit. Three of its nine hashes no longer match: a source file was reformatted, and both predictor caches were rebuilt once to test determinism (identical predictions; only a recorded timing field differs). The runs were executed twice with byte-identical transcripts. The audit could not confirm the pre-run ordering beyond file times, nor the statement that development used synthetic matrices only. • Fairness. The audit regards the no-history variant as the primary comparison against the non-predictive schedulers, because the historical predictor is uncharged side information. The acceptance thresholds were fixed with pilot values of Ccert⋆C_cert in view. Scope. Two matrices, [0,1][0,1] boxes, unit costs, k=3k=3, one tail level each; no secondary cells were run. Nothing here concerns shared primitives, interval oracles or non-unit costs. The historical predictor was not designed as an algorithm selector. Evaluated post hoc as a plain per-instance selector on the official train/test split of the 2017 algorithm-selection challenge (Lindauer et al., 2019), the same pipeline is slightly worse than the single best algorithm on OPENML-WEKA-2017 (remaining gap 1.111.11) and leaves 0.520.52 of the gap on CSP-Minizinc-Obj-2016. These numbers are context for the statement that the predictor’s role is query ordering; no algorithm-selection performance claim is made. C.6 The primal–dual scheduler CAS-PD CAS-PD maintains, at each uncertified transcript, a universal witness W of unevaluated primitives (every certificate must evaluate at least one of them), raises a dual weight yWy_W until some member is tight under ∑W∋pyW≤cp _W py_W≤ c_p, and evaluates a tight primitive. In the independent exact point-query model with positive costs this gives LPD≤Ccert⋆≤Calg≤ΓrunLPDL_ PD≤ C_cert ≤ C_ alg≤ _ runL_ PD with LPD=∑WyWL_ PD= _Wy_W and Γrun _ run the largest witness size met in the run. Γrun _ run is run-dependent and can be as large as the number of primitives, so this is an instance-relative sandwich and not a constant or logarithmic competitive ratio. Appendix D Decision-preserving spectral coarsening Let P be a contiguous partition of the rank set. For block B=(a,b]B=(a,b] define μB=1b−a∑r=a+1bλr,cr=λr−μB, _B= 1b-a _r=a+1^b _r, c_r= _r- _B, and let λ~r=μB λ^P_r= _B on that block. With G(r)=∑h≤rλhG(r)= _h≤ r _h, define the chord deviation er=G(r)−G(a)−(r−a)μB,a≤r≤b.e_r=G(r)-G(a)-(r-a) _B, a≤ r≤ b. Concavity of G gives er≥0e_r≥ 0 and ea=eb=0e_a=e_b=0. For a current candidate box, sort lower and upper endpoint rows independently, writing L1≥⋯≥LSL_1≥·s≥ L_S and U1≥⋯≥USU_1≥·s≥ U_S. Define the block quantities AB=∑r=a+1b−1er[Lr−Ur+1]+,A_B= _r=a+1^b-1e_r[L_r-U_r+1]_+, B=∑r∈B(cr)+Ur−∑r∈B(−cr)+Lr,B_B= _r∈ B(c_r)_+U_r- _r∈ B(-c_r)_+L_r, ZB=∑r∈B(cr)+Lr−∑r∈B(−cr)+Ur.Z_B= _r∈ B(c_r)_+L_r- _r∈ B(-c_r)_+U_r. Put α=∑BAB _P= _BA_B, β=∑B _P= _BB_B, and α^=∑BmaxAB,ZB α_P= _B \A_B,Z_B\. Theorem D.1 (Uniform residual certificate). For every compatible row y, 0≤α≤α^≤ρλ(y)−ρλ~(y)≤β.0≤ _P≤ α_P≤ _λ(y)- _ λ^P(y)≤ _P. Therefore [ρλ~(ℓ)+α^,ρλ~(u)+β] [ _ λ^P( )+ α_P, _ λ^P(u)+ _P ] is a valid interval for the original spectrum. Proof. Inside a block, summation by parts gives ∑r∈Bcry(r)=∑r=a+1b−1er(y(r)−y(r+1))≥0. _r∈ Bc_ry_(r)= _r=a+1^b-1e_r(y_(r)-y_(r+1))≥ 0. Sorted endpoint monotonicity gives Lr≤y(r)≤UrL_r≤ y_(r)≤ U_r. Hence each descending gap in (S.14) is at least [Lr−Ur+1]+[L_r-U_r+1]_+, proving the block lower bound ABA_B. Substituting LrL_r against positive crc_r and UrU_r against negative crc_r gives ZB≤∑cry(r)Z_B≤Σ c_ry_(r). Substituting opposite endpoints gives the upper bound B_B. The maximum of two valid lower bounds remains valid; summing over blocks proves (S.12). Adding these residual bounds to the coarsened endpoint risks proves (S.13). ∎ The enhanced endpoint form is additive. If dr=Ur−Lrd_r=U_r-L_r, define EB=∑r∈B(μB−λr)+dr,DB=∑r=a+1b−1erminLr−Lr+1,dr+1.E_B= _r∈ B( _B- _r)_+d_r, D_B= _r=a+1^b-1e_r \L_r-L_r+1,d_r+1\. Direct subtraction yields =ρλ(u)+∑BEB,^=ρλ(ℓ)−∑BminDB,EB. U_P= _λ(u)+ _BE_B, L_P= _λ( )- _B \D_B,E_B\. Thus the best upper and lower corrections over exactly K blocks are obtained by the last-block recurrence H[k,b]=mink−1≤a<bH[k−1,a]+C(a,b),H[0,0]=0.H[k,b]= _k-1≤ a<b\H[k-1,a]+C(a,b)\, H[0,0]=0. Prefix sums and the single sign change of λr−μB _r- _B evaluate every block cost in polynomial rational time; after O(S2logS)O(S^2 S) preprocessing, the segmentation DP uses O(KS2)O(KS^2) arithmetic operations. Revelation raises sorted lower endpoints and lowers sorted upper endpoints, so AB,ZBA_B,Z_B can only improve and B_B can only shrink. Fixed-partition corrected intervals therefore tighten monotonically; optimizing over the unchanged partition family preserves that monotonicity. Define Kdec∃K_ dec^∃ using the original lower floor ABA_B, and Kdec♯K_ dec using maxAB,ZB \A_B,Z_B\. Both are the minimum number of blocks, over candidate-specific partitions with at most that many blocks, needed for the exact ID-aware separator. Because the upper correction is unchanged and the lower correction only improves, Kdec♯≤Kdec∃K_ dec ≤ K_ dec^∃ whenever finite. These are procedure-relative certified degrees, not intrinsic lower bounds on every possible representation. D.1 Current-box versus frozen-root margin bounds For a partition define h()=∑B∈∑r∈B(μB−λr)+=12‖λ−λ~‖1,hK=min||≤Kh().h(P)= _B _r∈ B( _B- _r)_+= 12\|λ- λ^P\|_1, h_K= _|P|≤ Kh(P). If current row j has maximum coordinate width wjw_j, (S.15)– (S.16) imply that its selected-side upper inflation and excluded-side lower deflation are each at most wjh()w_jh(P). Hence, with exact current-box endpoint gap γij _ij, (wi+wj)hK<γij(w_i+w_j)h_K< _ij is sufficient for K-block certification. Equality is also sufficient when the selected ID owns the tie. This is the factor-one current-box statement. If correction bounds are frozen once on a larger root box and reused inside a query-set optimizer, the residual envelope width is at most 2wjh()2w_jh(P), giving the separate factor-two sufficient transfer condition. The two statements use different boxes and are not interchangeable. Appendix E Arbitrary-spectrum coherent lower frontier For one lower row write as=ℓsa_s= _s and bs=xs≥asb_s=x_s≥ a_s. Let v0<⋯<vMv_0<·s<v_M be all distinct endpoints. On cell (vt−1,vt)(v_t-1,v_t) let ntn_t be the number of baseline lower endpoints above its interior and AtsA_ts indicate whether interval [as,bs][a_s,b_s] crosses the cell. With zs∈0,1z_s∈\0,1\ denoting revelation, ρλ(a[z←b])=v0+∑t=1M(vt−vt−1)G(nt+∑sAtszs), _λ(a[z← b])=v_0+ _t=1^M(v_t-v_t-1)G\! (n_t+ _sA_tsz_s ), where G(r)=∑h≤rλhG(r)= _h≤ r _h is linearly interpolated between integers. Because λ is nonincreasing, G is concave and nondecreasing. Relax z∈[0,1]Sz∈[0,1]^S with ∑szs=q _sz_s=q. The hypograph of each term in (S.20) has the exact linear description ηt≤G(r)+λr+1(nt+∑sAtszs−r),r=0,…,S−1. _t≤ G(r)+ _r+1 (n_t+ _sA_tsz_s-r ), r=0,…,S-1. Thus maximizing (S.20) is a polynomial-size rational LP. The missing issue is integrality. Take an LP optimum. If two fractional variables correspond to intervals Ij⊆IiI_j I_i, move δ=min1−zi,zjδ= \1-z_i,z_j\ mass from zjz_j to ziz_i. Cardinality is preserved; every cell covered by IjI_j is also covered by IiI_i, so every coverage count weakly increases. Because G is nondecreasing, the objective cannot decrease. At least one variable becomes integral. Repeating leaves fractional intervals with no containments. Such a proper interval family has left and right endpoints in the same strict order, so the fractional intervals active on any cell form one contiguous block. Order the remaining fractional variables z1,…,zrz_1,…,z_r, let si=∑h≤izhs_i= _h≤ iz_h, and note that their total is integer after subtracting the already integral cardinality. For θ∈[0,1)θ∈[0,1) set Zi(θ)=⌊si+θ⌋−⌊si−1+θ⌋.Z_i(θ)= s_i+θ - s_i-1+θ . Then Zi∈0,1Z_i∈\0,1\, total cardinality is preserved, and Zi=ziEZ_i=z_i for uniform θ. For any contiguous block of fractional variables, its rounded sum is either the floor or ceiling of its fractional sum and has that sum as expectation. After adding the integral part of a cell count, the two possibilities are adjacent integers. The linearly interpolated G is affine between them; hence θG(nt+∑sAtsZs(θ))=G(nt+∑sAtszs).E_θG\! (n_t+ _sA_tsZ_s(θ) )=G\! (n_t+ _sA_tsz_s ). Summing over cells gives expected rounded objective equal to the LP optimum. Only O(S)O(S) distinct rounded vectors occur as θ crosses fractional prefix breakpoints, so one can enumerate them and return an integral optimum and witness. Rational LP solvability, containment updates, breakpoint arithmetic, and objective comparisons all have polynomial bit length. This proves polynomial bit complexity for every unit-cardinality budget. The argument does not extend to arbitrary weighted budgets. Appendix F Structural arbitrary-spectrum upper algorithms For upper endpoint queries, let [xs,us][x_s,u_s] be the active query-change interval. With endpoint cells as above, define btb_t as the baseline number of upper endpoints above cell t and cQ(t)c_Q(t) as the number of queried intervals covering it. Then U(Q)=v0+∑tΔtG(bt−cQ(t)).U(Q)=v_0+ _t _tG(b_t-c_Q(t)). This follows from the layer-cake identity ρλ(y)=v0+∫G(|s:ys>z|)z _λ(y)=v_0+ G(|\s:y_s>z\|)\,dz. F.1 Common anchor and ordered blocks Containment exchange is safe at unit cost: replacing a selected interval by an unselected containing interval weakly increases every coverage cQ(t)c_Q(t) and therefore cannot increase (S.24). Among fixed-cardinality optima there is consequently a down-set in the two-rank partial order given by decreasing usu_s and increasing xsx_s. Assume first that all active intervals share an anchor, maxsxs≤minsus. _sx_s≤ _su_s. Let active coordinates be indexed by decreasing u, and let p(i)p(i) be their rank in increasing x. Let fixed inactive values be z1≥⋯≥zfz_1≥·s≥ z_f and define Bfix=∑j=1fλjzj,d(v)=|j:zj>v|,B_ fix= _j=1^f _jz_j, d(v)=|\j:z_j>v\|, Cb(v)=λb+d(v)v+∑j=d(v)+1f(λj+b−λj+b−1)zj.C_b(v)= _b+d(v)v+ _j=d(v)+1^f( _j+b- _j+b-1)z_j. If active values v1≥⋯≥vnv_1≥·s≥ v_n are inserted into the fixed background in order, telescoping rank shifts give ρλ(v1,…,vn,z1,…,zf)=Bfix+∑b=1nCb(vb). _λ(v_1,…,v_n,z_1,…,z_f)=B_ fix+ _b=1^nC_b(v_b). For exact query count q, construct lattice paths from (0,n)(0,n) to (n,0)(n,0). A row event processes the next uiu_i; a column event processes the next x value in decreasing order. Coordinate i is queried exactly when its row event occurs before its column event. Down-sets correspond to such paths. A state Dq(i,j,a)D_q(i,j,a) records row index i, column index j, and number a of completed queried coordinates. The number of completed unqueried coordinates is determined by (i,j,a)(i,j,a). If a row event closes an already passed column, charge the corresponding upper insertion Cb(ui)C_b(u_i); if a column event closes an already passed row, charge the realized insertion Cn−q+a(xi)C_n-q+a(x_i); the two commitment events have zero immediate cost. Every endpoint is charged once. Condition (S.25) fixes the relative stream order between unqueried upper and queried realized values, so no hidden path history affects future insertion costs. There are O(n2(q+1))O(n^2(q+1)) states and two outgoing transitions; all budgets require O(S4)O(S^4) rational arithmetic, and backpointers recover original query coordinates. If the active intervals split into value-separated blocks and each block has a common anchor, run the local DP at its global rank offset and convolve the block budget curves. Strict-positive-overlap components cannot cross block boundaries; conversely, if every such connected component has a common anchor, the components ordered by value form the required block partition. Sorting and scanning recognizes this condition in O(SlogS)O(S S) comparisons. F.2 Endpoint-pair diversity Group identical active pairs (xs,us)(x_s,u_s) into depd_ ep types with multiplicity mhm_h. At exact budget q, let zhz_h be the queried count in type h: 0≤zh≤mh,∑hzh=q,zh∈ℤ.0≤ z_h≤ m_h, _hz_h=q, z_h . The cell formula becomes (z)=v0+∑tΔtG(bt−∑hAthzh).U(z)=v_0+ _t _tG\! (b_t- _hA_thz_h ). It is concave on the continuous box-hyperplane relaxation. Suppose an optimal integer count vector has two partial types a,ba,b. Move along za+θ,zb−θz_a+θ,z_b-θ. The feasible interval in θ has integer endpoints and at either endpoint one of the two types becomes empty or full. Concavity implies at least one endpoint has objective no larger than the current point; since the current point is optimal, that integer endpoint is also optimal. Repeating leaves at most one partial type. Therefore it suffices to enumerate a subset of fully queried types and an optional partial type whose count is forced by the residual budget: at most (dep+1)2dep(d_ ep+1)2^d_ ep patterns. Evaluating each pattern gives all-budget work O((dep+1)2depS2logS)O((d_ ep+1)2^d_ epS^2 S) up to polynomial rational bit factors. Selected upper frontiers from either route and unrestricted excluded lower frontiers from Appendix E compose exactly by Theorem A.1. This yields the exact minimum original-box certificate and a witness. The parameter depd_ ep is endpoint-pair diversity, not spectral band count. Appendix G Few-price-class certificate-cost PTAS Primitive prices are strictly positive rationals from c distinct classes V1,…,VcV_1,…,V_c, where c is fixed. We first prove a class-count menu theorem for interval coverage and then apply it to spectral endpoint gains. G.1 Coverage formulation and local representatives Let z1<⋯<zMz_1<·s<z_M be marker points. For an interval set Q define cQ(z)=|I∈Q:z∈I|c_Q(z)=|\I∈ Q:z∈ I\| and F(Q)=∑t=1MBt(cQ(zt)),F(Q)= _t=1^MB_t(c_Q(z_t)), where each Bt:0,…,S→ℚ≥0B_t:\0,…,S\ _≥ 0 is nondecreasing and explicitly tabulated. Upper and lower spectral endpoint improvements take this form after endpoint-cell decomposition. Fix one price class and an anchor interval I=[a,b]I=[a,b]. Let KIK_I be class intervals containing anchor point b and CIC_I those containing the whole anchor interval. We construct a family ℛIR_I of SO(1/ε)S^O(1/ ) subsets of KIK_I, each containing CIC_I, with the following property: for every CI⊆MI⊆KIC_I M_I K_I there is RI∈ℛIR_I _I such that cRI(z)≥cMI(z)∀z,|RI∖CI|≤(1+ε)|MI∖CI|.c_R_I(z)≥ c_M_I(z) ∀ z, |R_I C_I|≤(1+ )|M_I C_I|. To see this constructively, order V=KI∖CIV=K_I C_I by increasing left endpoint. Enumerate all subsets of size at most H=⌈2/ε⌉H= 2/ , so small targets are present exactly. For a larger target of outside-compulsory size p, put d=⌊εp⌋≥εp/2d= p ≥ p/2. If fewer than d class intervals are absent from the target, taking all of KIK_I costs less than p+d≤(1+ε)p+d≤(1+ )p. Otherwise retain the whole prefix through the ddth omitted interval. Partition the suffix at every ddth target interval; in each full part retain the same number of intervals with largest right endpoints, with an analogous final partial part. The extra d prefix intervals compensate for the only partially started suffix part to the left of the anchor, while largest-right-endpoint replacement cannot reduce coverage to the right. There are O(1/ε)O(1/ ) parts, and enumerating d, the prefix, part boundaries, and final quota yields SO(1/ε)S^O(1/ ) candidates. This proves (S.32) without ever replacing a primitive by one of another price class. G.2 One-class paths and once-only charging Make a node (I,R)(I,R) for every anchor and representative from its family. Connect two real nodes only when their anchor intervals are disjoint and ordered. A path therefore has ordered anchors. Assign an edge from node v to node w the coverage proxy cRv∪Rwc_R_v∪ R_w on the slab between the anchor endpoints and cardinality charge |Rw∖Rv||R_w R_v|. If a physical interval appears at two path nodes, it spans both anchor endpoints and hence contains every intermediate anchor. It belongs to every intermediate compulsory set and representative. Membership is consecutive: an interval cannot disappear and later reappear. Consequently edge charges sum exactly to the cardinality of the union, with every physical primitive charged once. For an arbitrary comparison set in this price class, close it upward under containment (cost is unchanged inside the class). Greedily choose disjoint minimal anchor intervals. Every comparison interval contains at least one retained anchor endpoint. At each anchor choose the representative guaranteed by (S.32). Consecutive representatives have exactly the same intersection as their comparison-anchor sets: an interval from the first representative reaching the next anchor must contain it and is compulsory there; pointwise dominance forces equality of intersection cardinalities. Thus unions of adjacent representatives dominate comparison coverage on each slab. Consecutive membership also gives |⋃iRi|−|Jh|=∑i(|Ri|−|Mi|)≤ε∑i|Mi∖Ci|≤ε|Jh|, | _iR_i |-|J_h|= _i(|R_i|-|M_i|)≤ _i|M_i C_i|≤ |J_h|, because a comparison interval can be noncompulsory only at its first retained anchor. Hence the canonical path dominates the comparison coverage with (1+ε)(1+ ) class-count inflation. G.3 Synchronizing price classes The nonlinear BtB_t depend on total coverage, so class objectives cannot be optimized independently. Take the synchronized product of the c local path graphs. A product state holds one active edge per class and the exact vector r=(r1,…,rc)r=(r_1,…,r_c) of accumulated first-appearance charges. Over the common slab of the active edges, score W(e1,…,ec)=∑zt in slabBt(∑h=1cpeh(zt)).W(e_1,…,e_c)= _z_t in slabB_t\! ( _h=1^cp_e_h(z_t) ). Advance the class whose next anchor endpoint occurs first. Auxiliary endpoints are made distinct, so the product is acyclic. Consecutive membership makes rhr_h exactly the number of physical primitives from class h in the path union; no hidden union history is needed in the state. For an arbitrary product path, each slab proxy is coverage by a subset of its final union, so monotonicity of BtB_t implies product reward no greater than the actual F value of that union. For an arbitrary comparison set J, apply the canonical construction in each price class. The synchronized canonical product dominates total comparison coverage on every marker, and its class counts obey rh≤(1+ε)|J∩Vh|.r_h≤(1+ )|J∩ V_h|. For each final count vector retain the maximum-reward product path. At the canonical vector its retained path has reward at least the comparison reward, and its physical union has actual F at least its product reward. Therefore one returned menu item dominates J and obeys (S.35). There are at most ∏h(|Vh|+1)≤(S+1)c _h(|V_h|+1)≤(S+1)^c terminal count vectors. Each local graph has SO(1/ε)S^O(1/ ) size, so the synchronized dynamic program has bit complexity (S+1)O(c/ε)poly(m,L),(S+1)^O(c/ )poly(m,L), where L is total rational input encoding length. G.4 Spectral endpoints and full certificate For upper endpoint queries, cell coverage removes exceedances and the exact gain is U(∅)−U(Q)=∑tΔt[G(bt)−G(bt−cQ(t))],U( )-U(Q)= _t _t[G(b_t)-G(b_t-c_Q(t))], a sum of nonnegative nondecreasing functions of coverage. For lower endpoint queries, L(Q)−L(∅)=∑tΔt[G(at+cQ(t))−G(at)],L(Q)-L( )= _t _t[G(a_t+c_Q(t))-G(a_t)], which has the same property. Thus the menu theorem applies independently to selected upper and excluded lower rows. If query class h has price php_h, (S.35) gives C(R)=∑hphrh≤(1+ε)C(J).C(R)= _hp_hr_h≤(1+ )C(J). Let J⋆J be an exact optimum certificate. Replace every selected row by an upper-menu item with no larger upper key and every excluded row by a lower-menu item with no smaller lower key. The original lexicographic separator is preserved, while each row price grows by at most 1+ε1+ . The maximum selected replacement key is one of the scanned menu cuts. Therefore the algorithm considers a valid exact-decision certificate of price at most (1+ε)Ccert⋆(1+ )C_cert . Its output is itself a valid certificate, so Ccert⋆≤Calg≤(1+ε)Ccert⋆. C_cert ≤ C_ alg≤(1+ )C_cert . For fixed c this is a PTAS. The exponent depends on both c and 1/ε1/ , so the joint parameterization is XP, not FPT, and the scheme is neither an EPTAS nor an FPTAS. In the unit-cost special case, integrality also implies Calg=Ccert⋆C_ alg=C_cert whenever εCcert⋆<1 C_cert <1; choosing ε at this scale makes the exponent depend on Ccert⋆C_cert and gives at most an XP-style exact parameterization, not an FPT upgrade. Zero-price physical primitives are outside the theorem statement; they can be revealed for free before applying the positive-price theorem. Appendix H Online versus hindsight information The PTAS is a hindsight optimizer. A one-hot closed-box family separates it from zero-error online acquisition. Take n unresolved coordinates with box [0,2/λ1]n[0,2/ _1]^n and compare the unknown row with a known risk-one row. The all-zero realization and any single-hot realization have different winners. On a fixed hot realization, querying the hot coordinate alone certifies, so Ccert⋆=1C_cert =1. For a deterministic zero-error policy, consider its query order under all-zero responses and put the hot coordinate at the last location. Until that query, the transcript remains compatible with both decisions, so the policy uses all n queries on that fixed hot realization. For a randomized zero-error policy, for each realization of its random bits the average rank of the hot coordinate over the n possible locations is (n+1)/2(n+1)/2. Averaging first over locations and then randomness implies some fixed hot location has expected query cost at least (n+1)/2(n+1)/2. This is the standard closed-interval search obstruction; it is reported as a boundary, not as novelty of the queryable-uncertainty model. Appendix I Reproducibility and denominator specification I.1 Quadratic screening The quadratic tasks are controlled stress tests of the certificate and of the exact fallback; they use the non-predictive schedulers and are not compared with Ccert⋆C_cert . The principal matched tasks use m=12m=12 candidates, S=64S=64 scenarios, k=3k=3, ES tail mass 1.61.6, initial geometry rank 22, and exact-query batches of 3232. Each regime is one fixed instance. The fixed constructions are: Regime seed curvature decision margin tail density shared-leg reuse Benign 1101 0.20 1.00 0.10 0.60 Small margin 1701 0.20 0.03 0.25 0.75 High curvature 1401 1.50 0.75 0.20 0.60 The paid unit is one distinct candidate–scenario primitive query after structural reuse. The exhaustive denominators are 4480 on benign/high curvature and 4224 on small margin: they count the distinct priced primitives of the full-exact reference (70 per scenario on benign), not mSmS. On the benign task CAS-CI uses 125 queries (CAS-W 99, CAS-F 128). Candidate-only and scenario-only were run on benign and small-margin tasks. High curvature compares the three CAS-W, CAS-F and CAS-CI schedulers only against the exhaustive denominator; no missing one-sided baseline is imputed there. CAS-W (width) selects the unresolved row with largest ES-width potential and executes a geometric width-reduction epoch. The CAS-F (frontier) scores primitives by certified interval width, notional influence, liquidity/tail weight, and distance to the current kkth frontier. CAS-CI (certificate impact) caps the same influence proxy by the nearer candidate-specific accept/reject decision gap. These scores only order acquisitions; the interval certificate alone authorizes acceptance or rejection. PCA and randomized SVD construct low-rank scenario projectors. Their explained-variance or reconstruction score is never a stopping authority; the projector is passed to the same deterministic quadratic interval construction and exact certificate. For a quadratic response f(x)=c+g⊤x+12x⊤Hxf(x)=c+g x+ 12x Hx, let z=Pxz=Px and e=x−ze=x-z. The exact identity f(z+e)−f(z)=g⊤e+z⊤He+12e⊤Hef(z+e)-f(z)=g e+z He+ 12e He is enclosed by directed arithmetic, Cauchy–Schwarz, and the symmetric row-sum bound ‖H‖2≤max∑ji|Hij|\|H\|_2≤ _i _j|H_ij|. Hence the projector changes the center/radius of a deterministic interval but never changes certificate authority. Randomized SVD uses a fixed seed, ten oversamples, and four power iterations. A zero-query cell means the initial certified intervals induced by that geometry already separate the exact decision. The PCA counterexample cited in the main text is a small hand-built instance (four scenarios, two candidates, top-1) in which uncentered rank-one PCA retains 100/100.01=99.990001%100/100.01=99.990001\% of variance and the selected candidate has regret 5. 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. I.2 Predictive Merton baselines The predictive comparison uses m=12m=12, S=64S=64, k=3k=3 and benign, Student-t heavy-tail, and OOD-hedge evaluation regimes. Two deterministic training tasks use seed offsets 10001 and 20002 from regimes distinct from the evaluation regime; evaluation portfolio seed, regime, and OOD hedge family are held out. XGBoost uses 32 trees of depth 3. The MLP has one 16-unit hidden layer and maximum 2000 iterations. The predictive methods have no certificate authority. The plotted regret is ∑j∈Dpredρj−∑j∈Dexactρj, _j∈ D_ pred _j- _j∈ D_ exact _j, so it is measured in the same aggregate spectral-risk score units as the objective. I.3 Spectral compression The recorded primary compression population has 2080 rows plus 360 positive controls. Kdec♯K_ dec is the smallest band count certified by the specified enhanced correction/partition procedure, not an information- theoretic dimension. At S=128S=128, a memory-pressure safeguard interrupted computation: primary-world coverage is 62.5% for the geometric family, 37.5% for the linear/Gini-like family, and 0% for the irregular family. No S=128S=128 irregular-family statistic is imputed. At relative width r=1/2r=1/2, the observed median absolute Kdec♯K_ dec is 2 for the geometric family at S=32,64,128S=32,64,128, 1 for the linear/Gini-like family at all three observed sizes, and 1 for the irregular family at S=32,64S=32,64. The median ratio Kdec♯/SK_ dec /S is 1/64≈1.6%1/64≈ 1.6\% at S=64S=64 and S=128S=128 and 1/32≈3.1%1/32≈ 3.1\% at S=32S=32 and pooled over the computed population. The matched K=2K=2 ablation uses the same 200 cells (a fixed prefix of the world groups, not a random sample) for all four rules and yields certification rates 0.35,0.26,0.26,0.730.35,0.26,0.26,0.73 for uniform-rank, equal-spectral-mass, spectrum-only chord/minimax, and candidate-aware segmentation. I.4 Energy Before using the point-query certificate comparator, the native energy adapter passes five model-equivalence checks: (G1) one first-time action–scenario query triggers exactly one private recourse solve and repeated queries are memoized; (G2) the paid response equals an independently recomputed exact finite-horizon battery DP value; (G3) public lower/upper bounds are computed without consulting the hidden paid response; (G4) each paid primitive carries one unit of solve cost; and (G5) full revelation under the native oracle gives the same ID-resolved spectral-risk schedule as direct exact evaluation. The gate is what authorizes the clean point-query interpretation for this domain. The scale grid has A∈8,16,32A∈\8,16,32\ actions, S∈32,64,128S∈\32,64,128\ scenarios, k∈1,2k∈\1,2\, and eight seeds, giving 144 avoidance-only rows. A separately attempted scale-grid exact-ratio computation timed out and carries no computed decision/certificate fields; it is not included in the 144-row avoidance statistic. One paid primitive is one exact action–scenario battery-recourse dynamic-program solve, so the exhaustive denominator is Nsolve=AS.N_ solve=AS. Summed over the 144 cells, 93.0%93.0\% of these exact solves are avoided (1−∑Q/∑AS=0.93041-Σ Q/Σ AS=0.9304). The median cell avoids 92.9%92.9\% (0.92870.9287), the mean cell 91.2%91.2\%, and the worst cell 71.0%71.0\%; the nine (A,S)(A,S) family medians lie between 82.8%82.8\% and 96.0%96.0\%. These figures are not total runtime and exclude public-bound computation. The risk functional is empirical ES over the worst third of scenarios (tail mass S/3S/3, fractional on this grid). The upper public bound is the no-battery cost and the lower bound a per-step relaxation that ignores stock coupling; instances are synthetic with horizon 4. The acquisition rule is the non-predictive scheduler CAS-PD of Appendix C; CAS-PG was not run on this domain. Exact Ccert⋆C_cert and PTAS ratios are reported only on four separate S=16S=16 cells. On those cells CAS-PD uses between 2 and 11 times the hindsight certificate optimum (8/4, 29/12, 11/1, 8/1), so the avoidance result is not described as near-optimal online acquisition. I.5 Finance The finance grid crosses scenario counts S∈32,64,128S∈\32,64,128\ with candidate counts 12,24,4812,24,48. It uses shared primitives and interval-valued certified pricing, not information-disjoint point queries. Its 2.80×2.80×, 7.60×7.60×, and 17.20×17.20× ratios are naive per-package shock evaluations divided by distinct shared leg–scenario primitives for 12, 24, and 48 candidate packages. They measure workload sharing/cache opportunity and are not attributed to decision certification. The 3.00×3.00× fresh-pricer-call ratio is a separate cross-cell cache experiment comparing one cache shared across the three candidate-count cells at fixed scenario count with three independent caches. Repeated cold-cell timing was run on three scaled cells and establishes no speedup there (lower 95% bounds of the paired ratio 0.9610.961–0.9730.973); a fourth, smaller anchor cell from an earlier grid shows a marginal ratio of 1.0541.054 (95% interval 1.00041.0004–1.1301.130). The certified path evaluates all shared primitives on this workload, so there is no certification saving to report. The finance result is therefore exact fail-closed compatibility plus shared-work accounting, not a method-specific latency gain. Appendix J Certified nonlinear Merton enclosure Use ν for jump intensity and S0S_0 for spot. With log-jump mean μJ _J, variance δJ2 _J^2, mJ=μJ+δJ2/2m_J= _J+ _J^2/2, and κ=emJ−1κ=e^m_J-1, define pn=e−νT(νT)n!,An=e−(q+νκ)T+nmJ,B=Xe−rT,p_n=e^-ν T (ν T)^nn!, A_n=e^-(q+νκ)T+nm_J, B=Xe^-rT, hn=σ2T+nδJ2,zn=log(AnS0/B)hn+hn2.h_n= σ^2T+n _J^2, z_n= (A_nS_0/B)h_n+ h_n2. Merton’s European call mixture is C(S0,σ)=∑n≥0pn[AnS0Φ(zn)−BΦ(zn−hn)].C(S_0,σ)= _n≥ 0p_n [A_nS_0 (z_n)-B (z_n-h_n) ]. On the supported compact spot/volatility shock rectangle, the certified adapter evaluates a second-order Taylor polynomial and adds the Lagrange cubic remainder using uniform suprema of all third mixed derivatives. If F(h)F(h) is a mixture term after the volatility reparameterization, the third chain rule is Cσσσ=Fhhh(h′)3+3Fhhh′h′+Fhh′.C_σ=F_h(h )^3+3F_hh h +F_hh . The infinite mixture is truncated with a certified tilted-Poisson tail allowance; elementary and special-function evaluations are enclosed by outward-rounded interval arithmetic. These conditions imply the returned interval contains the exact shocked price on the declared domain. Unsupported conditions fail closed to direct certified pricing/refinement. This interval oracle is deliberately not identified with the exact point-query oracle used by the certificate PTAS. Appendix K Claim boundary summary • CAS-PG is exact for every predictor (Proposition C.1) and has no cost guarantee beyond [Ccert⋆,mS][C_cert ,mS]. Its measured cost is reported on two public tasks with one deterministic run each; the 1.141.14 and 1.181.18 multiples use uncharged historical outcomes on other instances and the 1.281.28 and 1.371.37 multiples do not. No algorithm-selection performance claim is made. • The energy, quadratic and finance studies use non-predictive acquisition; their work reductions are properties of the certificate layer. • The unrestricted coherent-spectral upper frontier and unrestricted full verifier remain open; no spectral NP-hardness or parameterized hardness result is claimed. • Kdec♯K_ dec is a procedure-relative certified degree. The compression study demonstrates small degrees on its computed population; it does not establish generic runtime acceleration from coarsening. • The few-price-class PTAS is hindsight-only, assumes information-disjoint exact point queries, and requires fixed positive price-class count. • Domain experiments establish exact decisions and stated work-count reductions under their own denominators. They do not transfer theorem complexity guarantees across information models.