Module 13: Reasoning & Test-Time Compute

Introduction

Every module so far spends a fixed amount of compute per answer: run the model once, decode a token at a time (m08), stop. The answer you get is the answer the model happened to produce on its single pass. But hard problems — multi-step arithmetic, logic, code — are exactly the ones where a single pass is most likely to slip.

Test-time compute is the frontier’s newest lever: spend more compute at inference to get a better answer, with the weights frozen. No retraining, no bigger model — just let the model think longer, or think several times and reconcile. This is the idea behind OpenAI’s o1 and DeepSeek-R1, and this module builds its most important, most learnable form from scratch:

  • Chain-of-thought (CoT): let the model write intermediate steps before the final answer, turning one hard leap into several easy ones.
  • Self-consistency: sample many independent chains, read off each final answer, and take the majority vote. One idea, a large, reliable gain.
  • Best-of-N: sample N candidates and let a verifier pick the best.

Why it matters for LLMs:

  • Self-consistency alone lifted GSM8K accuracy by +17.9 points over a single chain-of-thought pass (Wang et al., 2022) — no new parameters.
  • The reasoning models topping today’s benchmarks are, at their core, models that were taught (with RL) to use test-time compute well. Understanding the parallel, no-training version first makes the RL version legible.

What You’ll Learn

After this module, you can:

  • Explain the difference between train-time and test-time compute, and why spending more of the latter raises accuracy.
  • Build self-consistency from scratch: extract answers, tally a plurality vote, and aggregate many sampled chains.
  • Prove why voting works with Condorcet’s jury theorem, and see the exact condition it needs (the correct answer is the mode, which is weaker than “right more than half the time”).
  • Implement best-of-N with a verifier and see when it beats voting.
  • Read the compute–accuracy curve — the empirical signature of test-time scaling — and place chain-of-thought and RL-for-reasoning (o1 / R1) on it.
  • Build GRPO from scratch — the critic-free RL recipe behind DeepSeek-R1 — and train a toy policy to answer correctly from a verifiable reward alone, watching the group-relative advantage do the work of a value network.
  • Fix GRPO’s two 2025-diagnosed rough edges: Dr. GRPO (drop the length and difficulty normalizations for an unbiased advantage) and GSPO (a length-normalized sequence-level importance ratio that damps the variance that collapses long-sequence and MoE training).
  • Build CISPO from scratch — MiniMax-M1’s fix that clips the importance weight, not the token update — and prove with autograd why GRPO’s clip zeroes the gradient of rare “fork” tokens while CISPO keeps every token learning: the cliff-vs-plateau gradient, and the one unified M_{i,t} template that recovers GRPO/DAPO/CISPO.
  • Build GSPO from scratch — the sequence-level successor to GRPO behind Qwen3 — and prove why its length-normalized ratio is more stable: single-token equivalence to GRPO, the v/L variance law, and how it tames Mixture-of-Experts routing volatility without Routing Replay.
  • Build Tree of Thoughts from scratch on Game of 24: a thought generator, a state evaluator, and beam/DFS search with backtracking — and see why a wider beam recovers a fallible evaluator (the 4% → 74% story, made runnable).
  • Build a process reward model (PRM) from scratch and see why scoring every step beats scoring only the answer — catching the “right answer, wrong reasoning” false positives an outcome model rewards (Lightman et al., 2023) — and discover that Math-Shepherd’s automatic step label is the ToT solvability oracle in disguise.

Prerequisites

This module requires familiarity with:

  • Module 08: Generation — temperature sampling and the generate loop that produces the diverse chains we vote over.
  • Module 12: Alignment — the aligned model that actually produces answers to reason about.

Intuition: Think Longer, Answer Better

Ask a person a hard arithmetic question and make them answer instantly, and they’ll often be wrong. Give them scratch paper — chain-of-thought — and they do better. Let them solve it three different ways and go with the answer they reached most often — self-consistency — and they do better still. None of this changes who is solving the problem; it changes how much thinking they spend.

Language models are the same. A single greedy decode is the instant answer. Two cheap upgrades, neither touching the weights:

  1. Chain-of-thought — prompt the model to emit reasoning steps before the answer. Each token now conditions on written-out intermediate work instead of leaping straight to the result.
  2. Self-consistency — because sampling (m08) makes each run take a different reasoning path, run it many times and vote. A correct answer is a fixed target many paths land on; wrong answers scatter.

Step through it: one prompt, many sampled chains, one vote.

NoteKey Insight

Self-consistency needs the model to be unreliable but not adversarial: as long as the correct answer is the single most likely one per sample, more samples sharpen the vote toward it. The reasoning path is a means to an end — we marginalize it out and keep only where the chains agree.

The Math: Why Voting Helps (Condorcet)

Model each sampled chain as an independent voter that is correct with probability p. If it is wrong, take the worst case first: every wrong vote lands on the same wrong answer. Then the majority is correct exactly when more than half of n voters are correct:

P_\text{correct}(n) = \sum_{k > n/2} \binom{n}{k}\, p^{k} (1-p)^{n-k}.

This is Condorcet’s jury theorem. Its behavior is a sharp phase transition at p = \tfrac12:

  • If p > \tfrac12, P_\text{correct}(n) \to 1 as n \to \infty — more votes, more accuracy.
  • If p < \tfrac12, it goes to 0 — voting amplifies a bad model’s errors.
  • If p = \tfrac12, it stays at \tfrac12 forever.

Real self-consistency does better than this bound, because wrong answers do not collude — they scatter across many values. Then the correct answer only has to beat each wrong answer individually (be the mode), a much weaker condition than p > \tfrac12. Drive p and watch the curve swing from “amplifies errors” to “converges to certain”:

Code: Self-Consistency from Scratch

reasoning.py builds the whole pipeline as small, model-agnostic functions — they wrap any generator, so we can test them without a trained model. First, pull the answer out of a chain. Following GSM8K, the model marks its final answer with ####:

from reasoning import extract_answer

print(extract_answer("6 eggs/day * 7 days = 42 eggs.\n#### 42"))
print(extract_answer("...so there are 1,024 bytes. The answer is 1,024."))
print(extract_answer("I'm not sure."))   # nothing to extract
42
1024
None

Then tally a plurality vote — the most common answer wins, Nones ignored:

from reasoning import majority_vote, vote_distribution

answers = ["42", "36", "42", "42", "17", "42"]
print("distribution:", vote_distribution(answers))
print("vote winner: ", majority_vote(answers))
distribution: {'42': 4, '36': 1, '17': 1}
vote winner:  42

self_consistency puts them together: sample n chains, extract each answer, return the vote and the tally. Here we drive it with NoisyReasoner, a controllable stand-in whose per-sample accuracy is exactly p — no model needed to see the effect (swap in a temperature-sampled generate call for real use):

from reasoning import self_consistency, NoisyReasoner

gen = NoisyReasoner(correct="42", p=0.55, num_distractors=4, seed=0)

for n in (1, 5, 41):
    answer, dist = self_consistency(gen.sample, n)
    correct = "✓" if answer == "42" else "✗"
    print(f"n={n:>2}: voted {answer!r} {correct}   tally={dist}")
n= 1: voted '3' ✗   tally={'3': 1}
n= 5: voted '42' ✓   tally={'42': 2, '3': 1, '2': 2}
n=41: voted '42' ✓   tally={'1': 6, '42': 22, '2': 5, '3': 4, '0': 4}

A single sample is a coin-flip near p; by 41 samples the correct answer is the clear plurality even though the generator is right only 55% of the time. That is the phase transition, made concrete.

Watch Accuracy Climb with Compute

The headline of test-time compute: accuracy is a rising function of how many samples you draw. demonstrate_self_consistency runs thousands of problems at each sample count and reports the fraction solved — the empirical compute–accuracy curve — beside the Condorcet bound.

from reasoning import demonstrate_self_consistency

accuracy = demonstrate_self_consistency(p=0.55, num_distractors=4, trials=3000, seed=0)
============================================================
SELF-CONSISTENCY: accuracy vs. samples (test-time compute)
============================================================
  per-sample accuracy p = 0.55, distractors = 4, trials = 3000

     n   empirical   Condorcet
     1       0.560       0.550
     3       0.655       0.575
     5       0.779       0.593
    11       0.931       0.633
    21       0.992       0.679
    41       1.000       0.741

  More samples -> higher accuracy (since p > 1/2); the empirical
  curve beats the binary Condorcet bound because wrong answers scatter.
from reasoning import condorcet_majority_prob

# Bridge the empirical curve (and the theoretical bound) to the plot below.
sc_points = [
    {"n": n, "empirical": acc, "condorcet": condorcet_majority_prob(0.55, n)}
    for n, acc in accuracy.items()
]
ojs_define(sc_points = sc_points)
TipTry This

The measured curve (orange) sits above the Condorcet bound (blue). That gap is the scattering effect: with four distractors, the wrong 45% splits four ways (~11% each), so the correct 55% is the runaway plurality. Real reasoning benchmarks have many possible wrong answers, so self-consistency is even more forgiving than the binary theorem predicts.

Best-of-N and Verifiers

Voting assumes the right answer is common. But sometimes the model finds the right answer rarely — it just needs help recognizing it. Best-of-N samples N candidates and keeps the one a verifier (a learned scorer / reward model, m12) rates highest, so a single good sample can win even if it is outvoted:

from reasoning import best_of_n

# Toy verifier: prefers solutions that "show their work" (longer, with an '=').
def verifier(chain: str) -> float:
    return len(chain) + (5.0 if "=" in chain else 0.0)

candidates = iter([
    "#### 42",
    "6 * 7 = 42, so the total is 42.\n#### 42",
    "idk maybe 40\n#### 40",
])
best = best_of_n(lambda: next(candidates), score_fn=verifier, n=3)
print("verifier picked:\n", best)
verifier picked:
 6 * 7 = 42, so the total is 42.
#### 42

Voting and best-of-N are the two parallel ways to spend test-time compute: voting is a verifier-free majority; best-of-N trades the vote for a scorer that can spot a rare gem. Production systems blend them — e.g. weight each vote by its verifier score.

Chain-of-Thought & the Frontier

Two loose ends connect this from-scratch core to the models making headlines.

Chain-of-thought is the enabler. Self-consistency only helps if the sampled chains are diverse yet mostly-correct — which is exactly what CoT prompting produces. Asking for steps (“Let’s think step by step”) both raises per-sample accuracy p and creates the path diversity voting feeds on.

RL for reasoning is the sequential counterpart. Everything above is parallel test-time compute: draw independent samples, aggregate. The other axis is sequential — train the model (with RL against verifiable rewards) to produce one long, self-correcting chain that thinks longer on harder problems. That is the o1 / DeepSeek-R1 recipe; its GRPO objective is the natural from-scratch sequel to the DPO you built in m12 — and you build it next, below.

NoteKey Insight

There are two knobs for test-time compute: parallel (sample many, aggregate — this module) and sequential (one longer, self-correcting chain — RL-trained). Both trade inference FLOPs for accuracy, and both leave the pre-trained weights of the base model exactly where scaling laws (m07) left them.

The Sequential Branch: Training to Reason with GRPO

Self-consistency spends compute at inference on a frozen model. The reasoning models that top today’s benchmarks do something more: they are trained to spend that compute well — to emit one long, self-correcting chain and only then commit to an answer. The recipe that made this reproducible and open is GRPO (Group Relative Policy Optimization), introduced in DeepSeekMath (2024) and used to train DeepSeek-R1 (2025).

GRPO is reinforcement learning, and it is the direct sequel to the DPO you built in m12. Both push a policy toward better outputs using only a preference or reward signal, no labeled target text. The twist that makes GRPO special is how it estimates whether an answer was good.

The problem RL has to solve. To improve, the policy needs to know whether a sampled answer was better than expected. Classic PPO trains a second network — a critic / value model V(s), as big as the policy — just to predict that expected reward, so the “advantage” is r - V(s). That doubles the memory.

