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 $N$ 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 $N$ 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 $x$, you run the model $N$ times to produce a set of candidate responses. Formally, the candidate set is:

where:

• $x$ is the input prompt
• $y_i$ is the $i$-th candidate response
• $N$ is the number of independent samples drawn
• Each $y_i$ is sampled independently from the model's distribution: $y_i \sim p_\theta(\cdot \mid x)$

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 $T > 0$, 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 $t$ given the context is:

where:

• $z_t$ is the raw logit score for token $t$ from the model's output layer
• $T > 0$ is the temperature parameter
• $V$ is the vocabulary (the set of all possible tokens)
• $y_{<t} = (y_1, \ldots, y_{t-1})$ is the sequence of tokens generated so far
• The denominator is the partition function that ensures the distribution sums to 1

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

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

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 $k$ samples is correct can be computed exactly if you know how many of $n$ generated samples are correct. The pass@k formula, introduced for code generation evaluation, is:

where:

• $n$ is the total number of generated samples for a single problem
• $c$ is the number of correct samples among those $n$ ($0 \le c \le n$)
• $k$ is the number of samples you are allowed to submit ($k \le n$)
• $\binom{a}{b}$ denotes the binomial coefficient "a choose b"

The formula counts the fraction of size-$k$ subsets of the $n$ samples that contain no correct answer, and subtracts that from 1. If $c = 0$ (none are correct), pass@k = 0. If $c \ge k$, 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 $k$ samples contains no correct answer? There are $\binom{n - c}{k}$ ways to choose $k$ samples entirely from the $n - c$ incorrect ones, and $\binom{n}{k}$ ways to choose any $k$ 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 $p$, the expected pass@k simplifies to the approximation:

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

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

Scaling $k$ 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.

Generating many candidates is useless unless you can pick the best one. The selection problem is harder than it looks, because you cannot in general know which candidate is correct without running the same computation that originally produced it. Several approaches exist for this problem, each with different assumptions, costs, and reliability properties.

Majority voting (self-consistency). If answers to the same question can be compared directly, such as numerical answers or classification labels, select the most frequently occurring answer across all candidates. This works remarkably well for math reasoning: if you generate 40 chain-of-thought solutions and 28 of them arrive at the same numerical answer, that answer is likely correct even if many of the individual reasoning chains contain errors. The underlying reason is that correct answers tend to be unique (there is typically one right answer), while wrong answers are diverse (different chains make different mistakes). This asymmetry means that correct answers accumulate plurality votes while wrong answers split votes among many alternatives.

Majority voting requires no additional model and adds almost no compute overhead, since you just count answer occurrences. Its main limitation is that it only works when answers can be directly compared. For open-ended prose, there is no natural notion of two responses being "the same answer."

Reward model scoring. Train a separate scoring model on human preferences or correctness labels, then select the candidate with the highest score. This is the reranking paradigm used in passage retrieval and code generation. The quality of selection is bounded by the accuracy of the scorer, which means that reward model quality is the binding constraint. A poorly calibrated reward model will select confidently wrong answers, producing no benefit or even net harm from the sampling.

Process reward model (PRM) scoring. Rather than scoring completed answers, a PRM scores each reasoning step and aggregates across the chain. PRMs are more robust to "correct-answer, wrong-reasoning" failure modes because they require the intermediate steps to be valid. When used for candidate selection, the total score for a candidate is typically the product or minimum of its step-level scores. The product penalizes chains with any weak step; the minimum is even stricter, selecting only chains where every step is confident. We covered the design and training of PRMs in detail in the Process Reward Models chapter.

Verifier-guided selection. For structured tasks such as code or formal proofs, you can execute or symbolically check the candidate answer directly. A program that passes all test cases is correct by definition; no learned verifier is needed. This is the gold standard when applicable, because the verification is guaranteed correct and requires no additional model training.

The choice of selection strategy has a large impact on overall accuracy. Majority voting is cheap and reliable when the answer is discrete. Reward model scoring generalizes to open-ended outputs but depends on the quality of the scorer, which may itself be brittle on out-of-distribution queries. PRM scoring sits between these extremes: it is more expensive than majority voting because it requires running the reward model over every step of every candidate chain, but it is more reliable than outcome-level reward models because it catches errors at the step where they first occur rather than only penalizing wrong final answers.

