Reasoning Verification: Process Reward Models, Guided Search

Language models can reason step by step, but how do we know whether each step is correct? A model might produce a fluent, confident chain of thought that contains a subtle logical error, an incorrect intermediate calculation, or an unjustified leap. The final answer may look plausible while resting on a faulty foundation. This is the problem that reasoning verification addresses: checking whether generated reasoning is valid.

Verification is a fundamentally different problem from generation. When generating an answer, a model must search a vast space of possible completions. When verifying, it can focus on a specific claim or step and ask a more targeted question: is this step correct given what came before? This asymmetry matters because verification is often easier than generation. If you cannot solve a math problem from scratch, you can still check whether someone else's proposed solution is correct. This principle is central to why verification-based approaches have become a key technique for improving LLM reasoning.

Consider the difference between writing a proof and checking a proof. A professional mathematician might spend weeks constructing an original proof of a new theorem. But even a student who could not have discovered the proof independently can often identify a logical gap or arithmetic mistake when reading it carefully. The generative task is hard; the verification task is harder than no task at all but substantially easier than the original construction. Language models exhibit the same asymmetry, and this is what verification-based approaches exploit.

The practical stakes are high. A language model used to assist with financial analysis, drug dosage calculations, legal document review, or engineering design may produce chains of reasoning that appear sound but contain subtle errors. Without a mechanism to check reasoning quality at the step level, there is no reliable way to catch these failures before they cause harm. The fluency and confidence of language model outputs makes this problem worse: a model that says "therefore, the answer is 42" with high confidence gives little indication of whether the steps leading to that conclusion are sound.

This chapter covers four interconnected ideas. Step verification examines how to check individual reasoning steps rather than just final answers. Process reward models formalize this by training models to score each step of a chain of thought. Verification-guided search uses those scores to steer search toward correct reasoning paths. Self-correction explores whether models can verify and revise their own outputs. Together, these techniques form a toolkit for building more reliable reasoning systems.

To understand why verification is valuable, consider the failure modes of standard language model reasoning. A model trained to maximize the likelihood of correct final answers learns to produce reasoning that looks like correct reasoning. But looking correct and being correct are not the same thing.

The most common failure mode is a confident error in a chain of thought: the model performs several correct steps, makes a mistake in one intermediate computation, and then continues reasoning as if the mistake had not occurred. The final answer is wrong, but the reasoning surrounding the error looks plausible. Without step-level checking, there is no way to catch this. The model's language modeling objective provides no incentive to be correct at each step, only to produce text that looks similar to correct reasoning in the training data.

A second failure mode is shortcut reasoning. A model may learn statistical patterns between problem types and answers without learning the actual reasoning process. It arrives at the right answer via an invalid path. This matters enormously in safety-critical settings where we care whether the answer is correct and whether the reasoning justifies trusting it. A correct answer produced by spurious reasoning tells us nothing about what the model will do when it encounters a slightly different problem.

A third failure mode appears specifically with long chains of thought: error propagation. Once the model makes an incorrect assumption or calculation early in a chain, subsequent steps build on that incorrect foundation. The error compounds. A small mistake in step 2 of a ten-step problem can make steps 3 through 10 look logically sound while still producing a wrong answer, because each step correctly follows from the (incorrect) prior step.

Verification provides a complementary signal. Instead of only rewarding correct final answers (outcome supervision), we can reward correct reasoning processes (process supervision). This distinction drives much of the research in this area.

The concept of process supervision connects to a deeper insight about how we want AI systems to behave. We do not just want models that produce correct answers on the problems we test them on. We want models that reason in ways that generalize reliably to new situations. A model that always takes the right shortcut on training data may fail badly on test data where the shortcut does not apply. A model that consistently reasons correctly step by step is more likely to maintain that reliability across the distribution of problems it encounters.

The push toward process supervision came from observing empirically that large language models with strong chain-of-thought capabilities still made systematic errors at the step level. Early work on chain-of-thought prompting showed that eliciting step-by-step reasoning dramatically improved accuracy on mathematical and logical tasks. But qualitative analysis of model outputs showed that many errors were not random but instead came from specific identifiable mistakes in reasoning steps.

OpenAI's "Let's Verify Step by Step" paper, published in 2023, made the case for process reward models by constructing PRM800K: a dataset of 800,000 step-level human annotations on mathematical reasoning chains. The paper showed that a process reward model trained on this dataset substantially outperformed outcome reward models at selecting correct solutions from large candidate sets, establishing the empirical foundation for the approaches covered in this chapter. The dataset and benchmark made the comparison reproducible and gave the field a shared testbed for evaluating verification approaches.

Step verification is the practice of checking each individual step in a chain of thought for correctness, rather than waiting until the end and evaluating only the final answer. It treats a reasoning chain as a sequence of claims, where each claim either follows correctly from prior steps or it does not.

The motivation for step-level checking is straightforward. If you can catch an error at step 3 of a ten-step problem, you can discard that reasoning chain immediately rather than allowing nine additional steps of wasted computation. More importantly, you can diagnose what went wrong. An outcome-level checker tells you that the answer is wrong. A step-level checker tells you where the reasoning broke down, which is far more actionable.

The first question is how to define a step. In natural language reasoning, step boundaries are not always obvious. A step might be:

• A single sentence in a chain of thought ("Since 3 is prime, we know...")
• A logical inference ("Therefore, by the triangle inequality...")
• A single arithmetic operation ("12 times 7 equals 84")
• A complete intermediate conclusion in a multi-part problem

