Chapter 5.1 β€” Reasoning and Test-Time Compute

Contents

  1. Picking up where training leaves off
  2. Chain-of-thought: capability that was already there
  3. Self-consistency: marginalizing out the noise in a single chain
  4. From prompting trick to training objective
  5. Reinforcement learning on verifiable rewards
  6. DeepSeek-R1: a transparent case study
  7. o1 and the public arrival of test-time compute scaling
  8. Interview angle
  9. Self-check questions
  10. Sources

1. Picking up where training leaves off

Part IV ended on a deliberately unsettling note: a well-pretrained, well-aligned model is only "finished" for the capabilities that existed at the moment its training data was frozen and its RLHF or DPO pass completed. Everything in that part β€” tokenization, the pretraining objective, scaling laws, distributed training, preference optimization β€” describes how to turn compute and data into a fixed set of weights. Once training stops, the weights stop changing. But it turns out that the weights encode more than what a single greedy forward pass reveals, and the last few years of LLM engineering have been substantially about a different lever than more parameters or more pretraining tokens: how much computation the model is allowed to spend at inference time, per query, before it commits to an answer. This chapter is about that lever, and about how it went from a prompting curiosity to a first-class training objective in its own right.

This matters for the same reason the scaling laws in Chapter 4.3 mattered: it changes what "bigger" means. Scaling laws describe a relationship between training compute, model size, data, and loss. Test-time compute describes a second, largely independent axis β€” for a fixed model, how much better can it do if you let it think longer? The two axes are complementary, not competing, and a mature understanding of frontier LLM capability now requires reasoning about both.

2. Chain-of-thought: capability that was already there

The first clean demonstration that inference-time behavior alone could unlock large capability gains, with zero change to model weights, came from chain-of-thought prompting. Wei et al. (2022) showed that if you prompt a sufficiently large language model with a few worked examples that include explicit intermediate reasoning steps β€” rather than just a question followed directly by an answer β€” the model's accuracy on multi-step arithmetic, commonsense, and symbolic reasoning tasks jumps substantially, sometimes from near-random to strongly above baseline. Nothing about the model changed. The only thing that changed was the shape of the output it was asked to produce: instead of jumping straight to a terse final answer, it was induced to write out a plausible derivation first, token by token, and then state the answer.

Why would this help at all, given that the model's parameters are identical in both cases? The autoregressive factorization from Chapter 1.1 gives the mechanical answer: $P(x_i \mid x_1, \ldots, x_{i-1})$ conditions on everything generated so far, including the model's own prior tokens. When a model is forced to answer immediately, it has to produce the correct final token essentially "in one shot," with no intermediate computation externalized into the context window it can then condition on. When it is allowed to generate intermediate reasoning first, each reasoning step becomes additional context that the next step's prediction can condition on β€” the model is, in effect, using its own output as scratch space, spreading a hard, high-variance inference over many easier, lower-variance next-token predictions. This is a big deal precisely because it implies that the raw next-token-prediction capability trained into the weights during pretraining already contained latent reasoning ability that terse, direct-answer prompting had simply never surfaced. The capability was there; the elicitation method was the bottleneck.

This finding also reframed what "capability" even means for a language model. A model's competence is not a single fixed number determined only by its weights β€” it is a function of weights and inference procedure together. That reframing is the conceptual seed for everything else in this chapter.

3. Self-consistency: marginalizing out the noise in a single chain

Chain-of-thought prompting has an obvious weakness: a single sampled reasoning chain can go wrong at any step, and one bad step usually corrupts the final answer even if the model's underlying competence was sufficient to solve the problem. Wang et al. (2022) proposed a refinement that treats this as a sampling problem rather than a prompting problem: instead of generating one reasoning chain per question, sample several independent chains (using temperature or nucleus sampling for diversity), extract the final answer each chain arrives at, and take a majority vote across them. This is called self-consistency, and it improved accuracy on reasoning benchmarks substantially beyond greedy or single-sample chain-of-thought decoding.

