Reasoning and Test-Time Compute

What additional computation changes

Test-time compute is computation spent solving a new input. Here, the model’s learned parameters—the numerical values established during training—remain fixed. Additional work changes the solving procedure: the model can develop a solution before answering, generate several candidates, or revisit an attempt. A candidate is simply an attempted solution; producing one does not establish that it is correct. [1]

Training can make these operations more useful by changing what the model tends to generate. From scored attempts to updates explains that parameter adaptation. Executing a generation procedure faster is another separate intervention: speculative decoding accelerates generation while preserving a target distribution under its stated conditions. This chapter concerns choosing additional solving work and establishing whether that work helps.

The practical benefit is an opportunity to spend more effort where an immediate answer is inadequate. A thinking stage, described in Thinking Deeper in Gemini, adds intermediate generation before the final response. That opportunity also creates a tradeoff: more steps consume resources, and their usefulness depends on what they accomplish. [1]

Consider a constructed scheduling problem. Assign jobs A, B, and C to distinct slots 1, 2, and 3. A must precede B, and C must occupy slot 2. We will use this small problem where it makes differences between procedures visible. Its answers and candidate attempts are teaching examples, not observed model results.

Intermediate steps carry working state

Deliberation is work spent developing or reconsidering a solution before answering. Generated intermediate text can carry results into later steps: each generation step performs more computation using the existing text. A scratchpad holds this working state. The text consists of tokens, explained in Tokenization; Generation extends the prefix explains how earlier steps become input to later ones. [2][1]

Useful intermediate state reduces what remains unresolved. In the scheduling example, placing C in slot 2 leaves slots 1 and 3. Since A must precede B, A takes 1 and B takes 3. Each deduction enables the next. Decomposition serves the same purpose when it identifies prerequisite subproblems and passes their answers into later work; a list of subproblems without their dependencies does less. [3]

The 2021 scratchpad work made intermediate calculations and program states explicit. Some experiments trained models on those records, so their gains do not isolate extra computation at inference time. Chain-of-thought prompting asks for or demonstrates intermediate steps before the answer; Evaluate requests for intermediate steps explains that prompting method. [2][4]

A reasoning trace is a recorded sequence of intermediate steps. It can contain useful working state without fully explaining the model’s internal computation. In paired experiments with and without hints, tested reasoning models sometimes changed their answers toward a hint without acknowledging its influence in their traces. This establishes a gap between narrated reasoning and a full causal account, not deceptive intent. A correct answer alone cannot close that gap. [5]

Also distinguish a trace from a summary of it. Gemini’s documented thought summaries do not expose the complete internal thought sequence. The length of the displayed summary therefore does not measure all the reasoning work performed. [6]

Fresh attempts expand the candidate pool

Extending one attempt preserves its developing approach. Fresh sampling instead starts another attempt without supplying previous attempts or their feedback. Conditional on fixed inputs and sampling conditions, separate random draws can be independent while still frequently producing the same answer. Independence describes how attempts are drawn; diversity describes how their approaches or results differ. Sampling controls are introduced in Selection and stopping. [7]

The pool contains a valid answer, but generation has not identified it. Pass@k measures whether at least one successful candidate is available within an attempt budget; Attempt budgets explains its interpretation. Large Language Monkeys measured candidate coverage separately from selection. In its MATH experiments, tested selectors plateaued around one hundred samples while further sampling continued to reveal successful candidates. Some assessment checks were unavailable to the generating model. [8]

Fresh attempts are useful only if they produce alternatives worth considering and the system can recognize an acceptable result. Shared misconceptions can dominate the pool. A retry that receives a failed constraint is a different procedure: its generation is conditioned on new feedback, so it should not be analyzed as another independent draw from the original request. [9][10]

Agreement and aggregation

Self-consistency, introduced in 2022, samples several reasoning paths and aggregates their final answers. The implementation extracts an answer from each response, normalizes equivalent answers, and chooses the largest group. This addresses the brittleness of committing to one path: different successful paths may converge on the same answer. It requires meaningful answer equivalence, however, and a common mistaken answer can win. [11]

Normalize each scheduling response by listing slots in job order A, B, C. Attempts 1 and 2 both become X=(1,2,3), despite listing the jobs in different orders. Attempt 3 gives Y=(1,3,2), and attempt 4 gives Z=(3,1,2). X wins with two votes even though it puts C in the wrong slot. It has a plurality—the largest count—but not a strict majority, which would require more than half of four votes. [11]

