Reasoning Is Not a Race: When Stopping Early Beats Going Deeper
Authors: Mohan Zhang
Jiaxuan Gao
Shusheng Xu
Yi Wu
Venue: NeurIPS 2025 poster ()
Keywords: Long CoT Model
LLM Reasoning
Process Reward Model
Test time Scaling
Primary area: deep_learning

Abstract: We study the use of Process Reward Models (PRMs) for guiding Long Chain-of-Thought (CoT) reasoning in large language models. Although PRMs deliver fine-grained feedback in standard tasks, PRM-guided beam search does not consistently outperform PRM-free approaches in long CoT reasoning. We trace this shortfall to a "step quality degradation''—the expected step quality shows concave behavior, yielding unimodal or monotonically declining trends. To counteract this, we propose Z-Score Guided Early Stopping (ZGES), which halts search at the detected quality peak using local PRM-reward z-scores. Across multiple math benchmarks and model scales, ZGES outperforms both standard PRM-guided beam search and the PRM-free methods. Ablation studies further highlight the advantages and robustness of ZGES’s adaptive stopping mechanism.

Reasoning Is Not a Race: When Stopping Early Beats Going Deeper
Mohan Zhang!* Jiaxuan Gao Shusheng Xu²
Yi Wult
IIS, Tsinghua University *Ant Group
2hangmohan700gmail. com, jxwuyi@gmail.cmm com
Abstract
We study the use of Process Reward Models (PRMs) for guiding Long Chain-of- Thought (CoT) reasoning in large language models. Although PRMs deliver fine- grained feedback in standard tasks, PRM-guided beam search does not consistently outperform PRM-free approaches in long CoT reasoning. We trace this shortfall a "step quality degradation" the expected step quality shows concave behavior, yielding unimodal or monotonically declining trends. To counteract this, we propose Z-Score Guided Early Stopping (ZGES), which halts search at the detected quality peak using local PRM-reward z-scores. Across multiple math benchmarks and model scales, ZGES outperforms both standard PRM-guided beam search and the PRM-free methods. Ablation studies further highlight the advantages and robustness of ZGES's adaptive stopping mechanism.
1 Introduction
Process Reward Models (PRMs) play crucial role in test-time search of reasoning tasks [ for large language models (LLMs)). Compared the Outcome Reward Models (ORMs) [2] that focus solely on the correctness of the final answer, PRMs offer finer-grained supervision by providing stepwise rewards throughout the reasoning process. By offering feedback each step, PRMs help guide the model's reasoning path toward the correct solution path. Recent works have trained PRMs through automatically annotated labels to guide LLMs in beam search or to re-rank multiple candidate outputs from the LLMs (16), resulting in improved performance compared to naive sampling.
Chain-of- Thouuhht (CoT) 7 prompting has emerged as powerful method to enhance the reasoning ability of LLMs by decomposing complex problems into intermediate steps. Building on this technique, the emergence of Long CoT LLMs capable of sustaining long- oong-horizon reasoning chains, such OpenAl o1 [8] and DeepSeek R1 [9] has sparked growing interest in long-CoT reasoning. These models demonstrate significant advances in mathematical reasoning. code synthesis, and cross-domain inference [2 Compared to short CoT, Long CoT entails more comprehensive reasoning processes, greater depth in analyzing intermediate steps, and wider exploration of logical relationships [12). However, how to effectively apply PRMs to Long CoT reasoning tasks remains unclear. Specifically, we ask:
Q1: How well does PRM guide Long CoT models during test-time search? Q2: How enhance PRMs' effectiveness in test-time search under Long CoT settings?
In this work, to answer Q1, we evaluate the performance of Long CoT models with varying parameter sizes on math benchmarks including AMC2023, AIME2024, and AIME2025, using two prevalent classes of Process Reward Models: Hard PRM and Soft PRM (see Section 2 The hard PRM treats
"qqual contribution. *Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Local Z-Scoe
Step Quality Mean
i1
Æ=-06
82
local 2-300re=-1111
aj
83
Peak
Stopping
84
Step
Step Quality Degration
Peak
Stopping
(a) Beam Search
(b) Dynamic
Figure 1: Illustration of our proposed method: Z-Score Guided Early Stopping for Beam Search (ZGES). The locally normalized z-score-which is calculated cumulatively based on the scores of all preceding and the current step-ss at the stopping point falls below À (due to step degradation), triggering early termination. The LLM policy then directly generates the remaining trajectory and final answer from the preceding step (i.e., the peak).
step good if it lead to the correct answer, while the soft PRM learns to predict the step's value under the LLM policy [B.
Our findings reveal that PRM-guided beam search does not consistently outperform PRM-free methods such as Majority @ in Long CoT reasoning. This outcome counterintuitive, as beam search, guided by PRMs, is expected to explore and select intermediate reasoning steps more effectively than methods relying solcly on ranking the full responses. These results suggest that the current implementation of PRM-guided beam search may not fully leverage its potential advantages the context of Long CoT reasoning.
To investigate this phenomenon, we first perform in in-depth analysis on the step quality V during Beam Search defined as the probability of reaching the correct final answer from any intermediate state-ane observe that its trajectory is either unimodal or monotonically decreasing, behavior we term "step quality degradation." " We theoretically show that, due PRM's degrading re-ranking ability over the course of Beam Search, the expected step quality typically exhibits concavity(see Proposition (.8). providing a theoretical explanation for step quality degradation. These findings suggest that deeper reasoning steps in Beam Search are often suboptimal; we therefore propose early termination at the peak expected step quality to preserve high-quality reasoning. Specifically, we introduce Z-Score Guided Early Stopping (ZGES, answer to Q2), which terminates Beam Search based on the trend of step quality, identified by the local z-score average PRM reward at the current step (see Figure D.. ZGES leverages the strong consistency between PRM rewards and true step quality in their z-normalized forms, thereby adaptively preventing overly deep reasoning and enabling efficient early stopping.
We evaluate 7GES on Long CoT models of varying scales, including DeepSeek-FR -------il-----OOE -wwen- 1.5B and 7B (9. It consistently delivers strong performance across all Beam Search configurations and achieves the best results on all evaluated benchmarks.
Compared to standard beam search methods, ZGES achieves better performance with significantly lower computation requirement. For example, on the challenging AIME2024 benchmark, under the same expansion setting, ZGES with 16 beams outperforms standard Beam Search with 16 beams (60.0% + 66.7% when using which includes a comparison between ZGES and fixed-step stopping to highlight the benefits of adaptive stopping, as well as sensitivity analysis on the hyperparameter to demonstrate the robustness of ZGES.
Sessill-Qwen-ll We also conduct an ablation study Section
2 Preliminary
Formalizing LLM reasoning as an MDP model the reasoning process of L.LMs as a Markov Decision Process (MDP) enable formal analysis. A standard MDP is defined tuple M

---

Table I: Performance of different methods. We consider settings with the same total budget N = B x E as equivalent, although Beam Search introduce additional computation overhead due to the use of a reward model. Bold black numbers indicate the best performance under equívalent settings. Red superscripts denote the performance difference of Beam Search compared to Majority@e @ N under the same setting.
Model
AMC22
ATMR24
AIME22
(Majatty())
6015
0112
0118
4116
88
6032
#125
RI-Deeil Quen-15
M1.5
90.3
50.9
43.1
52.7
55.0
15.3
52.2
37.9
It ui-thaill-Qeen111
94.0
05.0
96.0
95.0
97.0
65.0
72.0
18.0
76.0
76.7
90.0
36.0
56.0
36,0
$6.0
8
16
32
4x2
5x2
16x
20
x
RI Duiiiill-rrrr- All-Sok
87.5
35,0
87 51224
92.5
92.5
413
55.3
56.7
S3,9000
60.0
76 7123
40.0
RI D--DDill--ee- SB Ha-d
92.5
87,5
92.5
92.5
50.0
36,2548
36
4000
53,31175
56.71-00
63.35
33.3%
300/
36
36 p1i33
36,7/415
RI-Disall Quen
95.0
66,79
73,3
50.0
46,71
56.7
Diviill-Qeeu-e TB Har
92.5
00.5
05.0 Mm
05,0
63,34419
700
73,
76.7
43
56.7
(S,A,T,r, H), where S is the state space, A is the action space, T x A - A(S) is the transition function, is the reward function, is the initial state distribution, and H is the time horizon. A policy æ S + (AA) maps each state to distribution over actions.
In the context of LLM reasoning, the input problem and the intermediate steps {a); d2,, ........ at) define the state at step as 8, = {x, di....,, dr). The action 4++1 ~ x(- 8r) represents the next reasoning step. Since the next state is deterministically constructed by appending the chosen action to the current state, the transition function deterministic: St+1 = T(5t, Q++1) = {z, aj...., ag a++1 A trajectory T {so, a1, $1,02, dg........ ST) leads to a final answer, which is considered correct if it matches the ground truth y.
Hard PRM and Soft PRM While M obtains PRM annotations from human raters, this approach lacks scalability, More recent works 3 13 address this by training PRMs to predict automatically- generated annotations that estimate the future likelihood of solving the problem successfully. During training, PRMs can be categorized based on how they define step correctness, leading to two types: hard PRMs and soft PRMs [3) Specifically, a hard PRM assumes that reasoning step is good if it can eventually lead to the correct final answer, whereas a soft PRM evaluates the quality of step based on the frequency with which it results in correct solution. We denote a general process reward model as r, which maps reasoning state 8 to a real value in the range
[0, 1]. i.e., r :::8:: 8 + [0, 1]. In particular, we define hard PRM as Fh S {0, }} and soft PRM as r. SS [0, 1].
PRM-guided Beam Search Beam Search can unlock the potential of PRMs to assign credit to
intermediate reasoning steps 4 [4 15). In this work, we denote the number of reasoning steps retained after pruning as the beam size (Abbreviated as Beam), and the number of expansions per Beam at each decoding step the expansion factor(Abbreviin
as Expansion). Specifically, consider a Beam Search configuration with a fixed Beam size B and expansion factor E, and follow the procedure below:
From the initial state so = {r}, sample B x E first-step candidates using the policy x, i.c., {a(+) T(. 60)) F
score all B x E candidates using the PRM r()), and select the top B candidates based on their scores.
From each of the selected B candidates, generate next-step candidates using the policy x,
resulting in B x E new candidates. Repeat this process iteratively.
Complete output trajectories from Beam Search are collected, and the final answer is chosen by Weighted Best of N (WBoN) (3) which selects the best result by weighting answer candidates based on the PRM rewards of the trajectories leading these answers.
3 PRM Based Methods For Long COT Model
In this section, we answer Q1 We first compare PRM-guided Beam Search with Majority @N (Section 3.1) finding that PRM guidance does not improve performance. Then, in Section 3.2) we experimentally observe that during the Beam Search process, the step quality exhibits unimodal
3

---

or monotonically decreasing pattem-referred to as step quality degradation winictttionwwhchh suboptimal performance of Beam Search. Our theoretical analysis Section 3.3 further confirms and explains this phenomenon, attributing it to the significant decline of PRM effectiveness as the search progresses.
which underlies the
3.1 Evaluate the Performance of PRM
Evaluation Strategies and Baselines We primarily focus evaluating the reasoning capability of PRM-guided Beam Search (introduced in Section 2) For comparison, we include PRM-free baseline Majority@1 N (i.e. self-consistency majority voting).
Experiment Setup Evaluations are performed on three challenging math benchmarks: AMC2023, AIME2024, and AIME2025. For PRM training, follow the settings proposed by [3, including both the hard and soft configurations (details are provided in Appendix B.T). We instantiate our LLM policy with two Long CoT models of different parameter scales: and DeepSeek- R1--istiill--eeeeeee with these two variants, ensuring consistency between policy and reward modeling.
(9]. The base models used for PRM training are also aligned
Result As shown in Table 1 although the Beam Search achieves state-of-the-an accuracy under some equivalent settings, performs worse than the Majority@N N-wichhh is PRM-frree- ffreeffeinnnn in most cases when evaluated on the Long CoT models. This finding stands in contrast to previous work using non-Long CoT-based models 3 4 where PRM-guided approaches generally achieved better performance than PRM-free baselines. This raises a key question: what happens during the search process with Long CoT models?
3.2 Degradation of Step Quality and Empirical Evidence
We define the step quality V*(ss as the probability that the LLM policy x reaches the correct answer from the current state.
= (s)
(1)
The step quality is equivalent the state-value function in sparse-reward reinforcement learning, where R(s, a) = upon task success and O otherwise [16]. The dynamics of (s)) during Beam Search reflect the changing quality of explored reasoning paths. We thus empirically study step quality evolution in this process.
1.0
0.63
0.53
Soft
1.50-00
Httrr
0.8
0.50
78-Soft
Step Quality
0.7
Step Quality
78-ffard
Step Quality
0.6
0.38
0.32
0.5
0.4
0.25
0.21
0.3
0.2
0.13
0.11
0.0
0.00
0.00
2k 4k 6k BK 10K12k14416K1Bk220
2k 4k 6k 8k 10112k14416K1BK20K
2k 4k 6k 8k 10K12k14416k11BB000
Token
Token
Token
(a) AMC2023
(b) AIME2024
(c) AIME2025
Figure 2: Empirical validation of Step Quality Degradation
We used PRM guide beam search under different configurations for the Long CoT model. We estimated the step quality of candidates using a Monte Carlo rollout method (details provided in Appendix B.2). The curves in Figure 2 are obtained by averaging the step quality of candidates at each search step over different configurations. The step quality consistently exhibits a monotonically decreasing unimodal pattern the number of steps increases (i.e., grows).
We collectively refer to the two typical forms of the step quality-uiimodal and monotonically decreusing- Step Quality Degrudation. Specifically, when the step index / is sufficiently large (i.e., the reasoning involves many steps, which more common in long CoT models due their extended output length), the step quality tends to decrease relatively low values. This degradation

---

indicates that Beam Search struggles to maintain high-quality candidates as t increases during the reasoning process.
Furthermore, on two benchmarks (AMC2023 and AIME2025), beam search step quality under Hard PRM with the 1.5B model exceeds that under Soft PRM, while on all other settings they comparable. Thus, Hard PRM appears more promising for guiding beam search. Consequently, all ZGES analyses and experiments in Section use only the Hard PRM configuration.
3.3 Theoretical Analysis: Concavity of the Step Quality
In this section, we show Proposition 33. the expected step quality concave /. due to PRM's degrading re-ranking ability in Beam Search, and provide theoretical explanation for step quality degradation. The proof is derived under the extreme cases of two mild and empirically justifiable assumptions, Assumption 3.1 and Assumption 3.2
Assumption 3.1. For a reasoning caannile policy т, transitions from a correct state st are more likely yield correct next state and final answer than those from incorrect one, i.e.. (s 8.) > p" (8e+1 8t) and p¹ (T 8t) > p² (T 8t).
In Assumption 3.1 we use the original letter to denote correctness, and a bar over the letter to indicate incorrectness. For instance, 8t represents the correct state at step i, while 8 represents the incorrect state at step t. This assumption is similar to the one in [6], which has been empirically validated, so we will not elaborate further.
Assumption 3.2. For reasoning- capacity gradually declines during Beam Search. Specifically, it becomes less effective in identifying the optimal candidate from the set (
reasoning-capable capable policy and well-aligned PRM, the PRM's re-ranking
(2) T(. 81) BxE
Assumption 3.2 is based our empirical observations, which will be validated in Appendix C.2
indicates the failure of the PRM as Beam Search progresses. Let ( 5s) = G, which represents the probability of transitioning from the correct state s the incorrect state št+1 during Beam Search (assuming Beam is for simplicity; using other Beam sizes yields similar conclusions).
Then obtain Corollary 3.3
Corollary 3.3. From Assumption 3.2, we can conclude that 6, < 6t i.e., as the search progresses, it becomes increasingly likely transition from correct state an incorrect one.
A smaller e, implies that the PRM is more effective selecting the optimal next step from the candidate set, so it reflects the re-ranking capability of the PRM. To capture the dynamic changes in step quality during the Beam Search process. Assuming the expectation of step quality:
(2) denotes the expectation of step quality at time step during the Beam Search process. We need to establish the variation pattern of E, throughout the Beam Search process. To facilitate the derivation. we consider an extreme case of Assumption 3.1 namely, for geasoning-capabll policy, we have and (5 5t) + We can then state the following lemma (Proof in
E+ = Pñs (5x) (0) V (s+) +
(8:)
(s((+11 st) +
Appendix A.I):
Lemma 3.4. Formally, when (s st) + 1 and (5 sx) - 1 for any t, we have V* + 1 and V* 1
In this scenario, let AV, denote the step quality difference between two consecutive correct states, where AV, = (8++1) - V (8t). We have the following lemma showing that it is a small quantity:
Lemma 3.5. Formally, when p=(51+1 st) and (x (t)) 1, it holds that AV. 1.
Proof. By applying Bayes decomposition, we can expand (*() as follows:
(=T(s)) = (s(+1 st) (5441) + (5141 8t) (5(++))
o(52)
Therefore, AV, Vd (8(+1) V (st) R nz (sc41 8t)) V (8 0()) 1
Similarly, we can prove that e, also a small quantity (Appendix B.T). From this, we can obtain the second-order difference expression of the expectation of step quality E, in the following theorem:
5

---

Theorem 3.6 (Second-order difference of E, ). Eet P (s)) P (s) denote the expectation of step quality. The second-order difference is given by A A²E, E, Ext2 + E. 2 2 We conclude that the second-order difference of Fg is:
A A = Pās(( 80)
AV++ - AV, + (()) 4+1)
(A)
(B)
The proof of Theorem 3.6 is provided in Appendix A.3 We know from Corollary 3.3 that term (B) strictly negative, while the sign of term (A) remains undetermined. Recall that 6, is defined to characterize the re-ranking capability of the PRM step t. So the absolute value of the term V (st)(E; E++1) (term B) serves as an indicator of how much the PRM's re-ranking accuracy deteriorates over time.
Claim 3.7. Under Assumption 3.2 which states that PRM re-ranking accuracy significantly degrades during beam search (see the Appendix C.2 expect |er E++1l dominate A AVe. Therefore, the second-order difference F. Pes (8t likely negative.
(AV - AV, V(se((< - Et+1)) is
Therefore, we state the following proposition:
Proposition 3.8 (Concavity of expectation of step quality). Since the second-order difference E of the expectation of step quality E, Pās (st 80) (8)) (ās V=) is typically negative, E, is concave in the discrete sense.
Proposition 3.8 shows that the expectation of step quality during the Beam Search process is generally concave, which results from the significant decline in PRM's s re-ranking capability as the search progresses, as established in Claim 3.7
We formalize general property of concave sequences follows:
Lemma 3,9 (Degradation of Concave Sequences). Ifa discrete sequence ft. satisfies A² < then Aft is non-increasing. In particular, when St. increases its growth slows down, and when fc decreases its decay accelerates.
This concavity lemma directly accounts for the two observed patterns of step quality degradation
Unimodal curves, where initial gains decelerate and eventually level off or reverse as growth slows;
Monotonic degradation, where AE, starts negative and keeps decreasing, leading to wors- ening quality over successive steps.
Table 2: Pearson correlation coefficients between PRM reward and step quality.
Model
AMC2023
ATME2024
AIME2025
R1 R1-Distill-Qwee 1.5B Hard
1.5d-Hard
0.991
0.977
0.935
Dii-itill-Qwee-7B..
0.914
0.949
0.965
Z-Score Guided Early Stopping For Beam Search
We address as follows. Section 4.1
establishes the consistency of z-scores between PRM Reward and Step Quality, forming the basis of our method. Section 4.2 introduces our heuristic method ZGES, and Section 4.3 reports experimental results demonstrating its effectiveness.
'These two scenarios are theoretical conjectures characterizing common suboptimal behaviors of E,. Con- cavity alone does not guarantee the function is strictly unimodal monotonically decreasing.

---

1.5B-Hard-AM233
HSB-Hard-AMME2
1.5B-HardAANN25
TB-Hard-AMC23
78-Hard-AIME24
78-Hard-AIMER AIME25
0.020
5,07
03.20
0.05
Residuals
PRM Reward Mean
Figure 3: Residual Analysis: Linear fitting of mean PRM reward and step quality for candidates at each step under the same beam search settings, with MAE mean calculation.
4.1 Consistency of Z-Scores between PRM Reward and Step Quality
As established in Section 3 step quality degradation is a primary factor limiting the effectiveness of beam search in Long CoT reasoning tasks. This observation suggests simple yet effective strategy: terminate the beam search at the point where the average step quality of candidates peaks, and let the L.LM policy complete the remainder of the trajectory. Theoretically, this approach can maximize the expected likelihood that the final output includes correct solution.
However, key challenge is that PRM estimates the only available signal during search are evidently biased 17]. This calls for reinterpreting PRM scores and identifying a variable that better approximates true step quality. Notably, the average PRM reward of candidates exhibits strong linear correlation with their average step quality (see Table 2 for Pearson correlation coefficients across beam search configurations on the same benchmark).
As observed, the Pearson correlation coefficients between them are consistently greater than 0.91, indicating strong linear correlation. To further enhance our judgment, we performed residual analysis on the mean PRM reward and mean step quality under different beam search settings. Additionally, calculated the mean MAE for each beam search configuration. The results presented in Figure The residual plots and low MAE confirm a good linear fit between the two variables
Having established the linear relationship, we further show that the z-scores of the two variables remain consistent throughout the search process.
Lemma 4.1 (Z-score Consistency). Let x4 and y, denote the mean PRM reward and mean step-quality of all beam-search candidates at step t under fixed beam setting B x E:
BxE
BxE
Σ
r(s--1,()))
). Yt
Σ V(S-11, (9))
Ft BXF
BXE
BxE are the beam candidates. If there exist constants k > 0 and b such that I; yt b for all then their z-normalized forms
where (a,) ~ x(. | 8 1)
By
2
3/2
0y
satisfy x/ for all f. Hence, the z-scores of the mean PRM reward and the mean step-quality coincide throughout the search trajectory.
Proof. Since ky + b, we have
x'
Px
ky + b
Mx
k ( ply)
1 My
y
o
O2
k TTy
0
which proves the claim.
4.2 Method: ZGES
Section 4.1 shows that, for the Long CoT model, the average PRM reward and the average step quality of candidates at each beam search step exhibit strong alignment after applying z-normalization. Since
Residuuls randomly scattered around zero without any clear pattern, indicating good linear fit.

---

z-scores reflect relative deviations from the local mean, they provide principled way to monitor the dynamics of search; negative z-score at the final step, for instance. indicates a local decline in quality relative to previous steps. This motivates the use of locally computed 7-scores as signal for identifying potential performance drops during search. Our method can formally described as follows.
Set the threshold and Beam Search configuration B x E.
2. Run Beam Search. each step record the mean PRM reward of all candidates, Zg.
3. Compute the local z-score of in using the sequence (.:)
4. If x/ < A, stop Beam Search early and directly decode from the candidates at step 1; otherwise, continue from Step 2.
Figure I iillsstrates the proposed ZGES method. The hyperparameter À governs the sensitivity of our dynamic carly-stopping criterion cnttrion-inntitiveele inntuiiively. a smaller À leads to later termination steps, while a larger À results in carlier stopping. In Section [.1 we conduct sweep different À values and observe that ZGES performance remains stable across wide range of setrings. This insensitivity to A highlights the robustness of our method.
4.3 Experiment
Experiment Setup The experimental setup consistent with Section 3.1 compare our method with Majority@e @N and the standard PRM-guided beam search methods, including Hard PRM and Soft PRM. Our method requires only simple modifications to the beam search algorithm. As noted in Section 3.3 only report results for method using the Hard PRM setting in this section. In all Beam Search settings, the expansion factor fixed to 2. For the hyperparameter A, we set 0.6 for the 1.5B model and À = 0 for the 7B model. As shown in Section 5.1 the performance generally insensitive to the choice of X.
1.5B Models
1.5B Models
1.5B Models
70
95
BEST
BEST
BEST
Accuracy (%)
Accuracy (%)
Accuracy (%)
50
Majolly@N Bear-Barchh-Bot
Majorlly@N
Majoily@N Bear-Baacch-Bot
40
BeariBaach--ott
Bear-Seerd-
Beer-hhcdd
BeenSSearc--Hord
2GES-Hard
20Ea-Hard
Z0ES-Hadd
30
25
2M 2
2
2 BxE N
BxE N
BxE or
(a) AMC2023
(b) AIME2024
(c) AIME2025
7B Models
7B Models
7B Models
100.0
85
Accuracy (%)
97.5
BEST
Accuracy (%)
80
BEST
Accuracy (%)
BEST
75
65
92.5
Majorby@N DeamSearch
70
Majorliv@N BeamSearch
50
MajoflygN BeanGearch
90.0
65
45
Bwe--Sercc-HHndd
ZGES-Hard
ZGES-Hard
ZGES-Hard
60
2*2 2*3
214
2
2*8
2*2
2"3
2'4
2*5
2
2
2
2
2*6
BxE or
BxE or N
BxE N
(d) AMC2023
(e) AIME2024
(i) AIME2025
Figure 4: Model Performance Results. The term BxE or N denotes the product of beam size and expansion in Beam Search, or the value of N in Majority @ N, respectively.
Main Result The comparison results are presented Figure competitive performance compared to the baselines, with the following notable advantages:
ZGES demonstrates highly

---

Best Performance Across Settings. Under all model scales and benchmark configurations, ZGES consistently achieves best results.
Robustness to Beam Size Scaling, As the beam size increases (from 4 to 64), ZGES outperforms all other baselines in most scenarios, indicating strong robustness.
Improved Performance with Reduced Computational Cost. Compared to standard beam search methods, ZGES achieves best performance even with relatively small beam sizes (as indicated by the intersection of the ZGES curve and the best performance line in the figures). Moreover, by incorporating
early stopping mechanism, ZGES reduces the number of PRM calls required during beam search (Table 3 effectively lowering computational overhead while maintaining
enhancing generation quality.
5 Ablation Study
In this section, conduct further analysis and discussion on the proposed ZGES method. In Section 5.1 we conducted hyperparameter sensitivity experiments of to investigate its impact. Section 5.2 compares the behavioral and performance differences between ZGES and the fixed-step stopping beam search.
5.1 The performance of ZGES exhibits robustness changes in hyperparameter.
The hyperparameter is the sole tunable parameter in our method, ZGES. We analyze how variations
in À affect the performance of ZGES. Specifically, we consider four values: -0.4, 00.6. -0.8, and -1.0. For each X, ZGES is evaluated using multiple x E Beam Search configurations, consistent
with those in Sections 3.1 and 4.3
1.5B Model
7B Model
1.5B Models
7B Models
0.80
Rieed-steo
0.80
Accuracy
0.75
Accuracy
0.66
Soft: 0.622
Hard: 0.8L8
0.79
Hard: 0.162
Soft: 0.768
0.579
0.78
0.65
0.64
0.60
0.62
A -4
008
s 1.
t -04
0.8
A -1
0.76
3
Stop Step
Stop Step
Figure Sensitivity Analysis
Figure 6: Comparison with Fixed-Step Stopping
The overall performance is assessed across three benchmark tasks. As shown in Figure the results are visualized using box plots to illustrate the impact of different À values on the performance of ZGES. We observe that the performance of ZGES remains consistent across different choices of indicating that the method is robust to the selection of this hyperparameter.
5.2 Dynamic Stopping is Better than Fixed-Step Stopping
To further highlight the advantage of ZGES with dynamic stopping, we compare it against a fixed-step stopping baseline that terminates Beam Search predetermined step.
As shown in Figure 6 both methods evaluated under the Hard PRM setting. The reported results correspond to the average performance across three benchmark tasks, using the same Beam Search configurations as described Section 5.I In the figure, "Soft" and "Hard" denote Beam Search guided by the standard Soft PRM and Hard PRM settings, respectively. The results show that ZGES outperforms the fixed-step stopping baseline configured within a selected step range that is expected to contain high-quality steps (as suggested by Figure 2 which we used to reduce computational cost. Moreover, both methods consistently outperform standard Beam Search, which is expected since the degradation of step quality over time has been demonstrated in Section 3

---

Table 3: Comparison of PRM calls and token ratios across models and tasks. 1.5B and 7B are the RI I--istilll-wwert models; (xES(x) denotes ZGES with À = z. PRM Call shows the average number of PRM calls; Tokens Ratio indicates the average number of tokens relative to Beam Search.
AMC23 PRM Call
AMC23
AIME24 PRM Call
AIME24
AIME25 PRM Call
AIME25
Model
Method
Tokens Ratio
Tokens Ratio
Tokens Ratio
1.5B
ZGES (-0.4)
3.08 _61 %
0.753 0.763
3,27 166%
0.929
3,33 [65%
0.926
1.5B
ZGES (-0.8)
3.18 [60 %
3,42 .64%
0.956
3.48 [63%
0.942
1.5B
Beam Search
7.91
9.55
9.53
7B
ZGES (-0.4)
2.97 156%
0.675 0.692
3,31 163%
0.839
3,33 162%
0.905
7B
ZGES (-0.8)
3.17 %
3,54 [61%% %
0.856
3.58 [.9%% %
0.911
7B
Beam Search
6.69
9.00
8.73
5.3
Token Usage and PRM Calls
We further analyze the efficiency of ZGES in terms of PRM calls and token usage across different models and tasks (Intuitively, these two metries will decrease compared to the standard method), Table 3 summarizes the results for the 1.5B and 7B models, comparing ZGES with standard PRM- guided Beam Search under different À settings.
From the table, we make three key observations. First, ZGES significantly reduces the number of PRM calls compared to the standard Beam Search (by more than 50% in most cases) while maintaining or even improving performance. Second, for both model sizes, smaller À result in more PRM calls, consistent with the analysis in [.1] smaller À delays the stopping point, leading to increased PRM usage. Third, the token ratio demonstrates that ZGES also reduces the overall token generation compared to standard Beam Search, indicating improved efficiency computation and resource usage. Overall, these ablation results further validate the practical advantages of ZGES in both effectiveness and efficiency.
Conclusion
In this paper, uncover "step quality degradation" in long-horizar Beam Search its step quality follows unimodal or monotonic degradation trends. To address this, we propose Z-Score Guided Early Stopping (ZGES), which monitors the local z-score of PRM rewards detect the quality peak and terminate search before degradation sets in. Empirical evaluation on diverse math benchmarks and Long CoT models shows that ZGES consistently surpasses both standard Beam Search and PRM-frec approaches, cutting computational cost while delivering stronger performance. Our work thus bridges theoretical insights into PRM limitations with practical, efficient search strategy.
Limitations Due to limited computational resources, we could not explore broader range of values (e.g., more aggressive early stopping with À E [0, 1). However, this does not hinder the demonstration of ZGES's 's effectiveness. In future work, we plan to investigate more flexible early stopping strategies beyond local Z-normalization.
10

---

References
[1] Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, llya Sutskever, and Karl Cobbe. Let's verify step by step. In The Twelfth International Conference on Learning Representations, 2023.
[2] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14168, 2021.
[3] Peiyi Wang, Lei Li, Zhihong Shao, RX Xu, Damai Dai, Yifei Li, Deli Chen, Yu Wu, and Zhifang Sui. Math shepherd: Verify and reinforce Ilms step-by-step without human annotations. arXiv preprint arXiv:23
2023.
[4] Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling Ilm test-time compute opti- mally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
[5] Jianqiao Lu, Zhiyang Dou, Hongru Wang, Zeyu Cao, Jianbo Dai, Yunlong Feng, and Zhijiang Guo. Autopsv: Automated process- supervsed verifier. Advances in Neural Information Processing Systems, 37:79935- 2024.
[6] Wendi Li and Yixuan Li. Process reward model with q-value rankings. arXiv preprint arXiv:2410. 1287, 2024.
[7] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
[8] Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai ol system card. arXiv preprint arXiv:2412. 2024.
[9] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et Deepseek-rl: Incentivizing reasoning capability in Iims via reinforcement learning. arXiv preprint arXiv:2501.12945 2025.
[10] Andong Chen, Yuchen Song, Wenxin Zhu, Kehai Chen, Muyun Yang, Tiejun Zhao, et al. Evaluating ol-like 11ms: Unlocking reasoning for translation through comprehensive analysis. arXiv preprint arXiv:2502. 1154,, 2025.
[11] Tianyang Zhong, Zhengliang Liu, Yi Pan, Yutong Zhang, Yifan Zhou, Shizhe Liang, Zihao Wu, Yanjun Lyu, Peng Shu, Xiaowei Yu, et al. Evaluation of openai ol: Opportunities and challenges of agi. arXiv preprint arXiv:
2024.
[12] Qiguang Chen, Libo Qin, Jinhao Liu, Dengyun Peng, Jiannan Guan, Peng Wang, Mengkang Hu, Yuhang Zhou, Te Gao, and Wanxiang Che. Towards reasoning era: A survey of long chain-of-thought for reasoning large language models. arXiv preprint arXiv:2503.09567, 2025.
[13] Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Meiqi Guo, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, et al. Improve mathematical reasoning in language models by automated process supervision. arXiv preprint arXhv:2406.06553 2024.
[14] Amrith Setlur, Chirag Nagpal, Adam Fisch, Xinyang Geng, Jacob Eisenstein, Rishabh Agarwal, Alekh Agarwal, Jonathan Berant, and Aviral Kumar. Rewarding progress: Scaling automated process verifiers for Ilm reasoning. arXiv preprint arXiv:2410.08146, 2024.
[15] Yufeng Yuan, Yu Yue, Ruofei Zhu, Tiantian Fan, and Lin Yan. What's behind ppo's collapse in long-cot? value optimization holds the secret. arXiv preprint 2rXiv:2503.01441, 2025.
[16] Richard Sutton, Andrew Barto, et al. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.

---

[17] Amirhossein Kazemnejad, Milad Aghajohari, Eva Portelance, Alessandro Sordoni, Siva Reddy, Aaron Courville, and Nicolas Le Roux. Vineppo: Unlocking rl potential for Ilm reasoning through refined credit assignment. arXiv preprint arXiv:2410.0160 2024.
[18] Michael Luo, Sijun Tan, Justin Wong, Xiaoxiang Shi, William Y. Tang, Manan Roongta, Colin
Cai. Jeffrey Luo, Li Erran Li, Raluca Ada Popa. and Ion Stoica. Deepscaler: Surpassing
ol ol-preview with 1.5b model by scaling rl. https: :
/pettyyretttteteer radio- b75 notion site/
DeepScaleR- SeepScaleR-Surpassinng Surpassing- 01 D1-Previes with a 1 5B Model - by Scaling RL 11111111222211600000088333333333 2025. Notion Blog.
[19] Yuliang Liu, Junjie Lu, Zhaoling Chen, Chaofeng Qu, Jason Klein Liu, Chonghan Liu, Zefan Cai, Yunhui Xia, Li Zhao, Jiang Bian, et al. Adaptivestep: Automatically dividing reasoning step through model confidence. arXiv preprini arXiv:2502. 13943, 2025.
[20] Liang Huang, Kai Zhao, and Mingbo Ma. When finish? optimal beam search for neural text generation (modulo beam size). arXiv preprint arXiv:8809.00069 2018.
[21] Yilin Yang, Liang Huang, and Mingbo Ma. Breaking the beam search curse: A study of (re-) scoring methods and stopping criteria for neural machine translation. arXiv preprint arXiv:1808.09582, 2018.
12

---

A Theory Proof
A.1 Proof of Lemma 3.4
Lemma 3.4. Formally, when p" (st-1 8t) + 1 and (5 5t) 7 1 for any t, we have
(=(s)) and V* <1. 1.
proof. Assume the reasoning horizon is T.
Then have
T-1
p² (T 81) 2
p (81+1 8:) +
1=1
therefore
(*)s) = p² $t) +11 1.
Similarly, for the error states, we have
T-1
p=
2
p (3:41 5:) + 1,
1=t
which implies
(5. = (F 8c) +.
A.2 Probability consistency between Pis and pd
Under an extreme case of Assumption 3.1, where p" (8++1 8t) and p" (8441 8x) show that the Beam Search transition probabilities satisfy
We
PBs 8x) +
and ( 8e) + 1.
Consider the special case in Section 3.3 where the beam set to to simplify the probability formulation of Beam Search. When starting from correct state Sı, the candidate set {a ~ x(- Bx) is sampled from the output distribution of æ. If the next step is randomly sampled from Bx then according to resampling theory, the selected action
BxE
the candidate set {a ~ x(- s)) still follows the probability distribution induced by Furthermore, since PRM is generally more efficient than naive random sampling, we have
( (t))
Following the same reasoning, also obtain
( 82) + 1.
Therefore, we have e, PBg (8t+1 8e) & 1.
13

---

A.3 Proof of Theorem 3.6
Theorem 3.6 (Second-order difference E, Let Et Pis(s (o) Pūs(3 (s))
denote the expectation of step quality. The second-order difference is given by A E²E; El+2 + Es 21++1 We conclude that the second-order difference of Eg
E (s su)
AV+1 - AV + (c) a+11
(8)
proof. As mentioned in Section 3.3
consider special case based on Assumption
3.1 where
the policy has strong reasoning ability. In this case, Pa (8t+1 st) + and p" (3r41
St) +
We first identify several small terms: AV, < 1, C. 1. V (8t)
(5 (St+1 8t)
< and
Pgs ( 8t) < (Appendix A.2 Lemma 3.4, Lemma 3.5
In the derivation, we ignore the products of small terms, e.g., AV, Cr.
According to the definition of the expectation of step quality, have:
E = Pis (&t (o) + (5 sp)
E BS (st+1 so)V + Pis (5 (5(11
Therefore, the first-order difference of E,, denoted as A A,, is given by: A E++1 Fx (s+1 V*)(1(())))) - Pss(s 8o) V))))
PBS (5 so)V (3:41) - P V*)
o(82)
Pis ($141 Pis so) + Pis (5 52 Pt)
sp)
V*($++1) - PPssss V*)
((22)
(s su) (Sts(1t11 (5)+1))))+)))))))))))))))))) - V (st)]
Piss(s So)
[1 CV" (st) +V)) V (st)
Pa (st s0)
AV, VvV &,V,
0(89)
(s 80) lAV, - G, (,V*((s))
Based on this, we derive the second-order difference A E, as follows:
A E
(Et+2 Est1) - (Et+1 - Et)
-EE411 AE,
Pus((stt1
su) [AV-1 c1+ V/ (s(+1) - (st
(st so) [AV, (s))
[PEs(
sc) + (5 so) P0)(PE55 [x)] [A V2+1 Er+1 V (s++1)]
(ss so) (AV - =
(
so) (P 8t) [AV+1 Ex+1 E V - [AV++1 El+1 V (sc+1))}
-Pgs 32 (0) BB (8t+1 5x) [AV+11 Ex4 / (s++1)
o(62)
(st 50) {(1 -e) [AV++ - 6241 (V* + AVV) - [AV - EE+1 + AV))))
Pis (8x so)
AV41-A4 + V(<) c++1
(A)
(B)
14

---

B Details of Experimental Setup
B.1 PRM Training
To train hard PRM and soft PRM, we gather 9K challenging questions from the training data of the DeepScaleR project [18] by keeping problems that have non-trivial accuracy for DeepSeek-RR -ereeck-- Distill-Qwen-7B. For each problem, we generate 16 responses, and generate 8 completions for each step in the generated responses to construct the PRM training dataset. We follow 3 to construct the datasets for Hard PRM and Soft PRM training.
B.2 Estimation of Expected Step Quality
To estimate the expectation of step quality, we average the step quality of all B x E candidates each time step. For each candidate, we adopt the Monte Carlo estimation method from [77. Specifically, starting from each candidate, we generate N subsequent trajectories (we set N = 4 in our experiments) and approximate the step quality by the proportion of trajectories that reach the correct answer. The experiments in [17] also demonstrate that using small N (5 in their experiments) does not introduce significant bias.
B.3 Step Segmentation
In general, step segmentation can be based on symbolic cues (e.g.. explicit "Step" annotations or line breaks), model confidence [19], or token-based heuristics. Given that DeepSeek-RI ----i-tiitl--tuuttt-----i------t models do not yield outputs with clearly demarcated step boundaries, we adopt a hybrid segmentation strategy that integrates symbolic markers and token-length priors.
Specifically, we treat certain tokens-such as line breaks ((n) or step-indicative phrases- as potential split points, and further apply this rule approximately every 2000 tokens to prevent overly fragmented segmentation in long outputs. This approach yields around 10-20 steps per output in practice and works well empirically.
C Additional Experiments and anlysis
C.1 Hyperparameter affects the aggressiveness of early stopping.
Local
À 0.0
A= 1.0
A 1.5
Figure 7: Smaller values of À result in earlier termination points.
We illustrate the influence of the parameter À on the stopping position using the concave function Figure as an example. Specifically, we compute the local Z-score at each discrete point (i.e., by performing Z-normalization on the values from the starting point up to the current point). We then apply three different values of X. As decreases, the stopping point moves later (or is delayed); conversely, larger À value leads to earlier stopping position (or advances).
15

---

C.2 Empirical Evidence for Assumption 3.2
Assumption 3.2 states that for a caassonnng-caaaaai policy, the re-ranking ability of the PRM gradually declines as Beam Search progresses it becomes increasingly difficult to select the optimal next step from the candidate
To empirically validate this, we consider DeepSeek-RR--Distill-7 as reasoning-capable policy, as evidenced by its performance the AMC2023 benchmark, where it achieves 90% accuracy without relying on any test-time methods (see T. We apply the Hard PRM to guide Beam Search and evaluate PRM's re-ranking ability each step by checking whether it can successfully identify the optimal next step from the B x E' candidate actions.
The optimal next step is determined using the Monte Carlo estimation of step quality described in Appendix B.2
0.8
0.8
Ranking acc
0.7
0.6
1.6
0.4
0.4
0.3
10
10
Step
Step
Figure 8: Re-ranking accuracy of Hard PRM on Figure 9: Re-ranking accuracy of Hard PRM on AMC2023
three benchmarks
We follow the above methodology to measure the re-ranking accuracy of PRM under different Beam Search configurations (Beam ranging from 4 to 64 with Expansion fixed to 2, same as in Section 3.1 The results shown in Figure and Figure
Figure & shows the accuracy measured exclusively on the AMC2023 benchmark, where the pol- icy exhibits stronger reasoning capabilities, thereby more closely aligning with the assumptions underlying our hypothesis. Figure 9 shows the average re-ranking accuracy across three benchmarks: AMC2023, AIME2024, and AIME2025.
From the results, it evident that the PRM's re-ranking ability declines Beam Search progresses, and this decline is quite pronounced. On the AMC2023 benchmark, the decrease is even more striking-almost linear. This provides strong support for the conjecture in Claim 3.7 indicating that PRM's performance deteriorates progressively as Beam Search advances. Consequently. the expectation of step quality exhibits concavity, which in turn gives rise to the step quality degradation discussed in Section 3.3
D Related Works (prior work on early stopping)
Previous studies have explored early stopping algorithms for beam search 20 21 These studies
focus on translation-style generation tasks, where hypotheses ranked by likelihood and length penalties, and have made important contributions to decoding strategies. In contrast, our work focuses on PRM-guided inference under the Long CoT model setting. We introduce novel z-score- based termination criterion motivated by empirical observations of PRM dynamics, which improves stopping reliability and reasoning performance.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction effectively capture the core ideas and contribu- tions our work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of work at the end of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
We provide detailed derivations for all presented theoretical results, either in the main text or the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We include as many details as possible the paper to facilitate reproduction of our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
18

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
We do release the code, but our method is straightforward to reproduce.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "cipps.c/puullc//guu /ot.e//uuudeeooeeouuummiiiiiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the appendix, we provide as many details as possible about our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
We did not conduct relevant discussions.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
19

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: These details are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We commit to adhering to the guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We not conduct related discussions.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not involve any high-risk activities.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We ensure that all referenced techniques are properly cited.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We did conduct related discussions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve this aspect.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve this aspect.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
22

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: Relevant clarifications have been made.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurd/: http://///////oofeeeeee///////// for what should or should not be described.
23


Reviews:
[{"review_id": "pFtjs26553", "reviewer": "Reviewer_egya", "summary": "This paper investigates the effectiveness of Process Reward Models (PRMs) in guiding test-time search for Long Chain-of-Thought (Long CoT) reasoning. The authors find that standard PRM-guided beam search does not consistently outperform PRM-free approaches like Majority@N. Through empirical and theoretical analysis, they observe a phenomenon of step quality degradation during beam search and propose Z-Score Guided Early Stopping (ZGES) as a remedy. ZGES monitors local trends in PRM reward signals and adaptively halts beam expansion when reasoning quality peaks, thereby reducing unnecessary computation and mitigating the diminishing returns of deeper search. The method is evaluated on Long CoT math benchmarks and shows improved accuracy and efficiency compared to conventional beam search methods.", "questions": "See above weakness", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper targets an important and practical challenge in reasoning with LLMs: improving test-time search in Long CoT settings using PRMs.\n\n2. The authors identify and explain the degradation of step quality during beam search with theoretical justification (concavity of step quality trajectory).\n\n3. ZGES is a simple yet effective strategy that improves performance while reducing compute, and is well supported by experiments.\n\nWeaknesses\n\n1. The findings partially contradict prior conclusions in PRM literature (e.g., Scaling LLM Test-Time Compute Optimally, AlphaZero-style lookahead), which have shown benefits from deeper reward-guided exploration. The paper would be strengthened by applying ZGES to a wider range of PRMs (e.g., value estimation PRMs trained with lookahead) to ensure its generality and reconcile these differing observations.\n\n2. The training process of the PRM used in this study is under-explained. There is little analysis of PRM accuracy, which is critical given that poorly trained PRMs may introduce unreliable reward signals. Related benchmarks like PRMBench could help validate the PRM’s fidelity.\n\n3. All experiments are limited to math datasets. Testing on other domains such as scientific QA (e.g., GPQA) would be valuable to demonstrate the generalization of ZGES beyond math reasoning.\n\n4. Since the Long CoT outputs from models like DeepSeek-R1 are not cleanly step-separated, the process of segmenting steps is crucial for PRM-guided reasoning, yet the paper provides no technical detail or justification for how step boundaries are identified.\n\n5. Minor writing issues exist, e.g., line 87 contains a typo: “reasonoing”.", "was_revised": true, "final_justification": "While the rebuttal clarified some minor points, the two core concerns remain insufficiently addressed. First, the reply lacks theoretical justification or detailed analysis to explain why the proposed method shows such a large performance gap between long-CoT and short-CoT settings, or with AlphaGo-style algorithms, and it does not address my request for experiments on more existing PRMs. Second, although the authors acknowledged a critical limitation, no preliminary attempt was made to run even a lightweight evaluation on the test set, which would incur minimal computational cost. These two points are central to both the method and its claimed effectiveness, and remain unresolved after the rebuttal.\n\nThat said, I acknowledge that the paper presents some new perspectives, so I would understand if it is ultimately accepted, but my final score remains cautious given the unresolved core issues.", "rebuttal": "**We thank the reviewer for the thoughtful feedback and valuable suggestions. We address each point below and believe our clarifications and additions help strengthen the paper.**\n\n---\n\n\n>**Weakness 1. Contradiction with prior PRM literature & generality of ZGES**\n\nWe thank the reviewer for highlighting the apparent discrepancy between our findings and prior PRM-related work, such as *Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters*. That work demonstrates that reward-guided exploration methods at test time—such as beam search and lookahead search—can significantly outperform PRM-free approaches like Majority@N. In contrast, our study finds that in the **Long CoT model** setting, beam search does not consistently outperform Majority@N.\n\nWe acknowledge this difference, but we believe the conclusions are not contradictory. The prior work is based on non-Long CoT models with relatively short reasoning traces, whereas our study focuses on PRM behavior under the Long CoT model setting, where the extended reasoning depth and structure present different challenges.\n\nTo further test the generality of our proposed ZGES method and to better reconcile these observations, we follow the reviewer's suggestion and evaluate the standard lookahead search method described in *Scaling LLM Test-Time Compute Optimally* under the Long CoT model setting. We then apply ZGES on top of it for comparison. **The results are as follows.**\n\n| Model | Method               | AMC23         | AIME24        | AIME25        |\n|:-----:|:---------------------|:--------------|:--------------|:--------------|\n|**1.5B**       | 🔴 **ZGES (λ = -0.4)** | **0.910** ↑2.5% | **0.600** ↑7.4% | **0.366** ↑2.0% |\n|**1.5B**       | 🔴 **ZGES (λ = -0.8)** | **0.915** ↑3.0% | **0.580** ↑5.4% | **0.373** ↑2.7% |\n|**1.5B**| Look Ahead Search          | 0.885          | 0.526          | 0.346          |\n|       |                      |                |                |                |\n|**7B**        | 🔴 **ZGES (λ = -0.4)** | **0.945** ↑0.5% | **0.780** ↑3.3% | **0.574** ↑6.1% |\n| **7B**       | 🔴 **ZGES (λ = -0.8)** | **0.945** ↑0.5% | **0.767** ↑2.0% | **0.573** ↑6.0% |\n|**7B** | Look Ahead Search          | 0.940          | 0.747          | 0.513          |\n\n> **Note:**  \n> - *Look Ahead Search* refers to the standard PRM-Guided Look Ahead Search without early stopping.  \n> - *ZGES(x)* denotes the ZGES method (used for Look Ahead Search) with λ set to x. \n\nThe experimental results are averaged over different beam size settings, with the expansion size fixed at 2. The results are highly encouraging: the ZGES method significantly outperforms the standard look-ahead search, suggesting that:\n\n1. **ZGES demonstrates strong generalizability** and can adapt to more general search algorithms.\n2. **Under the Long CoT model setting**, early stopping proves beneficial for both Beam Search and Look-Ahead Search, indicating that our observation may reflect a more general pattern.\n\n\n---\n\n>**Weakness 2. Lack of PRM training and accuracy analysis**\n\nThank you for pointing this out. We agree that understanding the fidelity of our trained PRM is critical. The training details of our PRM are provided in `Appendix B.1.` Our training procedure closely follows the method proposed in *Math-Shepherd: Verify and Reinforce LLMs Step-by-Step Without Human Annotations*.  To ensure the reliability of our PRM, we followed the reviewer’s suggestion and evaluated our trained PRM on PRMBench.  However, due to time constraints and the rebuttal deadline, the evaluation has not yet been completed. Once it is finished, we will promptly update the results and share them with you.\n\n\n---\n\n>**Weakness 3. Limited domains (only math reasoning)**\n\nWe thank the reviewer for pointing this out. You are absolutely right that evaluating ZGES on tasks beyond mathematical reasoning is important to demonstrate its generalization capability. Following your suggestion, we conducted experiments on the GPQA dataset, comparing the standard PRM-Guided Beam Search and our proposed ZGES method. The results are shown below:\n\n| Model | Method               | GPQA         |\n|:-----:|:---------------------|:--------------|\n|**7B**        | 🔴 **ZGES (λ = -0.4)** | **0.547** ↑2.7% |\n| **7B**       | 🔴 **ZGES (λ = -0.8)** | **0.541** ↑2.1% |\n|**7B** | Beam Search         | 0.520          | \n\n> **Note:**  \n> - *Beam Search* refers to the standard PRM-Guided Beam Search without early stopping.  \n> - *ZGES(x)* denotes the ZGES method (used for Beam Search) with λ set to x. \n---\n\n>**Weakness 4. Missing details on step segmentation**\n\nWe thank the reviewer for the insightful comment. In general, step segmentation can be based on symbolic cues (e.g., explicit \"Step\" annotations or line breaks), model confidence (see [1]), or token-based heuristics. Given that DeepSeek-R1-Distill-Qwen models do not yield outputs with clearly demarcated step boundaries, we adopt a hybrid segmentation strategy that integrates symbolic markers and token-length priors. Specifically, we treat certain tokens—such as line breaks or step-indicative phrases—as potential split points, and further apply this rule approximately every 2000 tokens to prevent overly fragmented segmentation in long outputs. This approach yields around 10–20 steps per output in practice and works well empirically.\n\n[1]: *AdaptiveStep: Automatically Dividing Reasoning Steps through Model Confidence, ICML 2025.*\n\n\n---\n\n>**5. Minor typo**\n\nThank you for pointing this out. We appreciate your careful reading and have corrected the typo (\"reasonoing\" → \"reasoning\") in line 87. The correction will be reflected in the revised version of the paper\n\n---\n\n**Summary**\n\nWe believe the reviewer’s comments have helped us clarify our methodology, better contextualize our contributions with respect to prior work, and strengthen the empirical evaluation. We hope the revised analysis addresses the concerns raised."}, {"review_id": "9BQY5EDk8y", "reviewer": "Reviewer_LAc4", "summary": "The work provides empirical evidence that Progress Reward Models (PRM) are ineffective for long Chain-of-Thought reasoning tasks and offers theoretical intuition and empirical analysis to provide the following explanation: The PRMs ability to correctly estimate the probability that the LLM finds the correct answer from a given token first increases and then decreases during the search process. An empirical analysis shows that this probability is highly correlated with the PRM score. This insight is leveraged to define an early stopping criterion for the search. The stopping criterion is based on the z-scores of the PRM scores: As soon as it drops below a certain threshold the search is stopped. A comparison with majority@N and standard PRM-guided beam search shows that the method achieves higher accuracy on reasoning tasks.", "questions": "* In the experiment in Section 4.3: How did you define the stopping criterion for the baselines?\n* What is $\\tau$ in Assumption 3.1?\n* How is the correctness of a state defined?\n* In Section 3.1, Equation (1): $\\pi$ is mentioned to be the LLM policy. What is the LLM policy? Is it PRM-guided beam search in this context?\n* If I understood it correctly, I would have assumed that the pattern in Figure 2 looks like the pattern in Figure (b). But in Figure 2, the step quality doesn't have this peak. Can you elaborate on this?\n* The theoretical analysis assumes a beam size of 1 (see line 165). This essentially reduces it to greedy search. To me, this seems like quite a strong restriction. Can you elaborate on this?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n* The paper provides a theoretical explanation for the empirical phenomenon that the performance of PRM-guided beam search drops in the **long** chain of reasoning regime\n* The idea to use z-scores to define an early-stopping criterion is original as far as I know\n* The work is significant as early-stopping helps to reduce computational costs/increases the performance in LLM-reasoning tasks\n* The paper provides an ablation study for the involved hyper parameters (stopping threshold, beam size). The results show that the method is relatively robust towards these choices. \n\n**Weaknesses:**\n* Clarity: there are some parts of the submission that are unclear to me. I am open to increasing my score if these issues can be clarified and resolved. I listed my questions below. \n* Related work: The related work section does not touch upon other pieces of work on early-stopping (a.k.a length normalization) for beam search such as:\n  > Google’s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation (Wu et al., 2016)\n\n  > When to finish? optimal beam search for neural text generation (modulo beam size). (Huang et al., 2017)\n\n  > Breaking the beam search curse: A study of (re-)scoring methods and stopping criteria for neural machine translation. \n\n**Minor comments:**\n* The legend in Figure 6 covers most of the plot. \n* lines 236-244 contain a proof for a theorem/proposition/statement that is never explicitly stated. It is stated informally \"... we demonstrate the the t-scores of the two variables remain consistent throughout the search process.\", but stating it explicitly would make it easier to refer to it/cite it in future work ect.\n* \"concave in the discrete sense\" $\\rightarrow$ isn't the discrete analogue to concavity simply submodularity? Is there are reason why you don't use this term?\n* For me, it would have been helpful if there was a definition of the \"Majority@N\" strategy included, in particular because there is no reference to a publication that introduces this method. I was not familiar with it.", "was_revised": true, "final_justification": "My concerns were addressed with the rebuttal, therefore I increased my score.", "rebuttal": "**We thank the reviewer for the thoughtful feedback and constructive suggestions. We are encouraged by the recognition of our contributions. Below, we address each of the reviewer’s concerns in detail.**\n\n---\n\n### Clarity Issues\n\n>**Comment:**  \n*There are some parts of the submission that are unclear to me. I am open to increasing my score if these issues can be clarified and resolved.*\n\n**Response:**  \nThank you for your openness. Specific clarifications are addressed in responses to your detailed questions below.\n\n---\n\n### Related Work on Early Stopping\n\n>**Comment:**  \n*The related work section does not mention prior work on early stopping / length normalization for beam search such as Wu et al. (2016), Huang et al. (2017), and others.*\n\n**Response:**  \nWe thank the reviewer for highlighting the relevant work on early stopping in beam search. These studies focus on translation-style generation tasks, where hypotheses are ranked by likelihood and length penalties. They have made important contributions to decoding strategies.\n\nIn contrast, our work focuses on *PRM-guided inference* under the *Long CoT* model setting. We introduce a novel **z-score-based termination criterion** motivated by empirical observations of PRM dynamics, which improves stopping reliability and reasoning performance.\n\nWe will add a discussion of these works in the *Related Work* section.\n\n\n---\n\n### Minor Comments\n\n>**Comment:**  \n*Figure 6 legend covers most of the plot.*\n\n**Response:**  \nThank you for pointing that out. We will correct the occlusion of the Figure 6 legend in the revised version of the paper.\n\n>**Comment:**  \n*Lines 236–244 include a proof but no explicit theorem statement.*\n\n**Response:**  \nWe thank the reviewer for the insightful comment. You're right — our earlier statement lacked formality. In the revision, we will include a lemma to formally state the z-score consistency.\n\n\n>**Comment:**  \n*\"Concave in the discrete sense\" – why not use \"submodular\"?*\n\n**Response:**  \nWe sincerely thank the reviewer for this thoughtful comment. We agree that **submodularity** is the standard discrete analogue to concavity, and we appreciate the suggestion. \n\nIn our work, the step quality function is defined over a one-dimensional discrete time index$t \\in \\{1, 2, \\ldots, T\\}$\n, rather than subsets of a ground set. We intentionally use the phrase “concave in the discrete sense” to provide an intuitive and accessible description of the diminishing trend in step quality over time. Our goal is to make this behavior immediately understandable to a broader audience, especially readers less familiar with the formalism of submodular set functions.\n\nSpecifically, we refer to functions \\( f \\) defined on integers \\( t \\) satisfying the **discrete concavity condition**:\n\n$$\nf(t+1) - f(t) \\leq f(t) - f(t-1)\n$$\n\nwhich parallels the classical second-derivative criterion for concavity in continuous settings.\n\nThat said, we fully acknowledge the reviewer’s point, and in the revised version of the paper, we will include a clarification on the connection between our definition and submodularity, to ensure greater precision and rigor.\n\n\n>**Comment:**  \n*Define Majority@N clearly – no citation provided.*\n\n**Response:**  \nThank you for the helpful suggestion. We would like to clarify the **Majority@N** strategy (also known as *self-consistency*):\nFormally, let the model generate a set of answers $\\{a_1, a_2, \\ldots, a_N\\}$. The final prediction is:\n\n$$\n\\hat{a} = \\arg\\max_{a \\in \\{a_1, \\ldots, a_N\\}} \\text{Count}(a)\n$$\n\ni.e., the most frequent answer among the N samples.\nTo enhance the clarity and readability of the paper, we will add a formal definition of Majority@N in the revised version.\n\n---\n\n### Responses to Specific Questions\n\n>**Q1: In the experiment in Section 4.3: How did you define the stopping criterion for the baselines?**  \n\n**A:** Thank you for the reviewer’s question. As stated in Section 4.3, the baselines include Majority@N and standard PRM-Guided Beam Search, neither of which employs early stopping.\n\n\n---\n\n>**Q2: What is $\\tau$ in Assumption 3.1?**  \n\n**A:** Thank you very much for your valuable question. \nIn our setting, $\\tau$ denotes a complete reasoning trajectory generated by the model when solving a given problem. It consists of a sequence of reasoning steps, i.e.,\n\n$$\n\\tau = \\{a_1, a_2, \\ldots, a_T\\},\n$$\n\nwhere $a_T$ (the final step) typically contains the model's predicted answer.\n\nAs we mention in Section 3.3, we would like to emphasize that under Assumption 3.1:\n\n* A trajectory denoted as $\\tau$ refers to a **correct** trajectory — that is, one where the final answer in $a_T$ is correct.\n* A trajectory denoted as $\\bar{\\tau}$ refers to an **incorrect** trajectory — that is, one where the final answer in $a_T$ is incorrect.\n\nWe will revise the paper to ensure this definition is clearly and consistently stated. \n\n---\n\n>**Q3: How is the correctness of a state defined?**  \n\n**A:**\n\nThank you for the reviewer’s insightful question. In Assumption 3.1, we follow the convention in [2], where state correctness is not explicitly defined per state but is implicitly captured by the quality of future outcomes. We will make this connection explicit in the revision.\n\n[2] *PROCESS REWARD MODEL WITH Q-VALUE RANKINGS, ICLR 2025.*\n\n---\n\n>**Q4: What is $\\pi$ in Equation (1)?  Is it PRM-guided beam search in this context?**  \n\n**A:**\nThank you for the question. In Equation (1), the *LLM policy* refers to the reasoning-capable LLM (in our setting, the Long CoT Model such as DeepSeek-R1-Distill-Qwen). We refer to it as a *policy* to align with our formulation in Section 2, where we model LLM reasoning as a Markov Decision Process (MDP).\n\nWe would like to clarify that the definition of *LLM policy* is independent of PRM-guided beam search. In other words, the *step quality* defined in Equation (1) is not based on the PRM-guided beam search procedure. Instead, it is defined under the context of letting the LLM directly generate.\n\n\n---\n\n>**Q5: Why doesn’t Figure 2 show a peak in step quality like Figure 2b?** \n \n**A:** We sincerely thank the reviewer for the question. Your understanding is absolutely correct — the empirical curves in Figure 2 are indeed expected to follow a similar pattern as the illustrative curve shown in Figure 1(b).\n\nWe would like to clarify that there do exist peaks in the curves of Figure 2, and these peaks typically occur at the second decoding step (i.e., around the 4k mark on the x-axis). However, these peaks are sometimes subtle and thus may be difficult to visually observe. That said, some curves do exhibit more prominent peaks, such as the statistics of the 1.5B model on the AIME24 dataset.\n\n---\n\n>**Q6: Why is beam size = 1 assumed in theoretical analysis? Isn’t that greedy search?**  \n\n**A:** \nWe thank the reviewer for the insightful question. You are absolutely right — setting the beam size to 1 is indeed equivalent to greedy search. We would like to clarify that this simplification is made purely for the ease of mathematical presentation and does not affect the overall problem formulation.\n\nIf the beam size is set to $N$, then in Equation (2), when computing the expectation of step quality, the expression\n\n\n$$ P^{\\pi} _ {\\text{BS}}(s _ t \\mid s _ 0) V^{\\pi}(s _ t) + P^{\\pi} _ {\\text{BS}}(\\bar{s} _ t \\mid s _ 0) V^{\\pi}(\\bar{s} _ t) $$\n\n\nshould be replaced with a sum over $N$ terms, i.e.,\n\n$$\n\\frac{1}{N} \\sum _{i=1}^{N} \\left( P^{\\pi} _ {\\text{BS}}(s _ t^i \\mid s _ 0) V^{\\pi}(s _ t^i) + P^{\\pi} _ {\\text{BS}}(\\bar{s} _ t^i \\mid s _ 0) V^{\\pi}(\\bar{s} _ t^i) \\right)\n$$\n\nwhere $s_t^i$ denotes the $i$-th beam candidate. The rest of the analysis and conclusions remain consistent under this more general form. We will annotate this point explicitly in the revised version for improved clarity and completeness.\n\n---\n\n### Final Remarks\n\nWe thank the reviewer again for the constructive review. We believe the revised paper better clarifies our contributions, improves alignment with related work, and resolves the open questions. We hope our responses and revisions address your concerns and demonstrate the significance of our findings."}, {"review_id": "i8Jhx4KadJ", "reviewer": "Reviewer_WZXW", "summary": "This paper studies the performance degeneration of Beam Search as the decoding step grows in searching for high-quality long CoT with a Process Reward Model (PRM). The authors define the step quality as the value of the state and estimate it using Monte Carlo simulation. Empirically, they observed that the step quality decreases significantly as the decoding step grows. They also theoretically show that the expected step quality is concave in the discrete sense.  To solve the degradation of step quality, the authors propose to use PRM scores as a proxy (based on a correlation analysis) and early terminate beam search when the z-score below a threshold. The merits of the proposed method are empirically verified.", "questions": "See my comments in Strengths And Weaknesses section", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think the authors do a very well job in presenting their core ideas. The problem to be solved is important, the analysis are intuitive and the claims are well supported, either empirically or theoretically. \n\nI have only some minor concerns regarding the paper. \n - First, although your method for early stopping is intuitive, it seems to have nothing to do with the theoretical results you have derived in Section 3.3. Can you shed some lights on how these results (especially Proposition 3.8) could be used in developing early stopping/pruning algorithms for BS or more generally, tree-search-based test-time scaling methods? \n - Second, note that the hyperparameter $\\lambda$ can be sensitive to the PRMs. One might need to tune case-by-case for different scenarios.\n - Third, I suggest the authors adding the results of token usages or the number of PRM calls, otherwise line 279-280 is not very well supported.\n\nSome minor presentation issues\n\n - line 23: O1 -> o1\n - line 46: insert a space after word \"concavity\"\n - line 85: it seems that $r_h$ should map to {$0,1$}, not $[0,1]$\n - Figure 5: the negative sign is too thin and almost invisible\n - How $\\lambda$ is set in your main results (Figure 4)?", "was_revised": true, "final_justification": "I am satisfied with authors' rebuttal. Therefore I maintained my score", "rebuttal": "**We sincerely thank the reviewer for their thoughtful comments, positive feedback, and constructive suggestions. Below we address each point in detail.**\n\n---\n\n### **Comment 1** Connection Between Theoretical Results and Early Stopping\n\nWe thank the reviewer for this insightful question. In Section 3.2, we observe the phenomenon of step quality degradation — namely, the expected step quality typically exhibits either a unimodal shape or a monotonically decreasing pattern. This empirical observation indicates that early stopping can be beneficial for the tasks considered in our experiments.  \n\nIn Section 3.3, we provide a theoretical explanation for this phenomenon. Specifically, `Proposition 3.8` establishes the concavity of step quality. As discussed in lines 209–212, both common forms of concave functions exhibit a peak, which offers theoretical support for early stopping. Combining this empirical evidence with our theoretical analysis naturally leads to our heuristic `ZGES` method.  \n\nRegarding your question on extending the theoretical insight beyond beam search to more general `tree-search-based test-time scaling methods`, we fully agree that this is a valuable direction. We are excited to report that we have already applied `ZGES` to a generalized form of beam search — `look-ahead search` (see our response to Reviewer egya, Weakness 1) — and found that `ZGES` consistently outperforms the standard look-ahead search. This suggests that the concavity of step quality revealed by our theory may be a general property, and we plan to further explore its theoretical implications for other forms of tree-search-based test-time scaling methods in future work.\n\n\n---\n\n### **Comment 2** Sensitivity of λ\n\nWe thank the reviewer for astutely pointing this out — we agree with your assessment. Indeed, hyperparameter tuning is a common challenge across most methods involving tunable parameters. We were aware of the potential sensitivity of our hyperparameter to PRMs, as you noted, and accordingly conducted a **sensitivity analysis** in Section 5.1 of the paper.\n\nSpecifically, we evaluated our method on both `1.5B` and `7B` models using different values of `λ` (-0.4, -0.6, -0.8, -1.0), and found that performance differences were **not significant** across these values (see Figure 5). This suggests that for both tested models, our method is relatively robust to `λ` within this range.\n\nAltogether, these experiments provide an initial empirical analysis of ZGES’s sensitivity to model scale, and suggest that the method exhibits **a degree of robustness**. We agree that developing **hyperparameter-free early stopping mechanisms** is an interesting and valuable future direction, and we leave this for future work.\n\n---\n\n### **Comment 3** Token Usage and PRM Calls\n\nWe thank the reviewer for the helpful suggestion, and we fully agree that including statistics on PRM call counts and token usage can strengthen the empirical justification of our claims in lines 279–280, thereby providing further evidence for the advantages of our method.\n\nFollowing your suggestion, we conducted additional analysis to report these statistics. The results are summarized as follows:\n| Model | Method   | AMC23 PRM Call | AMC23 Tokens Ratio | AIME24 PRM Call | AIME24 Tokens Ratio | AIME25 PRM Call | AIME25 Tokens Ratio |\n|:-----------:|:-----------:|:---------:|:------------:|:----------:|:-------------:|:----------:|:-------------:|\n| 1.5B| **ZGES (-0.4)** |   **3.08** ↓61%    |   **0.753**     |    **3.27** ↓66%    |   **0.929**     |    **3.33** ↓65%   |    **0.926**     |\n| 1.5B| **ZGES (-0.8)** |   **3.18** ↓60%    |   **0.763**     |    **3.42** ↓64%    |    **0.956**    |    **3.48**  ↓63%  |    **0.942**     |\n| 1.5B| Beam Search  |   7.91    |   ---     |    9.55    |    ---     |    9.53    |    ---     |\n| 7B| **ZGES (-0.4)**   |   **2.97** ↓56%    |   **0.675**     |    **3.31** ↓63%   |    **0.839**     |    **3.33** ↓62%    |    **0.905**     |\n| 7B| **ZGES (-0.8)**   |   **3.17** ↓53%    |   **0.692**    |    **3.54**  ↓61%  |    **0.856**     |    **3.58**  ↓59%  |    **0.911**     |\n| 7B| Beam Search    |   6.69    |   ---     |    9.00    |   ---     |    8.73    |    ---     |\n\n**Note:** \n1. `1.5B` represents the R1-Distill-Qwen-1.5B model, and `7B` represents R1-Distill-Qwen-7B.\n2. `ZGES(x)` denotes the ZGES method (applied to Beam Search) with λ set to x, while Beam Search refers to the standard Beam Search method.\n3. The `PRM Call` column shows the average number of PRM calls, and `Tokens Ratio` represents the average number of tokens generated by ZGES relative to Beam Search.\n\n\nWe can observe three interesting points:\n\n- Firstly, the experimental results strongly support the statement in lines 279-280 of our paper, namely that compared to the standard PRM-Guided Beam Search, the ZGES method can significantly reduce the number of PRM calls (by more than `50%`) without sacrificing performance, and even achieve better results (according to the experimental results in Section 4.3 of the paper).\n\n- Secondly, for the 1.5B or 7B models, we find that the smaller the value of `λ`, the more PRM calls are made. This is consistent with the theoretical prediction in Appendix C.1, where a smaller `λ` causes the stopping point to be delayed, resulting in more PRM calls.\n\n- Finally, we observe that from amc23 to aime25, as the difficulty of the problems increases, the number of PRM calls (for the ZGES method) also increases. We hypothesize that when the problem difficulty is higher, increasing exploration is beneficial.\n\n---\n\n### **Comment 4** Minor Presentation Issues\n\nWe appreciate your attention to detail and will address the following corrections in the revised version:\n\n- Line 23: \"O1\" → \"o1\"\n- Line 46: Add space after \"concavity\"\n- Line 85: Change the codomain of $ r _ h $ to  {0,1}\n- Figure 5: Fix the thin negative sign for better visibility\n- Clarify how $ \\lambda $ is set in Figure 4 (we will add this in the caption or appendix)\n\n**Regarding the final point**, we would like to clarify that in our main results (Figure 4), we chose a specific value of λ for each model: `λ` = -0.6 for the 1.5B model and `λ` = 0 for the 7B model. However, we would like to emphasize that, as we noted in our response to Comment 2, the performance is generally not highly sensitive to the choice of `λ`. That is, different `λ` values do not lead to significant differences in the results across models.\n\n---\n### **Once Again**\n\nWe thank the reviewer for their detailed and helpful review. We will incorporate all the above revisions to improve the clarity and rigor of our paper."}, {"review_id": "3UNiyvDiCZ", "reviewer": "Reviewer_NNk9", "summary": "First, this study has empirically found that the PRM quality during beam search degrades as step increases, making unimodal curve.\nTheoretical analysis also support the claim by deriving that the second order of the curve becomes minus value if we assume that the PRM’s re-ranking capacity gradually declines during beam search.\n\nSecond, it has proposed a method of early stopping beam search by setting the stopping trigger as the z-normalized PRM reward falling below a threshold. Experiments have demonstrated that the proposed method consistently outperform or competitive as the baseline methods (normal PRM beam search and self-consistency method), insisting the effectiveness of the proposed method.", "questions": "I would suggest that the authors update manuscripts to increase readability and clarity.\n- Figure1: This overview lacks lots of important information. First, there is no separate explanation for each of (a) and (b) in the caption. Second, The figure itself does not illustrate what to do after the early stopping (so readers cannot grasp the overall concept of the proposal at first glance). Third, there is no explanation in the caption/figure about what is \"locally normalized z-score\" and why it degrades as the steps increases. The explanation should not be detailed, but it should be simple but to the point.\n- \"Step quality\" is an important concept in this paper, but the detailed calculation approach was moved to Appendix B.2. It is better to describe it in Main page for readability.\n- Step 4 of the proposed method \"stop Beam Search early and directly decode from the candidates\": what kind of decoding strategy is used?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This study carefully observe the deficiency of PRM-based beam search and found that the cause of inferior performance was the consistent degradation of PRM quality as step increases. This finding is beneficial for the community.\n- The proposed method has shown to be effective across different size of models and multiple benchmarks, outperforming or competitive as major baselines.\n\nWeaknesses:\n- The theoretical analysis does not always support the claim that there exists unimodal peak. For instance, if the degradation happens at the begging step, the curve consistently decreases as step increases and there is no peak according to the theoretical consequence that second-order difference of the expected step quality is minus.\n- The proposed method is heuristic and not exciting, just early stopping the beam search.\n- Step 3 of the proposed method \"Compute the local z-score using the sequence of {x1, x2, ..., xt}\": In the early phase of the step, the size of the sequence is so small, so the normalized z-score becomes unstable.\n- Ideally, the baseline method should include manually annotated PRM approach to indicate an upper-bound of PRM.\n- I think there are some readability and clarity issues. Please see \"Questions\".", "was_revised": true, "final_justification": "I acknowledge that some of my concerns are resolved by the reply, but the core idea of the proposed method is heuristic and has less grounded on the finding theory of the degradation pattern of PRM, which may cause readers feel a gap between them (In a way, I feel like reading separated two papers though both of the sections are of good quality).\n\nHowever, after second consideration, my remaining concerns are trivial (i.e., if degradation occurs at the very beginning a unimodal pattern will not emerge, Local z-score is unstable in early steps, missing manually annotated PRM baseline), so I have raised my score from borderline reject to borderline accept.", "rebuttal": "**We sincerely thank the reviewer for the thoughtful and constructive comments. Below, we address each of your points in detail.**\n\n---\n\n### Weaknesses\n\n---\n\n>#### 1. **“Theoretical analysis does not always support the claim that there exists unimodal peak...”**\n\nWe thank the reviewer for this insightful observation. We agree that if degradation occurs at the very beginning, a unimodal pattern will not emerge. As clarified in our paper, step quality degradation can take two forms: unimodal and monotonically decreasing (see lines 135–136). Our theoretical analysis explicitly covers and explains both cases (see lines 205–212).\n\n---\n\n>#### 2. **“The proposed method is heuristic and not exciting...”**\n\nWe thank the reviewer for raising this point. However, we respectfully disagree that our method lacks novelty. Our contributions are as follows:  \n1. We investigated the step quality dynamics of PRM-guided Beam Search under the long CoT model setting and empirically demonstrated the existence of the step quality degradation phenomenon (to the best of our knowledge, we are the first to do so).  \n2. We provided a theoretical explanation for why this degradation occurs.  \n3. Based on both theoretical and empirical analysis, we proposed an adaptive early stopping method, ZGES, which is simple to implement yet achieves strong performance across multiple tasks and models. Moreover, it can be applied to more general search methods such as look-ahead search and outperforms baselines (see our response to Reviewer egya, Weakness 1). Therefore, our method is not limited to Beam Search but can broadly benefit search-based test-time scaling methods for LLM reasoning tasks.\n\n---\n\n>#### 3. **“Local z-score is unstable in early steps...”**\n\nWe appreciate your insight and the question raised. We acknowledge that statistical instability exists when the sample size is small. However, in our implementation, we apply a technique that sets a minimum early stopping step (e.g., set to 3), meaning ZGES will not perform early stopping before step 3, which effectively mitigates the instability issue. We will include this detail in the revised manuscript.\n\n---\n\n>#### 4. **“Missing manually annotated PRM baseline...”**\n\nWe appreciate the reviewer’s suggestion and agree that manually annotated data can provide a higher-quality PRM as an upper bound baseline.\n\nHowever, as noted in our response to Weakness 2, research on PRM-guided test-time scaling for long CoT models is limited, and no publicly available manually annotated PRM data exists for this setting.\n\nDue to the high cost of manual annotation, most methods rely on automatically annotated data, which better suits practical efficiency needs.\n\nWe will clarify this limitation in the revised manuscript and highlight developing high-quality manual PRMs as future work to improve performance and baseline comparisons.\n\n\n---\n\n### Questions and Clarity Issues\n\n---\n\n>#### Q1: *Figure 1 lacks clarity*\n\nWe thank the reviewer for these constructive comments. We agree that Figure 1 can be improved for clarity. In the revision, we will:  \n1. Provide separate, concise explanations for subfigures (a) and (b) in the caption.  \n2. Update the figure to illustrate the procedure after early stopping so that the overall method can be understood at a glance.  \n3. Add a brief explanation in the caption/figure about what the locally normalized z-score is and why it tends to decrease as the step count increases.\n\nWe believe these changes will make Figure 1 more self-contained and easier for readers to grasp the main idea.\n\n---\n\n>#### Q2: *Step quality definition relegated to Appendix*\n\nWe thank the reviewer for pointing this out. We agree that \"step quality\" is a key concept in our work and that describing its calculation in the main text would improve readability. In the revision, we will move a concise version of the calculation from Appendix B.2 to the main paper, while keeping the full details in the appendix for completeness.\n\n---\n\n>#### Q3: *Step 4 decoding strategy*\n\nWe thank the reviewer for the question. In Step 4, after early stopping, we decode from the remaining candidates using **nucleus sampling (top‑p)** with `p = 0.95`. The temperature is set to `0.6` for the 1.5B model and `1.0` for the 7B model."}]

Author rebuttal:

Meta-review: The paper identifies and analyzes a deficiency of process reward model (PRM)-based beam search, showing that it arises from the degradation of PRM quality as the search step increases. To address this issue, the authors propose a Z-score guided early stopping algorithm and demonstrate its performance benefits. The contribution is timely and interesting. Some concerns, as noted by the reviewers, remain. For example, comparisons with additional existing PRM baselines would strengthen the work. Overall, the strengths outweigh the weaknesses, and I recommend acceptance. I also encourage the authors to incorporate the reviewers’ comments into the camera-ready version.
Decision: Accept (poster)