Reasoning models and test-time compute
A model can get better answers without getting bigger: it can think longer before it answers, or try many times and pick the best try. This session explains chain-of-thought, majority vote, best-of-N with a verifier, when extra test-time compute beats a larger model, and how chat models expose a thinking mode with a budget and a real latency cost.
What you will learn
- What chain-of-thought (CoT) is, and why writing intermediate tokens gives a fixed-size model more compute and more serial steps
- Self-consistency: sample many reasoning paths and take a majority vote over the final answers, and when the vote helps or hurts
- Best-of-N with a verifier, pass@k and coverage, and why selection plateaus while coverage keeps rising
- Parallel versus sequential test-time compute (sampling, revisions, search), and the FLOPs exchange rate between test-time compute and model size
- How reasoning models such as o1 and DeepSeek-R1 are trained to think, and what changes in their outputs
- Thinking mode in chat models: the think tags, on/off switches, budget forcing, and the latency, cost and KV-cache memory of long thoughts
Why this matters
Until 2024, the main way to make a language model smarter was to make it bigger or train it longer. Reasoning models added a second knob: spend more compute at test time, when the model answers a question. The model writes a long chain of thought before the answer, or it tries many times and a vote or a verifier picks the best try.
This knob is now everywhere. OpenAI’s o1 (September 2024) was presented as a model whose accuracy rises both with more reinforcement-learning training and with more “time spent thinking” at test time. [Certain] On the 2024 AIME math exam, OpenAI reported 74% with one sample per problem, 83% with a consensus (majority vote) over 64 samples, and 93% when re-ranking 1000 samples with a learned scorer; GPT-4o solved 12%. [Certain] DeepSeek-R1 showed that open models can learn the same behavior with reinforcement learning on problems with checkable answers (session 70). Qwen3 and Claude chat models now have a thinking mode that the user can switch on, off, or limit with a token budget [Certain]; Gemini models have a similar setting. [Likely]
The price is real: a thinking answer can contain thousands of extra tokens. That means more latency, more cost per request, and more KV-cache memory. An engineer must know when extra thinking helps, when a vote helps, when a bigger model is the better buy, and how to put a limit on all of it.
Chain of thought: write the steps, then the answer
A normal answer goes straight from the question to the result: “Q: … A: 11.” A chain of thought (CoT) is a sequence of intermediate steps written before the final answer: “Roger started with 5 balls. 2 cans of 3 balls each is 6 balls. 5 + 6 = 11. The answer is 11.” That example is from the CoT paper by Wei et al. (2022). [Certain]
Wei et al. got this behavior by prompting: they put eight worked examples with written steps in the prompt (few-shot CoT). With PaLM 540B on the GSM8K grade-school math benchmark, the solve rate went from 17.9% with standard prompting to 56.9% with chain-of-thought prompting. [Certain] The paper also found that CoT only helped models of about 100B parameters or more; smaller models wrote fluent but illogical chains and did worse. [Certain] Kojima et al. (2022) then showed that you do not even need examples: adding “Let’s think step by step” raised text-davinci-002 from 17.7% to 78.7% on MultiArith and from 10.4% to 40.7% on GSM8K (zero-shot CoT). [Certain]
We can write CoT as a latent variable (a hidden quantity we do not observe directly). The model first samples a reasoning chain \(z\), then an answer \(y\). The probability of an answer is a sum over all chains that lead to it:
- Read the symbols
- \(x\)
- the question (the prompt)
- \(z\)
- one reasoning chain: the tokens written between the question and the final answer
- \(y\)
- the final answer, for example the number after “The answer is”
- \(p_\theta\)
- the language model with weights \(\theta\); both factors come from the same next-token model
Formula (72.1) explains two things. First, greedy decoding picks one chain \(z\) and trusts it; if that chain has one wrong step, the answer is wrong. Second, the best answer is the one with the largest total probability over all chains, and we can estimate that by sampling many chains and counting answers. That is self-consistency, later in this session.
Why thinking tokens help
A transformer spends a fixed amount of compute per token. A forward pass through a model with \(N\) parameters costs about \(2N\) floating-point operations (FLOPs) per token, ignoring attention (session 25). The cost does not depend on how hard the question is. If the answer is one token, the model gets one forward pass to find it.
- Read the symbols
- \(C_{\text{answer}}\)
- compute spent to produce one response, in FLOPs (prompt processing not counted)
- \(N\)
- number of model parameters
- \(T_{\text{think}}, T_{\text{ans}}\)
- number of thinking tokens and of final-answer tokens
Thinking tokens help in two ways.
- More total compute. Each extra token is another \(2N\) FLOPs spent on the same question. The model can “buy” compute for hard questions by writing more.
- More serial steps. Inside one forward pass, information flows through \(L\) layers, once. A token written at step \(t\) is read back as input at step \(t+1\), so a chain of \(T\) tokens lets a computation go through about \(L \cdot T\) layers in sequence. Some problems (multi-step arithmetic, tracking a state) need many dependent steps; a fixed-depth network cannot do them in one pass.
Theory supports the second point. Feng et al. (2023) argue that bounded-depth transformers cannot directly output the answers to basic arithmetic and equation tasks unless their size grows super-polynomially with the input, while a constant-size transformer can solve them by writing CoT steps. [Certain] Merrill and Sabharwal (2023) show that the power grows with the number of steps: a logarithmic number of CoT steps adds little, a linear number lets the model recognize all regular languages, and a polynomial number gives exactly the problems solvable in polynomial time (under their assumptions). [Certain] Figure 1 shows the serial path.
How to read Figure 1
At \(T = 0\) the answer comes from one pass: 4 layers in a row here, 36 in Qwen3-8B. Each thinking token adds one more full pass to the path and \(2N\) more FLOPs. Move the slider to 10: the path is 44 layers long in the drawing. Real reasoning models write thousands of tokens, so their serial path is tens of thousands of layer steps long, far deeper than any network we could train directly.
A careful point: the content of the chain matters, not only its length. Pfau et al. (2024, “Let’s Think Dot by Dot”) found that meaningless filler tokens can replace CoT only on specific tasks and only with special training. [Likely] In normal use, the written steps work because the model reads its own partial results.
Self-consistency: sample many chains, vote on the answer
Greedy decoding gives one chain. Self-consistency (Wang et al., 2022) samples many chains with temperature, reads the final answer of each, and returns the most frequent answer. [Certain] The idea: there are many correct ways to reason to the right answer, and they agree at the end; wrong chains make different mistakes and spread over many wrong answers.
- Read the symbols
- \(N\)
- number of sampled chains (Wang et al. used 40)
- \(y_i\)
- the final answer parsed from sample \(i\); the chain \(z_i\) itself is thrown away
- \(\mathbb{1}[\cdot]\)
- 1 if the condition is true, else 0; the sum counts votes for answer \(a\)
With PaLM-540B, 40 sampled paths (temperature 0.7, top-k 40) raised GSM8K from 56.5% (greedy CoT) to 74.4%. [Certain] The paper also tried weighting each vote by the chain’s probability; the plain unweighted majority vote did as well as the best weighted version (74.4% versus 74.1%). [Certain] Self-consistency is the same as estimating the arg-max of the marginal (72.1) by Monte Carlo.
- input: model \(p_\theta\), question \(x\), number of samples \(N\), temperature \(\tau \gt 0\)
- for \(i = 1 \dots N\) do // can run in parallel as one batch
- sample a chain and answer \((z_i, y_i) \sim p_\theta(\cdot \mid x)\) at temperature \(\tau\)
- parse \(y_i\) into a normal form (for example, “18”, “18.0” and “$18” all become 18)
- count votes per distinct answer; drop samples with no parsable answer
- return the answer with the most votes // formula (72.3); break ties at random
When does the vote help?
Take the simplest case: two possible answers, right or wrong. Each sample is right with probability \(p\), independently. With an odd \(N\), the vote is right if more than half the samples are right:
This is the Condorcet jury theorem: if \(p \gt 0.5\), \(P_{\text{vote}} \to 1\) as \(N\) grows; if \(p \lt 0.5\), it goes to 0. The vote amplifies whatever is already the most likely answer. With many possible answers the rule becomes: the vote converges to the right answer if the right answer is more likely than every single wrong answer, even if \(p\) is far below 0.5.
Two answers, \(p = 0.6\), \(N = 5\). The vote is right if 3, 4 or 5 samples are right:
\(P(3) = \binom{5}{3}\,0.6^3\,0.4^2 = 10 \times 0.216 \times 0.16 = 0.3456\); \(P(4) = 5 \times 0.1296 \times 0.4 = 0.2592\); \(P(5) = 0.6^5 = 0.07776\).
Sum: \(P_{\text{vote}}(5) = 0.68256\). So five votes turn 60% into 68.3%. With \(N = 25\) it is 84.6%, and with \(N = 64\) (ties broken by a coin flip) 94.6%. If instead \(p = 0.4\), five votes give 31.7%: the vote makes things worse.
Now many answers: right with \(p = 0.4\), one popular wrong answer with \(q = 0.3\), and the remaining 0.3 spread over answers that never repeat. Then the vote is right with probability 0.40 at \(N = 1\), 0.571 at \(N = 5\), 0.831 at \(N = 64\) and 0.973 at \(N = 256\) (exact sums over the multinomial distribution; Figure 2 computes them). Swap \(p\) and \(q\) (\(p = 0.3\), \(q = 0.4\)) and the vote falls from 0.30 at \(N = 1\) to 0.169 at \(N = 64\).
Best-of-N, verifiers and pass@k
Majority vote only needs final answers that can be compared. A second way to pick among \(N\) samples is a verifier: a model or a program that gives each candidate a score. Best-of-N returns the highest-scoring sample:
- Read the symbols
- \(v_\phi\)
- the verifier with weights \(\phi\): an outcome reward model (scores the whole answer), a process reward model (scores each step), or a program (unit tests, a proof checker)
- \(\hat\imath\)
- index of the chosen sample
Cobbe et al. (2021), who introduced GSM8K, trained such a verifier: sample many solutions, let the verifier rank them, return the top one. They found that verification improved GSM8K results substantially and scaled better with more data than plain fine-tuning. [Certain] A middle path is the weighted vote: sum verifier scores per distinct answer instead of counting votes. Reward models and their weak points are the topic of session 73.
To measure how much any selection method could gain, we use coverage, also called pass@k: the chance that at least one of \(k\) samples is correct. This is what an oracle verifier (one that is never wrong) would achieve. If each sample is right with probability \(p\), pass@k \(= 1 - (1-p)^k\). In practice we draw \(n \ge k\) samples, count \(c\) correct ones, and use the unbiased estimator from the Codex paper (Chen et al., 2021): [Certain]
- Read the symbols
- \(n\)
- number of samples drawn per problem (for example 200)
- \(c\)
- how many of the \(n\) samples are correct
- \(\binom{n-c}{k} / \binom{n}{k}\)
- the chance that a random subset of \(k\) of the \(n\) samples contains no correct one
Example: \(n = 10\), \(c = 3\), \(k = 5\): \(1 - \binom{7}{5}/\binom{10}{5} = 1 - 21/252 = 0.9167\). Simply computing \(1 - (1 - c/n)^k\) is biased for small \(n\); that is why the combinatorial form is used. [Certain]
Coverage keeps rising for a long time. Brown et al. (2024, “Large Language Monkeys”) found coverage grows over about four orders of magnitude of samples; on SWE-bench Lite, DeepSeek-Coder-V2-Instruct solved 15.9% of issues with one sample and 56% with 250 samples, when the unit tests choose. [Certain] But when there is no perfect checker, majority vote and reward models stopped improving after several hundred samples. [Certain] The gap between coverage and what you can actually select is the main limit of parallel sampling.
Figure 2 models this with one question. The verifier is imperfect: it gives correct answers a higher average score (separation \(d\), in units of the noise), and a fraction \(f\) of wrong answers fool it and look correct. In this toy model the chance that best-of-N picks a correct answer is
- Read the symbols
- \(\varphi, \Phi\)
- density and cumulative distribution of the standard normal; scores are “mean + Gaussian noise”
- \(d\)
- how far the verifier separates good answers from normal wrong answers
- \(f\)
- fraction of wrong answers that the verifier scores like correct ones (they “hack” the verifier)
- \(N p\, \varphi(s-d)[\dots]^{N-1}\)
- one of the \(N\) samples is correct with score \(s\), and all other \(N-1\) samples score below \(s\)
As \(N \to \infty\), the top score almost surely belongs to a correct answer or to a fooling wrong one, so \(P_{\text{BoN}} \to p / (p + (1-p) f)\). With \(p = 0.4\), \(f = 0.1\): 0.87, no matter how many samples. This is the plateau.
How to read Figure 2
The grey curve is the ceiling: a perfect checker. With the defaults, at \(N = 5\) coverage is 0.922, majority vote 0.571 and best-of-N 0.716. Majority vote starts slowly but keeps climbing because \(p \gt q\); best-of-N climbs fast and then flattens near 0.87. Set \(q\) above \(p\): majority vote goes down with more samples. Set \(f = 0\): best-of-N climbs toward 1. Set \(q = 0\): every wrong answer is unique, and the vote wins even with \(p = 0.2\). Real tasks are a mix of all these cases.
- input: model \(p_\theta\), verifier \(v_\phi\), question \(x\), number of samples \(N\)
- sample \(N\) candidates \((z_i, y_i)\) in one batch // parallel compute
- score each one: \(s_i \leftarrow v_\phi(x, z_i, y_i)\) // one extra forward pass per candidate
- best-of-N: return \(y_{\hat\imath}\) with \(\hat\imath = \argmax_i s_i\) // formula (72.5)
- weighted vote: for each distinct answer \(a\), \(S(a) \leftarrow \sum_{i: y_i = a} s_i\); return \(\argmax_a S(a)\)
- if a program can check answers (tests, proof checker), use it as \(v_\phi\): then accuracy follows pass@N // formula (72.6)
Parallel or sequential, and test-time compute versus model size
Sampling \(N\) independent answers is parallel test-time compute. You can also spend compute sequentially: let the model revise its own answer (self-refinement, RAS2 chapter 5), or write one much longer chain that checks and corrects itself. A third family is search: generate step by step and use a process reward model (PRM, a verifier that scores each step) to keep only the most promising partial solutions, as in beam search or tree search.
Snell et al. (2024) compared these on the MATH benchmark with PaLM 2-S*. Their main findings: [Certain]
- The best way to spend test-time compute depends on question difficulty (they bin questions by the base model’s own pass@1, estimated from 2048 samples, into five levels).
- On easier questions, sequential revisions were better; on harder ones, a mix of parallel sampling and revisions, or search with a PRM, was better. Beam search with a PRM helped on hard questions but hurt on easy ones at high budgets (over-optimizing the verifier).
- Picking the strategy per difficulty (“compute-optimal” scaling) beat best-of-N while using about 4× less test-time compute.
- In a FLOPs-matched comparison, on questions where the small model already had a non-trivial success rate, test-time compute could beat a model about 14× larger. On the hardest questions, the larger model was better.
How do you match FLOPs between “bigger model” and “more thinking”? Snell et al. use \(X = 6 N D_{\text{pre}}\) for pretraining and \(Y = 2 N D_{\text{inf}}\) for inference (session 35). Making the model \(M\) times larger multiplies both, to \(M(X + Y)\). The small model may then spend \(k\) times its inference compute, where \(X + kY = M(X + Y)\): [Certain]
- Read the symbols
- \(M\)
- how many times more parameters the larger model has
- \(D_{\text{pre}}, D_{\text{inf}}\)
- tokens used in pretraining, and total tokens generated over the model’s whole service life
- \(R\)
- inference load: \(R \ll 1\) for a research model used a little, \(R \gg 1\) for a product that serves billions of requests
- \(k\)
- the factor by which the small model may multiply its inference compute (for example, sample \(k\) answers per question)
With \(M = 14\), Snell et al.’s three settings \(R = 0.16, 0.79, 22\) give \(k = 257.8,\ 63.4,\ 15.8\). The heavier the inference load, the less extra test-time compute you can afford, because the larger model’s pretraining cost is spread over more requests. Figure 3 lets you try this with a toy set of five difficulty bins.
How to read Figure 3
With \(M = 14\), \(R = 1\): \(k = 53\). The vote lifts bins 1 to 3 to 1.00, 1.00 and 0.97, above the large model. In bin 4 the popular wrong answer (0.25) beats the right one (0.20), so voting gives only 0.29, below the large model’s 0.45. In bin 5 the small model rarely gets it right: 0.05 against 0.20. Raise \(R\) to 22: \(k\) drops to 15.8, so only 15 samples, and bin 3 falls to 0.85. This is the shape of Snell et al.’s result: extra test-time compute wins where the small model is already partly right, and a bigger model wins where it is not. Their actual method used revisions and PRM search, not plain voting.
Reasoning models: training a model to think
Prompting and voting work with any model. A reasoning model is trained so that it writes long, useful chains by itself: it plans, tries an approach, checks it, notices mistakes and backtracks. The main recipe since 2024 is reinforcement learning with verifiable rewards: give the model problems with checkable answers (math with a known result, code with tests), sample long answers, and reward correct final answers (session 70).
DeepSeek-R1 (2025) is the best documented open example. [Certain]
- The prompt template asks the model to put its reasoning inside <think> … </think> and the answer inside <answer> … </answer>.
- DeepSeek-R1-Zero was trained with RL (GRPO) directly from the base model, with rule-based rewards. Its AIME 2024 pass@1 rose from 15.6% to 71.0%, and to 86.7% with a majority vote over 64 samples.
- During training, the length of its answers grew steadily: the model learned by itself to spend hundreds to thousands of reasoning tokens. The paper reports an “aha moment” in which the model stops and re-evaluates its first approach (“Wait, wait. Wait. That’s an aha moment I can flag here.”).
- The full DeepSeek-R1 adds a small cold-start SFT set and more stages; it reached 79.8% pass@1 on AIME 2024. Its reasoning traces were then used to distill smaller dense models (session 59).
- pass@1 was estimated from several samples per question (between 4 and 64) at temperature 0.6, top-p 0.95, not from greedy decoding.
A cheaper route is supervised fine-tuning on good reasoning traces. s1 (Muennighoff et al., 2025) fine-tuned Qwen2.5-32B-Instruct on only 1,000 questions with reasoning traces; training took 26 minutes on 16 H100 GPUs. [Certain] So the behavior of long thinking can be taught with little data once a base model is strong; RL is what discovers and sharpens it.
Thinking mode in chat models: switches, budgets and latency
The format: thinking tokens inside the chat template
In a chat model, thinking is just text inside special tags, written in the assistant turn before the visible answer (session 9). Qwen3 is a clear open example: [Certain]
- One model has both a thinking mode and a non-thinking mode. Thinking is the default. The user can add /think or /no_think to a message; in a multi-turn chat the last flag wins.
- In the Hugging Face template, enable_thinking=False pre-fills an empty block <think>\n\n</think>\n\n so the model goes straight to the answer. In the tokenizer, <think> is token 151667 and </think> is 151668.
- The model card recommends temperature 0.6, top-p 0.95, top-k 20 in thinking mode, and warns not to use greedy decoding because it can cause endless repetition. It also says old thinking content should not be kept in the chat history; only the final answers are.
Budget control
A thinking budget is a limit on the number of thinking tokens. There are three common ways to apply it.
- Hard stop at decode time (budget forcing). When the thinking reaches the budget, the server stops it and inserts the end-of-thinking tag. s1 also appends “Final Answer:”. [Certain] Qwen3 inserts “Considering the limited time by the user, I have to give the solution based on the thinking directly now.” and then </think>; the report says this ability was not explicitly trained but appeared after merging the two modes. [Certain]
- Forced extension. s1 can also make the model think longer: if the model tries to end its thinking too early, the end tag is suppressed and “Wait” is appended, which often makes it re-check its answer. This moved s1-32B from 50% to 57% on AIME24. [Certain]
- An API parameter. Anthropic’s manual extended thinking takes budget_tokens: at least 1,024, less than max_tokens, and it is a target rather than a strict cap; thinking tokens are billed as output tokens. Newer Claude models replace it with “adaptive thinking” controlled by an effort level, where the model may skip thinking on easy inputs. [Certain] OpenAI’s reasoning models take an effort setting (low, medium, high). [Likely]
- Read the symbols
- \(t\)
- number of thinking tokens written so far
- \(B_{\min}, B_{\max}\)
- the lower and upper thinking budgets
- \(\langle\texttt{/think}\rangle\)
- the end-of-thinking tag; after it the model writes the visible answer
How to read Figure 4
Step through it. At step 3 the model wants to stop at 180 tokens, below \(B_{\min}\). At step 4 the end tag is suppressed and “Wait” is appended, so the model re-checks and finds its error. At step 6 the trace reaches \(B_{\max}\), so the server inserts the end tag itself. The final answer is written after </think> and does not count toward the thinking budget, but it does count toward max_tokens.
Overthinking
More thinking is not always better. Chen et al. (2024) show that o1-like models often spend many tokens on trivial questions such as “2 + 3 = ?” with little benefit, and propose training that cuts this overhead while keeping accuracy on GSM8K, MATH500, GPQA and AIME. [Certain] The Claude documentation also describes diminishing returns from larger budgets, depending on the task. [Certain] A good system picks the budget per request: none for chit-chat, small for lookups, large for proofs and hard code.
The latency, cost and memory of thinking
Thinking tokens are generated one at a time in the decode phase, so they cost time linearly (session 78):
- Read the symbols
- \(v_{\text{dec}}\)
- decode speed for one sequence, in tokens per second
- \(L, H_{kv}, d_h\)
- layers, key-value heads and head dimension; the factor 2 is for keys and values
- \(b\)
- bytes per number (2 for bf16)
For Qwen3-8B (36 layers, 8 KV heads, head dimension 128, bf16) the KV cache is \(2 \times 36 \times 8 \times 128 \times 2 = 147{,}456\) bytes = 144 KiB per token (session 80). A 32,768-token thought therefore holds 4.5 GiB of KV cache for one request. Long thinking reduces how many requests fit on a GPU at once, which reduces throughput. Figure 5 puts the numbers together.
Qwen3-8B, 8.2B parameters. Compute per generated token \(\approx 2 \times 8.2\times10^9 = 16.4\) GFLOPs (72.2). A direct 10-token answer costs 164 GFLOPs. A 4,000-token thought plus a 300-token answer costs \(16.4 \times 10^9 \times 4300 = 70.5\) TFLOPs, about 430 times more.
Latency at 60 tokens/s with 0.5 s of prefill: without thinking, \(0.5 + 300/60 = 5.5\) s. With thinking, \(0.5 + 4300/60 = 72.2\) s. The user waits 13 times longer. Majority vote over 8 samples run in parallel does not add wall-clock time if the server has room (a batch), but it multiplies output tokens and KV memory by 8.
How to read Figure 5
Defaults: 72.2 s instead of 5.5 s, 4,300 output tokens instead of 300, and 0.66 GiB of KV cache instead of 0.11 GiB. Push thinking to 32,000 tokens: about 9 minutes at 60 tok/s, and 4.5 GiB of KV cache for one sample. Raise \(N\) to 8: latency stays the same (parallel), but tokens and memory are 8 times larger. Thinking is cheap in FLOPs per token but expensive in time and memory.
Code: voting, best-of-N, pass@k and budget forcing in PyTorch
The first part simulates a “model” on 400 problems, each with its own accuracy and its own popular wrong answer, and compares coverage, majority vote and best-of-N with a noisy verifier that some wrong answers fool. The second part runs budget forcing (72.9) on a toy decoder. It runs on a CPU in about a second and prints the same numbers every time.
import math, torch from collections import Counter torch.manual_seed(0) # 1) A synthetic "model" that answers 400 problems. For problem j it writes the # right answer (id 0) with prob p_j, a popular wrong answer (id 1) with prob q_j, # and otherwise a random wrong answer (ids 2..999). P, NMAX = 400, 64 p = torch.distributions.Beta(1.2, 1.5).sample((P,)) # per-problem accuracy q = (1 - p) * torch.rand(P) * 0.6 # popular wrong answer def sample_answers(n): # [P, n] answer ids u = torch.rand(P, n) rand_wrong = torch.randint(2, 1000, (P, n)) return torch.where(u < p[:, None], 0, torch.where(u < (p + q)[:, None], 1, rand_wrong)) ans = sample_answers(NMAX) correct = ans == 0 # a noisy verifier: score = 1.5 if correct else 0, plus N(0, 1) noise; # 10% of wrong answers fool it and look correct fool = (torch.rand(P, NMAX) < 0.1) & ~correct score = 1.5 * (correct | fool).float() + torch.randn(P, NMAX) def majority_vote(a): # formula (72.3) # Counter keeps first-seen order, so a tie goes to the answer sampled first return torch.tensor([Counter(row.tolist()).most_common(1)[0][0] for row in a]) def best_of_n(a, s): # formula (72.5) return a.gather(1, s.argmax(1, keepdim=True)).squeeze(1) def pass_at_k(n, c, k): # formula (72.6), unbiased if n - c < k: return 1.0 return 1.0 - math.comb(n - c, k) / math.comb(n, k) print("N pass@N majority best-of-N") for n in [1, 4, 16, 64]: a, s = ans[:, :n], score[:, :n] cover = correct[:, :n].any(1).float().mean().item() mv = (majority_vote(a) == 0).float().mean().item() bon = (best_of_n(a, s) == 0).float().mean().item() print(f"{n:<3} {cover:.3f} {mv:.3f} {bon:.3f}") c = correct.sum(1) print("mean pass@1 from 64 samples:", round(sum(pass_at_k(NMAX, int(ci), 1) for ci in c) / P, 3)) print("pass@5 estimate, n=10, c=3:", round(pass_at_k(10, 3, 5), 4)) # N pass@N majority best-of-N # 1 0.500 0.500 0.500 # 4 0.810 0.630 0.688 # 16 0.960 0.788 0.780 # 64 0.993 0.803 0.808 # mean pass@1 from 64 samples: 0.466 # pass@5 estimate, n=10, c=3: 0.9167 # 2) Budget forcing on a toy decoder. END is the end-of-thinking token. END, WAIT, V = 1, 2, 50 def toy_logits(ids): # a "model" that wants to stop after about 40 tokens g = torch.Generator().manual_seed(len(ids)) z = torch.randn(V, generator=g) z[END] = (len(ids) - 40) / 4.0 # stopping gets more likely as it writes more return z def think_with_budget(min_tok, max_tok): ids, waits = [], 0 while True: if len(ids) >= max_tok: # budget reached: force the end (72.9) ids.append(END); break nxt = int(toy_logits(ids).argmax()) if nxt == END and len(ids) < min_tok: ids.append(WAIT); waits += 1 # too early: suppress END, write "Wait" continue ids.append(nxt) if nxt == END: break return len(ids) - 1, waits # thinking length (without END) for lo, hi in [(0, 10**9), (0, 20), (60, 10**9)]: n, w = think_with_budget(lo, hi) print(f"min={lo:<3} max={hi if hi < 10**9 else 'none':<5} -> thinking tokens {n}, 'Wait' inserted {w}x") # min=0 max=none -> thinking tokens 48, 'Wait' inserted 0x # min=0 max=20 -> thinking tokens 20, 'Wait' inserted 0x # min=60 max=none -> thinking tokens 60, 'Wait' inserted 11x
Read the table the way you read Figure 2. Coverage climbs to 0.993, but the two selection methods both stop near 0.80: majority vote because on some problems the popular wrong answer is more common than the right one, best-of-N because some wrong answers fool the verifier. Note also that the single-sample accuracy at \(N = 1\) (0.500) is a noisy estimate; the unbiased pass@1 averaged over all 64 samples is 0.466. In a real system, replace sample_answers with batched generation at temperature 0.6 to 1.0, parse the final answer with a strict rule, and replace the verifier with a reward model or with unit tests.
Where this is used
| Setting | Test-time method | Notes |
|---|---|---|
| Math and science reasoning (AIME, MATH, GPQA) | Long CoT from a reasoning model; majority vote (cons@64) for reported numbers | o1 and DeepSeek-R1 report both pass@1 and consensus scores [Certain] |
| Code generation and bug fixing (SWE-bench) | Many samples, unit tests as the verifier | Coverage grows with samples; tests make selection close to pass@k [Certain] |
| Chat assistants (Qwen3, Claude) | Thinking mode on or off; budget or effort level per request | Thinking off for simple chat to save latency [Certain] |
| Agents with tools | Thinking between tool calls (“interleaved thinking”); retries | Each thought adds latency to every step of the loop [Certain for Claude’s API] |
| Training data for smaller models | Generate many traces, keep verified ones, fine-tune (rejection sampling, distillation) | DeepSeek-R1 distilled models; s1 used 1,000 traces [Certain] |
| Video QA and Video-RAG | A VLM reasons over retrieved clips step by step; several sampled answers are voted | Long video contexts make each thinking token more expensive, because attention reads a large KV cache [Likely] |
| Temporal grounding and key-moment detection | Sample several predicted time spans and pick by agreement or by a verifier that re-checks the frames | Agreement between spans is measured by overlap, not exact match [Speculation] |
| Video classification and action recognition | Usually a single pass; test-time augmentation (several crops or clips, averaged) is the classic version of “more compute at test time” | The same vote-or-average idea, without text reasoning [Certain] |
Common mistakes
- Voting with greedy decoding. Greedy gives the same chain every time, so \(N\) votes are one vote. Self-consistency needs sampling (temperature above 0).
- Comparing answers as raw strings. “18”, “18.0” and “$18” are one answer. Without normalization the vote splits and gets worse. For code, compare by behavior (test results), not by text.
- Expecting the vote to fix systematic errors. If one wrong answer is more likely than the right one, more votes make the result worse (Figure 2 with \(q \gt p\)).
- Reporting pass@k as if it were accuracy. pass@k assumes an oracle picks the right sample. A deployed system without a checker gets majority-vote or best-of-N accuracy, which can be far lower.
- Using \(1 - (1 - c/n)^k\) for pass@k. It is biased for small \(n\); use the combinatorial estimator (72.6) with \(n \ge k\).
- Greedy decoding with a thinking model. The Qwen3 card warns it can cause endless repetition; use the recommended sampling settings.
- Keeping old thoughts in the chat history. It wastes context and can confuse the model; most templates strip earlier thinking and keep only final answers (check your model’s rules: some APIs keep them).
- Setting max_tokens below the thinking budget. The answer gets cut off after the thought, and the user sees nothing useful. Leave room for the answer.
Interview questions
What is chain-of-thought, and why does it improve reasoning?basic
What is self-consistency, and why does it work?basic
When does majority voting fail?core
Majority vote versus best-of-N with a reward model: which do you choose?core
Define pass@k. How do you estimate it without bias?core
Parallel versus sequential test-time compute: what is the difference and when is each better?core
When is spending more compute at test time better than using a bigger model?advanced
How are reasoning models like DeepSeek-R1 trained, and what changes in their behavior?advanced
How do you control the thinking budget of a chat model?core
enable_thinking=False pre-fills an empty think block, or /no_think in the message. (2) Hard budget at decode time: when the thought reaches \(B_{\max}\) tokens, insert the end-of-thinking tag (optionally a short instruction or “Final Answer:”) and let the model answer. (3) Minimum budget: suppress the end tag and append “Wait” (s1). (4) API parameters: Anthropic’s budget_tokens (at least 1,024, below max_tokens, a target not a strict cap) or effort levels. Always leave room in max_tokens for the visible answer.What does a long thought cost in serving, beyond FLOPs?advanced
Is the chain of thought a faithful explanation of the model’s answer?advanced
Exercises
- Two answers, each sample right with \(p = 0.7\). What is the majority-vote accuracy with \(N = 3\)?
- You draw \(n = 20\) samples for a coding problem and \(c = 2\) pass the tests. Estimate pass@1 and pass@10 without bias.
- With formula (72.8), how many times its inference compute may a small model use if the alternative is a 4× larger model and \(R = 0.5\)?
- A reasoning model writes 12,000 thinking tokens and a 400-token answer at 40 tokens/s, with 1 s of prefill. How long does the user wait?
- Qwen3-8B, 16 parallel samples of 8,192 tokens each (prompt and output together). How much KV-cache memory in bf16?
- In Figure 2, set \(p = 0.3\), \(q = 0.4\). Why does majority vote get worse as \(N\) grows, and what happens to best-of-N with \(d = 3\), \(f = 0\)?
Answerscheck
Key takeaways
- Chain-of-thought writes intermediate steps before the answer; CoT is a latent variable and the answer probability sums over chains (72.1).
- Each token costs about \(2N\) FLOPs (72.2), so thinking tokens buy compute and, more importantly, serial steps that a fixed-depth network lacks.
- Self-consistency samples many chains and votes (72.3). The vote amplifies the most likely answer: it helps when the right answer beats every wrong one and hurts otherwise (72.4).
- Best-of-N uses a verifier (72.5). Coverage pass@k (72.6) keeps rising with samples, but imperfect verifiers plateau (72.7).
- Test-time compute and model size are not 1-to-1: with FLOPs matched (72.8), more thinking wins on easy and medium questions and light inference load; a bigger model wins on the hardest ones.
- Reasoning models (o1, DeepSeek-R1) learn long thinking with RL on verifiable rewards. Chat models expose it as a thinking mode with switches and budgets (72.9); its latency and KV memory grow linearly with thinking tokens (72.10).
Key formulas
References for this session
- Wei et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Wang et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models
- Snell et al. (2024). Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
- Raschka, Build a Reasoning Model (From Scratch), chapter 4: Inference-time scaling
- Raschka, Build a Reasoning Model (From Scratch), chapter 5: Self-refinement
- Wei et al. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
- Kojima et al. (2022). Large Language Models are Zero-Shot Reasoners
- Wang et al. (2022). Self-Consistency Improves Chain of Thought Reasoning in Language Models
- Cobbe et al. (2021). Training Verifiers to Solve Math Word Problems
- Chen et al. (2021). Evaluating Large Language Models Trained on Code
- Brown et al. (2024). Large Language Monkeys: Scaling Inference Compute with Repeated Sampling
- Snell et al. (2024). Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
- Lightman et al. (2023). Let’s Verify Step by Step
- OpenAI (2024). Learning to Reason with LLMs (blog)
- DeepSeek-AI (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning
- Muennighoff et al. (2025). s1: Simple test-time scaling
- Qwen Team (2025). Qwen3 Technical Report
- Anthropic (2026). Extended thinking (API documentation)
- Chen et al. (2024). Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs
- Merrill & Sabharwal (2023). The Expressive Power of Transformers with Chain of Thought
- Feng et al. (2023). Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective
- Pfau et al. (2024). Let's Think Dot by Dot: Hidden Computation in Transformer Language Models
- Turpin et al. (2023). Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting
- Raschka, Build a Reasoning Model (From Scratch), chapter 4: Inference-time scaling
- Raschka, Build a Reasoning Model (From Scratch), chapter 5: Self-refinement