More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD)
Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg · 2026
Read More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD) by Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-21522.txt.
Introduction
Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, and Barak Hirshberg get more solved questions from a fixed budget of language model tries. The usual score counts a question as solved if any of many tries succeeds. With a fixed budget, a better score counts how many distinct questions get solved overall.
Their reset-and-discard method drops stalled attempts early and starts fresh ones. Wasted tries on one hopeless question can then fund progress on others. The metric they propose matches what users with real budgets care about. It rewards breadth of solved problems over deep grinding on a few.
Catalog record
| CREATOR | Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-21522
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD) Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg Abstract The performance of large language models (LLMs) on verifiable tasks is usually measured by pass@ k k , the probability of answering a question correctly at least once in k k trials. At a fixed budget, a more suitable metric is coverage@cost, the average number of unique questions answered as a function of the total number of attempts. We connect the two metrics and show that the empirically-observed power-law behavior in pass@ k k leads to a sublinear growth of the coverage@cost (diminishing returns). To solve this problem, we propose Reset-and-Discard (ReD), a query method of LLMs that increases coverage@cost for any given budget, regardless of the pass@ k k form. Moreover, given a pass@ k k , we can quantitatively predict the savings in the total number of attempts using ReD. If pass@ k k is not available for the model, ReD can infer its power-law exponent. Experiments on three LLMs using HumanEval demonstrate that ReD substantially reduces the required attempts, tokens, and USD cost to reach a desired coverage, while also offering an efficient way to measure inference power-laws. \declaretheorem [name=Theorem,numberlike=thm]thmR \declaretheorem [name=Lemma,numberlike=thm]lemR \declaretheorem [name=Corollary,numberlike=thm]corR 1 Introduction Generating multiple independent candidate solutions has become a standard way to improve the performance of LLMs on verifiable reasoning tasks such as coding, mathematics, and formal proof search. Across model families and benchmarks, this can yield striking gains: relatively small models can approach or even exceed the single-sample performance of larger models when allowed many attempts ( 12 ; 8 ; 55 ; 65 ) . These gains are typically reported via pass@ k : the probability that at least one out of k generations solves a single , randomly-chosen instance ( 35 ; 12 ; 24 ; 8 ; 31 ; 32 ; 10 ; 40 ; 53 ; 18 ; 39 ) . Recent work has uncovered a remarkably regular empirical pattern: for many tasks, 1-\text{pass@}k decays as a power-law in k across orders of magnitude ( 53 ; 40 ; 33 ) . In practice, inference compute is often shared across a workload: a batch evaluation with a fixed token cap, an automated code repair system that must address as many tickets as possible, or a service provider operating under latency and cost constraints. In these settings, the relevant objective is not \text{pass@}k , but how many distinct questions are solved under a fixed global budget. Yet, efficient allocation policies under a fixed budget across many tasks remain underexplored. To formalize this objective we adopt coverage@cost - the expected number of unique problems solved after spending a total budget (measured in attempts, tokens or USD). coverage@cost is a metric that rewards solving more problems rather than spending disproportionate compute on a small number of hard instances. Crucially, coverage@cost depends not only on the model, but also on the policy used to allocate attempts across problems. A common implicit allocation scheme is solve-to-completion : repeatedly sample a problem until it is solved, then move to the next. When per-problem success probabilities vary (difficulty distribution), this policy is difficulty-biased, since hard problems consume many attempts, reducing throughput for the overall workload. Under the empirically observed power-law \text{pass@}k behavior, 1-\text{pass@}k\propto k^{-\alpha} , commonly with 0<\alpha<1 , this effect can be extreme. In that case, we show that solve-to-completion yields sublinear coverage@cost growth, meaning that additional budget buys diminishing returns in the number of distinct solved problems. We propose an alternative allocation policy, Reset-and-Discard (ReD) : (1) Reset sampling to the next task in line, after a fixed number of attempts \tau (in the extreme, after every attempt), and (2) Discard problems as soon as they are solved so no further compute is spent on them. Intuitively, failures provide information: a problem that has already failed several times is more likely to be hard, so the expected marginal gain from another attempt is smaller than starting fresh on a new instance. ReD implements this “breadth-first” approach directly, and is straightforward to deploy in any pipeline that already supports repeated sampling and verification. Our work proves the following: (1) We connect \text{pass@}k to coverage@cost via renewal theory and derive expressions for coverage@cost as a function of the budget, given pass@ k . (2) We prove that resetting strictly improves coverage@cost for any budget and any underlying difficulty distribution, and that the optimal resetting protocol is ReD every attempt ( \tau=1 ). (3) Given an empirical or modeled \text{pass@}k curve, we can predict the budget savings induced by ReD to reach any target coverage; conversely, ReD trajectories provide a statistically efficient way to estimate inference power-law exponents when direct large- k \text{pass@}k measurement is impractical. We validate these results on multiple LLMs and the HumanEval benchmark ( 12 ) , demonstrating that ReD increases the number of distinct problems solved at fixed budgets, yielding large savings relative to solve-to-completion allocation. Our main contributions are: • We derive an exact mapping from \text{pass@}k to coverage@cost and characterize its growth under power-law \text{pass@}k . Namely, if the pass@ k scales as a power-law with exponent 0<\alpha<1 , as commonly empirically observed for LLMs, a standard, solve-to-completion scheme induces sublinear growth for coverage@cost. If, however, \alpha>1 , coverage@cost grows linearly. • We propose Reset-and-Discard (ReD) and prove that resetting improves coverage@cost at every budget and that ReD every attempt ( \tau=1 ) is the optimal resetting strategy . Concretely, if the pass@ k scales as a power-law with exponent 0<\alpha<1 , ReD induces linear growth for coverage@cost, and if \alpha>1 , its growth is linear with a larger slope than solve-to-completion. • We show how to predict attempts savings from \text{pass@}k , and how to estimate inference-scaling exponents from ReD runs when large- k evaluation is costly. • We empirically demonstrate that ReD leads to substantial throughput improvements on verifiable LLM coding benchmarks. The rest of the paper is structured as follows: In Section 3 , we define coverage@cost and provide its mapping from the pass@ k metric. In Section 4 , we derive our main theoretical results for coverage@cost under our proposed resetting policy (ReD), where the number of unique tasks is large. We also discuss the practical implementation of ReD on finite-sized datasets. In Section 5 , we show that the pass@ k scaling exponent can be inferred efficiently using ReD. Finally, we provide empirical verification of our results on LLM coding tasks in Section 6 , and conclude in Section 7 . 2 Related Work Test-time compute on verifiable tasks. Repeated sampling with automatic verification is a standard way to amplify LLM performance on coding tasks, mathematics, and formal proof search, commonly summarized by \text{pass@}k ( 12 ) . Recent work documents inference-time scaling of coverage/pass@ k over large sample budgets ( 8 ; 65 ) , and studies compute-optimal ways to allocate test-time compute within a prompt via search and verifiers ( 55 ) ; see also the survey of inference-time algorithms ( 63 ) . Inference-time scaling laws and forecasting large- k . Several works propose models that explain