Test-Time Compute: Sampling, Refinement, Optimal Inference

Training a language model is expensive. You run billions of gradient updates over trillions of tokens, burn weeks of GPU time, and produce a set of weights that are frozen before the model ever sees a real user query. After that, every inference call uses exactly the same amount of compute, regardless of whether the question is "What is 2 + 2?" or "Prove the Riemann hypothesis." This uniformity is economical but wasteful: trivial questions receive the same resources as intractable ones.

Test-time compute refers to the deliberate allocation of additional computation at inference time to improve output quality. Instead of accepting whatever the model produces in a single forward pass, you spend more FLOPS, generate more candidates, or let the model iterate over its own answers. The key insight is that some problems are easier to verify than to solve, and a model that can check its own work, even imperfectly, can use that signal to self-improve during the generation process.

This chapter examines the main strategies for scaling test-time compute: generating and ranking multiple samples, applying iterative self-refinement, designing compute-optimal inference budgets, and the emerging empirical scaling laws that govern how answer quality changes as you spend more inference FLOPS. As we explored in the preceding chapters on Process Reward Models and Constitutional AI, giving a model the ability to evaluate its own output is a prerequisite for most of these techniques to work.

The dominant paradigm in deep learning is the pretrain-then-deploy pipeline: train once, infer cheaply. This makes sense when you want to serve millions of identical requests per day. But it creates a ceiling on quality that more training alone cannot raise, because the bottleneck is not the model's parameter count but the determinism of single-pass greedy decoding.

The pretrain-then-deploy pipeline treats every inference call as equally important, and allocates the same fixed computation to every query regardless of its difficulty. This works well for an easy task like sentiment classification, where a single pass almost always produces a correct answer. But for a hard task like constructing a mathematical proof or debugging a subtle concurrency issue, the probability of a correct single-pass answer may be only a few percent. The model has the relevant knowledge, but the decoding process is too noisy or too shallow to surface it reliably in one attempt. Scaling training compute helps but reaches its own plateau: at some point, adding more parameters or training tokens yields diminishing returns, and the residual errors are driven by decoding stochasticity rather than lack of knowledge.

Consider how a human expert solves a hard problem. They do not produce the final answer in one uninterrupted stream of thought. They draft, re-read, spot errors, try alternatives, abandon dead ends, and synthesize the best path found so far. All of this happens at "test time," after the expert has finished their formal training. The question test-time compute research asks is: can we build models that do the same thing?

There is a deeper reason to expect that test-time compute can work: for many tasks, verification is fundamentally easier than generation. Running a candidate proof through a formal checker, executing a candidate program against test cases, or checking whether a candidate answer is internally consistent are all substantially simpler operations than producing the proof, program, or answer in the first place. A model that can generate many plausible attempts and verify each one can exploit this asymmetry. It combines the generative power of a large language model with the reliability of a checking process, producing outputs that neither component could achieve alone.

The historical analogy is Monte Carlo methods in classical computation. When a deterministic algorithm for a problem is slow or unknown, you can instead sample many random solutions and accept the first one that passes a cheap test. Test-time compute is the neural network version of the same idea, applied to natural language and structured reasoning rather than numerical optimization. Just as Monte Carlo integration improves with more samples even when the analytic solution is intractable, test-time compute improves answer quality even when the model's individual output distribution is imperfect.

There are two complementary ways to spend extra compute at inference:

• More parallel samples: Generate independent candidate answers from the same prompt, then select the best one. This works because the model's output distribution contains good answers at non-trivial probability; you just need enough draws to land on one.
• Deeper sequential reasoning: Let the model produce a chain of intermediate steps, verify each step, and revise before committing to the next. This increases depth rather than breadth, and is especially useful when the answer space has structure that rewards step-by-step reasoning.

These two strategies are not mutually exclusive. You can generate reasoning chains (breadth) and evaluate each one step by step (depth). The best empirical results tend to combine both, and much of the recent research on large reasoning models, including OpenAI's o1 and o3 family, rests on precisely this combination.