GRPO’s one idea: let the group be the baseline. For a prompt q, sample a whole group of G answers o_1, \dots, o_G from the current policy, score each with a reward r_i, and use the group’s own mean reward as the expectation. An answer that beat its group’s average gets pushed up; one below average gets pushed down. No critic, no value network — just the samples you already drew.

NoteKey Insight

The reward can be verifiable: for math or code you don’t need a learned reward model at all — you can check whether the final answer is correct. DeepSeek-R1 trained on exactly this (a correctness reward plus a format bonus), and R1-Zero reached frontier reasoning with no supervised reasoning traces at all — pure RL from a rule that grades the answer.

The Math: Group-Relative Advantage

Score the group, then turn raw rewards into advantages by standardizing within the group:

A_i = \frac{r_i - \operatorname{mean}(r_1, \dots, r_G)}{\operatorname{std}(r_1, \dots, r_G) + \varepsilon}.

Subtracting the mean centers the signal (this is the critic-free baseline); dividing by the std puts every prompt on the same scale. A group that is all correct or all wrong has zero std → zero advantage — correctly, since there is nothing relative to learn from it.

Every token in output o_i shares that one scalar A_i. The policy is then nudged with the same clipped surrogate PPO uses, with a KL leash to a frozen reference policy \pi_\text{ref}:

\mathcal{J}_\text{GRPO} = \frac{1}{G}\sum_{i=1}^{G} \min\!\Big(\rho_i A_i,\ \operatorname{clip}(\rho_i,\, 1-\varepsilon,\, 1+\varepsilon)\,A_i\Big) \;-\; \beta\, \mathbb{D}_\text{KL}\!\left(\pi_\theta \,\|\, \pi_\text{ref}\right), \qquad \rho_i = \frac{\pi_\theta(o_i \mid q)}{\pi_{\theta_\text{old}}(o_i \mid q)}.

Two guards keep the update honest. The clip is a trust region: once a sample’s probability has moved more than \varepsilon in the helpful direction, the clipped branch wins the \min and its gradient goes to zero, so one lucky group can’t yank the policy off a cliff. The KL penalty keeps \pi_\theta near the reference so it doesn’t forget how to write — or learn to reward-hack. GRPO uses Schulman’s unbiased, always-non-negative k3 estimator, \mathbb{D}_\text{KL} = e^{d} - d - 1 with d = \log\pi_\text{ref} - \log\pi_\theta.

Step by Step

Code: GRPO from Scratch

The whole algorithm is three small functions plus a loop. It lives in grpo.py; here we build the pieces inline. Start with the advantage — the one line that replaces PPO’s critic:

import torch
from grpo import group_relative_advantages, kl_divergence

# A group of 4 answers to one prompt; only the first was correct (verifiable reward).
rewards = torch.tensor([1.0, 0.0, 0.0, 0.0])
adv = group_relative_advantages(rewards)
print("rewards   :", rewards.tolist())
print("advantages:", [round(a, 3) for a in adv.tolist()])
print("mean ~ 0  :", round(float(adv.mean()), 4), " std ~ 1:", round(float(adv.std(unbiased=False)), 4))

# All-correct (or all-wrong) group -> no relative signal -> zero advantage.
print("all-correct advantages:", group_relative_advantages(torch.ones(4)).tolist())
rewards   : [1.0, 0.0, 0.0, 0.0]
advantages: [1.732, -0.577, -0.577, -0.577]
mean ~ 0  : 0.0  std ~ 1: 1.0
all-correct advantages: [0.0, 0.0, 0.0, 0.0]

The correct answer gets a positive advantage, the wrong ones negative, and an all-equal group yields zeros. Now the KL leash — the k3 estimator, non-negative by construction:

same = kl_divergence(torch.tensor(-1.0), torch.tensor(-1.0))   # policy == reference
moved = kl_divergence(torch.tensor(-2.0), torch.tensor(-1.0))  # policy drifted away
print(f"KL when unchanged: {float(same):.3f}")
print(f"KL after drifting: {float(moved):.3f}  (always >= 0)")
KL when unchanged: 0.000
KL after drifting: 0.718  (always >= 0)

Put them together with the clipped surrogate and you have the GRPO loss — exactly the objective loss.backward() differentiates. To keep it hand-followable we make each “answer” a single token: a categorical policy over K candidate answers, where an output’s log-prob is one entry of log_softmax. (For a real chain you sum the per-token log-probs of the generated sequence; the loss above is unchanged.)

from grpo import ToyReasoningPolicy, grpo_step

# A uniform policy over 6 possible answers; answer 3 is correct.
policy = ToyReasoningPolicy(num_answers=6, seed=0)
print(f"before: p(correct) = {float(policy.probabilities()[3]):.3f}  (chance = {1/6:.3f})")

for _ in range(30):
    grpo_step(policy, correct=3, group_size=32, lr=0.5)

print(f"after : p(correct) = {float(policy.probabilities()[3]):.3f}  "
      "(learned from a verifiable reward — no critic, no labels)")
before: p(correct) = 0.167  (chance = 0.167)
after : p(correct) = 0.993  (learned from a verifiable reward — no critic, no labels)

Each grpo_step samples a group from the current policy, grades it, standardizes the rewards into advantages, and takes a few clipped-surrogate gradient steps toward the above-average answers — the full loop in grpo.py.

Watch a Policy Learn to Reason

demonstrate_grpo runs that loop from a uniform start and records the curve. The policy climbs from chance (1/K) toward near-certainty on the correct answer, driven only by a reward that says right or wrong — a from-scratch miniature of the R1 recipe.

from grpo import demonstrate_grpo

grpo_hist = demonstrate_grpo(num_answers=6, correct=3, steps=40,
                             group_size=32, lr=0.5, seed=0, verbose=False)

# Bridge the learning curve to the interactive plot below.
ojs_define(grpo_curve = grpo_hist)
TipTry This
  1. Kill the reward signal. In the demonstrate_grpo call, set correct to an answer, then imagine every reward were identical — the advantages would all be zero and the curve would stay flat. This is why a group that is all right or all wrong teaches nothing.
  2. Shrink the group. Re-run with group_size=4 vs group_size=64. Smaller groups give noisier advantage estimates (the mean baseline is shakier), so the climb is bumpier — the same bias/variance trade a critic would smooth.
  3. Turn up the leash. Raise beta toward 1.0. The KL penalty fights the reward, slowing how fast the policy departs its uniform reference — a stronger leash trades learning speed for staying close to the starting model.

GRPO’s Rough Edges: Two 2025 Fixes

The GRPO you just built is the recipe DeepSeekMath published in 2024. It works — the curve above proves it — but by 2025 two groups had put its objective under a microscope and found two distinct defects, each with a one-line fix that the field promptly adopted (both live in the models topping today’s leaderboards). Neither fix is a new algorithm; each surgically repairs one part of the objective you already have:

  • Dr. GRPO repairs the advantage — GRPO’s normalization quietly injects two biases.
  • GSPO repairs the importance ratio — GRPO corrects a per-sequence reward with per-token ratios, and the mismatch is unstable.

Look back at GRPO’s per-sample objective, written out per token:

\frac{1}{|o_i|}\sum_{t=1}^{|o_i|} \min\!\Big(\rho_{i,t}\,\hat{A}_i,\; \operatorname{clip}(\rho_{i,t},1-\varepsilon,1+\varepsilon)\,\hat{A}_i\Big), \qquad \hat{A}_i = \frac{r_i - \operatorname{mean}(\mathbf{r})}{\operatorname{std}(\mathbf{r})}.

Two seemingly-innocent factors — the \tfrac{1}{|o_i|} out front and the \operatorname{std}(\mathbf{r}) in the denominator — are exactly where Dr. GRPO finds bias, and the per-token \rho_{i,t} is exactly what GSPO rewrites.

Dr. GRPO: An Unbiased Advantage

Liu et al. (Understanding R1-Zero-Like Training, 2025) traced a puzzling symptom — GRPO makes responses grow longer over training, especially the wrong ones — back to the objective itself. They isolate two biases:

  1. Response-level length bias, from dividing by |o_i|. For a correct response (\hat{A}_i > 0), the \tfrac{1}{|o_i|} weight gives a shorter answer a larger per-token push — the policy learns to be terse when it is right. For an incorrect one (\hat{A}_i < 0), a longer answer has a bigger |o_i|, so each of its tokens is penalized less — the policy is discouraged from long wrong answers only weakly, and response length creeps up.
  2. Question-level difficulty bias, from dividing by \operatorname{std}(\mathbf{r}). A verifiable reward is binary, so a group with a fraction p correct has \operatorname{std} = \sqrt{p(1-p)}. That is small when a question is nearly solved (p\to1) or nearly hopeless (p\to0), so 1/\operatorname{std} hands those questions an outsized weight. Batch-wide advantage normalization is standard RL practice; doing it per question is what over-weights the easy/hard extremes.

Dr. GRPO (“GRPO Done Right”) removes both terms. Drop the \tfrac{1}{|o_i|} (use a constant normalizer) and stop dividing by the std:

\hat{A}_i^{\text{Dr.GRPO}} = r_i - \operatorname{mean}(\mathbf{r}).

Still centered on the group mean — the no-critic idea is untouched — just no longer rescaled per question. grpo_variants.py builds it beside the GRPO advantage you already have:

import torch
from grpo_variants import centered_advantages, difficulty_weight
from grpo import group_relative_advantages

rewards = torch.tensor([1.0, 1.0, 0.0, 0.0])   # a p = 0.5 group (informative)
print("GRPO   (÷ std):", group_relative_advantages(rewards).tolist())
print("Dr.GRPO(centered):", centered_advantages(rewards).tolist())
# The difficulty bias made concrete: GRPO's implicit per-question weight, 1/std,
# as the group goes from balanced (p=0.5) to nearly solved (p→1).
for p in (0.5, 0.9, 0.99):
    print(f"p={p:>4}:  std={ (p*(1-p))**0.5 :.3f}   GRPO weight={difficulty_weight(p, eps=1e-2):6.2f}")

The balanced group carries weight \approx 2; the nearly-solved one carries \approx 9 — more than four times the pull, for a question the model has almost mastered. The widget sweeps every p: watch GRPO’s weight bottom out at p=\tfrac12 and rocket up at both ends, while Dr. GRPO stays flat at 1.

TipTry This
  1. Drag p to the edges. Slide p correct toward 0 or 1 and watch GRPO’s weight climb past ×10 while Dr. GRPO holds at ×1. Those are the questions the model has nearly mastered or has no chance on — the ones GRPO lets dominate the update.
  2. Sit at p=0.5. The one place GRPO and Dr. GRPO nearly agree is a balanced group, where the relative signal is richest. The bias is entirely about unbalanced groups.

GSPO: A Sequence-Level Ratio

GRPO’s other rough edge is subtler and, at scale, more dangerous. Its importance ratio \rho_{i,t} = \pi_\theta(o_{i,t})/\pi_{\theta_{\text{old}}}(o_{i,t}) is per token — one ratio, one clip, for every token. But the reward r_i is a single number for the whole sequence. Correcting a sequence-level signal with token-level weights is, the Qwen team argue (Group Sequence Policy Optimization, 2025), a misapplication of importance sampling: each token adds noise, and over a long response that noise accumulates. On a Mixture-of-Experts model — where the routed experts shift between \pi_{\theta_{\text{old}}} and \pi_\theta — it is enough to send training into irreversible collapse.

GSPO’s fix is to make the importance ratio a single, length-normalized quantity for the entire sequence:

s_i(\theta) = \left(\frac{\pi_\theta(y_i \mid x)}{\pi_{\theta_{\text{old}}}(y_i \mid x)}\right)^{1/|y_i|} = \exp\!\left(\frac{1}{|y_i|}\sum_{t=1}^{|y_i|} \log \frac{\pi_\theta(y_{i,t})}{\pi_{\theta_{\text{old}}}(y_{i,t})}\right).

Because \pi(y_i) = \prod_t \pi(y_{i,t}), this is the geometric mean of the per-token ratios. The objective keeps GRPO’s \min/clip shape but uses s_i and clips once per response:

\mathcal{J}_{\text{GSPO}} = \frac{1}{G}\sum_{i=1}^{G} \min\!\Big(s_i\,\hat{A}_i,\; \operatorname{clip}(s_i, 1-\varepsilon, 1+\varepsilon)\,\hat{A}_i\Big).

(The advantage \hat{A}_i is still GRPO’s group-relative one — GSPO keeps the std; it only changes the ratio.) A consequence worth flagging: s_i is length-normalized, so it sits close to 1 — GSPO’s clip \varepsilon is around 10^{-3}, an order of magnitude tighter than GRPO’s 0.2. Reuse GRPO’s wide clip here and it would never bind.

from grpo_variants import (token_ratios, sequence_importance_ratio,
                           gspo_surrogate)

# One response of 4 tokens; the third token moved a lot off-policy.
logp_new = torch.tensor([-1.0, -1.2, -3.0, -0.9])
logp_old = torch.tensor([-1.0, -1.0, -1.0, -1.0])

print("per-token ratios ρ:", [round(r, 3) for r in token_ratios(logp_new, logp_old).tolist()])
s = sequence_importance_ratio(logp_new, logp_old)
geo = token_ratios(logp_new, logp_old).prod() ** (1/4)
print(f"sequence ratio s_i = {float(s):.4f}   (geometric mean = {float(geo):.4f})")

The single off-policy token yanks one \rho down to 0.13, but s_i — the geometric mean — barely notices. That damping is the whole point. And it means the single-token toy policy from earlier could never have shown GSPO off: with |y_i| = 1 the geometric mean is the one token ratio, so GSPO is identical to GRPO. The difference only appears once responses have length — which is exactly where the variance lives:

# |y_i| = 1  ⇒  GSPO's surrogate equals GRPO's (matching clip widths).
from grpo import grpo_surrogate
lpn = [torch.tensor([-0.9]), torch.tensor([-1.1])]
lpo = [torch.tensor([-1.0]), torch.tensor([-1.0])]
adv = torch.tensor([1.0, -1.0])
gspo = gspo_surrogate(lpn, lpo, adv, clip_eps=0.2)
grpo = grpo_surrogate(torch.tensor([-0.9, -1.1]), torch.tensor([-1.0, -1.0]), adv, clip_eps=0.2)
print(f"single-token GSPO = {float(gspo):.6f}   GRPO = {float(grpo):.6f}   equal: {torch.allclose(gspo, grpo)}")

Why is the token-level ratio noisier? If each token’s log-ratio has variance \sigma^2, then the un-normalized product \prod_t \rho_{i,t} has log-variance L\sigma^2 — it grows with length L. GSPO’s length-normalized s_i has log-variance \sigma^2/L — it shrinks. Step the length below and watch the two curves fan apart from their shared value at L=1:

NoteKey Insight

The two fixes are orthogonal, because they touch different halves of the same objective. Dr. GRPO edits what the advantage is — it deletes the length and difficulty rescalings so every token and every question count fairly. GSPO edits at what granularity the ratio corrects — it swaps G\!\cdot\!L noisy per-token ratios for G stable per-sequence ones. You can apply either, or both; the modern recipes (DeepSeek, Qwen3) draw from this menu.

WarningPitfall: Length-normalize the loss, not just the reward

Dr. GRPO’s length fix is about the loss — removing the \tfrac{1}{|o_i|} that divides each response’s summed surrogate. It is not the same as normalizing the reward. If you keep dividing the per-response loss by its token count “to keep scales comparable,” you have re-introduced the exact length bias Dr. GRPO removes. Sum the token terms and divide by a constant (e.g. a fixed max length), never by each response’s own length.

WarningPitfall: GSPO’s clip is not GRPO’s clip

Because s_i is length-normalized it lives near 1, so GSPO clips with \varepsilon \approx 10^{-3} (Qwen use 3\!\times\!10^{-4} / 4\!\times\!10^{-4}). Drop GRPO’s \varepsilon = 0.2 into GSPO and the clip never activates — every update passes through unclamped and you lose the trust region entirely. The clip range is tied to the definition of the ratio; change one, retune the other.

DAPO (ByteDance, 2025) is the third member of this family worth knowing: it keeps the token-level ratio but adds clip-higher (a wider upper clip so rare high-advantage tokens aren’t suppressed), dynamic sampling (drop the all-right and all-wrong groups that teach nothing — the same degenerate group the GRPO pitfalls warn about), and a token-level loss that coincides with Dr. GRPO’s length fix. We build Dr. GRPO and GSPO here because each isolates one clean, provable idea; DAPO combines several — so we build it too, once all three ideas are in hand, in The Production Recipe: DAPO Combines Four Fixes.

The Sequence-Level Fix: GSPO

GRPO has a hidden crack, and it only shows when you scale. Look again at the importance ratio — the term that lets you reuse samples from a slightly stale policy \pi_{\theta_\text{old}} to update the current \pi_\theta:

w_{i,t} = \frac{\pi_\theta(y_{i,t} \mid x, y_{i,<t})}{\pi_{\theta_\text{old}}(y_{i,t} \mid x, y_{i,<t})}.

GRPO applies this correction at every token. But importance sampling only works as an average over many samples — reweighting by \pi_\text{target}/\pi_\text{behavior} corrects a distribution only in expectation over N \gg 1 draws. At a single token position you have exactly one sample from that next-token distribution, so w_{i,t} does no correcting at all. It is just noise. And the noise accumulates with response length and is then amplified by the clip — which is why, when the Qwen team pushed GRPO to long chains and giant Mixture-of-Experts models, training didn’t just wobble, it collapsed, irreversibly (Zheng et al., 2025).

The fix follows one principle: the unit of optimization should match the unit of reward. The reward is granted to the whole response, so correct off-policy at the level of the whole response, not per token. That is Group Sequence Policy Optimization (GSPO) — the algorithm behind the latest Qwen3 models.

NoteKey Insight

GRPO and GSPO share everything — the group-relative advantage, the clipped surrogate, the verifiable reward. They differ in one place: the unit the importance ratio lives on. GRPO puts a noisy ratio on every token; GSPO puts one ratio on the whole sequence. Same recipe, different granularity — and that single change is the difference between collapse and stability at scale.

The Math: Sequence-Level Importance Ratio

GSPO defines the importance ratio on the sequence likelihood, then normalizes by length so it doesn’t explode as responses grow — a geometric mean of the per-token ratios (Zheng et al., 2025, Eq. 7):

s_i(\theta) = \left( \frac{\pi_\theta(y_i \mid x)}{\pi_{\theta_\text{old}}(y_i \mid x)} \right)^{1/|y_i|} = \exp\!\left( \frac{1}{|y_i|} \sum_{t=1}^{|y_i|} \log \frac{\pi_\theta(y_{i,t} \mid x, y_{i,<t})}{\pi_{\theta_\text{old}}(y_{i,t} \mid x, y_{i,<t})} \right).

The objective is the same clipped surrogate you already built — but now one scalar per response, clipping entire sequences in or out, with the same group-relative advantage (Eq. 5–6):

J_\text{GSPO}(\theta) = \mathbb{E}\left[ \frac{1}{G} \sum_{i=1}^{G} \min\!\big( s_i(\theta)\, A_i,\; \text{clip}(s_i(\theta),\, 1-\varepsilon,\, 1+\varepsilon)\, A_i \big) \right], \qquad A_i = \frac{r_i - \text{mean}(\mathbf{r})}{\text{std}(\mathbf{r})}.

Write out the gradient and the whole distinction fits in one line. GRPO weights each token’s log-prob gradient by that token’s own ratio; GSPO weights every token in a response equally by the single s_i:

\nabla_\theta J_\text{GRPO} \propto A_i \cdot \underbrace{\tfrac{1}{|y_i|}\textstyle\sum_t w_{i,t}\, \nabla_\theta \log \pi_\theta(y_{i,t})}_{\text{each token weighted by its noisy } w_{i,t}}, \qquad \nabla_\theta J_\text{GSPO} \propto A_i \cdot s_i \cdot \underbrace{\tfrac{1}{|y_i|}\textstyle\sum_t \nabla_\theta \log \pi_\theta(y_{i,t})}_{\text{all tokens weighted equally by } s_i}.

The step-through below makes it concrete on one response with a couple of “misbehaving” tokens (say an expert route flipped): GRPO’s per-token weights are jagged, one of them spiking far from 1; GSPO collapses them to a single flat line — the length-normalized s_i.

Why Length Normalization Tames Variance

Why the 1/|y_i| exponent — why a geometric mean rather than the raw likelihood ratio? Because of what happens to variance as responses get long. Model each per-token log-ratio \delta_t = \log(\pi_\theta/\pi_{\theta_\text{old}}) as independent noise with variance v (the residue a single off-policy sample leaves behind). Then three quantities pull in three different directions:

\underbrace{\text{Var}(\log w_t) = v}_{\text{token weight — flat}}, \qquad \underbrace{\text{Var}\Big(\log \textstyle\prod_t w_t\Big) = L\,v}_{\text{raw sequence ratio — grows}}, \qquad \underbrace{\text{Var}(\log s) = \tfrac{v}{L}}_{\text{GSPO ratio — shrinks}}.

The raw product of per-token ratios is a variance bomb — its spread grows linearly with length, so a naïve sequence ratio would be useless on long chains. GRPO’s per-token weights don’t blow up, but they don’t shrink either: L independent noisy weights, each scaling a different token’s gradient, and the noise never averages out. Only the length-normalized s_i has variance that shrinks with length — the geometric mean averages the noise away, pinning s_i near 1 no matter how long the response. That is also why GSPO’s clip range is ~1000× tighter than GRPO’s (\varepsilon \approx 3\times 10^{-4} vs 0.2): s_i simply doesn’t move much, so the trust region is narrow.

The chart plots all three (from length_variance_demo, Monte-Carlo dots on top of the closed forms — they agree). Watch the product curve climb and the GSPO curve dive as length grows.

TipTry This
  1. Follow the two curves apart. At L=1 all three variances coincide (a one-token response — GSPO is GRPO). As L grows they fan out: product up as L v, GSPO down as v/L. The gap at L=128 is a factor of L^2 = 16{,}384.
  2. Check the dots on the lines. The hollow dots are a seeded Monte-Carlo estimate; the solid lines are the closed forms v, Lv, v/L. They land on top of each other — the law isn’t a hand-wave, it’s exact.

Mixture-of-Experts: Where GRPO Breaks

The variance story turns catastrophic on Mixture-of-Experts models, and this is the headline result of the GSPO paper. In an MoE, each token is routed to a few of many experts. After a single gradient update, the Qwen team measured that ~10% of the experts activated for the same response flip to different ones (deeper models, worse). When the expert under \pi_\theta differs from the one under \pi_{\theta_\text{old}}, that token’s likelihood — and thus its ratio w_{i,t} — lurches wildly. A handful of flipped tokens is enough to wreck the per-token ratios GRPO depends on.

Their old fix was Routing Replay: cache the old policy’s expert routes and force \pi_\theta to reuse them, just so the token ratios stay sane — extra memory, extra communication, and a cap on the model’s real capacity. GSPO deletes that machinery. It never looks at individual token likelihoods, only the sequence likelihood, which stays stable because the model keeps its overall language-modeling ability even as individual routes flip. The demo (routing_flip_demo) shows it: a few flipped tokens send the max token ratio and the raw product through the roof, while the length-normalized s_i barely leaves 1. Drive the number of flipped experts and watch the two worlds diverge.