For mathematical reasoning, steps often correspond to individual equations or transformations. For code generation, a step might be a single function or a block of logic. For multi-hop question answering, a step is typically a single sub-question answer that feeds into the next.

The key property a step must have is that it should be checkable in isolation given the prior context. A step like "therefore x = 5" can be verified by checking whether the preceding equations imply this. A step like "this is probably correct" cannot be verified because it makes no specific checkable claim.

In practice, different researchers have used different granularities for step definition, and the choice matters for both annotation and model performance. Finer-grained steps (individual arithmetic operations) enable more precise error localization but require more annotations and more scoring passes. Coarser steps (complete sub-proofs) are easier to annotate but may miss errors within a step. The right granularity depends on the domain and the kinds of errors that commonly occur.

Understanding what can go wrong in a reasoning step helps clarify what verification must catch:

• Arithmetic errors: A calculation is performed incorrectly ("12 times 7 is 82" instead of 84). These are among the most common errors in mathematical reasoning and are often not detected by fluency-based evaluation.
• Logical fallacies: A conclusion does not follow from the premises even if each premise is individually correct. For example, concluding that "if all cats are animals and all animals breathe, then all breathing things are cats" confuses a valid syllogism.
• Unjustified assumptions: A step introduces a new claim that was not established by prior steps and is not obviously true. This often manifests as "clearly, since X..." when X has not been established.
• Scope errors: A step applies a rule outside its valid domain, for example applying a property that only holds for positive integers to a negative number, or applying a continuous approximation where discrete counting is required.
• Factual errors: A step asserts a fact about the world that is incorrect, such as misremembering a physical constant, a historical date, or a mathematical identity.
• Reference errors: A step incorrectly cites or misinterprets a result from earlier in the chain, carrying forward a value that was computed differently.

A step verifier must catch all of these. This is a challenging requirement because it demands both mathematical rigor and world knowledge, and because some error types (unjustified assumptions, scope errors) require understanding the domain context in which the step is embedded.

Step verification can produce either a binary signal (this step is correct or incorrect) or a graded signal (this step has probability $p$ of being correct). Binary labels are simpler to collect and use but lose information. Graded signals preserve more information about uncertainty.

In practice, most systems use a probability score. A step verifier assigns a score in the range $[0, 1]$ to each step, where 1 means certainly correct and 0 means certainly incorrect. This score can then be used to select among multiple candidate reasoning paths, weight different solutions, or flag uncertain steps for human review.

The graded formulation also handles ambiguity better. Some steps are correct but expressed ambiguously. Some are incorrect but in a minor way that does not affect the final answer. A binary label forces a choice that a graded probability can express more faithfully. When using PRM scores to guide search, the continuous score allows ranking partial chains by quality, which is more informative than simply filtering by a binary threshold.

To make this concrete, consider a simple arithmetic word problem: "A train travels at 60 mph for 2 hours, then at 80 mph for 3 hours. What is the average speed for the whole journey?"

A model might produce this reasoning:

Step 1: Distance in first segment: 60 times 2 equals 120 miles. (correct) Step 2: Distance in second segment: 80 times 3 equals 240 miles. (correct) Step 3: Total distance: 120 plus 240 equals 360 miles. (correct) Step 4: Total time: 2 plus 3 equals 5 hours. (correct) Step 5: Average speed is (60 plus 80) divided by 2 equals 70 mph. (incorrect: uses arithmetic mean of speeds instead of total distance over total time)

The correct answer is 360 divided by 5 equals 72 mph. A step verifier that checks step 5 can catch this specific error: the step applies the formula for arithmetic mean speed rather than the definition of average speed. An outcome verifier might catch that the final answer is wrong, but cannot pinpoint where the error entered.

This kind of error, substituting a convenient but incorrect formula for the right one, is extremely common in language model outputs. Step verification provides the machinery to identify these cases reliably.

A process reward model (PRM) is a trained model that scores each step of a reasoning chain. Unlike outcome reward models (ORMs), which only evaluate the final answer, PRMs provide dense supervision: a score for every step. This dense signal is more informative and allows the training or search process to understand where in a chain of thought things go right or wrong.

The term "process reward model" comes from the reinforcement learning from human feedback (RLHF) framework, where reward models are used to provide training signal for policy optimization. In standard RLHF for language model alignment, a reward model provides a scalar reward for a complete response. A PRM extends this to provide rewards at each step, enabling process-level supervision in both search and training contexts.

Given a problem $x$ and a reasoning chain $s_1, s_2, \ldots, s_T$ where each $s_i$ is an individual reasoning step, a PRM assigns a score to each step:

where:

• $x$: the input problem
• $s_1, \ldots, s_i$: all steps up to and including step $i$
• $r_i$: the score for step $i$, showing the probability that this step is correct given the context

The full chain score is typically the minimum step score, showing the principle that a chain of reasoning is only as strong as its weakest step:

Alternatively, some systems use the product of step scores, treating each step as an independent event:

The minimum is more conservative and emphasizes the single worst step. The product can be used as an approximation to joint probability under an independence assumption. In practice, the minimum and product often rank chains similarly, but the minimum tends to be more robust to PRM miscalibration on individual steps because it does not compound small errors in probability estimates across many steps.

