This section is about a model that learns to reason by training on its own correct answers. You give it problems whose answers you know. It writes step-by-step solutions, you keep the ones that end in the right answer, you fine-tune the model on what you kept, and you repeat. Apart from a handful of worked examples in the prompt, no person writes a solution. This loop is a stage in how today's reasoning models are trained, and interviewers ask what it optimizes and why it eventually stops improving.

Here is the result that made people take the loop seriously. In 2022, Eric Zelikman and colleagues tried it with GPT-J, a language model with 6 billion parameters (Zelikman et al. 2022). One of their benchmarks was GSM8K, a set of grade-school math word problems with 7,473 training problems. Fine-tuned to write the final answer directly, using every training problem and its answer, the model scored 5.8% on the test set. Then they let the same model write its own step-by-step solutions to the training problems. They kept only the solutions that ended in the right answer, fine-tuned on those, and repeated. The final round trained on only a quarter of the problems (25.0%), the ones the model had solved by itself, yet the model reached 10.1%. One more trick, rationalization, which we meet below, raised it to 10.7% (Table 2 of the paper).

How can a model learn from text it wrote itself? It did not grade its own work. Every kept solution passed a check against the reference answer, and that check knows something the model does not. This is the argument of the whole chapter, first made in §26.1. A model can improve on its own outputs only when something that knows more than its own guesses says which outputs were good. Here that something is an answer check, and this loop is the simplest way to turn it into training data. At larger scale the same loop beat fine-tuning on human-written solutions for Google's PaLM 2 models on MATH, a benchmark of competition mathematics problems, and on programming problems (Singh et al. 2023). A version of it is also a stage of the DeepSeek-R1 recipe (§18.5).

This section answers four questions. What does fine-tuning on your own correct answers optimize? We will see that it is a policy gradient step and also an instance of expectation-maximization, a classic recipe for fitting models with hidden variables. Why do implementations that look the same optimize different objectives? What does showing the model the answer cost? And where does the loop stall? The last answer comes down to one number, the chance that a problem produces even one correct sample.

Keep what worked, train on it, repeat

Start with the one-round version from §18.2. Sample many solutions to each training problem, keep the ones a checker accepts, and fine-tune on them. This is rejection sampling fine-tuning (RFT). Run it again and again, each round sampling from the newly fine-tuned model, and you have the loop of this section.

We need a few symbols. A training problem is a prompt $x$ with a reference answer $a^\star$. The model is a policy $\pi_\theta(y\mid x)$, a probability distribution over complete responses $y$, with parameters $\theta$. Each response is a chain of thought that ends in a final answer, which an extractor reads off as $\operatorname{ans}(y)$. The verifier of §18.3 checks that answer and returns a reward of 1 or 0, $R(x, y) = \mathbb{1}[\operatorname{ans}(y) = a^\star]$. The success probability of a problem is the chance that one sample is correct,

In plain words, $p_\theta(x)$ is the fraction of the model's samples that solve problem $x$. §18.2 called it the per-problem pass@1. We write it with $\theta$ because training moves it. Each round draws $n$ samples per problem, and we write $c$ for the number that are correct.

Picture the answer check as a sieve. Pour the model's samples through it, and what stays behind is reasoning that happened to work. Fine-tuning on what stayed shifts probability toward it. The next round samples more reasoning of that kind, and some of it now works on problems that failed before. The sieve can only keep what the model sometimes produces, so the loop climbs exactly as far as its samples reach.

The loop is older than language models, and it has a standard name, expert iteration.

Many famous methods are this template. AlphaZero is expert iteration with a tree search over game moves as the expert (§26.2). STaR, the method of the opening, is expert iteration with greedy decoding plus an answer check (and rationalization, met below) as the expert. Polu et al. (2022) used proof search in the Lean proof assistant as the expert, with Lean's own checker as the verifier. The methods differ only in how the expert is built and how the apprentice's loss is weighted.

Before any theory, look at what one round yields.

Three facts are already visible. Easy problems dominate the data unless we cap how many solutions each problem may contribute. Hard problems contribute rarely, roughly in proportion to $np$ when $np$ is small. And a problem the model never solves is invisible to the loop. The rest of the section makes each of these exact.

The last line previews the question of coverage. A problem solved two times in a thousand contributes data in only 12% of rounds of 64 samples. It takes 347 samples to make that a coin flip.

Many pipelines also keep at most $K_{\max}$ correct solutions per problem, a cap, so that easy problems do not flood the data. The general rule for one round, with and without a cap, is short.

