Two literatures, one problem, and a theorem that bounds the promise

In 2024, Zhou et al. published "On Speeding Up Language Model Evaluation," accepted at ICLR 2025.1 The method treats the cells of an evaluation grid, meaning method-example pairs, as arms in a multi-armed bandit, sequentially selects promising pairs to actually run, and fills in unobserved cells with low-rank matrix factorization. The headline result: the top-performing method can be identified "using only 5-15% of the typical resources," an 85-95% cost saving against an exhaustive sweep.

In 2026 a second, independent group published SySRs (Synchronized Successive Rejects), a best-arm-identification bandit that provably exploits similarity between models to eliminate weak candidates early.2 Its verifiable result: the best model is reliably identified on all fifteen benchmarks tested using at most 35% of the model/test-point pairs. Note the direction of that bound. Thirty-five percent is the paper's worst case across benchmarks, so it implies savings of at least roughly 65%, a floor rather than a cap. And note that the two papers' figures are not interchangeable: 85-95% belongs to Zhou et al., the roughly-65%-plus floor belongs to SySRs, and blending them into a single range (an error that appeared in our own early working notes before verification caught it) misdescribes both.

So the mechanism is published, twice, by groups who got there first. The framing law for this entire series follows: what remains is an intellectual-history observation and an engineering-adoption argument, not a novelty claim.

The objection a well-read practitioner reaches for first: doesn't the routing literature already cover budget-aware model selection? RouteLLM trains a router on preference data to choose between a strong and a weak model per query3; FrugalGPT cascades queries through models of increasing cost until an answer clears a quality bar.4 Both allocate spend across models under a budget, and both are sometimes cited as if they settle the eval-efficiency question.

They are adjacent, not identical, and the distinction is the decision being made. Routing makes a per-production-query serving decision at inference time: which model answers this request, for this user, right now. Eval-grid pruning makes an evaluation-budget allocation decision across a fixed Cartesian grid of (model, task, effort) cells, before anything ships, with the goal of characterizing the grid rather than serving the query. The overlap review behind this series examined that distinction directly and it held. The two problems share a budget and a set of models; they differ in decision object, timing, and success criterion. Conflating them leads to importing serving-layer solutions into a measurement problem, which is precisely the category of confusion this series exists to name.

Budgeted multi-armed bandits were not an analogy imported into advertising. They are ad allocation's home turf, and the canon is worth reading in its own words. For readers new to the vocabulary: a multi-armed bandit is the formal model of sequential decision-making under uncertainty. Try options, learn which pays, balance exploration of uncertain options against exploitation of known-good ones. Regret is the cumulative loss relative to always having played the best option. A budgeted bandit adds the constraint that pulls cost money and the money runs out, which changes both the algorithms and the meaning of "optimal."

Slivkins (2013) poses pay-per-click ad allocation directly as a budgeted bandit: each ad has an uncertain click probability and a spending limit, one ad is selected per round, and the paper develops a UCB-style algorithm with performance guarantees for that setting.5 Combes, Jiang and Srikant (SIGMETRICS 2015) supply the theory spine: regret lower bounds that apply to any uniformly good algorithm in the budgeted setting, and a proof that B-KL-UCB, a natural variant of KL-UCB, is asymptotically optimal for the cost-per-impression and cost-per-click models they study.6 Xia et al. (IJCAI 2015) extend Thompson sampling, the Bayesian workhorse of modern experimentation, to budgeted bandits, sampling posteriors over both reward and cost per arm and selecting on the ratio, with a proven distribution-dependent regret bound of O(ln B), where B is the budget, for Bernoulli bandits.7

Three properties of this literature matter for evals. First, heterogeneous per-arm dollar costs are native to the formulation: arms cost different, unknown-mean amounts, exactly like eval cells, where a frontier model at maximum reasoning effort costs orders of magnitude more per run than a small model at minimum. Second, pacing is a first-class concern: the algorithms are built not to exhaust the budget before learning. Third, the guarantees are proven, with matching lower bounds. The two directly-on-point eval papers use bespoke machinery instead (low-rank completion in Zhou et al., synchronized elimination in SySRs), and neither carries the classical budgeted-MAB regret guarantees for the heterogeneous-dollar-cost case. That is not a criticism of those papers; it is an open aisle in the library they did not visit.

A reference-list check of both eval papers, run during the drafting of this series and independently re-confirmed by a subsequent adversarial review pass against the live full texts, found no citation to Slivkins, to Combes, Jiang and Srikant, or to Xia et al.12 Their bandit lineage runs instead through the best-arm-identification literature: the re-check located "UCB-E (Audibert and Bubeck, 2010)" inside Zhou et al.'s references. The reverse direction cannot exist for timing reasons, so the checkable direction is the one that was checked. We state the method and its limits plainly: two independent reference-list reads of the arXiv full texts, high confidence, not an exhaustive bibliometric audit.

What does the convergence prove? Less than it is tempting to claim. It is suggestive that the budgeted-bandit formalism fits the problem (the same constraints reliably summon the same mathematics), but it is also consistent with a duller explanation: bandit theory is the standard toolkit every one of these authors would have learned regardless of application. Treat the convergence as suggestive, not dispositive. The practical payoff is narrower and more durable: the older literature has already worked out the single-best-arm regime, with hard per-arm budgets, pacing discipline, and proven optimality when one arm dominates. What it has not solved is the regime a heterogeneous eval grid actually sits in, and that boundary is the subject of the next section. Borrow the pacing discipline; do not borrow the optimality claim.

