acceptodds
Under review as a conference paper at ICLR 2027

Mitigating Over-Optimization in PRM-Guided Search in Mathematical Reasoning by Optimizing the Guide

Abstract

Process reward models (PRMs) provide dense step-level guidance for search-based reasoning, enabling inference-time compute to be allocated toward promising partial solutions. However, recent evidence suggests that PRM-guided search can over-optimize imperfect process rewards, pruning viable trajectories while expanding spurious ones. In this work, we theoretically show that directly leveraging PRM score is vulnerable to verifier noise through an extreme-value effect: non-viable prefixes become more likely to receive spuriously high scores as reasoning depth increase. Therefore, we formulate the PRM-guided search as a robust optimization problem over plausible reward perturbations, termed maximin PRM-guided search, leading to a training-free robust process supervision method that preserves promising alternatives when step-level scores are noisy. Maximin PRM-guided search mitigates this failure mode by reducing sensitivity to over-optimized PRM outliers. Without fine-tuning or online adaptation, maximin search consistently improves the PRM-guided search by 17–35% on average, outperforming outcome- and step-level baselines in 14 out of 16 settings.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Guided decoding, reasoning model, test-time scaling, process reward model

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_FAZUOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper examines over-optimization in PRM-guided search for mathematical reasoning: when verifier scores are imperfect, repeatedly retaining high-scoring reasoning prefixes may prematurely prune viable prefixes. The authors theoretically analyze this phenomenon and propose maximin PRM-guided search, which considers similarities between candidate prefixes alongside their PRM scores to reduce sensitivity to correlated verifier errors. The method is training-free and can be incorporated into existing PRM-guided search procedures. Experiments cover two generators, four mathematical reasoning benchmarks, and two inference budgets, with additional noise-injection and ablation studies. Table 1 reports best or tied-best performance in most evaluated settings.

Critical strengths
  1. The paper addresses a practically relevant problem with a clear theoretical motivation. It shifts attention from improving the verifier itself to making better search decisions under verifier uncertainty. This perspective is useful, and the training-free design gives the method practical potential.
  2. The experiments show promising performance improvements. The method achieves improvements with both generators, particularly on MATH-500. For example, it improves over step-level beam search (SBS) by 4.4 percentage points with Qwen2.5-Math-1.5B at N=16 and by 3.8 percentage points with Phi-3.5-mini-instruct at N=64. These results support the paper's central intuition that better pruning rules can make more effective use of an existing PRM.
Critical weaknesses
  1. The connection between the empirical gains and the robustness interpretation would benefit from more direct validation. The theoretical analysis provides a reasonable foundation for the method. However, evidence that the uncertainty proxy used in practice reflects actual verifier error remains limited. The paper also does not directly compare against diversity-promoting pruning methods using the same representations, inference budgets, and comparable hyperparameter-tuning conditions. It therefore remains unclear how much additional benefit the regularizer derived from the verifier-error model and the adaptive RKHS radius provide beyond general diversity regularization.
  2. Some experimental results need to be reconciled, and the reliability of the reported gains would benefit from further clarification. For example, Section 6.1 reports an improvement from 6.7% to 13.3% for Phi-3.5-mini-instruct on AIME'24 at N=64, whereas the corresponding entries in Table 1 are 7.8% and 8.9%. Section 6.2 also gives both 76% and 71% as the apparent noise-free SBS accuracy. In addition, the aggregation used to obtain the reported average improvement of 17–35% is not sufficiently clear. Although Appendix F reports standard deviations, the small size of the AIME benchmarks and the modest differences in some settings make paired statistical analysis particularly useful. Reconciling these results and clarifying their uncertainty would strengthen confidence in the findings. Since these points concern the main empirical conclusions, they materially affect my current assessment.
