Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
Authors: Zeyu Gan
Yun Liao
Yong Liu
Venue: ICML 2025 poster (2025)
Keywords: large language models
test-time scaling
information theory
Primary area: deep_learning->large_language_models
TL;DR: This paper theoretically analyzes external slow-thinking methods in LLMs, linking snowball errors to reasoning accuracy and providing insights to enhance the interpretability of existing approaches.

Abstract: Test-time scaling, which is also often referred to as *slow-thinking*, has been demonstrated to enhance multi-step reasoning in large language models (LLMs). However, despite its widespread utilization, the mechanisms underlying slow-thinking methods remain poorly understood. This paper explores the mechanisms of external slow-thinking from a theoretical standpoint. We begin by examining the snowball error effect within the LLM reasoning process and connect it to the likelihood of correct reasoning using information theory. Building on this, we show that external slow-thinking methods can be interpreted as strategies to mitigate the error probability. We further provide a comparative analysis of popular external slow-thinking approaches, ranging from simple to complex, highlighting their differences and interrelationships. Our findings suggest that the efficacy of these methods is not primarily determined by the specific framework employed, and that expanding the search scope or the model's internal reasoning capacity may yield more sustained improvements in the long term. We open-source our code at https://github.com/ZyGan1999/Snowball-Errors-and-Probability.

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
Zeyu Gan 123
Yun Liao
Yong Liu 123
Abstract
of LLMs improves with the growth of model size and train- ing data. Over the past few years, the trend in this field has been toward expanding the scale of training phase, result- ing in significant performance improvements (Yuan et al., 2023; Zelikman et al., 2022; Rafailov et al., 2024). How- ever, the marginal gains model performance diminish as scale increases, and training more powerful models necessi- tates substantial rise in investment. Consequently, recent researches have shifted focus to scaling strategies beyond model size, including optimizations during the post-training phase and even at the test-time stage (Snell et al., 2024).
Test-time scaling, which is also often referred to as slow-thinking, has been demonstrated to enhance multi-step reasoning in large language models (LLMs). However, despite its widespread utilization, the mechanisms underlying slow- thinking methods remain poorly understood. This paper explores the mechanisms of external slow-thinking from theoretical standpoint. We begin by examining the snowball error effect within the LLM reasoning process and connect it to the likelihood of correct reasoning using information theory. Building on this, we show that external slow-thinking methods can be interpreted as strategies to mitigate the error probability. We further provide comparative analysis of popular external slow-thinking approaches, ranging from simple to complex, highlighting their differences and interrelation- ships. Our findings suggest that the efficacy of these methods is not primarily determined by the specific framework employed, and that expanding the search scope the model's internal reasoning capacity may yield more sustained improvements in the long term. We open-source our code at https: bttps://githuu Snowba 1 1-Err-----r-are Pro.aniidddobbbbbr........
Following the release of LLMs with remarkable reason- ing capabilities, such as OpenAl's ol (2024), DeepSeek's R1 (2025), and Qwen's QwQ (2024b), it has become widely acknowledged that scaling the inference process of LLMs offers promising avenue for further enhancing model per- formance. Specifically, empirical studies have shown that the reasoning quality of LLMs improves with extended in- ference time (Lightmaan al., 2023). This observation has sparked new research trajectory focused on augmenting the reasoning abilities of LLMs by increasing inference costs during the test-time phase, concept referred to as test-time scaling, or more colloquially, slow-thinking.
Test-time scaling strategies can be generally classified into two primary approaches: internal and external slow- thinking (Jiang et al., 2024; Min et al., 2024). Internal slow-thinking involves adjusting model parameters through additional training on specifically designed reasoning tasks, aiming to inherently extend the model's output length and thereby enhance its reasoning capabilities. In con- trast, external slow-thinking focuses on increasing infer- ence costs by introducing additional computational steps, such as re-sampling or re-generating model outputs multiple times (Brown et al., 2024), thereby prolonging inference time and improving reasoning quality.
1. Introduction
Scaling laws (Kaplan al., 2020) have been widely ac- cepted guiding principle in the development of large language models (LLMs), indicating that the performance
"Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China Beeijigg Key Laboratory of Research on Large Models and Intelligent Governance "Enginerrin Research Center of Nexi-Generation Intelligent Search and Recommenda- tion, MOE 'College of Artificial Intelligence, Tianjin University of Science and Technology, Tianjin, China. Correspondence to: Yong Liu <liuyonggsaie @ ruc.edu.en>>
This paper focuses on external slow-thinking techniques, which are inspired by human cognitive processes. When facing complex questions, humans often take extra time to reflect and refine their intermediate answers, leading to greater accuracy. Similarly, external slow-thinking methods, such as the Best-of-N (BoN) strategy, draw multiple sam- ples and evaluate them using techniques like majority voting
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
Real World
Training Data
Representation
Projection
Machine Leurning
(a) The Platonic Representation Hypothesis
T
Evaluation
X
Implicit Thoughts
Observed Responses
Reward
(b) The Platonic Reasoning Hypothesis
Figure 1. Two examples of Plato's allegory of the cave in artificial intelligence. (a) The training data accessible the model just shadows on the wall, serving as projections of the real world. (b) The responses of the LLM we observe are also shadows on the wall, reflecting the model's implicit reasoning thoughts during task execution.
or ranking (Cobbe et al., 2021). Beyond simpler methods, advanced frameworks like CoT (Wei et al., 2022), ToT (Yao al., 2024), and MCTS- approaches inspired by Al- phaGo (Silver et al., 2016) explore solution spaces in structures identify optimal answers (Zhang et al., 2024; Feng et al., 2023).
erating rate. This "snowball effect" illustrates how small changes can compound over time. In the context of LLMs, this effect first manifests as the progressive accumulation of token-level errors in auto-regressive next-token prediction (NTP) tasks, potentially causing significant deviations from the expected or golden answers (Bachmann & Nagarajan, 2024).
Despite their promise, external slow-thinking methods face several challenges. First, the mechanisms behind their ef- fectiveness remain poorly understood, hindering the design of more advanced and efficient strategies. Second, practi- cal implementations of complex slow-thinking techniques often achieve limited success unless significant computa- tional resources are added. This is due to the difficulty of optimizing design choices and hyperparameters, which fre- quently results in suboptimal performance. To address these challenges, we propose a systematic framework based on information theory, linking external slow-thinking methods the probability of correct reasoning in LLMs.
For reasoning tasks, however, the snowball effect shifts to the sentence level, making the errors more challenging to characterize. To understand these errors, it is critical first examine the nature of reasoning. Prior research suggests that LLM reasoning can be conceptualized executing sequence of primitive tasks at each reasoning step (Ton et al., 2024), prompting further investigation into how such errors accumulate across the reasoning process.
Let's reconsider Plato's allegory the cave!. which has been widely used highlight the limitations of AI mod- els (Huh al., 2024). In this analogy, training data serve mere projections of the real world, akin to shadows on the wall, as illustrated in Figure 1(a). Similarly, in LLM reasoning, generated responses are the shadows, reflect- ing the model's 's implicit reasoning processes, as illustrated in Figure 1(b).
We begin by analyzing the snowball errors in LLM rea- soning in Section 2. and subsequently relate this effect to the likelihood of reasoning errors in Section 3, In Sec- tion 4, we further explore the probability of correct reason- ing within the the real-world practice, and compare various slow-thinking strategies in Section 5. Finally, review relevant literature in Section and present our conclusions in Section 7.
For example, when solving problem like "Calculate 3r + 2y." the model implicitly executes reasoning steps such t (Calculate 3x} - l2: {Calculate 2y} + l3: [Add 3x and 2y}. However, these steps are abstract and cannot be directly observed in outputs. Instead, the response sequence +
2. Snowball Errors in LLM Reasoning
Imagine rolling a snowball on a snowy surface during winter.
'In this allegory. Plato describes individuals confined to cave, learning about the world solely through the shadows its wall.
As the distance increases, the snowball grows at an accel-
2

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
22 + r3g can be multiple possible expressions of the same reasoning process. Moreover, since individual responses cannot fully encapsulate the corresponding steps t,, minor inaccuracies accumulate, ultimately leading to significant snowball errors.
Proposition 3.1. (Probability of reasoning errors.) Let 4 denote an implicit thought step l, and ri represent the corresponding generated response. Given predicted thought & derived from ri using a prediction function i = [(r)), the probability of reasoning error at step I is defined as the likelihood of the event et, where el t1 + tt. This probability is denoted as P(es) = P(4 + l1).
To quantify snowball errors in LLM reasoning, we consider mutual information (MI) between the implicit reasoning sequence t and the observed response sequence r, denoted as [(t; r). This metric captures the shared information between the two sequences. Furthermore, the minor in- accuracies in the responses at each reasoning step can be assessed as information loss, which can be quantified by the difference between the MI [(t; r) and the information entropy of the implicit thoughts t, denoted as (t)). And it can be mathematically defined as:
To estimate the probability of reasoning errors, we propose utilizing information theory to establish a connection be- tween snowball errors and the likelihood of reasoning errors. Specifically, our analysis start from the following lemma:
Lemma 3.2. (Information loss inequality.) Given a reason- ing process defined above, and under the assumption that the mutual information I (fr,r) decreases with respect to I when 1 2 2, the information loss in the 1-th step salisfies:
Definition 2.1. (Information loss.) Given reasoning pro- cess with implicit thoughts t and corresponding responses r, the information loss in the 1-th step is defined as:
H(((())
(()r))) 2 2-1
InfoLoss(ri) = H (tx) - 1 (fr; m1) H (t/lr))
The proof is provided in Appendix A. Lemma 3.2 indi- cates that the information loss in the 1-th step is bounded by the average snowball errors in the previous steps. Based on this lemma, can subsequently derive the lower bound of the probability of reasoning errors.
The snowball errors can be further defined as the accumula- tion of information loss across all reasoning steps as follows: Definition 2.2. (Snowball errors, or cumulative information loss.) Given reasoning process with implicit thoughts t and corresponding responses the snowball errors in the I-th step are defined as:
Theorem 3.3. (Lower bound of P(ex).) Given a reasoming
process and conditions defined above, when 2 2, the probability of reasoning error at step I satisfies:
-z((t)))= H(lr)ss
(zr(t)r) -Hole) 1-1
P(ei) 2 log 2oog-'((TT) ((T) -
where denotes the number of reasoning steps.
where [Ti] is the size of the support of t4. Hy(ei) is the entropy of the indicator random variable of event e,, which is relatively small constant.
3. From Snowball Errors to Probability
In this section, we seek to establish a theoretical connection between snowball errors and the probability of reasoning er- rors in LLMs. We begin by formally defining the probability of reasoning errors and subsequently derive lower bound for this probability using principles from information theory. Finally, we empirically validate the presence of snowball errors in the reasoning processes of L.MMs.
The proof mainly relies on Fano's inequality (Fano, 2008) and is provided in Appendix A.2. Theorem 3.3 sets a lower bound on the probability of reasoning errors at every inter- mediate step l. Since H (t(rr represents the cumulative information loss up to step 1, it is assumed to increase at least linearly with 1. Furthermore, when the snowball ef- fect occurs, (t(()) may grow faster than linearly. As result, the lower bound on the probability of reasoning er- rors rises with the reasoning path length i, indicating that the chance of errors increases as snowball errors accumulate.
3.1. Probability of Reasoning Errors
As the reasoning path grows longer, snowball errors accu- mulate, leading to significant factual inaccuracies, which we define as reasoning errors. This subsection explores the relationship between snowball errors and the probability of reasoning errors.
3.2. Empirical Verification
To empirically verify the existence of snowball errors in LLM reasoning, we conducted experiments using the GSM8k dataset (Cobbe et al., 2021). The evaluation was performed on three ofate-of-the-ar reasoning LLMs: Llama- 3. I-8t-Instt (2024), Qwen2.5-78 ----tttuuuttt Instruct (2024a), and 1-8 (2024). We estimate the
To evaluate reasoning errors, we first define them clearly. Since the response r; represents the implicit thought ft a natural approach is to assess whether sufficiently powerful mapping function f can reconstruct & from ri-
3

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
1a-ma-3,1188--nsttee
Owen2.5-78-Insttuu
Skywork-ol-Open-L ama-3.1-88
Riteed
1.7
Mrunnca Roos hitel
S1-9ted
19
10
tircorBookre
Ritol
90
081
Roward Hilee
0.2-
0.C-
12.05
0.4
0.4
19:35
0--
0.5
2500
1000
.300
3000
forrcce Lengh
Auprage Length.
Aurrae Leegh:
Figure 2. The estimated MI and reward of the responses generated by different LLMs on GSM8k. The x-axis denotes the average length of the responses. The left y-axis represents the estimated MI between each response and the golden answer, whereas the right y-axis shows the corresponding reward. "e" indicates the estimated MI for individual questions, while "-" "ndd" "-"" respectively depict the fitted curves of the estimated MI and reward. "---"" depicts the lincar baseline.
mutual information r();r) per token and the reward of the responses to illustrate their relationship with the reasoning path length L. Detailed experimental settings are provided in Appendix C.I.
represented as sequence of L. reasoning steps, i.e., R. [ri (2, .r., An oracle ø is then employed to evaluate the quality of each step ri produced at layer 1, denoted as Φ(r))- In practice, this evaluation is often determined by human feedback or a reward model. Furthermore, we assume that for each reasoning step, there exists a corresponding golden step r/. representing the most accurate and correct step that the LLM should generate, aligning with ideal human reasoning.
generated autoregressively by the LLM.
As illustrated in Figure 2, the estimated mutual information decreases in a nearly exponential and much faster rate than linear decay as L increases. Since our verification com- putes the average mutual information per token, the actual rate of decline in mutual information for tokens appearing later in the sequence is likely to be more pronounced. Fur- thermore, the reward scores of the responses correspond to the mutual information, and also diminish with increasing response length. These findings confirm the existence of snowball errors by verifying that the information loss can accumulate much faster than linearly in the reasoning pro- cesses of LLMs, and illustrate their relevance to the quality of responses, aligning with our theoretical analysis. For a more robust verification, we also include results on larger LLMs for a more robust verification in Appendix D.1 and an additional analysis by different difficulty levels in Ap- pendix D.2.
Based on the above setting, the oracle evaluation can be used to quantify the correctness of a response. Specifically, we define this measure as follows:
Definition 4.1. (r-correct step.) A step ri is considered as r-correct if the quality difference between the step and the golden step is less than t, i.e., (é(1)) - <(ri)l S T.
Similarly, we can define the correctness of entire reason- ing process follows:
Definition 4.2. (r-correct reasoning.) A response R. is considered as 7-correct if all steps in the sequence are т- correct, i.e., Vl, (o(r)))(((())))) d(ri)l S T (denoted as (R) S r).
4. Probability of Correct Reasoning in External Slow-Thinking
Definition 4.1 and Definition 4.2 provide formal definitions for measuring the correctness of reasoning step or an entire reasoning process. Intuitively, for a given task, the proba- bility of achieving r-correct step is determined by three primary factors: the capability of the LLM, the correctness threshold т, and the length of the current reasoning path.
Previous analyses demonstrate that the probability of reason- ing errors, P(er), increases with the number of reasoning steps 1. In the practice, however, reasoning errors are often reflected in the reward associated with the generated re- sponses. In this section, we extend our theoretical analysis to real-world scenarios and explore the mechanisms under- lying the effectiveness of external dow-thinking methods.
4.2. Probability of Correct Reasoning
The results shown in Figure 2 indicate that the average MI can decrease exponentially with the reasoning length, which suggests that the average snowball errors increase exponen- tially with the reasoning length. Since the probability cannot exceed 1, with Theorem 3.3, we thus hypothesize that the probability of encountering an error in practice follows an
4.1. What is a Correct Reasoning?
We begin our analysis by defining the reasoning process in real-worlh settings. Given a question ro, a response R is
4

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
1 for the con- venience of subsequent analyses. Thus the probability of generating correct step in layer I can be proposed as:
exponential decay function: P(er)
Ae-
step, the expansion of the reasoning space introduces the challenge of selecting the most promising reasoning path from pool of candidates. In summary, let Pr([generate] de- note the probability of generating a r-correct reasoning and Pr((selecs) denote the probability of selecting a r-correct reasoning. The overall probability of obtaining a r-correct response can then be expressed as:
Proposition 4.3. (Probability of T-correct step.) We pro- pose that the probability of generating a r-correct step is related to the layer index I in the following way:
S min(Ane Pr -(()
Pr (R) S 7] = Pr (Tgemnerate) x Pr (Tseleat)
where ' is a constant relevant to correctness т, and a premise that the step Tt-1 already T-correct.
While the width-eeppansion strategy can effectively increase Pr (Fgenerstee, the additional reasoning steps introduced also heighten the complexity of selecting the most promising rea- soning path, thereby reducing Pr (Taelect). To illustrate this trade-off, we use beam search a baseline width- expansion strategy. Beam search is a widely adopted method in tree search algorithms, where the search tree's 's width is expanded by generating kt child nodes at each layer while retaining only the top-b most promising candidates. The result of this analysis is formalized in the following lemma.
This proposition mainly aims to obtain more intuitive con- clusions in subsequent analysis and is based the intuition of LLM's multi-step reasoning errors. In particular, we point out in Appendix B that under more relaxed and gen- eralized proposition, our subsequent theoretical results can still be guaranteed.
With Proposition 3.1, we can derive the probability of gen- erating a 7-correct response as follows:
Lemma 4.5. (Probability of r-correct reasoning in width- expanding methods.) For a beam-search-like strategy which samples steps and keeps b steps as candidates at each expansion, the probability of obtaining r-correct response is upper bounded by:
Lemma 4.4. (Probability of r-correct reasoning.) The probability of generating T-correct response RR is:
L 11 Pr - -(r)) ST]
(r(
ST]
1=1
S Afe 112-1)
Pr (r( T|
II -1 -11--xe--1 1=1
Lemma 4.4 shows that the probability of generating a correct response decreases exponentially with the reasoning leangth L. This result aligns with the practical experience that the LLM is more likely to make mistakes in more complex reasoning tasks with more reasoning layers.
where en is the probability of selecting a T-correct step from b candidates, which is primarily determined by the reliability of the value function employed in the selection.
The proof is provided in Appendix A.3. Since the typical reasoning setting holds that k 2 1, and 0 S X < 1, the probability of generating a correct response can be further simplified as follows:
4.3. External Slow-Thinking Mechanisms
In general, external slow-thinking methods aim to enhance the correctness of generated responses by incorporating ad- ditional reasoning steps. Due to the inherent stochastic nature of the L.L''s sampling mechanism, the probabil- ity of generating a correct response cannot be guaranteed. However, by introducing supplementary reasoning steps and employing multiple re-sampling strategies, the likelihood of producing a correct response can be effectively increased.
Theorem 4.6. (Upper bound of the probability of r-correct
reasoning in width-expanding methods.) The probability of obtaining a T-correct response upper bounded by:
Pr S T] S eb "K 1(++1)
The proof is provided in Appendix A.4, and we also pro- vide an empirical analysis about the influence of k in Ap- pendix D.3. Lemma 4.5 and Theorem 4.6 show that the prob- ability of generating correct response in width-expanding methods depends on three key factors: the number of gen- erations k per layer, the number of candidates b selected per layer, and the correctness threshold т. Specifically, components related to 4, represent Pr (Tweeer), which are influenced by the reliability of the value function used in selection. Meanwhile, Pr (Tgenerate) is mainly determined by
Although different methods employ varying strategies to explore the reasoning space, they share two common char- acteristics: (1) Width-Expansion For reasoning sequence of length L, most external slow-thinking methods aim to expand the width of the reasoning space. This expansion is achieved either through simple re-generation techniques (e.g., BoN, CoT-SC) or via more sophisticated approaches like tree search (c.g.. ToT, MCTS). (2) Generation & Selec- tion. Despite the challenge of generating a good reasoning
5

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
the expansion width k and reasoning path length L. Com- pared with Lemma 4.4, Theorem 4.6 further illustrates the mechanism of external slow-thinking methods. By scaling k, these methods can improve the probability of correct rea- soning at the cost of additional reasoning steps. However, the effectiveness heavily depends on the reliability of the value function, reflected in ef. For slow-thinking methods to be effective, the value function must satisfy e > to ensure an improvement in the probability upper bounds.
MCTS. Here, the "best" and "worst" cases are defined based the difficulty for BoN to achieve a comparable probabil- ity of correct reasoning, rather than the actual performance of MCTS.
Using the RAP-like classic MCTS strategy (Hao et al., 2023) as an example, where MCTS terminates once a reasoning path of length L is derived, the best-case scenario occurs when MCTS expands only the deepest leaf' node at each step. Assuming b child nodes MCTS in this scenario reduces to a beam search strategy with both a sample size and beam width of b. The probability of obtaining a ar r-correct reasoning in the best-case scenario can then be expressed as:
expanded per iteration,
Based on the above analysis, we can infer the underlying mechanisms of external slow-thinking methods. By ex- panding the reasoning space, these methods effectively increase the probability of generating a correct response, thereby mitigating the impact of snowball errors. How- ever, selecting the most promising reasoning path poses significant challenge, as the effectiveness of this selection heavily depends on the reliability of the employed value function, which can substantially influence the overall performance of the method. We also provide analyses of the mechanism of external slow-thinking methods from other perspective in Appendix E.
Lemma 5.2. (Upper bound of the probability of r-correct reasoning with MCTS in best case.) The probability of obtaining r-correct response in MCTS in the best case satisfies:
Pr (r( S S ST) X/E 1IL
2
In the worst-case scenario, MCTS must expand all pos- sible child nodes at each step, ultimately constructing a complete b-ary search tree that terminates at the L-th layer. Consequently, the probability of obtaining r-correct response with MCTS in the worst-case scenario can be bounded as:
5. Comparison between External Slow-Thinking Frameworks
Previous analyses have demonstrated that external slow- thinking methods effectively increase the search width, thereby enhancing the probability of correct reasoning. In this section, use the simplest strategy, Best-of-N (BoN), and the widely adopted sophisticated strategy, Monte Carlo Tree Search (MCTS), as examples to compare their effective- ness and examine the impact of specific framework designs.
Lemma 5.3. (Upper bound of the probability of r-correct reasoning with MCTS in worst case.) The probability of generating r-correct response in MCTS in the worst case satisfies:
Pr ST S X (
II Ev
5.1. Correct Reasoning Probability
We begin by determining the probability of correct reasoning for BoN and MCTS using the results from Theorem 4.6. With the assumption that the total number of reasoning steps L, BoN can be characterized as generating N reasoning steps in the first layer, followed by the generation of a single step in subsequent layers, and finally applying reward model (RM) to select one path from the N candidates in the L-th layer. Accordingly, the probability of achieving r-correct reasoning with BoN can be bounded as follows:
The proof is analogous to that of Theorem 4.6, with the primary difference being that, in Lemma 5.2, we have k b, whereas in Lemma 5.3, k = b/.
Lemma 5.2 and Lemma 5.3 establish upper bounds on the probability of correct reasoning for MCTS in the best-case and worst-case scenarios, respectively. These results illus- trate that the probability of correct reasoning with MCTS is influenced by both the search width b and the length of the reasoning path L. Although MCTS provides a more sophisticated reasoning strategy and introduces additional complexity to mitigate snowball errors, it is important to note that selection errors also accumulate due to the in- creased complexity. This accumulation is reflected in the exponential term within the c terms.
Lemma 5.1. (Upper bound of the probability of c-oorectt reasoning with BoN.) The probability of obtaining T- correct response in BoN satisfies:
Pr (R) < rl S NNN M(++1)
In contrast, MCTS employs more intricate structure, mak- ing it difficult to derive a closed-form -oredmffommmooo expression for the probability of correct reasoning. To simplify the analysis, we consider the "best-case" and "worst-case" scenarios for
5.2. Comparison between BoN and MCTS
Since MCTS introduces exponential selection errors due to its increased complexity, it is necessary to perform a fair
6

---

Rethinking External :low-Thinking: From Snowball Errors to Probability of Correct Reasoning
Salf Consistency
ORM Vate
ORM Max
MCTS
MCTS
MCTS
Accuracy (86)
Accuracy
Accurscy
0.3
Nged
Mast aio
Mre
Neak
Mees 50
Nest
75
180
22
180
12
11a
304
s0a N
sis
150
175
GSMBK
Consistency
Accuracy (50
Accuracy (95)
65-
Accuracy (%)
11
2V
N
105
32% 320
aic
26
125
17%
N
N
PrOntoQA
Figure 3. Comparison of the accuracy of various reasoning strategies on GSM8k and PrOntoQA. - indicates the accuracy of the baseline MCTS, while "-"" represents the accuracy of BoN under different N settings. The x-axis corresponds to the varying values of N. Additionally, the estimated values Nres and Neal! are marked by vertical green dashed lines.
comparison between BoN and MCTS. This challenge arises from the inability to fully characterize the reward model (RM) employed in practice. For instance, it is difficult to determine whether selecting correct step from N candi- dates in single iteration is more or less challenging than selecting correct step from b candidates across I. iterations, particularly when NN O(b²).
to match the probability of correct reasoning with MCTS in the worst-case scenario by comparing the upper bounds provided in Lemma 1 and Lemma 5.3:
Corollary 5.5. Despite the influence of RM, the minimal N for making BoN obtain the comparable correct reasoning probability with MCTS worst case is Nworst O(b4). min
To address this issue, we compare the two methods by exam- ining the minimal value of required for BoN to achieve a probability of correct reasoning comparable to MCTS in both the best-case and worst-case scenarios, assuming the use of ideal reward model, which ensures that whenever at least one correct candidate exists, Vk, 6 1.
Corollary 5.4 and Corollary 5.5 reveal that the minimal N required for BoN to achieve probability of correct reasoning comparable to MCTS is ( in the best-case scenario and ( in the worst-case scenario.
Next, we analyze the total reasoning cost of BoN and MCTS when N set with corresponding Nmi.- Since BoN gener- ates N reasoning paths, each of length L, the total reasoning cost for BoN is N x L. Using the results from the above corollaries, can infer that when MCTS operates in the best-case scenario, the total reasoning cost of BoN is (bL)). In contrast, when MCTS is in the worst-case scenario, the to- tal reasoning cost of BoN increases to OLLb*) For MCTS, according to previous analyses, the total reasoning cost O(bL) in the best-case scenario and O ) in the worst- case scenario. We summarize the comparison of the total
Under this assumption, we derive the minimal N required for BoN to match the probability of correct reasoning with MCTS in the best-case scenario by comparing the upper bounds provided in Lemma 5.1 and Lemma 5.2:
Corollary 5.4. Despite the influence of RM, the minimal N for making BoN obtain the comparable correct reasoning probability with MCTS in best case is Nheu (b).
min
Similarly, we can derive the minimal N required for BoN

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
BoN (comparable)
MCTS (baseline)
increasing N can enhance BoN's performance even without reward model. For ORM Vote and ORM Max strategies, guided by the reward model, BoN achieves performance comparable to MCTS when N lies between Mes and Neat- Notably, when N is near Nes. BoN may slightly underper- form compared to MCTS but not significantly. Conversely, setting N to a larger value within this range allows BoN to match or even surpass MCTS. These findings align with previous observations of MCTS's limited success in LLM reasoning and support our theoretical analysis.
Best Case
((bL)
((bL)
Worst Case
(
O(b²)
Table 1. Comparison of the total reasoning cost between MCTS and its comparable BoN. We assume MCTS generates a reasoning path of length L and expands & child nodes at each expansion, while BoN generates Nain reasoning paths, each of length L.
reasoning cost between BoN and MCTS in Table 1.
6. Related Work
The results in Table I indicate that when BoN and MCTS achieve a comparable probability of correct reasoning, the total reasoning cost of BoN remains close to that of MCTS. In the best-case scenario, their costs asymptotically equivalent, while in the worst-case scenario, BoN's 's cost may exceed MCTS when L is small but stays reasonable. As L grows larger. BoN's s cost can even fall below MCTS. This analysis shows that BoN can achieve similar reasoning accuracy to MCTS with comparable reasoning costs, and these findings are applicable other external slow-thinking frameworks.
Information Theory. Information theory provides a theoret- ical basis for quantifying the information contained in ran- dom variables. The entropy H (X) of random variable X measures its information content, while mutual information T(X;Y) H(X) (XX) Y) quantifies the information shared between two variables. Applications of informa- tion theory span numerous fields, including bounding the generalization capacity of deep learning models (Russo & Zou, 2019; Xu Raginsky, 2017) and improving task inter- pretability (Slonim et al., 2001; Hu et al., 2019; West et al., 2019). Recently, it has been employed to analyze synthetic data generation (Gan & Liu, 2024) and measure reasoning errors in LLMs (Ton et al., 2024).
In conclusion, external slow-thinking methods introduce additional reasonin steps to mitigate the impact of snow- ball errors. However, on one hand, the inaccuracy of the reward function can result in the additional reasoning steps incurring extra selection costs, which may decrease the probability of correct reasoning. On the other hand, the effectiveness of mitigating snowball errors is primarily determined by the total reasoning cost, with the specific framework having limited impact on the overall outcome.
Reasoning with LLMs L.MS have made substantial progress in understanding and generation, particularly for complex reasoning tasks. Foundational work (Brown et al., 2020) established LLMSs few-shot learners, while Chain- of- of-Thought (CoT) prompting (Wei al., 2022) introduced multi-step reasoning by explicitly generating intermediate steps. Self-Consistency (Wang et al., 2022) further im- proved robustness by aggregating multiple reasoning paths. informationntheorette approaches (Ton et al., 2024) have also provided theoretical insights into quantifying and miti- gating reasoning errors, showcasing the interplay between empirical advancements and theoretical frameworks.
5.3. Empirical Evaluation
We empirically compare the accuracy of BoN and MCTS on two reasoning tasks: GSM8k (Cobbe et al., 2021) and PrOn- toQA (Saparov & He, 2022). Following prior work (Feng et al., 2023), we use the recommended settings to optimize MCTS and calculate the corresponding N for BoN to align its reasoning cost with MCTS. Due differences in how reasoning paths are generated, exact alignment is imprac- tical. To address this, we define N as reasonable if it lies between Niss (aligned reasoning steps) and Neal (aligned LLM calls). We evaluate BoN with three selection strategies: Self-Consistency, ORM Vote, and ORM Max. Details of the experimental setup are in Appendix C.2, and results are pre- sented in Figure 3. Furthermore, we also include additional experimental verifications on a planning task Game24 (Yao et al., 2024) in Appendix D.4.
External Slow-Thinking Test-time scaling has proven ef- fective in enhancing LLM reasoning (Snell et al., 2024), this timely inference scaling law has been empirically analyzed and verified (Wu et al., 2024). External thwnthhng meth- ods, such as generating additional tokens (Wei al., 2022) and incorporating tree search algorithms (Yao et al., 2024), expand the reasoning space without retraining. Techniques like beam search (Kang et al., 2024) and Monte Carlo Tree Search (MCTS) (Zhang et al., 2024; Feng et al., 2023) have further advanced reasoning capabilities. However, these methods require significantly more computational resources compared to simpler strategies like Best-of-N and often yield limited practical improvement. The underlying mech- anisms of their effectiveness remain area of ongoing exploration.
Since PrOntoQA is a binary classification task with only true or false answers, increasing N in the Luff-Consistency strat- egy cannot improve BoN's s performance without a reward model. In contrast, for GSMSk, where answers are diverse,
8

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
7. Conclusion
Ré, C., and Mirhoseini, A. Large language monkeys: Scaling inference compute with repeated sampling. arXiv preprint arXiv:2407.21787 2024.
In this paper, we analyzed the mechanisms behind the ef- fectiveness of external slow-thinking methods. We linked snowball errors in LLM reasoning to reasoning errors using information theory and showed how external slow-thinking methods reduce errors by expanding the reasoning space. We also examined the trade-off between additional reason- ing costs and the probability of achieving correct reasoning. Through comparisons of methods ranging from Best-of- (BoN) to Monte Carlo Tree Search (MCTS), we found that the key factors influencing effectiveness are the reward function's ss capability and the total reasoning cost, with the specific search framework playing secondary role. Our findings suggest that optimizing reward functions and im- proving policy model reasoning capabilities are more es- sential for designing more effective external slow-thinking methods a long run.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models few-shot learners. Advances in neural information processing systems, 33: 1877-1901, 2020.
Cobbe, K.,, Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110 200: 14168, 2021.
Deepseek-rl: DeepSeek-AI.
Incentivizing reasoning ca- pability in iims via reinforcement learning, 2025. URL https:/ httpss//arxiv..oo wttaaaiii....ibaaaaa /ttp://///aaiv...rrr/////22/.1.1 12948.
Acknowledgments
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle,
A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint arXIv:2407.21188322000 2024.
This research was supported by National Natural Sci- ence Foundation of China (No.62476777), National Key Research and Development Program of China (No. 2024YFE0203200), CCF-ALIMAMA TECH Kangaroo Fund &NO.CCF-ALIMANT OF 2024008), and Huawei- Renmin University joint program on Information Retrieval. We also acknowledge the support provided by the fund for building worldclass universities (disciplines) of Ren- min University of China and by the funds from Beijing Key Laboratory of Big Data Management and Analysis Methods, Gaoling School of Artificial Intelligence, Renmin University of China, from Engineering Research Center of Next-Generation Intelligent Search and Recommendation, Ministry of Education, from Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "DoubleFirst Class" Ini- tiative, Renmin University of China, from Public Policy and Decision- maniing Research Lab of Renmin University of China, and from Public Computing Cloud, Renmin Univer- sity of China.
Fano, R. M. Fano inequality. Scholarpedia, 3(10):6648, 2008.
Feng, X., Wan, Z., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang, J. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint #rXiv:2309.77199 2023.
Gan, Z. and Liu, Y. Towards a theoretical understanding of synthetic data in I1m post-training: A reverse-bottleneee perspective. arXiv preprint arXiv:2410.01720, 2024.
Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. Measuring statistical dependence with hilbert-schmidt norms. In International conference on algorithmic learn- ing theory, pp. 63-77. Springer, 2005.
Hao, S., Gu, Y., Ma, H., Hong. J., Wang. Z., Wang, D., and Hu, Z. Reasoning with language model is planning with world model. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference on Empirical Meth- ods in Natural Language Processing, pp. 8154-8173, Singapore, December 2023. Association for Computa- tional Linguistics. doi: 10. 12216663/112002..mmmlpp main. 507. URL https: h http://aaaatthooogoooooo org/ 2023. emnlp-main. 507/.
Impact Statement
This paper presents work whose goal is to advance the field of Large Language Models. There are many potential soci- etal consequences of our work, none which we feel must be specifically highlighted here.
References
Bachmann, G. and Nagarajan, V. The pitfalls of next-token prediction. arXiv preprint arXiv:2403.06663 2024.
Hu, S., Yan, X., and Ye, Y. Multi-task image cluster- ing through correlation propagation. IEEE Transactions on Knowledge and Data Engineering, 3313):1113-1127, 2019.
Brown, B., Juravsky, J., Ehrlich, R., Clark, R., Le, Q V.,
9

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
Huh, M., Cheung, B., Wang, T., and Isola, P. Position:
large language models. In Ku, L.-W., Martins, A., and Srikumar, V. (eds.), Findings of the Association for Computational Linguistics: ACL 2024, pp. 4864- 4888, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/000 findings-acl.290. URL https:/ http://aaaanthooogy.... org 202g/2224.2 findingsnnnniie a90.
The platonic representation hypothesis. In Salakhut- dinov, R., Kolter, Z., Heller, K., Weller, A., Oliver, N., Scarlett, J., and Berkenkamp, F. (eds.), Proceed- ings of the 41 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learn- ing Research, pp. 20617-20642. PMLR, 21-27 Jul 2024. URL https: /ttp///eeeeeegs..ccee mwr. malr.pzee press/ v235 4235/huh24a. html.
Rafailov, R., Sharma, A., Mitchell, E., Manning, D. Er- mon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Ad- vances in Neural Information Processing Systems, 36, 2024.
Jiang. J., Chen, Z., Min, Y. Chen, J., Cheng, X., Wang, J., Tang, Y., Sun, H., Deng. J., Zhao, W. X., al. Technical report: Enhancing IIm reasoning with reward-guided tree search. arXiv preprint arXiv:2411.11694 2024.
Russo, D. and Zou, J. How much does your data explo- ration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302- 323, 2019.
Kang, J., Li, X. Z., Chen, X., Kazemi, A., Sun, Q.. Chen, B., Li, D., He, X., He, Q.. Wen, F., al. Mindstar: Enhancing math reasoning in pre-trained ilms inference time. arXiv preprini arXiv:2405. 16266 2024.
Saparov, A. and He, H. Language models are greedy rea- soners: A systematic formal analysis of chain-of-thought. arXiv preprint arXiv:2210.012400 2022.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836: 2020.
Silver, D., Huang, A., Maddison, C. Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. arXiv preprini arXiv:2305.20050, 2023.
Slonim, N., Tishby, N., et al. The power of word clusters for text classification. In 23rd European Colloquium on Information Retrieval Research, volume 1, pp. 200, 2001.
Liu, C. Y., Zeng, L., Liu, J., Yan, R., He, J., Wang, C., Yan, S., Liu, Y., and Zhou, Y. Skywork-reward: Bag of tricks for reward modeling in llms. arXiv preprint arXiv:2410. 18451, 2024.
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling Ilm test- time compute optimally can be more effective than scal- ing model parameters, arXiv preprint arXiv.2408.03314. 2024.
Ma, W.-D. K., Lewis, J., and Kleijn, W. B. The hsic bot- tleneck: Deep learning without back-propagee propagatiin.. In Proceedings of the AAAI conference on artificial intelli- gence, volume 34, pp. 5085-5092. 2020.
Team, Q. Qwen2.5: A party of foundation models, Septem- ber 2024a. URL https: /wwp/wwwwmmmmmmmm////.../.e...mm hwt.hl..i............... io/ blog/ htsp//wwn2../.
Min, Y., Chen, Z., Jiang. J., Chen, J., Deng, J., Hu, Y., Tang, Y., Wang, J., Cheng, X., Song, H., et al. Imitate, explore, and self-improve: A reproduction report on slow-thinking reasoning systems. arXiv preprint arXiv:2412.09413, 2024.
Team, Q. Qwq: Reflect deeply on the boundaries of the unknown, November 2024b. URL htttps://qwent
github.io/bbooo wtt.://///bopggoo. qwqq 32b preview/.
ol Team, S. Skywork-ol open series. https: /// huggingface catlaacecco/ee Skywork, November 2024. URL httpp://huggingge wtt.cee...../kkokkoookk
Ton, J.-F, Taufqq. M. F., and Liu, Y. Understanding chain- of of-thought in llms through information theory. arXiv preprint 2rXiv:2411.11988. 2024.
Novembeee
OpenAl. Learning to reason with 1ms,, 2024. URL
Wang. X., Wei, J., Schuurmans, D., Le. Q., Chi, E., Narang, S., Chowdhery, A., and Zhou, Self-consistency im- proves chain of thought reasoning in language models. arXiv preprint arXiv:2203.1l 11171, 2022.
https: /twp///ppea//a///////e//ee commii index/ learning-ton toannnttt---o reason with 1lms/. Accessed: September 12. 2024.
Qian, C., Zhang, J., Yao, W., Liu, D., Yin, Z., Qiao, Y., Liu, Y., and Shao, J. Towards tracing trustwor- thiness dynamics: Revisiting pre-training period of
Wang, Z., Bukharin, A., Delalleau, O., Egert, D., Shen, G., Zeng, J., Kuchaiev, O., and Dong, Y. Helpsteer2- preference: Complementing ratings with preferences,
10

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
2024.
URL https://araivv.orr/abb////
01257.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. Zhou, D., al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837,, 2022.
West, P., Holtzman, A., Buys, J., and Choi, Bottlesum: Unsupervised and self-supervised sentence summariza- tion using the information bottleneck principle. arXiv preprint xrvi: 11t.v::99990740000 2019.
Wu, Y. Sun, Z., Li, S., Welleck, S., and Yang, Y. Infer- ence scaling laws: An empirical analysis of compute- optimal inference for problem-solving with language models. arXiv preprint arXiv:2408.0077 2024.
Xu, A. and Raginsky, M. Information-theerrticc analy- sis of generalization capability of learning algorithms. Advances in neural information processing systems, 30, 2017.
Yao, S., Yu, D., Zhao, J., Shafran, L., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024.
Yuan, Z., Yuan, H., Li, C., Dong, G., Lu, K., Tan, C., Zhou, C., and Zhou, Scaling relationship on learning math- ematical reasoning with large language models. arXiv preprint ar arXiv:2308.0 0/855 2023.
Zelikman, E., Wu, Y., Mu, J., and Goodman, N. Star: Boot- strapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476-15488 2022.
Zhang, D., Zhoubian, S., Hu, Z., Yue, Y., Dong, Y., and Tang, J. Rest-mets*; Llm self self-training via process reward guided tree search. arXiv preprint arXiv:2406. 03866, 2024.

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
A. Proofs
A.1. Proof of Lemma 3.2
Proof. Since (t) decreases with respect to I, we have
1(Gr)) Σ 1-1 1((ir))
1-1
by the definition of mutual information, we can derive that
H(4) H(4m)) - Σ H(t,) (())))s))
1
(I)
H(tm))))
1-1 H(t)
H(talr)) 2 Σ 1-1 + (ti) - -
Since along the reasoning process, LLM is continiously introducing new information, we have H(4) 2 Σ E H(t) Therefore, we have:
Σ D + (())
شي Σ H(tm))
(2)
Hence, together with equation (1) and equation (2), we can further derive that:
1-1 H(talrs)
He((t)r)
H(tilr)) 2
Σ 1-1 1-1
(3)
This finishes the proof.
A.2. Proof of Theorem 3.3
Proof. Define an indicator random variable E, where E = 1 if occurs, and E = otherwise. More specifically,
if # t
E
0 if = t
Based on the definition of entropy, we have:
H(t(8)= = (EE)) ()))),))
(4)
For the first term (F)()) we have:
H( (EE) :b((e))
(5)
For the second term H (.) we can expand it as:
Ht))E,,) H(t = 0. = 0) -
(6)
Since E = 0 implies & = t., we have (t; E 0, it) 0. And since E implics & * ti, we have P(E 1) P(e)).
Therefore, we have:
Htt|EE &) = Ht P(e))
(7)
Considering the upper bound of the entropy of a random variable, we have the following lemma.
Lemma A.1. (Principle of maximum entropy.) Let X be a random variable with support X, the entropy H H(X) satisfies:
H(X) < log([>{).
with equality if and only if X is uniformly distributed over X.
12

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
Since E 1 indicates that & o 4, then when & is given condition, random variable 4 can be narrowed down [7] different values, where Ti is the support of 4. Therefore, we have:
1
H(4 1,4) S log( T7| 1).
(8)
Combining equation (7) and equation (8), we have:
S (og(()) P(e).
(9)
Combining equation (5) and equation (9), we have:
11 (t)l6) s log([Ti| 1))((r) Ho(e:).
(10)
Considering the markov chain f - ry + f, due to data processing inequality, we have:
f(t S (trrr.).
Based on the definition of mutual information, can further derive that:
H(tiln) & H(t(())
(11)
With equation (10) and equation (11), we have:
H(tilm)) s log([Ti) ())p(e))())) Hole)).
(12)
With lemma 3.2, we have:
H(tinn Hellthr
(13)
1-1
Together with equation (12) and equation (13), we have:
log(ITi 1)P(et) Holei) 2 He((t)r)
(14)
1-1
Hence, we can further derive that:
P(e:) 2 log log- 1)
(t(()))
Hblei)
(15)
1-1
This finishes the proof.
A.3. Proof of Lemma 4.5
Proof. Assuming that the probability of generating r-correct thought is then with & sampling times, the probability of generating at least one r-correct thought 1 - (1 11-p0 +)
With lemma 4.3, we have p S _!_ then the probability of generating r-correct thought at the I-th layer
Pr[[@(r)) <(77) < < (1 ))
(16)
The probability of generating a r-correct response is the product of the probability of generating a 7-correct thought in each layer.
Pr (R) <| II a Pr (()m)))((r))))))))))))))))))))))
< II coll (1 Xe
(17)
13

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
A.4. Proof of Theorem 4.6
Proof. The following inequality always holds when & 2 1 and S de - 1:
- X7e 16 - k
(18)
Then with lemma 4.5, we have:
(r( S
II ee dxE 11)
II [6 (1- k),E
(19)
II Cskdd 1=1
c ' e -(++11
This finishes the proof.
B. Relaxed Theoretical Results
Proposition 4.3 was designed to facilitate subsequent analyses while maintaining readability. The negative exponential form provides simple yet effective characterization of accuracy decay. Below, we would like to prove that our main results remain valid under weaker assumption when Pr [[ø(n)) <(ri)) S decreases monotonically with l.
Proposition B.1. (Relaxed probability of T-correct step for Proposition 4.3.) Instead of requiring Pr [lo(r)) - dbri)l <]] min (1) now assume only that the left-hand side decreases monotonically with and converges to 0, ie.,
( (( S min (E(1, 1),
where E(L, 2 decreases monotonically with and converges to
Under this weaker condition, by noting that (1, : I1 E(I,T), T), we derive revised relaxed bounds for subsequent results in the main text presented below:
Lemma B.2. (Relaxed probability of r-correct reasoning for Lemma 4.4.) After relaxation, the probability of generating 7-correct response R. is:
Pr( <] II Pr((o(m) -(r)) <
<1),
Lemma B.3. (Relaxed probability of T-correct reasoning expaddexp methods for Lemma 4.5.) After relaxation, for Sram--eearc-like strategy which samples steps and keeps b steps as candidates at each expansion, the probability of obtaining r-correct response is upper bounded by:
L Pr (r( S ST S 1-
(1-E(()))))
Theorem B.4. (Relaxed upper bound of the probability of r-correct reasoning in cridt--eppnding methods for Theorem 4.6.) After relaxation, the probability of obtaining T-correcl response is upper bounded by:
Pr (T) < <] S cl
Lemma B.5. (Relaxed upper bound of the probability of rcoorect reasoning with BoN for Lemma 5.I.) After relaxation, the probability of obtaining T-correct response in BoN satisfies:
Pr (R) S r) NLLL
14

---

Rethinking External Slow-Thind :low-Thinking: From Snowball Errors to Probability of Correct Reasoning
Lemma B.6. (Relaxed upper bound of the probability of T-correct reasoning with MCTS in best case for Lemma 5.2.) After relaxation, the probability of obtaining T-correct response in MCTS in the best case satisfies:
Pr(w(R) S (l,))
Lemma B.7. (Relaxed upper bound of the probability of t-correct reasoning with MCTS in worst case for Lemma 5.3.) After relaxation, the probability of generating a T T-correct response in MCTS in the worst case satisfies:
Pr(v(R) S 26 5 L1L+D
(1,T
II eyg.
These modifications of relaxed results preserve the validity of Corollary 5.4, Corollary 5.5, and Table 1, confirming that theoretical results are robust even without the original exponential form in Proposition 3.1.
C. Experiment Settings
C.1. Settings for Verifying Snowball Errors
For each question, we generated multiple responses from the LLMs and collected them as a set to represent r. Additionally, a larger I.LM,
(2024), was used to rewrite the ground-truth answers multiple times, creating set of rewritten golden answers as an estimate of t. We also utilize an outcome reward model Skywork- Reward-- Llama-3.1-88 1-BBB (Liu al., 2024) evaluate the quality of the responses. Following prior studies (Qian et al., 2024; Ma et al., 2020), utilized the Hilbert-Schmice Independence Criterion (HSIC) (Gretton et al., 2005) estimator of mutual information, I(t;:)).
In our experiments, we generated responses for each question in the GSM8k dataset (Cobbe et al., 2021) 10 times using the tested LLMs to construct the response set r. Similarly, the ground-trum truth answers were rewritten 10 times using the Llama-3.1 -eeeetton-700000 C0B-IIntruut-HH model (Wang et al., 2024) form a of rewritten golden answers, serving as an approximation of
The Hilbert-Schmmid Independence Criterion (HSIC) (Gretton al., 2005) employed to estimate the mutual information [(t;;)) r1) between the response set and the rewritten golden answers. The bandwidth parameter a for the Gaussian kernel used HSIC computation was set to 50. To account for differences in response lengths, the estimated HSIC values were further normalized to obtain a per-token measure, ensuring fair comparison across responses of varying lengths.
To ensure consistency response generation, we utilized the following reasoning prompt for the tested LLMs:
Please answer the question step by step and put the final answer in \boxed(].
For rewriting the ground-truth answers, the following rewriting prompt was used:
You will be given problem-solving process. Please rewrite this process without changing its logic content. Ensure that the output includes only the rewritten process and nothing else.
Serroblem-Solvingg Process:** {input}
**Rewritten **
This setup was carefully designed to capture the relationship between the generated responses and the golden answers while controlling for logical consistency and content fidelity during the rewriting process.
C.2. Settings for Comparison between BoN and MCTS
Given a baseline MCTS which expands for p times, and expands b child nodes at each expansion, with the aim to equal the times of calling LLM for inference, we can calculate the corresponding value N for BoN as Nea = p x b. Similarly, with the aim to equal the times of reasoning steps, given the average length of reasoning paths is L, we can calculate the corresponding value of N for BoN as Nu. pxb
15

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
To ensure fair and comprehensive comparison, we consider any N within the range of New to N reasonable value for BoN to achieve comparable reasoning cost MCTS. Subsequently, we evaluated the performance of BoN using three different selection strategies: (1) Self-Consistency: Select the most frequent final answer among the N reasoning results. (2) ORM Vote: Select the final answer with the highest total ORM scores across all reasoning paths. (3) ORM Max: Select the result of the reasoning path with the highest individual ORM score.
In our experiments, we compared the performance of BoN and MCTS in the context of the Snowball task. We first determine the baseline MCTS setting according to the recommendation in previous work (Feng et al., 2023). Specifically, in GSM8K, we set the tree max width to 6 Tree Max depth And in Game24, set the tree max width 20 and Tree Max depth 4.
In PrOntoQA, we set the tree max width to 6 and Tree Max depth to 15.
Subsequently, we trace the search process of the baseline MCTS and statics the average expansion width b and average expansion times for the two tasks. We then estimate the ideal average reasoning steps L for the two tasks by analyzing the ground ground-truth reasonings. Finally, we calculate corresponding Neal and Nees according to above values. The detailed results are shown Table 2.
GSM8k
PrOntoQA
Game24
avg. 4.26
1.67
4.56
avg. p
4.54
9.45
3.99
avg. I.
3.11
4.00
3.00
Neall
19.40
15.77
18.24
Nres
6.23
3.94
6.08
Table 2. Settings for BoN and MCTS in GSM8k, PrOntoQA and Game24.
D. Additional Empirical Verification
D.1. Snowball Error Verifications on Larger LLMs
For a more robust verification of our theoretical findings, we have conducted extensive analyses on larger language models (Qwen2.5- 1-5---4B-nnae Instruct and Qwen2.5-32B-Instee Instruct) in addition to the 7B/8B models presented in Figure 2. We maintained identical experimental settings and workflow described in the original experiments to ensure methodological consistency, and we present the additional results in Figure 4.
Our key findings from these additional experiments demonstrate that the MI decay pattern remains consistent across larger model sizes, exhibiting similar behavior to smaller models. Also, response quality continues to show a negative correlation with output length, as observed in our original experiments.
D.2. Snowball Error Analysis by Difficulty Levels
We have conducted verifications for the snowball errors at different difficulty levels. The experiments are performed on MATH-500 (Lightman et al., 2023), where the questions are divided into 5 different difficulty levels (level 1 for the simplest, level 5 for the most difficult). The results are presented in Figure 5. In (a), we present the relationship between the estimated MI and average response length different levels. For all levels, we observe similar MI decay phenomena like Figure in our main text. In (b), we present the relationship between the average accuracy and the length of responses different levels. For all 5 levels, observed that accuracy generally decreases with response length. Furthermore, the accuracy of the simplest level 1 decreases significantly when the length increases, demonstrating the harm of overthinking. These results demonstrate that the MI decay phenomenon is highly relevant to the response length even when the influence of question difficulty is similar.
D.3. Influence of k
For better understanding Theorem 4.6, we have conducted an analysis about the influence of k in the theoretical findings, which is presented in Figure 6. The experiments are performed on GSMSk and PrOntoQA.
The results illustrate that: (1) the reasoning correctness increases when the reasoning cost increases, which aligns with the theoretical findings in Theorem 4.6; (2) for simpler PrOntoQA task where the value function is more reliable, the accuracy
16

---

Rethinking External Slow-Thinking From Snowball Errors to Probability of Correct Reasoning
Qwen2.5-14B-nnstruct
Qwen2.5-32B-Instruuc
Data Fitted
-31.5
0.7
-276
0.5
MI Fitted
MI Linear Baseline
0.6-
MI Linear Baseline
27
Fitted
-32.00
(per token!
0.3
Reward
32
0.3
28
0.1
-32.10
0.2
-28
0.1
0.0
-28
-32.15
0.0
-0.1
1000
2000
2500
3000
1000
2000 Average Length L
3000
Average Length L
Figure Additional snowball error verifications. We have conducted extra experiments on larger LLMs, including Qwen2.5- Instruct and Qwen2.5- Instruutt with the same setting results in Figure 2 of our main text.
(a) MI Analysis by Difficulty Levels
(b) Accuracy Analysis by Difficulty Levels
Accuracy vs Length
10
055
1.0
2009
100
1106
61
63
<1000
L0ve
2099
Santn
2008
Longth Responses
Figure 5. Snowball error analysis by different difficulty levels. We have conducted extra experiments analyze the mutual information (MI) and accuracy at different difficulty levels. The questions at the same level share similar difficulty. (a) The MI analysis by difficulty levels. (b) The accuracy analysis by different difficulty levels.
17

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
70
Accuracy
60
50
40
GSM6k
PrOntoQA
30
Max Action
Figure 6. Influence of k. We have conducted extra experiments to further verify Theorem 4.6 by examining the influence of k. The experiments are performed on GSM8k and PrOntoQA, and we vary the value the max max-action an MCTS while keeping other hyperparameters optimal, according to previous studies.
N
6
8
10
14
16
18
20
ORM- 17.96%
29.01 %
38.67%
46.13%
50.83%
53.87%
59.94%
63.81 %
66.85%
67.68%
ORM-Max
17.96%
29.01% %
38.67%
46.13%
50.83%
53.87%
59.94%
63.81 11%
67.13%
68.23%
Table Additional verification for BoN v.s. MCTS in Game24. The baseline MCTS obtain accuracy of 64.80% where Noe. 6.08 and Nam 18.24.
increases faster than GSM8k when & increases.
D.4. Additional Verification for BoN v.s. MCTS
We conducted additional verification experiments using the Game24 benchmark (Yao et al., 2024), which requires solving arithmetic puzzles to obtain the number 24. The setting similar with Figure 3, and we present the results Table
This result illustrates similar conclusion to Fig.3, when the total reasoning cost comparable, BoN can achieve a comparable and even better performance than MCTS.
E. More External Slow-Thinking Mechanisms Analysis
The external slow-thinking methods sometimes not only expand the width of the search space, but also perform repeatedly sampling and evaluating.
For example, besides expanding the width, Lookahead Search increase the computation steps in evaluating the thought by looking ahead for steps. This can be seen as a test of whether the current thought is good enough, i.e., affecting cb-
An intuitive understanding is that the more steps look ahead, the more likely can find the best thought. This is due the fact that the probability of generating correct thought is related to the layer index I, and the probability of generating correct thought increases with the layer index l.
Definition E. (6-wrong thought.) A thought rı is considered as 5-wrong if the difference between the thought and the golden thought is larger than 5, i.e (Ø(n) <(r)) 2 6.
Lemma F.2. (probability of generating 5-wrong thought.) The probability of generating d-wrong thought is:
Pr Pr(((m)) -(7)))))7r7)(1 2 = max(1 >1.
(20)
18

---

Rethinking External Slow-Thinking: From Snowball Errors to Probability of Correct Reasoning
Definition E.3. (distinguishable condition.) We now assume that e; is guaranteed only if the correct thought and woring thuought distinguishable. That is, given correct thought rı (should be selected) and wrong thought ri (should not be selected), the following inequality holds:
Pr [o(r)) 6( 8-
(21)
We further analysis the lower bound of eq. (21) in the following theorem.
Theorem E.4. (lower bound of distinguishable condition.) The distinguishable condition is guaranteed with the following probability lower bound with the condition when 2 In >x:
Pr [Ø(r)) o(r, ) 2 8-8 --
= Ardse-
(22)
Proof.
Pr [d(n)) - x(r)) 2 - -] = Pr [d(ri) - o(T)) )- - [o(rt) - 66
(23)
2 Pr [d(r)) - p(r)) ) 2 6) x Pr(o(ri) - 6(r) s].
-r(o(r))-o(r)
For the first term, since Pr [ő(r))- ((T))))))))) 2 max(1 Age 0), we have:
Pr [o(r)) <(T)) 2 6 > 1 - Age
(24)
While for the second term, since 2 In X, have X-e 1 s thus
Pr Pr(o(rī) 6(n) S minn( ,1 ,,
(25)
With eq (23), we have
Pr (r(o(r))((r7)) -
2 2 Pr (o(1)) ((T))) 2 20 x Pr((o(r)) - p(n) s|
2 (1 Ase X
(26)
A,e ArdsE
This finishes the proof.
With theorem E.4, we can derive the best setting of rollout step y in Lookahead Search. Corollary E.S. (best setting of rollout step in Lookahead Search.) The best setting of rollout step 7 in the I-th layer in Lookahead Search is:
गt = max(In 2hs - 1,0).
(27)
Proof. Evaluating the thought in the 1-th layer by looking ahead for 7 steps, the lower bound of distinguishable condition is:
f(n) = Are (1+x) -(+-m) - Ap7aee -(1++x),
(28)
the derivation of f(1) is:
d f(m) -(+x0) 2d,dse 2(1+)) dr
(29)
-> -1tre) 22se
Let d. drg f(x) O, have:
3t 1n l.
(30)
Considering the practical meaning, we have
n max 0) max(In 2\a 1,0).
(31)
This finishes the proof.
This corollary shows that the best setting of rollout step y in Lookahead Search is related to the layer index I, and not always the larger the better.
19


Reviews:
[{"review_id": "ONva3iIplB", "reviewer": "Reviewer_yYwM", "summary": "The paper analyzes the mathematical mechanism behind the slow thinking of large language models. First, the authors define snowball errors using information theory. Then, they derive a lower bound on the probability of reasoning errors based on snowball errors. This bound indicates that the probability of errors increases as snowball errors accumulate. Their further derivation shows that the probability of generating a correct response decreases exponentially with reasoning length. They then prove that expanding the reasoning space through slow thinking can increase the probability of correct reasoning. Finally, they compare two slow-thinking methods, BoN and MCTS, finding that the key factors influencing the results are the capability of the reward function and the total reasoning cost.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable feedback. Below are our point-by-point responses:\n\n## Lack of Empirical Verification for Proposition 4.3\n\nProposition 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**. \n\n**(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$. \n\nTo address your concern, we relax the original assumption and demonstrate that our core results hold under a more general condition:\n> **Relaxed Proposition 4.3:** \n> \n> 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., \n> \n> $ \\operatorname{Pr}\\left[|\\phi(r_l)-\\phi(r_l^*)| \\leq \\tau\\right] = \\operatorname{min} \\left( \\xi(l,\\tau),1 \\right),$ \n> \n> where $\\xi(l,\\tau) \\geq 0$ decreases monotonically with $l$ and converges to $0$. \n\n\nUnder this weaker condition, we derive revised bounds presented in the bullet list below: \n\n- **Lemma 4.4:** $\\xi^{L}(l,\\tau)$,\n- **Lemma 4.5:** $\\prod_{l=1}^{L}\\epsilon_b \\left[ 1-\\left( 1-\\xi(l,\\tau) \\right)^k \\right]$,\n- **Theorem 4.6:** $\\epsilon_b^L k^L \\xi^{L}(l,\\tau)$,\n- **Lemma 5.1:** $\\epsilon_N N^L \\xi^{L}(l,\\tau)$,\n- **Lemma 5.2:** $\\epsilon_b^L b^L \\xi^{L}(l,\\tau)$,\n- **Lemma 5.3:** $b^{\\frac{L(L+1)}{2}}\\xi^{L}(l,\\tau)\\prod_{l=1}^{L}\\epsilon_{b^l}$,\n\nwhere $\\xi^{L}(l,\\tau) := \\prod_{l=1}^{L}\\xi(l,\\tau)$. \n\nThese 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***. \n\n\n**(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. \n\n## LLMs in Different Sizes\nWe 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. \n\nThe 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. \nWe maintained identical experimental settings and workflow as described in Figure 2 to ensure methodological consistency. \n\nOur key findings from these additional experiments demonstrate that:\n- The MI (Mutual Information) decay pattern remains consistent across larger model sizes, exhibiting similar behavior to smaller models.\n- Response quality continues to show a negative correlation with output length, as observed in our original experiments.\n\nThese significant findings will be systematically incorporated into our revised manuscript, including comprehensive analysis for the extra results and corresponding updates to Figures/Tables. \n\n\n## Typos and Figure Ticks\nWe 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. \n\nWe believe these responses adequately address all concerns raised. We greatly appreciate your time and constructive feedback.", "claims_and_evidence": "Mostly good. All the statements have been theoretically proven. The author provides empirical verification for the existence of snowball errors and the comparison between BoN and MCTS. However, there is no empirical verification for the statement that \"the probability of generating a correct response decreases exponentially with reasoning length.\"", "methods_and_evaluation_criteria": "The selected benchmarks are suitable.", "theoretical_claims": "Yes, all are correct.", "experimental_designs_or_analyses": "The selected LLMs are all small (< 10B). The verification will be more robust by selecting models of different sizes.", "relation_to_broader_scientific_literature": "The paper provide a theoretical perspective to analyze the slow-thinking mechanism. `It proves the slow-thinking methods are effective to improve the reasoning correctness of LLMs", "essential_references_not_discussed": "As far as I know, no more papers need to be discussed or cited.", "other_strengths_and_weaknesses": "Strengths: This paper provides a systematic theoretical study of the mechanism of slow-thinking.\n\nWeaknesses: There is no empirical verification for the claim that \"the probability of generating a correct response decreases exponentially with the reasoning length L.\" I believe this verification can be conducted by annotating the reasoning length of each question in a dataset (e.g., GSM8K) and then analyzing the relationship between accuracy and length to determine if accuracy indeed decreases exponentially with the reasoning length.", "other_comments_or_suggestions": "- line 238: leangth -> length. \n- Figure 3: set the tick numbers on the x-axis to integers.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6fg0s3To3Q", "reviewer": "Reviewer_UzVe", "summary": "This paper aims to provide rationales for the effectiveness of inference-time compute scaling, also known as slow thinking, particularly from an information-theoretic perspective.\n\nFirst, it argues that as the length of a reasoning path increases, the probability of encountering an error along the path also grows, potentially at a rate exceeding linear scaling.\n\nSecond, it posits that slow-thinking methods enhance reasoning by expanding the breadth of the reasoning space, thereby increasing the likelihood of generating a correct response. However, their effectiveness depends on the quality of the selection module, which is responsible for identifying the correct response from among the candidates.\n\nAll of these claims are substantiated and analyzed through mathematical frameworks and empirical experiments, at least according to the authors.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the thorough and constructive reviews. Below we address each concern raised by the reviewers.\n\n## Concerns about the Assumptions\nWe 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.\n\n**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.** \n\n**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. \n\n**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. \n\nAnother 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. \n\n\n## More Experiments\nWe appreciate the reviewer's suggestions for expanded experimental validation and are pleased to provide additional empirical evidence or explanations as follows. \n\n1) **Extra Benchmark Task: Game of 24**. \nWe 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:\n\n|  $N$   | 2  | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |\n|  -  | - | - | - | - | - | - | - | - | -| -|\n| ORM-Vote  | 17.96% | 29.01% | 38.67% | 46.13% | 50.83% | 53.87% | 59.94% | 63.81% | 66.85% | 67.68% |\n| ORM-Max  | 17.96% | 29.01% | 38.67% | 46.13% | 50.83% | 53.87% | 59.94% | 63.81% | 67.13% | 68.23% |\n\n**where $N_{res}=6.08,N_{call}=18.24$, and baseline MCTS obtain an accuracy of 64.80%.** \nThis 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. \n\n2) **Larger LLMs**. \nBeyond 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. \n\n3) **Alternative Search Algorithms**. \nWe categorize existing approaches into:\n- **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! \n- **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.** \n\n\n[1] Tree of thoughts: Deliberate problem solving with large language models (NeurIPS 2023).\n\n[2] AlphaZero-like tree-search can guide large language model decoding and training (ICML 2024).\n\n## Essential References Not Discussed\nWe appreciate your suggested references and will incorporate them in our revision.", "claims_and_evidence": "- Claim 1 (Section 3): The probability of a reasoning error is lower-bounded by a certain threshold, derived from the concept of snowball errors introduced in Section 2.\n- Evidence 1: The mathematical proofs presented in Sections 2 and 3 appear reasonable, though I am not entirely certain. However, they rely on a strong assumption that each reasoning step follows a single gold-standard thought process. This assumption contradicts the widely accepted notion that multiple reasoning paths can lead to the same answer. Additionally, it is somewhat trivial to observe that as the length of a model-generated sequence increases, errors occurring earlier in the sequence are more likely to have a greater impact on later parts.\n\n***\n\n- Claim 2 (Section 4): The probability of correct reasoning in recent external slow-thinking methods depends on the combined process of generating multiple answer candidates and selecting the correct one from the pool.\n- Evidence 2: This argument is reasonable; however, it is not entirely convincing to assume that there exists only a single gold-standard reasoning path, as stated in Section 4 (r_l^*).", "methods_and_evaluation_criteria": "The paper primarily focuses on investigating the inner workings of slow thinking rather than proposing a new solution or method for further improvement. As a result, it does not discuss the novelty or effectiveness of any proposed approach.\n\nNevertheless, the study would have been more insightful if it had incorporated a broader range of related methods beyond BoN and MCTS in its experiments.", "theoretical_claims": "This paper presents a series of definitions, proofs, and lemmas, most of which appear reasonable. However, I have some concerns, as mentioned above. Additionally, I acknowledge the possibility of mathematical errors in the provided proofs that I may not have detected.", "experimental_designs_or_analyses": "The empirical experiments are limited in terms of both the target tasks and the models used. Specifically, only 8B-scale models are evaluated, and the study focuses on just two tasks (GSM8K and ProntoQA). This raises concerns about the generalizability of the findings to models of different sizes and a broader range of tasks.", "relation_to_broader_scientific_literature": "Inference-time compute scaling, also known as “slow thinking,” is a prominent topic in the machine learning and NLP communities. Consequently, this research is expected to make a meaningful contribution to the literature.", "essential_references_not_discussed": "Maybe not essential but related: How Language Model Hallucinations Can Snowball (ICML 2024)", "other_strengths_and_weaknesses": "Please see the above comments.", "other_comments_or_suggestions": "Please see the above comments.", "questions_for_authors": "Please see the above comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Jtg4X6yfaL", "reviewer": "Reviewer_Qdus", "summary": "The paper focuses on analyzing ``snowball effects'', where the model's implicit thinking process is not well represented by the tokens they generate at each step, hence accumulating throughout the inference. They analyze this phenomenon through information-theoretic perspective to give lower bounds for correct reasoning for well-known methods such BoN and ToT.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable feedback and constructive comments. Below, we provide point-by-point responses to address the raised concerns.\n\n## The Snowball Error and the Length\nWe 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.\n\nTo 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. \n\nThe 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. \n\nMoreover, 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]. \n\n[1] Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., ... & Cobbe, K. (2023). Let's verify step by step. ICLR.\n\n[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.\n\n[3] Sui, Y., et al. (2025). Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models. arXiv:2503.16419.\n\n\n\n## Extension to AoT and AoT+\nWe appreciate the suggestion to explore extensions to AoT and AoT+. We would like to address this from two perspectives:\n\n1) **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.\n\n2) **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.\n\n\n## Typos in Proposition 4.3\nAfter careful consideration, we believe Proposition 4.3 is mathematically sound.\n\nWe 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.\n\n## Extension for more Test-Time Scaling Methods\nOur 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:\n\n1) **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.\n2) **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. \n\n[4] Tack, J., et al. (2025). LLM Pretraining with Continuous Concepts. arXiv:2502.08524.\n\n[5] Chen, Y., et al. (2025). Inner thinking transformer: Leveraging dynamic depth scaling to foster adaptive internal thinking. arXiv:2502.13842.\n\n[6] Yu, Q., et al. (2025). Enhancing Auto-regressive Chain-of-Thought through Loop-Aligned Reasoning. arXiv:2502.08482.\n\nWe believe these responses adequately address all concerns raised. We greatly appreciate your time and constructive feedback.", "claims_and_evidence": "I found Figure 2 to be confusing. If the problem has more variables/steps to arrive at an answer, the length $L$ will naturally be greater, this might also reduce the performance since at each step, the model will need to choose the next step from more options (since we have more variables). However, this is also correlated with step length $L$, worrying me that the snowballing effect is a side effect of this, and not being able to represent the implicit thinking in the generated tokens. Perhaps, testing this idea on other datasets where the length of the solution does not necessarily imply a more difficult solution (such as adding $n$ many numbers, though this is just an option).", "methods_and_evaluation_criteria": "See the previous section.", "theoretical_claims": "I did check the proofs. I believe there is a typo in the proposition 4.3, which the rhs should be 1 - rhs.", "experimental_designs_or_analyses": "Yes, see the previous section.", "relation_to_broader_scientific_literature": "Test-time scaling is significant to improve the performance of pre-trained models in post-training phase, since the current models started to have slower improvements even though the training data and quality in the pre-training stage has never been higher. Having tools to analyze test-time scaling methods is important in the sense that researchers will have tools to improve upon these method. However, I believe the test-time scaling view in the paper, only represents a part of the literature. Newer test-time scaling methods such ``Algorithm of Thoughts'' (AoT) [1] and AoT+ [2] show improvements by scaling the reasoning within-context, in opposed to the methods only considering CoT chains in each context (such as BoN, ToT, GoT, RAP). I believe, if the paper can integrate their analysis to these cases, to perhaps explain their efficiency in terms of output tokens, it can be a significant addition to the reasoning/planning literature.\n\n[1] Algorithm of thoughts: Enhancing exploration of ideas in large language models (ICML 2024), https://arxiv.org/abs/2308.10379\n[2] LLMs Can Plan Only If We Tell Them (ICLR 2025), https://arxiv.org/abs/2501.13545", "essential_references_not_discussed": "Not for the paper's results, but more discussions on test-time scaling methods would be helpful. Please see previous mentioned papers.", "other_strengths_and_weaknesses": "Strengths:\n- Easy to read and well-written\n- The paper proposes a new information-theoretic perspective at investigating the behavior of various test-time scaling methods\n- The topic is timely\n- The experiments are mostly supportive of the narrative\n\nWeaknesses:\n- The algorithms of focus for the analysis can be increased to include methods that have a single context solution such as AoT, as opposed to ToT.\n- Please see previous comments on Figure 2.", "other_comments_or_suggestions": "- Proposition 4.3 might have a typo in the results (see previous comment regarding this).", "questions_for_authors": "- Do the authors think their analysis can be extended to more test-time scaling methods? And can be updated to include hints on the solution efficiency? (producing fewer tokens while having a similar performance)\n\nIn the current state of the paper, I give a ``Weak Accept'' rating, however, if authors make the necessary changes to improve the applicability of the paper as explained in my previous comments, I'd be happy to reconsider my score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "59VHzwMizO", "reviewer": "Reviewer_A7PQ", "summary": "This paper analyzes the potential snowball error effect that may occur during the reasoning process of Large Language Models (LLMs), and connects it to the probability of correct reasoning using information theory. Within this theoretical framework, external slow thinking methods can be interpreted as strategies for reducing the probability of errors.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable feedback. Below, we address your concerns point by point.\n\n## Regarding Prior Work [1]\nWhile 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.**\n\nThe 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.** \n\nWe 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. \n\nSpecifically, we overcome several limitations of [1]:\n\n- [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.\n- [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.\n\n**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. \n\n[1] Ton, J. F., Taufiq, M. F., & Liu, Y. (2024). Understanding Chain-of-Thought in LLMs through Information Theory. arXiv preprint arXiv:2411.11984.\n\n[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.\n\n## Regarding LaTeX Formatting\nWe confirm that our manuscript adheres to ICML 2025’s LaTeX template (https://icml.cc/Conferences/2025/AuthorInstructions), ensuring compliance with formatting guidelines.\n\n## Clarifying the Paper’s Structure\nThank you for your inquiry about the connection between the two aspects of our paper. Below, we provide a detailed explanation:\n\nOverall, the structure of our paper can be divided into 2 parts: \n1) **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. \n2) **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$.\n\n**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). \n\n**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. \n\nFor 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!**", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "In fact, I have thoroughly studied and read the work which is followed by this paper: \"Understanding chain-of-thought in LLMs through information theory.\" This work proposes a theoretical framework for evaluating the correctness of each step in the chain-of-thought (COT) using information theory. However, I personally believe that this work has two major issues ：it has not yet been published or widely validated and recognized. I would like to ask the authors whether they have conducted an analysis of the shortcomings of this theory and made improvements, or if they have directly followed the work as it is.", "experimental_designs_or_analyses": "The paper conducts experimental validation for its two proposed theoretical insights, making them both reliable and clear.", "relation_to_broader_scientific_literature": "Please refer to the section on theoretical claims.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths：\n1.The paper provides a very clear introduction to the background and its proposed theoretical method.\n2.The theoretical framework and contributions of the paper are substantial and meet the high standards expected for ICML submissions.\n\nWeaknesses：\n1. The LaTeX formatting of the paper contains errors, and the wrong template appears to have been selected\n2. The choice of prior work to follow seems questionable; please refer to the section on theoretical claims for specific concerns.\n3. The two main aspects of the paper do not seem to form a cohesive synergy. Specifically, I find that the connection between snowballing errors \n and overthinking is not very apparent.\nI would suggest that the authors provide a more intuitive explanation, rather than relying solely on theoretical arguments for acceptance.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please refer to the section on theoretical claims and Weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zoJPOMs68U", "reviewer": "Reviewer_NREt", "summary": "This paper discusses the issue of understanding and improving external slow-thinking methods in LLM reasoning. The authors (1) propose a theoretical framework based on information theory that analyzes snowball errors and (2) connects them to the probability of reasoning errors in LLMs. This method aims to explain why external slow-thinking works, quantify its limitations, and inform better design of slow-thinking strategies over baseline methods. They provide experimental results to demonstrate how mutual information decays along reasoning steps and validate the presence of snowball errors. They also offer a theoretical comparison of different external slow thinking methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the insightful and constructive feedback provided in your reviews. Below, we address each concern in detail.\n\n## The General Linkage between MI Decay and Reasoning Errors\nWe 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$). \n\nIn 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.\n\n**The internal reflection mechanism constitutes the key distinction between external and internal slow-thinking methods.** \n- External slow-thinking methods rely on **width-expansion**, broadening the search space.\n- Internal slow-thinking methods leverage **reflection**, enabling recovery from intermediate states.\n\nWe 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+). \n\nAdditionally, 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. \n\nWe thank you for your valuable suggestions and will enhance the clarity and comprehensiveness of our manuscript in the revised version.\n\n## The Universality of Snowball Error Dynamics across All Slow-Thinking Methods\nAs 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.\n\nMoreover, 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).\n\n## Detailed Explanation of Figure 2\nWe 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):\n\n1) **Prompting & Inference:**\n    - Models are prompted (see Appendix B.1) to generate step-by-step reasoning.\n    - Observed answers ($r$) and implicit thoughts ($t$, derived from ground-truth rewrites) are collected.\n2) **Mutual Information (MI) Estimation:**\n    - Following prior work, we compute and estimate the MI between $r$ and $t$.\n    - Each question’s result is plotted as a blue dot in Figure 2.\n3) **Reasoning Quality Evaluation:**\n    - An outcome reward model assesses reasoning correctness.\n    - The relationship between MI and reasoning quality is fitted to produce the final curve in Figure 2.\n\nIn the camera-ready version, we will elaborate on Appendix B.1 as per your suggestion to improve clarity.", "claims_and_evidence": "Most of the paper’s claims are supported by empirical evidence. The most important observations are that mutual information tends to decay along reasoning steps and that snowball errors can occur in LLM reasoning chains. \nI have concerns regarding some claims: (1) the general linkage between MI decay and reasoning errors. While MI decay may correlate with reasoning challenges, it is unclear that this directly causes errors, especially given that LLMs often exhibit self-correction abilities during generation. (2) the universality of snowball error dynamics across all slow-thinking methods. Best-of-N and MCTS have fundamentally different mechanisms for handling reasoning. Simply applying a single information-theoretic framework may oversimplify these differences.", "methods_and_evaluation_criteria": "The authors use widely adopted benchmark datasets that are appropriate for evaluation.", "theoretical_claims": "The idea of analyzing and improving external slow-thinking in LLM reasoning through an information-theoretic framework is novel and timely. Most existing work focuses on empirical evaluations of prompting or decoding strategies, but these approaches cannot formally explain why slow-thinking methods work or when they fail, limiting our theoretical understanding and principled design of such methods. This paper introduces a method based on mutual information decay analysis to model snowball errors in reasoning, as well as significantly improves our understanding of the challenges and trade-offs in multi-step LLM reasoning.\n\nThe workflow is well-structured, as it connects theoretical modeling with empirical validation on standard reasoning benchmarks to make the analysis both grounded and actionable. This approach bridges the gap between empirical success of slow-thinking methods and their theoretical understanding, and further provides guidance for designing more robust reasoning strategies in LLMs.", "experimental_designs_or_analyses": "The experiments are extensive, with detailed analysis of the results. These experiments validate the effectiveness of the proposed information-theoretic framework in capturing mutual information decay and reasoning errors. The authors also demonstrate the method's robustness and generality across different sizes and complexities of reasoning datasets and baselines.", "relation_to_broader_scientific_literature": "LLM reasoning and CoT prompting. This paper offers a new theoretical perspective on error accumulation.\nBest-of-N and MCTS. This paper provides an information-theoretic framework to analyze their limitations.\nError propagation. This paper formalizes these as snowball errors driven by mutual information decay.", "essential_references_not_discussed": "Not found.", "other_strengths_and_weaknesses": "See above.", "other_comments_or_suggestions": "Adding a more detailed explanation of Figure 2, including how to interpret the MI curves in relation to reasoning quality, would improve clarity.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x48eHBtfGj", "reviewer": "Reviewer_S59i", "summary": "The paper provides theoretical analysis of the snowball error in reasoning models with external thinking mechanism. The paper unveil some interesting properties of reasoning models. However, the strong assumptions make most results somewhat obvious and/or unhelpful.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable feedback. Below are our responses to the concerns raised. \n\n## About the Probability that the Thoughts are Incorrect\nOur 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$).\n\nWe 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.\n\nWe will improve presentation clarity in the revision.\n\n## About the Formulation of Intermediate Error\nWe 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.** \n\nOur 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.**\n\n## About the Results of Theorem 3.3\nTheorem 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. \n\nThis result is empirically verified by Fig.2 from two aspects. \n- Mutual information decreases (snowball error increases) with $l$ (Definition 2.1 & 2.2).\n- Response quality degrades with decreased MI.\n\nAdditional 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. \n\n## About the Results of Lemma 4.4\nWe understand your concerns may be about ***lemma 4.4*** and will respond from the following two aspects: \n1) **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\"). \n2) **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.** \n\n## Experiments for Theorem 4.6\nWe take theorem 4.6, which is a main result in our paper and lemma 5.x are its derivations, for the subsequent response. \n\nTheorem 4.6 relates reasoning cost ($k$), length ($L$), and value function reliability ($\\epsilon_b$) to the upper bound of correct reasoning probability.\n\n**For $L$:**\n\nThe impact of reasoning length has been implicitly verified through:\n- ***Analysis by Difficulty*** section in our repository. \n- Fig. 2 results. \n\nThis evidence confirms that longer paths increase errors.\n\n**For $k$ and $\\epsilon_b$:**\n\nWe 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.\n\nBesides, 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***. \n\n[1] AlphaZero-like tree-search can guide large language model decoding and training (ICML 2024).\n\nWhile 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.", "claims_and_evidence": "- The setting in the paper is oversimplified, leading to loose bounds and somewhat obvious/unhelpful results. \n    - The authors did not discuss the possibility that the thoughts are incorrect. They only analyzed the errors in transforming thoughts into reasoning tokens. The paper, therefore, provides an incomplete picture of the problem (and a complete analysis is what I expected after reading the introduction. IMHO, the author should rewrite parts of the paper to better reflect the contributions).\n    - The facts that thoughts and reasoning steps are generated sequentially and one mistake in the sequence can lead to wrong output were not discussed and ignored in the formulation.  In the paper, the accumulative error is simply the sum of errors at all steps.\n    - The gap between the true error and the upper bound in theorem 3.3 is too big (Fig. 2). This could be a consequence of the weakness mentioned in the previous point.\n    - Due to the strong assumption on $P(e)$, theorem 4.4 is not very informative. The probability of correct answers decays too fast at the rate of $\\Theta(e^{-L^2})$. This goes against empirical evidence where models can still generate long correct answers with decent probability.\n\nPost rebuttal comments: I raised the score to 3.", "methods_and_evaluation_criteria": "- This is a theory paper so the experiments are for demonstration purposes. The presented experiments are good but some more experiments are needed to validate the theory. For example, experiments for theorem 4.4 and lemma 5.x are missing.", "theoretical_claims": "As stated in the Claim section, the theory is based on strong assumptions leading to somewhat obvious and unhelpful conclusions.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The paper can have a good contribution to the literature if the weaknesses are addressed. Understanding the mechanisms for reasoning is important as it can lead to more effective and efficient reasoning methods.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "No.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Please address the weaknesses mentioned in the previous sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a timely and theoretically grounded analysis of slow-thinking mechanisms in LLMs through the lens of information theory, introducing the notion of snowball errors to formalize error accumulation in reasoning. Reviewers note that some theoretical assumptions may oversimplify real-world dynamics or lead to loose bounds. Although some key claims, such as exponential decay of correctness, lack direct experimental confirmation, reviewers generally agree on the novelty and clarity of the contribution. Despite the raised concerns, the paper opens a promising direction for better understanding and designing inference-time reasoning strategies. Hence, I decide to recommend for weak accept.
Decision: Accept (poster)