The favorable, logarithmic-regret results in the budgeted-bandit literature hold in narrow regimes. In the bandits-with-knapsacks formulation, they hold essentially when one resource constrains you and the optimal policy commits to a single best arm. Sankararaman and Slivkins' "Bandits with Knapsacks beyond the Worst-Case" gives the full characterization of when logarithmic, instance-dependent regret is achievable in that setting.8 Outside those conditions, in particular the moment the optimal policy must mix arms (playing different arms for different task types), the lower bound degrades to Ω(√T). If the grid sits in the arm-mixing regime (our reading from the internal research spike, attributed to the spike rather than to the paper's own wording), then the lower bound applies. For a heterogeneous eval grid where different models win on different task types, we read this as the typical case rather than the exception: the optimal allocation is a mixture.

Concrete arithmetic makes the boundary bite. The eval grid studied in this research (an internal multi-model agent-evaluation harness KellerAI builds and operates itself, not a third-party or client system) works out to 34,320 cells: 3 subjects × 260 tasks × 44 model-effort slots. That sounds enormous until you divide it the other way. At the (subject, model, effort) arm granularity the harness uses, a full exhaustive sweep gives each arm at most 260 observations, one per task. A few hundred observations per arm is enough for a bandit to prune obviously dominated arms early, which is where the published savings come from. It is nowhere near enough to certify a near-optimal mixture under an Ω(√T) lower bound.

Hence the scoping rule this series repeats until it sticks: adaptive cell pruning under a spend cap, never "optimal allocation." A design document that promises the former is describing something the published methods actually deliver.12 A vendor pitch that promises the latter on eval-sized data is over-claiming against a known lower bound, and now you know the theorem to cite back.8

Neither eval paper dwells on what adoption costs an engineering team, so we will. A bandit consumer replaces a static enumerate-then-run loop with an adaptive select-execute-update loop: the runner must consult allocation state before each pull and write results back after it. That state has to live somewhere durable, which surfaces the real prerequisite: a persistent spend ledger across invocations, tracking per-arm cost and reward. The harness studied in this research does not have one today, and in our assessment that primitive, not the algorithm, is the long-lead item for any team in the same position.

Pruning also inherits an auditability question, and it is the same one our companion paper on attribution raises about data-driven attribution: an early-eliminated arm is a cell somebody may later ask you to justify never having measured. "The bandit's confidence bound excluded it" is a true answer with the same shape as "the model decided": acceptable in some rooms, disqualifying in others. For small grids, cheap models, or audit regimes where a compliance reviewer needs every cell actually measured rather than algorithmically skipped, the exhaustive sweep is the correct engineering choice, not a fallback for teams that couldn't build the fancy thing.

The map should also include the approaches that sidestep bandits entirely. Static difficulty-based test-set filtering via item-response theory achieves non-adaptive savings (reported at 44-70% in that setting) with no allocation loop and no ledger, at the cost of adaptivity.9 And tinyBenchmarks compresses the example axis rather than the model-arm axis, selecting anchor examples that predict full-benchmark performance; it composes with arm-axis pruning rather than competing against it.10 A team could reasonably adopt the static filter first, the example compression second, and the bandit loop only when the remaining grid still exceeds the budget.

The overlap review behind this series returned its verdict with high confidence: the core mechanism is already published. Two things survive for a team building in this space, and both should be stated at exactly their size. First, treating reasoning-effort level as its own explicit bandit axis, jointly with model choice (a three-way composite arm of subject × model × effort rather than an opaque method identifier), is a real but modest structural difference from the published setups. It is bookkeeping that makes the cost-quality trade visible to the allocator; it is not a new algorithm. Second, reaching for the classical budgeted-MAB family (B-KL-UCB, budgeted Thompson sampling67), with proven regret bounds for heterogeneous per-arm dollar costs, rather than bespoke methods, is a defensible algorithm choice. A "different algorithm, same problem" engineering note, not a new problem formulation.

That is the honest ledger, and it is worth pausing on how it was enforced: the working notes behind this series originally contained a blended savings range and a title that claimed convergence on "the same algorithm." Verification against the primary sources corrected the figure, and the title now says what the evidence supports: the same budgeted-bandit problem, solved with different algorithms by each community.

If you're deciding whether to act on this:

• Size the prize per paper, not blended. Zhou et al. report needing 5-15% of typical resources1; SySRs reports a worst case of 35% of pairs.2 Run the arithmetic on your own grid (cells, per-cell dollar cost, observations per arm) before believing either number transfers.

• Scope the promise in writing. "Adaptive cell pruning under a spend cap" goes in the design doc; any sentence containing "optimal allocation" comes out. The Ω(√T) regime is the expected case for a mixed grid.8

• Sequence the prerequisites. Persistent spend ledger, audit story for skipped cells, then the algorithm. Consider the static IRT filter9 and example compression10 first; they may capture most of the savings with none of the loop.

• If your reviewers need every cell measured, sweep exhaustively and spend this paper's reading time elsewhere. That is a correct outcome, not a failure to adopt.

The mathematics belongs to two literatures that built it independently. The eval papers own the application; ad-tech owns the budget discipline; the regret theory owns the boundary of the possible. Sometimes the most useful thing a paper can tell you is that your problem was formalized twice, and exactly where to look up each treatment.