---
title: "Metastable Dynamics of Chain-of-Thought Reasoning: Provable"
description: "This paper gives a theoretical explanation for why extra compute at inference time improves LLM… 79 references, cited by 6 papers here."
authors: ["Juno Kim", "Denny Wu", "Jason Lee", "Taiji Suzuki"]
year: 2025
venue: "arXiv:2502.01694"
source: "https://arxiv.org/abs/2502.01694"
doi: "10.48550/arxiv.2502.01694"
arxiv: "2502.01694"
licence: "CC BY 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/kim-2025-metastable-dynamics-chain-thought-reasoning/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/kim-2025-metastable-dynamics-chain-thought-reasoning/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2025](https://md.research.elamur.ai/free/en/papers/2025/page/13/) / 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

**Authors:** Juno Kim, Denny Wu, [Jason Lee](https://md.research.elamur.ai/free/en/authors/jason-d-lee/) and Taiji Suzuki · **Year:** 2025 · **Venue:** arXiv:2502.01694 · **Licence:** [CC BY 4.0 (arXiv)](http://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2502.01694) · [PDF](https://arxiv.org/pdf/2502.01694) · [DOI 10.48550/arxiv.2502.01694](https://doi.org/10.48550/arxiv.2502.01694) · [arXiv 2502.01694](https://arxiv.org/abs/2502.01694) · [OpenAlex](https://openalex.org/W4407184659)

**Citations:** 0 citations (OpenAlex, 2026-10-14) · [6](https://md.research.elamur.ai/free/en/papers/kim-2025-metastable-dynamics-chain-thought-reasoning/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## 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 University](https://md.research.elamur.ai/free/en/universities/princeton-university/) — University, Princeton, United States · 137 works · 53,849 citations
- [The University of Tokyo](https://md.research.elamur.ai/free/en/universities/the-university-of-tokyo/) — University, Tokyo, Japan · 98 works · 9,611 citations
- [RIKEN Center for Advanced Intelligence Project](https://md.research.elamur.ai/free/en/labs/riken-center-for-advanced-intelligence-project/) — Research institute, Tokyo, Japan · 17 works · 963 citations
- [RIKEN](https://md.research.elamur.ai/free/en/labs/riken/) — Research institute, Wako, Japan · 31 works · 613 citations

Also on the byline: [Flatiron Health](https://ror.org/0508h6p74).

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 19,503 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 18,805 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 17,959 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 17,789 works

🧭 Topics (2): [🧮 Reasoning](https://md.research.elamur.ai/free/en/topics/reasoning/) · 1,948 works · [🪶 Efficient models & compression](https://md.research.elamur.ai/free/en/topics/efficient-models/) · 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.

```bibtex
@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}
}
```

- [← previous MetaFaith: Faithful Natural Language Uncertainty Expression in LLMs](https://md.research.elamur.ai/free/en/papers/liu-2025-metafaith-faithful-natural-language-uncertainty/)
- [next → Minimal Pair-Based Evaluation of Code-Switching](https://md.research.elamur.ai/free/en/papers/sterner-2025-minimal-pair-based-evaluation-code/)
- [↑ back to papers of 2025](https://md.research.elamur.ai/free/en/papers/2025/page/13/)

## 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](https://scholar.google.com/scholar?q=Emmanuel+Abbe%2C+Samy+Bengio%2C+Aryo+Lotfi%2C+Colin+Sandon%2C+and+Omid+Saremi%2E+How+far+can+transformers+reason%3F+The+locality+barrier+and+inductive+scratchpad%2E+In+Advances+in+Neural+Information+Processing+Syst)
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](https://md.research.elamur.ai/free/en/papers/bai-2022-constitutional-ai-harmlessness-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](https://scholar.google.com/scholar?q=J%2E+Beltra%CC%81n+and+C%2E+Landim%2E+Metastability+of+reversible+finite+state+Markov+processes%2E+Stochastic+Processes+and+their+Applications%2C+121%288%29%3A1633%E2%80%931677%2C+2011%2E)
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](https://scholar.google.com/scholar?q=Maciej+Besta%2C+Nils+Blach%2C+Ales+Kubicek%2C+Robert+Gerstenberger%2C+Michal+Podstawski%2C+Lukas+Gianinazzi%2C+Joanna+Gajda%2C+Tomasz+Lehmann%2C+Hubert+Niewiadomski%2C+Piotr+Nyczyk%2C+et+al%2E+Graph+of+thoughts%3A+solving+el)
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](https://scholar.google.com/scholar?q=Volker+Betz+and+Ste%CC%81phane+Le+Roux%2E+Multi%2Dscale+metastable+dynamics+and+the+asymptotic+stationary+distribution+of+perturbed+Markov+chains%2E+Stochastic+Processes+and+their+Applications%2C+126%2811%29%3A+3499%E2%80%93352)
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](https://scholar.google.com/scholar?q=Satwik+Bhattamishra%2C+Arkil+Patel%2C+Phil+Blunsom%2C+and+Varun+Kanade%2E+Understanding+in%2Dcontext+learning+in+transformers+and+LLMs+by+learning+to+learn+discrete+functions%2E+In+International+Conference+on+Lea)
7. Alessandra Bianchi and Alexandre Gaudillière. Metastable states, quasi-stationary distributions and soft measures. Stochastic Processes and their Applications, 126, 2016. [find](https://scholar.google.com/scholar?q=Alessandra+Bianchi+and+Alexandre+Gaudillie%CC%80re%2E+Metastable+states%2C+quasi%2Dstationary+distributions+and+soft+measures%2E+Stochastic+Processes+and+their+Applications%2C+126%2C+2016%2E)
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](https://scholar.google.com/scholar?q=Anton+Bovier%2C+Michael+Eckhoff%2C+Ve%CC%81ronique+Gayrard%2C+and+Markus+Klein%2E+Metastability+and+low+lying+spectra+in+reversible+Markov+chains%2E+Communications+in+Mathematical+Physics%2C+228%3A219%E2%80%93+255%2C+2002%2E)
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](https://scholar.google.com/scholar?q=Nader+Bshouty+and+Vitaly+Feldman%2E+On+using+extended+statistical+queries+to+avoid+membership+queries%2E+Journal+of+Machine+Learning+Research%2C+2%3A529%E2%80%93545%2C+09+2001%2E)
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](https://scholar.google.com/scholar?q=Yuri+Burda%2C+Harri+Edwards%2C+Deepak+Pathak%2C+Amos+Storkey%2C+Trevor+Darrell%2C+and+Alexei+A%2E+Efros%2E+Large%2Dscale+study+of+curiosity%2Ddriven+learning%2E+In+International+Conference+on+Learning+Representations%2C+20)
11. Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. [Exploration by random network distillation](https://md.research.elamur.ai/free/en/papers/burda-2018-exploration-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](https://scholar.google.com/scholar?q=David+Chiang%2C+Peter+Cholak%2C+and+Anand+Pillay%2E+Tighter+bounds+on+the+expressivity+of+transformer+encoders%2E+In+International+Conference+on+Machine+Learning%2C+2023%2E)
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](https://scholar.google.com/scholar?q=Emilio+Cirillo%2C+Francesca+Nardi%2C+and+Julien+Sohier%2E+Metastability+for+general+dynamics+with+rare+transitions%3A+escape+time+and+critical+configurations%2E+Journal+of+Statistical+Physics%2C+161%2C+2014%2E)
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](https://md.research.elamur.ai/free/en/papers/grattafiori-2024-llama-3-herd-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](https://scholar.google.com/scholar?q=Ezra+Edelman%2C+Nikolaos+Tsilivis%2C+Benjamin+L%2E+Edelman%2C+eran+malach%2C+and+Surbhi+Goel%2E+The+evolution+of+statistical+induction+heads%3A+in%2Dcontext+learning+Markov+chains%2E+Advances+in+Neural+Information+Proc)
16. Konstantin Fackeldey, Alexander Sikorski, and M. Weber. Spectral clustering for non-reversible Markov chains. Computational and Applied Mathematics, 37, 2018. [find](https://scholar.google.com/scholar?q=Konstantin+Fackeldey%2C+Alexander+Sikorski%2C+and+M%2E+Weber%2E+Spectral+clustering+for+non%2Dreversible+Markov+chains%2E+Computational+and+Applied+Mathematics%2C+37%2C+2018%2E)
17. Vitaly Feldman. A general characterization of the statistical query complexity. Proceedings of Machine Learning Research, 65:785–830, 2017. [find](https://scholar.google.com/scholar?q=Vitaly+Feldman%2E+A+general+characterization+of+the+statistical+query+complexity%2E+Proceedings+of+Machine+Learning+Research%2C+65%3A785%E2%80%93830%2C+2017%2E)
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](https://scholar.google.com/scholar?q=Guhao+Feng%2C+Bohang+Zhang%2C+Yuntian+Gu%2C+Haotian+Ye%2C+Di+He%2C+and+Liwei+Wang%2E+Towards+revealing+the+mystery+behind+chain+of+thought%3A+a+theoretical+perspective%2E+In+Advances+in+Neural+Information+Processing+)
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](https://scholar.google.com/scholar?q=Xidong+Feng%2C+Ziyu+Wan%2C+Muning+Wen%2C+Stephen+Marcus+McAleer%2C+Ying+Wen%2C+Weinan+Zhang%2C+and+Jun+Wang%2E+Alphazero%2Dlike+tree%2Dsearch+can+guide+large+language+model+decoding+and+training%2E+arXiv+preprint+arXiv%3A2)
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](https://scholar.google.com/scholar?q=R%2E+Fernandez%2C+F%2E+Manzo%2C+F%2E+R%2E+Nardi%2C+E%2E+Scoppola%2C+and+J%2E+Sohier%2E+Conditioned%2C+quasi%2Dstationary%2C+restricted+measures+and+escape+from+metastable+states%2E+The+Annals+of+Applied+Probability%2C+26%282%29%3A+760%E2%80%93793)
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](https://scholar.google.com/scholar?q=Roberto+Fernandez%2C+Francesco+Manzo%2C+Francesca+Nardi%2C+and+Elisabetta+Scoppola%2E+Asymptotically+exponential+hitting+times+and+metastability%3A+A+pathwise+approach+without+reversibility%2E+Electronic+Journal+)
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](https://scholar.google.com/scholar?q=David+Fritzsche%2C+Volker+Mehrmann%2C+Daniel+Szyld%2C+and+Elena+Virnik%2E+An+SVD+approach+to+identifying+metastable+states+of+Markov+chains%2E+Electronic+Transactions+on+Numerical+Analysis%2C+29%3A+46%E2%80%9369%2C+2008%2E)
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](https://md.research.elamur.ai/free/en/papers/gandhi-2024-stream-search-sos-learning-search/). 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](https://md.research.elamur.ai/free/en/papers/deepseek-ai-2025-deepseek-r1-incentivizing-reasoning-capability/). 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](https://md.research.elamur.ai/free/en/papers/hoffmann-2022-training-compute-optimal-large-language/). 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](https://md.research.elamur.ai/free/en/papers/hsieh-2023-distilling-step-step-outperforming-larger/). 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](https://scholar.google.com/scholar?q=Xinyang+Hu%2C+Fengzhuo+Zhang%2C+Siyu+Chen%2C+and+Zhuoran+Yang%2E+Unveiling+the+statistical+foundations+of+chain%2Dof%2Dthought+prompting+methods%2E+arXiv+preprint+arXiv%3A2408%2E14511%2C+2024%2E+%E2%80%94+%5BarXiv%3A2408%2E14511%5D%28https%3A)
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](https://scholar.google.com/scholar?q=Muhammed+Emrullah+Ildiz%2C+Yixiao+Huang%2C+Yingcong+Li%2C+Ankit+Singh+Rawat%2C+and+Samet+Oymak%2E+From+self%2Dattention+to+Markov+models%3A+unveiling+the+dynamics+of+generative+transformers%2E+In+International+Confer)
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](https://scholar.google.com/scholar?q=Martin+Nilsson+Jacobi%2E+A+robust+spectral+method+for+finding+lumpings+and+meta%2Dstable+states+of+non%2Dreversible+Markov+chains%2E+Electronic+Transactions+on+Numerical+Analysis%2C+37%3A296%E2%80%93306%2C+2010%2E)
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](https://md.research.elamur.ai/free/en/papers/openai-2024-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](https://scholar.google.com/scholar?q=Ziwei+Ji+and+Matus+Telgarsky%2E+Risk+and+parameter+convergence+of+logistic+regression%2E+arXiv+preprint+arXiv%3A1803%2E07300%2C+2019%2E+%E2%80%94+%5BarXiv%3A1803%2E07300%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1803%2E07300%29)
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](https://scholar.google.com/scholar?q=Andy+L+Jones%2E+Scaling+scaling+laws+with+board+games%2E+arXiv+preprint+arXiv%3A2104%2E03113%2C+2021%2E+%E2%80%94+%5BarXiv%3A2104%2E03113%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2104%2E03113%29)
33. Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, 2011. [find](https://scholar.google.com/scholar?q=Daniel+Kahneman%2E+Thinking%2C+fast+and+slow%2E+Farrar%2C+Straus+and+Giroux%2C+2011%2E)
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](https://md.research.elamur.ai/free/en/papers/kaplan-2020-scaling-laws-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](https://scholar.google.com/scholar?q=Michael+Kearns%2E+Efficient+noise%2Dtolerant+learning+from+statistical+queries%2E+Journal+of+the+ACM%2C+45+%286%29%3A983%E2%80%931006%2C+November+1998%2E)
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](https://scholar.google.com/scholar?q=Juno+Kim+and+Taiji+Suzuki%2E+Transformers+provably+solve+parity+efficiently+with+chain+of+thought%2E+arXiv+preprint+arXiv%3A2410%2E08633%2C+2024%2E+%E2%80%94+%5BarXiv%3A2410%2E08633%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2410%2E08633%29)
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](https://md.research.elamur.ai/free/en/papers/kimi-team-2025-kimi-k1-5-scaling-reinforcement/). 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](https://md.research.elamur.ai/free/en/papers/kumar-2024-training-language-models-self-correct/). 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](https://scholar.google.com/scholar?q=C%2E+Landim%2E+Metastability+for+a+non%2Dreversible+dynamics%3A+The+evolution+of+the+condensate+in+totally+asymmetric+zero+range+processes%2E+Communications+in+Mathematical+Physics%2C+330%2C+2012%2E)
40. C. Landim. Metastable Markov chains. arXiv preprint arXiv:1807.04144, 2018. — [arXiv:1807.04144](https://arxiv.org/abs/1807.04144) [find](https://scholar.google.com/scholar?q=C%2E+Landim%2E+Metastable+Markov+chains%2E+arXiv+preprint+arXiv%3A1807%2E04144%2C+2018%2E+%E2%80%94+%5BarXiv%3A1807%2E04144%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1807%2E04144%29)
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](https://scholar.google.com/scholar?q=Claudio+Landim+and+Tiecheng+Xu%2E+Metastability+of+finite+state+Markov+chains%3A+A+recursive+procedure+to+identify+slow+variables+for+model+reduction%2E+Latin+American+Journal+of+Probability+and+Mathematica)
42. David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2nd edition, 2009. [find](https://scholar.google.com/scholar?q=David+Asher+Levin%2C+Yuval+Peres%2C+and+Elizabeth+Lee+Wilmer%2E+Markov+Chains+and+Mixing+Times%2E+American+Mathematical+Society%2C+2nd+edition%2C+2009%2E)
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](https://scholar.google.com/scholar?q=Hongkang+Li%2C+Meng+Wang%2C+Songtao+Lu%2C+Xiaodong+Cui%2C+and+Pin%2DYu+Chen%2E+How+do+nonlinear+transformers+acquire+generalization%2Dguaranteed+CoT+ability%3F+In+High%2Ddimensional+Learning+Dynamics+2024%3A+The+Emergenc)
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](https://scholar.google.com/scholar?q=Yingcong+Li%2C+Kartik+Sreenivasan%2C+Angeliki+Giannou%2C+Dimitris+Papailiopoulos%2C+and+Samet+Oymak%2E+Dissecting+chain%2Dof%2Dthought%3A+compositionality+through+in%2Dcontext+filtering+and+learning%2E+In+Advances+in+Neu)
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](https://scholar.google.com/scholar?q=Zhiyuan+Li%2C+Hong+Liu%2C+Denny+Zhou%2C+and+Tengyu+Ma%2E+Chain+of+thought+empowers+transformers+to+solve+inherently+serial+problems%2E+arXiv+preprint+arXiv%3A2402%2E12875%2C+2024b%2E)
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](https://md.research.elamur.ai/free/en/papers/lightman-2023-let-s-verify-step-step/).
47. Neal Madras and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, 12, 2001. [find](https://scholar.google.com/scholar?q=Neal+Madras+and+Dana+Randall%2E+Markov+chain+decomposition+for+convergence+rate+analysis%2E+Annals+of+Applied+Probability%2C+12%2C+2001%2E)
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](https://scholar.google.com/scholar?q=Ashok+Vardhan+Makkuva%2C+Marco+Bondaschi%2C+Adway+Girish%2C+Alliot+Nagle%2C+Martin+Jaggi%2C+Hyeji+Kim%2C+and+Michael+Gastpar%2E+Attention+with+Markov%3A+A+framework+for+principled+analysis+of+transformers+via+Markov+)
49. William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023. [find](https://scholar.google.com/scholar?q=William+Merrill+and+Ashish+Sabharwal%2E+The+expresssive+power+of+transformers+with+chain+of+thought%2E+arXiv+preprint+arXiv%3A2310%2E07923%2C+2023%2E)
50. Carl D. Meyer. Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems. SIAM Review, 31(2):240–272, 1989. [find](https://scholar.google.com/scholar?q=Carl+D%2E+Meyer%2E+Stochastic+complementation%2C+uncoupling+Markov+chains%2C+and+the+theory+of+nearly+reducible+systems%2E+SIAM+Review%2C+31%282%29%3A240%E2%80%93272%2C+1989%2E)
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](https://scholar.google.com/scholar?q=Carl+Dean+Meyer%2E+The+dondition+of+a+finite+Markov+chain+and+perturbation+bounds+for+the+limiting+probabilities%2E+SIAM+J%2E+Algebraic+Discret%2E+Methods%2C+1%3A273%E2%80%93283%2C+1980%2E)
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](https://scholar.google.com/scholar?q=Eshaan+Nichani%2C+Alex+Damian%2C+and+Jason+D%2E+Lee%2E+How+transformers+learn+causal+structure+with+gradient+descent%2E+arXiv+preprint+arXiv%3A2402%2E14735%2C+2024%2E+%E2%80%94+%5BarXiv%3A2402%2E14735%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F2402%2E147)
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](https://md.research.elamur.ai/free/en/papers/al-2021-show-your-work-scratchpads-intermediate/). arXiv preprint arXiv:2112.00114, 2021.
54. OpenAI. Spinning up: proximal policy optimization (PPO), 2018. [https://spinningup.openai.com/en/latest/algorithms/ppo.html](https://spinningup.openai.com/en/latest/algorithms/ppo.html). 2025-01-26. [↗](https://spinningup.openai.com/en/latest/algorithms/ppo.html)
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](https://scholar.google.com/scholar?q=URL+Accessed%3A+Daniel+Paulin%2E+Concentration+inequalities+for+Markov+chains+by+Marton+couplings+and+spectral+methods%2E+Electronic+Journal+of+Probability%2C+20%3A1%E2%80%9332%2C+2015%2E)
56. Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. OpenAI Blog, 2018. [find](https://scholar.google.com/scholar?q=Alec+Radford%2C+Karthik+Narasimhan%2C+Tim+Salimans%2C+and+Ilya+Sutskever%2E+Improving+language+understanding+by+generative+pre%2Dtraining%2E+OpenAI+Blog%2C+2018%2E)
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](https://md.research.elamur.ai/free/en/papers/sanford-2024-understanding-transformer-reasoning-capabilities-graph/). 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](https://scholar.google.com/scholar?q=Clayton+Sanford%2C+Daniel+Hsu%2C+and+Matus+Telgarsky%2E+Transformers%2C+parallel+computation%2C+and+logarithmic+depth%2E+In+International+Conference+on+Machine+Learning%2C+2024b%2E)
59. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. [find](https://scholar.google.com/scholar?q=John+Schulman%2C+Filip+Wolski%2C+Prafulla+Dhariwal%2C+Alec+Radford%2C+and+Oleg+Klimov%2E+Proximal+policy+optimization+algorithms%2E+arXiv+preprint+arXiv%3A1707%2E06347%2C+2017%2E)
60. Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning, 2017. [find](https://scholar.google.com/scholar?q=Shai+Shalev%2DShwartz%2C+Ohad+Shamir%2C+and+Shaked+Shammah%2E+Failures+of+gradient%2Dbased+deep+learning%2E+In+International+Conference+on+Machine+Learning%2C+2017%2E)
61. Ohad Shamir. Distribution-specific hardness of learning neural networks. Journal of Machine Learning Research, 19:32:1–32:29, 2018. [find](https://scholar.google.com/scholar?q=Ohad+Shamir%2E+Distribution%2Dspecific+hardness+of+learning+neural+networks%2E+Journal+of+Machine+Learning+Research%2C+19%3A32%3A1%E2%80%9332%3A29%2C+2018%2E)
62. Kumar Shridhar, Alessandro Stolfo, and Mrinmaya Sachan. [Distilling reasoning capabilities into smaller language models](https://md.research.elamur.ai/free/en/papers/shridhar-2023-distilling-reasoning-capabilities-into-smaller/). 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](https://scholar.google.com/scholar?q=David+Silver%2C+Thomas+Hubert%2C+Julian+Schrittwieser%2C+Ioannis+Antonoglou%2C+Matthew+Lai%2C+Arthur+Guez%2C+Marc+Lanctot%2C+Laurent+Sifre%2C+Dharshan+Kumaran%2C+Thore+Graepel%2C+et+al%2E+A+general+reinforcement+learning+a)
64. Charlie Snell, Jaehoon Lee, Kelvin Xu, and Aviral Kumar. [Scaling LLM test-time compute optimally can be more effective than scaling model parameters](https://md.research.elamur.ai/free/en/papers/snell-2024-scaling-llm-test-time-compute/). 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](https://scholar.google.com/scholar?q=Ryan+Tifenbach%2E+On+an+SVD%2Dbased+algorithm+for+identifying+meta%2Dstable+states+of+Markov+chains%2E+Electronic+Transactions+on+Numerical+Analysis%2C+38%3A17%E2%80%9333%2C+2011%2E)
66. Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong. [Solving olympiad geometry without human demonstrations](https://md.research.elamur.ai/free/en/papers/trinh-2024-solving-olympiad-geometry-without-human/). 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](https://md.research.elamur.ai/free/en/papers/uesato-2022-solving-math-word-problems-process/).
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](https://md.research.elamur.ai/free/en/papers/wei-2022-chain-thought-prompting-elicits-reasoning/). 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](https://scholar.google.com/scholar?q=Kaiyue+Wen%2C+Huaqing+Zhang%2C+Hongzhou+Lin%2C+and+Jingzhao+Zhang%2E+From+sparse+dependence+to+sparse+attention%3A+unveiling+how+chain%2Dof%2Dthought+enhances+transformer+sample+efficiency%2E+arXiv+preprint+arXiv%3A241)
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](https://scholar.google.com/scholar?q=John+Wicks+and+Amy+Greenwald%2E+An+algorithm+for+computing+stochastically+stable+distributions+with+applications+to+mltiagent+learning+in+repeated+games%2E+In+Conference+on+Uncertainty+in+Artificial+Intel)
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](https://scholar.google.com/scholar?q=Geoffrey+Wolfer+and+Aryeh+Kontorovich%2E+Estimating+the+mixing+time+of+ergodic+Markov+chains%2E+arXiv+preprint+arXiv%3A1902%2E01224%2C+2022%2E+%E2%80%94+%5BarXiv%3A1902%2E01224%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1902%2E01224%29)
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](https://md.research.elamur.ai/free/en/papers/wu-2024-inference-scaling-laws-empirical-analysis/). 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](https://md.research.elamur.ai/free/en/papers/xiang-2025-towards-system-2-reasoning-llms/). 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](https://scholar.google.com/scholar?q=Yuxi+Xie%2C+Anirudh+Goyal%2C+Wenyue+Zheng%2C+Min%2DYen+Kan%2C+Timothy+P%2E+Lillicrap%2C+Kenji+Kawaguchi%2C+and+Michael+Shieh%2E+Monte+Carlo+tree+search+boosts+reasoning+via+iterative+preference+learning%2E+arXiv+preprint)
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](https://scholar.google.com/scholar?q=Keyulu+Xu%2C+Jingling+Li%2C+Mozhi+Zhang%2C+Simon+S+Du%2C+Ken%2Dichi+Kawarabayashi%2C+and+Stefanie+Jegelka%2E+What+can+neural+networks+reason+about%3F+arXiv+preprint+arXiv%3A1905%2E13211%2C+2019%2E)
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](https://scholar.google.com/scholar?q=Shunyu+Yao%2C+Dian+Yu%2C+Jeffrey+Zhao%2C+Izhak+Shafran%2C+Tom+Griffiths%2C+Yuan+Cao%2C+and+Karthik+Narasimhan%2E+Tree+of+thoughts%3A+deliberate+problem+solving+with+large+language+models%2E+Advances+in+Neural+Informati)
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](https://scholar.google.com/scholar?q=Oussama+Zekri%2C+Ambroise+Odonnat%2C+Abdelhakim+Benechehab%2C+Linus+Bleistein%2C+Nicolas+Boulle%CC%81%2C+and+Ievgen+Redko%2E+Large+language+models+as+Markov+chains%2E+arXiv+preprint+arXiv%3A2410%2E02724%2C+2024%2E+%E2%80%94+%5BarXiv%3A2410)
78. Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. [Star: bootstrapping reasoning with reasoning](https://md.research.elamur.ai/free/en/papers/zelikman-2022-star-bootstrapping-reasoning-reasoning/). Advances in Neural Information Processing Systems, 35:15476–15488, 2022.
79. Table of Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 3 [find](https://scholar.google.com/scholar?q=Table+of+Contents+1+Introduction+1%2E1+Our+Contributions+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+%2E+1+3)

*Updated 3 November 2026*