In plain words, a fixed sampling budget sets a floor on which problems the loop can see. Once $p$ falls well below $1/n$, a problem almost never shows up in the data. At $p = 1/n$ it still shows up in about 63% of rounds, since $1 - (1 - 1/n)^n \approx 1 - 1/e$. In an interview, "how many samples do I need before a problem with a 1-in-500 solve rate contributes?" has the answer "about $0.69 \times 500 \approx 350$ for even odds".

import numpy as np
from scipy.stats import binom

def expected_yield(p, n, cap=None):
    raise NotImplementedError

STaR, step by step

STaR, the Self-Taught Reasoner, is expert iteration for chains of thought with one extra move, rationalization. §18.2 sketched it in four steps and gave its result on CommonsenseQA. Here is the algorithm exactly as Zelikman et al. (2022) ran it. Two terms first. A rationale is the chain of reasoning written before the answer. Greedy decoding always picks the most likely next token, so it gives one deterministic response.

Each design choice has a reason, and each has a cost that later parts of the section price.

• Greedy decoding. One rationale per problem per round, built from the most likely token at each step (a high-probability response, though not necessarily the most likely one). Zelikman et al. tried widening the data by sampling at temperature 0.5 or 0.7 instead, and the models got worse, because more answers were right for wrong reasons. Sampling also multiplies generation cost by the number of samples. The cost of greedy decoding is coverage. A problem whose greedy answer is wrong contributes nothing, whatever its $p_\theta(x)$. Rationalization was invented to repair that.
• Restarting from the original model. Each round trains $M$ afresh on the data produced by the latest model, which the authors did "to avoid overfitting". The number of fine-tuning steps starts at 40 and grows by 20% per round.
• Keeping the few-shot prompt during sampling. It reduced drift, the tendency of later rationales to wander away from the style of the examples.

The staged learning on addition is a curriculum nobody designed. We explain it in the part on where bootstrapping stalls.

Filtered fine-tuning is a policy gradient

§18.2 showed that on one batch of samples, the loss of filtered fine-tuning and the REINFORCE loss with 0/1 rewards have the same gradient up to a positive constant. That identity answers a natural question. Fine-tuning on a kept sample raises that sample's probability. Why should that raise accuracy? Because, at the moment the samples are drawn, it is exactly a sampled step of gradient ascent on expected accuracy. Zelikman et al. pointed this out in the paper that introduced STaR, and everything else in this section builds on it.

The tool is the log-derivative trick of §15.3. The gradient of an expected reward equals the expected value of the reward times $\nabla_\theta\log\pi_\theta(y\mid x)$, the gradient of the sample's log probability, which is called the score. Estimating that expectation from samples is the REINFORCE estimator. A tiny case shows the link. Draw 4 samples and suppose only the second is correct. RFT's loss is $-\tfrac14\log\pi_\theta(y_2\mid x)$, so its gradient pushes up $y_2$ with weight $\tfrac14$ and ignores the other three. REINFORCE with rewards $(0, 1, 0, 0)$ does exactly the same.

Proof. The log-derivative trick gives, for each problem,

The verifier does not depend on $\theta$, so no gradient flows through $R$. At $\theta = \theta_{\text{old}}$ the samples come from $\pi_\theta$ itself, so the sample mean $\frac1n\sum_i R(x,y_{x,i})\nabla_\theta\log\pi_\theta(y_{x,i}\mid x)$ is an unbiased estimate of that expectation. Summing over problems gives $-\nabla_\theta\mathcal{L}_{\text{RFT}}$. ∎

In plain words, every kept sample pulls the parameters toward making itself more likely, and the samples the verifier rejects are multiplied by zero. That multiplication by zero is the filter. Throwing failures away is not a heuristic bolted onto RL. It is what the REINFORCE gradient looks like when rewards are 0 or 1 and there is no baseline, a number subtracted from every reward.

STaR departs from this exact statement in three ways, and each one matters.

1. Greedy decoding is not sampling. The theorem needs $y \sim \pi_\theta$. A greedy rationale is a deterministic, high-probability response, not a sample, a biased choice that keeps reinforcing the model's favorite line of reasoning. Zelikman et al. describe this trade as lower variance in exchange for biased exploration.
2. Many gradient steps on one batch. The theorem holds only at $\theta = \theta_{\text{old}}$. After the first optimizer step the samples no longer come from the current model, so they are off-policy. Filtered fine-tuning applies no correction for that, unlike PPO, which reweights by a probability ratio and clips it (§15.6). Training to convergence on the kept set is not a gradient step at all.
3. Restarting from the base. Each round's model is the base model fine-tuned on new data, not the previous model plus a step.

