Reasoning Models Tutorial En

§0 TL;DR Cheat Sheet

1. Paradigm shift: previously we scaled training compute (parameters + data); now we scale inference compute (reasoning tokens / search / verification). Snell et al. 2024 (arXiv 2408.03314) gave the compute-optimal test-time scaling recipe: under the same inference FLOPs, a hybrid strategy of best-of-N + PRM beam search + sequential revision is >4× more efficient than pure best-of-N; under FLOPs-matched settings, small model + optimized test-time compute can match or exceed a 14× larger model on certain tasks.
2. o1 (OpenAI Sep 2024): uses RL to train hidden chain-of-thought; the API only returns a reasoning_tokens count, not content. o3 (Dec 2024) scored 75.7% (low compute) / 87.5% (high compute, 172× budget) on ARC-AGI—the first time abstract reasoning benchmarks approached human-level performance.
3. DeepSeek-R1-Zero (arXiv 2501.12948, Jan 2025): pure RL from a base model, no SFT cold start, rule-based reward (answer correct/wrong + format), using GRPO (no critic); the "aha moment" emerged—the model learned to reflect, backtrack, and verify on its own.
4. DeepSeek-R1: four-stage pipeline = SFT cold start (thousands of high-quality CoT) → reasoning-oriented RL → rejection sampling + general SFT → all-scenario RL. Matched o1 on math/code benchmarks like MATH-500 and AIME.
5. GRPO (DeepSeekMath, arXiv 2402.03300): removes the critic value network; for each prompt, sample $G$ responses $\{o_i\}$ and replace GAE with group-relative advantage $A_i = (r_i - \text{mean}(\mathbf{r})) / \text{std}(\mathbf{r})$. Halves memory and stabilizes training.
6. PRM vs ORM: ORM (outcome reward) only scores the final answer; PRM (process reward, Lightman 2023 "Let's Verify Step by Step") scores each reasoning step, allowing best-of-N to select better traces. Math-Shepherd (Wang et al. 2023, arXiv 2312.08935) samples Monte Carlo completion rollouts from intermediate steps (not MCTS tree search), uses soft/hard estimation from final-answer correctness to auto-label step labels, eliminating human annotation.
7. s1 (Muennighoff Feb 2025, arXiv 2501.19393): "Wait" budget forcing—forcibly append "Wait" at </think> to make the model continue thinking; 1K-sample SFT + inference control surpasses o1-preview by 27% (AIME24).
8. Common pitfalls: CoT ≠ reasoning (the model may post-hoc fabricate stories); self-consistency breaks on distribution-shifted problems; PRM training easily overfits step patterns; on long-CoT, GRPO's critic-free design is actually an advantage (critic is hard to learn).

§1 Why This Is the Biggest Paradigm Shift of 2024-2026

1.1　From train-time scaling to test-time scaling

The 2020-2023 scaling laws (Kaplan, Hoffmann/Chinchilla): performance ∝ log(params × data × FLOPs)—but this is training-time compute. Once a model is trained, inference compute is fixed (one forward pass).

Two anomalies appeared in 2024:

• OpenAI o1: spending more inference tokens to think → performance keeps improving, showing log-linear scaling (OpenAI's public figure: accuracy vs reasoning compute is a straight line)
• Snell et al. 2024: under fixed inference/test-time compute budget, using compute-optimal scaling (best-of-N + PRM beam search + sequential revision hybrid) lets small models in FLOPs-matched settings match or even exceed 14× larger models—provided the base model already has non-trivial success rate on the task

• System 1 (fast): one greedy decode = one path
• System 2 (slow): multiple paths + verifier + backtrack = tree search (Tree-of-Thought) or long CoT (o1)

Think of LLMs as a policy + value combination (like AlphaZero); inference is an MCTS-like search process.

1.2　Core components of reasoning models

       problem prompt
           │
           ↓
   ┌───────────────────────────┐
   │   Policy LLM (sampler)    │ ← generate candidate reasoning traces
   │   - greedy / temperature  │
   │   - long CoT (o1, R1)     │
   │   - tree expansion (ToT)  │
   └───────────────────────────┘
           │  N traces
           ↓
   ┌───────────────────────────┐
   │  Verifier / Reward Model  │
   │  - ORM (outcome only)     │
   │  - PRM (per-step)         │
   │  - rule-based (math/code) │
   └───────────────────────────┘
           │
           ↓
   ┌───────────────────────────┐
   │  Aggregator               │
   │  - majority vote (SC)     │
   │  - best-of-N (verifier)   │
   │  - beam search (PRM)      │
   │  - MCTS (rStar)           │
   └───────────────────────────┘
           │
           ↓
       final answer

Different reasoning model lines essentially make choices among these three components:

• o1 / R1: internalize search into the policy (long CoT single-pass generation, policy reflects on its own)
• ToT / rStar: external explicit search (MCTS / BFS / beam)
• Best-of-N + PRM: sampling + verifier (most naive test-time scaling)

§2 CoT Evolution: from Wei 2022 to o1

2.1　Chain-of-Thought (Wei et al., NeurIPS 2022, arXiv 2201.11903)

Core finding: few-shot prompts that demonstrate "step-by-step reasoning" trigger emergent reasoning ability on large models (>62B PaLM); GSM8K jumps from 18% → 57%.

Q: Roger has 5 tennis balls. He buys 2 more cans of tennis balls. Each can has 3 tennis balls. How many tennis balls does he have now?
A: Roger started with 5 balls. 2 cans of 3 balls each is 6 balls. 5 + 6 = 11.
The answer is 11.

Key points:

• Not fine-tuning—pure prompting; the base model already has the capability
• Emergence: on small models, CoT actually degrades (noise exceeds signal)
• Kojima et al. 2022 "Let's think step by step" later showed zero-shot CoT also works

2.2　Self-Consistency (Wang et al. 2022, arXiv 2203.11171)

Observation: CoT decoding is stochastic (temperature > 0); sampling the same problem multiple times yields different reasoning paths, but the correct answer usually appears more often (if the model is capable enough).

Algorithm:

1. Sample $N$ CoTs for the same prompt
2. Extract the final answer from each
3. Majority vote for the majority answer

$$\hat{y} = \arg\max_{y \in \mathcal{Y}} \sum_{i=1}^{N} \mathbb{1}[\text{extract}(\text{trace}_i) = y]$$

Result: GSM8K +17.9% (Wang et al.'s reported PaLM-540B number).

2.3　Tree of Thoughts (Yao et al., NeurIPS 2023, arXiv 2305.10601)

Upgrade CoT from a chain to a tree: each node is a "thought" (one reasoning step); from the root, BFS/DFS expands multiple candidate children, the LLM scores them itself ("is this step promising?"), keeping top-k.

          root (problem)
           │
   ┌───────┼───────┐
  step1a  step1b  step1c        ← sample k thoughts
   │       ✗       ✗            ← LLM evaluator score
   │       prune  prune
   ├──────┼──────┐
 step2a step2b step2c           ← expand surviving node

Game of 24 (use 4 numbers + arithmetic ops to get 24):

• GPT-4 CoT: 4% success rate
• GPT-4 ToT (b=5, depth=3): 74%—huge jump

2.4　From ToT to long-CoT (o1 / R1 route)

ToT requires an external search framework (recursive prompting + state management). o1 / R1 take a different route: they train search into the policy itself—a single long CoT, but the model learns on its own to:

• "wait, let me reconsider..."
• "actually that's wrong, the correct way is..."
• "let me verify by trying a different approach"

These backtracking / reflection tokens are rare in base models; only via repeated sampling + reward signal in RL can they be amplified into stable behavior. R1-Zero's reported "aha moment" is when this behavior suddenly emerges during RL training.

§3 PRM vs ORM: Two Routes for Reasoning Verifiers

3.1　Definition

3.2　PRM800K (Lightman et al. 2023, arXiv 2305.20050)

OpenAI human-labeled 800K step-level labels on the MATH dataset: each step is positive / neutral / negative.

Training objective (per-step classification):

$$\mathcal{L}_\text{PRM} = -\sum_{t=1}^{T} \log p_\phi(\ell_t \mid s_{\leq t})$$

where $\ell_t \in \{+, 0, -\}$, $s_{\leq t}$ is the first $t$ reasoning steps.

At inference, use PRM as verifier:

$$\text{score}(\text{trace}) = \prod_{t} p_\phi(\ell_t = +\mid s_{\leq t}) \quad \text{or} \quad \min_t p_\phi(\ell_t = +\mid s_{\leq t})$$

(The product form is more standard; the min form is more pessimistic but catches the weakest step.)

3.3　Math-Shepherd (Wang et al. 2023, arXiv 2312.08935) — auto-labeling step labels

Human labels are expensive; how to scale? Math-Shepherd's idea: use MCTS rollouts to estimate each step's "potential correctness rate".

For each step s_t (partial reasoning):
  rollout K completions from s_t
  count how many final answers are correct
  reward_t = (correct count) / K

Intuition: if a step is good, walking down from it should easily yield a correct answer; if bad, no path will succeed.

Train PRM with Math-Shepherd labels: MSE regression or BCE classification. Mistral-7B on GSM8K: 77.9% → 84.1%, no human labels needed.

3.4　Generative PRM and Critic LM

After 2024, "generative verifiers" became popular: treat PRM as next-token-prediction ("is this step correct? yes/no"), directly reusing the LLM architecture without a separate reward head. Representative work: Generative Verifiers (Zhang et al. 2024, arXiv 2408.15240). Advantage: can leverage in-context reasoning for scoring, more accurate than scalar-head PRM.

§4 Best-of-N + Verifier: The Most Naive Test-Time Scaling

4.1　Formula

Given prompt $x$, policy $\pi$, verifier $V$, sample count $N$:

$$i^{*} = \arg\max_{i \in [N]} V(\text{trace}_i), \quad \text{trace}_i \sim \pi(\cdot \mid x); \quad \hat{y} = \text{extract}(\text{trace}_{i^{*}})$$

Theoretical limit ("oracle BoN", assuming perfect verifier):

$$\text{pass}@N = 1 - (1 - \text{pass}@1)^N$$

Reality: the verifier is imperfect, so BoN's saturation curve is far below the oracle. Snell 2024 found:

• On easy problems, BoN quickly saturates (marginal returns small after N=4)
• On hard problems, BoN keeps improving up to N=64 / 128
• Compute-optimal: hard problem → increase N; easy problem → greedy

4.2　Best-of-N + PRM code

import torch
from typing import Callable

def best_of_n_prm(
    policy_sample: Callable,          # prompt -> (trace, step_list)
    prm_score: Callable,              # step_list -> scalar in [0, 1]
    prompt: str,
    n: int = 16,
    aggregation: str = "min",         # "min" | "prod" | "mean"
) -> tuple[str, float]:
    """
    Best-of-N with process reward model verifier.
    Returns (best_trace, best_score). Note: in `prod` mode, `best_score`
    is the cumulative log-product (negative); compare scores within the same
    aggregation mode only.
    """
    best_trace, best_score = None, -float("inf")
    for _ in range(n):
        trace, steps = policy_sample(prompt)
        step_probs = [prm_score(steps[: t + 1]) for t in range(len(steps))]
        if aggregation == "min":
            score = min(step_probs)
        elif aggregation == "prod":
            # log-sum to avoid numerical underflow
            score = sum(torch.log(torch.tensor(p) + 1e-9) for p in step_probs).item()
        elif aggregation == "mean":
            score = sum(step_probs) / len(step_probs)
        else:
            raise ValueError(aggregation)
        if score > best_score:
            best_score, best_trace = score, trace
    return best_trace, best_score

4.3　Self-Consistency code

from collections import Counter
from typing import Callable
import re

def _extract_braced(s: str, open_idx: int) -> str | None:
    """From the first `{` after `\boxed{`, extract the inner content via balanced brace matching (supports nested LaTeX)."""
    if open_idx >= len(s) or s[open_idx] != "{":
        return None
    depth = 0
    for i in range(open_idx, len(s)):
        if s[i] == "{": depth += 1
        elif s[i] == "}":
            depth -= 1
            if depth == 0:
                return s[open_idx + 1:i]
    return None  # unclosed

def extract_answer(trace: str) -> str:
    """Extract the final answer from a trace. Note: production needs more thorough normalization (units, fractions→decimals, LaTeX simplification, etc.)."""
    # Use balanced brace matching for `\boxed{...}` to avoid truncating `\boxed{\frac{1}{2}}` to `\frac{1`
    pos = trace.find(r"\boxed")
    if pos != -1:
        inner = _extract_braced(trace, pos + len(r"\boxed"))
        if inner is not None:
            return inner.replace(",", "").replace("$", "").strip()
    m = re.search(r"answer is[:\s]+([^.\n]+)", trace, re.IGNORECASE)
    if m:
        return m.group(1).strip().replace(",", "").replace("$", "").strip()
    return ""

def self_consistency(
    policy_sample: Callable,
    prompt: str,
    n: int = 40,
    temperature: float = 0.7,
) -> tuple[str, dict]:
    """Self-Consistency: sample N traces, majority vote on extracted answers."""
    answers = []
    for _ in range(n):
        trace = policy_sample(prompt, temperature=temperature)
        ans = extract_answer(trace)
        if ans:                            # skip parse failures
            answers.append(ans)
    if not answers:
        return "", {}
    counts = Counter(answers)
    return counts.most_common(1)[0][0], dict(counts)

§5 The RL Route: PPO → GRPO

5.1　Vanilla PPO recap (Schulman et al. 2017)

For each token $t$, policy gradient with clipping:

$$\mathcal{L}_\text{PPO} = -\mathbb{E}_t \left[ \min\!\left( \rho_t A_t,\; \text{clip}(\rho_t, 1-\epsilon, 1+\epsilon) A_t \right) \right]$$

where

• $\rho_t = \pi_\theta(o_t \mid s_t) / \pi_{\theta_\text{old}}(o_t \mid s_t)$ is the importance ratio
• $A_t$ is the advantage, commonly GAE-$\lambda$: $A_t = \sum_{l\geq 0} (\gamma\lambda)^l \delta_{t+l}$, $\delta_t = r_t + \gamma V_\psi(s_{t+1}) - V_\psi(s_t)$

Pain points:

1. Need to train a value network $V_\psi$ (critic), usually the same size as the policy—memory doubles
2. Critic training on long-CoT is hard to converge (reward is extremely sparse, only final answer right/wrong)
3. GAE requires token-level value estimation; on long-CoT (4K+ tokens), each token's value estimate is very noisy

5.2　GRPO (Shao et al. 2024, DeepSeekMath, arXiv 2402.03300)

Core idea: use group statistics to replace the critic.

Algorithm:

1. For each prompt $x$, sample $G$ completions $\{o_1, \dots, o_G\}$ from $\pi_{\theta_\text{old}}$ (typically $G = 16$ or $64$)
2. Use a reward model to score each completion $\{r_1, \dots, r_G\}$
3. Group-relative advantage (trace-level, not token-level):

$$\boxed{\;A_i = \frac{r_i - \text{mean}(\mathbf{r})}{\text{std}(\mathbf{r}) + \epsilon}\;}$$

1. Broadcast trace-level $A_i$ to all tokens in that trace: $A_t = A_i \;\forall t \in o_i$
2. Update the policy with the PPO clipping objective (same formula as above, but $A_t$ comes from steps 3-4); DeepSeekMath/R1 also add KL regularization $\beta \cdot \mathrm{KL}(\pi_\theta \,\|\, \pi_\text{ref})$. In practice, use Schulman's unbiased k3 estimator $\widehat{\mathrm{KL}}_t = e^{\log\pi_\text{ref}(o_t|s_t) - \log\pi_\theta(o_t|s_t)} - (\log\pi_\text{ref}(o_t|s_t) - \log\pi_\theta(o_t|s_t)) - 1$ per token (always $\geq 0$), then mask + average

• Same prompt, same source: $G$ completions share prompt difficulty; differences come entirely from policy output; mean automatically subtracts prompt-specific baseline, equivalent to a control variate
• No value network needed: directly saves half memory + doubles compute; the critic on long-CoT is hard to learn anyway (sparse reward + long episodes)
• Stability comes from group size $G$: larger $G$ → lower advantage estimation variance; DeepSeek-R1 uses $G \approx 16$

5.3　GRPO advantage computation code

import torch

def grpo_advantage(rewards: torch.Tensor, eps: float = 1e-6) -> torch.Tensor:
    """
    Group-relative advantage estimation.

    Args:
        rewards: [G] tensor of trace-level rewards (one prompt's group).
        eps: numerical stability.

    Returns:
        advantages: [G] tensor, mean ≈ 0, std ≈ 1.
    """
    mu = rewards.mean()
    sigma = rewards.std(unbiased=False)        # use biased std (divide by G, not G-1)
    return (rewards - mu) / (sigma + eps)


def grpo_loss(
    log_probs_new: torch.Tensor,               # [G, T] new policy log p
    log_probs_old: torch.Tensor,               # [G, T] old policy log p (detached)
    log_probs_ref: torch.Tensor,               # [G, T] reference policy log p
    rewards: torch.Tensor,                     # [G] trace-level
    mask: torch.Tensor,                        # [G, T] valid token mask
    clip_eps: float = 0.2,
    kl_beta: float = 0.04,
) -> torch.Tensor:
    """Single-prompt GRPO loss (group size = G traces).
    Requires `log_probs_old` and `log_probs_ref` to both be detached (no gradient);
    if the caller passes a tensor with gradient, it will incorrectly backprop into the old/reference policy.
    """
    adv = grpo_advantage(rewards)              # [G]
    adv = adv.unsqueeze(-1)                    # [G, 1] broadcast to tokens

    # Defensive detach: even if the caller forgot, old / ref policy won't be backproped
    log_probs_old = log_probs_old.detach()
    log_probs_ref = log_probs_ref.detach()

    # PPO clipping
    ratio = torch.exp(log_probs_new - log_probs_old)        # [G, T]
    surr1 = ratio * adv
    surr2 = torch.clamp(ratio, 1 - clip_eps, 1 + clip_eps) * adv
    pg_loss = -torch.min(surr1, surr2)                       # [G, T]

    # KL regularization: constrain policy not to drift too far from reference
    # DeepSeekMath/R1 use Schulman's unbiased k3 estimator:
    #   KL ≈ exp(log_ref - log_new) - (log_ref - log_new) - 1   ≥ 0
    # This is a sample unbiased estimator of KL(π_θ || π_ref), always non-negative, much more stable than raw log-ratio
    log_diff = log_probs_ref - log_probs_new               # [G, T]
    kl = torch.exp(log_diff) - log_diff - 1.0              # [G, T], ≥ 0
    loss = pg_loss + kl_beta * kl                          # [G, T]

    # Masked mean over valid tokens
    return (loss * mask).sum() / mask.sum().clamp_min(1.0)

• log_probs_old must be detached (not part of gradient), otherwise it forms a strange gradient path with ratio
• std biased vs unbiased has small impact but must be consistent (DeepSeek's public version uses biased)
• When all $G$ rewards are identical (all wrong or all correct), std = 0 and $r_i - \mu \equiv 0$; after adding eps, advantage = 0 → policy-gradient term zeros out; but the KL regularization term still exists, so total loss degenerates to kl_beta * KL (still pulling policy back to reference). In production, usually skip such prompts (data filtering) to avoid signal-less updates, or clamp std to a lower bound (e.g., 0.1)
• Mask must cover all padding tokens, otherwise padded log-probs pollute the loss

5.4　Why GRPO is sample efficient (L3 frequently-asked)

Observation: R1 paper's publicly disclosed ~800K samples (≈ 600k reasoning + 200k non-reasoning) is the Stage 3 rejection sampling + SFT data, not RL prompt count; R1 Stage 2 reasoning RL prompt count is not strictly disclosed, but overall training compute (~147K H800-hours) is still significantly less than contemporary RLHF (InstructGPT used millions of human preference pairs); GRPO is the core algorithmic contribution.

Root causes (beyond just "saving the critic"):

1. Trace-level reward naturally aligns with trace-level credit: GRPO directly broadcasts trace reward as advantage to all tokens; no critic needed for per-token credit assignment. Under settings where reward only sees the final answer, this is the standard policy-gradient estimate of sequence-level Monte-Carlo return (not "optimal", but trace-level is more stable than the critic's noisy per-token V on long-CoT)
2. Contrast within the same prompt automatically eliminates prompt-level noise: advantage = $(r - \mu) / \sigma$ stabilizes the advantage distribution; policy updates move in more accurate directions; equivalent to paired comparison within each prompt
3. PPO clipping limits single-step update magnitude: together with $G$, ensures the policy doesn't blow up due to a single prompt's outlier reward
4. Rule-based reward is hard to be RM-hacked: r1 uses rule reward (answer regex matching + format <think></think>), no learned RM to over-optimize; advantage primarily reflects "did you answer correctly". Note rule rewards are not completely unhackable—policy can still exploit regex loopholes, format tricks, or test-set leakage—but they avoid the main failure mode of learned-RM drifting off the training distribution

R1 training GPU hours ≈ 147K H800-hours (DeepSeek public number)—two orders of magnitude smaller than GPT-4 training; the result of GRPO + data refinement + rule reward acting together.

§6 Complete DeepSeek-R1-Zero / R1 Pipeline

6.1　R1-Zero: extreme experiment of pure RL without SFT

Only assumption: the base model (DeepSeek-V3-Base, 671B MoE) already has basic language + math capability.

Training:

• Reward = accuracy_reward + format_reward (rule-based, no RM)

  • accuracy_reward: whether the answer can be auto-extracted + matches ground truth
  • format_reward: whether reasoning is wrapped in <think>...</think>
• Algorithm: GRPO, $G = 16$, KL $\beta = 0.001$
• Data: math (MATH, AIME, etc.) + code (LeetCode-like executable evaluation)

Emergent behaviors ("aha moment", DeepSeek-R1 paper Fig 3):

• After a few K steps, CoT length spontaneously grows (200 tokens → thousands of tokens)
• Self-reflection phrases like "Wait, let me reconsider...", "Actually that's wrong", "Let me verify by..." appear
• On AIME 2024, pass@1 goes from base 15.6% → 71.0% (far exceeding GPT-4o-0513's 9.3%)

Problem: R1-Zero's output has readability issues—reasoning process language mixed (Chinese + English + math symbols jumping around), sometimes not paragraphed, hard for humans to read. So R1 added subsequent stages.

6.2　R1's complete 4-stage pipeline

Core insights:

• Stage 1 = readability injection, not for reasoning (reasoning comes from RL)
• Stage 3 = generalization injection, transferring reasoning capability learned from math/code RL to non-verifiable domains (writing, dialogue, QA)
• Stage 4 = safety + helpfulness alignment, equivalent to closing RLHF

6.3　R1-Distill: distilling R1 into smaller models

DeepSeek used Stage 3 data (600K reasoning samples) to do pure SFT (no RL) on Qwen2.5-{1.5B, 7B, 14B, 32B} and Llama3-{8B, 70B}, producing the R1-Distill series.

Key findings (paper Table 5):

• DeepSeek-R1-Distill-Qwen-32B on AIME 2024: 72.6 vs o1-mini's 63.6—SFT-distilled small model surpasses o1-mini
• 1.5B model on MATH-500: 83.9, far exceeding original Qwen2.5-Math-1.5B's 51.0
• The public R1-Distill only did SFT, no additional RL; authors explicitly note "incorporating RL could substantially boost performance"—so "whether distill + RL gives more" is an open question, not "can't be done"

• DeepSeek-R1-Distill-Qwen-32B (SFT only) > DeepSeek-Qwen-32B-RL (direct RL from scratch on Qwen)
• Reason: small model base is too weak; pure RL hardly causes reasoning to emerge; using R1 generated reasoning traces for SFT is equivalent to distillation through demonstrations, directly copying the "reasoning behavior pattern".
• Implication: emergent reasoning needs big base + strong RL; on small models, distillation copy is the most economical route.

§7 Test-Time Scaling: Snell 2024 and s1 Budget Forcing

7.1　Core conclusions of Snell et al. 2024 (arXiv 2408.03314)

Question: under fixed inference FLOPs, how to allocate optimally?

Experimental setup:

• Same base model (PaLM-2 family)
• Different test-time strategies: BoN, majority vote, ToT-like beam search, PRM beam search, sequential revision (let model see its own answer and revise)
• Compute-optimal: dynamically select strategy per prompt based on difficulty (easy → greedy; hard → beam search + PRM)

Core finding:

• Under fixed budget, optimal test-time scaling > 14× model scaling (on certain MATH subsets)
• Easy problems: majority vote / BoN 4-8 is enough
• Hard problems: PRM-guided sequential revision + beam search gives the biggest gains

$$\text{Compute}_\text{optimal}(x) = \arg\min_{(\theta, N)} \mathbb{E}[L(\pi_\theta(x; N))] \;\text{s.t.}\; \text{FLOPs}(\theta, N) \leq B$$

• $\theta$ = model size, $N$ = test-time samples / beam width
• Practical heuristic from the paper: on problems where base model pass@1 > 30%, adding N is more cost-effective than adding parameters

7.2　s1: Simple Test-Time Scaling (Muennighoff et al. Feb 2025, arXiv 2501.19393)

The simplest reasoning model: 1000-sample SFT + budget forcing inference control.

Data (s1K, 1000 samples):

• Filtered by three criteria: difficulty, diversity, quality
• Each sample: question + reasoning trace (generated by Gemini Thinking) + answer

Training: 26 minutes of SFT on Qwen2.5-32B-Instruct (16×H100, 1 epoch)—possibly the cheapest reasoning model in history.

Inference trick: budget forcing

Model generates:
<think>
[reasoning tokens...]
[model attempts to output </think>, but current token count < target_budget]
[forcibly replace </think> with "Wait"]
[model continues reasoning...]
...
[when token count >= target_budget or naturally ends]
</think>
Answer: ...

Result: on AIME 2024, s1-32B (with budget forcing) = 56.7%, exceeds o1-preview's 44.6%.

• SFT taught the base model the <think>...</think> format, but reasoning length has a distribution (short problems → short reasoning)
• Forcibly injecting "Wait" makes the model stop at </think> boundary, activating its in-context "reflection" ability
• Equivalent to forcing the model to stay in "thinking mode" for more reasoning path samples
• Failure case: when base model has never seen reflection patterns, content after "Wait" is garbage—s1's 1K SFT data already implicitly contains reflection patterns

7.3　Sequential vs Parallel test-time compute

Snell 2024 reports: parallel is more cost-effective for easy problems; sequential significantly better for hard problems.

§8 MCTS for Reasoning: rStar Series

8.1　PUCT formula (AlphaGo / AlphaZero origin)

At node $s$, for each action $a$, PUCT score:

$$\boxed{\;U(s, a) = Q(s, a) + c_\text{puct} \cdot \pi(a \mid s) \cdot \frac{\sqrt{N(s)}}{1 + N(s, a)}\;}$$

• $Q(s, a)$ = current $(s, a)$'s mean value (exploitation)
• $\pi(a \mid s)$ = policy prior (from policy network)
• $N(s)$ = total visit count for node $s$
• $N(s, a)$ = how many times action $a$ was selected
• $c_\text{puct}$ = exploration constant (typical 1.0-2.0)

Intuition: actions with fewer visits + favored by policy + currently high value are preferred.

8.2　rStar (Microsoft Research, arXiv 2408.06195) key idea

Treat LLM as policy + value plugged into MCTS:

• State: current partial reasoning $s_{
• Action: next-step action (rStar defines 5 reasoning actions: propose one-step, propose sub-question, generate full CoT, decompose, rephrase)
• Reward: at terminal node, use mutual consistency check (verified by another LLM)

rStar-Math (arXiv 2501.04519) goes further: use MCTS rollouts to auto-label process labels (similar idea to Math-Shepherd), train a process preference model (PPM), then policy + PPM self-evolve for four rounds. Qwen2.5-Math-7B on MATH: 58.8 → 90.0, approaching o1-preview.

8.3　Simplified MCTS for reasoning pseudocode

import math
from dataclasses import dataclass, field
from typing import Optional

@dataclass
class MCTSNode:
    state: str                          # partial reasoning trace
    parent: Optional["MCTSNode"] = None
    prior: float = 0.0                  # policy network prob
    visit_count: int = 0
    value_sum: float = 0.0
    children: dict[str, "MCTSNode"] = field(default_factory=dict)
    is_terminal: bool = False

    @property
    def q_value(self) -> float:
        return self.value_sum / self.visit_count if self.visit_count > 0 else 0.0

def puct_score(node: MCTSNode, parent_visits: int, c_puct: float = 1.5) -> float:
    """PUCT: Q + c * P * sqrt(N_parent) / (1 + N)"""
    return node.q_value + c_puct * node.prior * math.sqrt(parent_visits) / (1 + node.visit_count)

def select(root: MCTSNode) -> MCTSNode:
    """Traverse tree by PUCT until reaching a leaf."""
    node = root
    while node.children and not node.is_terminal:
        node = max(node.children.values(),
                   key=lambda c: puct_score(c, node.visit_count))
    return node

def expand(node: MCTSNode, policy_lm, k: int = 4):
    """Sample k next-step candidates from policy LM."""
    if node.is_terminal:
        return
    candidates = policy_lm.sample_next_steps(node.state, k=k)   # list of (step_text, prior)
    for step_text, prior in candidates:
        new_state = node.state + "\n" + step_text
        is_term = step_text.startswith("Final answer:")
        node.children[step_text] = MCTSNode(
            state=new_state, parent=node, prior=prior, is_terminal=is_term,
        )

def rollout(node: MCTSNode, policy_lm, verifier) -> float:
    """Simulate from node to terminal; return reward."""
    if node.is_terminal:
        return verifier(node.state)
    state = node.state
    while len(state) < 4096:
        step = policy_lm.sample_next_step(state, temperature=1.0)
        state += "\n" + step
        if step.startswith("Final answer:"):
            break
    return verifier(state)   # ORM or PRM final score

def backup(node: MCTSNode, reward: float):
    """Propagate reward up the path."""
    while node is not None:
        node.visit_count += 1
        node.value_sum += reward
        node = node.parent

def mcts_search(prompt: str, policy_lm, verifier, n_simulations: int = 100, k: int = 4) -> str:
    """Standard MCTS for reasoning."""
    root = MCTSNode(state=prompt)
    # First expand the root, ensuring root.children is non-empty
    expand(root, policy_lm, k=k)
    for _ in range(n_simulations):
        leaf = select(root)
        if leaf.visit_count > 0 and not leaf.is_terminal:
            expand(leaf, policy_lm, k=k)
            if leaf.children:
                leaf = max(leaf.children.values(),
                           key=lambda c: c.prior)        # first pick highest prior
        reward = rollout(leaf, policy_lm, verifier)
        backup(leaf, reward)
    if not root.children:
        return root.state                                 # safety guard
    # Descend along the highest visit_count path until terminal or leaf (unexpanded)
    # This returns a complete trace rather than just the first-level child; if the
    # strongest mid-level path didn't reach terminal, it returns the deepest expanded state on that path
    node = root
    while node.children and not node.is_terminal:
        node = max(node.children.values(), key=lambda c: c.visit_count)
    return node.state

8.4　PRM-Guided Beam Search (lighter alternative)

Instead of full MCTS, keep only top-$b$ partial traces, scoring each step with PRM:

import math

def prm_beam_search(
    policy_lm,
    prm,
    prompt: str,
    beam_width: int = 4,
    expansion: int = 4,
    max_steps: int = 16,
) -> str:
    """PRM-guided step-level beam search."""
    # (cumulative_log_score, partial_trace, is_done)
    beams = [(0.0, prompt, False)]
    for _ in range(max_steps):
        new_beams = []
        for score, trace, done in beams:
            if done:
                new_beams.append((score, trace, True))
                continue
            # Expand `expansion` candidate steps from current trace
            candidates = policy_lm.sample_next_steps(trace, k=expansion, temperature=0.8)
            for step, _ in candidates:
                new_trace = trace + "\n" + step
                step_prob = prm.score_step(new_trace)        # in [0, 1]
                # Accumulate log probability (numerically stable)
                new_score = score + math.log(step_prob + 1e-6)
                is_terminal = step.startswith("Final answer:")
                new_beams.append((new_score, new_trace, is_terminal))
        # Defensive edge case: if all beams expand empty candidates, avoid max(empty)
        if not new_beams:
            break
        # Pick top-b by cumulative log-score
        beams = sorted(new_beams, key=lambda x: x[0], reverse=True)[:beam_width]
        if all(b[2] for b in beams):
            break
    # Return the highest-scoring trace (fall back to initial prompt if beams empty)
    return max(beams, key=lambda x: x[0])[1] if beams else prompt

§9 Full Landscape of Reasoning Models

9.1　Comparison table of mainstream reasoning models (as of 2026)

9.2　Selection decision tree (frequently asked in interviews)

Task domain?
├── Math/competition (AIME / IMO) ─→ R1 / R1-Distill-32B / o1 / s1-32B
├── Formal theorem proving (Lean / Coq) ─→ DeepSeek-Prover-V2
├── Code (Codeforces / SWE-bench) ─→ o1-pro / R1 / Claude 3.7 + thinking
├── General reasoning (agent / chain task) ─→ Claude 3.7 / Gemini 2 Thinking / R1
├── Small-model deployment (edge / mobile) ─→ R1-Distill-1.5B-7B
└── ARC-AGI / abstract reasoning ─→ o3 (high-compute tier)

Deployment budget?
├── High (thousands of CoT tokens / problem) ─→ o1, o3, R1, Claude 3.7-extended
├── Medium (1-2K CoT tokens) ─→ s1-32B, R1-Distill-32B
└── Low (greedy or BoN=8) ─→ R1-Distill-1.5B + best-of-N with verifier

9.3　Does CoT really reflect reasoning? (deep question)

Classic controversy: the echo of Attention is not Explanation (Jain & Wallace 2019) for CoT—does the reasoning shown reflect the model's internal computation?

Evidence:

• Supports authentic: Anthropic Sleeper Agents (Hubinger et al. 2024) shows CoT content influences downstream action (not pure post-hoc rationalization)
• Supports non-authentic: Turpin et al. 2023 "Language Models Don't Always Say What They Think" found that with biased exemplars, the model's CoT gives plausible but wrong reasoning (biased but CoT doesn't mention the bias)
• R1-Zero's "aha moment" is limited evidence: behavioral changes (longer + more reflection) do correlate with performance gains, but could still be surface pattern

In interviews, always give balanced view: CoT is useful + partially trustworthy; but can't be treated as 100% explanation.

§10 25 Frequently-Asked Interview Questions (L1 must-know / L2 advanced / L3 top labs)

Ranked from the perspective of top lab interviewers simulated by gpt-5.5 xhigh.

L1 Must-Know (any LLM position will ask)

L2 Advanced (reasoning direction / research roles)

L3 Advanced (top labs / research direction)

§A Appendix: Core paper timeline + one-line summaries

Reverse chronological:

1. DeepSeek-R1 (2501.12948) —— covers GRPO + 4 stages + R1-Zero "aha moment"
2. DeepSeekMath (2402.03300) —— original GRPO algorithm paper
3. Let's Verify Step by Step (2305.20050) —— PRM foundations
4. Snell et al. (2408.03314) —— test-time compute scaling paradigm

After reading these 4 + this cheat sheet, reasoning model interview questions should cover 80%+.