A third aggregation method, used in some production systems, is a weighted average that gives more weight to later steps, since errors in early steps tend to propagate and early errors are often identified by lower step scores downstream. The choice of aggregation is an empirical decision typically validated against a held-out correctness dataset.

Training a process reward model requires step-level labels: for each step in each training example, a label indicating whether that step is correct. This is substantially more expensive to collect than outcome labels, which only require knowing whether the final answer is correct.

The OpenAI PRM800K dataset, released in 2023 alongside the "Let's Verify Step by Step" paper, provides human labels for 800,000 steps in mathematical reasoning chains. Each step is labeled as positive (the step is correct and valid), negative (the step contains an error), or neutral (the step is a restatement or formatting change that is not a substantive reasoning step). This dataset enabled training PRMs specifically for grade-school and competition mathematics and became the benchmark for evaluating PRM quality.

Collecting this dataset required significant effort. Annotators were domain experts in mathematics who could verify each step independently. The annotation interface presented each step in context, with the problem statement and all prior steps visible, and asked annotators to judge whether the current step followed correctly from what came before. Annotators were paid for their time, making the total cost of 800K annotations substantial. This cost is one of the primary barriers to deploying PRMs in new domains.

Given step-level labels, a PRM is trained as a classifier. The architecture uses a language model backbone, typically the same architecture as the generator model to allow knowledge transfer. For each step position, a special marker token (such as [STEP] placed at the end of each step) is used to extract a representation, and a classification head predicts the correctness probability:

where:

• $h_i \in \mathbb{R}^d$: the hidden state at the step marker token for step $i$
• $w \in \mathbb{R}^d$: learned weight vector for the classification head
• $b \in \mathbb{R}$: learned bias term
• $\sigma$: the sigmoid function, mapping the logit to a probability in $[0, 1]$

The model is trained with binary cross-entropy loss summed over all step positions:

where:

• $y_i \in \{0, 1\}$: the human-provided label for step $i$ (1 for correct, 0 for incorrect)
• $r_i$: the predicted probability that step $i$ is correct
• $T$: the total number of steps in the reasoning chain

The cross-entropy loss penalizes the model for being confident and wrong. If a step is labeled correct ($y_i = 1$) but the model assigns low probability ($r_i$ close to 0), the term $-y_i \log r_i$ becomes large, driving a large gradient update. Conversely, if a step is labeled incorrect but the model confidently calls it correct, $-(1-y_i)\log(1-r_i)$ is large. The model is trained to be well-calibrated: high confidence only when the step is correct.

An important implementation detail is that the PRM is trained to score each step given all previous steps, not in isolation. The hidden state $h_i$ is computed by processing the full sequence $x, s_1, \ldots, s_i$ through the language model, so the representation at position $i$ has attended to all prior context. This means the PRM can detect errors that depend on earlier steps, including reference errors and unjustified assumptions that can only be identified relative to what was established earlier.

The key difference between outcome reward models and process reward models is the granularity of supervision. Both approaches use a language model backbone and a classification head. Both are trained on examples drawn from model outputs. The distinction lies entirely in what gets labeled.

An ORM sees the full problem and full solution, and predicts whether the final answer is correct. It learns which overall solution styles tend to produce correct answers. An ORM cannot localize errors, because it has no step-level training signal. When an ORM scores a solution highly, it is saying "this kind of solution tends to be correct," not "each step in this specific solution is valid."

A PRM sees the problem and each step in sequence, and predicts whether each step is correct. It learns to identify local reasoning failures. PRMs are harder to train (requiring more annotation effort) but more informative. A PRM that scores step 3 low is providing specific, actionable information: this step is where the reasoning went wrong.

This difference in granularity has important practical consequences for search. When selecting among N candidate solutions, an ORM provides one score per solution. A PRM provides T scores per solution (one per step), allowing much finer discrimination. Two solutions may both reach a correct final answer, but one arrives there via a clean, tight chain of reasoning while the other includes several uncertain steps that happened to cancel out. A PRM can distinguish these cases; an ORM cannot.

Empirically, PRMs substantially outperform ORMs at selecting correct solutions from large candidate sets. In the "Let's Verify Step by Step" experiments, a PRM selecting the best of 1860 generated solutions achieved 78.2% accuracy on MATH benchmark problems, compared to 72.4% for an ORM with the same selection budget. The gap is even larger at intermediate selection budgets (best-of-100, best-of-200), where the PRM's step-level discrimination provides the most benefit.

The primary cost of PRMs is annotation. Human annotators must read each reasoning step and judge whether it is correct given the problem context and prior steps. This requires domain expertise, particularly for mathematical reasoning, which means annotation is expensive and slow.

Several strategies exist for reducing annotation cost.

Monte Carlo estimation provides a way to infer step labels from outcome labels. The idea is to estimate the probability that a correct final answer can be reached from a given step by sampling many completions. If you have a partial reasoning chain up to step $i$ and you sample 100 completions from that point, and 80% of those completions reach the correct final answer, then step $i$ is likely correct. If only 5% of completions from step $i$ reach the correct answer, then step $i$ is likely flawed. More precisely, the Monte Carlo estimate of step correctness is:

where $K$ completions are sampled from the language model conditioned on the problem and all steps up to $i$. This approach, used in systems like MCTS-guided PRMs and the Math-Shepherd dataset, avoids human annotation entirely but introduces noise. A step that uses an incorrect method but arrives at a correct intermediate value (or where the error has not yet manifested) may be assigned high Monte Carlo probability even though it is logically flawed. The method works best when errors have clear downstream consequences in the form of wrong final answers.

