Reasoning and test-time compute

Separate three things usually conflated under "reasoning" in a language model: the computational effect of intermediate steps, their statistical effect, and their value as an explanation. Cover how chain-of-thought is elicited, the trace as a latent variable, test-time compute (parallel and serial), search-and-reasoning strategies (self-consistency, best-of-N, tree/graph search), and the honest distinction between a model that LOOKS like it reasons and verifiable correctness.

Track

Research

Module

9 · Agent cognition & reasoning

Prerequisites

The Transformer and the residual stream

When a model writes "let us think step by step" and produces a chain of intermediate steps before answering, something real changes — but what? There are three candidate answers and they do not exclude each other. The computational one: each generated token is another pass through the network, so the trace extends the effective DEPTH of the computation. The statistical one: the trace is a latent variable the model marginalizes over, and sampling several traces approximates the most probable answer better. The explanatory one: the trace describes the process by which the model reached the answer.

The first two have solid theoretical and empirical support today. The third is, as we will see, false in general and true only under conditions that must be measured. Keeping them apart is the prerequisite for building systems that use the model's reasoning WITHOUT trusting it more than warranted.

An autoregressive model that writes a trace z and then an answer y defines p(y | x) as a sum over all possible traces of p(z | x)·p(y | x, z). The answer the user wants is typically the most probable ANSWER — argmax over y of p(y | x). But greedy decoding and beam search approximate something else: the most probable TRACE and its answer. The two coincide when the probability mass concentrates on one trace; they diverge when many distinct, individually-unlikely traces lead to the same answer.

This gap is the formal argument for self-consistency. Consider a toy distribution over traces for a multiplication problem: suppose several correct decompositions each carry modest probability and all lead to the right answer, while a single trace with a dropped carry is the SINGLE most probable trace and leads to a wrong answer. The most probable trace is wrong, yet the correct answer can still hold the majority of the marginal mass. Sampling traces and voting on the final answer targets the mode of the marginal — which is not what maximum-probability decoding computes.

Trace (z)

The intermediate steps between question and answer. A latent variable: the quantity of interest is the answer, obtained by marginalizing over traces.

Coverage (pass@N)

The probability that at least one of N independent samples is correct: 1 − (1 − p)^N for per-sample success p. It is an upper bound on what any selection method can achieve — turning coverage into accuracy requires an external signal or an aggregation rule.

Faithfulness

A causal property, not a vibe. A trace is causally relevant if intervening on its logical content changes the answer; it is complete with respect to a factor if, whenever that factor changes the answer, the trace mentions it. Both are measurable; neither follows from the trace being plausible or well-written.

The computational mechanism is precise. A Transformer of fixed depth performs a constant number of sequential steps per token — attention and the feed-forward network are parallel over positions. Under limited numerical precision, a single forward pass belongs to a constant-depth circuit class, so a direct answer cannot, under standard complexity conjectures, solve problems that require many dependent steps. Generating tokens breaks that ceiling: each token is fed back as input, so the next pass can read the result of the previous one.

Expressivity results in the literature make this quantitative: with T steps of chain-of-thought, constant-depth Transformers with modest embedding size can solve anything a Boolean circuit of size T can, and the benefit concentrates on problems that are hard to parallelize. The crucial caveat: these are EXISTENCE results. They say weights EXIST that, with enough steps, implement the algorithm. They do NOT say training finds those weights, nor that a given model uses its trace that way, nor that the trace TEXT describes the computation. A striking data point in the source: with dense, specific supervision a Transformer can be trained to use meaningless filler tokens ("...") instead of a chain of thought on certain algorithmic tasks — if tokens help regardless of what they say, the visible trace need not show the computation.

synthetic — self-consistency: sample traces, vote the answer
# Approximates argmax_y p(y | x) = the MODE OF THE MARGINAL,
# not the answer of the single most-probable trace.
def self_consistency(model, x, N, temperature=0.7):
    votes = {}
    for _ in range(N):
        z, y = model.sample(x, temperature)   # a trace and its answer
        y = canonicalize(y)                    # equivalent answers must merge
        votes[y] = votes.get(y, 0) + 1         # one vote per sample
    return argmax(votes)                       # ties broken at random

# PROVEN behavior: variance reduction, NOT bias reduction.
# If the model concentrates mass on a WRONG answer, more samples
# converge to the wrong answer with increasing confidence.

Spending more compute at inference is today a capability lever comparable to scaling the model. There are two axes. The PARALLEL axis generates N independent candidates and aggregates them (best-of-N, voting, reranking); it is trivial to distribute and easy to analyze. The SERIAL axis lengthens a single trajectory — a longer trace, iterative revision, or step-by-step search guided by a verifier; it exploits information from earlier steps but has latency proportional to its length.

1. 1Estimate the per-sample success rate p for the kind of query, from a small pilot — this bounds everything that follows.
2. 2If a cheap, reliable checker exists, prefer generating several candidates and verifying over trusting one long trace.
3. 3If no checker exists, voting works only when the correct answer is the MODAL one; otherwise it amplifies the dominant error.
4. 4Allocate adaptively: one sample when the model is consistent, more samples or search only when the first samples disagree.
5. 5Normalize answers before aggregating (numbers, equivalent formulas, code) — poor normalization fragments the votes and defeats the whole point.

The source reports, under FLOP-matched conditions and in domains with verifiable answers, that inference compute can sometimes outperform a much larger model on problems where the small model already has a non-trivial success rate — while on the hardest problems, more pretraining still wins. It also reports NON-monotone behavior: tasks constructed so that reasoning longer REDUCES accuracy (distractor counting, spurious-feature regression, constraint tracking). Treat all of these as MEASURED under specific conditions in math and code, where verifiers exist; extrapolating to open-ended tasks is not justified.

