Reasoning Is Not a Race: When Stopping Early Beats Going Deeper

We sincerely thank the reviewer for the thoughtful and constructive comments. Below, we address each of your points in detail.

---

Weaknesses

---

1. “Theoretical analysis does not always support the claim that there exists unimodal peak...”

We 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).

---

2. “The proposed method is heuristic and not exciting...”

We thank the reviewer for raising this point. However, we respectfully disagree that our method lacks novelty. Our contributions are as follows:

1. 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).
2. We provided a theoretical explanation for why this degradation occurs.
3. 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.

---

3. “Local z-score is unstable in early steps...”

We 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.

---

4. “Missing manually annotated PRM baseline...”

We appreciate the reviewer’s suggestion and agree that manually annotated data can provide a higher-quality PRM as an upper bound baseline.

However, 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.

Due to the high cost of manual annotation, most methods rely on automatically annotated data, which better suits practical efficiency needs.

We will clarify this limitation in the revised manuscript and highlight developing high-quality manual PRMs as future work to improve performance and baseline comparisons.

---

Questions and Clarity Issues

---

Q1: Figure 1 lacks clarity

We thank the reviewer for these constructive comments. We agree that Figure 1 can be improved for clarity. In the revision, we will:

1. Provide separate, concise explanations for subfigures (a) and (b) in the caption.
2. Update the figure to illustrate the procedure after early stopping so that the overall method can be understood at a glance.
3. 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.

We believe these changes will make Figure 1 more self-contained and easier for readers to grasp the main idea.

---

Q2: Step quality definition relegated to Appendix

We 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.

---

Q3: Step 4 decoding strategy

We 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.

We sincerely thank the reviewer for their thoughtful comments, positive feedback, and constructive suggestions. Below we address each point in detail.

---

Comment 1 Connection Between Theoretical Results and Early Stopping

We 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.

In 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.

Regarding 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.

---

Comment 2 Sensitivity of λ

We 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.

Specifically, 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.

Altogether, 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.

---

Comment 3 Token Usage and PRM Calls

We 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.

Following your suggestion, we conducted additional analysis to report these statistics. The results are summarized as follows:

Note:

1. 1.5B represents the R1-Distill-Qwen-1.5B model, and 7B represents R1-Distill-Qwen-7B.
2. ZGES(x) denotes the ZGES method (applied to Beam Search) with λ set to x, while Beam Search refers to the standard Beam Search method.
3. 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.

We can observe three interesting points:

• 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).

• 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.

• 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.

---

Comment 4 Minor Presentation Issues

We appreciate your attention to detail and will address the following corrections in the revised version:

• Line 23: "O1" → "o1"
• Line 46: Add space after "concavity"
• Line 85: Change the codomain of $r _ h$ to {0,1}
• Figure 5: Fix the thin negative sign for better visibility
• Clarify how $\lambda$ is set in Figure 4 (we will add this in the caption or appendix)

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.

---

Once Again

We 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.

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.

---

Clarity Issues

Comment:
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.

Response:
Thank you for your openness. Specific clarifications are addressed in responses to your detailed questions below.

---

Related Work on Early Stopping

Comment:
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.

Response:
We 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.

In 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.

We will add a discussion of these works in the Related Work section.

---

Minor Comments

Comment:
Figure 6 legend covers most of the plot.

Response:
Thank you for pointing that out. We will correct the occlusion of the Figure 6 legend in the revised version of the paper.

Comment:
Lines 236–244 include a proof but no explicit theorem statement.

Response:
We 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.

Comment:
"Concave in the discrete sense" – why not use "submodular"?

Response:
We sincerely thank the reviewer for this thoughtful comment. We agree that submodularity is the standard discrete analogue to concavity, and we appreciate the suggestion.

In our work, the step quality function is defined over a one-dimensional discrete time index$t \in \{1, 2, \ldots, T\}$ , 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.

Specifically, we refer to functions $f$ defined on integers $t$ satisfying the discrete concavity condition:

$$f(t+1) - f(t) \leq f(t) - f(t-1)$$

which parallels the classical second-derivative criterion for concavity in continuous settings.

That 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.

Comment:
Define Majority@N clearly – no citation provided.

Response:
Thank you for the helpful suggestion. We would like to clarify the Majority@N strategy (also known as self-consistency): Formally, let the model generate a set of answers $\{a_1, a_2, \ldots, a_N\}$. The final prediction is:

$$\hat{a} = \arg\max_{a \in \{a_1, \ldots, a_N\}} \text{Count}(a)$$

i.e., the most frequent answer among the N samples. To enhance the clarity and readability of the paper, we will add a formal definition of Majority@N in the revised version.

---

Responses to Specific Questions

Q1: In the experiment in Section 4.3: How did you define the stopping criterion for the baselines?

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.

---

Q2: What is $\tau$ in Assumption 3.1?

A: Thank you very much for your valuable question. In 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.,

$$\tau = \{a_1, a_2, \ldots, a_T\},$$

where $a_T$ (the final step) typically contains the model's predicted answer.

As we mention in Section 3.3, we would like to emphasize that under Assumption 3.1:

• A trajectory denoted as $\tau$ refers to a correct trajectory — that is, one where the final answer in $a_T$ is correct.
• A trajectory denoted as $\bar{\tau}$ refers to an incorrect trajectory — that is, one where the final answer in $a_T$ is incorrect.

We will revise the paper to ensure this definition is clearly and consistently stated.

---

Q3: How is the correctness of a state defined?

A:

Thank 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.

[2] PROCESS REWARD MODEL WITH Q-VALUE RANKINGS, ICLR 2025.

---

Q4: What is $\pi$ in Equation (1)? Is it PRM-guided beam search in this context?

A: Thank 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).

We 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.

---

Q5: Why doesn’t Figure 2 show a peak in step quality like Figure 2b?

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).

We 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.

---

Q6: Why is beam size = 1 assumed in theoretical analysis? Isn’t that greedy search?

A: We 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.

If the beam size is set to $N$, then in Equation (2), when computing the expectation of step quality, the expression

$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)$

should be replaced with a sum over $N$ terms, i.e.,

$$\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)$$

where $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.

---

Final Remarks

We 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.

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.

---

Weakness 1. Contradiction with prior PRM literature & generality of ZGES

We 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.

We 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.

To 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.

Note:

• Look Ahead Search refers to the standard PRM-Guided Look Ahead Search without early stopping.
• ZGES(x) denotes the ZGES method (used for Look Ahead Search) with λ set to x.

The 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:

1. ZGES demonstrates strong generalizability and can adapt to more general search algorithms.
2. 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.

---

Weakness 2. Lack of PRM training and accuracy analysis

Thank 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.

---

Weakness 3. Limited domains (only math reasoning)

We 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:

Note:

• Beam Search refers to the standard PRM-Guided Beam Search without early stopping.
• ZGES(x) denotes the ZGES method (used for Beam Search) with λ set to x.

---

Weakness 4. Missing details on step segmentation

We 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.

[1]: AdaptiveStep: Automatically Dividing Reasoning Steps through Model Confidence, ICML 2025.

---

5. Minor typo

Thank 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

---

Summary

We 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.