Extraction is part of the algorithm. Treat unparseable responses explicitly, and define tie handling before observing results. A policy might obtain another sample within its budget or return an unresolved result. These are implementation choices. Voting itself supplies evidence of recurrence in the model’s output distribution, not satisfaction of the task. [12]

Generative aggregation performs a different operation. In Mixture-of-Agents, later models receive earlier responses and generate a new response from them. The output can combine useful material, but it is a new candidate rather than a counted or selected existing answer. Its new claims require assessment. Open-ended prose also makes equivalence harder: two responses may agree on one claim and conflict on another. [13]

What a verifier establishes

A verifier checks a stated property of a candidate. Its acceptance means that the candidate passed those checks under their assumptions. A test oracle decides whether observed behavior is acceptable; it can omit cases or encode the wrong expectation. Independently running a test does not repair a mistaken requirement shared by the implementation and test. Checks and their limits develops this distinction. [14]

Executable constraints

For the scheduling problem, acceptance requires all three jobs, allowed slots, distinct assignments, and both stated constraints. Checking only C’s slot would accept A=3, B=1, C=2 even though A follows B. Checking a partial assignment cannot establish complete success. The following Python function checks the full acceptance contract; it accepts data, not generated code.

def valid_assignment(candidate):
    if not isinstance(candidate, dict):
        return False
    if set(candidate) != {"A", "B", "C"}:
        return False

    slots = list(candidate.values())
    if not all(type(slot) is int and 1 <= slot <= 3
               for slot in slots):
        return False
    if len(set(slots)) != 3:
        return False

    return candidate["A"] < candidate["B"] and candidate["C"] == 2

There are six complete permutations to inspect. Requiring C=2 leaves (1,3,2) and (3,1,2); requiring A before B leaves only (1,3,2). This deduction establishes uniqueness for this example without assuming anything about a model. In a larger optimization problem, finding a feasible assignment would not establish that it is best. CP-SAT explicitly distinguishes feasibility from proven optimality. [15]

Other checks

Lean separates proof construction from acceptance: higher-level syntax and tactics produce terms checked by a kernel. Its axiom audit matters too. An axiom is an assumption, not a proved statement; inconsistent assumptions can undermine accepted proofs. [17][19]

Checking is not always easy relative to solving. Clinical answer verification can require much of the expertise needed to produce the answer, as discussed in From Ambient Documentation to Clinical Intelligence. Also identify who can access each check. A hidden reference answer may support final assessment without being available to guide a deployed solver. [20][8]

Selection under imperfect scores

Best-of-N generates N candidates, scores them, and chooses a preferred result. An application should distinguish eligibility—whether a candidate meets acceptance requirements—from ranking among eligible candidates. The planning system described in Real AI Agents Need Planning, Not Just Prompting combines alternative generation, pruning, and validation within a budget. Those operations require an explicit rule for the case where nothing qualifies. [21]

A learned scorer predicts a judgment from examples. An outcome scorer evaluates completed solutions; a process scorer evaluates intermediate steps. This distinction says what is scored, not how trustworthy the score is: both can be fallible predictions. Let’s Verify Step by Step trained a process scorer from human step judgments and an outcome scorer from final-answer checks. Outcome and process feedback explains their training. Ranking candidates only establishes a relative preference. Interpreting a score as a probability of correctness requires calibration evidence: observed correctness rates must match the probabilities claimed. [22]

Accepting X is a false acceptance; rejecting Y is a false rejection, relative to the complete constraint check. Audit both errors using independently assessed candidates. Shared generator–judge weaknesses can survive a separate judging call. Validate the judge explains how to establish the judge’s usefulness rather than assuming it from agreement or confidence. [23]

Increasing N can intensify this problem. In reward-model overoptimization experiments, a fixed generator produced candidates and a proxy scorer selected the highest score. Stronger selection eventually reduced quality according to a separate gold scorer. That reference was itself a model, but the experiment demonstrates that selection can exploit evaluator imperfections without updating generator weights. More search puts pressure on the acceptance rule as well as on the generator. [24]

Feedback changes the next attempt

Revision supplies an earlier candidate and feedback to the next generation. Its potential advantage is information: a failed check can identify an obligation that the candidate missed. An unguided instruction to reconsider supplies no external evidence. A model critique adds an interpretation; an executable counterexample adds a concrete case where the candidate fails. [25]

