Reasoning & Test-Time Compute: theory

Self-consistency, best-of-N, Tree-of-Thoughts and MCTS over reasoning steps, process vs outcome reward models, self-correction and inference scaling laws.

A model's answer to a hard question gets better when it is allowed to think longer, or to try several times. Test-time compute spends extra computation at inference to improve answers without changing the weights. This page builds the main ways of doing it, each with a small example:

writing the reasoning out, step by step;
sampling many solutions and voting;
scoring the solutions with a verifier;
searching over partial solutions, up to Monte Carlo tree search;
revising an answer.

Chain of thought

Asking a model to write intermediate steps before the final answer, chain-of-thought prompting, substantially improves large models on arithmetic and multi-step problems (Wei et al., 2022). Each generated step becomes context for the next: the model computes in its own output.

Example. "A shop sells pens at 3 euros. Anna buys 4 pens and pays with a 20-euro note. How much change?" Answering directly requires doing two operations at once. With a chain of thought, the model writes "4 pens cost $4 \cdot 3 = 12$ euros. The change is $20 - 12 = 8$ euros. Answer: 8": each line is one easy step, and the result of the first is in the text when the second is written.

Reasoning models such as DeepSeek-R1 are trained with reinforcement learning on verifiable rewards (section 12) to produce long chains of thought by themselves.

Sampling many times: self-consistency and best-of-N

A single sampled chain can go wrong at any step, but different correct chains tend to reach the same answer, while wrong chains tend to disagree. Self-consistency (Wang et al., 2023) samples $N$ chains, extracts each final answer, and returns the most frequent one (majority voting). It needs no extra model, only a way to parse answers.

Example. Six sampled chains end with the answers 42, 42, 41, 42, (no answer found) and 7. Ignoring the missing one, 42 appears 3 times out of 5: it wins. No single chain had to be trusted.

With a verifier that gives each solution a score, there are two more options:

Best-of-N returns the single highest-scoring solution.
Weighted voting sums the scores of all the solutions that reach the same answer, and returns the answer with the largest total: it combines the agreement of voting with the judgement of the verifier.

Example. Four solutions with answers 12, 12, 15, 8 and verifier scores $0.5, 0.6, 0.9, 0.2$ . Best-of-N takes the highest score, $0.9$ : the answer 15. Weighted voting adds up per answer: 12 gets $0.5 + 0.6 = 1.1$ , 15 gets $0.9$ , 8 gets $0.2$ : the answer 12. The two methods disagree: the second trusts two moderate agreeing solutions over one confident outlier.

How far can sampling go? Brown et al. (2024) measured coverage, the fraction of problems solved by at least one of $k$ samples, and found it often grows log-linearly with $k$ over several orders of magnitude (each tenfold increase in samples adds roughly the same amount of coverage). Coverage is only useful if the right sample can be recognized: easy with unit tests or a proof checker, much harder with voting or an imperfect verifier.

Outcome and process reward models

An ORM (outcome reward model) scores a whole solution by its final answer. A PRM (process reward model) scores every intermediate step. Uesato et al. (2022) compared the two kinds of feedback; Lightman et al. (2023) collected PRM800K, 800,000 human labels on the steps of 75,000 solutions, and found that a process-supervised model selected correct solutions to MATH problems far more reliably than an outcome-supervised one.

To rank solutions they define the PRM score of a solution as the probability that every step is correct: the product of the per-step correctness probabilities. A solution with one wrong step and a lucky final answer gets a high ORM score but a low PRM score.

Example. Two four-step solutions. Solution A: every step is judged $0.9$ likely to be correct. Solution B: steps $0.99, 0.99, 0.3, 0.99$ : one step is doubtful, the others are excellent.

score A B

product $0.9^4 = 0.656$ $0.99 \cdot 0.99 \cdot 0.3 \cdot 0.99 = 0.291$

minimum $0.9$ $0.3$

last step only (outcome-style) $0.9$ $0.99$

An outcome-style score prefers B (its last step looks perfect), but the product and the minimum prefer A, because B has a step that probably went wrong.

score	A	B
product	$0.9^4 = 0.656$	$0.99 \cdot 0.99 \cdot 0.3 \cdot 0.99 = 0.291$
minimum	$0.9$	$0.3$
last step only (outcome-style)	$0.9$	$0.99$

A product of many probabilities becomes tiny: $0.99^{1000} = 4 \times 10^{-5}$ , and $0.5^{2000}$ is smaller than the smallest number a float64 can store, so it becomes exactly 0. That is why such scores are computed as a sum of logarithms, which stays a sensible number ( $-1386$ in that case).

Searching over steps: Tree of Thoughts

Sampling complete solutions wastes compute on chains that went wrong early. Tree of Thoughts (Yao et al., 2023) treats reasoning as search:

a state is a partial solution;
a proposer generates candidate next steps ("thoughts"), each giving a new state;
an evaluator, often the model itself prompted to judge, gives each state a value;
a search algorithm decides what to expand.

With breadth-first search, each level keeps the $b$ most valuable states, expands each into $k$ candidates, and scores them again: a beam search over thoughts instead of tokens (section 11).

Example. A toy puzzle: reach the number 10, starting from 1. A step either adds 3 or doubles; the value of a state is minus its distance from 10. Keep $b = 2$ states per level, 3 levels.