The statistical intuition is straightforward once you see the reasoning chain as a latent variable being marginalized out. Formally, chain-of-thought treats the answer $a$ as depending on the question $q$ through a latent reasoning path $r$: $P(a \mid q) = \sum_r P(a \mid r, q) P(r \mid q)$. A single greedy or sampled chain is one draw from $P(r \mid q)$, and conditioning the answer on that one draw is a high-variance estimate of the true marginal. Sampling many chains and voting on the resulting answers approximates that marginalization directly β€” it is Monte Carlo estimation applied to reasoning paths instead of to, say, an expectation in a policy gradient. Errors that are idiosyncratic to a particular sampled path (an arithmetic slip, a wrong case split) tend not to be correlated across independent samples, so they wash out under voting, while the "signal" β€” reasoning paths that are actually valid β€” reinforces itself because multiple independent valid paths tend to converge on the same correct answer. This is the same logic that makes ensembling or bagging work in classical statistics, applied here to a model's own stochastic reasoning rather than to independently trained models.

Self-consistency is also the first appearance in this book of a pattern that becomes central later in the chapter: spending more inference-time compute (more samples, more generated tokens) as a direct, controllable way of buying more accuracy, with no retraining required. It is a primitive form of test-time compute scaling, discovered as a prompting-and-sampling trick before it was understood as a general paradigm.

Tree-of-thought, introduced by Yao et al., generalizes the same underlying instinct β€” sample more, don't commit to one path β€” into an explicit search procedure rather than independent chains voted on only at the end. Instead of generating complete reasoning chains and aggregating their final answers, tree-of-thought treats reasoning as a search over a tree of partial thoughts: at each step, the model generates several candidate continuations of the reasoning so far, an evaluation step (the model judging its own partial progress, or a heuristic) scores how promising each partial path looks, and the search explores the more promising branches further while pruning the rest, with the option to backtrack if a branch that looked promising turns out to be a dead end. This buys something self-consistency's independent-chains-then-vote structure cannot: the ability to abandon a bad direction partway through instead of only after generating a complete, possibly wasted chain, at the cost of needing an explicit evaluation function and a more expensive search procedure per problem.

4. From prompting trick to training objective

Chain-of-thought prompting and self-consistency both treat reasoning as something you elicit from a frozen, already-trained model through clever inference-time procedure β€” better prompts, better sampling and aggregation. They do not change what the model was trained to do. The natural next question, and the one that defines the current frontier, is: what if you trained the model specifically to produce long, effective, exploratory reasoning traces, rather than relying on inference-time tricks layered on top of a model that was never optimized for that behavior in the first place?

This shift matters because prompting can only elicit reasoning patterns that are already latent in the pretrained distribution, in roughly the form the training data expressed them. Human-written text on the internet mostly shows finished reasoning β€” clean derivations, confident conclusions β€” rather than the messy, exploratory process of getting there: false starts, self-correction, backtracking, checking an intermediate result against a different method. If a capability is genuinely useful (catching your own arithmetic error mid-derivation, abandoning an unpromising approach halfway through) but rarely modeled explicitly in pretraining data, no amount of prompting can make the model reliably do it, because the underlying distribution simply doesn't put much probability mass there. The fix is to make the model's own long-form reasoning behavior itself the object of an optimization process, rather than something reverse-engineered from imitation of human-written text.

5. Reinforcement learning on verifiable rewards

The training recipe that emerged to do this leans on a specific property of certain task domains: verifiability. For math problems and many code tasks, you can check whether a final answer is correct β€” the numeric answer matches, the unit test passes β€” cheaply, automatically, and unambiguously, without needing a human rater or a learned reward model of the kind used in RLHF (Chapter 4.5). This is a crucial difference from the RLHF setting, where the reward signal comes from a model trained to imitate human preference judgments and is therefore noisy, expensive to obtain at scale, and vulnerable to reward hacking. A verifiable reward β€” did the code compile and pass the tests, does the final boxed number equal the ground truth β€” is close to ground truth by construction.

It's worth being precise about what kind of verifiable reward this is: an outcome reward, checking only the final answer, with every intermediate reasoning step scored implicitly and identically through whatever credit the RL update assigns backward from that one final signal. Process reward models (PRMs), studied in detail by Lightman et al., take the opposite approach: train a model to score the correctness of each individual step in a reasoning trace, not just the final answer, using step-level human or model-generated labels, and use that denser per-step signal to train against instead of (or alongside) the sparse outcome signal. Lightman et al. found process supervision measurably outperforming outcome supervision on hard math benchmarks, on the reasoning that a dense, step-by-step reward gives the model useful gradient signal even on trajectories that ultimately land on a wrong final answer, rather than treating an entire long trace as equally (un)rewarded just because the last number was wrong. The cost is that a PRM reintroduces exactly the fragility a verifiable outcome reward was chosen to avoid in the first place β€” it's a learned model of step-level correctness, not a program-checkable oracle, so it can be gamed and it requires expensive step-level labels to train, which is precisely why outcome-reward RL on domains with cheap, automatic final-answer verification became the more scalable default this section describes, with PRMs remaining an active area of research for domains where a denser training signal is worth that cost.