Questions for authors
  1. Could the authors reconcile the numerical differences between Table 1 and the main text and explain precisely how the average improvement of 17–35% is calculated? For settings with small performance differences, could per-seed results or paired confidence intervals be provided?
  2. The paper states that, when reference step rewards are unavailable, the maximum within-trajectory variation in estimated step rewards is used as a proxy. Could the authors provide the complete formulas for this proxy and the resulting RKHS radius, including how the proxy corresponds to the residual vector in Eq. (7)? On an offline subset with reference scores, is there evidence that the proxy and kernel similarity respectively capture verifier-error magnitude and error correlations?
  3. Under the same representations, inference budgets, and hyperparameter-tuning conditions, does the method retain an advantage over diversity-promoting pruning or randomized SBS? Such a comparison would help establish the contribution of the robustness formulation.
  4. Could the authors clarify how the theoretical approximation guarantee applies to the implemented optimization procedure, particularly how the assumptions required by randomized greedy are satisfied?
  5. Does the performance advantage remain when budgets are matched by actual generated tokens, PRM computation, or total runtime? Which computational steps are included in the reported runtime overhead?
3 comments

Thank you for the thorough and constructive review. We are glad that you found the shift from improving the verifier to making better search decisions under verifier uncertainty useful. We also appreciate your careful reading of the empirical section (text and Table 1 mismatch), and have corrected them and respond to each of your questions below. We respond to each question below and have uploaded a revised manuscript, with changes marked in magenta.

Q1: Numerical differences between Table 1 and the main text

Q: Could the authors reconcile the numerical differences between Table 1 and the main text and explain precisely how the average improvement of 17–35% is calculated? For settings with small performance differences, could per-seed results or paired confidence intervals be provided?

A: Thanks for raising an unclear presentation of the improvements. The values are intended to be provided by averaging improvements over datasets separately for each generator–budget pair. However, on aggregation, recomputing “17–35%” by the stated procedure from Table 1 gives 28/3/26/9%, and we realized that the cited numbers in the main body are from the previous version of the paper. We have corrected all numbers in the mainbody, and changed this relative, average scaling into the direct percentage improvements in the paper. We have uploaded a revised manuscript, with changes marked in magenta.

Abstract """ Without fine-tuning or online adaptation, maximin search matches or improves step-level beam search in 15 of 16 settings, by up to 4.4 and 7.8 percentage points on MATH-500 and AIME'24, respectively, and attains the best or tied-best result among outcome- and step-level baselines in 14 of 16 settings. """

Introduction""" 3) we derive a training-free plug-in algorithm that matches or improves step-level beam search in 15 of 16 evaluated settings, by up to 4.4 and 7.8 percentage points on MATH-500 and AIME'24, respectively, and attains the best or tied-best result in 14 of 16 settings. """

Section 6.1""" For instance, with Qwen2.5-Math-1.5B, SBS is below BoN-MBR on GSM8K at N = 64 (87.5 vs. 88.8), on MATH-500 at N = 16 (72.4 vs. 75.2), and on AIME'24 at N = 16 (8.9 vs. 14.4). """

Section 6.1""" Maximin achieves the best or tied-best result in 14 of the 16 generator–dataset–budget blocks. Relative to SBS, it is better in 13 blocks, tied in 2, and 0.2 points lower in 1 (GSM8K with Phi-3.5-mini-instruct at N = 64), with only a 0.27% increase in runtime at N = 16. The largest gains are on MATH-500 and AIME'24: with Qwen2.5-Math-1.5B at N = 16, maximin improves over SBS from 72.4% to 76.8% on MATH-500 and from 8.9% to 16.7% on AIME'24, and with Phi-3.5-mini-instruct at N = 64, from 66.4% to 70.2% on MATH-500. """

Q2: Uncertainty radius proxy computation and its correlation to the true residual

Q: The paper states that, when reference step rewards are unavailable, the maximum within-trajectory variation in estimated step rewards is used as a proxy. Could the authors provide the complete formulas for this proxy and the resulting RKHS radius, including how the proxy corresponds to the residual vector in Eq. (7)? On an offline subset with reference scores, is there evidence that the proxy and kernel similarity respectively capture verifier-error magnitude and error correlations?