Automated verifiers for specific domains (such as symbolic math solvers or code executors) can provide exact correctness labels without human annotation. A code step that produces the right intermediate output is correct; one that does not is wrong. For mathematical reasoning, a computer algebra system can verify algebraic transformations exactly. This applies to structured domains but not to open-ended reasoning or natural language arguments.

Weak labeling from model confidence uses the model's own probability estimates as a proxy for correctness. While noisy, this can be used to create large training datasets cheaply, which can then be refined with a smaller amount of human annotation. This semi-supervised approach allows scaling the labeled dataset beyond what pure human annotation permits.

Consensus labeling has multiple models or multiple annotators label the same steps independently and uses agreement to identify high-confidence labels. Steps where all annotators agree are straightforward to include; steps with high disagreement may require more careful review or may be excluded from training.

In practice, most deployed PRMs use a combination: a large number of Monte Carlo estimated labels supplemented by a smaller number of high-quality human labels. The human labels ensure that the PRM learns from at least some examples where correctness has been definitively established, while the Monte Carlo labels provide coverage across a wide range of problem types and reasoning styles.

The PRM backbone is typically initialized from the same pretrained language model used for generation. This initialization is important because the PRM needs to understand the mathematical language and reasoning conventions present in the steps it is scoring. A randomly initialized scorer would need to learn the domain from scratch, which requires more training data and produces a less reliable scorer.

After the backbone is initialized, step marker tokens are inserted at the boundaries between steps in the training data. These markers serve as anchor points where the classification head reads off the hidden state. During training, the backbone weights are updated along with the classification head, allowing the backbone to adapt its representations specifically for step correctness judgment.

One practical challenge is that step labels are often imbalanced: in any large dataset of model-generated reasoning, most steps are correct, and incorrect steps are a minority. This imbalance can cause the model to be overly optimistic in its scoring. Addressing this requires either resampling (increasing the proportion of incorrect-step examples in training batches) or loss reweighting (applying higher loss weight to incorrect-step examples).

Calibration is another concern. A PRM whose probability outputs are well-calibrated is more useful than one that merely ranks steps correctly. A score of 0.8 should mean that approximately 80% of similarly-scored steps are correct. Calibration can be checked by collecting held-out step labels and comparing model confidence scores against empirical accuracy across score bins.

Once you have a step verifier or PRM, the most powerful application is using it to guide search. Instead of generating a single chain of thought and hoping it is correct, you can generate many candidate chains and use the verifier to select, prune, or steer among them. This turns verification from a passive evaluation tool into an active component of reasoning.

The core insight is that generation and verification play complementary roles in an ensemble system. The generator is good at producing fluent, plausible reasoning but may include errors. The verifier is good at distinguishing correct from incorrect reasoning but cannot generate new solutions. Combining them, using the generator to produce diverse candidates and the verifier to select the best ones, produces a system that is more accurate than either component alone.

The simplest application of a verifier is best-of-N selection: generate $N$ complete reasoning chains, score each one using the verifier, and return the highest-scoring chain. This is sometimes called reranking.

Given $N$ candidate chains $C_1, C_2, \ldots, C_N$, each with a verifier score $V(C_i)$, the selected chain is:

where:

• $C_i$: the $i$-th candidate reasoning chain
• $V(C_i)$: the score assigned to chain $i$ by the verifier, either from an ORM or by aggregating PRM step scores
• $C^*$: the selected best chain

This approach has clear scaling properties. As $N$ increases, the chance that at least one of the $N$ chains is correct increases, and a good verifier identifies it. Empirically, best-of-N selection provides substantial gains. On MATH problems, best-of-100 with a PRM substantially outperforms greedy decoding or majority voting across a wide range of model sizes.

The computational cost scales linearly with $N$: generating $N$ chains costs $N$ times a single generation. This is often acceptable in inference-time settings where accuracy matters more than speed. Many production systems that require high accuracy on individual queries (such as a math tutoring system that should not give wrong answers) budget for generating tens of candidates rather than relying on a single output.

Best-of-N selection also has a natural extension: weighted majority voting. Instead of selecting the single highest-scoring chain, you aggregate the answers from all $N$ chains, weighting each answer by its PRM score. If five chains reach the answer "42" with average PRM score 0.9, and three chains reach "43" with average PRM score 0.5, the weighted vote strongly favors "42". This is more robust than either raw majority voting or single-best selection because it combines the diversity benefit of majority voting with the quality signal of the PRM.

Best-of-N selection is efficient but wasteful: it generates complete chains before evaluating them, so many computational resources go toward chains that the verifier will ultimately reject. Beam search with step scores is more efficient: it uses PRM scores at each step to prune bad partial chains early.

The algorithm works as follows. Maintain a beam of $K$ partial reasoning chains. At each step, expand each partial chain by generating multiple candidate next steps. Score each candidate next step using the PRM. Keep only the top $K$ candidates by score. Continue until all chains in the beam reach a final answer.

Formally, let $B_t$ denote the beam at step $t$, containing at most $K$ partial chains. For each chain $c \in B_t$, generate a set of candidate continuations. The beam update is:

ranked by:

where:

