mlsanityData to 7 Oct 2026

Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation

arXiv 2502.01694 ↗First posted 2 Feb 2025cs.AI cs.LG stat.MLcited by 25

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

also in 1 more
Abstract (arXiv)

A key paradigm to improve the reasoning capabilities of large language models (LLMs) is to allocate more inference-time compute to search against a verifier or reward model. This process can then be utilized to refine the pretrained model or distill its reasoning patterns into more efficient models. In this paper, we study inference-time compute by viewing chain-of-thought (CoT) generation as a metastable Markov process: easy reasoning steps (e.g., algebraic manipulations) form densely connected clusters, while hard reasoning steps (e.g., applying a relevant theorem) create sparse, low-probability edges between clusters, leading to phase transitions at longer timescales. Under this framework, we prove that implementing a search protocol that rewards sparse edges improves CoT by decreasing the expected number of steps to reach different clusters. In contrast, we establish a limit on reasoning capability when the model is restricted to local information of the pretrained graph. We also show that the information gained by search can be utilized to obtain a better reasoning model: (1) the pretrained model can be directly finetuned to favor sparse edges via policy gradient methods, and moreover (2) a compressed metastable representation of the reasoning dynamics can be distilled into a smaller, more efficient model.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 33 of its 78 references that are in the map. First posted on arXiv 2 Feb 2025.

Builds on

33 of 78 references.

Closest ancestors · 8

Same direction, newest first

  1. 2025Towards System 2 Reasoning in LLMs: Learning How to Think With Meta Chain-of-Thought8 Jan
  2. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought11 Oct
  3. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency7 Oct
  4. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods25 Aug
  5. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithms28 May
  6. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  7. 2023The Expressive Power of Transformers with Chain of Thought11 Oct
  8. 2022Distilling Reasoning Capabilities into Smaller Language Models1 Dec

Other references · 25

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2024The Llama 3 Herd of Modelscited by 14,192
  3. 2020Scaling Laws for Neural Language Modelscited by 6,411
  4. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  5. 2023Let's Verify Step by Stepcited by 3,598
  6. 2022Constitutional AI: Harmlessness from AI Feedbackcited by 2,950
  7. 2022Training Compute-Optimal Large Language Modelscited by 2,927
  8. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
  9. 2024OpenAI o1 System Cardcited by 1,220
  10. 2025Kimi k1.5: Scaling Reinforcement Learning with LLMscited by 1,193
  11. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  12. 2022Solving math word problems with process- and outcome-based feedbackcited by 871
13 more
  1. 2023Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizescited by 710
  2. 2024Training Language Models to Self-Correct via Reinforcement Learningcited by 405
  3. 2023Alphazero-like Tree-Search can Guide Large Language Model Decoding and Trainingcited by 291
  4. 2024Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Modelscited by 282
  5. 2024Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learningcited by 238
  6. 2019What Can Neural Networks Reason About?cited by 155
  7. 2024Stream of Search (SoS): Learning to Search in Languagecited by 141
  8. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 114
  9. 2018Risk and parameter convergence of logistic regressioncited by 81
  10. 2021Scaling Scaling Laws with Board Gamescited by 62
  11. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 39
  12. 2024Large Language Models as Markov Chainscited by 33
  13. 2019Estimating the Mixing Time of Ergodic Markov Chainscited by 24

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 13; 2026: 12.

25 papers.

Sort:

By area:

  1. 2025Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Modelscited by 381
  2. 2025From System 1 to System 2: A Survey of Reasoning Large Language Modelscited by 319
  3. 2025Big-Math: A Large-Scale, High-Quality Math Dataset for Reinforcement Learning in Language Modelscited by 104
  4. 2025Topology of Reasoning: Understanding Large Reasoning Models through Reasoning Graph Propertiescited by 28
  5. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  6. 2025Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalizationcited by 12
  7. 2025DAG-Math: Graph-of-Thought Guided Mathematical Reasoning in LLMscited by 4
  8. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
  9. 2025Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectoriescited by 3
  10. 2026Reliable Chain-of-Thought via Prefix Consistencycited by 3
  11. 2025Data Shifts Hurt CoT: A Theoretical Studycited by 2
  12. 2026A Relative-Budget Theory for Reinforcement Learning with Verifiable Rewards in Large Language Model Reasoningcited by 2
13 more
  1. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  2. 2026Reasoning about Reasoning: BAPO Bounds on Chain-of-Thought Token Complexity in LLMscited by 1
  3. 2026Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Tracescited by 1
  4. 2026Post-Training with Policy Gradients: Optimality and the Base Model Barriercited by 1
  5. 2026A Theoretical Framework for Self-Play Theorem Proving Algorithmscited by 1
  6. 2025Reasoning without Regretcited by 0
  7. 2025ARM: Discovering Agentic Reasoning Modules for Generalizable Multi-Agent Systemscited by 0
  8. 2025Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methodscited by 0
  9. 2026Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Proverscited by 0
  10. 2026How Transformers Learn to Plan via Multi-Token Predictioncited by 0
  11. 2026Memory as a Markov Matrix: Sample Efficient Knowledge Expansion via Token-to-Dictionary Mappingcited by 0
  12. 2026Provable Benefits of RLVR over SFT for Reasoning Models: Learning to Backtrack Efficientlycited by 0
  13. 2026Langevin-Informed Transfer Learning: Replacing Target Samples by Black-Box Feedbackcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Mean-Field Dynamics of Chain-of-Thought Reasoning in Large Language Models
  2. 2026When LLM Meets Tree Search: A Systematic View of Inference as Search in Large Language Models
  3. 2026Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models
  4. 2025Early Stopping Chain-of-thoughts in Large Language Models
  5. 2025From Reasoning to Super-Intelligence: A Search-Theoretic Perspective
  6. 2025Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures
  7. 2025Why Does Reasoning Length Converge? Unveiling the Underfitting-Overfitting Trade-off in Chain-of-Thought
  8. 2025Explainable Chain-of-Thought Reasoning: An Empirical Analysis on State-Aware Reasoning Dynamics