From Correctness to Utility: Gain-Based Prefix Evaluation for LLM Reasoning
For LLM reasoning tasks, this work provides a more effective prefix-level supervision signal that outperforms existing process reward models in scenarios with large search spaces or sparse rewards.
The authors propose a Prefix Utility Model (PUM) that evaluates reasoning prefixes by their effect on increasing the probability of successful completion (prefix gain), rather than local step correctness. PUM improves performance in Best-of-N selection, beam search, and reinforcement learning for mathematical reasoning, especially with large candidate pools and sparse rewards.
Reasoning prefixes shape the future trajectory of LLM problem solving, yet existing process reward models usually evaluate them through local step correctness. We argue that correctness is a useful but indirect proxy for the effect we ultimately care about: whether a prefix increases the probability of successful completion. We define this effect as prefix gain, the solve-rate improvement induced by conditioning lightweight student model group on a prefix, and use it to train a Prefix Utility Model (PUM) with a simple pairwise ranking objective. PUM learns outcome-grounded prefix utility and can score both complete trajectories and partial reasoning prefixes. Across Best-of-$N$ selection, beam search, and reinforcement learning on mathematical reasoning, PUM provides a strong prefix-level supervision signal, especially when candidate pools are large, search budgets increase, or rule-based rewards are sparse. We release all data, models, and code at https://zhiqix.github.io/pum-project-page.