So the policy gradient view explains why the loop improves expected accuracy. It does not explain what fitting the kept data to convergence does, or what restarting does. For that we need a second lens, which comes from two papers at DeepMind.

Self-training as growing-batch reinforcement learning

Growing-batch reinforcement learning collects a dataset with the current policy, then improves the policy offline on that fixed dataset, then collects again. (Plain batch RL learns once from a single fixed dataset.) The self-training loop has exactly this shape.

The "EM" in the name is a claim. It is true in a precise sense, which we now prove.

ReST-EM is expectation-maximization

Expectation-maximization (EM) is a recipe for maximizing a likelihood that sums over something hidden. Here the observed fact is "the model answered problem $x$ correctly", and the hidden part is which chain of thought it wrote to get there. EM alternates two steps. The E-step makes a best guess at the hidden part, here by collecting the model's own correct responses. The M-step fits the model to that guess, here by fine-tuning on them. The objective EM climbs is $\sum_x \log p_\theta(x)$, the log probability of solving each training problem, summed over problems.

The distribution the E-step produced, the model's own responses restricted to the correct ones and renormalized, has a name, and the rest of the section uses it often.

Now the claim in ReST-EM's name can be stated and proved. Any distribution on correct responses gives a lower bound on the log probability of success, and the success-conditioned policy is the one that makes the bound tight.

In plain words, each round asks "which of my own correct answers would I have produced?" and then "make those more likely". Sampling and filtering answer the first question exactly, and fine-tuning does the second. If the fine-tuning really improves its objective, the log probability of solving the training problems can only go up. The bound $F_x$ is the evidence lower bound (ELBO) of variational inference, with the response as the hidden variable and "correct" as the observation. §32.2 derives the general ELBO and runs the same two steps on Gaussian mixture models. There the E-step computes how much each point belongs to each cluster, and the M-step refits each cluster's weight, mean, and covariance.

Three consequences follow, and each one is a common interview probe.

The M-step in practice is fine-tuning normalized per prompt. We cannot compute an expectation under $\pi^{+}_{\theta_t}$, but the kept samples are exact draws from it. So for a problem with $c_x \ge 1$ correct samples, the estimate of its M-step term is $\frac{1}{c_x}\sum_{\text{kept}}\log\pi_\theta(y\mid x)$. Every solved problem gets total weight 1, however many of its samples were correct. Hold that thought, because it is not what most implementations do.

A lookup table memorizes in one step. Suppose $\pi_\theta(\cdot\mid x)$ could be any distribution for each $x$, as in the four-response example. Cross-entropy is maximized by matching the target, so the M-step would set $\pi_{\theta_{t+1}} = \pi^{+}_{\theta_t}$. That has success probability 1 on every problem that was ever solved, so EM converges in one round by memorizing the solutions it found. With a real network the M-step is a projection. It picks the member of the model family closest to $\pi^{+}_{\theta_t}$, in the sense of the summed divergence $\sum_x D_{\mathrm{KL}}(\pi^{+}_{\theta_t}\Vert\pi_\theta)$. The parameters are shared across problems, so fitting the solved problems moves the unsolved ones too. Everything interesting about bootstrapping lives in that projection, including generalization to the test set and the curriculum effects later in this section.

Restarting from the base costs nothing in theory and helps in practice. When the M-step has a unique maximizer, its value does not depend on where the optimizer starts. So ReST-EM's choice to fine-tune the base model each round changes nothing in the theorem. In practice fine-tuning stops long before the maximum, because it is early-stopped when reward on a validation set stops improving. Then the starting point acts as a regularizer that limits drift from the base. Singh et al. found that restarting matched continuing from the last iterate on APPS, a benchmark of programming problems, and transferred much better to HumanEval, another code benchmark. The price is the theorem's guarantee, since an early-stopped M-step need not increase $F$. Separately, ReST-EM's test accuracy on APPS fell in the second iteration while its training accuracy kept rising. Singh et al. attribute this to overfitting a small set of training problems.

How you average the loss decides what you optimize

Here is a detail that looks like bookkeeping. You have a batch of samples, some correct. You can average the loss over all samples drawn for a prompt. You can average it over each prompt's kept samples. Or you can weight each sample by its advantage, as GRPO does. GRPO, the group-relative policy gradient of §18.4, is the standard algorithm for RL with verifiable rewards (RLVR), reinforcement learning against an answer check. It samples a group of responses per prompt. It scores each one by its reward minus the group's mean reward, divided by the group's standard deviation. These three choices are different objectives, and we can say exactly which.