Counterexample-guided program synthesis provides a precise precedent. In the 2006 finite-program method, a synthesizer proposed a program matching accumulated examples. A verifier searched for an input violating the specification; each counterexample constrained the next proposal. Verification checked every replacement. The guarantees depended on the finite modeled domain and solver machinery. A language-model critique does not acquire those guarantees merely by resembling this loop. [26]

Self-Refine’s 2023 procedure used a language model for initial generation, feedback, and revision, retaining the input and prior iterations without updating weights. Its published algorithm stops at a limit or task-specific condition and returns the final revision. It does not independently preserve and select the best verified answer. [27]

That distinction matters because revisions can regress. Intrinsic-correction experiments with historical models found correct-to-incorrect changes without external feedback. Stopping whenever a hidden reference says the answer is correct gives a correction procedure privileged information. Those results concern the tested models and protocols; they are not an impossibility theorem for correction. [28]

Feedback must also be usable. How to Improve Your Agents describes faulty critiques propagating into revisions and stronger-model feedback that a smaller model cannot effectively follow. A practical response is bounded revision with candidate retention: preserve earlier eligible results, record which candidate each check concerns, and recheck the entire changed answer. This is a design choice motivated by regression risk, not a promise that every revision improves. [10]

The candidate A=1, B=2, C=3 fails because C must occupy slot 2. Moving C there without changing B would assign two jobs to the same slot. A revision must also preserve distinct slots and place A before B, then pass all checks again. The feedback identifies a defect; it does not replace the acceptance contract.

Expand and prune partial solutions

Search can avoid the cost of completing every attempted solution by checking alternatives while they are still unfinished. A search state records a partial solution; an expansion adds a possible next step. The frontier holds unfinished states available for further work. A search budget limits the work spent generating and evaluating those states. [29]

In the scheduling example, assigning only A=3 violates no constraint between jobs already assigned. Yet it leaves no later slot for B. The state is locally consistent but cannot be extended to a solution. Rejecting it is pruning. If the search had followed that branch, it can backtrack to an earlier state and try another choice. The branching figure shows these checks before completion.

The frontier creates an allocation choice: which state should be expanded next? A heuristic supplies an estimate of promise. Beam search retains a bounded set of alternatives at each depth and advances in depth order. Best-first search expands the highest-priority frontier entry, so it can compare states at different depths. Ordering, pruning, and stopping are separate decisions. A sequence-likelihood score estimates how probable text is under the model, not whether it solves the task. Pruning by an inaccurate score can discard the useful path; guarantees that depend on particular score properties do not transfer to arbitrary learned judgments. [30]

Selective exploration has a long history. Newell, Shaw, and Simon’s 1958 account of the Logic Theory Machine described symbolic proof search guided by heuristics when exhaustive exploration was impractical. Previously established theorems could support later proofs, but the search could still fail. The distinction between representing possibilities and allocating limited computation to them also matters when proposals and judgments come from learned models. [31]

Tree of Thoughts brought this structure to language-model reasoning in 2023. Its states contain intermediate thoughts—equations, words, or paragraphs, depending on the task—and models propose continuations and estimate their promise. These estimates guide search rather than prove that a branch will succeed. Searching proposed solutions is also distinct from executing actions that change an external system; Choose the next useful action explains that responsibility. [29]

Learn from sampled continuations

Monte Carlo tree search (MCTS) uses sampled continuations, or rollouts, to estimate whether a partial solution deserves more work. It selects a path, expands a state, evaluates a continuation, and updates visit counts and estimated returns—the rewards expected from those branches. This update is called backup. A 2006 branch-selection method adds an exploration bonus to those estimates, balancing exploitation of promising branches with exploration of less-visited alternatives. [32]

Suppose success earns 1 and failure 0. One successful rollout gives branch L an average return of 1; one failure gives R 0. If exploration later finds a success from R, its average becomes (0+1)/2 = 0.5. These estimates need not equal the branches’ true success rates. [32]

AlphaGo’s 2016 contribution showed complementary roles for learning and search. Policy predictions guided exploration; a value network and simulated play evaluated positions; search accumulated branch statistics before choosing a move. Go supplies precise legal moves, transitions, and terminal outcomes. This makes it a useful precedent for learned search, while sharply limiting what can be inferred about natural-language simulations from its success. [33]

Dialogue search illustrates the harder boundary. A model can propose conversational strategies, simulate possible replies, and score outcomes, as described in How to Improve Your Agents. Those simulated replies are predictions, not observations of actual people. Poor simulation or scoring can direct more search toward an attractive fiction. RL Environments and Simulators develops the fidelity problem. [34]