Verifier-guided selection is uniquely powerful for code and formal math because the verification is guaranteed correct. No amount of reward model training can match the reliability of a formal checker or a unit test suite. For this reason, the most impressive test-time compute results in the literature tend to appear on coding and math benchmarks, where this class of feedback is available.

The simulation reveals a consistent pattern: majority voting becomes increasingly valuable once repeated correct answers form a consensus. Its gains peak across the early-to-middle doublings and then diminish as accuracy approaches its ceiling. This is the behavior predicted by the pass@k formula: informed selection converts candidate coverage into accuracy, while random selection remains at the base rate.

Multiple sampling generates candidates in parallel and selects among them. Iterative refinement takes a fundamentally different approach: it generates candidates sequentially, using each evaluation to guide the next generation. The model produces an initial answer, evaluates it, and uses the evaluation to produce an improved version. This mirrors the way a human writer drafts and revises: not by writing many independent versions and picking the best, but by progressively improving a single working draft through repeated critique.

The distinction matters because refinement can sometimes reach quality levels that pure parallel sampling cannot. If the correct answer requires a specific insight that the model rarely generates from scratch, even 100 independent samples may all miss it. But if you give the model a near-correct answer and ask it to identify and fix the specific flaw, the targeted feedback may guide it to the correct path. Refinement exploits the asymmetry between generation and verification in a more directed way than sampling.

The simplest form is self-refinement, where the model critiques its own output and revises it. A typical prompt sequence is:

1. Generation prompt: "Solve the following problem: {problem}"
2. Critique prompt: "Here is a proposed solution: {solution}. Identify any errors or weaknesses in the reasoning."
3. Refinement prompt: "Given this critique: {critique}, revise the solution to address the identified issues."

Steps 2 and 3 can repeat for several iterations, with each cycle consuming additional tokens and therefore compute. The model is acting as both solver and verifier, which works better than you might expect because generation and verification are distinct different cognitive tasks. A model may not generate a correct proof in one pass, but it may recognize that a specific step is invalid when asked directly. The critique role invokes a different part of the model's learned behavior than the generation role, and these two roles have different error rates on different parts of the problem.

The critical weakness of pure self-refinement is that the model's blind spots as a generator are correlated with its blind spots as a critic. If the model consistently makes a particular type of error, say, off-by-one errors in array indexing, it will tend to miss those same errors during critique as well. The model's knowledge gaps are persistent: they do not magically disappear when you ask the model to assume a different role. External feedback breaks this correlation by introducing a signal that is not derived from the same model that made the original error.

Another subtlety is that iterative self-refinement can sometimes make outputs worse rather than better. If the model's self-critique is inaccurate, it will "fix" aspects that were already correct, introducing new errors in the process. This happens when the critique task is harder than the original generation task, which can occur for complex, multi-step problems where the model cannot reliably reason about the correctness of intermediate steps. Research results on self-refinement by Madaan et al. (2023) document both the successes and the failures, and consistently find that structured external feedback outperforms pure self-critique.

A more reliable form of iterative refinement incorporates external signals that are independent of the model's own beliefs:

• Code execution feedback: Run the generated program against test cases and feed the error message back into the model. The error message is often more informative than anything the model could generate as a self-critique, because it identifies the exact line and nature of the failure rather than producing a general comment about code quality.
• Retrieval augmentation: After generating an initial answer, retrieve documents relevant to the specific claims made, then refine to incorporate the retrieved evidence. This is particularly useful for factual tasks where the model may confidently generate plausible-sounding but incorrect information.
• Formal verification feedback: For math proofs, feed the output into a proof assistant like Lean or Coq and return the specific error message. Even a partial proof that fails at a specific step gives the model much more precise information than a general-purpose self-critique.
• Human-in-the-loop feedback: Ask a human for a specific critique, then let the model incorporate it. This is expensive but often the highest-quality signal, and it is used in RLHF (Reinforcement Learning from Human Feedback) pipelines where the human preference signal is collected to train reward models.

