Abstract
Large language models (LLMs) struggle with multi-step reasoning, where inference-time scaling has emerged as a promising strategy for performance improvement. Verifier-guided search outperforms repeated sampling when sample size is limited by selecting and prioritizing valid reasoning paths. However, we identify a critical limitation: scaling flaws, prevalent across different models (Mistral 7B and DeepSeekMath 7B), benchmarks (GSM8K and MATH), and verifiers (outcome value models and process reward models). As sample size increases, verifier-guided search exhibits diminishing advantages and eventually underperforms repeated sampling. Our analysis attributes this to verifier failures, where imperfect verifiers misrank candidates and erroneously prune all valid paths. These issues are further exacerbated in challenging and out-of-distribution problems, restricting search effectiveness. To mitigate verifier failures, we explore reducing reliance on verifiers and conduct preliminary investigations using two simple methods. Our findings reveal fundamental limitations in verifier-guided search and suggest future directions.
Introduction
Large Language Models (LLMs) often struggle with complex, multi-step mathematical reasoning. To improve performance at inference time, two primary strategies are employed: repeated sampling (generating multiple independent solutions and selecting the best) and verifier-guided search (using a reward model to evaluate and prune partial reasoning steps).
Intuitively, guided search should be more compute-efficient by focusing resources on the most promising paths. However, this research identifies a "scaling flaw": while search-based methods excel at low sample counts, they hit a performance ceiling much earlier than simple repeated sampling. This study investigates the "bottleneck" created by imperfect verifiers and explores why search-based methods fail to scale effectively.
Methodology and Benchmarks
The researchers evaluated Step-level Beam Search using two distinct verifier types:
- Outcome-Supervised Value Models (OVMs): Estimating the probability that a partial path leads to a correct final answer.
- Process-Supervised Reward Models (PRMs): Scoring the correctness of individual reasoning steps.
Performance was benchmarked across GSM8K (grade-school math) and MATH (competition-level math), including specific "Out-of-Distribution" (OOD) splits where models were tested on problems significantly harder than their training data.
The Scaling Flaw: A Sprint vs. Marathon Paradox
The core finding is that search is a "sprint" winner but a "marathon" loser. At small sample sizes ($N=1$), guided search significantly outperforms repeated sampling. However, as $N$ increases, the performance of repeated sampling continues to climb, while search-based performance plateaus or even declines.
As shown in the figure above, the "Performance Inversion" is stark. On the MATH dataset with a DeepSeekMath 7B model, OVM-guided search is overtaken by repeated sampling at a sample size of just 4. By $N=32$, search performance is nearly 20% lower than simple sampling. Even with more granular PRMs on GSM8K, search initially leads by 20% but falls 5% behind by $N=32$.
Root Causes: Verifier Failures and the Sparsity Trap
The researchers attribute this scaling failure to "verifier failures." In approximately 80% of failed searches, the generator had actually produced a valid path, but the verifier failed to select it or erroneously pruned it.
This is particularly problematic in difficult problems where correct reasoning paths are "sparse." In a sparse solution space, a single ranking error by the verifier can prune the only viable path. Repeated sampling avoids this trap because it never prunes. Furthermore, verifiers prove to be brittle in OOD scenarios, where their reliability drops significantly, making deterministic pruning a risky strategy for real-world applications.
Mitigating Verifier Reliance
To address these flaws, the study explored two methods to reduce over-reliance on imperfect verifiers:
- Stochastic Selection: Using a softmax function instead of greedy selection to give lower-ranked (but potentially correct) paths a chance to survive. This improved selection accuracy by up to 11.2% in OOD settings.
- One-time Monte Carlo Rollout: Blending the verifier's estimate with a concrete reward signal from a single complete rollout. Interestingly, relying solely on rollouts often yielded higher gains than using the verifier alone, highlighting the prevalence of "hallucinations" in current reward models.
Conclusion and Future Directions
The scaling flaws identified here suggest that the current paradigm of deterministic pruning in guided search is fundamentally limited by verifier accuracy. Future research should focus on developing uncertainty-aware verifiers that can balance exploration and exploitation more effectively, as well as improving the robustness of reward models to out-of-distribution challenges.
Summary updated