WarningSequence-level ≠ ignoring tokens

GSPO still uses every token’s log-prob — it just weights them together into one ratio instead of trusting each token’s ratio alone. The length normalization is load-bearing: drop the 1/|y_i| and you’re back to the raw product, whose variance grows with length and whose clip range would have to change with every response length. The geometric mean is what makes one clip range work for all lengths.

Code: GSPO from Scratch

The whole change from GRPO is one function — swap the per-token ratio for the length-normalized sequence ratio. It lives in gspo.py. Start with the ratio, and prove the claim that GSPO generalizes GRPO: on a one-token response the two are identical.

import torch
from gspo import sequence_importance_ratio

# Per-token log-probs for a group of 2 responses, each 4 tokens long.
logp_old = torch.tensor([[-1.0, -0.8, -1.2, -0.5],
                         [-0.9, -1.1, -0.7, -1.0]])
logp_new = torch.tensor([[-0.7, -0.9, -1.0, -0.6],   # response 0 drifted up overall
                         [-1.3, -1.0, -0.9, -1.2]])   # response 1 drifted down
s = sequence_importance_ratio(logp_new, logp_old)
print("sequence ratios s_i :", [round(float(v), 4) for v in s])

# It's the geometric mean of the per-token ratios — verify directly:
per_token = torch.exp(logp_new - logp_old)
geo_mean = per_token.prod(dim=1) ** (1 / 4)
print("geometric mean check:", torch.allclose(s, geo_mean))
sequence ratios s_i : [1.0779, 0.8395]
geometric mean check: True
from grpo import ToyReasoningPolicy, grpo_surrogate, group_relative_advantages, verifiable_reward
from gspo import gspo_surrogate

# One-token responses from the GRPO toy policy: s_i must equal w_i, so GSPO == GRPO.
policy = ToyReasoningPolicy(num_answers=6, seed=1)
answers = policy.sample_group(8)
lp_old = policy.log_probs(answers).detach()
with torch.no_grad():
    policy.logits += torch.randn(6) * 0.3          # move off-policy
lp_new = policy.log_probs(answers)
adv = group_relative_advantages(verifiable_reward(answers, correct=3)).detach()

s1 = sequence_importance_ratio(lp_new.unsqueeze(1), lp_old.unsqueeze(1))   # T = 1
gspo_l = gspo_surrogate(s1, adv, clip_low=0.2, clip_high=0.2)
grpo_l = grpo_surrogate(lp_new, lp_old, adv, clip_eps=0.2)
print(f"GSPO loss = {float(gspo_l):.6f}   GRPO loss = {float(grpo_l):.6f}")
print("identical on single-token responses:", torch.allclose(gspo_l, grpo_l))
GSPO loss = -0.092663   GRPO loss = -0.092663
identical on single-token responses: True
/var/folders/hl/bw75m5hd5xvfyx8j9qd71vjw0000gn/T/ipykernel_65811/1146972460.py:16: UserWarning: Converting a tensor with requires_grad=True to a scalar may lead to unexpected behavior.
Consider using tensor.detach() first. (Triggered internally at /Users/runner/work/pytorch/pytorch/pytorch/torch/csrc/autograd/generated/python_variable_methods.cpp:837.)
  print(f"GSPO loss = {float(gspo_l):.6f}   GRPO loss = {float(grpo_l):.6f}")

GSPO is a strict generalization of GRPO: same objective, but the ratio is now a length-normalized geometric mean, so it stays sane when responses run long. Now a multi-token policy that actually learns from it — ToySequencePolicy generates length-L sequences, sequence_reward grades each by how many positions it gets right (a verifiable reward), and gspo_step runs one sequence-level update.

from gspo import ToySequencePolicy, gspo_step

# A policy over length-4 sequences, vocab 5; target is [0, 1, 2, 3].
policy = ToySequencePolicy(seq_len=4, vocab_size=5, seed=0)
target = [0, 1, 2, 3]
print(f"before: p(correct token) = {policy.prob_correct(target):.3f}  (chance = {1/5:.3f})")

for _ in range(40):
    gspo_step(policy, target=target, group_size=48, lr=0.5)

print(f"after : p(correct token) = {policy.prob_correct(target):.3f}  "
      "(sequence-level ratios, verifiable reward, no critic)")
before: p(correct token) = 0.200  (chance = 0.200)
after : p(correct token) = 0.957  (sequence-level ratios, verifiable reward, no critic)

Watch a Policy Learn (Sequence-Level)

demonstrate_gspo runs that loop from a uniform start and records the curve. A policy producing whole sequences, corrected off-policy at the sequence level, climbs from chance (1/K) toward near-certainty — the from-scratch shape of the recipe behind Qwen3.

from gspo import demonstrate_gspo

gspo_hist = demonstrate_gspo(seq_len=4, vocab_size=5, steps=40,
                             group_size=48, lr=0.5, seed=0, verbose=False)
ojs_define(gspo_curve = gspo_hist)
NoteKey Insight

Notice what this section did not claim: that GSPO learns the toy faster than GRPO. On a tiny problem it doesn’t — GSPO’s win is stability at scale, not toy speed. The provable stories are the ones that survive: single-token equivalence, the v/L variance law, and the routing-flip absorption. Those are why Qwen3 trains with GSPO — not a rigged race on a 4-token toy.

GSPO-token: A Token-Level Face

One loose end. Sometimes you do want a per-token advantage — multi-turn RL, where different turns of a conversation deserve different credit. GSPO offers a token-level variant, GSPO-token, that keeps sequence-level stability while allowing per-token advantages. The trick is a stop-gradient (PyTorch .detach(), written \text{sg}[\cdot]):

s_{i,t}(\theta) = \text{sg}[s_i(\theta)] \cdot \frac{\pi_\theta(y_{i,t} \mid x, y_{i,<t})}{\text{sg}[\pi_\theta(y_{i,t} \mid x, y_{i,<t})]}.

The ratio of a quantity to its own detached copy is exactly 1 in value, so s_{i,t} numerically equals s_i for every token — but in the gradient only the un-detached numerator survives, contributing s_i \cdot \nabla_\theta \log \pi_\theta(y_{i,t}). So when every token shares the sequence advantage, GSPO-token is numerically identical to GSPO — same loss, same gradient — yet it exposes a per-token advantage slot the sequence form doesn’t have.

from gspo import sequence_importance_ratio, gspo_surrogate, gspo_token_surrogate, ToySequencePolicy
from grpo import group_relative_advantages
from gspo import sequence_reward

policy = ToySequencePolicy(seq_len=4, vocab_size=5, seed=0)
seqs = policy.sample_group(6)
lp_old = policy.log_probs_per_token(seqs).detach()
with torch.no_grad():
    policy.logits += torch.randn(4, 5) * 0.2
adv = group_relative_advantages(sequence_reward(seqs, [0, 1, 2, 3])).detach()

# Sequence objective + gradient.
lp_a = policy.log_probs_per_token(seqs)
loss_seq = gspo_surrogate(sequence_importance_ratio(lp_a, lp_old), adv, 0.2, 0.2)
policy.logits.grad = None; loss_seq.backward(); grad_seq = policy.logits.grad.clone()

# Token objective with the SAME advantage broadcast to every token.
lp_b = policy.log_probs_per_token(seqs)
adv_tok = adv.unsqueeze(1).expand(6, 4)
loss_tok = gspo_token_surrogate(sequence_importance_ratio(lp_b, lp_old), lp_b, adv_tok, 0.2, 0.2)
policy.logits.grad = None; loss_tok.backward(); grad_tok = policy.logits.grad.clone()

print(f"loss:  seq={float(loss_seq):.6f}  token={float(loss_tok):.6f}")
print("identical value :", torch.allclose(loss_seq, loss_tok))
print("identical grad  :", torch.allclose(grad_seq, grad_tok, atol=1e-6))
loss:  seq=0.029907  token=0.029907
identical value : True
identical grad  : True

The Production Recipe: DAPO Combines Four Fixes

Dr. GRPO and GSPO each isolate one clean idea and prove it. DAPO (Yu et al., ByteDance, DAPO: An Open-Source LLM Reinforcement Learning System at Scale, 2025) is the other kind of paper: it is a recipe, four decoupled edits stacked onto GRPO, published with the code and data that trained a Qwen2.5-32B base model to 50 points on AIME 2024 — past DeepSeek-R1-Zero-Qwen-32B’s 47 — in half the training steps. Its name is its two headline moves: Decoupled Clip and Dynamic Sampling Policy Optimization.

DAPO keeps GRPO’s group-relative advantage A_i = (r_i - \text{mean})/\text{std} (note: not Dr. GRPO’s mean-only form — DAPO leaves the advantage alone) and, like the long-CoT recipes, drops the KL leash entirely: at these scales the policy should move far from the base model, so a reference-KL penalty only holds it back. Onto that stripped-down objective it stacks four independent fixes. We have already built the machinery for each; this section assembles them.

The Math: Four Decoupled Edits

DAPO’s objective (Eq. 8 of the paper), with the per-token ratio r_{i,t}(\theta) = \pi_\theta(o_{i,t} \mid q, o_{i,<t}) / \pi_{\theta_\text{old}}(o_{i,t} \mid q, o_{i,<t}):

\mathcal{J}_\text{DAPO}(\theta) = \mathbb{E}\!\left[ \frac{1}{\sum_{i=1}^{G} |o_i|} \sum_{i=1}^{G} \sum_{t=1}^{|o_i|} \min\!\Big( r_{i,t}\,A_i,\; \text{clip}\big(r_{i,t},\, 1-\varepsilon_\text{low},\, 1+\varepsilon_\text{high}\big)\,A_i \Big) \right], \quad \text{subject to}\quad 0 < \big|\{o_i \text{ correct}\}\big| < G.

Read against GRPO’s \frac{1}{G}\sum_i \frac{1}{|o_i|}\sum_t \min(\dots), four things changed — and only these four:

Edit The one-line change What it fixes
Clip-Higher one \varepsilon → (\varepsilon_\text{low}, \varepsilon_\text{high}) = (0.20, 0.28) entropy collapse
Dynamic Sampling keep only groups with 0 < \#\text{correct} < G dead (zero-gradient) batches
Token-Level Loss \tfrac{1}{G}\sum_i\tfrac{1}{|o_i|} → \tfrac{1}{\sum_i |o_i|} long chains down-weighted
Overlong Shaping hard -1 at the cap → a soft length ramp reward noise from truncation

Each is a couple of lines in dapo.py, built against the exact grpo.py this module already ships. Take them one at a time.

Clip-Higher: Room to Explore

PPO clips the ratio to a trust region [1-\varepsilon,\, 1+\varepsilon]. For a token with positive advantage the \min selects the clipped branch — and its gradient goes to zero — the moment r_{i,t} climbs past 1+\varepsilon. With a symmetric \varepsilon = 0.2 that ceiling is 1.2: a rare, low-probability but correct “exploration” token can be up-weighted by at most 20% per update before it freezes, while already-likely tokens keep getting reinforced. The distribution sharpens, entropy collapses, and the policy stops exploring.

DAPO’s fix is to decouple the two sides of the clip and raise only the ceiling: \varepsilon_\text{low} = 0.20, \varepsilon_\text{high} = 0.28. The lower bound stays put (a bad token still can’t be crushed to nothing in one step), but the zero-gradient wall for good tokens moves from 1.2 to 1.28 — more room to lift a promising rare token. Drag the ceiling and watch the wall move:

TipTry This
  1. Slide \varepsilon_\text{high} back down to 0.20. The orange curve lands exactly on the grey GRPO dashes and the shaded headroom vanishes — Clip-Higher at \varepsilon_\text{high} = \varepsilon_\text{low} is GRPO. dapo.py’s clipped_objective_terms proves this against grpo_surrogate.
  2. Push it to 0.40. The wall slides right to \rho = 1.4; a rare good token can now be up-weighted 40% before its gradient dies. Too far and the trust region stops being a leash — DAPO stops at 0.28.

