Technical Summary: From Correctness to Utility: Gain-Based Prefix Evaluation for LLM Reasoning

1. Problem Statement

Large Language Models (LLMs) solve problems through sequential reasoning, where intermediate prefixes significantly shape future trajectories. Existing process reward models (PRMs) typically evaluate these prefixes based on local step correctness—judging whether an intermediate step is valid or likely to follow a correct path. However, the authors argue that local correctness is an indirect and often insufficient proxy for the ultimate goal: determining whether a prefix increases the probability of a successful completion.

A locally correct step may leave the remaining trajectory brittle, while an incomplete or non-standard prefix might reveal a key idea that improves downstream solvability. Furthermore, current rollout-based methods often estimate absolute state values tied to specific policies, failing to explicitly measure the marginal improvement caused by the prefix itself relative to the problem and solver population. The central challenge is to formulate a prefix evaluation metric that captures utility—the extent to which a prefix improves the chance of success—rather than just correctness.

2. Methodology

2.1 Core Concept: Prefix Gain

The paper defines prefix gain as the marginal improvement in downstream solve probability induced by a prefix $p$ for a problem $x$. Formally, for a student model $s$ with policy $\pi_s$, the gain is:
$$g_s(x, p) = q_s(x, p) - q_s(x, \emptyset)$$
where $q_s(x, p)$ is the probability of solving the problem after observing prefix $p$, and $q_s(x, \emptyset)$ is the probability of solving it from scratch. A positive gain indicates the prefix aids success; a negative gain indicates it hinders it.

2.2 Estimation via Lightweight Student Models

To estimate gain scalably, the authors employ a group of lightweight student models ($S = \{s_1, \dots, s_M\}$) with varying capability levels.

1. Sampling: Diverse prefixes are sampled from reasoning trajectories.
2. Rollout: Each student solves the problem with and without the prefix to generate empirical solve rates.
3. Gain Profile: This yields a distribution of gains across the student population.
4. Scalarization: The authors decompose the gain profile into:
   • Intrinsic Utility: A transferable component shared across solvers (reflecting general usefulness).
   • Policy-Dependent Utility: Solver-specific variations based on capability and style.
     For the main model, they adopt a simple scalarization: normalizing gains for each student and averaging them to estimate the intrinsic utility $G_{intr}(x, p)$.

2.3 Prefix Utility Model (PUM)

The authors train a Prefix Utility Model (PUM), an LLM-based scalar evaluator, using the following pipeline:

• Data Construction (PUM-Math): Constructed from 20K mathematical reasoning trajectories. Instead of manual step annotations, they generate 280K outcome-grounded pairwise utility preferences.
  • Vertical Pairs: Compare prefixes at different truncation points of the same trajectory.
  • Horizontal Pairs: Compare prefixes of similar length from different trajectories of the same problem.
  • Labeling: Pairs are labeled based on the difference in intrinsic utility estimates. An adaptive margin filters out noisy or conflicting preferences.
• Training Objective: PUM is trained using a Bradley-Terry pairwise ranking loss. It takes a problem $x$ and prefix $p$ as input and outputs a scalar utility score $U_\theta(x, p)$. The model is optimized to prefer prefixes with higher estimated gain.

3. Key Contributions

1. Formulation of Prefix Evaluation as Gain Estimation: The paper shifts the paradigm from local correctness to counterfactual gain estimation, measuring how much a prefix improves downstream solve probability relative to a baseline.
2. PUM-Math Dataset: The construction of a large-scale, gain-based prefix supervision dataset derived from 20K trajectories and 280K pairwise preferences, requiring no manual step-level annotations.
3. Prefix Utility Model (PUM): A trained evaluator that provides outcome-grounded prefix utility signals.
4. Empirical Validation: Demonstration that gain-based supervision improves performance across three distinct reasoning paradigms:
   • Best-of-N Selection: Selecting the best trajectory from a pool of candidates.
   • Beam Search: Guiding search by pruning unpromising partial prefixes.
   • Reinforcement Learning (RL): Providing dense credit assignment signals for policy optimization.

4. Experimental Results

4.1 Best-of-N Selection

Across MATH500, GAOKAO2023, and AIME2025 benchmarks, PUM achieved the best or near-best selection accuracy, particularly when candidate pools were large ($N \ge 32$). Unlike PRM baselines that often over-score locally plausible but incorrect reasoning, PUM's outcome-grounded utility provided stronger trajectory-level verification. It also demonstrated superior ranking robustness, assigning consistently high ranks to correct responses and low ranks to incorrect ones.

4.2 Beam Search

In beam search experiments on MATH500 and GAOKAO2023, PUM consistently outperformed PRM, PQM, and CRM baselines. The performance gap widened as search budgets increased (e.g., $N=100$), where PUM reached 78.00% accuracy (Qwen) and 73.60% (Llama). This suggests PUM is more effective at preserving partial reasoning prefixes that remain useful after further expansion, whereas other methods often degrade due to misalignment with final correctness.

4.3 Reinforcement Learning

• Outcome-Anchored Setting: When combined with rule-based GRPO, PUM improved the weighted average accuracy from 55.21% (vanilla GRPO) to 58.09%.
• Process-Only Setting: In settings without final-answer rewards, PRM and PQM training initially improved but later collapsed due to "reward hacking" (generating longer, locally correct but ultimately incorrect responses). PUM remained stable, achieving 57.21% average accuracy.
• Hard Data Learning: On problems where the base model failed to produce correct solutions in 16 rollouts (sparse rule-based rewards), PUM-only training yielded significantly faster improvement than vanilla GRPO, demonstrating high data efficiency.

4.4 Further Analyses

• Weak-to-Strong Generalization: PUM generalized effectively to stronger policy models (Qwen2.5-32B) not used in its training, indicating it captures intrinsic utility rather than just fitting generation patterns.
• Scalability: Performance improved with larger backbone models and increased training data, suggesting the supervision signal is not saturated.
• Cost Efficiency: PUM-Math required approximately 18.5x less labeling computation than the Math-Shepherd dataset (which relies on a 7B model for step-level supervision), while avoiding manual annotation entirely.

5. Significance and Claims

The paper claims that outcome-grounded gain provides a more effective and efficient supervision target for prefix evaluation than local correctness. By shifting focus from "is this step valid?" to "does this step improve the chance of solving the problem?", PUM offers a robust signal for:

• Verification: Distinguishing correct trajectories from plausible but incorrect ones in large candidate pools.
• Search: Guiding exploration in beam search by identifying promising partial states.
• Credit Assignment: Providing dense, reliable rewards for RL, especially in scenarios with sparse final answers.

The authors emphasize that this approach separates prefix usefulness from problem difficulty and solver prior ability, enabling more scalable and data-efficient construction of process supervision datasets.

6. Limitations

The authors acknowledge several limitations:

• Domain Scope: Experiments are currently limited to mathematical reasoning, where reliable final-answer verification is possible. Extending to domains with ambiguous or delayed outcomes would require learned verifiers.
• Computation: While cheaper than manual annotation, gain estimation still requires substantial computation from student rollouts.
• Scalarization: The current method uses a simple scalar average of student gains. It does not fully exploit the distributional structure of prefix utility (e.g., policy-dependent variations), which is left for future work.