Computation of uncertainty radius proxy. At a pruning step tt with candidates τ1,⋯ ,τN\tau_1, \cdots, \tau_N, let si,1,⋯ ,si,ts_{i,1}, \cdots, s_{i,t} be PRM estimates along candidate ii. Their mean is the score sis_i used for selection. As a proxy for the unobserved residual νi\nu_i in Equation 7, we use the maximum within-trajectory PRM variation ν~i=max⁡a,b≤t(si,a−si,b)\tilde{\nu}_i = \max_{a,b \leq t} (s_{i,a} - s_{i,b}), and set B~=ν~i(K+10−6)−1ν~i\tilde{B} = \sqrt{\tilde{\nu}_i (K + 10^{-6})^{-1} \tilde{\nu}_i}, where 10−610^{-6} is added for numerical stability. Here, B~\tilde{B} is recomputed at every pruning step from the current candidates; Figure 3 shows how it varies across problems and depth.

Correlation with reference error. We cannot compute this on the search-time prefixes, because they have no reference step rewards. We therefore ran the analysis on the MATH split of ProcessBench, which provides human-annotated step labels. Within each trajectory we standardize the PRM scores and the step labels separately, and compare the range of the standardized scores (disparity) with their mean absolute difference from the standardized labels (error). Across 372 trajectories, the two are positively rank-correlated for all three PRMs we tested:

PRMSpearman ρ\rho95% CI (1,000 bootstrap resamples)
Skywork-o1-Open-PRM-1.5B0.56[0.46, 0.66]
Skywork-o1-Open-PRM-7B0.43[0.32, 0.54]
Qwen2.5-Math-PRM-7B0.72[0.64, 0.78]

This supports using the score range as a relative indicator of how unreliable the PRM is on a trajectory. We appreciate the reviewer’s question that clarifies and justifies our choice of PRM error proxy, and we added the above discussions in Section 5.1 "Empirical choice of the RKHS radius B" and Appendix B.4 “Disparity-PRM error analysis.”

Q3: Comparison with generic diversity promoting methods

Q: Under the same representations, inference budgets, and hyperparameter-tuning conditions, does the method retain an advantage over diversity-promoting pruning or randomized SBS? Such a comparison would help establish the contribution of the robustness formulation.

A: We added two step-level diversity baselines, diverse beam search (DBS) and DPP-based selection, each with two different regularization coefficients. They use the same generator and the same inference budget (N=8) as Maximin. As shown in Table R1 below, diversity alone does not reproduce the gain of maximin. Specifically, on AIME’24, every DBS and DPP configuration is even below SBS (50.0–63.3% vs. 66.7%), while maximin is above it (73.3%). Also, on AIME’25, the best diversity configuration (DPP, λ\lambda = 0.1) only matches maximin (50.0%). Importantly, the diversity baselines change by up to 6.7 points with the choice of the regularization coefficient λ\lambda, whereas maximin uses a single configuration without tuning. An MBR-style baseline (BoN-MBR) is already in Table 1. Finally, on the broader scope mentioned in W1, the new setting adds a stronger generator and a second PRM. Evaluation beyond mathematical reasoning is listed as a limitation in the new Conclusion.

Table R1. Qwen3-4B-Instruct-2507, RLHFlow-Llama3.1-8B-PRM-Deepseek-Data, N = 8. Values in parentheses are the diversity regularization coefficient λ\lambda.

MethodAIME'24AIME'25
DBS (λ\lambda=0.1)50.043.3
DBS (λ\lambda=0.5)56.746.7
DPP (λ\lambda=0.1)63.350.0
DPP (λ\lambda=0.5)63.346.7
BoN-PRM56.733.3
SBS66.743.3
Maximin73.350.0

On Randomized SBS We are not aware of a published method by this name; SBS (Chen et al., 2024) is deterministic top-m selection. The closest control in the paper is §6.2 (Qwen2.5-Math-1.5B, MATH-500 subset), where SBS selects on Gaussian-perturbed PRM scores. Perturbation improves SBS only at the smallest level (+2.8% relative at ε = 0.1) and degrades it at larger levels (down to −16.9%). This is still lower than Maximin's performance.

Q4: Theoretical approximation guarantee of optimization procedure

