Research map / Large language models / Reasoning and chain of thought

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

ICML 2025 · Large language models › Reasoning and chain of thought · approach: Efficient and adaptive thinking · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives an information-theoretic account of external slow-thinking (test-time scaling) in LLM reasoning, linking snowball errors to a lower bound on reasoning error and an upper bound on correct-reasoning probability for BoN and MCTS, with small GSM8K/PrOntoQA/Game24 comparisons.

Problem

Test-time scaling (slow-thinking) improves multi-step LLM reasoning, but the mechanisms behind external slow-thinking methods are poorly understood and costly to tune.

Approach

Defines snowball errors as cumulative information loss (via mutual information between implicit thoughts and responses), derives lower bounds on per-step reasoning error via Fano's inequality, and models external slow-thinking as width expansion plus selection, yielding upper bounds on correct-reasoning probability for BoN and MCTS and a cost comparison between them.

Key results

• Estimated per-token mutual information between reasoning and golden thoughts decays faster than linearly (nearly exponentially) with response length on GSM8K for Llama-3.1-8B, Qwen2.5-7B and Skywork-o1-8B.
• Theory: BoN matches the best-case MCTS correct-reasoning bound with N=O(b) and the worst-case bound with N=O(b^{L/2}), so BoN's total cost is comparable to MCTS.
• On Game24, BoN with ORM-Vote reaches 67.68% at N=20, versus a baseline MCTS accuracy of 64.80%.

Measured effects reported in the paper

Surprising findings

• Authors report that a reward-model-guided Best-of-N can match or surpass MCTS when cost is aligned, suggesting the specific search framework matters less than total reasoning cost.
• Response quality (reward) tends to decline with longer responses, consistent with overthinking harming accuracy on level-1 MATH problems.

Limitations

• Key modeling assumptions (exponential decay of step-correct probability, P(e_l)=1-lambda e^{-l}) are hypothesized rather than derived from data.
• Mutual information is estimated via HSIC on rewritten golden answers, an approximate proxy for the implicit thought t.
• MCTS best/worst-case analysis is idealized, and the empirical comparison covers only a few tasks with a single base model family.

Experimental setup

Datasets: GSM8K PrOntoQA Game24 MATH-500

Benchmarks: GSM8K PrOntoQA Game24 MATH-500

Metrics: accuracy mutual information estimate (HSIC, per token) reward score

Baselines: Best-of-N MCTS Self-Consistency beam search

Builds on: Chain-of-Thought Self-Consistency RAP Tree of Thoughts Fano's inequality

Closest papers by meaning

• Does Thinking More Always Help? Mirage of Test-Time Scaling in Reasoning Models (NeurIPS 2025 · similarity 0.91)
• Don’t Think Longer, Think Wisely: Optimizing Thinking Dynamics for Large Reasoning Models (NeurIPS 2025 · similarity 0.90)
• Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning (NeurIPS 2025 · similarity 0.90)
• The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity (NeurIPS 2025 · similarity 0.90)
• Think or Not? Exploring Thinking Efficiency in Large Reasoning Models via an Information-Theoretic Lens (NeurIPS 2025 · similarity 0.90)
• The Illusion of Diminishing Returns: Measuring Long Horizon Execution in LLMs (ICLR 2026 · similarity 0.90)