Now the general case. Singh et al. write their Improve step (Algorithm 1 and Equation 3 of their paper) as the reward-weighted log-likelihood averaged over all generated samples. That is the per-sample normalization of the RFT theorem, not the per-prompt normalization the EM derivation produces. Their cap of 10 kept solutions per problem moves it partway back, as we will see.

Fix one prompt with success probability $p = p_\theta(x)$. Draw $n$ samples $y_1, \dots, y_n \sim \pi_\theta(\cdot\mid x)$ with rewards $R_i$, and let $C = \sum_i R_i$ be the number correct. Write $\nabla$ for $\nabla_\theta$. Three estimators of an update direction are in common use,

Here $\hat A_i = (R_i - \bar R)/(s + \epsilon)$ is the GRPO advantage, with $\bar R = C/n$, $s$ the sample standard deviation of the $R_i$ (with $n - 1$ in the denominator), and $\epsilon > 0$ small. The first estimator is filtered fine-tuning averaged over all samples (STaR, RFT). The second is fine-tuning averaged over each prompt's kept samples (EM). The third is GRPO with one update per batch.

In plain words, all three push every prompt in the same direction, the one that raises its success probability. They differ only in how loudly each prompt speaks. RL weighs a unit of progress equally everywhere. EM multiplies a prompt's voice by $1/p$, so a prompt solved once in a hundred tries speaks a hundred times louder than a solved one. On hard prompts, with $p$ below one half, GRPO sits in between. On easy prompts it gives more weight than either, because its weight $1/\sqrt{p(1-p)}$ is symmetric about one half, so GRPO also boosts prompts it nearly always solves. Two caveats keep the theorem honest. At finite $n$ the per-prompt estimator falls short of $\nabla\log p$ by the factor $1 - (1-p)^n$, the coverage of the round. And the theorem is about the expected update at the sampling policy, so it describes one on-policy step, not a fine-tuning run to convergence on a fixed dataset.

The last column settles the question about ReST-EM. ReST-EM averages its loss over all generated samples, so every kept sample has the same weight, and the cap lets a prompt keep at most $K_{\max}$ of them. Each kept sample is a draw from $\pi_\theta^{+}$, so the expected sum of a prompt's kept scores is $\mathbb{E}[\min(C, K_{\max})]\,\nabla p/p$. With no cap the same sum is $\mathbb{E}[C]\,\nabla p/p = n\,\nabla p$, which is RL's expected update times $n$. So the cap gives the prompt a weight of $\mathbb{E}[\min(C, K_{\max})]/(np)$ relative to RL.

In ReST-EM's setting that weight is 0.35 at $p = 0.9$, 0.62 at $p = 0.5$, and 1.00 for every $p \le 0.1$, since the cap rarely binds there. The method named after EM sits much closer to RL than to EM. Precisely, the per-sample M-step is itself EM, but on a different objective, $\log\sum_x p_\theta(x)$, the log of the expected number of problems solved. Its E-step treats the prompt as hidden too, putting weight proportional to $\pi_{\theta_t}(y\mid x)R(x, y)$ on each correct pair, so each prompt's share is proportional to its $p$. The gradient of that objective points the same way as RL's, which explains both the name and the weighting. What its cap does is stop easy problems from dominating, which is the reason Singh et al. gave for it. A cap of $K_{\max} = 1$ gives EM's weighting up to a constant factor, and $K_{\max} = n$ gives RL's, so the cap moves between the two objectives.

Before trusting a proof, check it. The cell draws 40,000 groups of 8 samples from a softmax policy over five responses, two of them correct, and compares each estimator's average with the theorem.

Every coordinate of each average is the same multiple of $\nabla p$, up to Monte Carlo noise. The multiples match the predicted 1.000, 4.194, and 1.975. The three estimators really are parallel, and the theorem's scalar is the whole difference.

The widget below plots each method's weight against $p$ and shows where the whole update goes for a population of prompts.

In an interview, the short version is this. Two teams run "the same" filtered fine-tuning, one averaging the loss over samples and one over prompts. The first optimizes $\sum_x p$ and the second $\sum_x \log p$. The second team spends far more of its update on hard problems.

Do the discarded failures matter?

GRPO uses the wrong samples and filtered fine-tuning throws them away. Yet the theorem says both expected updates point along $\nabla p$. So the failures do not change the direction of the expected update. They change two other things.

