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:
- Repeated sampling: Independently sampling multiple complete solutions and hoping at least one is correct.
- 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:
- Stochastic selection: Sampling candidate steps via a softmax distribution over verifier scores instead of greedily picking top-$b$ paths.
- 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