- 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
- 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.
- 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
- 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.
- 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
- 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?
- 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?
- 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.
- 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?
- 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
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 with candidates , let be PRM estimates along candidate . Their mean is the score used for selection. As a proxy for the unobserved residual in Equation 7, we use the maximum within-trajectory PRM variation , and set , where is added for numerical stability. Here, 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:
| PRM | Spearman | 95% CI (1,000 bootstrap resamples) |
|---|---|---|
| Skywork-o1-Open-PRM-1.5B | 0.56 | [0.46, 0.66] |
| Skywork-o1-Open-PRM-7B | 0.43 | [0.32, 0.54] |
| Qwen2.5-Math-PRM-7B | 0.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, = 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 , 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 .
| Method | AIME'24 | AIME'25 |
|---|---|---|
| DBS (=0.1) | 50.0 | 43.3 |
| DBS (=0.5) | 56.7 | 46.7 |
| DPP (=0.1) | 63.3 | 50.0 |
| DPP (=0.5) | 63.3 | 46.7 |
| BoN-PRM | 56.7 | 33.3 |
| SBS | 66.7 | 43.3 |
| Maximin | 73.3 | 50.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 , the randomized-greedy start is a -approximation in expectation, and (b) the swap stage does not decrease . We explain how each condition relates to the implementation. We note that for fixed , our objective function is submodular and in general non-monotone for any scores s and any (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 with , Buchbinder et al. (2014) show that it is a constant-factor approximation in expectation; since we use , this gives the factor . 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 . The shift is used only in the analysis. The implementation does not compute , 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 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.
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. """