level candidates kept (value)

1 4, 2 4 ( $-6$ ), 2 ( $-8$ )

2 7, 8, 5, 4 8 ( $-2$ ), 7 ( $-3$ )

3 11, 16, 10, 14 10 ( $0$ ), 11 ( $-1$ )

The search finds 10. With $b = 1$ (greedy), level 2 keeps only 8, and level 3 offers 11 and 16: the best is 11. The path to 10 went through 7, which greedy search had thrown away because 8 looked better at that moment.

level	candidates	kept (value)
1	4, 2	4 ( $-6$ ), 2 ( $-8$ )
2	7, 8, 5, 4	8 ( $-2$ ), 7 ( $-3$ )
3	11, 16, 10, 14	10 ( $0$ ), 11 ( $-1$ )

Monte Carlo tree search

MCTS (Monte Carlo tree search) builds a search tree by repeating four phases (Browne et al., 2012):

Selection: from the root, move to the child with the highest UCT (Upper Confidence bounds applied to Trees) score until reaching a node that is not fully expanded.
Expansion: add one untried child.
Simulation: estimate the new node's value, by a random rollout to the end or with a value model.
Backpropagation: add the value to the statistics of every node on the path back to the root.

The UCT rule (Kocsis and Szepesvári, 2006) applies, at every node, the UCB1 rule for the multi-armed bandit problem (choosing which of several slot machines to play):

\mathrm{UCT}(j) = \frac{W_j}{N_j} + c \sqrt{\frac{\ln N_{\text{parent}}}{N_j}}

where $W_j$ is the total value collected through child $j$ , $N_j$ its number of visits (so $W_j / N_j$ is its average value), $N_{\text{parent}}$ the visits of its parent, $\ln$ the natural logarithm and $c$ a constant (such as 1.4). The second term grows for children visited rarely. It balances exploitation of moves that look good with exploration of moves that might be better. After the search, the move played is the most visited child. The same loop, with a language model proposing steps and a PRM or verifier as the value, is used for reasoning.

Example. A parent visited 10 times, $c = 1.4$ .

Child A: total value 6 over 8 visits: average $0.75$ , bonus $1.4\sqrt{\ln 10 / 8} = 0.75$ . Score $1.50$ .

Child B: total value 1 over 2 visits: average $0.50$ , bonus $1.4\sqrt{\ln 10 / 2} = 1.50$ . Score $2.00$ .

B is selected although its average is lower: it has been tried only twice, and might be better than it looks. A child never visited has score $\infty$ : every child is tried at least once.

A complete tiny run: the root has two actions, a (reward 0) and b (reward 1), and both lead to the end. Iteration 1 expands a (value 0); iteration 2 expands b (value 1); in iteration 3 the scores are $0 + 1.4 \cdot 0.83 = 1.17$ for a and $1 + 1.17 = 2.17$ for b: b is selected, and keeps being selected. After a few iterations b has the most visits: it is the move played.

Self-correction

A model can also revise its own answer: generate, critique, rewrite. Self-Refine (Madaan et al., 2023), where one model generates, gives itself feedback and refines, improved outputs on seven tasks ranging from dialogue responses to math reasoning. Huang et al. (2024) found that on reasoning tasks, models asked to review their own answers without external feedback often do not improve and can turn right answers into wrong ones. Revision helps most when the critique has a real signal behind it: a test that failed, an error message, a verifier.

Scaling test-time compute

Snell et al. (2024) asked how to spend a fixed inference budget. The best method depends on the difficulty of the question: in their experiments best-of-N was more effective on easier questions and at higher budgets, beam search against a PRM on harder ones and at lower budgets, and for revisions the best ratio of sequential to parallel sampling also depended on difficulty. Choosing the strategy per prompt ("compute-optimal" scaling) improved efficiency by more than 4× over best-of-N, and on problems where the smaller model already had some success, test-time compute let it outperform a model 14 times larger.

References

J. Wei et al., Chain-of-Thought Prompting Elicits Reasoning in Large Language Models, arXiv, 2022.
X. Wang et al., Self-Consistency Improves Chain of Thought Reasoning in Language Models, ICLR, 2023.
B. Brown et al., Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, arXiv, 2024.
J. Uesato et al., Solving math word problems with process- and outcome-based feedback, arXiv, 2022.
H. Lightman et al., Let's Verify Step by Step, arXiv, 2023. PRM800K; the PRM score as a product of step probabilities.
S. Yao et al., Tree of Thoughts: Deliberate Problem Solving with Large Language Models, NeurIPS, 2023.
L. Kocsis, C. Szepesvári, Bandit Based Monte-Carlo Planning, ECML, 282–293, 2006. UCT.
C. B. Browne et al., A Survey of Monte Carlo Tree Search Methods, IEEE Transactions on Computational Intelligence and AI in Games 4(1), 1–43, 2012.
A. Madaan et al., Self-Refine: Iterative Refinement with Self-Feedback, arXiv, 2023.
J. Huang et al., Large Language Models Cannot Self-Correct Reasoning Yet, ICLR, 2024.
C. Snell et al., Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters, arXiv, 2024.

Reasoning & Test-Time Compute