Reasoning Verification › Verification-Guided Search

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:

$$C^* = \arg\max_{i=1}^{N} V(C_i)$$

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:

$$B_{t+1} = \text{top-K}\left\{ (c \oplus s) : c \in B_t, s \in \text{expand}(c) \right\}$$

ranked by:

$$\text{score}(c \oplus s) = \text{PRM}(x, c_1, \ldots, c_t, s)$$

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:

$$\text{UCT}(v) = Q(v) + c \sqrt{\frac{\ln N(\text{parent}(v))}{N(v)}}$$

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:

$$P(\text{success}) = 1 - (1 - p)^N$$

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.