Two literatures, one problem, no citations between them

In 2024, Zhou et al. published "On Speeding Up Language Model Evaluation" (ICLR 2025): treat the cells of an LLM evaluation grid as bandit arms, sequentially pick promising method-example pairs, fill in the rest with low-rank matrix factorization, and identify the top-performing method "using only 5-15% of the typical resources," an 85-95% cost saving.1 In 2026, a second, independent group published SySRs, a Successive-Rejects-style elimination bandit that identifies the best model on all fifteen benchmarks tested using at most 35% of the model/test-point pairs.2 That 35% is the paper's worst case, so it implies roughly a 65% floor on savings, not a cap. The two figures belong to two different papers and should never be blended into one range.

So: adaptive bandit pruning of an LLM evaluation grid under a cost cap is a published idea, twice over, by groups who did it before we thought about it.

One more piece of prior art worth naming explicitly, because it is the objection a reader will reach for first: this isn't LLM routing. RouteLLM3 and FrugalGPT4 also allocate spend across models under a budget, but they make a per-production-query serving decision at inference time: which model answers this request. Eval-grid pruning makes an evaluation-budget allocation decision across a fixed grid of (model, task, effort) cells before anything ships. The overlap review behind this post examined that distinction directly; it is why bandit pruning for evals and LLM routing are adjacent problems rather than the same problem under different names.

Budgeted multi-armed bandits were not an analogy imported into ad-tech. They are ad allocation's home turf. A quick tour of the canon. Slivkins (2013) poses pay-per-click ad allocation directly as a bandit problem where each ad has an uncertain click probability and a spending limit, and gives a UCB-style algorithm with performance guarantees for that budgeted setting.5 Combes, Jiang and Srikant (SIGMETRICS 2015) prove regret lower bounds for the budgeted setting and show 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, proving a distribution-dependent regret bound of O(ln B), where B is the budget, for Bernoulli bandits.7

For readers new to the vocabulary: a multi-armed bandit is the formal model of "try options, learn which pays, and balance exploring uncertain options against exploiting good ones." Regret is how much you lose 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 what "optimal" means.

That last clause is the whole reason ad-tech's version of this literature is worth an eval engineer's attention. An eval grid burns real dollars per cell, and different dollars per cell, since a frontier model at maximum reasoning effort costs orders of magnitude more than a small model at minimum. That is exactly the heterogeneous per-arm-cost, hard-budget regime the ad-allocation papers formalized, with pacing discipline (don't exhaust the budget before you've learned anything) as a first-class concern. The two directly-on-point eval papers use bespoke machinery instead: low-rank completion in Zhou et al., synchronized elimination in SySRs. Neither carries the classical budgeted-MAB regret guarantees for heterogeneous dollar costs.

Here is the striking part. A reference-list check of both eval papers, run while drafting this post, found no citation to Slivkins, to Combes/Jiang/Srikant, or to Xia et al.; their bandit lineage runs through the best-arm-identification literature (Audibert and Bubeck and successors) instead. The reverse direction cannot exist for timing reasons, so the checkable direction is the one that was checked.

Two research communities, a decade apart, converged on "budgeted bandit over a grid of costly options" without apparently reading each other. Convergence like this is suggestive that the formalism fits the problem, though it is also consistent with budgeted-bandit theory simply being the standard toolkit every one of these authors would have learned regardless of application. Treat it as suggestive, not dispositive. The practical takeaway is narrower and more useful: the older literature has already solved the single-best-arm regime, with hard per-arm budgets, pacing, and proven optimality when one arm dominates. It has not solved the harder, mixed-arm regime a heterogeneous eval grid actually sits in, which the next section addresses. Borrow the pacing discipline; don't borrow the optimality claim.

If this post has one warning to leave with you, it's this one. The favorable, logarithmic-regret results in the budgeted-bandit literature hold in narrow regimes: in the bandits-with-knapsacks formulation, essentially when one resource constrains you and the optimal policy is a single best arm. The moment the optimal policy must mix arms, playing different arms for different task types (the expected case for a heterogeneous eval grid, where different models win on different tasks), the lower bound degrades to Ω(√T). Sankararaman and Slivkins give the full characterization of when logarithmic, instance-dependent regret is achievable8; our internal research spike's reading is that a heterogeneous eval grid sits in the unfavorable regime as the typical case, not the exception.

Concrete arithmetic makes the point sharper. 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 notice it gives each (subject, model, effort) arm at most 260 observations in a full exhaustive sweep. A few hundred observations per arm is enough for a bandit to prune obviously dominated arms early. It is nowhere near enough to certify a near-optimal mixture under an Ω(√T) bound. Our research scopes any implementation accordingly: adaptive cell pruning under a spend cap, not a converged optimal allocator. Any vendor or blog post promising the latter on eval-sized data is over-claiming, and now you know the theorem to cite back at them.

Adoption also has a real build cost that neither eval paper dwells on. A bandit consumer replaces a static enumerate-then-run loop with an adaptive select-execute-update loop, and it needs a persistent spend ledger across invocations, a primitive the studied harness does not have today. And pruning inherits the auditability question our companion post on attribution raises about data-driven attribution: an early-eliminated arm is a cell someone may later ask you to justify never having measured. 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 choice, not a fallback.

Two adjacent approaches deserve a sentence so the map is honest. Static difficulty-based test-set filtering via item-response theory offers non-adaptive savings without the bandit machinery, reporting 44-70% in that setting9, and tinyBenchmarks compresses the example axis rather than the model-arm axis, so it composes with arm pruning rather than competing against it.10

Our overlap review returned a clear verdict: the core mechanism is already published, with high confidence. What survives for a team building this is modest and worth stating at exactly that size. Treating reasoning-effort level as its own explicit bandit axis, jointly with model choice, rather than folding configuration into an opaque method id, is a real but modest structural difference from the published setups: bookkeeping, not an algorithm. And reaching for the classical budgeted-MAB family (B-KL-UCB, budgeted Thompson sampling), with proven regret bounds for heterogeneous per-arm dollar costs, instead of bespoke methods, is a defensible algorithm choice. An engineering-adoption note, not a new problem formulation.

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 resources; SySRs reports a worst case of 35% of pairs. Run the arithmetic on your own grid before believing either number transfers.

• Scope the promise. Write "adaptive cell pruning under a spend cap" into the design doc, and strike any sentence that says "optimal allocation." The Ω(√T) regime is the expected case for a mixed grid.

• Check the prerequisites. A persistent spend ledger and an audit story for skipped cells come before the algorithm. If your reviewers need every cell measured, stop here and sweep exhaustively.

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