This opens up a reinforcement learning loop that looks structurally like RLHF's PPO-based optimization, but with the reward model replaced by a program-checkable oracle: the policy (the language model) generates a long reasoning trace followed by a final answer, the trace-plus-answer is scored automatically against a verifier, and the policy is updated to increase the probability of trajectories that lead to verified-correct answers. Because the reward is cheap and reliable, this loop can be run at a scale that would be prohibitive with human-in-the-loop reward modeling, and because nothing about it depends on imitating a fixed dataset of human demonstrations, the model is free to discover its own reasoning strategies β€” including long chains involving self-correction, alternative-method verification, and abandoning unpromising directions β€” as long as those strategies raise the probability of eventually landing on the verified-correct answer. Crucially, once trained this way, the model does not need to be prompted into producing reasoning traces at inference time; producing them is now simply what it does by default, and the length of the trace becomes a natural, learned, per-problem-difficulty quantity rather than a fixed prompting template.

This is the technical core of the "test-time compute scaling" paradigm: model size and pretraining compute (Chapter 4.3) determine one axis of capability, and the amount of inference-time computation the model chooses to spend generating its reasoning trace before answering determines a second, largely orthogonal axis. A smaller model allowed to reason for longer can, on some tasks, match or beat a larger model forced to answer immediately β€” which has real consequences for how a practitioner should think about the size-versus-latency-versus-accuracy tradeoff in production systems, a topic this book returns to in the systems-design chapter of Part VI.

6. DeepSeek-R1: a transparent case study

DeepSeek-R1 (DeepSeek-AI, 2025) is worth studying closely because it is one of the more transparent public accounts of this training recipe actually working, at frontier scale, described in enough detail to reason about concretely rather than through blog-post marketing language. The reported recipe applies large-scale reinforcement learning with verifiable rewards β€” correctness on math and code tasks checked automatically β€” directly against a base model, without an intervening supervised fine-tuning stage of the kind normally used to first teach a model to produce well-formatted, instruction-following output. The specific RL algorithm is GRPO (Chapter 4.5), which is a large part of why this recipe is affordable at the scale DeepSeek-AI ran it at: GRPO's whole design point is removing PPO's separate value network by estimating a token's advantage from the relative rewards of a sampled group of completions to the same prompt, which matters enormously here because a verifiable-reward RL loop like this one is already generating and scoring many long reasoning traces per prompt β€” GRPO gets its baseline essentially for free out of that same batch of samples, rather than needing a whole second learned network to provide one. The striking empirical claim is that reasoning behaviors resembling deliberate, exploratory thought β€” the model reconsidering an approach, checking its own work, allocating more generation to harder subproblems β€” emerge from this RL process itself, as a consequence of optimizing for verified correctness over long trajectories, rather than being hand-specified or distilled from an existing reasoning-capable model. DeepSeek-AI also reports a distillation step, transferring the reasoning patterns learned in the large RL-trained model into smaller dense models via supervised fine-tuning on the larger model's outputs, which is itself an important practical point: once you have a strong reasoning teacher, propagating that behavior to smaller, cheaper models does not require repeating the expensive RL process from scratch.

For an interview-level understanding, the important takeaways from DeepSeek-R1 are not the specific benchmark numbers but the structural claims: verifiable-reward RL, applied directly and at scale, is sufficient to elicit long, effective reasoning traces without hand-authored chain-of-thought demonstrations; the resulting behavior transfers via distillation; and the entire recipe is a training-time investment that pays off as a controllable test-time compute budget at inference.

7. o1 and the public arrival of test-time compute scaling

OpenAI's o1 is the model that made this paradigm broadly visible outside the research community, largely by making "the model thinks before it answers, and you can see it taking longer to do so" a mainstream product experience rather than a research footnote. It's worth being precise, for interview purposes, about what is and isn't a citable claim here: the original "Learning to Reason with LLMs" announcement of o1 was a blog post, not a peer-reviewed or arXiv-indexed paper, and should not be cited as one. The citable academic document is the later o1 System Card (OpenAI, 2024), which is the appropriate reference when discussing o1's reported safety evaluation and capability characteristics in a way that needs a real citation trail. This distinction β€” between what a lab announces publicly and what is actually available as a verifiable, citable technical document β€” is itself a useful thing to be careful about when discussing frontier capabilities in a technical interview, since overclaiming a blog post as "the o1 paper" is an easy and avoidable precision error.

