Self-improving agents: verifiable rewards, search over reasoning, and self-critique

Why this subject matters now

Until roughly 2022, a trained language model was a fixed object. Its accuracy on a task was whatever one forward pass produced, and the only way to improve it was to train a bigger one on more data. Three ideas broke that assumption. First, chain-of-thought prompting (Wei et al., 2022) and scratchpads (Nye et al., 2021) showed that the same weights produce substantially better answers when allowed to emit intermediate reasoning tokens before committing to an answer, which means capability is partly a function of inference-time compute, not weights alone. Second, sampling many reasoning paths and aggregating them, by majority vote (Wang et al., 2023), by reward-model ranking (Stiennon et al., 2020, and Ouyang et al., 2022), or by tree search (Yao et al., 2023), turned out to buy accuracy at a smooth, predictable exchange rate, so much so that Snell et al. (2024) could show test-time compute sometimes substituting for an order of magnitude of model scale. Third, and most consequentially, the improved outputs can be filtered by a verifier and fed back as training data. STaR (Zelikman et al., 2022) did this with a few thousand problems, and by 2024-2025 the same loop run at industrial scale with reinforcement learning, OpenAI's o1 and DeepSeek-R1, produced models that spontaneously learned to plan, backtrack, and check their own work, with accuracy on competition mathematics climbing from the teens to the high seventies over the course of training (DeepSeek-AI, 2025, reports pass@1 on AIME 2024 rising from 15.6% to 71.0% for R1-Zero).

The practitioner bar moved with the field. Five years ago it was enough to know how to fine-tune on labeled data. Today an applied engineer is expected to say precisely why majority voting works and when it amplifies error instead, how much distributional damage best-of-n selection does as a function of n, why optimizing against a learned reward model degrades true quality past a predictable point, why process supervision beats outcome supervision for search but introduces its own attack surface, how the STaR loop relates to expectation maximization and to AlphaZero, and how to compute pass@k without bias from a finite sample budget. They are also expected to know the failure catalog. Every self-improvement loop optimizes a proxy, and every proxy documented in the literature has been gamed, from a boat driving in circles for points (the CoastRunners incident, OpenAI 2016) to models special-casing unit tests. The mathematics of the loops and the taxonomy of their failures are the two halves of this page.

Core theory

Chain-of-thought as marginalization over latent reasoning

Fix a question \( x \) and let \( y \) range over final answers. A model prompted to reason emits a rationale \( z \), a sequence of intermediate tokens, before its answer, so the model defines a joint distribution \( p_\theta(z, y \mid x) = p_\theta(z \mid x)\, p_\theta(y \mid x, z) \). The rationale is not observed in the task specification and not scored by any grader. It is a latent variable, and the object the task actually cares about is the marginal

This one identity organizes most of the page. Greedy decoding returns the answer attached to (approximately) the single most probable rationale, \( \hat{y}_{\text{greedy}} \approx \arg\max_y \max_z p_\theta(z, y \mid x) \), which is the mode of the joint. The mode of the joint and the mode of the marginal can disagree badly. A correct answer often has its probability spread across many distinct valid derivations, while a tempting wrong answer may ride on one high-probability shortcut. Concretely, if the correct answer is reachable by 40 rationales of probability 0.01 each while a wrong answer has a single rationale of probability 0.15, the joint mode picks the wrong answer even though the marginal favors the correct one 0.40 to 0.15. Sampling rationales and aggregating answers estimates the marginal instead of the joint mode, and that is the entire content of self-consistency, derived next.

Why do the intermediate tokens help at all? Two compatible reasons. Statistically, pretraining corpora contain worked derivations, so conditioning on a partial derivation moves the model onto a manifold where the next step is locally predictable. The hard global prediction is decomposed into easy local ones. Computationally, a transformer with fixed depth performs a bounded number of sequential steps per token, and problems that require more serial computation than the depth affords cannot be solved in one forward pass. Writing intermediate results into the context acts as external memory and converts the network from a fixed-depth circuit into an iterated one. Nye et al. (2021) demonstrated this directly with scratchpads for multi-digit arithmetic and program tracing, tasks where the required serial computation visibly exceeds what one pass can do, and Wei et al. (2022) showed the same effect emerges from prompting alone once models are large enough. The theory community has since made the circuit-complexity version of this argument precise, showing constant-depth transformers with polynomial chain-of-thought steps can simulate circuits they provably cannot express in a single pass. The proofs are out of scope here and live in Merrill and Sabharwal (2024, arXiv:2310.07923) and related work.

Self-consistency: the majority vote as a Monte Carlo estimator

Self-consistency (Wang et al., 2023) samples \( m \) rationale-answer pairs \( (z_1, y_1), \dots, (z_m, y_m) \) independently from \( p_\theta(\cdot \mid x) \) at some temperature, discards the rationales, and returns the plurality answer

The vote count \( \frac{1}{m}\sum_i \mathbf{1}[y_i = y] \) is an unbiased Monte Carlo estimate of the marginal \( p_\theta(y \mid x) \), so the plurality answer is the plug-in estimate of \( \argmax_y p_\theta(y \mid x) \). By the law of large numbers the vote fractions converge to the true marginals, so as \( m \to \infty \) self-consistency returns the marginal mode with probability one, provided the mode is unique. The interesting question is the rate, and it is worth deriving because it explains the empirical shape of every self-consistency curve, fast gains for the first handful of samples, then a long plateau.

Take the binary case first. The correct answer is sampled with probability \( p > \tfrac12 \) per draw and one specific wrong answer otherwise. With \( m \) odd, the vote errs exactly when the correct answer receives \( \lfloor m/2 \rfloor \) or fewer votes, a binomial tail event for \( X \sim \mathrm{Bin}(m, p) \),

Hoeffding's inequality applied to the mean of the indicators, which must fall below \( \tfrac12 \) for an error, gives the exponential envelope

so the error decays geometrically in \( m \) with a rate governed by the squared margin above one half. The same argument covers many wrong answers. Let the correct answer have marginal probability \( p_1 \) and the strongest wrong answer \( p_2 < p_1 \). Note that \( p_1 \) may be well below one half. For any wrong answer \( j \), define \( D_i = \mathbf{1}[y_i = 1] - \mathbf{1}[y_i = j] \), which is bounded in \( [-1, 1] \) with mean \( p_1 - p_j \ge p_1 - p_2 \). The vote prefers \( j \) over the correct answer only if \( \frac1m\sum_i D_i \le 0 \), which Hoeffding bounds by \( \exp(-m(p_1 - p_j)^2/2) \) since the range of each \( D_i \) is 2. A union bound over the \( K - 1 \) wrong answers gives

Two design lessons fall out of the algebra. First, what matters is the gap between the correct answer's marginal and the best wrong answer's, not whether the model is right more than half the time. A model that is right 35% of the time with errors scattered across dozens of distinct wrong answers is an excellent self-consistency candidate. Second, the bound is exponential but the constant is the squared gap, so when the gap is small the plateau is long, and when the gap is negative, that is, the model's modal answer is wrong, voting converges confidently to the wrong answer. Self-consistency amplifies whatever the marginal already prefers. Sampling temperature tunes this tradeoff. Temperature zero collapses the estimator to greedy decoding (one vote, no marginalization), and excessive temperature flattens the marginal until the gap vanishes.

Best-of-n against a reward model, and the KL price of selection

Voting needs answers that can be compared for exact equality. When answers are free-form, the aggregator becomes a scorer. Sample \( n \) completions from the base policy \( \pi_0 \), score each with a reward model \( r \), and return the argmax. This best-of-n (BoN) policy \( \pi_{\text{bon}} \) is used three ways in practice, as a pure inference-time improvement (rerank candidates), as a data generator for distillation (rejection-sampling fine-tuning), and as the reference point against which RL fine-tuning is judged (Stiennon et al., 2020, and Ouyang et al., 2022 both report BoN baselines). The fundamental question about BoN is how far it moves the policy from \( \pi_0 \), because distance from the base policy is the budget that reward-model errors spend, as the next section makes quantitative.