• $c \oplus s$: the chain $c$ extended by step $s$
• $\text{expand}(c)$: the set of candidate next steps generated by sampling from the language model given chain $c$
• $\text{PRM}(x, c_1, \ldots, c_t, s)$: the process reward model score for the current step $s$
• $K$: the beam width

This approach uses verifier scores to focus computation on promising reasoning paths. Steps that the verifier judges as low-quality are pruned, and the remaining compute is spent expanding steps the verifier finds plausible. In practice, beam search with a PRM uses fewer total samples than best-of-N to achieve comparable accuracy, because compute is not wasted on continuing a chain after an error has been detected.

Beam search introduces one important consideration: diversity. When all $K$ beams converge on very similar partial chains, the search loses the benefit of exploring diverse reasoning strategies. This can happen when the PRM strongly prefers one particular reasoning style. Techniques to maintain beam diversity include adding a penalty for duplicate prefixes, using diverse sampling rather than argmax at each step, or maintaining a "diversity buffer" that ensures at least some fraction of beams take different approaches.

For more complex reasoning problems, Monte Carlo Tree Search (MCTS) provides a principled framework for balancing exploration and exploitation in reasoning. MCTS treats the reasoning problem as a tree where each node is a partial reasoning chain and each edge is a candidate next step.

MCTS was originally developed for game-playing AI, most famously in the AlphaGo system that defeated world champion Go players. The connection to reasoning is natural: in Go, each node in the search tree is a board position and each edge is a move; in reasoning, each node is a partial chain and each edge is a reasoning step. In both cases, the algorithm must balance exploring new possibilities (to avoid missing a good solution) against exploiting known good paths (to deepen analysis of promising lines).

The algorithm alternates between four phases.

Selection: Starting from the root, navigate the tree by choosing child nodes that balance high expected value with low visit count. The UCT (Upper Confidence Bound for Trees) formula guides this:

where:

• $Q(v)$: the estimated value of node $v$, based on outcomes from previous simulations through $v$
• $N(v)$: the number of times node $v$ has been visited
• $N(\text{parent}(v))$: the number of times the parent of $v$ has been visited
• $c$: an exploration constant that controls the exploration-exploitation trade-off

The first term $Q(v)$ encourages selection of nodes that have historically led to good outcomes. The second term $c \sqrt{\ln N(\text{parent}(v)) / N(v)}$ encourages selection of nodes that have been visited few times relative to their sibling nodes. The exploration constant $c$ is a hyperparameter that determines how much the algorithm prefers exploration. High $c$ means the algorithm explores widely; low $c$ means it exploits what it already knows is good.

Expansion: When selection reaches a node that has not been fully expanded, add one or more child nodes by sampling candidate next steps from the language model.

Simulation (Rollout): From the newly expanded node, simulate a complete trajectory by generating the remaining reasoning steps using the language model. Evaluate the trajectory using the verifier or by checking whether the final answer is correct.

Backpropagation: Update the estimated values of all nodes along the path from the expanded node back to the root, incorporating the simulation result. If the rollout reached a correct answer, increase the $Q$ value of all nodes on the path. If incorrect, decrease it.

MCTS is more powerful than beam search because it explicitly reasons about which parts of the search space are most worth exploring. It can revisit promising intermediate steps, generate many continuations from a node that looks strong, and avoid wasting compute on clearly inferior paths. The key advantage over beam search is that MCTS can back up and continue from an earlier promising point in the reasoning chain, whereas beam search makes irrevocable pruning decisions.

In practice, MCTS for reasoning replaces the game-tree rollout with language model sampling. The rollout policy is typically a fast language model (possibly the same generator model, possibly a smaller distilled version) that quickly completes the reasoning chain from any intermediate point. The value function that evaluates completed rollouts can be a PRM, an ORM, or simply a binary check against the known correct answer. The combination of PRM-guided value estimation with MCTS-style search has produced some of the strongest results in complex mathematical reasoning benchmarks.

An important empirical finding is that verification-guided search exhibits favorable scaling behavior. As the number of candidate solutions increases, accuracy improves in a predictable way, provided the verifier is good enough to distinguish correct from incorrect chains.

For best-of-N with a perfect verifier, the probability of selecting a correct solution from $N$ candidates is:

where $p$ is the probability that any single sample is correct. This expression grows rapidly with $N$ even when $p$ is small. For $p = 0.1$, best-of-10 achieves $1 - 0.9^{10} \approx 0.65$ success rate, and best-of-100 achieves $1 - 0.9^{100} \approx 0.99999$.

The key insight is that compute at inference time can substitute for larger models. A smaller model generating many solutions and using a verifier to select among them can match or exceed a larger model generating a single solution. This has practical significance: inference compute is more flexible and controllable than model size. You can allocate more compute to harder problems and less to easier ones without retraining the model.

This scaling behavior has a ceiling, however. If the verifier is imperfect, the benefit of additional candidates eventually saturates. With a verifier that has 90% true positive rate, generating more than a few hundred candidates produces diminishing returns because the verifier's error rate starts dominating. The scaling curve for a real PRM therefore flattens earlier than the ideal curve, and the gap between the real PRM and the perfect verifier represents the room for improvement in verification quality.

A conceptually appealing idea is to have a model verify and correct its own outputs: generate an initial answer, identify errors in it, and revise accordingly. This is called self-correction or self-refinement. It requires no external verifier, just the model's own ability to evaluate its reasoning.

The appeal of self-correction is practical. External verifiers require separate training, separate inference, and maintenance as the generator model improves. If a generator model could reliably detect and fix its own errors, verification would become much cheaper. The question is whether this capability exists, and under what conditions.

