Scaling LLM test-time compute optimally: what the Berkeley paper actually says

Reading Snell, Lee, Xu, and Kumar (UC Berkeley, 2024) after watching a 70B model fail repeatedly on a set of reasoning-heavy code review tasks that my engineers could handle in five minutes.

The production failure was consistent: complex multi-step refactoring suggestions, data-flow analyses, async correctness proofs. The model would get the first two steps right and then confidently produce step three with a subtle error that propagated through the rest. Single-shot generation, no retry logic. The standard answer from the team was to upgrade to a GPT-4-class model or Claude Opus — roughly 8–15× higher per-token cost. Before approving that budget, I wanted to know if we were actually hitting a capability ceiling or just a sampling strategy ceiling.

The question the Berkeley paper answers precisely is this: for a fixed inference compute budget, what's the optimal way to spend it? More specifically, when does running a smaller model multiple times with smart selection beat running a larger model once? The paper's title — "Scaling LLM Test-Time Compute Optimally" — undersells how practically sharp the answer is. It provides a framework for making that budget decision with quantified tradeoffs instead of intuition.

The two axes of LLM scaling

Up until 2024, the scaling conversation was almost entirely about pretraining compute: Chinchilla showed that given a FLOP budget for training, you should allocate it proportionally between model parameters and training tokens. Scaling laws gave you predictions about what a 10× larger training budget would buy in terms of perplexity, benchmark accuracy, and downstream task performance.

Test-time compute is a different axis. After a model is trained, you can spend additional FLOPs at inference by:

Generating multiple candidate solutions and selecting the best (Best-of-N)
Running a guided search through the solution space (beam search with a process reward model)
Having the model critique and revise its own outputs (sequential revision)
Thinking step-by-step with extended chain-of-thought

The central observation is that these two axes are partially substitutable: for some problem types, spending 4× more compute at inference produces similar accuracy gains to running a model that required 4× more training compute. Not always. Not for all problem types. But frequently enough that the substitution is worth reasoning about carefully.

The paper formalizes this with the concept of a compute-optimal test-time strategy: given a budget of N equivalent-model forward passes, what allocation of that compute across strategies maximizes expected accuracy? And critically, the optimal strategy is not fixed — it depends on the difficulty of the specific problem relative to the model's baseline capability.

The three strategies

The paper studies three main approaches to scaling test-time compute, with a fourth hybrid. Understanding what each actually does matters for evaluating when they help.

Best-of-N with an Outcome Reward Model (BoN + ORM)

Generate N independent complete solutions. Score each using a trained reward model that evaluates the final answer. Return the highest-scoring output.

The math is simple: if the model's probability of producing a correct solution in a single sample is p, then the probability that at least one of N samples is correct is 1 - (1-p)^N. For p = 0.3 and N = 10, that's 1 - 0.7^10 ≈ 0.97. You've taken a 30% single-shot accuracy to 97% with 10× compute.

The catch is that you need a reliable verifier to select among the N candidates. For math problems with numerical answers, you can check correctness exactly — the answer either matches or it doesn't. For code, you can run unit tests. For open-ended reasoning, you need a trained outcome reward model (ORM), and the ORM's quality becomes the binding constraint on your effective ceiling.

The other catch: BoN has high latency when run sequentially. If you run N completions in series on one GPU, total latency scales linearly with N. With enough parallel compute (N identical GPU replicas), you can amortize this — all N run simultaneously, latency equals one completion. But that requires parallel capacity and coordination overhead.

PRM beam search

Instead of generating complete solutions and picking the best, use a Process Reward Model to score each intermediate step and guide a beam search.

A PRM is a model trained to answer: "Given the reasoning chain so far, is this next step correct?" Not "is the final answer right" — that's the ORM's job. Rather, "is this intermediate step a valid move toward a correct solution?"

Beam search with a PRM works as follows:

Maintain a set of K active "beams" — partial solutions at the same step depth
For each beam, sample B candidate next steps
Score all K×B candidates with the PRM
Keep only the top K by PRM score; discard the rest
Repeat until all beams reach a terminal state
Score terminal states with an ORM; return the best

The compute cost is O(K×B×steps) — proportional to the number of beams maintained, the branching factor, and the depth of the solution. For a fixed compute budget, you can trade off K (breadth) against steps (depth).

Why is PRM beam search potentially better than BoN? Because it can prune bad paths early. In BoN, a generation that goes wrong in step two will still consume the compute needed to complete all remaining steps. PRM beam search detects the error at step two, drops that path from the beam, and reallocates compute to more promising directions. For problems with clear intermediate structure — multi-step math, algorithm derivations, formal proofs — this early pruning can be very efficient.