The first is variance. Subtracting a baseline $b$ from every reward adds no bias (§15.4), so $\frac1n\sum_i(R_i - b)\nabla\log\pi_\theta(y_i\mid x)$ has the same mean as $\hat{\mathbf{g}}_{\text{RL}}$ for any constant $b$. The wrong samples are what carry the baseline's $-b$. How much does it buy? The answer is a factor of $1/(1-p)$, a lot on easy prompts (10 times at $p = 0.9$) and almost nothing on hard ones.

The cell measures it on a softmax over 400 responses.

The second thing failures change is what happens away from the sampling policy. The theorem describes one step at $\theta_{\text{old}}$. Fitting a fixed set of correct samples to convergence keeps pushing up those exact samples and pushes nothing down, so wrong responses that resemble the kept ones rise with them. Pang et al. (2024) measured this on GSM8K. Fine-tuning only on correct chains raised the log probabilities of the model's incorrect chains almost as much. On-policy RL with negatives resamples every step and pushes down what it actually produces wrong.

And there is a case where nothing helps. If all $n$ samples are wrong, $C = 0$ and all three estimators are exactly zero. Negatives cannot rescue a problem the model never solves.

import numpy as np

def grad_estimates(u, r, ys, eps=1e-6):
    raise NotImplementedError

def expected_gradients(u, r, n):
    raise NotImplementedError

Rationalization is approximate posterior inference

Plain expert iteration learns nothing from a problem the model never solves. STaR's rationalization attacks exactly those problems by showing the model the answer. §18.2 named its cost informally, training on text from a distribution the model only produces when it has the hint. The EM view lets us say precisely what the right target is and how far rationalization lands from it.

Split each response into a rationale $z$ and a final answer $a$, so $\pi_\theta(y\mid x) = \pi_\theta(z\mid x)\,\pi_\theta(a\mid x, z)$. In STaR the answer is read off the end of the rationale ("Therefore, the answer is (b)"). We idealize by assuming that $\pi_\theta(a\mid x, z)$ is the same whether or not the prompt contained a hint. In reality the hint also makes $a^\star$ easier to write at the end, which only adds false positives. We also model STaR's rationalization as sampling, though STaR decodes it greedily. Zelikman et al. themselves suggested this reading. They framed rationalization as sampling from the hinted model as a proposal distribution, a stand-in sampler whose draws estimate an average under the model's own distribution. The success probability is then a sum over rationales, $p_\theta(x) = \sum_z \pi_\theta(z\mid x)\,\pi_\theta(a^\star\mid x, z)$.

The right target for an unsolved problem follows from Bayes' rule. Take the rationales the model would write on its own, and weight each by how likely it is to end in the right answer. That is the posterior over rationales. Rationalization instead writes rationales with the answer in view.

The posterior is the right target because the gradient of $\log p_\theta(x)$ is an average under it. A distribution that differs from the posterior can be corrected by an importance weight, the ratio of the target's probability to the sampler's.

In plain words, here is how a model should learn from a problem it cannot solve. It should find the rationales it might itself have written that end at the right answer. It should weight them by how likely it was to write them, and make those more likely. Rationalization finds the rationales the model writes when it already knows the answer. When the hint only helps the model find its own good reasoning faster, the two agree. When the hint lets it write something it would never write unaided, a story that works backward from the answer, rationalization trains on that story as if it were reasoning. This is the faithfulness problem of §18.1, whether a written chain of thought reflects how the answer was really reached, turned into a training signal.

Why not apply the weights? For real rationales the weight is a ratio of two sequence probabilities, each a product over hundreds of tokens. So $\log w(z)$ is a sum of hundreds of per-token log-ratios. Wherever the hint changes the text, those terms pile up, the weights spread over many orders of magnitude, and the effective sample size $(\sum w)^2/\sum w^2$ collapses toward a single sample. The weights are smallest on exactly the rationales the hint created. So the correction mostly throws the rationalized samples away again, which returns us to plain expert iteration.

The principled alternative is to sample the posterior directly. TRICE (Phan et al. 2023) does this with Markov chain Monte Carlo (MCMC), a way to draw from a distribution you can only score. It beat STaR by about 11 points on average across the 27 BIG-Bench Hard reasoning tasks. Singh et al. reported the other side of rationalization's bias in one sentence. In their preliminary experiments it caused a substantial increase in false positives, solutions with the right answer and wrong reasoning, so ReST-EM does not use it.

In practice the safe default is the one ReST-EM chose. To reach hard problems, spend more samples under a strict answer check rather than show the answer. If you do use hints, audit a sample of what they produce. An interviewer who asks about rationalization wants three things. The right target is the posterior over the model's own rationales. The hint-conditioned proposal is biased toward stories that work backward from the answer. And importance weights fix the bias in theory but collapse on long sequences.