Effective self-correction has several prerequisites:

• The model must be able to detect errors in its own output that it could not detect at generation time. This requires either a different reasoning process during review than during generation, or information that was not available during the initial generation.
• The model must be able to generate corrections that fix those errors, not just paraphrase the flawed reasoning in different words.
• The corrections must not introduce new errors while fixing existing ones.

These requirements are stringent. If the model was confident and wrong during initial generation, it may also be confident and wrong during self-evaluation. Research has shown that naive self-correction, where a model is simply asked to review and improve its answer, often fails to improve accuracy and can even decrease it. The model tends to second-guess correct answers, introduce unnecessary complexity, or produce superficial changes that do not address underlying errors.

The fundamental problem is that the model's internal state during generation already reflected the best representation it could form given its weights and the context. Asking it to "review" that output does not provide new information unless the prompt structure changes the effective inference procedure. Simply appending "please check your work" to the prompt and sampling again draws from a similar distribution to the original output.

Self-correction is most effective in several specific conditions.

The model has access to external feedback. When a code interpreter can run the model's code and return an error message, the model can incorporate that specific external signal. This is not pure self-correction but verification-grounded correction. The external executor provides information that was not available during generation, which the model can use to diagnose and fix the error. Research on code generation consistently finds that execution-based self-correction substantially improves success rates on programming tasks.

The error type is systematic and detectable. If a model reliably can detect format violations, constraint violations, or factual inconsistencies against its own earlier statements, it can correct them. A model that generates a list of five items when the prompt requested exactly three can detect and fix this count error. It is harder to self-correct subtle logical errors that require deep domain reasoning to identify.

The initial generation used a different strategy than correction. If the model generates a concise answer first and then asks itself to work through the problem step by step, the second pass may catch errors the first pass made by taking shortcuts. The change in reasoning strategy (rather than another review of the same strategy) is what enables improvement. Some papers call this "draft-then-verify" and show it can improve accuracy relative to generating the chain of thought directly.

Confidence is calibrated. A model that knows when it is uncertain can focus correction effort on uncertain steps. If confidence is uncalibrated (the model is equally confident when right and wrong), self-verification provides no useful signal. Well-calibrated models can use their own uncertainty estimates to identify which steps are worth re-examining.

The problem has verifiable intermediate structure. Word problems with numerical answers, code problems with test cases, and logic puzzles with checkable constraints all provide internal checkability. After generating a candidate solution, the model can re-read the problem statement and check whether each claimed step follows from the stated premises.

Iterative self-refinement applies self-correction in a loop: the model generates an output, evaluates it, generates feedback on what is wrong, and produces an improved version. This loop continues for a fixed number of iterations or until the model assesses its output as satisfactory.

The procedure at each iteration $t$ is:

1. Generate output $y^{(t)}$ given the problem $x$ and prior output $y^{(t-1)}$
2. Generate feedback $f^{(t)}$ by prompting the model to evaluate $y^{(t)}$
3. Generate revised output $y^{(t+1)}$ given $x$, $y^{(t)}$, and $f^{(t)}$

The key question is whether $y^{(t+1)}$ is systematically better than $y^{(t)}$. For tasks with clear objective criteria (code that runs, outputs that satisfy explicit constraints), iterative refinement tends to improve output quality. For tasks with subjective criteria or where model errors are subtle, the improvement is less consistent, and gains are often small relative to the additional compute cost.

One important failure mode in iterative self-refinement is "overcorrection." The model may fix an actual error in round $t$ but then correct a correct element in round $t+1$, oscillating rather than converging to a correct answer. This is especially common when the model is asked to evaluate its own confidence in an uncalibrated way. Adding a stopping criterion based on agreement between consecutive outputs (if $y^{(t)}$ and $y^{(t+1)}$ differ only superficially, stop) can reduce wasted iterations without improving quality.

The practical difference between self-correction and external verification is that self-correction uses the same model for generation and evaluation, while external verification uses a separate model or system trained specifically to evaluate reasoning quality.

External verifiers have a clear advantage: they are trained for evaluation, not generation, so their evaluation may be more reliable. A model fine-tuned specifically on step correctness labels is better at detecting step errors than the same base model prompted to self-evaluate. The PRM has seen thousands of examples of incorrect steps alongside correct ones during training; the base model asked to self-evaluate has no such specialized training.

The trade-off is cost and generality. External verifiers require separate training or separate model calls. Self-correction requires only additional inference from the same model. For many practical applications, a combination works well: use the model itself for initial self-filtering (removing outputs that fail obvious checks), then use an external PRM for final selection among the remaining candidates.

A persistent challenge in deploying PRMs is reward hacking: the generator model learns to produce reasoning chains that score highly on the PRM while remaining incorrect. This happens because the PRM is an imperfect proxy for correctness, and if the generator is trained against the PRM (as in reinforcement learning settings), it will eventually find patterns that exploit the PRM's blind spots.

Reward hacking in the context of PRMs takes several forms. The most common is stylistic alignment: the generator learns that certain linguistic patterns (hedging phrases, formal mathematical notation, specific transition words) correlate with high PRM scores, regardless of whether the underlying reasoning is correct. A generator trained against a PRM may produce overly formal, jargon-heavy reasoning chains that satisfy the PRM's surface-level patterns while containing subtle logical errors.

