Elamur Research⌕
☰
home / papers / 2025 / Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation

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

Paper · 2025 · Juno Kim, Denny Wu, Jason Lee et al.

Summary

This paper gives a theoretical explanation for why extra compute at inference time improves LLM reasoning. That compute can be spent on search against a reward signal and then reused for RL fine-tuning or distillation. The authors model chain-of-thought generation as a random walk on a graph whose nodes are logical statements. Routine steps form densely linked clusters. Difficult steps are rare, low-probability links between clusters, so the walk lingers inside one cluster for a long time before jumping to another. Metastability theory is used to derive tight bounds on how long the walk takes to reach a target. The work uses no datasets or experiments; its contribution is a set of proofs. A search procedure with an intrinsic, curiosity-like reward that favours sparse edges shortens the expected time to reach the answer. Policy-gradient RL can feed this knowledge back into the base model. A compact chain over clusters can also be distilled into a smaller model. The authors further prove that, without global search, a logical version of the task cannot be solved efficiently. This gives test-time scaling a formal footing.

Key points

  • Model: a perturbed Markov chain with K clusters of size about M. Inter-cluster ("hard") edges have probability proportional to ε. Tasks are assumed to need Ω(K) hard steps on average.
  • Optimisation guarantees: the paper analyses a two-stage pretraining scheme for a simple softmax model, which includes a thresholding step that prunes low-probability transitions. It also gives guarantees for RL fine-tuning with PPO-Clip that boosts the identified sparse edges.
  • Distillation: a "meta-chain" defined over the set of clusters keeps only inter-cluster dynamics but preserves escape probabilities. Any set containing one representative per cluster is metastable (Proposition 2.1).
  • Lower bounds: a new statistical query dimension with additional information (SDA) is introduced and compared across four access regimes: no pretraining, path-only, local search and full search. The first three have SDA ≥ e^{Ω(K)}, while full search gives SDA = 1. Gradient-based learners restricted to local information therefore cannot even weakly learn the task in polynomial time.
  • Future directions: the authors suggest search guided by outcome rewards, backtracking-style CoT revision, iterative fine-tuning, and scaling laws for inference compute.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Princeton UniversityPrinceton · United States137 works · 53,849 citations🎓The University of TokyoTokyo · Japan98 works · 9,611 citations🔬RIKEN Center for Advanced Intelligence ProjectTokyo · Japan17 works · 963 citations🔬RIKENWako · Japan31 works · 613 citations

Also on the byline: Flatiron Health.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

🧭 Topics 2Research subjects and languages the work is about.Reasoning · 1,948 worksEfficient models & compression · 328 works

Cite

Cite as Juno Kim, Denny Wu, Jason Lee and Taiji Suzuki. 2025. Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation. arXiv:2502.01694.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2502.01694 · arXiv 2502.01694

@misc{kim2025metastable,
  title = {{Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation}},
  author = {Juno Kim, Denny Wu, Jason Lee and Taiji Suzuki},
  year = {2025},
  doi = {10.48550/arxiv.2502.01694},
  eprint = {2502.01694},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2502.01694}
}

References