Dynamic Sampling: Don’t Train on Unanimous Groups

Look again at the advantage. A group where every sampled answer is correct (or every one wrong) has zero reward variance, so group_relative_advantages returns exactly zero for every token — the group teaches nothing relative, and its gradient contribution is precisely 0. On an easy prompt with a strong policy, most groups come back unanimous, so a large slice of every batch is dead weight.

For a binary verifiable reward with per-sample accuracy p and group size G, a group is wasted iff it is all-correct (probability p^G) or all-wrong ((1-p)^G). So the wasted fraction is p^G + (1-p)^G, and DAPO’s Dynamic Sampling over-samples and discards exactly those groups, keeping the batch full of 0 < \#\text{correct} < G groups with live gradients. The wasted fraction is brutal for small groups at easy/hard prompts and melts away as G grows — a big group is rarely unanimous:

from dapo import demonstrate_dynamic_sampling

dyn = demonstrate_dynamic_sampling(group_sizes=[4, 8, 16], num_points=61, verbose=False)
ojs_define(dyn_data = dyn)

At p = 0.9 a group of 4 is wasted 66% of the time; a group of 16 only 19%. Dynamic Sampling is why DAPO can run a large G without most of the compute landing on dead gradients — dapo.py’s group_is_effective is the exact filter, and it is provably equivalent to “the advantages aren’t all zero.”

Token-Level Loss: Every Token Gets a Vote

GRPO normalizes per response: it averages each response’s token-mean, then averages across the group (\frac{1}{G}\sum_i \frac{1}{|o_i|}\sum_t). That inner \frac{1}{|o_i|} means every token of a 2,000-token chain contributes \frac{1}{2000} as much as the single token of a short one — long reasoning is quietly muffled, exactly when you want it heard. DAPO switches to a token-level mean: sum every token term across the whole group and divide by the total token count (\frac{1}{\sum_i |o_i|}\sum_i\sum_t). Now every token carries equal weight, so a response’s total say is proportional to its length.

The two schemes are a weighted average of the same per-response terms; only the weights differ. They coincide exactly when all responses share a length — and pull apart the instant they don’t:

from dapo import demonstrate_token_level

tok = demonstrate_token_level(lengths=[2, 4, 8, 32], verbose=False)
ojs_define(tok_data = tok)

Sample-level flattens all four responses to \tfrac14 each; token-level hands the 32-token chain the lion’s share. On long-CoT problems that difference is the point: DAPO wants the long, correct reasoning to drive the update, not be averaged into the noise. dapo.py’s dapo_surrogate and sample_mean_loss make both losses runnable, and a test pins the token-level loss to the length-weighted average.

Overlong Reward Shaping: A Ramp, Not a Cliff

The last edit is the gentlest. When a response is truncated at the length cap, it isn’t wrong — it just didn’t finish. Scoring it a hard -1 punishes correct reasoning that ran long and injects noise into the reward. DAPO replaces the cliff with a soft penalty (Eq. 13): no penalty until the last L_\text{cache} tokens, then a linear ramp down to -1 reached exactly at L_\text{max} (L_\text{max}=20480, L_\text{cache}=4096). It is continuous, so the policy feels length pressure building and learns to wrap up early instead of being blindsided at the wall:

from dapo import demonstrate_overlong

over = demonstrate_overlong(num_points=61, verbose=False)
ojs_define(over_data = over)

Code: DAPO from Scratch

The whole recipe lives in dapo.py, built against the very grpo.py this module already ships. Start with the two provable anchors that connect DAPO back to GRPO. Clip-Higher with a symmetric range is GRPO — same clip, same numbers:

import torch
from dapo import clipped_objective_terms, dapo_surrogate, sample_mean_loss
from grpo import grpo_surrogate

# One response, six tokens. DAPO's decoupled clip with clip_low == clip_high must
# reproduce GRPO's symmetric clip exactly.
torch.manual_seed(0)
logp_new, logp_old = torch.randn(6), torch.randn(6)
adv = torch.tensor(0.7)
dapo_terms = clipped_objective_terms(logp_new, logp_old, adv, clip_low=0.2, clip_high=0.2)
grpo_l = grpo_surrogate(logp_new, logp_old, adv.expand(6), clip_eps=0.2)
print("clip_low == clip_high  ⇒  DAPO ≡ GRPO :",
      torch.allclose(-dapo_terms.mean(), grpo_l, atol=1e-6))
clip_low == clip_high  ⇒  DAPO ≡ GRPO : True

Token-level vs sample-level is a change of normalization, nothing more. With equal-length responses the two losses agree to the last digit; give the group a long chain and they diverge — the token-level loss weights each response by its length:

# Equal lengths: the two normalizations coincide.
eq_new = [torch.tensor([-0.9, -1.0]), torch.tensor([-1.1, -0.95])]
eq_old = [torch.tensor([-1.0, -1.0]), torch.tensor([-1.0, -1.0])]
adv2 = torch.tensor([1.0, -1.0])
print("equal length  → token == sample :",
      torch.allclose(dapo_surrogate(eq_new, eq_old, adv2), sample_mean_loss(eq_new, eq_old, adv2)))

# Unequal lengths: DAPO's token-level loss is the *length-weighted* average.
uneq_new = [torch.zeros(2), torch.zeros(8)]
uneq_old = [torch.zeros(2), torch.zeros(8)]
adv3 = torch.tensor([1.0, -1.0])          # short response good, long response bad
per_resp = torch.stack([clipped_objective_terms(n, o, a).mean()
                        for n, o, a in zip(uneq_new, uneq_old, adv3)])
w = torch.tensor([2.0, 8.0]); expected = -(per_resp * w).sum() / w.sum()
print("unequal length → token-level = length-weighted mean :",
      torch.allclose(dapo_surrogate(uneq_new, uneq_old, adv3), expected, atol=1e-6))
equal length  → token == sample : True
unequal length → token-level = length-weighted mean : True

Now Dynamic Sampling: the filter that keeps a batch full of live gradients. An all-correct or all-wrong group has zero advantage, so it is dropped — and the keep rule is provably the same as “the advantages aren’t all zero”:

from dapo import group_is_effective, kept_fraction, dynamic_sample
from grpo import group_relative_advantages

for rewards in ([1., 1., 1., 1.], [0., 0., 0., 0.], [1., 0., 1., 0.]):
    r = torch.tensor(rewards)
    adv_zero = float(group_relative_advantages(r).abs().max()) == 0.0
    print(f"rewards={rewards}  effective={group_is_effective(r)!s:5}  "
          f"(all advantages zero = {adv_zero})")

# Over-sample until enough effective groups fill the batch; report the compute cost.
gen = torch.Generator().manual_seed(0)
out = dynamic_sample(lambda: (torch.rand(8, generator=gen) < 0.9).float(), target_groups=8)
print(f"\ncollected 8 effective groups in {out['rounds']} rollouts "
      f"({out['discarded']} unanimous groups discarded)")
print(f"analytic keep rate at p=0.9, G=8: {kept_fraction(0.9, 8):.3f}")
rewards=[1.0, 1.0, 1.0, 1.0]  effective=False  (all advantages zero = True)
rewards=[0.0, 0.0, 0.0, 0.0]  effective=False  (all advantages zero = True)
rewards=[1.0, 0.0, 1.0, 0.0]  effective=True   (all advantages zero = False)

collected 8 effective groups in 13 rollouts (5 unanimous groups discarded)
analytic keep rate at p=0.9, G=8: 0.570

DAPO is what you ship: not one clean theorem, but four independent, individually provable edits — a decoupled clip, a sampling filter, a token-level loss, and a soft length penalty — that together turned an open 32B base model into a state-of-the-art reasoner on a public recipe.

NoteKey Insight

The three siblings partition GRPO’s weaknesses cleanly. Dr. GRPO edits the advantage (unbiased r_i - \text{mean}). GSPO edits the ratio granularity (one sequence-level ratio). DAPO edits everything around the ratio — the clip bounds, which groups enter the batch, how tokens are averaged, and how length is rewarded — while leaving the advantage and the per-token ratio as GRPO had them. They compose: nothing stops you from running Dr. GRPO’s advantage inside DAPO’s token-level loop. The menu is the point.

WarningPitfall: Clip-Higher retunes the range, it does not just widen it

Clip-Higher decouples the two clip bounds; it does not symmetrically inflate them. Raising both \varepsilon_\text{low} and \varepsilon_\text{high} would also let a bad token be crushed toward zero probability in a single step — the very instability the trust region exists to prevent. DAPO raises only the ceiling (0.20 \to 0.28) and leaves the floor at 0.20: more room to promote a rare good token, no extra room to annihilate a bad one. Widen the wrong bound and you get exploration and collapse.

The Last Rough Edge: Clip the Weight, Not the Token

Dr. GRPO fixed the advantage. GSPO fixed the ratio granularity. DAPO’s Clip-Higher fixed the clip range — it noticed that the ceiling was smothering rare exploration tokens and widened it. But every one of these still clips the token update: the moment a token’s ratio r_{i,t} leaves the trust region, the \min(\cdot) surrogate hands it a flat, zero gradient. That token stops teaching the policy anything — not this step, and (because it is now off-policy) not the next few either.

Which tokens does that silence? Exactly the ones a reasoning model most needs to learn. When a chain of thought changes direction — “However…”, “Recheck the second step”, “Wait, that’s wrong” — it does so on a rare fork token. After the first on-policy update those pivotal tokens tend to have a high ratio (the policy just learned to like them), so they blow past 1+\varepsilon and get clipped out. DAPO widened the cliff to keep a few of them; CISPO (Clipped Importance-Sampling weight Policy Optimization, from MiniMax-M1) removes the cliff entirely.

The idea is one move: rewrite the objective as a REINFORCE policy gradient, and clip the importance-sampling weight instead of the token update. The weight is detached — it only rescales — so autograd never zeroes a token; every token keeps its policy-gradient direction, just with a bounded magnitude.

NoteKey Insight

GRPO/DAPO clip the update: a clipped token contributes nothing (zero gradient). CISPO clips the weight: a clipped token contributes a bounded amount (never zero). Same goal — keep one group from yanking the policy too far — but CISPO caps the step size without ever silencing a token. On a Qwen2.5-32B math study, MiniMax-M1 reports CISPO reaching DAPO’s accuracy in about half the training steps.

The Math: A Policy-Gradient Re-Expression

Recall GRPO’s per-token surrogate (the thing we maximize):

J^{\text{GRPO}}_{i,t} = \min\!\Big( r_{i,t}\,A_{i,t},\ \operatorname{clip}(r_{i,t}, 1-\varepsilon, 1+\varepsilon)\,A_{i,t}\Big), \qquad r_{i,t} = \frac{\pi_\theta(o_{i,t})}{\pi_{\theta_\text{old}}(o_{i,t})}.

Differentiate one token with A_{i,t}>0. While r_{i,t}<1+\varepsilon the first branch wins and \partial J/\partial \log\pi = A_{i,t}\,r_{i,t} (using \partial r/\partial\log\pi = r). The instant r_{i,t}\ge 1+\varepsilon the clipped branch is a constant — its gradient is zero. That is the cliff.

CISPO writes the objective as a plain REINFORCE term with a stop-gradient weight \operatorname{sg}(\hat r_{i,t}):

J^{\text{CISPO}}(\theta) = \mathbb{E}\!\left[\frac{1}{\sum_i |o_i|}\sum_{i}\sum_{t} \operatorname{sg}\!\big(\hat r_{i,t}\big)\, A_{i,t}\,\log \pi_\theta(o_{i,t})\right], \qquad \hat r_{i,t} = \operatorname{clip}\!\big(r_{i,t},\,1-\varepsilon^{\text{IS}}_\text{low},\,1+\varepsilon^{\text{IS}}_\text{high}\big).

