📊 statistics

More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD)

This paper introduces Reset-and-Discard (ReD), a query strategy that optimizes the coverage of unique questions solved by large language models within a fixed budget by mitigating the diminishing returns of traditional pass@k sampling through power-law-based allocation.

Original authors: Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sagi Meir, Tommer D. Keidar, Noam Levi, Shlomi Reuveni, Barak Hirshberg

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Guessing Game" Problem

Imagine you have a large bag of riddles (questions) and a limited amount of money to buy guesses (attempts) from a smart but sometimes stubborn friend (a Large Language Model or LLM). Your goal isn't just to solve one really hard riddle; your goal is to solve as many different riddles as possible before you run out of money.

The paper addresses a common mistake people make when playing this game.

The Old Way: "The Stubborn Gambler" (Solve-to-Completion)

Currently, most people use a strategy the authors call "Solve-to-Completion."

How it works: You pick Riddle #1. You ask your friend for an answer. If they get it wrong, you ask again. And again. And again. You keep asking Riddle #1 until they finally get it right. Only then do you move on to Riddle #2.
The Problem: Some riddles are just really, really hard. Your friend might get stuck on Riddle #1 for 50 attempts. By the time they finally solve it, you've spent 50 guesses. You have zero guesses left for Riddles #2 through #100. You solved one hard thing, but you missed out on 99 easy things.
The Result: As you spend more money, the number of new riddles you solve grows slower and slower. It's like trying to fill a bucket with a leaky hose; the harder you push, the less water actually gets in.

The New Way: "The Breadth-First Explorer" (Reset-and-Discard / ReD)

The authors propose a new strategy called Reset-and-Discard (ReD).

How it works:
1. You pick Riddle #1 and ask your friend once.
2. If they get it right, you celebrate, throw the riddle away (Discard), and move to Riddle #2.
3. If they get it wrong, you don't keep asking. You immediately stop, throw that riddle aside for now, and move to Riddle #2.
4. You go through the whole list of riddles, asking each one exactly once (or a few times).
5. Once you've gone through the whole list, you go back to the top and try the ones that were still unsolved.
The Analogy: Imagine you are a firefighter trying to put out many small fires. Instead of standing in front of one stubborn fire and spraying water on it until it's out (ignoring the other fires spreading nearby), you spray a little water on every fire. If a fire goes out, you leave it alone. If it's still burning, you come back to it later.
The Result: You solve a huge number of riddles very quickly. Even if you don't solve the hardest ones immediately, you solve all the easy and medium ones first. This gives you a much better "bang for your buck."

The Science Behind the Magic

The paper uses math to prove why this works so well.

The Power Law: The authors noticed that for these AI models, the chance of solving a problem drops off in a specific mathematical pattern (a "power law"). Basically, the harder the problem, the exponentially harder it gets to solve.
The "Diminishing Returns" Trap: Under the old "Stubborn Gambler" method, this math means that as you spend more money, you get fewer and fewer new solved problems.
The Fix: The "Reset-and-Discard" method breaks this trap. The math shows that by resetting after every attempt (or a few), you turn that slow, diminishing growth into steady, linear growth. You get a constant stream of solved problems no matter how many attempts you make.

Key Findings from the Experiments

The authors tested this on real AI models (like Llama and GPT) using three types of challenges:

Coding: Writing computer programs.
Math: Solving math word problems.
Reasoning: Answering complex multiple-choice questions.

What they found:

More Solutions: With the same amount of money (budget), ReD solved significantly more unique problems than the old method.
Cheaper: To reach a specific goal (like solving 80% of the problems), ReD required fewer attempts, fewer computer tokens, and less actual cash.
Works with Imperfect Checkers: Even if the system checking the answers makes mistakes (sometimes saying "wrong" when it's right, or vice versa), ReD still wins.
Predicting the Future: The authors also showed that by using ReD, you can actually figure out how smart the AI is (its "power-law exponent") without having to run thousands of expensive tests. It's like being able to guess the speed of a car just by watching it drive for a few seconds, rather than timing a full race.

The Bottom Line

If you have a fixed budget to get an AI to solve a list of problems, don't keep hammering on the hard ones. Instead, try every problem once, discard the ones you solved, and circle back to the ones you missed. This "Reset-and-Discard" strategy lets you solve far more problems for the same price, turning a slow, frustrating process into an efficient, high-speed machine.

Technical Summary: Reset and Discard (ReD) for LLM Inference

Problem Statement

Large Language Models (LLMs) are increasingly evaluated on verifiable tasks (e.g., coding, mathematics, formal proofs) using the pass@k metric, which measures the probability of solving a single instance correctly within $k$ attempts. Empirical observations indicate that for many tasks, the failure rate ( $1 - \text{pass@k}$ ) decays as a power law with respect to $k$ (i.e., $1 - \text{pass@k} \propto k^{-\alpha}$ ).

However, in practical inference scenarios with a fixed global budget (measured in attempts, tokens, or USD), the relevant objective is not the success rate on a single problem, but the coverage@cost: the expected number of unique problems solved given a total resource constraint. The standard allocation policy, solve-to-completion (repeatedly sampling a single problem until solved before moving to the next), is inefficient under power-law difficulty distributions. Because hard problems consume a disproportionate number of attempts, this policy leads to sublinear growth in coverage@cost when the power-law exponent $\alpha < 1$ (a common empirical finding). This results in diminishing returns, where additional budget yields fewer solved problems.

Methodology: Reset-and-Discard (ReD)

The authors propose Reset-and-Discard (ReD), an allocation policy that optimizes global throughput by treating the inference process as a breadth-first search across a problem set.

The ReD Protocol

Reset: Instead of persisting on a single problem until solved, the system attempts each problem for a fixed number of trials $\tau$ (in the optimal case, $\tau=1$ , i.e., every attempt).
Discard: If a problem is solved within $\tau$ attempts, it is immediately removed from the queue.
Rotation: If a problem is not solved after $\tau$ attempts, it is moved to the back of the queue, and the system immediately proceeds to the next available problem.

Theoretical Framework

The paper establishes a mathematical mapping between pass@k and coverage@cost using renewal theory.

Standard Policy: For a difficulty distribution where $P(p) \sim p^{\alpha-1}$ (leading to power-law pass@k), the expected number of attempts to solve a problem, $E[T]$ , diverges if $\alpha < 1$ . Consequently, coverage@cost grows sublinearly ( $\propto t^\alpha$ ).
ReD Policy: By resetting every $\tau$ $τ$ attempts, the effective number of attempts to solve a problem, $E[T_\tau]$ $E [T_{τ}]$ , becomes finite regardless of the underlying difficulty distribution.
- If $0 < \alpha < 1$ , ReD transforms the growth of coverage@cost from sublinear to linear ( $\propto t$ ).
- If $\alpha > 1$ , ReD maintains linear growth but with a steeper slope (higher efficiency) than the standard policy.
Optimality: The authors prove that resetting every attempt ( $\tau=1$ ) is the optimal strategy to minimize the expected number of attempts per solved problem for any difficulty distribution. This holds even with imperfect verifiers, provided the sum of False Negative and False Positive rates is less than 1.

Inference of Scaling Laws

The paper also demonstrates that ReD trajectories can be used to infer the power-law exponent $\alpha$ without requiring expensive large- $k$ evaluations. As ReD proceeds through rounds, the distribution of remaining unsolved problems converges to a Beta distribution. By analyzing the ratio of remaining problems between rounds, $\langle R_n \rangle / \langle R_{n+1} - R_n \rangle$ , one can linearly estimate $\alpha$ .

Key Contributions

Metric Connection: Derived an exact mapping from pass@k to coverage@cost, characterizing how power-law pass@k behavior ( $0 < \alpha < 1$ ) induces sublinear growth in standard allocation schemes.
ReD Algorithm: Proposed and proved the optimality of the Reset-and-Discard strategy. It guarantees linear growth in coverage@cost for $\alpha < 1$ and improves efficiency for $\alpha > 1$ .
Theoretical Guarantees: Proved that ReD strictly maximizes expected reward per attempt for any difficulty distribution and remains robust against verifier noise.
Exponent Inference: Developed a method to estimate inference scaling exponents directly from ReD runs, bypassing the need for costly large- $k$ sampling.
Empirical Validation: Demonstrated substantial improvements across three LLMs (Llama-3.1-8b, Llama-3.3-70b, GPT-oss-20b) and three benchmarks (HumanEval, GSM8K, MMLU-Pro).

Experimental Results

Experiments were conducted on the HumanEval dataset (coding), GSM8K (math), and MMLU-Pro (reasoning).

Efficiency: ReD significantly reduced the number of attempts, tokens, and USD cost required to reach a target coverage compared to solve-to-completion.
Model Comparison: On the HumanEval benchmark, ReD applied to a smaller model (Llama-3.1-8b) outperformed the standard allocation of a much larger model (Llama-3.3-70b) in terms of attempts and tokens up to ~90% coverage. In terms of USD cost, ReD on the 8b model was the most cost-effective strategy across all coverage levels.
Scaling Law Inference: Using ReD on the 8b model, the authors successfully inferred a power-law exponent of $\alpha \approx 0.34$ , which matched the exponent derived from high- $k$ pass@k measurements.
Robustness: The advantage of ReD was maintained even when simulating noisy verifiers.

Significance and Claims

The paper claims that ReD offers a fundamental shift in how inference compute is allocated for verifiable tasks.

From "Pay-per-Token" to "Outcome-as-a-Service": ReD allows systems to focus compute resources on the "frontier of learnability" (problems that are solvable within a few attempts) rather than wasting resources on hard instances that require diminishing returns.
Hierarchical Routing: The methodology supports efficient hybrid strategies where small models handle the bulk of problems via ReD, and only unsolved problems are routed to larger, more expensive models.
General Applicability: The approach is applicable to any pipeline supporting repeated sampling and verification, providing a provable improvement in throughput without requiring changes to the model architecture or training.

The authors maintain modesty regarding scope, noting that ReD is designed specifically for verifiable tasks where solution correctness can be automatically assessed. They do not claim applicability to non-verifiable generation tasks or propose integration with learned difficulty predictors as part of this work.