Multiple sampling is the simplest test-time compute strategy. Given a prompt , you run the model times to produce a set of candidate responses. Formally, the candidate set is:

where:

• is the input prompt
• is the -th candidate response
• is the number of independent samples drawn
• Each is sampled independently from the model's distribution:

The quality of this set depends on two factors. First, the coverage of the sample set: does it contain at least one good answer? Second, the selector's precision: can you reliably pick the best answer from the candidates? Both matter, and each is independently improvable. Coverage is primarily a function of the model's underlying accuracy and the sampling temperature. Selector precision is a function of the verification or scoring mechanism you apply.

It is worth emphasizing that even when coverage is high, a poor selector erases most of the benefit. If your selection rule cannot distinguish the correct answer from the wrong ones, having many correct candidates in the pool does not help. Conversely, even a mediocre selector can extract enormous value from a pool with high coverage. The two components interact multiplicatively: you need both to work.

When you sample with temperature , the model's output distribution over the next token is reshaped. The model ordinarily outputs raw scores called logits, and the softmax function turns them into probabilities. Temperature scales the logits before the softmax, controlling how peaked or flat the resulting distribution is. For a single decoding step, the probability of token given the context is:

where:

• is the raw logit score for token from the model's output layer
• is the temperature parameter
• is the vocabulary (the set of all possible tokens)
• is the sequence of tokens generated so far
• The denominator is the partition function that ensures the distribution sums to 1

When , the formula reduces to argmax decoding: the token with the highest logit receives all the probability mass. When , the distribution is unmodified. When , the distribution is flattened toward uniform, increasing diversity at the cost of coherence.

For multiple sampling to work well, you need diversity: if all samples are nearly identical, you get copies of the same answer, and selecting among them gives no improvement over single-pass decoding. The choice of is a design decision that trades off coverage (higher ) against quality per sample (lower ).

This tradeoff is task-dependent. For math problems where the correct answer is a specific number or expression, high temperatures can improve coverage by exploring more distinct reasoning paths, even if individual chains become noisier. For code generation, moderate temperatures around 0.7 to 0.9 tend to work well, since you want diverse logic but not incoherent syntax. For factual question answering, lower temperatures often work better because the model's top-probability answers tend to be factually correct, and increasing temperature mostly adds noise. The right setting requires empirical calibration for your specific task and model.

Another dimension of diversity is top-p (nucleus) sampling and top-k sampling, which we covered in detail in the GPT Architecture chapter. These methods further shape the sampling distribution by truncating low-probability tokens before sampling. In the context of multiple sampling, they control whether the model explores rare but potentially correct reasoning paths or stays close to its high-confidence outputs.

The probability that at least one of samples is correct can be computed exactly if you know how many of generated samples are correct. The pass@k formula, introduced for code generation evaluation, is:

where:

• is the total number of generated samples for a single problem
• is the number of correct samples among those ( )
• is the number of samples you are allowed to submit ( )
• denotes the binomial coefficient "a choose b"

The formula counts the fraction of size- subsets of the samples that contain no correct answer, and subtracts that from 1. If (none are correct), pass@k = 0. If , the formula equals 1 because every subset contains at least one correct answer.

To understand why the formula takes this form, consider the complementary event: what is the probability that a randomly chosen subset of samples contains no correct answer? There are ways to choose samples entirely from the incorrect ones, and ways to choose any samples. The ratio of these two binomial coefficients gives the probability of failure, which subtracted from 1 gives the probability of success.

For independent samples each correct with probability , the expected pass@k simplifies to the approximation:

where is the per-sample probability of correctness. This approximation is tight when is large relative to .

The practical implication is stark. Even a model with on a hard coding problem achieves:

Scaling from 1 to 50 converts a near-impossible task (5% success rate) into a highly likely success (92%). This is the mathematical core of why test-time compute works for verifiable tasks: you are not improving any single sample, but you are dramatically improving the probability that your sample set contains at least one correct answer.