Because \operatorname{sg}(\hat r_{i,t}) carries no gradient, the only thing autograd differentiates is \log\pi_\theta(o_{i,t}), so every token’s gradient is

\frac{\partial J^{\text{CISPO}}_{i,t}}{\partial \log\pi} = \operatorname{sg}(\hat r_{i,t})\,A_{i,t} = A_{i,t}\cdot\operatorname{clip}(r_{i,t}, \cdot,\, 1+\varepsilon^{\text{IS}}_\text{high}).

For A>0 this rises with r, then plateaus at A(1+\varepsilon) — and never drops to zero. GRPO’s cliff becomes CISPO’s plateau. MiniMax-M1 also disables the lower bound (it sets \varepsilon^{\text{IS}}_\text{low} large so 1-\varepsilon^{\text{IS}}_\text{low} never binds) and tunes only the ceiling \varepsilon^{\text{IS}}_\text{high}; the paper reports no specific number, so the widgets below use an illustrative \varepsilon^{\text{IS}}_\text{high}=0.2.

One template, three objectives. The paper writes GRPO, DAPO, and CISPO under a single form with a per-token mask M_{i,t}:

J(\theta) = \mathbb{E}\!\left[\frac{1}{\sum_i|o_i|}\sum_i\sum_t \operatorname{sg}(\hat r_{i,t})\,A_{i,t}\,\log\pi_\theta(o_{i,t})\;M_{i,t}\right], \quad M_{i,t} = \begin{cases} 0 & A_{i,t}>0 \text{ and } r_{i,t} > 1+\varepsilon_\text{high}\\ 0 & A_{i,t}<0 \text{ and } r_{i,t} < 1-\varepsilon_\text{low}\\ 1 & \text{otherwise.}\end{cases}

The trust-region objectives set M=0 on the clipped tokens (their gradient vanishes); CISPO sets M\equiv 1 and does all its variance control inside the bounded weight \hat r_{i,t}. The cliff is a masking choice — and CISPO declines to make it.

Below, drag the ratio of a token past the ceiling and watch GRPO’s effective gradient fall off the cliff while CISPO’s holds a bounded plateau.

TipTry This

Slide r into the shaded band (r>1+\varepsilon). The highlight dot (GRPO) snaps to the floor — that token has stopped learning — while the green dot (CISPO) sits on the plateau, still pushing. Now widen \varepsilon_\text{high}: GRPO’s cliff slides right (DAPO’s Clip-Higher, exactly), but CISPO never has a cliff to move. That is the whole difference between retuning the clip and removing it.

Code: CISPO from Scratch

Everything lives in cispo.py, built against the same grpo.py this module already ships. The honest way to compare two objectives is to read the gradient off each with autograd — no analytic shortcut, no quoted number. Start with the two anchors that tie CISPO back to what you know.

import torch
from cispo import (cispo_surrogate, gradient_wrt_logp, ppo_clip_mask,
                   unified_surrogate, importance_ratios)
from grpo import grpo_surrogate

# Anchor 1 — on-policy, in range, CISPO IS vanilla policy gradient.
# With r = 1 (logp_new == logp_old) and no clip binding, the gradient of the CISPO
# loss w.r.t. log π is exactly -A / N per token: REINFORCE, nothing added.
lp = torch.zeros(3, requires_grad=True)
adv = torch.tensor([1.0, -1.0, 0.5])
cispo_surrogate(lp, torch.zeros(3), adv).backward()
print("Anchor 1  grad == -A/N :", torch.allclose(lp.grad, -adv / 3, atol=1e-6))
print("          grad =", [round(float(g), 4) for g in lp.grad])
Anchor 1  grad == -A/N : True
          grad = [-0.3333, 0.3333, -0.1667]
# Anchor 2 — the headline. A "fork" token with a high ratio (r = 3.0) and positive
# advantage. GRPO clips it: zero gradient. CISPO keeps a bounded one.
lp_new = torch.log(torch.tensor([0.6, 0.2]))   # token 0: r = 0.6/0.2 = 3.0
lp_old = torch.log(torch.tensor([0.2, 0.2]))
a = torch.tensor([1.0, 1.0])

g_grpo  = gradient_wrt_logp(grpo_surrogate,  lp_new, lp_old, a, clip_eps=0.2)
g_cispo = gradient_wrt_logp(cispo_surrogate, lp_new, lp_old, a, eps_high=0.2)
print(f"fork token (r=3.0, A=+1):  GRPO grad {float(g_grpo[0]):+.3f}   "
      f"CISPO grad {float(g_cispo[0]):+.3f}")
# CISPO's surviving coefficient is -sg(r_hat)·A/N = -(1+ε)·1/2 = -0.6 (N=2 tokens).
print("GRPO silences it :", float(g_grpo[0]) == 0.0,
      " |  CISPO keeps -(1+ε)·A/N :", round(float(g_cispo[0]), 3) == -0.6)
fork token (r=3.0, A=+1):  GRPO grad +0.000   CISPO grad -0.600
GRPO silences it : True  |  CISPO keeps -(1+ε)·A/N : True

The clip that survives is the paper’s unified template: one objective, and a mask M_{i,t} that GRPO uses to zero the clipped tokens and CISPO leaves at all-ones.

# The mask is 0 exactly on the tokens GRPO's autograd gradient zeroes.
torch.manual_seed(0)
ln, lo = torch.randn(12), torch.randn(12)
adv_r  = torch.where(torch.randn(12) > 0, 1.0, -1.0)
ratio  = importance_ratios(ln, lo)
mask   = ppo_clip_mask(ratio, adv_r, eps_high=0.2, eps_low=0.2)
grpo_alive = (gradient_wrt_logp(grpo_surrogate, ln, lo, adv_r, clip_eps=0.2).abs() > 1e-9)
print("mask == where GRPO keeps a gradient :", torch.equal(mask.bool(), grpo_alive))

# unified_surrogate(mask=False) IS cispo_surrogate; mask=True reproduces the clip.
u = unified_surrogate(ln.clone().requires_grad_(True), lo, adv_r, eps_high=0.2, eps_low=0.2, mask=False)
c = cispo_surrogate(ln.clone().requires_grad_(True), lo, adv_r, eps_high=0.2, eps_low=0.2)
print("unified(mask=False) ≡ CISPO :", torch.allclose(u, c, atol=1e-7))
mask == where GRPO keeps a gradient : True
unified(mask=False) ≡ CISPO : True

Watch the Reflection Token Survive

Here is one reasoning step’s worth of tokens. Most are ordinary (ratio near 1); three are fork tokens — However, Recheck, Wait — that the policy just started to favor, so their ratio jumped high. The gradient magnitudes below come straight from torch.autograd.

from cispo import demonstrate_reflection_token

demo = demonstrate_reflection_token(eps_high=0.2, clip_eps=0.2)
print(f"{'token':>9} {'ratio':>6} {'adv':>6}  {'GRPO grad':>10} {'CISPO grad':>11}  fork")
for t in demo["tokens"]:
    print(f"{t['label']:>9} {t['ratio']:>6.2f} {t['advantage']:>6.2f}  "
          f"{t['grad_grpo']:>10.4f} {t['grad_cispo']:>11.4f}  {'★' if t['is_fork'] else ''}")
print(f"\nfork tokens still learning →  GRPO: {demo['kept_grpo']}/{demo['n_fork']}   "
      f"CISPO: {demo['kept_cispo']}/{demo['n_fork']}")
    token  ratio    adv   GRPO grad  CISPO grad  fork
      the   1.02   0.10     -0.0127     -0.0127  
   answer   0.98   0.20     -0.0245     -0.0245  
       is   1.05  -0.15      0.0197      0.0197  
  However   1.60   0.90      0.0000     -0.1350  ★
       we   1.01   0.05     -0.0063     -0.0063  
  Recheck   1.80   0.75      0.0000     -0.1125  ★
     step   0.99  -0.10      0.0124      0.0124  
     Wait   1.45   0.85      0.0000     -0.1275  ★

fork tokens still learning →  GRPO: 0/3   CISPO: 3/3
# Bridge the token spec to the widget; JS recomputes alive/gradient live as you
# drive ε_high (mirrors ppo_clip_mask + the detached upper-only clip exactly).
_toks = [{"label": t["label"], "ratio": t["ratio"], "advantage": t["advantage"],
          "is_fork": t["is_fork"]} for t in demo["tokens"]]
ojs_define(cispo_tokens = _toks)

Sweep \varepsilon_\text{high} all the way up and GRPO eventually widens its way back to the fork tokens — but only by loosening the trust region on every token, the instability DAPO warned about. CISPO keeps all three forks learning at every setting, because it never masked them in the first place; the clip only bounds how hard each one pushes.

WarningPitfall: CISPO is not “no clipping”

Dropping the clip entirely — plain REINFORCE with raw importance weights — lets a single token with a wildly off-policy ratio (r = 50) dominate the batch and blow up training. CISPO still clips; it just clips the detached weight (\operatorname{sg}(\hat r)), so the magnitude is bounded while the gradient direction of every token is preserved. Remove the clip from clipped_is_weight and you get variance, not stability. The trust region is still there — it just throttles instead of silences.

The Game of 24: An Exact Playground

To build search from scratch we need a problem where every step is exact — no model in the loop, no fuzzy grading. Game of 24 is perfect: given four numbers, use each exactly once with +\,-\,\times\,\div to make 24. It is the task Yao et al. used, and it has a clean tree structure.

  • A state is the multiset of numbers still in play, e.g. (4, 9, 10, 13).
  • A thought is one arithmetic move that combines two numbers into one, e.g. 13 - 9 = 4, leaving (4, 4, 10).
  • Three thoughts reduce four numbers to one; you win if that number is 24.

We keep numbers as fractions.Fraction, so a move like 6 / 4 stays exactly 3/2 and never drifts — the classic hard puzzle (3, 3, 8, 8) needs the fractional detour 8 / (3 - 8/3) = 24, which float arithmetic would fumble. The full implementation is in tree_of_thoughts.py.

from tree_of_thoughts import propose_steps, is_solvable, _to_state

# The thought generator: every legal next move from a state.
state = _to_state([4, 9, 10, 13])
moves = propose_steps(state)
print(f"{len(moves)} possible thoughts from (4, 9, 10, 13). A few:")
for step in moves[:4]:
    print(f"  {step.expr:>16}   ->  {tuple(str(x) for x in step.state)}")
36 possible thoughts from (4, 9, 10, 13). A few:
        4 + 9 = 13   ->  ('10', '13', '13')
        4 * 9 = 36   ->  ('10', '13', '36')
        4 - 9 = -5   ->  ('-5', '10', '13')
         9 - 4 = 5   ->  ('5', '10', '13')
# The oracle: an exhaustive, exact check of whether a state can still make 24.
print("(4, 9, 10, 13) solvable:", is_solvable([4, 9, 10, 13]))
print("(1, 1, 1, 1)   solvable:", is_solvable([1, 1, 1, 1]))
(4, 9, 10, 13) solvable: True
(1, 1, 1, 1)   solvable: False

The oracle is_solvable is a perfect evaluator — but it works by running the entire search internally. That is exactly the luxury a real Tree of Thoughts does not have: it must judge a half-finished state without solving it. That gap is the whole game.

Code: Search from Scratch

Breadth-first search with a beam keeps the whole thing honest: expand every surviving state, score the children, and carry only the top b forward. Chain-of-thought falls out as the b = 1 special case.

from tree_of_thoughts import bfs_search, chain_of_thought, oracle_evaluator, evaluates_to_24

