Prefix Utility Model Outperforms Step-Correctness Rewards for LLM Reasoning Search

Rather than scoring reasoning steps by local correctness, Prefix Utility Model (PUM) trains on prefix gain — the solve-rate improvement a prefix induces in a lightweight student model — using pairwise ranking. PUM improves Best-of-N selection, beam search, and RL on math reasoning, with gains most pronounced at large candidate pools or sparse rule-based rewards. Data and models are released.