Q: Could the authors clarify how the theoretical approximation guarantee applies to the implemented optimization procedure, particularly how the assumptions required by randomized greedy are satisfied?

A: Theorem 3 is stated for a generic inner solver. It assumes that (a) for each grid point η\eta, the randomized-greedy start is a ρ\rho-approximation in expectation, and (b) the swap stage does not decrease JηJ_\eta. We explain how each condition relates to the implementation. We note that for fixed η\eta, our objective function is submodular and in general non-monotone for any scores s and any η>0\eta >0 (cf. Section 5).

Condition (a) The inner solver is the Random Greedy algorithm of Buchbinder et al. (2014): m rounds, each adding an element drawn uniformly from the m largest marginal gains (Appendix B.4), so it returns exactly m elements. For nonnegative submodular objectives under the exact cardinality constraint ∣S∣=m|S|=m with m≤N/2m \le N/2, Buchbinder et al. (2014) show that it is a constant-factor approximation in expectation; since we use m=N/4m=N/4, this gives the factor ρ\rho. However, nonnegativity is not guaranteed for arbitrary scores, which is why Theorem 3 states it as a condition, in the sentence immediately before the theorem. Corollary 3 (Appendix D.3) gives the general statement without this condition: the surrogate is shifted by $ L_\eta = \min_{|S| \le m} J_\eta (1_S)$, and the bound acquires the additive term (1−ρ)LH(1 - \rho)L_H. The shift is used only in the analysis. The implementation does not compute LηL_\eta, since subtracting a constant changes neither the marginal gains nor the selected set.

Condition (b) The 1-swap refinement accepts a swap only if its gain in Eq. (11) is strictly positive, so Jη(qη†)≥Jη(qηrg)J_\eta(q_\eta^\dagger)\ge J_\eta(q_\eta^{\rm rg}) holds for every realization. Therefore, condition (b)n holds by construction. To make how theoretical approximation guarantee applies to the implemented optimization procedure clearer to the readers, we have added the above discussion under “Remark (Applicability to the implemented procedure).” after Theorem 3.

Q5: SBS vs Maximin under the same computational budget

Q: Does the performance advantage remain when budgets are matched by actual generated tokens, PRM computation, or total runtime? Which computational steps are included in the reported runtime overhead?

A: SBS and Maximin run the same search loop and differ only in which m of the N candidates are retained. At every pruning step both expand m parents with 4 continuations each, under the same limits (128 tokens per step, depth 30, 2,048 tokens per trajectory; Appendix F), and both score the same number of candidates with the PRM. Generator calls and PRM evaluations per step are therefore identical by construction. Realized token counts are not forced to be equal, because the two methods retain different prefixes, which can terminate at different depths.

Maximin adds only the CPU job for the selection step: kernel construction, the radius, and Algorithm 1 (grid search, randomized greedy, swap refinement). All three are included in the reported overhead of 0.27% at N=16. Per pruning step they take 6.2 ms at N=16 and 91.9 ms at N=64; the component breakdown and the timing protocol are in our response to Reviewer TvEp (Q2) and in the new "Runtime overhead" paragraph of Appendix F.

Reviewer_TvEpOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper argues that PRM-guided step-level search can over-optimize noisy or systematically biased process scores and prune prefixes that could still lead to successful reasoning. Section 4 formalizes a greedy failure mode: maximization over noisy process scores can select non-viable prefixes even when viable continuations exist, with risk depending on verifier uncertainty, generator coverage, search width, and depth. Section 5 proposes a training-free robust selection objective that adds a kernel-based uncertainty penalty to the nominal PRM score, using an RBF kernel over PRM trajectory representations and an RKHS smoothness model to capture correlated verifier errors across similar prefixes. The paper derives a worst-case aggregate error bound (Theorem 2), reformulates the resulting cardinality-constrained objective into a family of submodular problems, and solves it with randomized greedy plus one-swap local search (Algorithm 1), with an end-to-end approximation guarantee (Theorem 3). Section 6 evaluates on GSM8K, MATH-500, AIME’24, and AIME’25 with two generators and Skywork o1-PRM, reporting best or tied-best results in 14 of 16 generator-dataset-budget settings and roughly 17–35% average improvement over SBS, plus better robustness to injected reward noise.

