Source-linked AI summary
Large Language Monkeys: Scaling Inference Compute with Repeated Sampling
Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoc V. Le, Christopher Ré, Azalia Mirhoseini
TL;DR
LLM inference is often restricted to one attempt despite the potential to scale computation at inference time. The paper studies repeated sampling of candidate solutions across tasks and models, finding that coverage scales with sample count and can substantially improve verified performance, while non-automatic verification methods plateau.
Problem
LLM use often limits problem solving to one attempt, leaving inference-time computation less systematically explored than training compute.
Method
The paper systematically evaluates repeated independent sampling across tasks, models, and sample budgets, using automatic or other verification methods to select answers.
Results
56% of SWE-bench Lite issues are solved by DeepSeek-Coder-V2-Instruct with 250 samples versus 15.9% with one sample, exceeding the 43% single-sample state-of-the-art.
Takeaways & Limitations
Repeated sampling can amplify weaker models and sometimes make them more cost-effective than fewer attempts from stronger models when correct samples can be identified.
Takeaways & Limitations
The experiments use independent attempts with the same prompt and hyperparameters, leaving refinements such as varying these choices for future work.
Abstract
from arXiv · showhide
Scaling the amount of compute used to train language models has dramatically improved their capabilities. However, when it comes to inference, we often limit models to making only one attempt at a problem. Here, we explore inference compute as another axis for scaling, using the simple technique of repeatedly sampling candidate solutions from a model. Across multiple tasks and models, we observe that coverage -- the fraction of problems that are solved by any generated sample -- scales with the number of samples over four orders of magnitude. Interestingly, the relationship between coverage and the number of samples is often log-linear and can be modelled with an exponentiated power law, suggesting the existence of inference-time scaling laws. In domains like coding and formal proofs, where answers can be automatically verified, these increases in coverage directly translate into improved performance. When we apply repeated sampling to SWE-bench Lite, the fraction of issues solved with DeepSeek-Coder-V2-Instruct increases from 15.9% with one sample to 56% with 250 samples, outperforming the single-sample state-of-the-art of 43%. In domains without automatic verifiers, we find that common methods for picking from a sample collection (majority voting and reward models) plateau beyond several hundred samples and fail to fully scale with the sample budget.
1 Introduction
Training-scale gains have outpaced investment in inference-time computation, where LLMs are often limited to one attempt. This work investigates repeated sampling as a simple way to scale inference compute and systematically characterize its benefits across tasks, models, and sample budgets.
- LLM capabilities have improved across coding, mathematics, and reasoning as training compute has scaled through larger models, longer pre-training, and larger datasets.
- Users and developers often restrict LLMs to one attempt, despite inference compute increasing with model size and prompting methods such as chain-of-thought producing longer outputs.
- Repeated sampling generates many independent candidate solutions at positive temperature and uses a domain-specific verifier, such as unit tests, to select a final answer.
- The paper explores repeated sampling to improve reasoning performance and characterize its benefits across tasks, models, and sample budgets.
- Coverage measures the fraction of problems solvable using any generated sample as the number of samples increases.
2. Precision: How often can we identify correct samples from our collection of generations?
Repeated sampling increases coverage and can improve performance or reduce inference costs, but realizing these gains requires verifiers that can identify correct samples. Without automatic verifiers, majority voting and reward models plateau as sample collections grow.
- Verification: Repeated sampling is useful only when correct samples can be identified, making scalable verification necessary as increasingly rare correct generations appear.
- Coverage: Coverage increases substantially with repeated sampling across math and coding tasks, reaching over 300x on CodeContests with Gemma-2B from 0.02% with one sample to 7.1% with 10,000 samples.
- Verified performance: 56% of SWE-bench Lite issues are solved by DeepSeek-Coder-V2-Instruct with 250 samples, compared with 15.9% using one sample and 43% for the single-sample state-of-the-art.
- Inference cost: Holding total inference FLOPs constant, some datasets favor smaller models with more samples, while others favor fewer samples from larger models.
- Inference cost: Sampling five times from DeepSeek-Coder-V2-Instruct solves more SWE-bench Lite issues than single samples from Claude or GPT while costing over 3x less.
- Verification: On MATH, coverage rises from 82.9% with 100 samples to 98.44% with 10,000, while majority voting or reward models improve only from 40.50% to 41.41%.
- Coverage: Coverage often follows an approximate exponentiated power law in the number of samples, producing nearly log-linear growth across several orders of magnitude.
2 Scaling Repeated Sampling
Repeated sampling scales inference compute by generating multiple candidates and evaluating whether any solves each problem. Across tasks and models, coverage generally rises with sample count, improving performance and sometimes reducing cost when verification is available.
- Evaluation framework: Coverage measures the fraction of problems solved by at least one generated sample, while success rate also depends on identifying correct samples.For coding and formal-proof tasks, automated verifiers can handle this identification step.
- Evaluation framework: The evaluation covers GSM8K, MATH, MiniF2F-MATH, CodeContests, and SWE-bench Lite, using answer checks, Lean4, test cases, or unit-test suites as appropriate.SWE-bench Lite problems require editing a repository file and can be checked with repository unit tests.
- Across tasks: 56% of SWE-bench Lite problems were solved with repeated sampling, compared with 43% for the single-attempt state of the art.The repeated-sampling setup used independently generated attempts with the Moatless Tools framework.
- Across model sizes and families: 7.1% pass@10k was achieved by Gemma-2B on CodeContests, up from 0.02% pass@1, an increase of over 300x.On MATH, Pythia-160M increased from 0.27% pass@1 to 57% pass@10k.
- Across model sizes and families: Coverage increases across almost every tested model, spanning 70M–70B parameters, Llama, Gemma, and Pythia families, and Base and Instruct models.The Pythia family achieved zero CodeContests coverage even with 10,000 samples.
- Performance and cost: The model maximizing coverage depends on task and compute budget: Llama-3-8B-Instruct is better on several fixed-FLOP tasks, while the 70B model is usually more cost-effective for CodeContests.FLOPs are a crude cost metric because batching and specialized optimizations affect throughput.
3 Characterizing the Benefits of Repeated Sampling
Coverage often follows an exponentiated power law as the sample budget grows, although the fit is imperfect for some task-model pairs. Models from the same family exhibit similarly shaped coverage curves with different horizontal offsets.
- Coverage can often be modelled with an exponentiated power law in the number of samples.The fit is not equally accurate for all curves, with MiniF2F-MATH providing a notable exception.
- 3.2 Similarities in Coverage Curves Across Models: Coverage curves for models from the same family resemble S-curves with similar slopes but distinct horizontal offsets.
- The fitted relationship provides early evidence that inference-scaling benefits can be characterized, though it is less exact than training scaling laws.
- 3.2 Similarities in Coverage Curves Across Models: After logarithmic horizontal alignment, within-family curves follow similar shapes and require approximately constant multiplicative sample-budget increases to improve coverage between fixed levels.The curves are shifted to pass through (1, c), where c is the maximum pass@1 score in the family.
4 Harnessing Repeated Sampling Requires Precision
Repeated sampling increases coverage, but exploiting that coverage requires reliable precision: verifiers must identify rare correct samples among many candidates. Common selection methods plateau, while evaluation datasets and test suites introduce additional verification constraints.
- 4.1 Common Verification Methods Don’t Always Scale with the Sample Budget: Success rates for majority voting and reward-model methods plateau around 100 samples, while coverage continues increasing and eventually exceeds 95%.Majority voting saturates because rare correct solutions do not change the most common answer.
- 4.1 Common Verification Methods Don’t Always Scale with the Sample Budget: Coverage acts as performance with an oracle verifier, whereas majority vote, reward-model best-of-N, and reward-model weighted voting attempt to identify correct samples.
- 4.1 Common Verification Methods Don’t Always Scale with the Sample Budget: Over 90% of graded chains of thought were faithful, including on problems where correct answers were generated infrequently.The faithful reasoning steps indicate signal that a verifier could exploit.
- 4.2.1 Flaky Tests in SWE-bench Lite: 11.3% of SWE-bench Lite problems have flaky test suites that can inconsistently classify the same candidate solution.Some tests are nondeterministic because candidate solutions handle unordered Python sets differently across runs.
- 4.2.2 False Negatives in CodeContests: 35 of 122 CodeContests problems with Python3 solutions contain provided correct solutions that fail their corresponding tests.Multiple valid outputs and malformed mutated inputs contribute to false negatives.
5 Discussion and Limitations
Repeated sampling can amplify weaker models when correct outputs are identifiable, but its broader usefulness depends on verification and inference-system design. The experiments also leave several avenues for improving sample diversity, interaction, and information sharing.
- Repeated sampling can amplify weaker models and sometimes make them more performant and cost-effective than stronger models using fewer attempts.
- Improving Repeated Sampling: The experiments independently generate every attempt with the same prompt and hyperparameters, leaving solution diversity as an explicit improvement direction.The authors suggest combining token-level temperature sampling with higher-level diversity mechanisms.
- Improving Repeated Sampling: Single-turn generation without execution feedback is used for CodeContests and MiniF2F, despite available automatic verification tools.Multi-turn interaction may improve solution quality but makes each attempt more expensive.
- Improving Repeated Sampling: The experiments isolate attempts from one another, although verifier feedback and existing samples may help generate better future attempts.
- Repeated Sampling and Inference Systems: Repeated sampling is a throughput-oriented inference workload distinct from latency-sensitive chatbot serving.Prompt overlap and specialized attention optimizations can reduce the cost of many samples.
- Verifiers: Scaling repeated sampling to tasks without automatic verifiers requires improved methods for identifying correct outputs, including self-assessment for subjective tasks.
6 Related Work
Related work places repeated sampling within broader efforts to scale inference computation, including search, deliberation, ensembles, and self-critique. Prior studies already report strong repeated-sampling results in coding and puzzle-solving, while scaling-law work motivates characterizing predictable performance changes.
- Scaling Inference Compute: Inference-time scaling methods include tree search, deliberation, model ensembles, and self-critique or response refinement.
- Repeated Sampling: Repeated sampling has improved capabilities across coding and puzzle-solving, with coding performance reported to scale to a million samples when verification tools are available.
- Scaling Laws: Training scaling laws motivate studying predictable relationships between model performance and compute allocation at inference time.
A Sampling Experimental Setup
The experiments evaluate repeated sampling across formal proofs, programming, and mathematics, using many generated solutions and task-specific correctness checks.
- Lean Formal Proofs: 130 Lean4 MiniF2F test questions are evaluated with 10-second timeouts for every tactic step.Solutions are graded with lean-dojo 1.1.2 and Lean 4.3.0-rc2.
- Lean Formal Proofs: 10,000 samples per problem are generated for the formalized MATH problems, with five validation-set theorems used as few-shot examples.Sampling uses temperature 0.5 without nucleus sampling.
- CodeContests: 140 CodeContests test questions without image tags are sampled 10,000 times each and checked against concatenated public, private, and generated tests.Sampling uses temperature 0.6 and top-p 0.95.
- MATH: 128 randomly selected test-set problems are sampled 10,000 times each and graded by exact-match or equivalence to the ground-truth answer.The mathematics setup uses temperature 0.6 without nucleus sampling and 512-token outputs.
- GSM8K: 128 randomly sampled test-set problems are evaluated with 10,000 samples per problem and answer extraction followed by exact-match or equivalence checking.The GSM8K setup uses five randomly sampled training examples per problem, temperature 0.6, and 512-token outputs.
B.1 Experimental Setup
The SWE-bench Lite experiments use an unmodified DeepSeek-Coder-V2-Instruct agent with repeated completions, while separately accounting for flaky test suites.
- Agent setup: DeepSeek-Coder-V2-Instruct is evaluated with the off-the-shelf Moatless Tools framework and Voyage AI embeddings.The model and framework are used without modifications.
- Sampling: 250 independent completions are sampled for each SWE-bench Lite problem using temperature 1.6.The temperature was selected by sweeping 1.0, 1.4, 1.6, and 1.8 on 50 test problems.
- Flaky tests: 34 SWE-bench Lite problems have flaky test suites, including 30 cases where flakiness appeared even for dataset-author solutions.An additional instance was machine-dependent and associated preliminarily with unpinned dependencies.
- Evaluation: The full evaluation runs flaky problems 11 times and uses majority voting, while the non-flaky subset removes the 34 listed instances.The subset contains 266 problems.
- Evaluation: Figure 9 reports SWE-bench Lite results both excluding and including problems with flaky tests, with the trend noted as unchanged.The left graph excludes all problems in Table 3, whereas the right graph includes them.
C.1 Experimental details
Coverage curves are fit with exponentiated power laws using log-spaced sample budgets and nonlinear parameter fitting.
- Curve fitting: 40 points spaced evenly on a log scale from 0 to 10,000 are used to fit each coverage curve.Duplicate points are removed before fitting.
- Curve fitting: SciPy’s curve_fit function estimates the a and b parameters from Equation 3.The fitted parameters are chosen using the selected coverage-curve points.
- Curve fitting: The fitting procedure models coverage as an exponentiated power law over the sampled budget range.This procedure operationalizes the paper’s coverage-curve analysis.
C.2 Additional results
Additional experiments extend exponentiated power-law fitting across datasets and models, while verification metrics are computed from repeated random sample subsets.
- Additional results: Figure 10 presents power-law fits for coverage curves across an expanded set of datasets and models.The figure broadens the coverage-curve analysis beyond the initially reported task and model combinations.
- Verification metrics: 100 random subsets of size k are evaluated for each verification method on the same 128-problem MATH and GSM8K subsets.The reported values are means and standard deviations across subsets.
- Verification metrics: Majority Vote, Reward Model + Best-of-N, and Reward Model + Majority Vote are the verification metrics computed from 10,000 samples per problem.The procedure uses the same problem subsets for both datasets.
E GSM8K incorrect answer
A GSM8K test problem contains an incorrect ground-truth answer. Correcting the arithmetic changes the reported average loss from $3 to $3.5 per race.
- A GSM8K test problem, indexed as 1042 on HuggingFace, has an incorrect ground-truth solution.
- The original solution computes an $11 win on the second race and a $15 loss on the third race, yielding an average loss of $3.
- $16.5, not $15, is the correct third-race loss because it is 1.5 times the $11 second-race win.
- $3.5 per race is the corrected average loss, based on total losses of $21.5 across the first and third races and the $11 second-race win.