The requirement: a PRM. Training a PRM requires step-level labels. For each reasoning chain in your training data, you need to know which steps are correct and which are not. This is expensive to obtain: OpenAI's PRM800K dataset (used as a reference in this paper) required human annotators to label 800K individual reasoning steps. You can use synthetic PRM training via Monte Carlo rollouts — generate many continuations from each step and use whether those continuations lead to correct final answers as a signal for step quality — but this requires significant compute and the resulting PRMs have higher variance than human-labeled ones.

DVTS: Diverse Verifier Tree Search

Standard PRM beam search has a mode-collapse problem: all K beams can converge to the same wrong solution. If the PRM confidently scores a particular reasoning pattern highly (and is wrong about it), all beams follow that pattern. You've spent K× compute exploring K near-identical paths.

The paper introduces DVTS as a fix: instead of one beam of width K, run K/m independent PRM beam searches of width m. Each sub-search uses its own random seed and explores independently. At the end, pick the best terminal state across all sub-searches using the ORM.

DVTS trades search depth for diversity. A single beam of K=16 can go deeper and prune more aggressively. K/m = 4 independent beams of m=4 each produce more varied final candidates at the cost of less pruning within each sub-search. The paper shows DVTS outperforms vanilla beam search specifically because of this diversity benefit: in the regime where PRM scores are noisy and the model has multiple plausible reasoning paths, maintaining diversity is worth more than maintaining depth.

Why difficulty changes the optimal strategy

Here's the insight that makes the paper worth reading carefully rather than just taking the "use more compute" message at face value.

Define problem difficulty as 1 - pass@1: the fraction of single-sample generations that produce an incorrect answer. A pass@1 of 0.8 means the model gets it right 80% of the time on a single try — easy. A pass@1 of 0.05 means 95% of single samples are wrong — hard.

The optimal strategy changes discontinuously as difficulty changes:

Easy problems (pass@1 > ~0.7): Best-of-N has diminishing returns almost immediately. If the model is already right 70% of the time, N=4 gets you to ~99% — and going to N=16 adds almost nothing. PRM beam search is wasteful because there aren't many wrong paths to prune. The compute is better spent elsewhere. For these problems, a simple greedy decode with temperature 0 often beats anything more elaborate, and test-time compute is largely wasted.

Moderate difficulty (pass@1 between ~0.15 and ~0.70): This is the sweet spot for test-time compute. PRM beam search can efficiently find correct solutions by exploring the space. DVTS improves on vanilla beam search by maintaining diversity. BoN with a good ORM also helps but requires more total compute to match PRM search efficiency. The paper's key result lives here: a compute-optimal strategy with a smaller model can match a model roughly 14× larger in parameter count when problems land in this difficulty range.

Hard problems (pass@1 < ~0.15): PRM beam search degrades badly. When the model rarely produces correct reasoning, the PRM is being asked to distinguish between flavors of wrong. Beam search confidently explores a space where nearly all paths lead to incorrect solutions. BoN can still help at large N — if pass@1 is 0.05, N=100 gives you ~99.4% coverage — but the compute requirements are enormous, and you need N parallel GPUs to avoid catastrophic latency. For the hardest problems in this regime, no amount of test-time compute on the current model helps much; what you actually need is a stronger model or, for reasoning tasks specifically, a learned capability the current model doesn't have.

The practical implication: to apply test-time compute efficiently, you need to estimate difficulty upfront. The paper uses oracle difficulty (computed from many samples after the fact). In production, you're estimating it from the problem statement before generating anything — which is a substantially harder task.

The compute-optimal frontier

The paper's central experimental contribution is computing what they call the compute-optimal frontier: the accuracy achievable as a function of test-time FLOPs, assuming you pick the best strategy for each difficulty level.

On the MATH benchmark, using PaLM 2-S as the base model: with a test-time compute budget of roughly 4× the cost of single-pass generation, the compute-optimal strategy achieves accuracy comparable to PaLM 2-L — a model substantially larger in parameter count. The equivalence is not universal across all problems; it holds specifically for problems in the moderate-difficulty range. For very hard problems, the larger model maintains its advantage.

The framing the paper uses: pretraining compute and test-time compute are partially interchangeable scaling resources, but with different efficiency profiles across difficulty levels. Pretraining compute improves capabilities uniformly — a stronger model is better across all difficulty levels. Test-time compute is targeted — it helps most at moderate difficulty, where intelligent search is tractable, and helps least at the extremes.