The common thread across these feedback sources is that they are derived from a process that is structurally different from, and often more reliable than, the model itself. Running code against tests is a ground-truth check; retrieving documents accesses external knowledge the model may not have internalized; a human expert can catch errors that are invisible to the model. Each of these breaks the correlation between generator and critic that limits pure self-refinement.

A refinement loop can be formalized as a sequential process where each iteration updates the answer using the previous answer and new feedback. Starting from an initial answer $y^{(0)}$ generated from prompt $x$, each subsequent answer is produced by a refinement operator $f$:

where:

• $x$ is the original problem prompt, kept constant across all iterations
• $y^{(t)}$ is the answer at iteration $t$ (the current best solution)
• $e^{(t)}$ is the evaluation or feedback signal computed from $y^{(t)}$, such as an error message, a critique, or a reward score
• $f$ is the refinement function, implemented as a language model conditioned on all three inputs
• $y^{(T)}$ is the final answer after $T$ total refinement iterations

Under this formalization, the expected quality of $y^{(T)}$ after $T$ iterations is a function of the refinement operator's quality and the convergence rate of the process. A well-designed refinement operator converges rapidly; a poorly designed one may oscillate or diverge.

The refinement process has a natural analogy to gradient descent in weight space. Just as gradient descent iteratively updates model weights in the direction that reduces loss, iterative refinement updates the generated answer in the direction indicated by the feedback signal. The key difference is that refinement operates in the discrete space of language tokens rather than in the continuous space of model parameters, and the "gradient" is a natural language critique rather than a mathematically derived gradient vector.

This analogy helps clarify when refinement will converge. Gradient descent converges when the loss surface is well-behaved and the learning rate is appropriate. Refinement converges when the feedback signal accurately identifies the specific errors in the current answer and the model correctly implements the indicated changes. When the feedback is vague, the analogous "step" is poorly directed and convergence is slow. When the feedback is precise (a specific error message pointing to line 47 of a program), the analogous "step" is well-directed and convergence can be fast.

Iterative refinement is most effective when three conditions hold:

• Verifiability: There is a reliable way to evaluate the current answer. This can be automated (executing code, checking proofs) or model-based (using a well-trained critic), but the evaluation must be more reliable than the generation.
• Revisability: The answer space supports incremental improvement. Continuous outputs such as prose and code are easier to revise than discrete choices, because partial revisions make sense. You can fix one bug without rewriting the entire program; you cannot partially fix a multiple-choice answer selection.
• Budget surplus: The number of allowed tokens is large enough to sustain multiple critique-revise cycles. Each cycle approximately doubles the token cost relative to single-pass generation, so deep refinement chains are expensive.

Research results on self-refinement show mixed outcomes: for structured tasks with executable feedback, iterative refinement is highly effective and can convert a mediocre first-pass solution into a correct one within two or three cycles. For open-ended generation tasks without a clear correctness criterion, quality often plateaus after one or two iterations, and the model may introduce new errors while correcting old ones. The lesson is that refinement is not a universal solution but a powerful tool for specific problem types.

You have a fixed inference budget of $B$ total tokens, or equivalently, a fixed number of FLOPS beyond the base model cost. How should you allocate them? Should you generate $N$ independent samples of fixed length, or should you generate fewer samples but allow each one to use a longer chain of thought? Should you run $T$ refinement iterations, or use the same tokens for a single longer generation?

These questions define the compute-optimal inference problem: given a budget $B$ and a task, find the allocation strategy that maximizes expected output quality. This is a practical question. In production systems, the inference budget is directly proportional to cost and inversely proportional to throughput. Getting the allocation right can mean the difference between a system that is economically viable and one that is not.

The problem is also more subtle than it appears. The optimal allocation is not a fixed property of the model; it depends on the task type, the model's base accuracy, the quality of the selection mechanism, and the relationship between chain length and per-sample accuracy. Understanding how these factors interact is the key to designing efficient inference systems.

The fundamental tradeoff is between breadth (more parallel samples) and depth (longer reasoning chains per sample). Let $B$ be the total token budget. If you generate $N$ samples each of length $L$, then the budget constraint is:

where:

• $B$ is the total token budget (fixed)
• $N$ is the number of independent samples
• $L$ is the length of each sample in tokens

This constraint defines a tradeoff curve: holding $B$ fixed, increasing $N$ forces $L$ to decrease, and vice versa. The extreme points are:

where $L_{\min}$ is the minimum useful answer length for the task. The optimal point along this curve depends on the task. For verifiable tasks with low per-sample accuracy, breadth tends to win at small budgets because you need many attempts to land on a correct solution. For tasks where structured reasoning chains substantially improve per-sample accuracy, depth tends to win because the conditional accuracy given a well-formed chain is much higher.

To see why, consider the expected accuracy under each extreme. For the all-breadth strategy with $N = B / L_{\min}$ samples of fixed minimal length, each sample has accuracy $p_{\min}$, the accuracy achievable in $L_{\min}$ tokens:

For the all-depth strategy with a single sample of length $B$, the accuracy is $p_{\max}$, the accuracy achievable with the full budget in one chain:

Breadth wins when $p_{\min}$ is low but $N = B / L_{\min}$ is large enough that the combined probability of at least one correct sample exceeds $p_{\max}$. Depth wins when the full-chain accuracy $p_{\max}$ is much higher than $p_{\min}$, meaning the chain-of-thought reasoning provides substantial value that cannot be replicated by sampling more short chains.

The two curves in this plot represent qualitatively different problem types, and they point toward opposite allocation strategies. The breadth-wins curve rises monotonically because the model's per-sample accuracy does not depend on chain length: it is the kind of problem where the answer is either in the model's knowledge or it is not, and more reasoning time does not help much. Short, independent samples are the right tool. The depth-wins curve shows that allocating all compute to a single long chain yields the highest accuracy, because the per-sample accuracy collapses when chains are too short to complete the reasoning.

In practice, most real tasks fall somewhere between these extremes. A math problem that requires five reasoning steps benefits from some minimum chain length (you need at least enough tokens to complete the derivation), but additional breadth helps once that minimum is satisfied. Identifying where a specific task sits on this spectrum requires empirical measurement on a held-out validation set.

A key empirical question is whether inference compute exhibits scaling laws analogous to training compute laws. For a fixed model and task distribution, the relationship between the number of generated samples $N$ and the probability of a correct answer follows an approximate power law. An empirical fit often has the form:

where:

• $N$ is the number of samples (or equivalent token budget)
• $a > 0$ is a scale coefficient reflecting the marginal value of each additional sample at the task
• $b \in (0, 1)$ is the scaling exponent, typically observed in the range 0.1 to 0.3, reflecting sublinear returns
• $c \ge 0$ is the baseline accuracy floor at $N = 1$ (single-pass greedy decoding)

The exponent $b$ being in the range $(0, 1)$ means doubling the compute budget gives a smaller relative gain each time. Going from 1 to 2 samples improves accuracy more than going from 64 to 128 samples. This matches the intuition from the pass@k formula: early samples cover the most likely correct answers; later samples fill in increasingly unlikely edge cases.

The existence of power-law scaling at inference time is significant because it means inference compute obeys the same mathematical regularity as training compute. Just as the Chinchilla scaling laws (covered in the Scaling Laws chapter) predict model quality from training budget, inference scaling laws can in principle predict answer quality from inference budget for a given task and model. This makes it possible to reason systematically about the tradeoff between training and inference compute rather than treating each as a separate, independent choice.

Work by Snell et al. (2024) shows that a smaller model with compute-scaled inference can match or exceed a larger model running greedy decoding on hard reasoning tasks. A model with 3.8B parameters using 256 samples with PRM reranking can match a 70B model with single-pass decoding on MATH benchmarks. This "compute equivalence" result suggests that inference compute and parameter count are partially substitutable, at least for tasks with verifiable structure. The practical implication is that teams with limited hardware can potentially close quality gaps by spending more on inference rather than training or serving larger models.

The most efficient inference systems route problems to different compute budgets based on estimated difficulty. Instead of applying the same sampling strategy to every query, adaptive allocation reserves expensive multi-sample strategies for the queries that need them, and handles easy queries with cheap single-pass decoding.

Several mechanisms implement adaptive allocation:

Difficulty estimation. Use a fast heuristic, such as few-shot scoring, a lightweight classifier, or the model's own uncertainty estimate, to predict whether a question is easy, medium, or hard before full generation. Allocate budget proportionally. Even an imperfect difficulty classifier substantially reduces average cost if it correctly identifies the easy queries that dominate most real-world distributions.