Critical strengths
  • The paper gives a concrete and interpretable characterization of over-optimization in PRM-guided search, not just an empirical observation. Theorem 1 in Section 4 separates the viable-frontier term from the non-viable-outlier term and clearly explains how verifier noise, candidate coverage, and search width interact.
  • The robust objective is theoretically motivated rather than an ad hoc diversity heuristic. Theorem 2 in Section 5.1 provides a worst-case aggregate verifier-error bound under RKHS smoothness, and the kernel penalty has a clear uncertainty interpretation.
  • The method is training-free and designed as a plug-in for existing PRM-guided search. The variational reformulation and Algorithm 1 in Section 5.2 are practical, and Theorem 3 gives an approximation guarantee relative to the robust objective.
  • The ablation study in Section 6.3 supports the main design choices: the local swap refinement, the adaptive uncertainty radius, and the angular/RBF kernel geometry all matter. The injected-noise experiment in Section 6.2 and Figure 2 supports the robustness claim.
Critical weaknesses
  • The empirical scope is narrow and misses a key baseline. Section 6 and Table 1 cover only mathematical reasoning, two relatively small generators, and one PRM. Appendix E.2 discusses MBR, diverse beam search, and DPP-style selection, but the main experiments do not include a step-level diversity/DPP or robust-selection baseline under the same PRM and budget. Therefore the central claim that the gains come from robustness to verifier misspecification, rather than generic diversity regularization, is not empirically isolated.
  • The reported runtime overhead needs support. Section 6.1 and Section 6.3 report only about 0.27% runtime overhead at a budget of 16, despite the algorithm involving a grid search, randomized greedy initialization, and swap refinement at every pruning step. Without a timing protocol, hardware details, and a breakdown by component, this number is difficult to assess and potentially misleading.
Questions for authors
  • How exactly is the uncertainty radius computed in the main experiments? Is any oracle or calibration data used, or only the proxy described in Appendix F? Can you report the correlation between the proxy and true residuals on a small calibration set?
  • What is the wall-clock overhead per sample and per pruning step, including kernel construction, grid search, randomized greedy, and swap refinement? Why is the reported overhead only about 0.27%?
  • Can you add a step-level diversity/DPP or MBR-style selection baseline under the same PRM and inference budget, to test whether the gains come from robustness rather than generic diversity?
2 comments

Thank you for the careful review, and for the positive assessment of the characterization of over-optimization (Theorem 1) and of the robust objective and its guarantee (Theorems 2–3). We respond to each question below and have uploaded a revised manuscript, with changes marked in magenta.

Q1: Uncertainty radius proxy computation and its correlation to the true residual

Q: How exactly is the uncertainty radius computed in the main experiments? Is any oracle or calibration data used, or only the proxy described in Appendix F? Can you report the correlation between the proxy and true residuals on a small calibration set?

A: Only the proxy is used. No oracle rewards and no calibration data are used in any experiment in the paper. The proxy is described in Section 5.1 and Appendix B.3; we agree that the description was too brief, and the paper now gives the formula, which is detailed below.

Computation of uncertainty radius proxy. At a pruning step tt with candidates τ1,⋯ ,τN\tau_1, \cdots, \tau_N, let si,1,⋯ ,si,ts_{i,1}, \cdots, s_{i,t} be PRM estimates along candidate ii. Their mean is the score sis_i used for selection. As a proxy for the unobserved residual νi\nu_i in Equation 7, we use the maximum within-trajectory PRM variation ν~i=max⁡a,b≤t(si,a−si,b)\tilde{\nu}_i = \max_{a,b \leq t} (s_{i,a} - s_{i,b}), and set B~=ν~i(K+10−6)−1ν~i\tilde{B} = \sqrt{\tilde{\nu}_i (K + 10^{-6})^{-1} \tilde{\nu}_i}, where 10−610^{-6} is added for numerical stability. Here, B~\tilde{B} is recomputed at every pruning step from the current candidates; Figure 3 shows how it varies across problems and depth.