This is the quantitative basis for why o1/o3 and DeepSeek R1 make sense: rather than training arbitrarily larger dense models, you train a model that has learned to allocate test-time compute efficiently (through reinforcement learning on reasoning traces), then let it use more compute at inference on hard problems. The Snell et al. framework is the theoretical underpinning; the o1-class models are its learned embodiment.

Production tradeoffs no one mentions in the benchmark posts

Latency structure is completely different between strategies. BoN with parallel sampling has latency equal to one completion (if you have N parallel slots), but requires N GPU-seconds of compute. PRM beam search is sequential — you can't start step k+1 until you've scored all branches at step k — so latency grows with depth. For a real-time application with p99 latency requirements, beam search can violate your SLA even when BoN with parallel replicas doesn't. You need to measure the latency distribution of your specific task's step depth, not just average case.

The ORM is load-bearing infrastructure, not an afterthought. BoN's ability to find the correct answer among N candidates depends entirely on the ORM's precision. If the ORM has 80% accuracy in distinguishing correct from incorrect solutions, and you're running BoN-16, you'll sometimes select a wrong answer over a correct one. Reward model overoptimization (Goodhart's Law applied to inference) is real: you can pick the solution that best exploits your ORM's blind spots rather than the genuinely correct one. This effect grows with N. Production deployments need to monitor: what fraction of BoN selections, when checked against ground truth, are actually wrong? If this fraction grows over time, your ORM is being increasingly Goodharted by distribution shift.

PRM training cost is substantial and often underestimated. The paper uses PRM800K, which was produced by OpenAI. If you're building this capability internally, plan for: collecting multi-step reasoning traces at scale, annotating step-level correctness (either human or Monte Carlo synthetic), training a separate reward model, and iterating. For most teams, the honest answer is: you don't have a PRM, and you can't get one quickly. This limits you to BoN + ORM or BoN + ground-truth verifier. Both are still useful; they just don't give you the compute efficiency gains that PRM beam search provides.

Difficulty estimation in production is unsolved in the paper. The paper's experiments assume oracle difficulty — they know, from pre-computed pass@N statistics, exactly how hard each problem is. In production, you have one shot to estimate this before choosing a strategy. Options: a cheap proxy model that estimates confidence on the input, a learned classifier trained on (problem features → difficulty), or adaptive compute (run once, check confidence, decide whether to scale). None of these are in the paper. You're on your own for the deployment piece, which is the hardest part.

GPU topology shapes which strategies are viable. BoN is embarrassingly parallel: if you have 16 replicas, running BoN-16 costs you one latency unit. If you have 1 GPU, it costs you 16 latency units. PRM beam search is not parallelizable across steps (it's sequential), but within each step, scoring K×B candidates can be batched efficiently. On a single A100, PRM beam search may actually have better wall-clock latency than BoN at the same compute budget, because the beam scoring can be batched. On a 16-GPU cluster with enough memory, BoN wins on latency. The right strategy depends heavily on your hardware topology.

When you have a verifier, you probably don't need a PRM. For code generation, unit tests are a nearly perfect verifier — you know exactly whether the code is correct. For math with closed-form answers, exact matching works. When ground-truth verification is available, BoN + ground truth is both simpler and more reliable than BoN + ORM or PRM beam search. The paper's main argument for PRM beam search is compute efficiency relative to BoN. But BoN with a perfect verifier at N=16 is often good enough and much simpler to operate than anything involving a PRM. The complexity budget matters.

Failure modes in practice

Reward model collapse under distribution shift. Your ORM or PRM was trained on a specific distribution of reasoning tasks. When production traffic drifts — new problem types, unusual phrasings, edge cases your training data didn't cover — both model types will assign confident scores to incorrect solutions. This failure is silent: the model is confident it selected the best solution; it's just wrong about what "best" means on the shifted distribution. Production systems need accuracy checks on a held-out set of problems with ground-truth answers, sampled regularly from live traffic.

PRM beam search mode collapse on hard problems. For problems at the hard end of the difficulty spectrum, the PRM often assigns high scores to the dominant wrong reasoning pattern — the one the model is confidently wrong about. Beam search concentrates all compute on this pattern, producing K beams that all arrive at the same incorrect answer with high PRM confidence. DVTS partially mitigates this, but not entirely. If you observe beam diversity collapsing to near-zero in your traces, you're in this failure mode, and the fix is either a better PRM or falling back to BoN on problems where beam diversity is low.

Revision loops that make correct answers wrong. Sequential self-revision — generate, critique, revise — is theoretically appealing but has a well-documented failure mode: the model revises a correct answer to an incorrect one because its critique model disagrees with the correct answer for the wrong reasons. This is especially common when the initial answer is correct but unusual in phrasing or approach, and the critique model has learned to penalize unusual-seeming answers. If you use sequential revision, you need to track how often revision changes a correct answer (which you can only measure if you have ground truth). It's higher than you'd expect.

N is too small at high difficulty to matter. For problems where pass@1 ≈ 0.02, you need N ≈ 150 to have a 95% chance of getting at least one correct sample. Running BoN-16 on these problems gives you 28% coverage — better than nothing, but you're spending 16× the compute for less than a 30% success rate. The practical consequence: test-time compute is not a magic escalation path for hard problems. If your model reliably fails on a class of inputs, the right intervention is model improvement, not inference-time search.

When not to use test-time compute scaling

When you can't verify the output. Every test-time compute strategy depends on selecting among multiple candidates. Selection requires a signal about which candidate is better. For tasks where ground truth is not checkable and no trained reward model exists — creative writing, open-ended business advice, strategic analysis — you have no reliable basis for selection. BoN-16 with a weak ORM can easily surface the most confidently wrong answer. The overhead of running 16 completions is wasted if your selection signal is noise.

When the problem is retrieval, not reasoning. If a model fails because it lacks a specific fact, running more inference steps doesn't help. The model will confidently hallucinate the fact in all N samples; you'll select the most fluent hallucination. Test-time compute scaling is specifically a tool for problems that are reasoning-tractable — where the information needed is in the model's weights and the failure mode is search, not knowledge. If you're seeing failures on factual recall or very recent events, fix the retrieval layer, not the inference strategy.

When p99 latency is your binding constraint. If users require responses within 3 seconds at the 99th percentile, and BoN-8 with parallel sampling takes 2.8 seconds median, your tail will blow the budget. PRM beam search on multi-step problems often has unbounded latency variance (depth varies with problem). You need tight p99 latency control, and test-time compute strategies make this harder unless you implement hard timeout cutoffs with fallback to best-so-far — which changes the semantics of what you're computing.

When the model has systematic bias, not variance. Test-time compute helps when the model is right sometimes and wrong sometimes — there's variance to exploit. If the model has a systematic blind spot — it consistently misunderstands a particular problem structure, or consistently applies an incorrect rule — N samples from the same systematic error gives you N copies of the same wrong answer. BoN-16 with an ORM trained on the same distribution will confidently pick the wrong answer every time. Systematic failures need targeted fine-tuning or prompt engineering, not sampling.

When training a PRM is the prerequisite you can't meet. The best compute efficiency results in the paper come from PRM beam search. If you can't train a reliable PRM for your domain — and most teams can't without substantial annotation infrastructure — you're limited to BoN + ORM or BoN + ground-truth verifier. These still work well and are worth using, but the efficiency gains relative to running a larger model are smaller. Be realistic about which strategies are actually available to you given your infrastructure.

What this means for model selection

The practical framing I've settled on for the code review pipeline: test-time compute is worth trying when you have a reliable verifier (unit tests, exact output matching, human-checkable criteria) and the problems are in the moderate-difficulty range for your current model. The signal for "moderate difficulty" is: your current model gets it right sometimes in production, but with frustrating inconsistency. Not "never right" — that's hard. Not "almost always right" — that's easy, single-shot is fine.

For the code review task, the answer turned out to be: implement BoN-8 with GPT-4-as-judge as the ORM, running 8 parallel completions against the model we already had. The GPT-4 judge call costs about 15% of one completion. Total cost: 8.15× per query. Single-shot accuracy on our held-out set: 61%. BoN-8 accuracy: 84%. The 8× larger model (GPT-4 Turbo at the time) got 87% on the same set — at 15× the per-token cost, before the overhead of running 8 samples.

The math worked out in favor of BoN-8 with the smaller model. Not because the smaller model was better — it wasn't — but because for moderate-difficulty reasoning tasks, the variance in smaller-model outputs is exploitable, and the cost of verification was cheap relative to the cost of a larger model.

The paper gives you the framework to run this calculation for your own situation. The key inputs are your current pass@1 on a held-out problem set, the cost of running your verifier, the latency budget, and whether you have access to a PRM. The paper doesn't give you the production deployment path; it gives you the evidence to avoid spending 15× more on a bigger model before checking whether smarter sampling gets you most of the way there.

Scaling LLM Test-Time Compute Optimally — Charlie Snell, Jaehoon Lee, Kelvin Xu, Aviral Kumar. UC Berkeley, 2024.