A model reasoning step by step defines a distribution over traces; search strategies decide how to traverse it, using a generator (propose a step) and, optionally, an evaluator (score an intermediate state). Chain-of-thought is the minimal strategy: one trace, no evaluator, and its structural weakness is left-to-right decoding — an early error is never revised. Self-consistency samples many traces and votes. Tree-of-Thoughts makes intermediate states explicit, proposing several next steps per state, scoring each with an evaluator, and expanding the best (breadth-first with pruning, or depth-first with backtracking). Graph-of-Thoughts generalizes the tree to a graph with an aggregation operation — partial solutions can be merged, impossible in a tree. Monte Carlo Tree Search builds the tree asymmetrically with a selection rule that balances exploitation and exploration.

When does search beat voting? The source argues it depends on two checkable conditions: that errors are decided EARLY and irreversibly in the trace (search structure), and that an evaluator of intermediate states better than chance exists. Without the first, voting suffices; without the second, searching is spending budget to prune at random. A toy analysis shows evaluator noise compounds MULTIPLICATIVELY with depth: an evaluator that is "pretty good" per step can be poor at the problem level, and an uninformative evaluator reduces tree search to exactly what random pruning would give.

In a retrieval-augmented system, a trace that cites passages does NOT prove the answer depended on them; attribution is checked by intervention (remove the passage and see if the answer changes) or by a support verifier, not by reading the trace. In an agent, reasoning before an action helps choose the action and helps audit the process, but it is NOT an authorization: an impeccably reasoned plan can propose a disallowed action, and the decision to execute belongs to an external policy. This lab's thesis lands here precisely — the model proposes hypotheses and computations; the computations are delegated (to interpreters, solvers), the hypotheses are verified, and the decision is taken outside the model.

Delegating exact execution matters. Many arithmetic errors in a trace are not errors of SETUP but of EXECUTION — the model frames the problem correctly and drops a carry. Having the model emit an executable program that an interpreter runs keeps what the model does well (translating language into structure) and offloads what it does poorly (running many dependent steps without error), and yields an auditable, semantics-defined object instead of free natural language. Its limits are equally clear: a correct program for a MISREAD problem precisely computes the wrong answer, and executing generated code is an action with effects that requires isolation.

The honest core of the lesson: a correct-LOOKING chain is not a proof of correctness. Faithfulness studies in the source show traces that rationalize an answer actually decided by an unmentioned cue (reordering options so the "correct" one is always first can swing accuracy sharply, with the trace never naming the bias); traces whose removal or paraphrase does not change the answer (post-hoc); and that training can degrade faithfulness — reinforcement learning may increase the use of a hint while verbalization of it does not increase. A long, well-written trace reliably raises a human reader's confidence regardless of its correctness. That is the trap.

• ▸Execution errors: correct setup, wrong arithmetic — fixed by a deterministic tool, never by re-reading the trace.
• ▸Rationalization: the answer is decided by an unmentioned factor and the trace justifies it after the fact (a completeness violation).
• ▸Illogical shortcuts: steps that look rigorous but hide a leap, documented on hard problems.
• ▸Over- or under-deliberation: traces that grow without improving the answer, or that stop too early.
• ▸Reinforcement-learned models trained on VERIFIABLE rewards concentrate mass on trajectories the base could already produce (improving p, not coverage) in the studied methods and scales — a result about those methods, not a theorem; and they only work where a cheap, reliable checker exists (closed-form math, code with tests).

Expected direction: It is unsound because a plausible, well-written trace is weak evidence, not a guarantee: faithfulness studies show traces routinely rationalize answers actually driven by unmentioned factors, and are often post-hoc (the answer does not causally depend on the stated steps), so "the trace explains the match" does not establish that the match is correct — and a longer trace only raises reader confidence without raising correctness. A defensible design lets the model EXTRACT the fields and PROPOSE the correspondence, runs the arithmetic in code, checks the business rules in a deterministic rules engine, and keeps the trace only as context for a human reviewer. Approval depends on the external verification, never on the trace; the decision lives outside the model.

Greedy decoding and self-consistency optimize two different quantities. What are they, and when do they diverge?

Greedy/beam decoding approximates the most probable TRACE and returns its answer; self-consistency estimates the mode of the marginal over answers, argmax_y p(y | x). They coincide when mass concentrates on one trace, and diverge when many distinct, individually-unlikely traces lead to the same answer — then the single most-probable trace can be wrong while the correct answer holds the majority of the marginal mass.

In what sense is chain-of-thought "extra computation", and what do the expressivity results NOT establish?

Each generated token is another forward pass whose output can be read by the next pass, so a trace of T steps extends effective serial depth beyond the constant-depth limit of a single pass — letting constant-depth Transformers solve problems a direct answer cannot under standard conjectures. The results are EXISTENCE results: weights exist that implement the algorithm. They do not show training finds them, that a given model uses its trace that way, or that the trace text describes the actual computation.

Why does voting (self-consistency) reduce variance but not bias, and what practical failure does that imply?

Voting amplifies the per-sample majority in whatever direction it points; it converges to the model's modal answer. If the model places more mass on a wrong answer than on the correct one, more samples converge to the wrong answer with increasing confidence. So voting only helps when the correct answer is the modal one, and otherwise reliably entrenches the dominant error.

Give the two checkable conditions under which tree search beats voting, and why it fails without them.

First, errors must be decided early and irreversibly in the trace (search structure) — otherwise votes over final answers suffice and branching adds nothing. Second, there must be an evaluator of intermediate states better than chance — otherwise pruning is random. Evaluator noise also compounds multiplicatively with depth, so a weak step-level evaluator becomes a poor problem-level one; with an uninformative evaluator, tree search collapses to random pruning.