# With a perfect evaluator, even a beam of 5 finds a valid derivation.
sol = bfs_search([4, 9, 10, 13], beam_width=5, evaluator=oracle_evaluator)
print("solution:", sol.expr)
print("lands on exactly 24:", evaluates_to_24(sol.expr))
solution: 9 - 13 = -4; 4 - 10 = -6; -6 * -4 = 24
lands on exactly 24: True

Two properties make this a search, not a guess, and both are tested in tests/test_tree_of_thoughts.py:

  • Soundness. Every derivation the search returns is checked with exact Fraction arithmetic to equal 24 and to use each starting number exactly once.
  • Completeness. With the oracle evaluator, the search finds a solution iff the puzzle is solvable — verified against a brute-force solver over hundreds of number combinations.
from tree_of_thoughts import dfs_search

# DFS backtracks out of dead ends; on the classic hard puzzle it finds the
# fractional route a greedy chain would never keep alive.
hard = dfs_search([3, 3, 8, 8], evaluator=oracle_evaluator)
print("(3, 3, 8, 8):", hard.expr)
(3, 3, 8, 8): 8 / 3 = 8/3; 3 - 8/3 = 1/3; 8 / 1/3 = 24

Why Beam Width Buys Accuracy

Here is the crux. With the oracle evaluator, beam width does not matter — even b = 1 solves every solvable puzzle, because a perfect judge never points you down a dead branch. But a real evaluator is an LLM, and it is wrong sometimes. Its realistic failure is a false negative: it looks at a still-winnable state and declares it hopeless, pruning the one branch that would have worked.

We model that with noisy_evaluator — the oracle, but it deterministically gives up on a fraction of good states (a hash of the state, not a random draw, so every run is reproducible). Now beam width earns its keep: a greedy chain (b=1) that gets talked off the true path has no recourse, while a wider beam kept a backup. Step through one real search below — greyed thoughts were pruned, the highlighted ones kept in the beam, and the star is the winning 24.

TipTry This
  1. Kill the branching. In the bridge cell set beam_width=1 and re-render — the single greedy path often dead-ends before it reaches 24.
  2. Trust the judge less. Raise error_rate toward 0.7. The evaluator gives up on more good states, so you need a wider beam to survive its mistakes.
  3. Change the puzzle. Swap [4, 9, 10, 13] for the hard [3, 3, 8, 8] and watch the search hunt for the fractional route.

Interactive Exploration: Drive the Beam

The payoff, in miniature. Across a set of 20 real puzzles, drive the beam width and watch the solve rate climb under the imperfect judge — while the oracle ceiling stays flat at 100%. This is the exact shape of the paper’s headline: GPT-4 on Game of 24 goes from 4% (chain-of-thought) to 74% (ToT, b=5). Search does not make the model smarter; it makes it robust to a fallible evaluator.

Verifying the Reasoning, Not Just the Answer

Every verifier so far — the best-of-N scorer, the GSM8K reward model, the Tree of Thoughts state evaluator — ultimately judges the final answer. That is outcome supervision, and it has one blind spot that motivates this whole section: a chain can reach the right answer through wrong reasoning. Two mistakes that cancel, a lucky arithmetic slip, a leap that happens to land on the target — an outcome reward model (ORM) scores every one of them a perfect 1.0, because it only ever looks at the last line.

A process reward model (PRM) scores every step. It doesn’t just say “this solution is wrong” — it says “it went wrong here.” Lightman et al. (2023), Let’s Verify Step by Step, showed that a PRM trained on 800K human step-labels (the PRM800K dataset) reranks solutions far better than an ORM, precisely because it stops rewarding right-answer-wrong-reasoning false positives.

To make this a fact you can run — not a benchmark you must trust — we build PRMs on the same kind of exact playground as Tree of Thoughts. A “solution” is a linear arithmetic chain, and each step a op b = c has an exact validity oracle: the arithmetic must check out (via Fraction, no eval) and the step must be connected — its first operand equals the previous step’s result. The perfect PRM is that oracle; the ORM only reads the final value. Now plant a compensating error and watch them disagree:

NoteKey Insight

An outcome reward model asks “is the answer right?”; a process reward model asks “is every step right?”. The gap between them is the set of solutions that get lucky — right answer, broken reasoning. Process supervision closes that gap and, as a bonus, tells you exactly which step to distrust.

The Math: Aggregating Step Scores

A PRM emits one score p_i per step — a probability that step i is correct. To rerank whole solutions you must collapse the vector (p_1, \dots, p_T) into one number. The choice matters:

s_\text{product} = \prod_{i=1}^{T} p_i, \qquad s_\text{min} = \min_i p_i, \qquad s_\text{mean} = \tfrac1T \textstyle\sum_i p_i, \qquad s_\text{last} = p_T .

Product is the paper’s pick: if the p_i are independent correctness probabilities, \prod_i p_i is exactly P(\text{the whole solution is correct}). It carries a slight bias against longer solutions (more factors below 1). Minimum — the weakest link — performs about as well (78.2% vs 77.6% on the paper’s MATH subset) with no length bias, and is the robust default here. The two naive baselines fail in an instructive way: mean forgives a single bad step (one 0 among many 1s barely moves the average), and last looks only at the final step — collapsing right back toward outcome supervision. Drive the four strategies on a few chains and watch which ones a single bad step can fool:

TipTry This
  1. Pick “One bad step (compensated)” and switch to mean, then last. Both score it well above min/product — the exact failure mode that lets a broken chain survive reranking.
  2. Pick “Two shaky middle steps.” Watch product fall faster than min as two sub-1 factors multiply — the length bias the paper warns about, in miniature.

Code: A Process Reward Model from Scratch

Everything lives in prm.py. The perfect PRM is the exact step oracle; the ORM reads the last line only. Here is the crux chain that fools the outcome model:

from fractions import Fraction
from prm import step_rewards, prm_score, orm_score, first_error_index

crux = ["3 * 4 = 12", "12 + 8 = 21", "21 + 3 = 24"]   # 12 + 8 should be 20, not 21

print("per-step PRM rewards:", step_rewards(crux))     # [1, 0, 1] — step 2 is a lie
print("ORM (outcome) score :", orm_score(crux, Fraction(24)))   # 1.0 — answer is 24
print("PRM (process) score :", prm_score(crux, "min"))          # 0.0 — a step is wrong
print("first error at step :", first_error_index(crux))         # index 1
per-step PRM rewards: [1, 0, 1]
ORM (outcome) score : 1.0
PRM (process) score : 0.0
first error at step : 1

The outcome model is fooled and the process model is not — and the PRM even localizes the mistake. With the binary oracle, min and product agree exactly (both are 1.0 iff every step is valid), which is precisely the discrimination an outcome model lacks. A real PRM emits soft probabilities instead of a hard 0/1; soft_step_rewards fakes one deterministically so the aggregation strategies of the previous section actually differ.

Reranking: PRM vs ORM Best-of-N

The paper’s headline experiment is reranking: generate N solutions per problem (they used N = 1860) and keep the one the verifier rates best. We reproduce it in miniature. A candidate pool mixes three archetypes — valid (right answer, sound reasoning), flawed (right answer, a compensating error), and wrong (wrong answer) — and we ask each strategy: is the solution you selected actually valid, start to finish?

from prm import demonstrate_prm

demo = demonstrate_prm()
print("pool mix:", demo["pool_mix"])
cur = demo["curves"]
print(f"\n{'N':>3}  {'PRM':>6}  {'ORM':>6}  {'majority':>8}")
for i, n in enumerate(cur["n"]):
    print(f"{n:>3}  {cur['prm'][i]:>6.3f}  {cur['orm'][i]:>6.3f}  {cur['majority'][i]:>8.3f}")
pool mix: {'valid': 103, 'flawed': 142, 'wrong': 155}

  N     PRM     ORM  majority
  1   0.250   0.250     0.250
  2   0.443   0.367     0.313
  4   0.687   0.410     0.360
  8   0.907   0.417     0.403
 16   0.997   0.460     0.460
 32   1.000   0.403     0.403
 64   1.000   0.490     0.490

The PRM climbs toward 1.0 — with more samples it almost always finds a fully valid chain and picks it. The ORM plateaus: every right-answer candidate ties at score 1.0, so it cannot tell a valid chain from a lucky-but-flawed one, and majority voting (which also judges only the final answer) does no better. This is the whole argument for process supervision, made runnable:

Labeling Steps Without Humans

PRM800K cost 800,000 human labels. Math-Shepherd (Wang et al., 2023) removes the human: it defines a step’s quality as its potential to deduce the correct answer, and estimates that with Monte-Carlo rollouts. From a step, decode N completions and see how many reach the right answer:

y^{\text{HE}}_i = \mathbb{1}\big[\exists\, j : a_j = a^\star\big], \qquad y^{\text{SE}}_i = \frac{1}{N}\sum_{j=1}^{N} \mathbb{1}\big[a_j = a^\star\big].

Hard estimation (HE) labels a step 1 if any completion reaches the answer; soft estimation (SE) uses the fraction. Notice what HE actually asks: “from this prefix, is a correct answer still reachable?” — which is exactly Tree of Thoughts’ is_solvable oracle, estimated by sampling instead of exhaustive search. The search evaluator and the process reward are the same object.

from prm import hard_estimate, soft_estimate

# Rollout outcomes from a step: did each sampled completion reach the answer?
rollouts = [True, False, False, True, False]
print("HE (any reach?) :", hard_estimate(rollouts))   # 1 — the answer is still reachable
print("SE (fraction)   :", soft_estimate(rollouts))    # 0.4 — a graded step value
HE (any reach?) : 1
SE (fraction)   : 0.4

That closes the loop on this module: verification and search are one idea — a value on a partial solution — and a PRM is how you learn it cheaply enough to guide every branch, rerank every sample, and shape every reward.

Common Pitfalls

When implementing test-time compute, watch out for:

  1. Voting with greedy decoding. Self-consistency needs stochastic sampling (temperature > 0, top-p/top-k from m08). Greedy makes every chain identical, so the “vote” is n copies of one answer — no gain.
  2. Voting when p < ½ and the answer space is small. With a single dominant wrong answer, more samples make you more confidently wrong. Voting helps only when the correct answer is the mode.
  3. Comparing raw strings. "42", "42.", and "1,024" vs "1024" must be normalized before tallying, or correct chains split their own vote. That is why extract_answer strips commas and pulls a clean number.
  4. Counting compute as free. N-sample self-consistency costs ~N× the FLOPs of one pass. The compute–accuracy curve has diminishing returns; past some N the next point of accuracy is not worth the tokens.
  5. Trusting a weak verifier in best-of-N. Best-of-N is only as good as its scorer — an exploitable verifier makes the model reward-hack (m12), picking samples that fool the scorer rather than solve the problem.
  6. A degenerate GRPO group teaches nothing. If every sampled answer earns the same reward (all correct, or all wrong), the group’s std is zero and every advantage is zero — no gradient. Reward design and a policy that isn’t already saturated matter: you need a spread of outcomes for the group baseline to have signal.
  7. Dropping GRPO’s KL leash. Without the \beta\,\mathbb{D}_\text{KL} term the policy is free to chase the reward straight into reward-hacking or degenerate text. The clipped surrogate bounds one step; the KL keeps the model near a sane reference across many steps.
  8. Mistaking the evaluator for the oracle. Tree of Thoughts is only as good as its state evaluator. In a real system that evaluator is an LLM guessing “sure / maybe / impossible” — it makes mistakes, and a false “impossible” on a winnable state prunes the answer. A wider beam is how you buy robustness to those mistakes; it does not fix a systematically bad judge.
  9. Letting the tree explode. Branch factor \times depth is exponential. The beam width b (BFS) or the pruning threshold (DFS) is what keeps search tractable — and only decomposable problems (where a partial state can be scored at all) suit a tree search in the first place.
  10. Trusting the answer over the reasoning. An outcome model rewards a chain that reaches the right answer through a wrong step. If the answer is automatically checkable that may be fine — but for building trustworthy traces (training data, tool plans, anything you’ll act on), a right-answer- wrong-reasoning chain is a landmine. Score the process, not just the outcome.
  11. Aggregating step scores with mean or last. A single broken step barely dents the average, and last ignores the whole chain but its final line — both quietly re-import the outcome model’s blind spot. Use product (P(all steps correct)) or min (the weakest link) so one bad step actually sinks the score.
  12. Shipping GRPO’s 2024 objective unexamined. GRPO’s \tfrac{1}{|o_i|} and \div\,\operatorname{std} inject a length bias (wrong answers grow longer) and a difficulty bias (easy/hard questions dominate); its per-token importance ratio accumulates variance that can collapse MoE training. Dr. GRPO removes the two normalizers; GSPO moves the ratio to the sequence level. If you build GRPO, know which of these your setting needs — and remember GSPO’s clip \varepsilon is ~10^{-3}, not GRPO’s 0.2.