import numpy as np

def posterior(prior, lik):
    raise NotImplementedError

def star_target(proposal, lik):
    raise NotImplementedError

Coverage, and where bootstrapping stalls

Now the question of the opening, what stops the loop. The coverage theorem says a problem with success probability $p$ contributes with probability $1 - (1-p)^n$, which is about $np$ when $np$ is small. A problem at $p = 0$ contributes nothing, and one at $p \ll 1/n$ contributes rarely. Whether the loop ever reaches such a problem depends on something the coverage theorem does not see. Does learning on other problems raise its $p$?

To see this clearly, strip everything away. Give each training problem a difficulty $d_x$ and give the model a skill. In the shared model one number $\theta$ is the skill for every problem, and $p_\theta(x) = \sigma(\theta - d_x)$, where $\sigma(z) = 1/(1 + e^{-z})$ is the logistic sigmoid. Then $\nabla_\theta\log p_\theta(x) = 1 - p_\theta(x)$. In the tabular model each problem has its own skill $\theta_x$, and $p = \sigma(\theta_x - d_x)$. The shared model stands for a network whose parameters serve every problem, and the tabular model for a lookup table.

Each round samples $n$ attempts per problem and takes the per-prompt EM step of the theorem. The shared skill moves by $\theta \leftarrow \theta + \eta\cdot\operatorname{mean}_x\,\mathbb{1}[C_x \ge 1](1 - p_x)$, with step size $\eta$. Each tabular skill moves by $\theta_x \leftarrow \theta_x + \eta\,\mathbb{1}[C_x \ge 1](1 - p_x)$. Rationalization, when it is on, gives each failed problem one hinted attempt that succeeds with probability $\sigma(\theta - d_x + b)$, so the hint is worth $b$ units of difficulty.

The three panels tell the story of this section in miniature. The tabular model solves what it could already sample and stops, at about 57% of the problems, because a problem's skill moves only when that problem produces a correct sample. Rationalization extends its reach by about 1.5 units of difficulty, to 71%, only half the hint's worth $b = 3$. The reason is that the hint is one attempt against eight. Far past the frontier $p \approx e^{\theta - d}$, so the eight unhinted samples succeed with probability about $8e^{\theta - d}$ and the hinted attempt with about $e^{3}e^{\theta - d} \approx 20e^{\theta - d}$. The hint makes a contribution only about 3.5 times as likely, which is worth $\ln 3.5 \approx 1.25$ units of difficulty. The shared model climbs the entire ladder. Every solved problem raises the one skill that all problems use, which raises $p$ on the next-harder problems until they start producing samples of their own. That is a curriculum nobody designed, and it is what STaR saw on addition, poor at $n$ digits until it was good at $n - 1$.

The widget runs the expected version of this toy. Choose a ladder of difficulties, the number of samples, and whether skill is shared, then press Play to run the rounds. Turning on hints adds rationalization, one extra attempt on each failed problem with the answer shown, which makes it 3 units of difficulty easier.

The gap is the clean case of a stall. While the skill is inside the easy band, the easy problems drive it up. Once they are solved, $1 - p_x \to 0$ for all of them and their pull fades, while the hard problems are still too far away to produce samples. The skill then creeps up only slowly, and whether it reaches the hard band within the budget depends on $n$, because the first hard successes arrive at a rate of about $np$. In the expected toy with $n = 4$, every easy problem reaches a success probability of one half by round 7. The first hard problem, at difficulty 10, reaches it only at round 32. With $n = 64$ it gets there at round 13. Real datasets have gaps of this kind wherever a new idea is needed that no easier problem teaches. In practice a plateau of this kind is the signal to change something. Add stepping-stone problems, spend more samples on the frontier, or switch to a method that explores.

import numpy as np

def bootstrap(d, n, rounds, shared=True, eta=3.0, theta0=1.0, rationalize=False, b=3.0):
    raise NotImplementedError

def first_solved_round(history, thresh=0.5):
    raise NotImplementedError

Right answers for the wrong reasons

The sieve checks the answer, not the reasoning. A sample can reach $a^\star$ by luck, by a wrong argument, or by two errors that cancel. Every such sample is kept and trained on as if it were good reasoning. How much of the kept data is like that?

§26.1 gave the tool, the precision of a filter, the fraction of kept samples that are really good. Here the filter judges reasoning, so we need a new symbol. Suppose a sample's reasoning is genuinely correct with probability $\rho$. This $\rho$ plays the role of the generator's accuracy $p$ in the formula there, and it is not this section's $p_\theta(x)$, the chance that the answer is right. The filter accepts correct reasoning with probability $\mathrm{TPR}_g$ (its true positive rate) and incorrect reasoning with probability $\mathrm{FPR}_g$ (its false positive rate). Bayes' rule gives the fraction of kept samples with correct reasoning,