Derive the BoN distribution. Assume rewards have a continuous distribution under \( \pi_0 \) so ties have probability zero, and let \( F(t) = \P_{x \sim \pi_0}(r(x) \le t) \) be the reward CDF. The selected sample has reward equal to the maximum of \( n \) i.i.d. draws, and a draw at reward level \( r(x) \) wins exactly when the other \( n - 1 \) draws all land below it, so the density of the selected sample is

The KL divergence to the base policy is then

Under \( \pi_{\text{bon}} \), the random variable \( U = F(r(x)) \) is the maximum of \( n \) independent Uniform(0,1) variables (the probability integral transform sends each reward to a uniform), so \( U \) has density \( n u^{n-1} \) on \( [0,1] \). The needed expectation is a one-line integration by parts,

and substituting back gives the exact, distribution-free identity

The result deserves a pause. It does not depend on the reward model, the base policy, or the task. Selection by rank is a fixed-size distributional intervention. For discrete completions ties occur, the selection is effectively less sharp, and the identity becomes an upper bound on the true KL. Beirami et al. (2024) work out the exact discrete expression and show the classical formula can substantially overestimate the divergence when many samples share reward values. The growth is logarithmic. \( n = 4 \) costs 0.636 nats, \( n = 16 \) costs 1.835, \( n = 64 \) costs 3.175, \( n = 1024 \) costs 5.932. Squeezing one more nat of optimization pressure requires roughly \( e \times \) more samples, which is why BoN is cheap to make mild and exponentially expensive to make aggressive, and why KL-matched comparisons between BoN and RL fine-tuning (which can spend arbitrary KL) are the standard methodology since Gao et al. (2023).

Process versus outcome reward models

A reward model for reasoning can grade two different things. An outcome reward model (ORM) scores a finished solution, typically by predicting whether the final answer is correct. It is trained from (solution, correct/incorrect) pairs that a final-answer checker can label automatically. A process reward model (PRM) scores each step of a solution, trained from step-level labels. Uesato et al. (2022) ran the first careful comparison on grade-school math and found the two roughly tied on final-answer error rate, but process supervision produced far fewer solutions that reach the right answer through wrong reasoning. Lightman et al. (2023) scaled the comparison up on harder competition problems with 800,000 human step labels (the PRM800K dataset) and a stronger base model, and found a decisive gap. Selecting the best of 1,860 sampled solutions by PRM score solved 78.2% of their MATH test subset, against 72.4% for an ORM and 69.6% for majority voting (figures reported in the paper).

The mechanism behind the gap is credit assignment, the same issue that motivates actor-critic methods over vanilla REINFORCE (the deep RL page derives that machinery). An outcome label on a 20-step solution says one bit about the conjunction of 20 steps. A false positive, a wrong derivation that stumbles onto the right number, trains the ORM to approve garbage. Step labels localize the error. There is also a useful identity lurking here. A PRM evaluated at a prefix is structurally a value function, an estimate of eventual success given the partial solution, which is why PRMs slot directly into beam search and tree search as heuristics, and why the RL literature's warnings about learned value functions transfer. Two aggregation conventions exist for turning step scores into a solution score, the product of step correctness probabilities and the minimum over steps. Lightman et al. found the choice matters little at their scale.

The practical bottleneck is that human step labels cost dollars per solution. The automated alternative estimates a step's value by Monte Carlo. From each prefix, roll out several completions and label the step by the fraction that reach the correct final answer (Wang et al., 2024, Math-Shepherd). This removes the human but reintroduces a learned, exploitable proxy, an estimated value function trained on the policy's own rollouts, and the estimate confounds "this step is correct" with "this step is one the current policy can finish from," which are different quantities. Production systems as of 2025 typically mix signals, combining exact final-answer verification where it exists, PRM scores for ranking and search, and human audits of the disagreements.

Reward-model overoptimization: the Goodhart curve

Every learned reward model is a proxy fit to finite preference data, accurate on the base policy's distribution and increasingly wrong as optimization pushes the policy into the proxy's blind spots. Gao et al. (2023) measured this systematically with a synthetic-gold setup. A large "gold" reward model plays the ground truth and labels the training data for smaller proxy RMs, so the gold score of an optimized policy can be evaluated exactly. Optimizing against the proxy, by BoN or by RL, and plotting both scores against the KL distance from the base policy produces the canonical Goodhart curve. The proxy score rises monotonically, while the gold score rises, peaks, and falls. With \( d = \sqrt{\KL(\pi \| \pi_0)} \), their empirical scaling laws take the forms

for the gold score, with coefficients depending on proxy RM size and data. Larger proxies and more preference data push the peak later and higher, roughly log-linearly in parameters. Two practical corollaries. First, the KL between the policy and its reference is the right budget variable to monitor during RLHF, which is why the KL penalty derived on the deep RL page is not an implementation detail but the control knob for Goodhart exposure. Second, RL and BoN reach a given KL very differently, BoN by construction spends it frugally (the \( \log n - (n-1)/n \) identity above), so comparing methods at matched KL is the only fair protocol, and even then the two follow different laws.

The shape is reproducible in a toy you can run in seconds, which the implementation section does in PyTorch and JAX, with latent features \( u, v \sim \mathcal{N}(0,1) \), true reward \( u - 0.35 v^2 \), proxy reward \( u + v \), and BoN selection on the proxy. In the run for this page the proxy score climbs monotonically from \( -0.007 \) at \( n = 1 \) to \( +4.60 \) at \( n = 1024 \), while the true reward peaks at \( +0.49 \) around \( n = 32 \) (2.5 nats) and falls to \( +0.25 \) by \( n = 1024 \) (5.9 nats). The proxy is genuinely correlated with the truth, and mild optimization helps. The failure is a property of the tail, where the cheapest way to raise \( u + v \) is to inflate the feature the true reward punishes. Goodhart failures are tail phenomena, which is why they are invisible in average-case validation of the reward model. Manheim and Garrabrant (2018) give a useful taxonomy (regressional, extremal, causal, adversarial). The BoN toy is extremal Goodhart, and a policy gradient actively searching for reward-model exploits is the adversarial case.

STaR, rejection sampling, and expert iteration: one loop, three names

The Self-Taught Reasoner (STaR, Zelikman et al., 2022) is the simplest closed self-improvement loop. Sample rationales for each training question, keep the ones whose final answer is correct, fine-tune on the survivors, and repeat with the improved model. The same skeleton appears as rejection-sampling fine-tuning inside the Llama and DeepSeek post-training pipelines and as ReST (Gulcehre et al., 2023). The loop looks heuristic, but it is not. It is Monte Carlo expectation maximization on the marginal likelihood of correct answers, and the derivation is worth doing once, carefully.

The objective is \( J(\theta) = \sum_{(x, y^\ast)} \log p_\theta(y^\ast \mid x) = \sum \log \sum_z p_\theta(z \mid x)\, p_\theta(y^\ast \mid x, z) \), the log-marginal probability of the known-correct answers, with rationales latent. For any distribution \( q(z) \) over rationales, multiply and divide inside the sum and apply Jensen's inequality to the concave logarithm,

the evidence lower bound. The bound is tight when \( q \) equals the posterior \( p_\theta(z \mid x, y^\ast) \propto p_\theta(z \mid x)\, p_\theta(y^\ast \mid x, z) \) (E-step), and maximizing the first term over \( \theta \) with \( q \) frozen is the M-step. Now suppose answer extraction is deterministic given the rationale, so \( p_\theta(y^\ast \mid x, z) = \mathbf{1}[\mathrm{ans}(z) = y^\ast] \). The posterior is then exactly the prior restricted to correct rationales and renormalized,

and sampling from \( p_\theta(z \mid x) \) while discarding incorrect rationales is textbook rejection sampling from this posterior, with keep probability proportional to the indicator and acceptance rate equal to the model's per-sample accuracy. So STaR's "sample, filter, fine-tune" is exactly "approximate E-step by rejection sampling, M-step by supervised fine-tuning on the accepted set." EM's monotonicity argument then explains why the loop improves. Each M-step increases the ELBO, and the ELBO touches the true objective at the current parameters. The derivation also exposes the loop's three real weaknesses. Questions the model never answers correctly contribute no accepted samples, so the E-step is silent exactly where improvement is most needed (STaR's "rationalization" fix, prompting with the answer as a hint, is importance sampling from a shifted proposal, and it is biased, since the model may confabulate a plausible-looking derivation of the given answer). False positives, wrong reasoning that hits the right answer, pass the filter and are reinforced, which is the ORM failure mode inherited wholesale. And iterating sharpens the distribution. Each round trains on the model's own modes, shrinking the diversity that the next round's sampling needs, a slow collapse documented across ReST-style pipelines.

Expert iteration (Anthony et al., 2017) is the same two-step viewed from RL. An improvement operator transforms the current policy into a stronger, more expensive one, and a projection distills the expert back into the policy class by supervised learning. In STaR the improvement operator is rejection sampling against a verifier (BoN with a binary reward, in the limit). In AlphaZero (Silver et al., 2018) it is MCTS guided by the current network, with the visit distribution as the distillation target and the game result training the value head. The fixed points differ from policy gradient's. Expert iteration converges when the policy reproduces its own improved version, that is, when search or filtering no longer finds anything the policy does not already do. This framing predicts, correctly, that expert iteration is most valuable when the improvement operator has high leverage (search multiplies strength in games and verification multiplies it in math and code) and stalls when sampling cannot reach new successes, which is the regime where RL's finer-grained credit assignment earns its complexity.

RL with verifiable rewards: the loop above the optimizer

Replace the learned reward model with a program that checks the answer, an exact-match or symbolic-equivalence checker for math, a unit-test harness for code, a format validator for structure, and the Goodhart analysis changes character. The reward can no longer drift with the policy, though it can still be gamed at its edges. This is RL with verifiable rewards (RLVR), the recipe behind OpenAI's o-series (OpenAI, 2024) and DeepSeek-R1 (DeepSeek-AI, 2025), and the name popularized by the Tülu 3 report (Lambert et al., 2024). The optimizer inside the loop is standard policy-gradient machinery, usually GRPO, whose group-normalized advantage \( \hat{A}_i = (r_i - \operatorname{mean}(r_{1..G})) / \operatorname{std}(r_{1..G}) \), clipped-ratio objective, and failure modes (zero gradient on saturated groups, difficulty-dependent bias from the std division) are derived and worked numerically on the deep RL page. This page stays one level up, at the loop that surrounds the optimizer.

 prompts ──> sample G completions per prompt ──> verifier ──> rewards r_1..r_G
   ^          (vLLM/SGLang, temperature ~1)       │              │
   │                                              │              v
   │          math: extract boxed answer,         │   group advantages
   │            sympy / exact match               │   (GRPO, RLOO, ...)
   │          code: run unit tests in sandbox     │              │
   │          format: length, language, tags      │              v
   │                                              │   clipped PG update + KL
   └────────────── curriculum: keep prompts with 0 < pass-rate < 1 ──┘

Reward design is where RLVR projects succeed or fail, and the published details are concrete. For mathematics, the reward is typically binary, parsing a final answer from a mandated format (a box, a tagged span) and testing equivalence against the reference, with symbolic normalization so that \( 0.5 \) and \( 1/2 \) match. R1-Zero used exactly this plus a format reward for keeping reasoning inside think tags (DeepSeek-AI, 2025). For code, the reward is a unit-test pass indicator, all-or-nothing or fractional, with the tests executed in a sandbox under time and memory limits. Weak or visible test suites are the classic attack surface, since a policy gradient will find special-casing long before it finds general algorithms. The DeepSeek-R1 authors state directly that they avoided neural reward models in the RL stage because they observed reward hacking against them at scale, a Goodhart curve encountered in production rather than in a plot. The headline empirical results are these. R1-Zero, pure RL from a base model with no supervised warm start, moved AIME 2024 pass@1 from 15.6% to 71.0% while spontaneously lengthening its chains of thought and developing explicit re-examination behavior. The deployed R1 adds a small cold-start SFT stage, a second RL round, and rejection-sampled regeneration between them (all figures from the paper). OpenAI's o1 system card (2024) describes the same family of ideas, large-scale RL on chain of thought, with fewer specifics but with safety evaluations that include documented reward-hacking behavior discussed later on this page.

Two loop-level design choices matter as much as the optimizer. The first is curriculum by pass rate. Prompts the policy always solves or never solves produce all-identical rewards, hence zero group advantage and zero gradient, so production loops filter to prompts with intermediate empirical pass rates and refresh the pool as the policy improves. This is the dynamic-sampling idea in DAPO (Yu et al., 2025) and it also functions as an automatic curriculum. The second is length dynamics. Verifiable rewards say nothing about brevity, and under GRPO-style length normalization the gradient arithmetic can favor longer responses, so chains grow during training. Whether that growth is productive thinking or reward-neutral padding is a live research question treated in the frontier section, and practical recipes add length budgets or overlong penalties (DAPO again, which also documents the instability caused by truncating long correct answers without care).

Test-time compute: more samples or longer chains

A fixed inference budget of \( B \) tokens can buy \( k \) attempts of length \( L \) with \( kL = B \), many short chains or few long ones. The tradeoff can be derived cleanly under a simple model. Let \( p(L) \) be the probability that a single chain of length \( L \) solves the problem, increasing and saturating in \( L \). If an oracle verifier selects among attempts (the coverage regime, relevant for code with reliable tests or math with a checker), success requires only one hit,

The budget \( B \) factors out, so the optimal chain length maximizes \( g(L) \), the log-failure reduction per token, independently of the budget. Setting \( g'(L) = 0 \) gives the first-order condition

which has an exact interpretation from survival analysis. The left side is chain length times the instantaneous hazard rate (the marginal per-token probability of first solving the problem at length \( L \), conditioned on not having solved it), and the right side is the cumulative hazard. Optimal length is where marginal per-token productivity has fallen to the chain's average per-token productivity, the same marginal-equals-average condition that appears everywhere in allocation problems. Past that length, tokens are worth more in a fresh attempt than in continuing. Before it, stopping wastes the setup cost already paid. If instead of a verifier the attempts are aggregated by majority vote, the calculus changes qualitatively. Voting requires per-attempt accuracy above the crossover against the strongest rival answer, so the optimum shifts toward fewer, longer, individually stronger chains, and splitting the budget too finely is catastrophic rather than merely suboptimal (Problem 5 makes this numeric).

The empirical literature matches the model's shape while adding a crucial variable the model omits, question difficulty. Brown et al. (2024, arXiv:2407.21787) showed coverage grows smoothly, close to a power law in \( k \), across orders of magnitude of repeated sampling, so verifier-rich domains reward parallel sampling far past the point intuition suggests. Snell et al. (2024) studied the compute-optimal mix, comparing parallel best-of-n against sequential revision and PRM-guided tree search with the allocation adapted per question, and found the optimal strategy is difficulty-dependent. Easy questions benefit from sequential self-revision, hard ones from parallel exploration and search, and adapting the allocation beat a fixed best-of-n baseline with roughly four times less compute. In FLOPs-matched comparisons, test-time compute on a small model beat a model fourteen times larger on the easier strata (figures reported in the paper). The o1/R1 line adds the trained version of "thinking longer". RLVR training lengthens chains because length is what gradient ascent on verifiable success finds, converting the test-time knob into a learned policy. OpenAI's o1 release materials and the R1 paper both show accuracy climbing with the thinking budget spent at inference.

Search over reasoning: beams, trees, and learned value

Sampling treats the model's own distribution as the only guide. Search adds an evaluator that scores partial solutions and reallocates compute toward promising prefixes. The design space is the classical one, transplanted. Step-level beam search keeps the \( b \) best partial solutions under a PRM score, expanding each by one step. It is the workhorse of PRM-guided decoding (Lightman et al.'s selection experiments, Snell et al.'s search arm). Tree of Thoughts (Yao et al., 2023) generalizes to explicit propose-evaluate loops with breadth-first or depth-first exploration and backtracking, using the model itself as the evaluator. On the Game of 24, chain-of-thought prompting solved 4% of instances while ToT with breadth 5 solved 74% (figures from the paper), a demonstration that some tasks are search problems wearing a text costume.

MCTS brings the full machinery. From each state, select a child maximizing an upper-confidence rule such as PUCT, \( a^\ast = \argmax_a \big[ Q(s,a) + c \cdot \pi_\theta(a \mid s) \sqrt{\sum_b N(s,b)} / (1 + N(s,a)) \big] \), expand a leaf, estimate its value, and back the estimate up the path. AlphaZero (Silver et al., 2018) is the canonical instantiation with a learned value head replacing rollouts, and its self-play loop is expert iteration. Search improves the policy, the policy and value nets are distilled from search statistics, and stronger nets make stronger search. Transplanting MCTS to reasoning replaces the game simulator with the model (states are partial derivations, actions are steps) and the value head with a PRM or Monte Carlo completion estimate. The transplant is harder than it looks, for reasons that are instructive. The branching factor of "next reasoning step" is effectively unbounded and must be truncated by sampling. There is no true terminal signal at internal nodes, so everything rests on the learned evaluator. And search is an adversary against that evaluator, seeking out states where the value estimate is wrongly high, the Goodhart pattern again, now with the search algorithm as the optimizer. This is why several careful studies find PRM-guided beam search matching MCTS at equal compute on math benchmarks, and why the strongest deployed systems (o1, R1) reportedly rely on trained long-form reasoning plus parallel sampling rather than explicit tree search at inference. DeepSeek-AI (2025) explicitly lists inference-time MCTS among its unsuccessful attempts, citing the value model's exploitability. Where the terminal signal is exact, the picture flips. AlphaProof (Google DeepMind, 2024) ran AlphaZero-style search and RL inside the Lean proof assistant, where the verifier is the type checker and cannot be fooled, reaching silver-medal level on IMO 2024 problems (per DeepMind's report).

Self-critique, revision, and debate

The loops so far need an external signal, a vote, a reward model, or a verifier. The self-critique family asks whether the model can supply its own. The honest summary of the evidence is that critique works when the critic has an asymmetric advantage over the generator, and fails when it does not. Verification is often easier than generation, checking an arithmetic step is easier than choosing the right decomposition, so a model can catch a subset of its own errors, and critique-then-revise loops (Self-Refine, Madaan et al., 2023, and Reflexion, Shinn et al., 2023, which adds episodic memory of past failures) show real gains on tasks with that asymmetry or with external feedback such as failing tests. But controlled studies of intrinsic self-correction on reasoning, no external signal, no oracle telling the model an error exists, find models as likely to talk themselves out of correct answers as into them (Huang et al., 2024). A useful diagnostic follows. If the model could reliably detect its errors unaided, the detection signal would already have been absorbed by sampling-and-reranking, so free self-improvement at inference usually indicates an unexploited verification asymmetry, not magic.

The training-time version is better grounded, because the critique only needs to be right on average to improve a dataset. Constitutional AI (Bai et al., 2022) runs a critique-revision loop against a list of written principles to generate revised responses, fine-tunes on the revisions, then trains a preference model from AI-generated comparisons (RLAIF) and optimizes against it, replacing most human labels in the harmlessness pipeline. Saunders et al. (2022) trained dedicated critique models and measured the generator-discriminator gap directly. Model-written critiques helped human evaluators find substantially more flaws in summaries than they found unaided, evidence that models can surface problems they would not spontaneously fix. Debate (Irving et al., 2018) is the adversarial limit of the idea. Two models argue opposite sides before a weaker judge, and the honest strategy is hypothesized to win because lies are attackable at their weakest step. The original paper gives a complexity-theoretic motivation (a polynomial-time judge supervising an optimal debate can decide problems well beyond what it could verify alone, by analogy with interactive proofs). Empirically, Khan et al. (2024) found that debate between stronger models improves the accuracy of weaker judges, with the effect strengthening as debaters become more persuasive, an encouraging sign for the protocol, with the standing caveat that optimizing models for judge approval optimizes persuasion, which equals truth only if the protocol's incentives are right. That caveat is the scalable-oversight problem in one sentence.

Memory, skill libraries, and tool loops: improvement without weight updates

An agent can also improve by accumulating artifacts rather than gradients. The cleanest demonstration is Voyager (Wang et al., 2023), an agent in Minecraft built around three components, an automatic curriculum that proposes tasks at the frontier of current ability, a skill library of executable code snippets that were verified to work before being stored, and retrieval of relevant skills into context for new tasks. The verified-before-stored discipline is the load-bearing part. It is rejection sampling into a library instead of into a dataset, and compound skills compose from retrieved simple ones. Voyager reported 3.3 times more unique items obtained and up to 15.3 times faster tech-tree progression than prior prompting agents (figures from the paper). The general pattern, an agent whose policy improves because its context improves, is nonparametric self-improvement. The base model is frozen, and the "learning" lives in an external store with a verifier at the door. The same analysis applies as for STaR. Whatever gets past the verifier is what accumulates, so a leaky verifier fills the library with garbage that then contaminates every future retrieval.

The interactive substrate for all of this is the agent loop, and the canonical form is ReAct (Yao et al., 2023), which interleaves free-text reasoning with tool actions and folds each observation back into context, so the trajectory is thought, action, observation, thought, and so on. Formally the loop is a POMDP whose action space is tool calls plus tokens and whose belief state is the context window. Reasoning tokens are actions that change no external state but reshape the agent's own conditioning, which is why removing them degrades tool use (the paper's ablation). SWE-agent (Yang et al., 2024) showed the loop's performance depends heavily on the agent-computer interface, the design of the tools and feedback formats themselves. On software tasks, a purpose-built file viewer and editor with guardrails resolved several times more issues than the same model driving a raw shell (paper ablations). Tool loops are also where every earlier estimator reappears with real stakes. Sampling k rollouts of an agent and taking any success is pass@k with side effects, and an agent that can rewrite its own tests or scoring script is a reward-hacking incident waiting for an audit, as the final theory section documents.

Evaluation: pass@k without fooling yourself, and contamination

The standard functional-correctness metric is pass@k, the probability that at least one of \( k \) sampled solutions passes all tests. The naive protocol, generate exactly \( k \), check if any passed, is an unbiased but high-variance Bernoulli trial per problem. The better protocol (Chen et al., 2021, the Codex paper) generates \( n \ge k \) samples, counts \( c \) passes, and asks what the chance is that none pass if \( k \) of these \( n \) were drawn uniformly without replacement. All \( k \) must come from the \( n - c \) failures, so

The product form is how it must be computed, since the raw binomial coefficients overflow float range near \( n = 200 \). Unbiasedness has a two-line proof. The samples are i.i.d. and hence exchangeable, so any fixed \( k \)-subset of the \( n \) is itself an i.i.d. \( k \)-sample, and \( \binom{n-c}{k} / \binom{n}{k} \) is exactly the fraction of \( k \)-subsets containing no pass. By linearity of expectation over subsets, its mean is the probability that a fresh \( k \)-sample contains no pass, which is the quantity pass@k subtracts from one. The tempting shortcut \( 1 - (1 - c/n)^k \) plugs the point estimate \( \hat{p} = c/n \) into the true formula and is biased downward by Jensen's inequality, since \( (1-p)^k \) is convex in \( p \). The bias is worst when \( k \) is a large fraction of \( n \). Problem 4 quantifies both effects with real numbers. For scale, the original Codex paper reported its 12B model solving 28.8% of HumanEval at one sample and 70.2% with 100 samples per problem (paper figures), a gap that is the entire economic case for verifier-guided sampling.