Exercises

Exercise 1: The break-even sample count

from reasoning import condorcet_majority_prob

# For p = 0.55, how many samples n does the Condorcet bound need to first exceed
# 0.90? (Loop odd n and check.) Then confirm real scattered-distractor accuracy
# reaches it sooner.

# Your implementation here:

Exercise 2: Self-consistency vs. best-of-N

from reasoning import self_consistency, best_of_n, NoisyReasoner

# Build a generator that is correct only 30% of the time but whose correct
# chains are always the longest. Show best_of_n(score_fn=len) beats
# self_consistency at the same N. When does voting win instead?

# Your implementation here:

Exercise 3: Weighted voting

from collections import Counter

# Combine voting and verification: instead of one vote per chain, weight each
# chain's vote by a verifier score, then take the argmax. Implement
# weighted_vote(answers, scores) and compare to plain majority_vote.

# Your implementation here:

Exercise 4: GRPO with a shaped reward

from grpo import ToyReasoningPolicy, group_relative_advantages, grpo_step

# The verifiable_reward above is 0/1. Give partial credit instead: reward the
# correct answer 1.0, a "close" answer (index correct-1 or correct+1) 0.5, else 0.
# Write shaped_reward(answers, correct, num_answers) -> tensor, then run GRPO with
# it (adapt grpo_step, or roll your own loop). Does the policy still converge on
# the exactly-correct answer, or does partial credit slow it down?

# Your implementation here:

Exercise 5: Measure the branching factor

from tree_of_thoughts import propose_steps, _to_state

# How fast does the tree grow? Count the thoughts proposed from a 4-, 3-, and
# 2-number state, and estimate the size of the full tree (product of branch
# factors over the 3 levels). This is why an unbounded search is hopeless and a
# beam is mandatory.

# Your implementation here:

Exercise 6: A vote-based state evaluator

from tree_of_thoughts import bfs_search, propose_steps, _to_state

# The paper offers a second evaluator strategy: instead of *valuing* each state
# alone, *vote* across a set of states for the most promising. Write
# vote_evaluator(states) that returns, for each state, a score = how many of the
# other states it can reach 24 faster than (fewest remaining moves). Plug it into
# bfs_search and compare its solve rate to the lookahead evaluator.

# Your implementation here:

Exercise 7: A verifier-weighted vote

from prm import prm_score, orm_score, generate_candidate_pool
from fractions import Fraction

# Combine voting with a PRM. Instead of one vote per candidate (majority) or the
# single argmax (best-of-N), weight each candidate's vote for its final answer by
# its PRM score, then take the answer with the most PRM-weighted mass. Write
# prm_weighted_vote(pool) and compare its selected answer's validity to plain
# majority voting on a generate_candidate_pool(200). Does down-weighting the
# flawed (right-answer-wrong-reasoning) chains change the winning answer?

pool = generate_candidate_pool(200, target=24, seed=0)

# Your implementation here:

Exercise 8: CISPO never silences a token

import torch
from cispo import cispo_surrogate, gradient_wrt_logp, fraction_tokens_clipped
from grpo import grpo_surrogate

# Build a batch of 50 tokens whose ratios are deliberately scattered off-policy
# (some well above 1+ε, some well below 1-ε) with random advantage signs. Then:
#   (a) report fraction_tokens_clipped(...) for GRPO — the share of tokens whose
#       gradient GRPO has zeroed — and confirm it is > 0;
#   (b) compute the per-token CISPO gradient with gradient_wrt_logp(cispo_surrogate,
#       ...) and confirm NONE of the (nonzero-advantage) tokens has a zero gradient;
#   (c) as you raise eps_high from 0.1 to 1.0, does GRPO's clipped fraction go up or
#       down? Explain why in one line (hint: DAPO's Clip-Higher).

torch.manual_seed(7)
logp_new = torch.randn(50) * 1.5     # off-policy on purpose
logp_old = torch.randn(50) * 1.5
adv = torch.where(torch.randn(50) > 0, 1.0, -1.0)

# Your implementation here:

Summary

Key takeaways:

  1. Test-time compute is a third axis. Beyond bigger models and more data (m07 scaling laws), you can spend more compute at inference to raise accuracy — with the weights frozen.
  2. Self-consistency is sample-and-vote. Draw many chain-of-thought samples, extract each answer, take the plurality. It lifted GSM8K by +17.9 points with no new parameters.
  3. Condorcet explains it. If each sample is correct with probability p > \tfrac12, the majority of n is correct with probability \to 1; below \tfrac12 voting backfires. The real requirement is weaker — the correct answer just has to be the mode, since wrong answers scatter.
  4. Accuracy rises with samples. The compute–accuracy curve climbs (with diminishing returns), and empirically beats the binary Condorcet bound.
  5. Best-of-N uses a verifier instead of a vote, so it can surface a rare correct answer — as good as its scorer, and vulnerable to reward hacking.
  6. Parallel vs. sequential. Sampling-and-aggregating is the parallel branch; RL-trained long self-correcting chains (o1 / R1) are the sequential branch. Both are test-time compute.
  7. GRPO trains reasoning without a critic. Sample a group of answers, use their mean reward as the baseline (A_i = (r_i - \text{mean})/\text{std}), and nudge the policy with a clipped surrogate plus a KL leash. With a verifiable reward (is the answer correct?) it needs no reward model and no labeled traces — the DeepSeek-R1 recipe, built from scratch in grpo.py.
  8. GRPO’s 2024 objective has two provable fixes. Dr. GRPO removes the \tfrac{1}{|o_i|} (a length bias that inflates wrong answers) and the \div\,\operatorname{std} (a difficulty bias that over-weights near-solved and hopeless questions), leaving A_i = r_i - \text{mean}. GSPO replaces the per-token importance ratio with a length-normalized sequence ratio s_i = (\pi_\theta/\pi_{\theta_\text{old}})^{1/|y_i|} — the geometric mean of the token ratios — whose log-variance is \sigma^2/L instead of L\sigma^2, stabilizing long-sequence and MoE training. Built from scratch in grpo_variants.py.
  9. GSPO fixes GRPO at scale by matching the unit of optimization to the unit of reward. GRPO’s per-token importance ratio w_{i,t} is a single-sample weight that does no real correcting; its noise accumulates with response length and collapses long-chain / Mixture-of-Experts training. GSPO puts one length-normalized ratio on the whole sequence, s_i = (\pi_\theta(y_i)/\pi_\text{old}(y_i))^{1/|y_i|}, and clips at the sequence level. On a one-token response s_i = w_i, so GSPO generalizes GRPO; on long ones \text{Var}(\log s_i) = v/L shrinks where the raw product’s grows as Lv. It even removes MoE Routing Replay — the recipe behind Qwen3, built from scratch in gspo.py (Zheng et al., 2025).
  10. DAPO is the recipe, not one theorem. Where Dr. GRPO and GSPO each isolate one clean fix, DAPO stacks four decoupled edits onto GRPO and ships the code: Clip-Higher (asymmetric clip \varepsilon_\text{low}/\varepsilon_\text{high} = 0.20/0.28, room to promote rare good tokens without letting bad ones collapse — fights entropy collapse); Dynamic Sampling (drop the all-right/all-wrong groups whose advantage is exactly zero, keeping 0 < \#\text{correct} < G — a wasted fraction of p^G + (1-p)^G); Token-Level Loss (normalize by total tokens \tfrac{1}{\sum_i|o_i|}, not per-response, so long chains aren’t muffled); and Overlong Reward Shaping (a soft length ramp instead of a hard -1 cliff). It keeps GRPO’s (r-\text{mean})/\text{std} advantage and drops the KL leash — Qwen2.5-32B to AIME’24 50 (past R1-Zero-Qwen-32B’s 47) in half the steps, built from scratch in dapo.py (Yu et al., 2025).
  11. CISPO clips the weight, not the token. GRPO/DAPO clip the token update — the \min(\cdot) surrogate hands a token whose ratio leaves the trust region a zero gradient, silencing exactly the rare high-ratio “fork” tokens (However, Recheck, Wait) that redirect a chain. CISPO rewrites the objective as REINFORCE with a detached, clipped importance weight \operatorname{sg}(\hat r_{i,t}), so every token keeps a bounded gradient and none is ever zeroed. GRPO’s cliff (A\cdot r \to 0) becomes CISPO’s plateau (A\cdot\min(r,1+\varepsilon)). One template with a mask M_{i,t} recovers all three: GRPO/DAPO mask the clipped tokens, CISPO sets M\equiv 1 — MiniMax-M1’s ~2× speedup over DAPO on a Qwen2.5-32B study, built from scratch in cispo.py (MiniMax, 2025).
  12. Search is the third axis. Tree of Thoughts turns reasoning into deliberate search: propose several next thoughts, evaluate each partial state, keep the best few, and backtrack. Chain-of-thought is the b=1 special case; self-consistency is k independent chains with no evaluation. Built from scratch on Game of 24 in tree_of_thoughts.py, with exact Fraction arithmetic and a solvability oracle so soundness and completeness are tested, not assumed.
  13. Beam width buys robustness to a fallible evaluator. With a perfect judge, greedy (b=1) already solves everything; the win from search appears only because the real evaluator (an LLM) makes mistakes. A wider beam keeps a backup when the judge wrongly gives up — the mechanism behind GPT-4’s 4% → 74% jump on Game of 24.
  14. Process supervision beats outcome supervision. An outcome reward model scores only the final answer, so it rewards chains that get lucky — right answer, broken reasoning. A process reward model scores every step; it rejects those false positives and localizes the mistake. Reranking best-of-N by a PRM climbs toward valid solutions while an ORM plateaus (prm.py, built from scratch on an exact arithmetic playground, Lightman et al., 2023).
  15. Aggregate steps with product or min. Collapse the per-step scores with \prod_i p_i = P(\text{all steps correct}) (the paper’s choice, slight length bias) or \min_i p_i (the robust weakest-link); mean and last forgive a single bad step and quietly re-import the outcome model’s blind spot.
  16. Verification and search are one idea. Math-Shepherd labels a step automatically by whether a correct answer is still reachable from it — which is exactly Tree of Thoughts’ is_solvable oracle. A value on a partial solution is the object that guides the search, reranks the samples, and shapes the reward alike.

What’s Next

You now have all three shapes of the reasoning story: the parallel branch (sample-and-aggregate), the sequential branch (GRPO, its 2025 refinements Dr. GRPO, GSPO, and CISPO, and the production recipe DAPO — training a model to reason from verifiable rewards, no critic), and the search branch (Tree of Thoughts — branch, evaluate, backtrack). From here the book turns to serving these compute-hungry models efficiently — Module 14: Quantization shrinks the weights, and speculative decoding speeds the decode — and to Module 15: Retrieval-Augmented Generation and agents that put reasoning to work on live knowledge.

Going Deeper

Core Papers:

Practical Resources: