🧪 Test-Time Compute & Reasoning Models

Before you start

Use transformers for autoregressive generation and context costs, evaluation for held-out comparisons, and probability and statistics for sampling and conditional success rates. The optional training discussion builds on RL basics.

After this chapter, you should be able to distinguish longer generation, candidate sampling, and search; compute a simple candidate budget; explain why a selector can waste additional samples; and design adaptive allocation from measured quality-cost curves.

The problem: one answer is too unreliable, but more work costs money

A model may fail a difficult calculation on its first attempt while succeeding on another attempt or after checking intermediate results. More inference work can improve the delivered answer by changing the proposal distribution, exploring alternatives, or validating them. It can also repeat the same error or select a persuasive wrong answer.

Test-time compute changes the work performed for a request. Training-time compute changes model parameters and is amortized over later requests. Comparing the two requires the query volume, model, task distribution, latency requirements, and quality target. A better result from two differently trained models is not an isolated experiment on inference compute.

Worked example: five answers and three selection rules

For the toy problem 3x + 4 = 130, five sampled solutions produce:

Candidate	Final answer	Learned judge score
A	42	0.80
B	41	0.95
C	42	0.70
D	41	0.65
E	41	0.60

Self-consistency groups equivalent final answers and selects the most frequent one: 41 wins three to two and is wrong. Best-of-N with a learned score selects B and is also wrong. An independent substitution check finds 3 × 42 + 4 = 130, while 3 × 41 + 4 = 127; it accepts A or C. In this task the executable check directly matches the specified equation. More realistic code tests may cover only part of the required behavior.

This example separates proposal quality from selection quality. The candidate pool contains a correct answer, but a vote or a weak judge does not necessarily deliver it.

For an illustrative budget, suppose each candidate uses 100 generated tokens and a model-based judge uses 20 output tokens per candidate. At hypothetical output rates of $2 per million generator tokens and $1 per million judge tokens:

generator: 5 × 100 = 500 tokens → $0.0010
judge:     5 × 20  = 100 tokens → $0.0001
total output charge = $0.0011
one 100-token generation without judging = $0.0002

That is 5.5 times the output charge, excluding input tokens, hidden reasoning, tool work, and infrastructure. The rates are invented for arithmetic, not current vendor prices. Total tokens from different models are not interchangeable FLOPs or dollars. The deterministic substitution check has a different cost again.

Notation and the objective

Symbol	Meaning
N	Number of sampled complete candidates
p	Probability one candidate is correct under a fixed sampling policy
B	Per-request budget in a declared unit, such as tokens, dollars, or elapsed time
Q(B, x)	Expected delivered-answer quality for input x at budget B
Cgen, Cscore	Cost of generating and evaluating candidates
K, b, S	Kept beam width, expansions per beam, and reasoning-step depth

For independent candidates with correctness probability p, the probability that at least one is correct is 1 − (1 − p)ᴺ. At p = 0.4 and N = 5, it is 1 − 0.6⁵ = 0.92224. This is an oracle-availability calculation, not the accuracy of the chosen answer. A weak selector can miss the correct candidate, and correlated errors violate the independence assumption.

The production objective might maximize expected task utility minus compute cost and latency penalties. State the metric: correctness, helpfulness, complete proof validity, or downstream task success may lead to different allocations. “Think longer” is not an objective by itself.

Three ways to spend more inference work

Longer sequential generation allows intermediate calculations, revisions, or tool use before the final response. It increases sequential decoding work and can create opportunities for both correction and new mistakes. Generated reasoning text is not a guaranteed faithful explanation of the model's internal computation. A user-facing worked solution should be checked on its own merits.

Parallel candidate sampling generates several attempts. A scoring model or verifier can select the best, while self-consistency aggregates normalized final answers. These are different selection rules. Diversity matters: deterministic copies or strongly correlated samples may add little value. Parallel execution can reduce elapsed time when capacity is available, but total generation and scoring work still grows.

Adaptive revision or search spends further work after inspecting an initial result or partial solution. It can focus effort on promising alternatives, but needs a signal that discriminates useful progress. Self-critique without new evidence can simply restate the original error.

Do not collapse all three into one “reasoning token count.” Prefill, decoding, KV-cache storage, scorer calls, tools, and queueing contribute differently to latency and cost.

Verification determines the value of extra candidates

An outcome reward model (ORM) scores a completed solution based on outcome labels or preferences. It can read the full solution and need not output a binary score. A process reward model (PRM) scores steps or prefixes, potentially catching errors before the solution finishes.

Specify what a process label means. Human labels of local mathematical validity differ from rollout-derived estimates of whether the current policy can finish correctly from a prefix. A flawed prefix might be repaired later; a valid but hard prefix might have no successful sampled continuation. Those labels should not be treated as equivalent truth.

PRM scores can guide pruning, but false negatives remove valid paths and false positives waste search. Minimum or product aggregation of step scores are heuristics; they are not automatically calibrated probabilities that an entire solution is correct. Product scores can strongly favor shorter traces unless the probabilistic interpretation and length handling are justified.

Evaluate the selected output under increasing search budgets. Selection exposes the scorer to extreme candidates it did not see during training, creating reward over-optimization. An improving oracle pass rate with flat selected accuracy suggests the selector is the bottleneck. Use independent tests or expert review for this diagnosis.

Allocate budgets using measured curves

Collect held-out queries and run a small grid of budget/strategy combinations, keeping the model and grading fixed. Estimate quality, latency distribution, and actual cost by query category. Label which queries benefit from more work; surface difficulty is only a proxy for that benefit.

A router may choose a direct answer, a longer attempt, extra samples, a tool check, or escalation. Use calibrated signals such as verifier results, task features, or disagreement. Model confidence language is not a calibrated probability. In production, evaluate routing decisions on held-out counterfactual runs or controlled exploration; observing only the chosen budget can hide systematic routing mistakes.

For an illustration with 1,000 requests, suppose 800 are assigned 200 output tokens and 200 are assigned 2,000. The total is 800 × 200 + 200 × 2000 = 560,000 output tokens. Giving every request 2,000 uses 2,000,000 tokens. At a hypothetical uniform $2 per million output tokens, the charges are $1.12 versus $4.00, excluding other costs. This is a 72% token reduction; quality retention must be measured, not inferred from the allocation.

Enforce per-request and service-wide budgets. Stop after verified completion, when a supported API budget is exhausted, or when another attempt has insufficient expected benefit. Repeated agreement is evidence to calibrate, not proof of correctness. Do not assume hidden reasoning tokens are observable or can be safely interrupted at arbitrary points.

Optional: beam search and MCTS

In step-level beam search, retain K partial solutions, expand each into b candidates, score them, and retain a new beam. With S rounds and average ℓ generated tokens per expansion, generator work is on the order of K b S ℓ tokens, plus scoring and prefix-processing cost. Early rounds, caching, shared prefixes, and variable lengths change actual work. An O(KS) comparison that omits branching, token length, and scorer cost is incomplete.

Monte Carlo Tree Search repeats selection, expansion, evaluation, and backup. Exploration bonuses balance revisiting promising branches against less explored ones. Leaf estimates can come from a value/PRM model or from complete rollouts scored by an outcome checker; MCTS does not inherently require a PRM. Search assumptions are harder in open-ended language than in games with known legal transitions and exact terminal outcomes.

Neither beam search nor MCTS is universally strongest. Both can focus computation on a scorer's blind spots and prematurely discard useful paths. Compare delivered quality at matched total cost, including verifier work and parallel capacity, rather than matched candidate counts alone.

Optional: how training prepares a model to use more compute

SFT can teach useful solution formats, demonstrations, and tool-use patterns. RL can reward sampled outputs using learned or verifiable signals; RLVR names the verifiable reward source, not a mandatory algorithm or absence of SFT. A test passing is only as meaningful as the specification it checks.

The DeepSeek-R1 report distinguishes R1-Zero, which applies RL to a pretrained base without a preceding post-training SFT stage, from the full R1 pipeline. The latter includes cold-start SFT, reasoning-focused RL, rejection-sampled reasoning plus general SFT data, and further RL. Distilled students learn from generated examples. “No post-training SFT” does not establish that a pretrained model never encountered demonstrations or reasoning patterns.

Public reports support claims about particular models and experiments. They do not reveal every proprietary model's exact reward mix or inference search implementation. Keep documented training observations separate from hypotheses about hidden mechanisms.

Check your understanding

At per-candidate correctness p = 0.2, what is the independent probability of at least one correct answer among four candidates? Does majority voting attain it? A beam retains K = 3 prefixes, expands b = 4 candidates each round, and runs S = 5 rounds of ten-token expansions; what is the rough expansion-token budget, ignoring startup and reuse?

Solution

The availability probability is 1 − 0.8⁴ = 0.5904. Majority voting need not select a correct answer even when one exists, and correlated candidates invalidate the calculation. The rough beam expansion budget is 3 × 4 × 5 × 10 = 600 generated tokens, plus scoring, prefix processing, and other work. Candidate availability and delivered accuracy must be evaluated separately.

Continue learning

RLHF and DPO explains preference and reward objectives, agentic AI adds bounded tool execution, and safety and alignment covers harmful behavior and reliability limits under stronger optimization.

References

• Snell et al., Scaling LLM Test-Time Compute Optimally: prompt-dependent allocation and compute-matched experiments.
• Wang et al., Self-Consistency: sampling reasoning paths and aggregating final answers.
• Lightman et al., Let's Verify Step by Step: process supervision and PRM800K.
• DeepSeek-AI, DeepSeek-R1: documented R1-Zero, R1, and distillation experiments.