Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning

We sincerely appreciate the insightful and constructive feedback provided in your reviews. Below, we address each concern in detail.

The General Linkage between MI Decay and Reasoning Errors

We formalize the reasoning process of LLMs as a planning-execution framework. Given a question, as illustrated in Fig.1, an LLM first plans a potential reasoning path, thereby generating implicit thoughts ($t$). Subsequently, the LLM attempts to execute the tasks specified in these thoughts, producing the observable responses ($r$).

In this work, our primary focus is analyzing the probability of correct reasoning, particularly examining error propagation in the execution phase under external search—where search algorithms are guided by external mechanisms (e.g., an auxiliary value model). By contrast, the "self-correction" capability (or reflection) primarily arises from the model’s internal reasoning ability. Specifically, the model autonomously detects potential errors and restarts the execution process from an earlier step.

The internal reflection mechanism constitutes the key distinction between external and internal slow-thinking methods.

• External slow-thinking methods rely on width-expansion, broadening the search space.
• Internal slow-thinking methods leverage reflection, enabling recovery from intermediate states.

We intend to conduct further analyses on the reflection mechanism in future work, where it can be rigorously modeled as a form of error accumulation with inherent trade-offs in error detection. Additional discussion on this topic can be found in our response to Reviewer Qdus (Section: Extension to AoT and AoT+).