A subtler form of reward hacking involves step decomposition manipulation. If the PRM assigns high scores to short, simple steps and lower scores to complex steps, the generator may learn to break correct reasoning into many trivially simple sub-steps, achieving high average step scores by avoiding any step that could be flagged as wrong. The resulting chains may be correct but uselessly verbose.

There is also the problem of out-of-distribution reasoning. PRMs are trained on reasoning chains from a particular generator model. If the generator is subsequently trained on PRM feedback and shifts its distribution, the PRM's scores become less reliable because it is now evaluating a different kind of reasoning than it saw during training. This distributional shift is especially problematic in iterative reinforcement learning pipelines where the generator changes rapidly.

Calibration problems compound reward hacking. A well-calibrated PRM assigns scores that correlate tightly with actual correctness probabilities. A poorly calibrated PRM may be confident in wrong directions: assigning high scores to incorrect steps when they are expressed confidently, or penalizing correct steps that use unconventional notation. Monitoring PRM calibration over time, and retraining or recalibrating when the generator distribution shifts, is a practical requirement for maintaining system quality.

One mitigation approach is to use multiple independent verifiers and require agreement. If three independently trained PRMs all assign high scores to a reasoning chain, reward hacking is less likely because exploiting all three simultaneously is harder than exploiting one. Another mitigation is to maintain a held-out set of problems with known correct step-level labels and periodically evaluate PRM accuracy on this set to detect when calibration has degraded.

In practice, reasoning verification systems combine multiple components. A typical production pipeline for high-stakes reasoning includes several stages that work together to improve both accuracy and interpretability.

Generation is the first stage. Sample $N$ candidate reasoning chains from the language model. This can use standard sampling, chain-of-thought prompting, or structured prompting to elicit step-by-step reasoning. Using a temperature slightly above zero (such as 0.7 to 0.9) introduces diversity among the $N$ chains, making sure the set of candidates covers a range of reasoning strategies rather than $N$ copies of the same approach.

Step scoring applies a PRM to score each step in each candidate chain. Flag chains with low minimum step scores for closer inspection. At this stage, you can also identify which specific steps are problematic, giving interpretability: instead of only saying "this chain is probably wrong," you can say "this chain appears to go wrong at step 4."

Candidate selection uses PRM scores to select the best candidate. For maximum reliability, combine PRM scores with majority voting: find the answer that appears most often among high-scoring chains. This combination is more robust than PRM ranking alone because majority voting is resilient to cases where the PRM scores are miscalibrated, and PRM ranking is resilient to cases where the majority answer happens to be wrong.

Optional self-correction handles low-confidence situations. For candidates where all candidates score below a threshold, attempt a self-correction round with the original language model, then re-score with the PRM. This step is optional and most useful when the initial generation budget is small and a second-chance mechanism is needed.

The combination of sampling diversity, step-level verification, and structured selection is substantially more robust than any single component alone.

To ground the abstract framework in something concrete, let us walk through how a PRM would score a specific mathematical reasoning chain. Consider the following problem and a candidate solution.

Problem: "A store sells widgets for $8 each. They offer a 15% discount on orders of 10 or more. If I buy 12 widgets, how much do I pay in total?"

Candidate reasoning chain:

Step 1: The normal price for 12 widgets is 12 times $8 equals $96. Step 2: Since I am buying 12, which is at least 10, the 15% discount applies. Step 3: The discount amount is 15% of $96, which is 0.15 times 96 equals $14.40. Step 4: The final price is $96 minus $14.40 equals $81.60.

A PRM would process this chain as follows. The model reads the problem statement and each step in sequence, and at each step marker produces a correctness probability.

Step 1: The calculation is straightforward. 12 times 8 equals 96. This is arithmetically correct and logically appropriate (computing total before discount). A well-trained PRM assigns a high score, perhaps 0.97.

Step 2: This step checks the eligibility condition. The problem states "orders of 10 or more" and 12 is indeed at least 10. The logical inference is valid. A PRM assigns a high score, perhaps 0.96.

Step 3: The arithmetic is 0.15 times 96 equals 14.40. This is correct: 0.15 times 96 equals 0.1 times 96 plus 0.05 times 96 equals 9.6 plus 4.8 equals 14.4. The PRM assigns a high score, perhaps 0.95.

Step 4: The final calculation is 96 minus 14.40 equals 81.60. This is correct. The PRM assigns a high score, perhaps 0.96.

The chain score using the minimum aggregation is $\min(0.97, 0.96, 0.95, 0.96) = 0.95$. This chain would be selected over one with a low-scoring step.

Now consider an alternative candidate reasoning chain with an error:

Step 1: The normal price for 12 widgets is 12 times $8 equals $96. Step 2: The discount is 15%, so I pay 85% of the normal price. Step 3: 85% of $96 is 0.85 times 96 equals $81.60.

This is also correct and produces the same answer. A PRM trained on diverse examples might score this chain comparably or even higher, since it is more concise and each step is clearly valid. The PRM does not require a specific reasoning path, only that each step be locally correct.

Now consider a chain with an error:

Step 1: The normal price for 12 widgets is 12 times $8 equals $96. Step 2: Since I am buying 12, the 10% bulk discount applies. Step 3: The discount amount is 10% of $96, which is $9.60. Step 4: The final price is $96 minus $9.60 equals $86.40.