79 references, 22 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can transformers reason? The locality barrier and inductive scratchpad. In Advances in Neural Information Processing Systems, 2024. find
  2. Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional AI: harmlessness from AI feedback. arXiv preprint arXiv:2212.08073, 2022.
  3. J. Beltrán and C. Landim. Metastability of reversible finite state Markov processes. Stochastic Processes and their Applications, 121(8):1633–1677, 2011. find
  4. Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial Int… find
  5. Volker Betz and Stéphane Le Roux. Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed Markov chains. Stochastic Processes and their Applications, 126(11): 3499–3526, 2016. find
  6. Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade. Understanding in-context learning in transformers and LLMs by learning to learn discrete functions. In International Conference on Learning Representations, 2024. find
  7. Alessandra Bianchi and Alexandre Gaudillière. Metastable states, quasi-stationary distributions and soft measures. Stochastic Processes and their Applications, 126, 2016. find
  8. Anton Bovier, Michael Eckhoff, Véronique Gayrard, and Markus Klein. Metastability and low lying spectra in reversible Markov chains. Communications in Mathematical Physics, 228:219– 255, 2002. find
  9. Nader Bshouty and Vitaly Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research, 2:529–545, 09 2001. find
  10. Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros. Large-scale study of curiosity-driven learning. In International Conference on Learning Representations, 2018. find
  11. Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019.
  12. David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, 2023. find
  13. Emilio Cirillo, Francesca Nardi, and Julien Sohier. Metastability for general dynamics with rare transitions: escape time and critical configurations. Journal of Statistical Physics, 161, 2014. find
  14. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
  15. Ezra Edelman, Nikolaos Tsilivis, Benjamin L. Edelman, eran malach, and Surbhi Goel. The evolution of statistical induction heads: in-context learning Markov chains. Advances in Neural Information Processing Systems, 2024. find
  16. Konstantin Fackeldey, Alexander Sikorski, and M. Weber. Spectral clustering for non-reversible Markov chains. Computational and Applied Mathematics, 37, 2018. find
  17. Vitaly Feldman. A general characterization of the statistical query complexity. Proceedings of Machine Learning Research, 65:785–830, 2017. find
  18. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. In Advances in Neural Information Processing Systems, 2023a. find
  19. Xidong Feng, Ziyu Wan, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17179, 2023b. find
  20. R. Fernandez, F. Manzo, F. R. Nardi, E. Scoppola, and J. Sohier. Conditioned, quasi-stationary, restricted measures and escape from metastable states. The Annals of Applied Probability, 26(2): 760–793, 2016. find
  21. Roberto Fernandez, Francesco Manzo, Francesca Nardi, and Elisabetta Scoppola. Asymptotically exponential hitting times and metastability: A pathwise approach without reversibility. Electronic Journal of Probability, 20, 2014. find
  22. David Fritzsche, Volker Mehrmann, Daniel Szyld, and Elena Virnik. An SVD approach to identifying metastable states of Markov chains. Electronic Transactions on Numerical Analysis, 29: 46–69, 2008. find
  23. Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D Goodman. Stream of search (SoS): learning to search in language. arXiv preprint arXiv:2404.03683, 2024.
  24. Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. DeepSeek-R1: incentivizing reasoning capability in LLMs via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025.
  25. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556, 2022.
  26. Cheng-Yu Hsieh, Chun-Liang Li, Chih-Kuan Yeh, Hootan Nakhost, Yasuhisa Fujii, Alexander Ratner, Ranjay Krishna, Chen-Yu Lee, and Tomas Pfister. Distilling step-by-step! Outperforming larger language models with less training data and smaller model sizes. arXiv preprint arXiv:2305.02301, 2023.
  27. Xinyang Hu, Fengzhuo Zhang, Siyu Chen, and Zhuoran Yang. Unveiling the statistical foundations of chain-of-thought prompting methods. arXiv preprint arXiv:2408.14511, 2024. — [arXiv:2408.14511](https://arxiv.org/abs/2408.14511) find
  28. Muhammed Emrullah Ildiz, Yixiao Huang, Yingcong Li, Ankit Singh Rawat, and Samet Oymak. From self-attention to Markov models: unveiling the dynamics of generative transformers. In International Conference on Machine Learning, 2024. find
  29. Martin Nilsson Jacobi. A robust spectral method for finding lumpings and meta-stable states of non-reversible Markov chains. Electronic Transactions on Numerical Analysis, 37:296–306, 2010. find
  30. Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. OpenAI o1 system card. arXiv preprint arXiv:2412.16720, 2024.
  31. Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300, 2019. — [arXiv:1803.07300](https://arxiv.org/abs/1803.07300) find
  32. Andy L Jones. Scaling scaling laws with board games. arXiv preprint arXiv:2104.03113, 2021. — [arXiv:2104.03113](https://arxiv.org/abs/2104.03113) find
  33. Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, 2011. find
  34. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020.
  35. Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45 (6):983–1006, November 1998. find
  36. Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought. arXiv preprint arXiv:2410.08633, 2024. — [arXiv:2410.08633](https://arxiv.org/abs/2410.08633) find
  37. Team Kimi, Angang Du, Bofei Gao, Bowei Xing, Changjiu Jiang, Cheng Chen, Cheng Li, Chenjun Xiao, Chenzhuang Du, Chonghua Liao, et al. Kimi k1.5: scaling reinforcement learning with LLMs. arXiv preprint arXiv:2501.12599, 2025.
  38. Aviral Kumar, Vincent Zhuang, Rishabh Agarwal, Yi Su, John D Co-Reyes, Avi Singh, Kate Baumli, Shariq Iqbal, Colton Bishop, Rebecca Roelofs, et al. Training language models to self-correct via reinforcement learning. arXiv preprint arXiv:2409.12917, 2024.
  39. C. Landim. Metastability for a non-reversible dynamics: The evolution of the condensate in totally asymmetric zero range processes. Communications in Mathematical Physics, 330, 2012. find
  40. C. Landim. Metastable Markov chains. arXiv preprint arXiv:1807.04144, 2018. — [arXiv:1807.04144](https://arxiv.org/abs/1807.04144) find
  41. Claudio Landim and Tiecheng Xu. Metastability of finite state Markov chains: A recursive procedure to identify slow variables for model reduction. Latin American Journal of Probability and Mathematical Statistics, 13, 2015. find
  42. David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2nd edition, 2009. find
  43. Hongkang Li, Meng Wang, Songtao Lu, Xiaodong Cui, and Pin-Yu Chen. How do nonlinear transformers acquire generalization-guaranteed CoT ability? In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning, 2024a. find
  44. Yingcong Li, Kartik Sreenivasan, Angeliki Giannou, Dimitris Papailiopoulos, and Samet Oymak. Dissecting chain-of-thought: compositionality through in-context filtering and learning. In Advances in Neural Information Processing Systems, 2023. find
  45. Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12875, 2024b. find
  46. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. arXiv preprint arXiv:2305.20050, 2023.
  47. Neal Madras and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, 12, 2001. find
  48. Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Martin Jaggi, Hyeji Kim, and Michael Gastpar. Attention with Markov: A framework for principled analysis of transformers via Markov chains. arXiv preprint arXiv:2402.04161, 2024. — [arXiv:2402.04161](https://arxiv.org/abs/2402.04161) find
  49. William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023. find
  50. Carl D. Meyer. Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems. SIAM Review, 31(2):240–272, 1989. find
  51. Carl Dean Meyer. The dondition of a finite Markov chain and perturbation bounds for the limiting probabilities. SIAM J. Algebraic Discret. Methods, 1:273–283, 1980. find
  52. Eshaan Nichani, Alex Damian, and Jason D. Lee. How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735, 2024. — [arXiv:2402.14735](https://arxiv.org/abs/2402.14735) find
  53. Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114, 2021.
  54. OpenAI. Spinning up: proximal policy optimization (PPO), 2018. https://spinningup.openai.com/en/latest/algorithms/ppo.html. 2025-01-26. ↗
  55. URL Accessed: Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20:1–32, 2015. find
  56. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. OpenAI Blog, 2018. find
  57. Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405.18512, 2024a.
  58. Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. In International Conference on Machine Learning, 2024b. find
  59. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. find
  60. Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning, 2017. find
  61. Ohad Shamir. Distribution-specific hardness of learning neural networks. Journal of Machine Learning Research, 19:32:1–32:29, 2018. find
  62. Kumar Shridhar, Alessandro Stolfo, and Mrinmaya Sachan. Distilling reasoning capabilities into smaller language models. arXiv preprint arXiv:2212.00193, 2022.
  63. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419):1140– 1144, 2018. find
  64. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters. arXiv preprint arXiv:2408.03314, 2024.
  65. Ryan Tifenbach. On an SVD-based algorithm for identifying meta-stable states of Markov chains. Electronic Transactions on Numerical Analysis, 38:17–33, 2011. find
  66. Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625(7995):476–482, 2024.
  67. Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14275, 2022.
  68. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022.
  69. Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, and Jingzhao Zhang. From sparse dependence to sparse attention: unveiling how chain-of-thought enhances transformer sample efficiency. arXiv preprint arXiv:2410.05459, 2024. — [arXiv:2410.05459](https://arxiv.org/abs/2410.05459) find
  70. John Wicks and Amy Greenwald. An algorithm for computing stochastically stable distributions with applications to mltiagent learning in repeated games. In Conference on Uncertainty in Artificial Intelligence, 2005. find
  71. Geoffrey Wolfer and Aryeh Kontorovich. Estimating the mixing time of ergodic Markov chains. arXiv preprint arXiv:1902.01224, 2022. — [arXiv:1902.01224](https://arxiv.org/abs/1902.01224) find
  72. Yangzhen Wu, Zhiqing Sun, Shanda Li, Sean Welleck, and Yiming Yang. Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models. arXiv preprint arXiv:2408.00724, 2024.
  73. Violet Xiang, Charlie Snell, Kanishk Gandhi, Alon Albalak, Anikait Singh, Chase Blagden, Duy Phung, Rafael Rafailov, Nathan Lile, Dakota Mahan, et al. Towards System 2 reasoning in LLMs: learning how to think with meta chain-of-thought. arXiv preprint arXiv:2501.04682, 2025.
  74. Yuxi Xie, Anirudh Goyal, Wenyue Zheng, Min-Yen Kan, Timothy P. Lillicrap, Kenji Kawaguchi, and Michael Shieh. Monte Carlo tree search boosts reasoning via iterative preference learning. arXiv preprint arXiv:2405.00451, 2024. find
  75. Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? arXiv preprint arXiv:1905.13211, 2019. find
  76. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024. find
  77. Oussama Zekri, Ambroise Odonnat, Abdelhakim Benechehab, Linus Bleistein, Nicolas Boullé, and Ievgen Redko. Large language models as Markov chains. arXiv preprint arXiv:2410.02724, 2024. — [arXiv:2410.02724](https://arxiv.org/abs/2410.02724) find
  78. Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476–15488, 2022.
  79. Table of Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/kim-2025-metastable-dynamics-chain-thought-reasoning/