Early exit. If the model reaches high-confidence agreement across a small $N$ (say, 5 out of 5 candidates agree), stop early without using the full budget. The stopping criterion can be any measure of candidate consensus: exact string match for mathematical answers, semantic similarity for prose, or a threshold on the reward model's score distribution.

Progressive refinement. Start with $N = 4$ samples. If the selector is uncertain (for example, a close vote between two candidate answers), increase to $N = 16$, then $N = 64$. This amortizes the cost of easy questions while preserving quality on hard ones. The model effectively makes a cascade of decisions: "Is this problem hard enough to warrant more compute?"

OpenAI's o1 and o3 family of models applies an implicit version of this strategy: they reason internally using a chain-of-thought scratchpad before producing an answer, spending more tokens on harder problems. The o3 model's exceptional performance on ARC-AGI benchmarks demonstrated that inference compute scaling can overcome task difficulties that large parameter counts alone cannot address. The model spends orders of magnitude more inference compute on the hardest problems than on routine queries, effectively self-routing its own budget.

The most interesting practical observation from adaptive systems is that problem difficulty is approximately predictable. A fast classifier trained on the question text alone can distinguish easy from hard questions with useful accuracy. This means the adaptive routing overhead is small compared to the budget savings on easy questions. In production systems, routing the easiest 70% of queries to single-pass decoding and reserving aggressive multi-sample strategies for the hard 30% can cut total inference cost in half with minimal quality loss on the overall distribution.

Adaptive allocation also changes the economics of test-time compute. A uniform multi-sample strategy applied to all queries is expensive and may not be justifiable for most applications. An adaptive strategy that targets the expensive resources at hard queries can achieve comparable quality at a fraction of the cost. This is the design philosophy behind modern reasoning models, and it represents one of the most important practical advances in efficient inference.

Let's implement the core ideas from this chapter: generating multiple samples from a model, evaluating them, and selecting via majority vote. We will use a toy setting with a simulated model to keep the code runnable, but the patterns apply directly to production-scale systems.

We start by defining a simple model wrapper and the core sampling loop.

The simulated model gives us reproducible experiments. Each call to sample is an independent forward pass through the model, returning a list of answers. In a real system, you would replace sample with an asynchronous batch request to the model's API, enabling all $N$ candidates to be generated in parallel rather than sequentially. The logic of majority voting and pass@k computation is identical whether samples are generated locally or through a remote API.

With candidate answers in hand, we implement majority voting to select the best response.

The majority_vote function uses Python's Counter to find the most frequent answer in $O(N)$ time. For numerical answers in real math problems, you would want to normalize the answer strings first, since the model might express the same number as "1/2", "0.5", or "0.50". Standardizing the answer format before voting is an important practical step that substantially improves the reliability of majority voting in production.

We also implement the exact pass@k formula for comparison with the approximation.

Even with only 10% per-sample accuracy, generating 50 samples and checking any correct one yields over 99% pass@50. This is the core power of test-time compute for verifiable tasks. Notice that the approximation and the exact simulation agree closely, confirming that the simple formula $1 - (1-p)^k$ captures the essential behavior.

The table also reveals the law of diminishing returns in action. Moving from $k = 1$ to $k = 5$ gives a gain of about 0.41 percentage points, but moving from $k = 50$ to $k = 100$ gives only about 0.01 percentage points. The first few samples do the heavy lifting; later samples mostly confirm what you already know.

Let's compare majority voting against random selection (baseline) and oracle selection (upper bound) to understand the practical gain from majority voting.

Majority voting closes a large portion of the gap between random selection and the oracle. At N=64 with a 25% per-sample accuracy, majority voting approaches the oracle bound, while random selection is capped at the model's base accuracy. This gap represents the practical value of having a good selection mechanism: it is not free compute, but it is value realized by combining generation with a reliable selector.

The oracle upper bound also reveals the ceiling on what any selection mechanism can achieve. Once coverage is high, the gap between majority vote and oracle narrows, confirming that the bottleneck has shifted from selection quality to coverage. At very large $N$, even a random selector would approach the oracle because almost every subset of the sample pool contains a correct answer.