The formula explains three observations from the papers. First, STaR found that sampling at a higher temperature raised the share of right answers reached by wrong reasoning. Wider sampling lowers the chance that a sample's reasoning is right while the chance of a lucky landing stays put, so precision falls. Second, rationalization raises $\mathrm{FPR}_g$ toward 1, because a model that can see the answer can write it at the end of nearly any argument. That is why ReST-EM saw a substantial increase in false positives and dropped it. Third, every false positive of the answer grader (§18.3) is worse in self-training than in evaluation, because each one becomes a training example that teaches the model to repeat it.

DeepSeekMath-V2 (Shao et al. 2025) states the frontier version of the same worry in its abstract, that "correct answers don't guarantee correct reasoning". Its response is to train a verifier that judges whole proofs instead of trusting final answers. The lesson of this chapter applies. Self-training is exactly as good as the check it filters by.

Learning from your own mistakes

The loop above throws away every wrong sample, often most of what it generates. Two methods put the wrong samples to use, in different ways. Both rely on DPO, direct preference optimization (§17.2). DPO trains a model on pairs of a preferred and a rejected response. It raises the log-probability margin of the preferred one over the rejected one, each measured relative to a fixed reference model.

Train a verifier on the failures. V-STaR (Hosseini et al. 2024) trains the generator as in STaR and uses the failures to train a verifier, a model that scores solutions. At each iteration it samples $k = 16$ solutions per training problem from the current generator. The correct ones join the generator's training set, and all of them, correct and incorrect, join a verifier training set. The generator's set starts with the dataset's own solutions, and each iteration fine-tunes the base model on the set so far. The verifier is trained with DPO on pairs of a correct and an incorrect solution to the same problem. It uses every such pair from all iterations so far, with the supervised fine-tuned model as the reference. It scores a solution by the solution's likelihood under the verifier. At test time the verifier picks the best of many samples.

The authors fine-tuned LLaMA 2 and CodeLLaMA at 7B and 13B parameters for three iterations. They used LoRA, small low-rank adapter matrices trained on top of a frozen model. The benchmarks were GSM8K for math and MBPP, a set of short Python programming problems, for code. V-STaR improved test accuracy over earlier self-improvement and verification methods by 6 to 17 percentage points on math and 4 to 12 on code. The 7B model surpassed base LLaMA 2 70B (8-shot) on GSM8K. Iterating mattered. Spending the same 48 samples per problem in a single round gave a weaker verifier, which the authors attribute to the better data that later, stronger generators supply.

Train the generator on pairs. Iterative Reasoning Preference Optimization (Pang et al. 2024) trains the generator itself. Each iteration samples chains of thought for every training prompt and forms pairs whose winner reached the correct answer and whose loser did not. It trains with the DPO loss plus a negative log-likelihood (NLL) term on the winner, normalized by its length, starting from the previous iteration's model. On GSM8K, Llama-2-70B-Chat went from 55.6% zero-shot to 73.1%, 78.0%, 81.1%, and 81.6% over four iterations, and to 88.7% with majority voting over 32 samples, against 70.7% for the starting model with the same vote. Supervised fine-tuning (SFT) on the gold chains of thought written for the dataset reached only 63.5%.

The NLL term was essential. Plain DPO on the first iteration's pairs reached only 61.8%. Without the NLL term, the log probability of the chosen chains fell during training even as their margin over the rejected chains grew, the likelihood displacement of §17.5. The NLL term is filtered fine-tuning, so Iterative RPO is STaR's loss plus a contrastive push away from the model's own wrong chains.

In practice the choice is where to spend the failures. At test time there is no reference answer to check against. A verifier trained on the failures stands in for that check and buys accuracy through best-of-$n$ selection, at the price of many samples per query. A preference loss on the model's own pairs instead uses the failures to train the generator itself, so it improves even a single sample at test time. Either way, keep the NLL term on the correct answers. An interviewer will ask why plain DPO on correct-versus-wrong pairs can lower the probability of the correct chains, and the answer is likelihood displacement.

import numpy as np

def build_pairs(problem, iteration, text, correct, upto):
    raise NotImplementedError

def pair_accuracy(pairs, score):
    raise NotImplementedError

The loop at real scale

The largest careful study of the loop is ReST-EM's, and its numbers are the ones to remember.