MCTS is worthwhile when what rollouts reveal improves later branch choices enough to pay for their cost. Compare it with fresh sampling and simpler partial search under budgets that include all simulations and evaluations. More elaborate search alone does not establish a better answer.

Total work and answer latency

Account for the complete procedure, not just its winning response. Repeated input processing, intermediate generation, final generation, verifier calls, and revisions all consume resources. So do candidates later rejected. A useful ledger records each operation’s candidate or request identity, measured usage, start and finish boundaries, and disposition: retained, rejected, interrupted, or unavailable. [35][36]

Configured effort and realized work differ. Gemini’s thinking documentation distinguishes thinking levels from numerical budgets; the latter guide generation and can be undershot or exceeded. Usage reports thought tokens separately from candidate-output tokens. Controls depend on the model and API, so configuration is not a substitute for accounting. [6]

OpenAI’s reasoning interface likewise reports reasoning-token usage. Its maximum output allowance includes reasoning, visible output, and non-visible formatting tokens. Exhausting that allowance can leave a response incomplete before any visible answer exists. A budget must leave room to construct and deliver the result, not merely to deliberate. [37]

Token totals are useful accounting units under identified conditions, but equal totals across models need not mean equal hardware work. Model size, tokenization, cached input processing, and execution configuration differ. Missing usage should remain unavailable rather than becoming zero. Record work observed before cancellation and distinguish requesting cancellation from confirmed execution cleanup; Cancellation and state release explains that boundary.

Parallel work changes elapsed time differently from total work. The critical path is the longest dependency path under stated operation durations. It determines earliest completion when prerequisites alone constrain starting. Resource contention can introduce further waiting. Shortening an operation off every critical path need not shorten completion. [38]

Measure the endpoint the application needs. A first stream event, first nonempty content, completed generation, and delivery of a checked answer are different boundaries. Queueing and network time also depend on the observer. Responsiveness and throughput explains serving measurements; AI Cost and Performance Engineering connects them to workload economics. [39]

Compare complete compute policies

A compute-policy comparison must identify what changed. Fix the model and version, matched task inputs, available tools, and final assessor when testing an inference procedure. Record sampling, runtime checks, allocation, stopping, and return rules. Develop settings on separate cases before final assessment. Baselines, budgets and repeated attempts explains these controls; here they prevent a better selector or privileged feedback from masquerading as a benefit of additional generation. [40]

A budget sweep evaluates several allowances. It can compare quality under a fixed resource limit or the resources needed to reach a quality target. An ablation changes a component to investigate its contribution. Measure returned-answer quality independently of the selector’s own score, and keep candidate coverage, abstention, deadline failures, and realized work separate. Repeated attempts and uncertainty in the difference help distinguish a useful change from sampling variation. [40]

Neither result supplies a universal conversion from reasoning tokens to accuracy. Nor does equal maximum allocation imply equal expenditure: one procedure may stop early, while another spends its allowance checking discarded candidates. A useful quality–cost frontier contains policies for which improving one objective requires sacrificing another, under comparable conditions. It must be built from measured complete policies, not inferred from a few headline scores. [43][44]

Why returns differ by task

Additional computation helps only through operations that address the limiting problem. Dependent deductions may benefit from extending working state. A brittle initial approach may benefit from fresh alternatives. An abundant pool of useful candidates with poor returned answers points toward selection. These diagnoses require separate observations of generation, checking, and delivery; apparent difficulty alone does not identify the bottleneck. [45][9]

The same search procedure can help at one budget or difficulty level and fail at another. In a study using PaLM 2-S* on MATH, beam search helped at small budgets, with diminishing gains as budgets grew. Stronger search sometimes reduced accuracy on easy problems; the authors attributed this to verifier exploitation. The group of hardest problems showed little progress under the tested methods. Difficulty therefore did not reliably identify where more work would help. [42]

Length can be an effect of difficulty rather than its remedy. Observing longer traces on hard inputs does not show that forcing longer traces improves those inputs. The s1 intervention demonstrates that extension conditions matter. Intrinsic-correction studies reveal another route to regression: further revision can replace a correct answer with an incorrect one. More work can therefore saturate or actively damage a result. [41][28]

The checking boundary changes across domains. Explicit finite constraints can support complete acceptance for their encoded problem. Code tests cover selected behavior and can share specification errors with the implementation. Open-ended expert judgments may lack a cheap, decisive checker. Clinical evaluation, for example, can require separate quality, safety, and boundary judgments; adding judges does not establish independent errors or complete coverage. [14][20]