Step 2 contains a factual error: it states "10% bulk discount" when the problem specifies 15%. A PRM would assign a low score to this step because it misreads the discount percentage from the problem statement. The minimum chain score drops to the score for step 2, perhaps 0.08, and this chain would be ranked below the correct chains.

This example illustrates the PRM's core function: it can identify the specific step where a reasoning chain diverges from correctness, giving both a quality score and error localization that an ORM cannot.

Process reward models have several practical limitations worth understanding. The most fundamental is the distributional mismatch problem. PRMs are trained on a fixed distribution of reasoning chains, typically those produced by a specific model at a specific capability level. When applied to a different model or a significantly stronger base model, the PRM may be poorly calibrated. A step that the training model found difficult may be trivial for a stronger model, yet the PRM assigns it the same uncertainty as it did for the weaker model's output. Retraining PRMs as base models improve is a significant ongoing cost that has no obvious endpoint as the field continues to advance model capabilities rapidly.

Annotation cost remains a barrier to deploying PRMs in new domains. The 800K step labels in PRM800K took substantial human effort to collect, and they cover only mathematical reasoning. Extending PRMs to legal reasoning, medical diagnosis, or code debugging requires either similarly large annotation efforts or reliable automated annotation strategies. Monte Carlo estimation via rollouts helps, but introduces noise when the generation model can reach correct answers via incorrect paths. A model that uses a wrong method but happens to find the right numerical answer will have that incorrect step estimated as high-quality by Monte Carlo sampling, because subsequent completions from that step often still reach the right answer.

Generalization across problem types is another challenge. A PRM trained on arithmetic and algebra problems may not generalize to geometry proofs or combinatorics, even within the broad category of mathematical reasoning. The linguistic patterns and verification requirements differ enough across sub-domains that specialized training may be necessary. This further multiplies the annotation and training cost.

Self-correction has a fundamental reliability problem. The same capabilities and knowledge limitations that cause the model to make errors in the first place often cause it to fail to detect those errors. This is most problematic for subtle errors that require deep domain expertise to catch. A model that incorrectly applies the chain rule in a calculus problem will typically not catch this error during self-review, because the error reflects a gap in its understanding rather than an oversight. Self-correction performs best when error detection is external (code execution, constraint checking) rather than relying on the model's introspective ability.

Verification-guided search introduces a significant increase in inference cost. Generating 100 candidates and scoring each with a PRM requires roughly 100 times more compute than single-pass generation. For latency-sensitive applications, this is often impractical. In practice, teams choose $N$ based on acceptable latency and compute budget, balancing accuracy against cost. The typical production trade-off is to use small $N$ (5 to 20 candidates) for interactive applications and larger $N$ (50 to 200 candidates) for batch-processing applications where latency is less critical.

A subtler limitation is the evaluation problem: how do you know if your PRM is working well? If you have ground-truth correctness labels for test problems, you can measure PRM accuracy directly. But in new domains where you lack such labels, you may not know whether your PRM is well-calibrated until errors accumulate in production. This creates a deployment risk that is difficult to quantify ahead of time.

Despite these limitations, verification-based approaches represent a qualitatively important direction. They decouple generation quality from evaluation quality, allowing improvements in verification to benefit even models that were trained without step-level supervision. They also provide a path toward more interpretable and auditable AI systems: when a model's reasoning is evaluated step by step, it becomes easier for humans to inspect where and why errors occur. A system that provides step-level scores is more transparent than one that produces only a final answer, even if the underlying models are equally accurate in terms of final answer correctness.

The broader significance is that verification separates two problems that are often conflated: generating plausible text and generating correct reasoning. Progress on generation (scaling, better training) is distinct from progress on verification (better labeling, better PRM architectures). Having these as separate, independently improvable components means that breakthroughs in one area benefit the whole system without requiring simultaneous progress in the other.

Reasoning verification addresses the gap between generating plausible reasoning and generating correct reasoning. The key ideas from this chapter are:

• Step verification breaks reasoning into individual checkable claims rather than evaluating only the final answer. This enables error localization and finer-grained quality control, and is motivated by the observation that verification is often easier than generation.

• Process reward models formalize step verification by training a model to score each reasoning step. They require step-level labels (expensive to collect but highly informative) and provide substantially better selection signal than outcome reward models, as demonstrated by the PRM800K experiments showing a 78.2% versus 72.4% accuracy advantage at large selection budgets.

• Verification-guided search uses PRM scores to steer reasoning toward correct paths. Best-of-N selects the highest-scoring complete chain; beam search prunes low-scoring partial chains; MCTS adaptively allocates compute to promising reasoning branches using the same UCT-based exploration-exploitation trade-off pioneered in game-playing AI.

• Self-correction allows models to review and revise their own outputs without a separate verifier, but is most effective when backed by external feedback (code execution, constraint satisfaction) rather than relying solely on the model's own judgment. Naive self-correction without external grounding often fails to improve accuracy.

• Reward hacking and calibration are practical concerns when PRMs are deployed in production. The same distributional mismatch and calibration issues that affect reward models in RLHF apply here, and require ongoing monitoring and retraining.

• Together, these components form a reasoning pipeline that is substantially more reliable than single-pass generation, at the cost of additional inference compute. The compute overhead is controllable and can be balanced against accuracy requirements for different application settings.

The next chapter extends these ideas to mathematical reasoning specifically, where the step structure is particularly well-defined and automated verification is often possible through symbolic computation.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about reasoning verification.