The specific empirical claim behind "test-time compute scaling," made concrete in OpenAI's own reporting on o1, is a curve directly analogous to the pretraining scaling laws of Chapter 4.3: plot task accuracy against the amount of compute spent at inference time (more sampled tokens of reasoning, roughly), and the relationship is smooth and improving, not a step function or a quickly-saturating one. That's the precise sense in which test-time compute is described as a second, largely orthogonal scaling axis to pretraining compute β€” not just "longer answers tend to help sometimes," but a curve with the same well-behaved, keep-paying-for-more-and-keep-improving shape that motivated pouring ever more compute into pretraining in the first place, now available as a knob a practitioner can turn per-request rather than only once, at training time, for every future request a model will ever serve.

Taken together, chain-of-thought prompting, self-consistency, RL on verifiable rewards, and the public arrival of models like o1 and DeepSeek-R1 trace a single arc: reasoning ability that was initially something you had to coax out of a frozen model through clever prompting became, over a few years, something trained directly into the model's default behavior, with the amount of inference-time "thinking" becoming a deliberate, tunable resource. That shift changes how a model's knowledge is used at answer time, but it does nothing to change what the model knows in the first place β€” its parametric memory is still exactly as frozen and exactly as fallible as it was at the end of pretraining. That limitation, and the standard engineering fix for it, is where the next chapter picks up.

8. Interview angle

Q: Why does chain-of-thought prompting improve accuracy if the model's weights never change? A strong answer invokes the autoregressive factorization directly: each generated token conditions on all prior tokens, including the model's own previously generated tokens. Forcing an immediate answer requires the correct output in a single forward pass with no externalized intermediate computation; allowing intermediate reasoning lets the model use its own generated context as scratch space, turning one hard prediction into a sequence of easier, conditioned ones. The underlying capability was latent in the pretrained distribution; the direct-answer prompting format was simply failing to elicit it.

Q: How does self-consistency differ from simply asking the model to "double-check its work" in one pass? A strong answer frames it as marginalizing over a latent reasoning-path variable via Monte Carlo sampling β€” multiple independent chains, majority vote on the extracted answer β€” rather than asking a single generation to self-critique, which is still one sample and inherits that sample's idiosyncratic errors. It should also note the cost tradeoff: self-consistency multiplies inference cost by the number of sampled chains.

Q: What's the actual difference between prompting-based chain-of-thought and the RL-trained "reasoning model" paradigm (o1, DeepSeek-R1)? A strong answer distinguishes elicitation from training: chain-of-thought and self-consistency extract latent behavior from a model via inference-time procedure alone, with no gradient updates involved, and are bounded by whatever reasoning patterns already exist, weakly, in the pretrained distribution. RL on verifiable rewards directly optimizes the model to produce effective long reasoning traces as its default behavior, allowing it to discover reasoning strategies not well-represented in the pretraining data, and makes trace length itself a learned, controllable quantity rather than a prompting artifact.

Q: Why is a verifiable reward signal such a big deal compared to the reward models used in RLHF? A strong answer notes that RLHF reward models are themselves learned approximations of human preference, trained on a finite, noisy set of human judgments, and are vulnerable to reward hacking (Chapter 4.4–4.6 material from Part IV). A verifiable reward β€” correctness of a math answer, passing a test suite β€” is close to ground truth by construction, cheap to compute at scale, and doesn't require human-in-the-loop labeling, which is why it enables RL at a scale that would be impractical with learned reward models alone. A strong answer also notes the tradeoff: verifiable rewards only exist for domains with checkable ground truth, which is why this paradigm is strongest in math and code and less directly applicable to open-ended generation.

Q: If I have a fixed inference latency budget, how should I think about model size versus test-time compute? A strong answer treats these as two separate levers along different axes of the capability surface described in Chapter 4.3's scaling laws, and notes that a smaller model given a larger reasoning budget can sometimes match a larger model answering immediately, which has direct implications for cost-latency-accuracy tradeoffs in a production system β€” a theme picked up again in the systems-design chapter of Part VI.