Missing information creates a different limit. If two intended requirements are both compatible with everything supplied, deliberating over that unchanged input cannot establish which requirement the requester intended. Obtaining evidence or asking for clarification changes the information available. That is a distinct intervention from generating more possible answers. Select for sufficient coverage explains this context boundary.

The value of another step

A compute policy decides how much solving work to allocate and where to spend it. The marginal benefit is the improvement expected from an additional operation. It may be more useful to check a promising candidate than to generate another, or to advance a moderately difficult task than to keep attacking an unproductive one. Such choices require estimates based on outcomes, not just activity. [46]

These questions predate language models. Dean and Boddy’s 1988 time-dependent planning analysis considered procedures that could return their current answer when interrupted. The motivating robot had to leave enough time to react after deliberating. Competing computations could have delayed, diminishing, or bounded benefits. This anytime perspective makes a usable current answer and time remaining to act part of the design; it does not imply that successive language-model revisions improve monotonically. [47]

Rational metareasoning treats computation itself as a decision. Russell and Wefald’s 1989 formulation weighs further computation against acting now. A simplified engineering restatement uses utility, the value assigned to an outcome: [48]

Here, c is a proposed computation, a₀ the current decision, a_c the decision selected afterward, and U its utility. The expectation averages over possible computation results; C includes direct expense and delay in the same utility units. A feasible computation with positive expected net value can justify continuing. Estimating that value is itself costly. A one-step approximation can also miss work whose benefit appears only after several enabling steps. [48]

Adaptive-consistency provides a concrete runtime rule. It updates answer counts and stops when a statistical criterion sufficiently favors the leading answer, subject to a sample cap. Its confidence concerns which answer is most probable under sampling, not whether that answer is true. In the reported aggregate GPT-3.5 reasoning comparison, fixed sampling used 40 responses with 76.4% accuracy; adaptive sampling averaged 10 with 76.2%. The comparison counts responses, not equal token work or wall time. [49]

Disagreement, failed checks, and apparent progress are possible allocation signals, not universal measures of remaining difficulty. Develop their interpretation on separate tasks and test whether the resulting policy improves delivered outcomes. Retrospective labels based on many known results are not automatically available at runtime. What confidence predicts explains why the event being predicted must be explicit. [46]

Stop with an explicit result

A stopping rule ends further solving work. Acceptance is a separate decision about what the evidence supports. Sufficiently checked success, a validated agreement rule, repeated unproductive attempts, and a hard deadline can all end work for different reasons. The end of one generated sequence merely creates an opportunity for the surrounding policy to decide what happens next. [21][49]

Solver statuses illustrate the distinction precisely. CP-SAT separates FEASIBLE, OPTIMAL, INFEASIBLE, MODEL_INVALID, and UNKNOWN. A limit can produce UNKNOWN before finding a solution or proving infeasibility. Failure to find an answer is not proof that none exists. Language-model search earns comparable claims only when corresponding checks or proofs actually exist. [15]

Reserve time and capacity for final checking and delivery before authorizing more exploration. Output-budget exhaustion can leave no visible answer at all. Preserve eligible candidates separately from unfinished revisions, and attach acceptance evidence to the exact version checked. A newer candidate should not displace a supported one simply because it was generated last. [37][28]

Return an accepted result when the required evidence exists. Return a qualified best-effort result only when the task permits unresolved obligations and those limits are explicit. Otherwise defer, reporting what remains missing or requesting the necessary information. Deferral, risk and review capacity explains how to evaluate that choice. Resource exhaustion must never silently convert an unchecked candidate into an accepted answer. [50]

Policy reference

Open questions

1. 01

   Portable allocation remains difficult because agreement, failed checks, and apparent progress mean different things across tasks. Progress would be a policy using deployment-available signals that improves held-out outcomes across workloads while accounting for its own decision cost. Learned adaptive computation offers a direction, not an established universal rule. [52]

2. 02

   Selectors must remain useful as search exposes increasingly unusual candidates. This is difficult when tests omit obligations and model judges share the generator’s mistakes. Progress would include independent audits showing which errors emerge as search grows, and acceptance rules that preserve quality under that increased pressure. [53][54]

3. 03

   Comparing policies under real delivery deadlines requires joining quality evidence with all executed work, checker contention, cancellation, and finalization. Response counts alone cannot settle this comparison. Progress would be reproducible experiments measuring usable delivered answers and complete resource consumption under shared workload conditions. [35][55]