Additionally, extra experiments have been conducted to verify the relationship between the MI, accuracy and lengths. The results are presented through an anonymized repository (https://anonymous.4open.science/r/extra-experiments-0E75/README.md), the Analysis by Difficulty section. We also kindly refer you to our discussion with reviewer Qdus (section "The Snowball Error and the Length") for contexts of this additional verification.

We thank you for your valuable suggestions and will enhance the clarity and comprehensiveness of our manuscript in the revised version.

The Universality of Snowball Error Dynamics across All Slow-Thinking Methods

As discussed in the previous section, while Best-of-N (BoN) and Monte Carlo Tree Search (MCTS) employ distinct search strategies, they share a fundamental similarity: both expand the search space under external value guidance. Consequently, they qualify as external slow-thinking methods, aligning with our analytical framework. From this perspective, any search strategy based on width expansion falls within the scope of our theoretical results.

Moreover, we believe our findings can extend to other slow-thinking paradigms, including internal slow-thinking (reflection-based) and implicit reasoning methods. For a more detailed discussion, please refer to our response to Reviewer Qdus (Section: Extension for More Test-Time Scaling Methods).

Detailed Explanation of Figure 2

We sincerely appreciate your thorough evaluation of Figure 2. Below, we simply summarize the key experimental settings (additional details will be provided in the appendix in the revised version):

1. Prompting & Inference:
   • Models are prompted (see Appendix B.1) to generate step-by-step reasoning.
   • Observed answers ($r$) and implicit thoughts ($t$, derived from ground-truth rewrites) are collected.
2. Mutual Information (MI) Estimation:
   • Following prior work, we compute and estimate the MI between $r$ and $t$.
   • Each question’s result is plotted as a blue dot in Figure 2.
3. Reasoning Quality Evaluation:
   • An outcome reward model assesses reasoning correctness.
   • The relationship between MI and reasoning quality is fitted to produce the final curve in Figure 2.

In the camera-ready version, we will elaborate on Appendix B.1 as per your suggestion to improve clarity.

We sincerely appreciate your valuable feedback. Below, we address your concerns point by point.

Regarding Prior Work [1]

While our work is inspired by [1], and both employ information theory to analyze chain-of-thought (CoT) reasoning, there are significant distinctions between our approaches.

The primary focus of [1] aligns with process reward models (PRMs) [2], which seek to evaluate the quality of intermediate reasoning steps. To achieve this, [1] leverages information-theoretic metrics to estimate information gain as supervisory signals. In contrast, our work aims to provide a theoretical foundation for understanding the mechanism of multi-step reasoning in LLMs.

We consider the former peer reviews of [1] for further discussion. The major concerns raised in [1]’s ICLR 2025 rebuttal (https://openreview.net/forum?id=ouRX6A8RQJ) primarily revolve around experimental design, whereas its theoretical formulation was generally praised. From the theoretical perspective, our paper is not a direct extension of [1]; a potential overlap lies in modeling CoT as a task-execution process, but our formulations differ substantially.

Specifically, we overcome several limitations of [1]:

• [1] relies on complex concepts (e.g., primitive tasks) and assumes identifiable tasks as combinations thereof. In contrast, we formulate reasoning as a transparent planning-execution process, bridging implicit thoughts to observable responses.
• [1] introduces additional assumptions (e.g., Bayesian networks) to model reasoning errors, whereas our framework is derived from simpler formulation and information-theoretical foundations (e.g. Fano’s inequality), culminating in Theorem 3.3, which establishes a clear lower bound with fewer assumptions.

In summary, our work diverges from [1] in scope, reasoning formulation, and error modeling. Although both studies build upon information theory, we argue that they contribute distinct perspectives. We hope this clarification enhances the understanding of our paper’s novel contributions.

[1] Ton, J. F., Taufiq, M. F., & Liu, Y. (2024). Understanding Chain-of-Thought in LLMs through Information Theory. arXiv preprint arXiv:2411.11984.

[2] Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., ... & Cobbe, K. (2023, May). Let's verify step by step. In The Twelfth International Conference on Learning Representations.

Regarding LaTeX Formatting

We confirm that our manuscript adheres to ICML 2025’s LaTeX template (https://icml.cc/Conferences/2025/AuthorInstructions), ensuring compliance with formatting guidelines.

Clarifying the Paper’s Structure

Thank you for your inquiry about the connection between the two aspects of our paper. Below, we provide a detailed explanation:

Overall, the structure of our paper can be divided into 2 parts:

1. Part 1 (Secs. 2–3): We analyze "snowball errors" and their relationship with reasoning errors. Theorem 3.3 formalizes this, with $H_{<l}(t|r)$ quantifying error accumulation—analogous to a snowball growing in size.
2. Part 2 (Secs. 4–6): Leveraging reasoning error probabilities, we theoretically analyze scaling methods (Theorem 4.6, Table 1, Figure 3). As noted in Line 270, correct reasoning is framed probabilistically (generation + selection), with external strategies (e.g., width expansion) aligning with variables $k$ and $b$.

For Part 1: The key theoretical insight (Theorem 3.3) formalizes "snowball errors"—minor inaccuracies in early reasoning steps that amplify over subsequent steps, analogous to how a snowball grows when rolled. This is quantified via conditional entropy $H_{<l}(t|r)$, which captures the compounding effect of errors. An intuitive analogy is provided in Sec.2 (~Line 104).

For Part 2: Theorem 4.6, Table 1, and Figure 3 analyze test-time scaling methods. We frame correct reasoning probabilistically, decomposing it into generation (producing candidate solutions) and selection (identifying the optimal one), as elaborated in Line 270. External slow-thinking methods relying on width expansion align with our theoretical variables $k$ and $b$, offering a principled justification for their efficacy.

For better illustration, We are happy to incorporate these intuitive explanations more prominently in the revised manuscript to improve clarity. We also hope our response can address your misunderstanding of our works and reconsider our contributions!

We sincerely appreciate your valuable feedback. Below are our responses to the concerns raised.

About the Probability that the Thoughts are Incorrect

Our theoretical analysis hinges on the framework presented in Fig.1, where we model the LLM reasoning process as a planning-execution mechanism. Given a question, the LLM first plans potential reasoning paths, generating implicit thoughts ($t$), before executing the tasks in these thoughts to produce responses ($r$).

We primarily focus on error propagation in the execution phase, which is justified because correct planning is a prerequisite for correct reasoning—planning errors inherently lead to incorrect results. However, empirical evidence suggests that even highly capable models can still commit errors during execution, which is our primary analytical focus.

We will improve presentation clarity in the revision.

About the Formulation of Intermediate Error

We explicitly recognize that a single mistake in the sequence can lead to incorrect output, which is naturally included in our setting. Our formulation captures how snowball errors accumulate across reasoning steps ($l$), ultimately exceeding a threshold and causing reasoning failure. In other words, snowball errors accumulate incrementally, while reasoning errors directly emerge from excessive accumulation.

Our formulation does consider the influence of prior steps. Step $l$ in our framework accounts for prior influences through prior snowball errors (or information loss), as defined in Definition 2.2. Furthermore, Theorem 3.3 evaluates reasoning error probability at each step $l$, explicitly linking it to accumulated errors from previous steps. Thus, our analysis operates at a step-level granularity, not merely aggregating errors over all steps.

About the Results of Theorem 3.3

Theorem 3.3 actually establishes a lower bound for reasoning error probability $e_l$ at step $l$. As snowball errors accumulate with increasing $l$, the error probability rises accordingly.

This result is empirically verified by Fig.2 from two aspects.

• Mutual information decreases (snowball error increases) with $l$ (Definition 2.1 & 2.2).
• Response quality degrades with decreased MI.

Additional experimental verification is available in our anonymous repository: https://anonymous.4open.science/r/extra-experiments-0E75/README.md, we kindly refer you to the Analysis by Difficulty section, also in our discussion with reviewer Qdus (section "The Snowball Error and the Length"). We will incorporate these supplemental results in our revision.

About the Results of Lemma 4.4

We understand your concerns may be about lemma 4.4 and will respond from the following two aspects:

1. The assumptions. Proposition 4.3 facilitates clarity and subsequent analyses (Sec 4.2, line 214). Our results generalize to any scenario where $\operatorname{Pr}\left[|\phi(r_l)-\phi(r_l^*)| \leq \tau\right]$ decreases monotonically with $l$. We kindly refer you to our discussion with reviewer yYwM (section "Lack of Empirical Verification for Proposition 4.3").
2. Further illustration for Lemma 4.4. The "$\leq$" in 4.4 originates from the operator "$\operatorname{min}$" in Proposition 4.3, where the single-step correct reasoning probability is controlled by a constant $\lambda_\tau$. While initially loose for small $l$, the bound tightens as $l$ increases, especially when $\lambda_\tau e^{-l} < 1$, reflecting rapidly increasing error probabilities in later reasoning steps.

Experiments for Theorem 4.6

We take theorem 4.6, which is a main result in our paper and lemma 5.x are its derivations, for the subsequent response.

Theorem 4.6 relates reasoning cost ($k$), length ($L$), and value function reliability ($\epsilon_b$) to the upper bound of correct reasoning probability.

For $L$:

The impact of reasoning length has been implicitly verified through:

• Analysis by Difficulty section in our repository.
• Fig. 2 results.

This evidence confirms that longer paths increase errors.

For $k$ and $\epsilon_b$:

We empirically validate $k$'s impact through RAP-like MCTS experiments [1]. See section Influence of $k$ in our repository. Results show improved reasoning accuracy with increased $k$. And the $\epsilon_b$ effect manifests in PrOntoQA's faster accuracy improvement versus GSM8k due to its simpler nature.

Besides, many external slow-thinking methods (listed in our related works) have empirically verified that increasing the cost in inference time can improve the model's reasoning capability, a.k.a. test-time scaling laws.

[1] AlphaZero-like tree-search can guide large language model decoding and training (ICML 2024).

While simplifying CoT formulations, our work provides essential foundations for execution-error analysis—a crucial first step acknowledged by other reviewers. We appreciate your recognition of this focused contribution.

We sincerely appreciate your valuable feedback and constructive comments. Below, we provide point-by-point responses to address the raised concerns.

The Snowball Error and the Length

We acknowledge your insightful observation that the length of responses could be correlated with question difficulty, beyond just snowball errors. This perspective significantly enriches the interpretation of our findings.

To validate our claims in scenarios where solution length does not necessarily correlate with solution difficulty, we have conducted additional experiments analyzing mutual information (MI) and accuracy across different difficulty levels. These experiments were performed on the MATH-500 dataset [1], where questions are categorized into five difficulty levels (Level 1 being simplest, Level 5 most difficult), with questions at each level sharing comparable difficulty.

The experimental results are available in our anonymized repository (https://anonymous.4open.science/r/extra-experiments-0E75/README.md), particularly in the Analysis by Difficulty section.

Moreover, this finding aligns with recent literature. For instance, [2] demonstrates that excessively long CoT reasoning can harm solution accuracy, a phenomenon referred to as overthinking [3].

[1] Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., ... & Cobbe, K. (2023). Let's verify step by step. ICLR.

[2] Wu, Y., Wang, Y., Du, T., Jegelka, S., & Wang, Y. (2025). When More is Less: Understanding Chain-of-Thought Length in LLMs. arXiv:2502.07266.

[3] Sui, Y., et al. (2025). Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models. arXiv:2503.16419.

Extension to AoT and AoT+

We appreciate the suggestion to explore extensions to AoT and AoT+. We would like to address this from two perspectives:

1. External vs. Internal Slow-Thinking: While AoT primarily utilizes ICL to teach algorithms to LLMs, the introduction of specialized instances enables new capabilities like reflection. This makes AoT more akin to internal slow-thinking approaches, whereas our current focus is on external slow-thinking methods.

2. Reflection Mechanism: However, we are actively planning to incorporate reflection mechanisms in subsequent work, as mentioned in later sections of this response. We believe this extension will substantially enhance the impact of our future research.

Typos in Proposition 4.3

After careful consideration, we believe Proposition 4.3 is mathematically sound.

We would like to highlight Definition 4.1, where the left-hand item in Proposition 4.3 represents the probability of generating a correct reasoning step, which contrasts with Theorem 3.3 and the statements in line 213 (the probability of errors). We will improve the clarity of this presentation in our revised manuscript.

Extension for more Test-Time Scaling Methods

Our primary focus remains on external search methods, where we believe similar width-expansion strategies can be readily extended. Additionally, we have identified two other noteworthy test-time scaling approaches:

1. Internal Slow-Thinking. As introduced in our paper (Line 32), these methods employ training and parameter updates to enable long-CoT capabilities (e.g., DeepSeek-R1). The key differentiator appears to be reflection mechanisms, allowing models to detect and correct reasoning errors. By formalizing reflection, our framework could extend to understanding internal slow-thinking methods. One possible formulation can be built on the fact that reflection can reset the snowball error and thus obtain better results, with some trade-offs to detect the potential reasoning error. This extension could significantly enhance our findings' broader implications.
2. Implicit Reasoning. This emerging paradigm [4-6] scales inference through looped computations rather than additional token generation. Our results may generalize to illustrate implicit reasoning benefits by formalizing error propagation in these looped structures.

[4] Tack, J., et al. (2025). LLM Pretraining with Continuous Concepts. arXiv:2502.08524.

[5] Chen, Y., et al. (2025). Inner thinking transformer: Leveraging dynamic depth scaling to foster adaptive internal thinking. arXiv:2502.13842.

[6] Yu, Q., et al. (2025). Enhancing Auto-regressive Chain-of-Thought through Loop-Aligned Reasoning. arXiv:2502.08482.

We believe these responses adequately address all concerns raised. We greatly appreciate your time and constructive feedback.

We sincerely appreciate the thorough and constructive reviews. Below we address each concern raised by the reviewers.

Concerns about the Assumptions

We note your thoughtful concerns regarding our methodological assumptions, specifically concerning: (1) the coverage of multiple valid reasoning paths, (2) the impact of error propagation, and (3) the single gold-standard path assumption ($r_l^{*}$) presented in Section 4. We address each point systematically.

Response to (1): We would like to clarify our conceptual framework (and apologize for any lack of clarity in the current manuscript). Our model treats LLM reasoning as a two-phase process: planning and execution. Given a question, The planning phase generates implicit thought sequences ($t$ in Fig.1), while the execution phase produces the observable responses ($r$). While we acknowledge multiple paths may lead to correct solutions, our analysis intentionally focuses on error probabilities within individual execution paths. More specifically, though multiple reasoning paths can lead to the answer, we focus on one specific path and discuss the errors and probabilities on this exact path.

Response to (2): We completely agree that earlier errors typically have greater cumulative impacts. However, our theoretical contribution (Theorem 3.3) specifically examines the initial error occurrence probability rather than its propagation effects. This focused analysis provides fundamental insights into the first-error statistics during reasoning chains.

Response to (3): Within our execution-phase modeling framework, where reasoning sub-tasks are pre-determined during planning, the gold-standard response assumption ($r_l^{*}$) remains both theoretically sound and practically meaningful for our analytical purposes.

Another possible concern of our setting could be the explanation of the "reflection" mechanism in many modern LLMs, A detailed discussion of its relationship to MI decay appears in our response to Reviewer NREt (Section "The General Linkage between MI Decay and Reasoning Errors"), which we respectfully refer you to for complementary analysis.

More Experiments

We appreciate the reviewer's suggestions for expanded experimental validation and are pleased to provide additional empirical evidence or explanations as follows.

1. Extra Benchmark Task: Game of 24. We conducted verification experiments using the Game of 24 benchmark ([1]), which requires solving arithmetic puzzles to obtain the number 24. Our results demonstrate consistent patterns in Figure 3:

where $N_{res}=6.08,N_{call}=18.24$, and baseline MCTS obtain an accuracy of 64.80%. This result illustrates a similar conclusion to Fig.3, when the total reasoning cost is comparable, BoN can achieve a comparable and even better performance than MCTS.

2. Larger LLMs. Beyond the 7B/8B models in Figure 2, we include additional validation on Qwen2.5-14B-Instruct and Qwen2.5-32B-Instruct. Results are available in our anonymous repository: https://anonymous.4open.science/r/extra-experiments-0E75/README.md, the Larger LLMs section.

3. Alternative Search Algorithms. We categorize existing approaches into:

• Non-tree-based methods (such as AoT): These methods typically incorporate reflection mechanisms that currently fall outside our theoretical framework focused on width-expansion limitations in tree-based methods. Alternatively, we discuss potential extensions to model reflection in our response to Reviewer Qdus (section "Extension for more Test-Time Scaling Methods"). We believe this will be an interesting extension of our future work. Thanks for your valuable advice!
• Tree-based methods (BFS, DFS, ToT, etc.): As demonstrated in [1,2], since MCTS are designed as a series of operations including "Selection, Expansion, Simulation and Backpropagation", MCTS has higher probability to select more valuable intermediate thoughts in practice. Thus, for a given total reasoning cost, MCTS usually outperforms naive tree-based methods, as shown in the results of [2]. When it comes to Fig.3, other existing tree-based methods will thus be a baseline lower than MCTS's, and leading to trival results. Hence, we choose MCTS as the sota baseline of the tree-based methods.

[1] Tree of thoughts: Deliberate problem solving with large language models (NeurIPS 2023).

[2] AlphaZero-like tree-search can guide large language model decoding and training (ICML 2024).

Essential References Not Discussed

We appreciate your suggested references and will incorporate them in our revision.

We sincerely appreciate your valuable feedback. Below are our point-by-point responses:

Lack of Empirical Verification for Proposition 4.3

Proposition 4.3 was designed to facilitate subsequent analyses (Sec 4.2, line 214) while maintaining readability. The negative exponential form provides a simple yet effective characterization of accuracy decay. Below, we address this concern comprehensively by demonstrating (1) the theoretical robustness of our results under a relaxed assumption and (2) empirical validation of the key relationship between accuracy and length.

(1) First, we would like to prove that our main results remain valid under a weaker assumption when $\operatorname{Pr}\left[|\phi(r_l)-\phi(r_l^*)| \leq \tau\right]$ decreases monotonically with $l$.

To address your concern, we relax the original assumption and demonstrate that our core results hold under a more general condition:

Relaxed Proposition 4.3:

Instead of requiring $\operatorname{Pr}\left[|\phi(r_l)-\phi(r_l^*)| \leq \tau\right] = \operatorname{min} \left(\lambda_\tau e^{-l},1 \right)$, we now assume only that the left-hand side decreases monotonically with $l$ and converges to $0$, i.e.,

$\operatorname{Pr}\left[|\phi(r_l)-\phi(r_l^*)| \leq \tau\right] = \operatorname{min} \left( \xi(l,\tau),1 \right),$

where $\xi(l,\tau) \geq 0$ decreases monotonically with $l$ and converges to $0$.

Under this weaker condition, we derive revised bounds presented in the bullet list below:

• Lemma 4.4: $\xi^{L}(l,\tau)$,
• Lemma 4.5: $\prod_{l=1}^{L}\epsilon_b \left[ 1-\left( 1-\xi(l,\tau) \right)^k \right]$,
• Theorem 4.6: $\epsilon_b^L k^L \xi^{L}(l,\tau)$,
• Lemma 5.1: $\epsilon_N N^L \xi^{L}(l,\tau)$,
• Lemma 5.2: $\epsilon_b^L b^L \xi^{L}(l,\tau)$,
• Lemma 5.3: $b^{\frac{L(L+1)}{2}}\xi^{L}(l,\tau)\prod_{l=1}^{L}\epsilon_{b^l}$,

where $\xi^{L}(l,\tau) := \prod_{l=1}^{L}\xi(l,\tau)$.

These modifications preserve the validity of Corollary 5.4, Corollary 5.5, and Table 1, confirming that our theoretical insights are robust even without the original exponential form in Proposition 4.3.

(2) Second, we have conducted extra empirical verifications of the relationship between the accuracy and the length. We provide additional experimental verification (anonymous repository: https://anonymous.4open.science/r/extra-experiments-0E75/README.md, see Analysis by Difficulty section). The results confirm that accuracy generally decreases with $l$ within the same difficulty level, exhibiting faster decay in early stages that gradually stabilizes. We also kindly refer you to our discussion with Reviewer Qdus (section "The Snowball Error and the Length"), which provides additional context on this verification.

LLMs in Different Sizes

We appreciate your suggestion regarding additional experiments with varying model sizes. In response to this valuable feedback, we have conducted extensive analyses on larger language models (Qwen2.5-14B-Instruct and Qwen2.5-32B-Instruct) in addition to the 7B/8B models presented in Figure 2.

The complete experimental results are also available in our anonymous repository: https://anonymous.4open.science/r/extra-experiments-0E75/README.md, we kindly refer you to the Larger LLMs section. We maintained identical experimental settings and workflow as described in Figure 2 to ensure methodological consistency.

Our key findings from these additional experiments demonstrate that:

• The MI (Mutual Information) decay pattern remains consistent across larger model sizes, exhibiting similar behavior to smaller models.
• Response quality continues to show a negative correlation with output length, as observed in our original experiments.

These significant findings will be systematically incorporated into our revised manuscript, including comprehensive analysis for the extra results and corresponding updates to Figures/Tables.

Typos and Figure Ticks

We thank the reviewer for these careful observations. All typos will be corrected and Fig.3's tick marks will be adjusted to integer values in the final version.

We believe these responses adequately address all concerns raised. We greatly appreciate your time and constructive feedback.