Scaling Flaws of Verifier-guided Search in Mathematical Reasoning

Fei Yu, Yingru Li, Benyou Wang

TL;DR

While verifier-guided search (using PRMs or OVMs) initially boosts reasoning performance over repeated sampling when sample budgets are small, it scales poorly. As sample size grows, search hits severe diminishing returns and is ultimately overtaken by simple repeated sampling because imperfect verifiers systematically misrank and prune away valid reasoning paths.

What Problem Does This Paper Address?

Inference-time scaling—allocating more compute during test-time generation—is one of the most promising frontiers in LLM mathematical reasoning. Typically, teams scale inference in one of two ways:

  1. Repeated sampling: Independently sampling multiple complete solutions and hoping at least one is correct.
  2. Verifier-guided search: Using step-level search (e.g., beam search) guided by an external verifier (such as a Process Reward Model or Outcome Value Model) to prune dead ends early and steer compute toward promising trajectories.

While search is widely assumed to be strictly more compute-efficient than brute-force sampling, the authors reveal a critical bottleneck: scaling flaws. As sample size or candidate budgets increase, verifier-guided search improvements stagnate, and simple repeated sampling ends up achieving higher coverage (the fraction of problems where at least one generated solution is correct).

Methods

The authors systematically analyze step-level beam search across two standard verifier paradigms:

  • Outcome Value Models (OVMs): Predict the probability of arriving at a correct final answer given the current partial path.
  • Process Reward Models (PRMs): Step-level models that score the correctness of each individual reasoning step.

To understand why search degrades, they dissect search failures into:

  • Generation failures: No valid continuation was produced at a given step.
  • Selection failures ("verifier failures"): Valid continuations existed, but the verifier scored them too low, causing beam search to prune all valid paths. Valid paths were identified via Monte Carlo rollouts (4 rollouts per candidate on GSM8K; 16 on MATH).

They also evaluate two simple inference-time remedies to reduce over-reliance on brittle verifier scores:

  1. Stochastic selection: Sampling candidate steps via a softmax distribution over verifier scores instead of greedily picking top-$b$ paths.
  2. One-time Monte Carlo rollout: Blending the verifier score with the empirical reward of completing the partial path to the end: $\lambda r + (1 - \lambda) v$.

Datasets

The authors evaluate generators (DeepSeekMath 7B and Mistral 7B) on standard and out-of-distribution (OOD) benchmarks:

  • GSM8K: Grade school math benchmark (in-distribution split).
  • MATH / MATH500: Challenging competition-level math across 5 difficulty levels.
  • OOD-L4 & OOD-L5: Custom difficulty splits where models are trained on easier levels (e.g., Levels 1–4) and tested on harder, unseen levels (Level 4 or Level 5) in MATH500 to simulate real-world distributional shifts.
  • Math-Shepherd: Used for PRM training data.

Key Insights and Ideas

  • Selection, not generation, is the culprit: 77% to 88% of search failures are selection failures. The generator frequently produces correct reasoning branches, but the verifier misranks them below flawed candidates, prematurely killing all viable solution trajectories.
  • Verifiers do not scale with candidate size: When candidate pool size ($K$) scales, the probability of generating at least one valid path rises (demonstrated by an oracle selector), but real verifiers fail to identify them. Scaling $K$ often plateaus or degrades search performance.
  • Sparsity magnifies failure: In harder or OOD problems, valid reasoning steps are sparse. The authors show that the failure rate of verifiers increases monotonically as valid path sparsity increases. Paradoxically, search fails hardest on the exact problems where it is needed most.
  • Ignoring the verifier can actually help: In Monte Carlo rollouts, the highest candidate selection accuracy was achieved at $\lambda = 1.0$—that is, relying entirely on rollout completion and completely discarding the verifier’s score.

Key Results

  • Repeated sampling overtakes search: While verifier-guided search holds an initial lead at small sample sizes (e.g., at sample size $b=1$, DeepSeekMath PRM search beats sampling by +20% on GSM8K and +13.5% on MATH L4), its gains stall. By a sample size of 32:
  • OVM search underperforms repeated sampling by ~10% on GSM8K and ~20% on MATH.
  • PRM search underperforms repeated sampling by ~5% on GSM8K and up to ~44% on harder MATH levels.
  • Worse on hard and OOD tasks: At sample size 32, OVM search trails repeated sampling by -3.1% on MATH Level 1, worsening monotonically to -23.9% on Level 5 and -32.8% on OOD-L5.
  • Mitigations yield immediate gains: Stochastic selection with temperature scaling improves step-selection accuracy across the board, gaining up to +11.2% on OOD-L4 and OOD-L5.

Limitations and Future Work

  • Metric scope: The paper focuses on coverage (pass@$k$, whether at least one candidate is correct) rather than single-answer precision, though coverage represents the theoretical ceiling for verification.
  • Model and verifier scale: The experiments evaluate 7B-parameter models; the authors did not test whether massive verifier models (e.g., 70B+) or substantially larger training datasets alleviate these scaling flaws.
  • Future directions: Promising avenues include dynamically measuring verifier uncertainty to modulate search trust and hybrid search schemes that balance exploitation with stochastic exploration.

Summary updated

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.
BibTeX
@inproceedings{yu2025scaling,
  author = {Fei Yu and Yingru Li and Benyou Wang},
  title = {{Scaling Flaws of Verifier-guided Search in Mathematical Reasoning}},
  booktitle = {LLM Reason and Plan @ ICLR},
  year = {2025},
  url = {https://openreview.net/forum?id=9vFB91wspX},
}

Loading related content...

Figure