9. Self-check questions

  1. Using the chain-rule factorization from Chapter 1.1, explain mechanically why generating intermediate reasoning tokens before a final answer can change the probability the model assigns to the correct final answer, even though the weights are unchanged.
  2. What latent variable does self-consistency marginalize out, and via what estimation procedure?
  3. Why can chain-of-thought prompting only elicit reasoning patterns that were already latent in the pretraining distribution, and why is that a limitation that RL-based training addresses differently?
  4. What makes a reward signal "verifiable," and why does verifiability matter for the scale at which RL training can be run?
  5. What is the key structural claim of DeepSeek-R1's reported recipe, independent of its specific benchmark numbers?
  6. Why is it inaccurate to cite the original o1 announcement as an academic paper, and what is the correct citable document?
  7. In what sense are test-time compute scaling and the pretraining scaling laws of Chapter 4.3 "orthogonal" axes of capability?

10. Sources

  • Wei, J., Wang, X., Schuurmans, D., et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. NeurIPS 2022. arXiv:2201.11903. https://arxiv.org/abs/2201.11903
  • Wang, X., Wei, J., Schuurmans, D., et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models. ICLR 2023. arXiv:2203.11171. https://arxiv.org/abs/2203.11171
  • Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y., & Narasimhan, K. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. NeurIPS 2023. arXiv:2305.10601. https://arxiv.org/abs/2305.10601
  • Lightman, H., Kosaraju, V., Burda, Y., et al. (2023). Let's Verify Step by Step (process reward models). arXiv:2305.20050. https://arxiv.org/abs/2305.20050
  • DeepSeek-AI (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. arXiv:2501.12948. https://arxiv.org/abs/2501.12948
  • OpenAI (2024). OpenAI o1 System Card. arXiv:2412.16720. https://arxiv.org/abs/2412.16720 (note: the original "Learning to Reason with LLMs" announcement was a blog post only, not on arXiv)

Self-check quiz

Test your understanding of this chapter with a short quiz β€” a mix of concept questions and quick calculations.

Why does chain-of-thought prompting improve accuracy even though the model's weights never change?

Explanation: The autoregressive factorization means each reasoning step becomes additional context the next step can condition on β€” spreading a hard, high-variance prediction over many easier ones.

What does self-consistency do differently from a single chain-of-thought generation?

Explanation: This is Monte Carlo estimation applied to reasoning paths: idiosyncratic per-chain errors tend not to correlate across samples, so they wash out under voting.

Why is a verifiable reward (e.g., a math answer checked against ground truth) considered a big advantage over RLHF's learned reward model?

Explanation: A learned RLHF reward model is a noisy approximation of human judgment; a verifiable reward (code compiles and passes tests, final answer matches) is essentially ground truth itself.

What is the key structural claim of DeepSeek-R1's reported training recipe?

Explanation: Reasoning behaviors resembling deliberate thought emerged from the RL process itself, as a consequence of optimizing for verified correctness over long trajectories.

Each independently sampled reasoning chain has a 60% chance of reaching the correct answer. If you sample 5 chains and take a majority vote (at least 3 of 5 correct), what is the probability the majority vote is correct? (Round to 2 decimal places.)

Explanation: P(Xβ‰₯3) for X~Binomial(5, 0.6) = C(5,3)(0.6)Β³(0.4)Β² + C(5,4)(0.6)⁴(0.4) + (0.6)⁡ = 0.3456 + 0.2592 + 0.0778 β‰ˆ 0.68.

Each independently sampled reasoning chain has a 70% chance of reaching the correct answer. If you sample 3 chains and take a majority vote (at least 2 of 3 correct), what is the probability the majority vote is correct? (Round to 2 decimal places.)

Explanation: P(Xβ‰₯2) for X~Binomial(3, 0.7) = C(3,2)(0.7)Β²(0.3) + (0.7)Β³ = 0.441 + 0.343 = 0.784 β‰ˆ 0.78.

If self-consistency samples $k = 10$ independent reasoning chains instead of 1, roughly how many times more inference compute does this cost compared to a single greedy chain?

Explanation: Self-consistency's cost scales linearly with the number of sampled chains β€” 10 chains β‰ˆ 10x the compute of one.

A verifier checks 2000 generated math solutions and finds 1200 verified correct. What is the verified-correct rate, as a percentage?

Explanation: 1200 / 2000 = 0.60 = 60%.