Now let's simulate iterative refinement and measure how quality evolves with each iteration. This demonstrates the key dynamics of the refinement process: the initial gain from the first revision, the diminishing returns in later iterations, and the convergence properties of different model configurations.

The simulated accuracy follows the theoretical curve closely. The refinement gain decreases geometrically: the first iteration yields the largest improvement, and subsequent iterations yield diminishing returns. This geometric decay is not arbitrary; it reflects the intuition that early revisions fix the most obvious errors, while later revisions address progressively subtler issues that become harder to identify and correct.

The decay_factor parameter controls how quickly returns diminish. A decay factor near 0 means each iteration provides essentially the same gain as the first (unrealistic in practice). A decay factor near 1 means each iteration provides nearly the same gain as the one before, implying slow convergence. The observed range in practice, roughly 0.4 to 0.7, means that the second iteration yields about half the gain of the first, and the third iteration yields about a quarter.

A natural question is whether a fixed token budget is better spent on multiple independent samples or on iterative refinement. This is the empirical version of the breadth-depth tradeoff question: multiple sampling increases breadth, while iterative refinement increases effective depth. Let's simulate both strategies under a shared compute budget and observe where each excels.

The relative advantage of each strategy depends on the budget magnitude and the task's properties. Multiple sampling tends to dominate at moderate budgets when per-sample accuracy is low; refinement dominates when the model's refinement operator is highly effective and the feedback signal is reliable. The crossover point shifts with model quality: stronger models that generate higher-quality first-pass answers get less benefit from parallel sampling but more benefit from targeted refinement, because their first-pass answers are close enough to correct that a focused critique can bridge the gap.

The core parameters governing test-time compute strategies are:

• N (number of samples): The number of independent candidates generated. Higher N improves coverage but increases latency proportionally.
• k (selection budget): The number of samples passed to the selector. Often equal to N, but can be smaller if you want faster selection.
• T (refinement iterations): The number of critique-revise cycles. Each iteration consumes tokens proportional to the answer length plus the critique.
• Temperature: Controls diversity in parallel sampling. Higher temperature gives more diverse candidates; lower temperature reduces variance but also coverage.
• Selector type: Majority vote, reward model, PRM, or verifier. Each has a different quality-cost tradeoff.

Test-time compute is powerful, but it comes with a set of constraints that matter in practice. Understanding these constraints is essential for making good engineering decisions about when and how to apply test-time compute in production systems.

Latency. Generating $N = 64$ samples takes approximately 64 times as long as single-pass decoding, assuming no batching. In interactive applications with subsecond response time requirements, this is often unacceptable. Parallel generation across multiple GPUs or TPUs reduces wall-clock latency, but increases hardware cost proportionally. The latency-quality tradeoff is the primary constraint limiting the adoption of aggressive test-time compute in interactive production systems. For batch-mode applications such as offline data processing or overnight analysis, latency is less critical and test-time compute is much easier to justify.

Cost. For API-based LLMs, test-time compute directly scales cost. Generating 64 candidates at $0.01 per 1K tokens costs 64 times as much per query as single-pass decoding. In research settings, this is manageable; in consumer applications with millions of queries per day, it is often prohibitive without caching or adaptive routing. Speculative decoding, key-value cache reuse across samples, and adaptive early-exit strategies can all reduce this cost, but they add engineering complexity.

Selector quality. The benefit of multiple sampling is bounded by the quality of the selection mechanism. A majority vote works well when wrong answers are diverse (so they split votes) and correct answers are consistent (so they accumulate votes). But for open-ended generation, where there is no single right answer, majority vote is inapplicable. Reward model selection requires a reliable scorer, which may itself require significant training effort and can fail on distribution-shifted inputs. The selector is a potential single point of failure: a well-calibrated model producing good candidates combined with a poorly calibrated scorer may perform worse than greedy decoding on the same queries.

Diminishing returns. The pass@k formula makes clear that improvements are sublinear in $N$. Going from $N = 1$ to $N = 4$ often yields the largest gain; going from $N = 64$ to $N = 256$ yields much less. Beyond a task-dependent threshold, additional samples add almost no value. This means you should empirically calibrate the optimal $N$ for your task rather than simply maximizing it. Overspending on test-time compute can be wasteful, and the resources might be better allocated to improving the base model or the selection mechanism.