The same paper ran ablations that say where the gain comes from, and most of them echo a result of this section.

The loop also runs where the check is not a reference answer, as long as something outside the model still decides what to keep.

The whole family fits in one table. Each row says how the data are made, what filters them, what loss the apprentice uses, where each round starts, and whether the failures are used.

From bootstrapping to RL with verifiable rewards

STaR, RFT, ReST-EM, and GRPO with verifiable rewards are often called the same idea. The theorem of this section says exactly in what sense that is true. All of them use the same 0/1 signal. When the responses are sampled from the policy, the expected update each makes on a prompt points along $\nabla p_\theta(x)$ (STaR's greedy decoding is the exception, a biased choice). So all of them climb some $\sum_x f(p_\theta(x))$ with $f$ increasing. If the model can represent it, their objectives share a maximizer on a finite training set, every problem solved with certainty. And all of them are blind at $p = 0$. None of them can reinforce a success it never samples. This is the cleanest statement of why the skeptical evidence in §18.5 finds that RL with verifiable rewards mostly sharpens what a base model can already sample, with pass@$k$ curves that cross at large $k$. (Pass@$k$ is the chance that at least one of $k$ samples is correct. That section also gives the counter-evidence from long RL runs.) These methods reweight the model's own samples. Only transfer through shared parameters, the curriculum effect, reaches genuinely new problems.

It is false in four senses. The weighting $f$ differs ($p$, $\log p$, $2\arcsin\sqrt p$), so the methods trade easy problems against hard ones differently. Batch methods fit a fixed dataset to convergence, far from the policy that generated it. On-policy RL takes small steps from fresh samples inside a trust region, a limit on how far one update may move the policy. Negatives cut variance in RL, and they train verifiers or preference losses elsewhere. And exploration differs, from greedy STaR to temperature sampling to search.

A practical rhythm follows. Start with the batch loop because it is cheap and stable. Watch the fraction of problems that contribute and the held-out accuracy. Switch to on-policy RL when the kept set stops growing. Late in training, use rejection sampling plus fine-tuning again, as R1 does before its final RL stage, to distill the RL policy's best behavior into a clean model.

In PyTorch

The block below runs exact EM on a small log-linear policy, $\pi_\theta(y\mid x) = \operatorname{softmax}_y(\boldsymbol\phi(x, y)^\top\theta)$, with 8 features shared across 64 prompts of 16 candidate responses each. The policy is small enough that the E-step can be computed in closed form and the M-step solved to convergence from the base each round. The block compares per-prompt weights (EM) with per-sample weights (filtered SFT averaged over samples). Then it shows that a lookup-table policy jumps to certainty in one EM step.

With per-prompt weights, $\sum_x\log p_\theta(x)$ rises every round, which is the monotonicity theorem at work. With per-sample weights the mean success probability rises faster, while $\sum_x\log p$ peaks and then falls, because that objective is willing to give up hard prompts for easy ones. The per-sample run is EM on $\log\sum_x p_\theta(x)$, which is why mean $p$ rises every round. The lookup table reaches nearly certain success on every prompt after one M-step. That is memorization rather than learning, which is why the generalization of real self-training lives in the shared parameters.

Read more

• Zelikman et al. (2022). STaR: Bootstrapping Reasoning With Reasoning. The algorithm, rationalization, the policy gradient interpretation in Section 3.1, and the discussion of temperature and few-shot prompts in Section 5.
• Anthony, Tian & Barber (2017). Thinking Fast and Slow with Deep Learning and Tree Search. Expert iteration as a general reinforcement learning template, with tree search as the expert.
• Singh et al. (2023). Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Models. ReST-EM, its EM derivation in Section 3, and the most careful ablations of the loop at scale.
• Gulcehre et al. (2023). Reinforced Self-Training (ReST) for Language Modeling. Grow and Improve steps with rising thresholds, as growing-batch RL for translation.
• Phan et al. (2023). Training Chain-of-Thought via Latent-Variable Inference. TRICE, which samples the posterior over rationales by MCMC and explains STaR's underweighting of hard questions.
• Polu et al. (2022). Formal Mathematics Statement Curriculum Learning. Expert iteration in Lean, and the clearest evidence that a shared model can climb a curriculum of unproven statements.
• Hosseini et al. (2024). V-STaR: Training Verifiers for Self-Taught Reasoners. Using the loop's failures to train a DPO verifier for best-of-$k$ selection.
• Pang et al. (2024). Iterative Reasoning Preference Optimization. DPO plus NLL on correct versus incorrect self-generated chains, and why the NLL term is needed.

Watch next

▶

▶

▶