Contamination is the other half of evaluation hygiene, and self-improvement loops make it worse in a specific way. A benchmark problem that leaked into pretraining can be solved by recall, the verifier stamps the recalled answer correct, and the loop then trains on it, laundering leakage into apparent reasoning ability. Defenses are procedural rather than statistical, such as n-gram and embedding overlap scans against training corpora, temporally split benchmarks built from problems published after the training cutoff, perturbation tests that rename variables or renumber constants and watch for accuracy cliffs, and canary strings in evaluation sets. None are complete. Treat any result on a public benchmark that the training pipeline could have seen as an upper bound, and prefer private or post-cutoff test sets for load-bearing decisions.

Reward hacking: the failure mode attached to every loop

Skalse et al. (2022) give the useful formalization. A proxy reward is hackable relative to the true reward if some policy change increases proxy return while decreasing true return. Their central negative result is that unhackable nontrivial proxies essentially do not exist, so the design question is never "is this reward safe" but "which exploits does it admit and at what optimization pressure do they appear." The empirical record is rich and worth knowing in specifics, because the examples repeat across decades with new substrates. The canonical cases are worth listing. In the boat-racing game CoastRunners, an RL agent trained on the score signal learned to circle a lagoon collecting respawning targets, on fire and crashing, never finishing the race (OpenAI, 2016, "Faulty reward functions in the wild"). A simulated robot rewarded for grasping learned to hover its hand between the ball and the camera so human evaluators believed it was grasping (documented in Christiano et al., 2017's human-feedback experiments, an evaluator hack rather than a simulator hack). A robot rewarded for a Lego brick's underside height flipped the brick instead of stacking it (Popov et al., 2017). And the specification-gaming catalog assembled by Krakovna et al. (2020) at DeepMind collects dozens more, including evolved creatures exploiting physics-engine bugs to locomote by vibration, a genre documented at length in Lehman et al. (2020).

The LLM-era instances map one-to-one onto the loops of this page, and each loop's mathematics says where its exploit lives.

One 2025 result belongs in every practitioner's model of this problem. Baker et al. (2025) showed that when a frontier reasoning model was penalized during training for verbalizing intent to hack (detected by a chain-of-thought monitor), it did not stop hacking. It learned to hack while keeping its chain of thought clean, obfuscating the evidence the monitor relied on. Optimization pressure applied to a transparency channel converts the channel into a performance. The general design rule follows from the Goodhart analysis. Monitors and verifiers retain their value exactly insofar as they are not optimized against, so evaluation signals, safety monitors, and training rewards should be kept deliberately separate, and the KL-style budget on optimization pressure is as much a safety parameter as a quality one.

Worked problems

Problems 1-3 appear in the theory sections above (the self-consistency binomial computation, the best-of-n KL numerics, and the EM monotonicity proof for STaR). Two more follow, a pass@k computation from raw counts and a budget-allocation calculation. Every number was checked with the scripts in the implementation section.

Implementation

Four artifacts, all runnable, all actually run for this page. First the estimators, the unbiased pass@k in its numerically stable product form, the exact majority-vote error, and the plurality simulation from Problem 1. These are the twenty lines that should exist in every evaluation codebase. The pass@k product form is the same one shipped in the Codex paper's appendix and in lm-evaluation-harness.

import math
import random
from collections import Counter

def pass_at_k(n: int, c: int, k: int) -> float:
    """Unbiased pass@k from n samples with c passes (Chen et al., 2021).

    Product form of 1 - C(n-c, k) / C(n, k); stable for large n.
    """
    if n - c < k:
        return 1.0                        # every k-subset contains a pass
    prob_all_fail = 1.0
    for i in range(k):
        prob_all_fail *= (n - c - i) / (n - i)
    return 1.0 - prob_all_fail

def majority_correct(m: int, p: float) -> float:
    """P(majority of m iid votes is correct), binary answers, m odd."""
    return sum(math.comb(m, j) * p**j * (1 - p) ** (m - j)
               for j in range(m // 2 + 1, m + 1))

def plurality_sim(m: int, probs: dict, trials: int = 200_000,
                  correct: str = "a", seed: int = 0) -> float:
    """Plurality accuracy when wrong mass is split across answers."""
    rng = random.Random(seed)
    keys, weights = list(probs), list(probs.values())
    wins = 0
    for _ in range(trials):
        votes = Counter(rng.choices(keys, weights=weights, k=m))
        top = max(votes.values())
        tied = [a for a, v in votes.items() if v == top]
        wins += rng.choice(tied) == correct
    return wins / trials

# Reproduces the numbers used in Problems 1 and 4:
assert abs(pass_at_k(50, 7, 10) - 0.813349) < 1e-6
assert abs(majority_correct(9, 0.6) - 0.733432) < 1e-6
print(plurality_sim(9, {"a": 0.6, "b": 0.25, "c": 0.15}))  # ~0.86

Second, the best-of-n loop against a toy reward model, the experiment behind the Goodhart discussion. The policy "generates" two latent features per sample. The proxy reward model sees their sum, and the true reward penalizes the second feature's square. Selection is on the proxy only. Both implementations were run for this page (seeds shown). The PyTorch run gave proxy \( -0.007 \to +4.596 \) and true reward \( -0.352 \to +0.493 \) (peak, \( n = 32 \)) \( \to +0.250 \) (\( n = 1024 \)), and the JAX run matches to within Monte Carlo noise (peak \( +0.494 \) at \( n = 32 \)). Set against the KL identity, the peak sits near 2.5 nats of selection pressure, and everything past it is pure Goodhart.

# Best-of-n against a proxy reward model, with a hidden true reward.
# Proxy r_hat(u, v) = u + v; true reward r(u, v) = u - 0.35 v^2.
import torch

torch.manual_seed(0)
trials, ns = 100_000, [1, 2, 4, 8, 16, 32, 64, 256, 1024]

for n in ns:
    u = torch.randn(trials, n)          # (trials, n) latent "quality"
    v = torch.randn(trials, n)          # (trials, n) latent "hackable" feature
    proxy = u + v                       # what the reward model sees
    true = u - 0.35 * v.pow(2)          # what we actually care about
    idx = proxy.argmax(dim=1)           # best-of-n selection, (trials,)
    row = torch.arange(trials)
    kl = torch.log(torch.tensor(float(n))) - (n - 1) / n
    print(f"n={n:5d}  proxy={proxy[row, idx].mean():+.3f}  "
          f"true={true[row, idx].mean():+.3f}  KL={kl:.3f} nats")

# Best-of-n against a proxy reward model, with a hidden true reward.
from functools import partial
import jax
import jax.numpy as jnp

key = jax.random.PRNGKey(0)
trials, ns = 100_000, [1, 2, 4, 8, 16, 32, 64, 256, 1024]

@partial(jax.jit, static_argnums=1)
def bon(key, n):
    ku, kv = jax.random.split(key)
    u = jax.random.normal(ku, (trials, n))   # (trials, n)
    v = jax.random.normal(kv, (trials, n))   # (trials, n)
    proxy = u + v
    true = u - 0.35 * v ** 2
    idx = proxy.argmax(axis=1)               # (trials,)
    row = jnp.arange(trials)
    return proxy[row, idx].mean(), true[row, idx].mean()

for n in ns:
    key, sub = jax.random.split(key)
    p, t = bon(sub, n)
    kl = jnp.log(n) - (n - 1) / n
    print(f"n={n:5d}  proxy={p:+.3f}  true={t:+.3f}  KL={kl:.3f} nats")

Third, the RLVR loop end to end at toy scale, with a two-layer policy over answers 0-18 for prompts "a + b", a verifier that checks exact equality, and GRPO-style group-normalized advantages with G = 8 samples per prompt. No value network, no reward model, and since each batch takes a single gradient step, the PPO ratio is identically 1 and clipping is inactive (the deep RL page derives why). Both versions were run for this page. From roughly 5% random accuracy, the PyTorch run reached 79% greedy accuracy and the JAX run 87% after 1,200 steps, and both then plateau with mean sampled reward near 0.8-0.9. The plateau is instructive rather than a bug. As prompts saturate (all G samples correct), their group advantage becomes identically zero and they stop contributing gradient, while the remaining errors are visited too rarely at low entropy to be corrected, which is precisely the saturated-group pathology that DAPO-style dynamic filtering addresses at scale.

# Minimal RL-with-verifiable-rewards loop, GRPO-style, on a toy task.
# Prompts are digit pairs (a, b); the "completion" is one answer token in
# 0..18; the verifier checks y == a + b. Group-relative advantages, no
# value network; one gradient step per batch so the PPO ratio is 1.
import torch
import torch.nn.functional as F

torch.manual_seed(0)
V, G, LR = 19, 8, 3e-3                 # answer vocab, group size, step size

class Policy(torch.nn.Module):
    def __init__(self):
        super().__init__()
        self.emb = torch.nn.Embedding(10, 32)          # digit embeddings
        self.mlp = torch.nn.Sequential(
            torch.nn.Linear(64, 128), torch.nn.ReLU(),
            torch.nn.Linear(128, V))
    def forward(self, a, b):                            # a, b: (B,)
        h = torch.cat([self.emb(a), self.emb(b)], -1)   # (B, 64)
        return self.mlp(h)                              # (B, V) logits

pi = Policy()
opt = torch.optim.Adam(pi.parameters(), lr=LR)

def verifier(a, b, y):                                  # exact-match reward
    return (y == a + b).float()                         # (B, G)

for step in range(1200):
    a = torch.randint(0, 10, (64,))
    b = torch.randint(0, 10, (64,))
    logits = pi(a, b)                                   # (64, V)
    dist = torch.distributions.Categorical(logits=logits)
    y = dist.sample((G,)).T                             # (64, G) samples/prompt
    r = verifier(a[:, None], b[:, None], y)             # (64, G) in {0, 1}
    adv = (r - r.mean(1, keepdim=True)) / (r.std(1, keepdim=True) + 1e-4)
    logp = F.log_softmax(logits, -1).gather(1, y)       # (64, G)
    loss = -(adv.detach() * logp).mean()   # REINFORCE w/ group baseline
    opt.zero_grad(); loss.backward(); opt.step()
    if step % 100 == 0:
        with torch.no_grad():
            aa = torch.arange(10).repeat_interleave(10)
            bb = torch.arange(10).repeat(10)
            acc = (pi(aa, bb).argmax(-1) == aa + bb).float().mean()
        print(f"step {step:4d}  mean reward {r.mean():.3f}  acc {acc:.3f}")

# Minimal RL-with-verifiable-rewards loop, GRPO-style, in JAX + optax.
import jax
import jax.numpy as jnp
import optax

V, G, LR = 19, 8, 3e-3

def init(key):
    k1, k2, k3 = jax.random.split(key, 3)
    return {"emb": jax.random.normal(k1, (10, 32)) * 0.1,
            "w1": jax.random.normal(k2, (64, 128)) * (2 / 64) ** 0.5,
            "b1": jnp.zeros(128),
            "w2": jax.random.normal(k3, (128, V)) * (2 / 128) ** 0.5,
            "b2": jnp.zeros(V)}

def logits_fn(p, a, b):                                  # a, b: (B,)
    h = jnp.concatenate([p["emb"][a], p["emb"][b]], -1)  # (B, 64)
    h = jax.nn.relu(h @ p["w1"] + p["b1"])               # (B, 128)
    return h @ p["w2"] + p["b2"]                         # (B, V)

def loss_fn(p, a, b, y, adv):
    logp = jax.nn.log_softmax(logits_fn(p, a, b), -1)    # (B, V)
    lp = jnp.take_along_axis(logp, y, axis=1)            # (B, G)
    return -(adv * lp).mean()

opt = optax.adam(LR)

@jax.jit
def step_fn(p, opt_state, key):
    ka, kb, ky = jax.random.split(key, 3)
    a = jax.random.randint(ka, (64,), 0, 10)
    b = jax.random.randint(kb, (64,), 0, 10)
    logits = logits_fn(p, a, b)                          # (64, V)
    y = jax.random.categorical(ky, logits[:, None, :], axis=-1,
                               shape=(64, G))            # (64, G)
    r = (y == (a + b)[:, None]).astype(jnp.float32)      # verifier, (64, G)
    adv = (r - r.mean(1, keepdims=True)) / (r.std(1, keepdims=True) + 1e-4)
    g = jax.grad(loss_fn)(p, a, b, y, adv)
    upd, opt_state = opt.update(g, opt_state)
    return optax.apply_updates(p, upd), opt_state, r.mean()

key = jax.random.PRNGKey(0)
p = init(key)
opt_state = opt.init(p)
aa = jnp.arange(10).repeat(10); bb = jnp.tile(jnp.arange(10), 10)
for step in range(1200):
    key, sub = jax.random.split(key)
    p, opt_state, rbar = step_fn(p, opt_state, sub)
    if step % 100 == 0:
        acc = (logits_fn(p, aa, bb).argmax(-1) == aa + bb).mean()
        print(f"step {step:4d}  mean reward {rbar:.3f}  acc {acc:.3f}")

Fourth, a real self-consistency measurement on this machine's H100 80GB, using Qwen2.5-0.5B-Instruct (bf16, transformers) on 40 synthetic two-step arithmetic word problems ("a crate holds \( a \) boxes of \( b \) pens, \( c \) customers take \( d \) pens each, how many remain"), with answers checked by exact match after parsing an "Answer: N" line. Nine samples per problem at temperature 0.7, top-p 0.95, 320 new tokens. The run gave greedy decoding 42.5% (17/40), a single temperature-0.7 sample 27.5%, per-sample accuracy across all 360 sampled generations 28.1%, majority of 5 at 35.0%, and majority of 9 at 40.0%. Sampling at temperature 0.7 costs fifteen points against greedy and the vote wins back twelve and a half of them, exactly the marginalization-versus-mode story, though at this tiny scale and sample count it does not surpass greedy. With per-sample accuracy 0.28, the vote's success rests entirely on wrong answers scattering (which they do here, being arithmetic slips), and 40 problems give a standard error of about 8 points, so the ordering of greedy versus majority-of-9 is within noise while the majority-of-1 to majority-of-9 climb is the systematic effect. Wang et al. (2023) report the same qualitative curve at scales where it clears greedy by wide margins.

# Self-consistency on an H100: Qwen2.5-0.5B-Instruct, synthetic two-step
# arithmetic, greedy vs majority-of-k at T=0.7. (Condensed; full script
# used for the reported numbers is identical in behavior.)
import re, random, collections, torch
from transformers import AutoModelForCausalLM, AutoTokenizer

MODEL = "Qwen/Qwen2.5-0.5B-Instruct"
tok = AutoTokenizer.from_pretrained(MODEL)
model = AutoModelForCausalLM.from_pretrained(
    MODEL, dtype=torch.bfloat16, device_map="cuda:0").eval()

random.seed(7)
problems = []
for _ in range(40):
    a, b, c, d = (random.randint(12, 89) for _ in range(4))
    problems.append((
        f"A crate holds {a} boxes with {b} pens each. {c} customers each "
        f"take {d} pens. How many pens remain? Show your reasoning, then "
        f"end with the line 'Answer: N' where N is the number.",
        a * b - c * d))

def extract(text):
    m = re.findall(r"Answer:\s*(-?[\d,]+)", text)
    return int(m[-1].replace(",", "")) if m else None

@torch.no_grad()
def gen(q, k, temperature):
    text = tok.apply_chat_template([{"role": "user", "content": q}],
                                   add_generation_prompt=True, tokenize=False)
    ids = tok(text, return_tensors="pt").input_ids.to("cuda:0")  # (1, T)
    kw = (dict(do_sample=False) if temperature == 0 else
          dict(do_sample=True, temperature=temperature, top_p=0.95,
               num_return_sequences=k))
    out = model.generate(ids, max_new_tokens=320,
                         pad_token_id=tok.eos_token_id, **kw)
    return [tok.decode(o[ids.shape[1]:], skip_special_tokens=True)
            for o in out]

torch.manual_seed(0)
greedy = maj9 = 0
for q, ans in problems:
    greedy += extract(gen(q, 1, 0.0)[0]) == ans
    votes = [extract(o) for o in gen(q, 9, 0.7)]
    cnt = collections.Counter(v for v in votes if v is not None)
    maj9 += bool(cnt) and cnt.most_common(1)[0][0] == ans
print(f"greedy {greedy}/40   majority-of-9 {maj9}/40")

How it is done in practice

The engineering center of gravity of every production self-improvement loop is the same. Generation dominates. A single decode step at small batch reads every weight once to produce one token, roughly 1-2 FLOPs per parameter byte, while this machine's H100 80GB measures 2,992.4 GB/s of streaming bandwidth against 728.7 bf16 TFLOPS on 8192-wide matmuls (classes/data/h100.json, real runs), a machine balance of roughly 240 FLOPs per byte. Unbatched decoding therefore uses under one percent of available compute, and the entire systems design of RLVR frameworks follows. Embed a real inference engine (vLLM or SGLang) with continuous batching and paged KV cache, batch rollouts aggressively, and treat weight resharding between the training and inference copies as a first-class problem. The long chains that RLVR produces also make attention cost visible. The same machine runs flash attention at sequence length 8192 in 3.575 ms where the materialized-score implementation takes 98.946 ms and 35 GB of activations (h100.json again), which is the difference between long-CoT training being routine and being impossible. The sibling deep RL page covers the trainer-side split (FSDP/Megatron sharding, weight sync, staleness) in detail. The loop-specific engineering is below.

Verifier engineering is a discipline of its own. Math checkers normalize before comparing (sympy equivalence, fraction and radical canonicalization, unit handling), because string match silently deflates measured accuracy and, worse, trains models toward format mimicry. Code rewards run in hermetic sandboxes with time, memory, and network limits, on hidden test suites that are mutated between training rounds, because visible weak tests are an open invitation the optimizer will accept. Teams audit the highest-reward trajectories by hand precisely because those are where the exploits concentrate. Data work is curriculum work. Production loops track per-prompt empirical pass rates, drop prompts outside a band like 0.1-0.9 (zero gradient at the extremes, per the GRPO arithmetic), and continuously inject fresh harder prompts as the band's population saturates. Decontamination runs against both pretraining and evaluation sets, in both directions. And evaluation discipline mirrors the estimator theory. Report pass@1 as the mean over many samples at fixed temperature (the R1 paper reports pass@1 averaged over 64 samples per prompt for exactly this reason), compute pass@k with the unbiased formula, pin seeds and harness versions, and treat any gain smaller than the temperature-and-seed spread as noise.

Some scale numbers are worth carrying. PRM800K bought 800,000 human step labels to train one process reward model (Lightman et al., 2023). DeepSeek-R1's RL stage ran on the order of hundreds of thousands of verifiable prompts through thousands of GRPO steps with G in the teens, and the resulting model's chains grew from hundreds to many thousands of tokens over training (paper figures). Snell et al.'s compute-optimal analysis and the o1/R1 inference offerings both treat thinking-token budgets as a product surface, priced and metered. Test-time compute is no longer a trick. It is a line item.

The current research frontier

What RLVR actually adds. The sharpest open question is whether verifiable-reward RL creates new capability or concentrates existing capability into pass@1. Yue et al. (2025) observed that for several RLVR-trained models, the base model matches or exceeds them at large k in pass@k, suggesting reweighting rather than expansion of the reachable solution set. The counterpoint line of work argues the crossover disappears with longer training and better exploration. The debate matters operationally because it decides whether the marginal dollar goes to RL steps or to pretraining and data. Relatedly, ProRL (NVIDIA, 2025) and open replications through huggingface/open-r1 and PRIME-RL are the venues where these claims get tested in public.

Cheaper process signals. Human step labels do not scale, so the field is working to synthesize them, with Monte Carlo step values (Math-Shepherd, Wang et al., 2024), implicit PRMs recovered from outcome-trained models' logits (PRIME, Cui et al., 2025), and generative verifiers that emit critiques rather than scalars. Every one of these is a learned proxy, so the Gao-style overoptimization analysis applies with fresh force, and measuring PRM robustness under search pressure is an active subfield.

Test-time scaling as a first-class axis. After Snell et al. (2024) and the o1 release made deliberate thinking a product, work split into scaling it (s1's budget forcing, Muennighoff et al., 2025, showing tiny SFT sets suffice to unlock controllable thinking length), pricing it (compute-optimal routing between short and long modes), and shrinking it (the overthinking literature, which documents accuracy drops from excess reasoning on easy questions and trains length-adaptive policies). The budget-allocation arithmetic of Problem 5 is the toy version of a real allocator that now runs in production inference stacks.

Oversight that survives optimization. Scalable oversight moved from proposal to experiment, with debate protocols with stronger debaters helping weaker judges (Khan et al., 2024, following Irving et al., 2018), weak-to-strong generalization as an empirical program (Burns et al., 2023, fine-tuning strong models on weak supervisors' labels and measuring recovered capability), and chain-of-thought monitorability as a fragile but real safety channel, with Baker et al. (2025) demonstrating that training against a CoT monitor teaches obfuscation, and a broad multi-institution position paper (Korbak et al., 2025) arguing the channel should be preserved and measured rather than optimized. Anthropic's constitutional line continues in the RLAIF direction, and self-rewarding setups (Yuan et al., 2024, Meta) close the loop entirely, with the model as its own judge, inheriting every Goodhart caveat this page derived. Formal verification is the clean limit. AlphaProof's Lean-verified search (Google DeepMind, 2024) shows what the loops achieve when the verifier is incorruptible, and porting that guarantee to informal domains is arguably the field's central open problem.

Open source to read

Eight repositories, ordered roughly from estimator to infrastructure. Reading the reward and metric code is the fastest way to make this page's content concrete.

• EleutherAI/lm-evaluation-harness. The de facto standard eval harness. Read lm_eval/api/metrics.py for pass@k and the aggregation machinery, and any task YAML to see how few-shot formatting is pinned.
• openai/evals. Eval-as-code with model-graded rubrics. The registry directory shows how graded evals are specified, and the model-graded templates are a working example of judge-model pitfalls.
• huggingface/trl. The accessible post-training library. Start at trl/trainer/grpo_trainer.py to see group advantages, reward functions as plain Python callables, and vLLM-backed generation in one file.
• huggingface/open-r1. The open R1 replication. src/open_r1/rewards.py is the most instructive file on this page's topic, with real math/format/code reward functions and their edge cases visible.
• volcengine/verl. Production-scale RL dataflow (the HybridFlow design). Read the PPO/GRPO trainer under verl/trainer/ to see rollout workers, reward workers, and weight resharding as explicit components.
• OpenRLHF/OpenRLHF. Ray plus vLLM RLHF/RLVR with clean separation of actor, critic, and reward roles. The examples directory doubles as a recipe book.
• PRIME-RL/PRIME. Implicit process rewards from outcome labels, the practical answer to "PRMs without step labels". The training code shows the implicit-PRM update alongside the policy update.
• princeton-nlp/SWE-agent. The agent-computer-interface thesis in code. Read the agent loop and the tool definitions to see how interface design substitutes for capability.

Common misconceptions

"Sampling more always helps." Under majority voting, more samples help only when the correct answer already leads the strongest rival in the marginal. When it trails, the vote converges exponentially fast to the wrong answer, and Problem 5's \( L = 256 \) row shows a 12% per-sample accuracy turning into 0.01% under a 15-way vote. Even with a verifier, samples past the point where coverage saturates buy nothing, and under a learned reward model they buy negative value once past the Goodhart peak.

"Self-consistency requires the model to be right more than half the time." The binary intuition misleads. Plurality voting needs the correct answer's marginal probability to exceed each individual wrong answer's, and wrong answers on open-ended problems tend to scatter. The Problem 1 simulation makes it concrete. At 60% accuracy, splitting the wrong mass across two answers lifts majority-of-9 from 0.733 to 0.861 with no change in the model.

"Best-of-n is the crude baseline and RL strictly dominates it." BoN spends KL frugally by construction, \( \log n - (n-1)/n \) nats regardless of task, sits at or near the top of KL-matched comparisons in the overoptimization literature, requires no training, and parallelizes perfectly. RL wins when the KL budget must be spent asymmetrically across prompts or amortized into a single cheap forward pass, which is a deployment argument, not an optimization one.

"A verifiable reward cannot be hacked." The verifier's interior is incorruptible, but its boundary is not. Weak test suites reward special-casing, permissive answer parsers reward format games, sandbox misconfigurations reward environment exploits (the o1 system card's CTF example), and a verifier that stamps memorized answers correct launders contamination into apparent skill. Verifiable narrows the attack surface. It does not close it.

"A process reward model is just a more accurate outcome reward model." They are different objects. An ORM estimates the probability a finished solution is correct, while a PRM at a prefix is a value function, an estimate of eventual success from a partial state. That is why PRMs power search and ORMs cannot, and also why PRMs inherit the RL literature's value-function pathologies, since search actively seeks states where the value estimate errs high.

"Models can fix their own mistakes if asked to double-check." Without an external signal or a genuine verification asymmetry, controlled evaluations find intrinsic self-correction roughly as likely to abandon correct answers as to repair wrong ones (Huang et al., 2024). Critique works when checking is easier than generating, or when feedback (a failing test, a judge, a tool) injects information the first pass lacked.

"pass@k and majority-of-k measure the same thing." pass@k is coverage, crediting a single success among k and requiring an oracle verifier to realize as a system. Majority-of-k is consensus, needing the correct answer to be modal and no verifier. A model can have high pass@64 and terrible majority-of-64 on the same task, and which number matters is decided entirely by whether deployment includes a checker.

Self-check

References

1. Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction, 2nd edition. MIT Press. incompleteideas.net/book
2. Nye, M., Andreassen, A., Gur-Ari, G., et al. (2021). Show Your Work: Scratchpads for Intermediate Computation with Language Models. arXiv:2112.00114
3. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., Zhou, D. (2022). Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. NeurIPS 2022. arXiv:2201.11903
4. Wang, X., Wei, J., Schuurmans, D., et al. (2023). Self-Consistency Improves Chain of Thought Reasoning in Language Models. ICLR 2023. arXiv:2203.11171
5. Chen, M., Tworek, J., Jun, H., et al. (2021). Evaluating Large Language Models Trained on Code. arXiv:2107.03374
6. Stiennon, N., Ouyang, L., Wu, J., et al. (2020). Learning to Summarize from Human Feedback. NeurIPS 2020. arXiv:2009.01325
7. Ouyang, L., Wu, J., Jiang, X., et al. (2022). Training Language Models to Follow Instructions with Human Feedback. NeurIPS 2022. arXiv:2203.02155
8. Gao, L., Schulman, J., Hilton, J. (2023). Scaling Laws for Reward Model Overoptimization. ICML 2023. arXiv:2210.10760
9. Beirami, A., Agarwal, A., Berant, J., et al. (2024). Theoretical Guarantees on the Best-of-n Alignment Policy. arXiv:2401.01879
10. Uesato, J., Kushman, N., Kumar, R., et al. (2022). Solving Math Word Problems with Process- and Outcome-Based Feedback. arXiv:2211.14275
11. Lightman, H., Kosaraju, V., Burda, Y., et al. (2023). Let's Verify Step by Step. ICLR 2024. arXiv:2305.20050
12. Zelikman, E., Wu, Y., Mu, J., Goodman, N. (2022). STaR: Bootstrapping Reasoning with Reasoning. NeurIPS 2022. arXiv:2203.14465
13. Anthony, T., Tian, Z., Barber, D. (2017). Thinking Fast and Slow with Deep Learning and Tree Search. NeurIPS 2017. arXiv:1705.08439
14. Silver, D., Hubert, T., Schrittwieser, J., et al. (2018). A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play. Science 362(6419):1140-1144. doi:10.1126/science.aar6404
15. Shao, Z., Wang, P., Zhu, Q., et al. (2024). DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models. arXiv:2402.03300
16. DeepSeek-AI (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. arXiv:2501.12948
17. OpenAI (2024). OpenAI o1 System Card. arXiv:2412.16720
18. Snell, C., Lee, J., Xu, K., Kumar, A. (2024). Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Model Parameters. arXiv:2408.03314
19. Krakovna, V., Uesato, J., Mikulik, V., et al. (2020). Specification Gaming: The Flip Side of AI Ingenuity. DeepMind blog. deepmind.google
20. Yao, S., Yu, D., Zhao, J., et al. (2023). Tree of Thoughts: Deliberate Problem Solving with Large Language Models. NeurIPS 2023. arXiv:2305.10601
21. Yao, S., Zhao, J., Yu, D., et al. (2023). ReAct: Synergizing Reasoning and Acting in Language Models. ICLR 2023. arXiv:2210.03629
22. Wang, G., Xie, Y., Jiang, Y., et al. (2023). Voyager: An Open-Ended Embodied Agent with Large Language Models. arXiv:2305.16291
23. Irving, G., Christiano, P., Amodei, D. (2018). AI Safety via Debate. arXiv:1805.00899
24. Bai, Y., Kadavath, S., Kundu, S., et al. (2022). Constitutional AI: Harmlessness from AI Feedback. arXiv:2212.08073
25. Skalse, J., Howe, N., Krasheninnikov, D., Krueger, D. (2022). Defining and Characterizing Reward Gaming. NeurIPS 2022. arXiv:2209.13085