Verification is a bottleneck. For refinement to work, you need reliable verification. In math and code, automated verification exists and is cheap. In prose, factual reasoning, and most real-world tasks, it does not. The performance gap between math-and-code tasks (where test-time compute is very effective) and open-ended language tasks (where it is much less so) reflects this asymmetry directly. Research on test-time compute for tasks without executable verifiers, such as creative writing or open-domain question answering, consistently shows smaller and less reliable improvements.

Distribution shift. Scaling inference compute often reveals failure modes that single-pass evaluation hides. A model may achieve 70% accuracy at $N = 1$ and plateau at 80% at $N = 100$ because the remaining 20% of questions involve systematic reasoning errors that no amount of resampling or refinement can fix without changing the weights. Identifying these plateaus matters for planning whether more test-time compute or more training data is the right investment. The plateau is the ceiling on what inference-time methods can achieve; only changes to the weights can raise it.

The theoretical and empirical work on test-time compute also highlights a fundamental question: when is a task limited by model capacity versus by stochasticity in the generation process? For stochastic failures, where the model knows the answer but sometimes expresses it incorrectly due to noise in the sampling process, test-time compute helps substantially. For systematic errors, where the model consistently produces the wrong answer because it lacks the relevant knowledge or reasoning capability, test-time compute cannot help. Distinguishing between these two failure modes is an active research problem, with implications for how to allocate compute across training and inference. Diagnostic tools like the pass@k plateau analysis and error clustering can help identify which failure mode dominates on a given task.

A final practical consideration is the interplay between test-time compute and model training. The best current reasoning models, including the o1/o3 family, are not simply pretrained models with sampling applied at inference. They are fine-tuned specifically to generate effective reasoning traces, and the training process rewards multi-step reasoning that leads to correct answers. The inference-time sampling strategy and the training objective are co-designed: the model is trained to produce the kind of reasoning chains that benefit from refinement and reranking, and the inference strategy is calibrated to exploit that capability. This co-design is what produces the large quality improvements observed in recent reasoning models, and it suggests that test-time compute is most powerful when the model itself has been optimized to use it.

Test-time compute is one of the most impactful levers for improving language model quality without retraining. The key ideas from this chapter are:

• Multiple sampling generates $N$ independent candidates and selects the best via majority vote, reward model scoring, PRM scoring, or direct verification. The pass@k formula characterizes how coverage improves with $N$, following the expression $1 - (1-p)^k$ for independent samples with per-sample accuracy $p$.
• Iterative refinement generates a candidate, evaluates it (via self-critique or external feedback), and revises. It works best when verification is reliable, answers are revisable, and the feedback signal is more accurate than the model's self-assessment. External feedback sources such as code execution and formal verification outperform pure self-critique because they break the correlation between the generator's errors and the critic's blind spots.
• Compute-optimal inference asks how to allocate a fixed token budget between breadth (more samples) and depth (longer reasoning chains). Easy problems prefer greedy decoding; hard verifiable problems prefer PRM-guided reranking with many samples; tasks where reasoning chains substantially improve per-sample accuracy prefer deeper chains over more samples.
• Scaling laws at inference time show sublinear but consistent returns from additional compute, following approximately $\text{Accuracy}(N) \approx a \cdot N^b + c$ with $b \in (0, 1)$. A small model with a large inference budget can match a large model with standard decoding on structured reasoning tasks, suggesting partial substitutability between model capacity and inference compute.
• Adaptive allocation routes queries to different compute budgets based on estimated difficulty, enabling production systems to achieve near-optimal quality at a fraction of the uniform-sampling cost.
• Practical limits include latency, cost, selector quality, diminishing returns, the verification bottleneck on open-ended tasks, and the ceiling imposed by systematic model errors that no amount of resampling can overcome.

As you move forward, the concepts from this chapter connect directly to the Retrieval-Augmented Generation chapter, where external knowledge is a form of test-time compute: instead of sampling more from the model, you query an external corpus and condition generation on the retrieved evidence. This is, in a sense, the most reliable form of external feedback possible, replacing model self-assessment with factual grounding from authoritative sources.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about test-time compute.