Correlation with reference error. We cannot compute this on the search-time prefixes, because they have no reference step rewards. We therefore ran the analysis on the MATH split of ProcessBench, which provides human-annotated step labels. Within each trajectory we standardize the PRM scores and the step labels separately, and compare the range of the standardized scores (disparity) with their mean absolute difference from the standardized labels (error). Across 372 trajectories, the two are positively rank-correlated for all three PRMs we tested:

PRMSpearman ρ\rho95% CI (1,000 bootstrap resamples)
Skywork-o1-Open-PRM-1.5B0.56[0.46, 0.66]
Skywork-o1-Open-PRM-7B0.43[0.32, 0.54]
Qwen2.5-Math-PRM-7B0.72[0.64, 0.78]

This supports using the score range as a relative indicator of how unreliable the PRM is on a trajectory. We appreciate the reviewer’s question that clarifies and justifies our choice of PRM error proxy, and we added the above discussions in Section 5.1 "Empirical choice of the RKHS radius B" and Appendix B.4 “Disparity-PRM error analysis.”

Q2: Wall-clock overhead of Maximin

Q: What is the wall-clock overhead per sample and per pruning step, including kernel construction, grid search, randomized greedy, and swap refinement? Why is the reported overhead only about 0.27%?

A: Maximin changes only the selection step. The trajectory representations are the PRM's last hidden states, which are already computed when the PRM scores the candidates, so selection needs no additional neural-network forward pass. Per pruning step, with N candidates, representation dimension D (1536 for Skywork-o1-Open-PRM-Qwen-2.5-1.5B) and beam size m = N/4, the overheads are 1) kernel construction,O(N^2 D); 2) the radius B~\tilde{B}, one N x N linear solve, O(N^3); 3) Algorithm 1: for each grid point, randomized greedy in O(mN) and at most 30 passes of 1-swap refinement at O(mN) per pass. When ξ=0.05\xi=0.05, the grid has 16 points for N=16 and 30 points for N=64.

As a result, for AMD Ryzen Threadripper 7960X (24 cores), single thread, Python 3.11.13, NumPy 2.2.6, float32, D = 1536, mean over 30 repetitions after 3 warm-up runs, we get

Nkernel (ms)radius (ms)Algorithm 1 (ms)total (ms)
160.0680.0196.1196.206
640.2680.04291.55991.869

This overhead is so small because, in the same pruning step, the generator produces up to 128 tokens for each of the N candidates and the PRM runs a forward pass over them. Against this, 6.2 ms of CPU selection gives the reported 0.27% increase in end-to-end wall-clock over SBS at N=16. To make these clearer in the paper, we have added the above discussion in Appendix F “Runtime overhead .”

Q3: Comparison with generic diversity promoting methods

Q: Can you add a step-level diversity/DPP or MBR-style selection baseline under the same PRM and inference budget, to test whether the gains come from robustness rather than generic diversity?

A: We added two step-level diversity baselines, diverse beam search (DBS) and DPP-based selection, each with two different regularization coefficients. They use the same generator and the same inference budget (N=8) as Maximin. As shown in Table R1 below, diversity alone does not reproduce the gain of maximin. Specifically, on AIME’24, every DBS and DPP configuration is even below SBS (50.0–63.3% vs. 66.7%), while maximin is above it (73.3%). Also, on AIME’25, the best diversity configuration (DPP, λ\lambda = 0.1) only matches maximin (50.0%). Importantly, the diversity baselines change by up to 6.7 points with the choice of the regularization coefficient λ\lambda, whereas maximin uses a single configuration without tuning. An MBR-style baseline (BoN-MBR) is already in Table 1. Finally, on the broader scope mentioned in W1, the new setting adds a stronger generator and a second PRM. Evaluation beyond mathematical reasoning is listed as a limitation in the new Conclusion.

Table R1. Qwen3-4B-Instruct-2507, RLHFlow-Llama3.1-8B-PRM-Deepseek-Data, N = 8. Values in parentheses are the diversity regularization coefficient λ\lambda.

