Reasoning in Language Models
Chain of thought, search over thoughts and verification.
A transformer spends a fixed amount of computation on each token it writes, so writing out intermediate steps buys it more computation, and theory makes that precise. Sampling many chains of thought, searching over them and checking them with verifiers turned this observation into the reasoning models of the mid-2020s. It also raised a sharp question: is the written reasoning the computation that actually produced the answer?
What you’ll learn
- State what chain of thought adds to a transformer's expressive power, from without it to exactly with polynomially many steps, and sketch why.
- Prove an exponential error bound for plurality voting, and explain why self-consistency cannot repair a wrong mode.
- Describe verifier-guided search, process versus outcome supervision, and reinforcement learning with verifiable rewards, including GRPO's group-relative advantages.
- Weigh the evidence on the faithfulness of chains of thought and on compositional generalization.
Chain of thought as computation
Chain-of-thought prompting (Wei et al., 2022) puts worked examples with intermediate steps in the prompt; "Let's think step by step" elicits steps without examples (Kojima et al., 2022); scratchpads trained models to write them (Nye et al., 2021). A decoder with layers performs sequential operations per token, but each new token can read every earlier one. So intermediate tokens give sequential steps, which matters for problems that are inherently serial.
Composing permutations of five objects is the hard case: given , decide whether their composition is the identity. Barrington (1989) proved this word problem -complete.
, and the inclusion is widely believed to be strict, though no proof is known. If it is strict, no direct-answer transformer of this kind solves the word problem for all .
With a chain of thought, emit the running product. Step reads input position and the previous token and applies a fixed lookup table, which a constant-depth network can do; steps solve the problem. The same construction runs any finite automaton, which gives the regular languages.
These are existence results. They do not say that training finds such solutions, or that a model trained on short chains extends to longer ones (length generalization). They also do not require the intermediate tokens to mean anything: Pfau, Merrill and Bowman (2024) trained transformers that solved certain tasks by writing meaningless filler tokens, so computation can hide in tokens whose text explains nothing. Faithfulness, the last step of this lesson, cannot be taken for granted.
Sampling, voting and search
Self-consistency (Wang et al., 2023) samples chains at a temperature above zero, extracts each final answer, and returns the plurality. It estimates , the most probable answer with the reasoning path marginalized out, rather than the answer of the single most probable path.
Fix a wrong answer and let . The are independent, lie in , and have mean at least :
The plurality can prefer only if gets at least as many votes, that is . Hoeffding's inequality for variables with range 2 bounds this:
A union bound over the wrong answers finishes the proof. Swapping the roles of and a more probable wrong answer gives the converse. ∎
Voting needs no verifier but can only sharpen the model's own beliefs. Search over thoughts goes further: Tree of Thoughts (Yao et al., 2023) treats partial chains as states, lets the model propose and evaluate next steps, and runs breadth- or depth-first search with pruning. Verifier-guided selection trains a model to score solutions and keeps the best of (Cobbe et al., 2021). Lightman et al. (2024) found that a process reward model, trained on about 800,000 human labels of individual steps, selected correct solutions to competition mathematics problems more reliably than an outcome model trained only on final answers.
A learned verifier is itself fallible. As grows, best-of- selection increasingly finds solutions that exploit its errors, and true accuracy can stop rising or fall, the overoptimization pattern Gao, Schulman and Hilton (2023) measured for reward models. A sound checker, such as a proof assistant's kernel, has no such failure mode: it can only fail to accept.
Training models to reason
STaR (Zelikman et al., 2022) bootstraps: sample rationales, keep those that reach the correct answer, fine-tune on them, and repeat. That is expert iteration, a Monte Carlo approximation to reinforcement learning with a binary reward. Reinforcement learning with verifiable rewards optimizes the reward directly, on problems whose final answers can be checked by a program (math answers, unit tests):
In GRPO, all eight sampled answers to a question are correct. Ignoring the KL penalty, how much does this question contribute to the policy gradient?
- A large positive push toward all eight answers
- Nothing: every reward equals the group mean, so every advantage is zero
- A negative push, because the question was too easy
- It depends on the length of the answers
Show the answer
B. Nothing: every reward equals the group mean, so every advantage is zero
Advantages are rewards relative to the group mean. With all rewards equal, every , as when all answers are wrong. Only questions that the model sometimes solves produce a learning signal, which is why training sets are often filtered for intermediate difficulty.
As of the mid-2020s, reasoning models such as OpenAI's o1 (2024) and DeepSeek-R1 (2025) are trained with large-scale reinforcement learning of this kind to write long chains of thought before answering, and their accuracy improves both with training compute and with how long they are allowed to think at test time. DeepSeek-AI reported that reinforcement learning with rule-based rewards alone, starting from a base model, produced long chains with self-checking and backtracking. In formal mathematics, language models generate proofs that Lean's kernel checks, so every accepted proof is correct, relative to the formal statement it proves.
How much of this is new capability is contested. Yue et al. (2025) compared pass@ at large and found that base models matched or exceeded their reinforcement-trained versions on several benchmarks, suggesting that the training mostly concentrates probability on solutions the base model could already sample. Others report gains on problems that base models essentially never solve. The answer may differ by task, model and training budget.
Faithfulness and generalization
A chain of thought is faithful if it reflects the process that actually determined the answer. The evidence is mixed at best:
- Turpin et al. (2023) added biasing features, such as always placing the correct answer of few-shot examples at option (A). Models' answers followed the bias, and their explanations rationalized those answers while almost never mentioning it.
- Lanham et al. (2023) intervened on chains by truncating them, inserting mistakes or paraphrasing them. How much answers depended on the chain varied widely across tasks, and on most tasks larger models depended on it less.
- Chen et al. (2025) gave reasoning models hints and found that, when a model used a hint, its chain of thought mentioned it often far less than half the time.
Faithfulness matters beyond explanation: reading chains of thought is one of the few available ways to monitor what a model is doing, and how robust that monitoring is remains debated.
Compositional generalization is the other recurring limit. Dziri et al. (2023) found that accuracy on multi-digit multiplication and logic-grid puzzles collapsed as the size of the problems' computation graphs grew, with errors compounding across steps. Changing the numbers and names in grade-school math problems, or adding irrelevant clauses, lowered accuracy (Mirzadeh et al., 2025); models trained on "A is B" did not infer "B is A" (Berglund et al., 2024); and on planning benchmarks, models produced many invalid plans (Valmeekam et al., 2023). Reasoning models improved many of these numbers. Whether that reflects general algorithms or broader coverage of familiar patterns is debated, and the "LLM-Modulo" proposal (Kambhampati et al., 2024) takes the neurosymbolic position: let models generate candidates and let sound external verifiers decide.
Key takeaways
- Direct-answer transformers with log-precision arithmetic lie in ; chains of thought add sequential steps, reaching all regular languages with steps and exactly with polynomially many. Existence is not learnability.
- Plurality voting errs with probability at most when the correct answer is the mode, and converges to the wrong answer when it is not: self-consistency sharpens beliefs but cannot correct them.
- Search over thoughts and verifier-guided selection add guidance; learned verifiers can be overoptimized, sound checkers cannot.
- Reasoning models are trained with reinforcement learning on verifiable rewards (GRPO's group-relative advantages need no critic); how much new capability this creates is contested.
- Chains of thought are often unfaithful, and compositional generalization remains fragile, which keeps external verification central.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Assuming , why can a log-precision transformer with chain of thought compose permutations of five objects when one that answers directly cannot?
- Chain of thought increases the model's precision
- Each written token can hold the running product, so sequential steps replace the network's fixed depth
- Chain of thought gives the model access to an external calculator
- The prompt's examples teach it the multiplication table of
Show the answer
B. Each written token can hold the running product, so sequential steps replace the network's fixed depth
Without intermediate tokens the computation is a constant-depth circuit, inside ; the word problem for is -complete. Writing makes each step a constant-size lookup.
For a question, a model's sampled answers are correct with probability 0.4, and two wrong answers each have probability 0.3. What happens to the plurality vote's accuracy as the number of samples grows?
- It tends to 1, because the correct answer is the most probable one
- It tends to 0, because the correct answer has probability below one half
- It stays at 0.4
- It tends to 0.5
Show the answer
A. It tends to 1, because the correct answer is the most probable one
Plurality needs only a margin over each competitor: here , and the error is at most , which tends to 0. A strict majority is not required.
Best-of- selection uses a learned verifier. As becomes very large, what can happen to the accuracy of the selected answers?
- It always rises toward 100%
- It stays exactly the same as for
- It can stop rising or fall, as selection exploits the verifier's errors
- It can only fall below the accuracy if the verifier is random
Show the answer
C. It can stop rising or fall, as selection exploits the verifier's errors
Selecting the maximum of an imperfect score over many samples favors samples where the score is most wrong, which is Goodhart's law. With a sound checker, such as a proof kernel or a complete specification, selection cannot be fooled in this way.
What did Turpin et al. (2023) show by adding biasing features to few-shot prompts?
- Chain of thought removed the bias entirely
- Models ignored the biasing features
- Biased prompts made models refuse to answer
- The features changed models' answers, while the explanations rarely mentioned them
Show the answer
D. The features changed models' answers, while the explanations rarely mentioned them
The answers tracked the bias (for example, the position of the correct option in the examples), and the chains of thought rationalized those answers while almost never referring to it: fluent explanations that were not faithful to what drove the prediction.
Further reading
- X. Wang et al., "Self-consistency improves chain of thought reasoning in language models," ICLR (2023).
- W. Merrill & A. Sabharwal, "The expressive power of transformers with chain of thought," ICLR (2024).
- H. Lightman et al., "Let's verify step by step," ICLR (2024).
- M. Turpin, J. Michael, E. Perez & S. R. Bowman, "Language models don't always say what they think: Unfaithful explanations in chain-of-thought prompting," NeurIPS (2023).
- DeepSeek-AI, "DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning," arXiv:2501.12948 (2025).