MethodAIME'24AIME'25
DBS (λ\lambda=0.1)50.043.3
DBS (λ\lambda=0.5)56.746.7
DPP (λ\lambda=0.1)63.350.0
DPP (λ\lambda=0.5)63.346.7
BoN-PRM56.733.3
SBS66.743.3
Maximin73.350.0
Reviewer_Ws91OpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies reward over-optimization in PRM-guided mathematical reasoning. The authors first analyze how verifier noise can lead to incorrect trajectory selection during search. They then propose Maximin PRM-guided Search, a training-free method that uses RKHS-based robust optimization and kernel regularization to improve trajectory selection. Experiments on four mathematical reasoning benchmarks demonstrate improvements over several existing search baselines.

Critical strengths
  1. Meaningful problem and theoretical contribution.The paper addresses reward over-optimization in PRM-guided reasoning and provides a principled RKHS-based robust optimization framework.

  2. Practical method and promising results. The proposed method requires no additional training and achieves improvements over existing search baselines on several mathematical reasoning benchmarks.

Critical weaknesses
  1. Insufficient experimental validation. The paper presents extensive theoretical analysis, but the experiments are relatively limited.

  2. Lack of stronger model evaluations. The experiments only involve Qwen2.5-Math-1.5B and Phi-3.5-mini-instruct with a single PRM. Without evaluations on stronger reasoning models and different PRMs, the generalizability and practical significance of the proposed method remain unclear.

  3. Insufficient adherence to academic writing conventions. The manuscript lacks a dedicated conclusion section and does not adequately summarize its main findings and implications. Despite its extensive theoretical development, the overall paper structure and presentation remain incomplete.

Questions for authors
  1. Can the authors provide additional experiments to validate the key theoretical assumptions and demonstrate how the proposed method reduces incorrect pruning?

  2. Why are the experiments limited to relatively small language models and a single PRM? Can the authors provide results on stronger reasoning models and different PRMs?

  3. Could the authors clarify the main findings and practical implications of this work, given the absence of a dedicated conclusion section?

2 comments

Thank you for the time and effort you spent reviewing our paper. We appreciate that you found the problem of reward over-optimization in PRM-guided reasoning meaningful, the RKHS-based robust optimization framework principled, and the training-free method practical.

We have carefully considered your concerns about the experimental scope and the paper structure, and we respond to each of them below. In brief: (i) we add experiments with a stronger generator (Qwen3-4B-Instruct-2507) and a different PRM, where maximin remains the best or tied-best method on AIME’24 and AIME’25; (ii) we validate the radius proxy, the only heuristic step not covered by the theory, on ProcessBench, and point to the existing analyses of incorrect pruning (§6.2 and Theorem 5); (iii) we add a dedicated Conclusion. We have uploaded a revised manuscript, with changes marked in magenta.

We hope the clarifications and additional experiments below address your concerns, and we would be grateful if you would take them into account in your final assessment.

W1, W2, Q2: Stronger reasoning models and different PRMs

Q: Why are the experiments limited to relatively small language models and a single PRM?

A: A selection rule can only make a difference when the candidate set contains both viable and non-viable prefixes. For this reason, Section 6 (“Base models and configuration”) chose generators “weak enough that step-level pruning decisions are non-degenerate”. Qwen2.5-Math-1.5B already reaches 89.3% on GSM8K and 78.8% on MATH-500 (Table 1), which leaves little room for differences between selection rules. AIME is far from saturated, so we use it for the stronger generator in the following new experiments.

Q: Can the authors provide results on stronger reasoning models and different PRMs?

A: We added experiments with a stronger generator, Qwen3-4B-Instruct-2507, and a different PRM, RLHFlow-Llama3.1-8B-PRM-Deepseek-Data, on AIME’24 and AIME’25 (N = 8; Table R1, added to Section 6.1). Maximin achieves the best accuracy on AIME’24 (73.3% vs. 66.7% for SBS) and ties the best on AIME’25 (50.0% vs. 43.3% for SBS). The improvement over SBS therefore carries over to a stronger generator and a different PRM.

Table R1. Qwen3-4B-Instruct-2507, RLHFlow-Llama3.1-8B-PRM-Deepseek-Data, N = 8. Values in parentheses are the diversity regularization coefficient λ\lambda.

MethodAIME'24AIME'25
DBS (λ\lambda=0.1)50.043.3
DBS (λ\lambda=0.5)56.746.7
DPP (λ\lambda=0.1)63.350.0
DPP (λ\lambda=0.5)63.346.7
BoN-PRM56.733.3
SBS66.743.3
Maximin73.350.0

Q1: Additional experiments to validate the key theoretical assumptions

Q: Can the authors provide additional experiments to validate the key theoretical assumptions and demonstrate how the proposed method reduces incorrect pruning?

A: We have revisited all assumptions in the paper. Assumption 1 (Gaussian noise) and RKHS smoothness are modeling assumptions. The conditions of Theorems 3 and 4 are technical and hold by construction of the sampler and the solver (cf. newly added discussion under “Remark (Applicability to the implemented procedure).” after Theorem 3.). Beyond these, two points can be checked empirically: (1) whether the radius proxy reflects verifier error, and (2) whether maximin avoids incorrect pruning when the verifier is wrong. We address them as follows.

(1) Radius proxy. We added an analysis on ProcessBench. For three PRMs, trajectories with a larger score range have larger error against the human step labels (Spearman ρ\rho = 0.44–0.72). Please refer to Appendix B.4 for detailed discussions about the setting.

(2) Incorrect pruning. In Section 6.2 (Figure 2), we inject Gaussian noise into the PRM scores, which reproduces the failure mode of Theorem 1. At ϵ\epsilon = 1.0 and 3.0, SBS loses 12.7% and 16.9% of its accuracy (relative), while maximin loses at most 1.4% and 5.4%. Theorem 5 (Appendix D.2) gives the formal condition under which maximin keeps a viable prefix that SBS prunes. We note that in original manuscript, the reference to it in Section 5.1 was broken, and we have fixed it and added the following sentence: “””A formal clustered-failure condition under which the robust selector preserves a viable alternative discarded by standard PRM beam selection is given in Theorem 5 (Appendix D.2).“””

Q3: Main findings and implications

Q: Could the authors clarify the main findings and practical implications of this work, given the absence of a dedicated conclusion section?

A: As per Reviewer Ws91’s suggestion, we have added the following dedicated Conclusion with the standard structure that includes summary, implications, limitations, future work.

“”” We studied the vulnerability of PRM-guided search to over-optimization of imperfect step-level reward estimates. Our analyses identify an extreme-value failure mode in which noisy PRM scores can cause search to favor non-viable prefixes as reasoning depth increases, thereby pruning promising trajectories and wasting inference-time compute. To address this, we formulated process supervision as robust optimization under plausible reward perturbations and derived a training-free robust selection procedure for PRM-guided decoding. Empirically, this approach improves guided search without additional verifier training or test-time adaptation.

The practical implication of our work is that raw PRM scores should not be treated as ground truth when guiding search. That is, scaling inference-time reasoning in PRM-guided search requires selection rules that stay reliable when the evaluator is uncertain, not only stronger evaluators. Our work has three main limitations. The theoretical analysis assumes Gaussian noise in Section 4 and RKHS-smooth structured error in Section 5; the uncertainty radius is set by a heuristic proxy rather than a consistent estimator; and the evaluation covers mathematical reasoning with 3 generators and 2 PRMs. Future directions include multi-turn agentic settings (Chae et al., 2025, Li et al., 2026) and self-generated guidance or reflection (Zhou et al., 2024; Bilal et al., 2026), where evaluators are likewise imperfect and correlated across similar states. ”””

Reference

Li et al. (2026). ToolPRMBench: Evaluating and Advancing Process Reward Models for Tool-using Agents. ACL.

Chae et al. (2025). Web-shepherd: Advancing prms for reinforcing web agents. NeurIPS.

Bilal et al. (2026) Refining Over Resampling: Test-Time Self-Correction for LLM Reasoning. arXiv.

Zhou et al. (2024) Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models. ICML.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.