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

Denny Wu; Jason Lee; Juno Kim; Taiji Suzuki

REVIEW 3 major objections 4 minor 78 references

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

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Chain-of-thought reasoning is a metastable Markov process: expected hitting time is $\widetilde{\Theta}(KM/\varepsilon)$, and search, RL, and distillation provably improve it.

desk verdict A serious theoretical framework for CoT as metastable Markov chains, but the main quantitative benefit estimate rests on a strong uniform-exploration assumption that can fail on natural graph structures. read the letter →

arxiv 2502.01694 v2 pith:UVR655QA submitted 2025-02-02 cs.AI cs.LGstat.ML

Juno Kim , Denny Wu , Jason Lee , Taiji Suzuki This is my paper · ORCID

classification cs.AIcs.LGstat.ML MSC 60J2068Q3268T07

keywords chain-of-thoughtmetastableMarkovchainsinference-timecomputereinforcementlearningdistillationhittingtimesstatisticalquerycomplexitysparsereasoningsteps

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to prove why inference-time search, reinforcement learning, and distillation help reasoning models, rather than just documenting that they do. The authors model chain-of-thought generation as a perturbed Markov process on a graph of logical assertions: easy reasoning steps are dense edges inside clusters, while hard steps are sparse, low-probability edges between clusters. They show the expected number of steps to reach a target state is roughly $\widetilde{\Theta}(KM/\varepsilon)$, and that search which identifies and upweights sparse edges cuts this time. They also prove that RL fine-tuning can install the improved transition probabilities with negligible damage to the base model, and that a compressed cluster-level chain can be distilled into a much smaller model while preserving escape dynamics. The final hardness result says that, for a logical reasoning task over sparse edges, any learner with only the generated path or a local neighborhood of it needs exponentially many queries, so global search is necessary.

What carries the argument

The paper's working model is a perturbed Markov chain on a state space of logical assertions, with easy within-cluster transitions of probability $\Theta(1/M)$ and hard inter-cluster transitions of order $\varepsilon$. The carrying tool is the perturbative metastability analysis: stochastic complementation defines the reduced within-cluster chains, the pseudo-spectral gap controls their rapid mixing, and the meta-chain $X^\varepsilon_\star$ with kernel $q^\varepsilon_\star(C_\ell|C_k)$ compresses each cluster to a single state. Assumption 4, uniform escape at rate $\Omega(\varepsilon/M)$ for every ordered pair of clusters, is what makes the hitting-time computation tight; the same metastable representation is then reused in the distillation construction and in the statistical query lower bounds.

What would settle it

Construct a graph that satisfies the dense-cluster and sparse-edge assumptions but arranges the sparse edges as a directed line of $K$ clusters, so that $q^\varepsilon_\star(C_k|C_1)=0$ for most $k$ and Assumption 4 fails. Simulate the expected hitting time from cluster 1 to cluster $K$; if it grows like $\widetilde{\Theta}(K^2 M/\varepsilon)$ or another superlinear-in-$K$ rate instead of $\widetilde{\Theta}(KM/\varepsilon)$, the uniform-escape assumption and the paper's central hitting-time theorem are refuted.

Watch

Extended reading notes

Core claim

The central claim is that the long-timescale behavior of CoT is captured by a meta-chain over clusters, with transition kernel $q^\varepsilon_\star(C_\ell|C_k)$, and that under a uniform escape condition the expected hitting time from an input state to an output state is $\widetilde{\Theta}(KM/\varepsilon)$. Search that rewards sparse edges improves this to $\widetilde{\Theta}(KM/\varepsilon_{\max})$, and the paper proves that PPO-Clip fine-tuning reweights those edges so that the base model behaves like $p^{\varepsilon'}$ with $\varepsilon'=(1-o(1))\varepsilon_{\max}$ while changing the model by only $o(1/M)$ in total variation. It further proves that a distilled $K$-state chain, trained only on cluster-transition data, recovers the meta-chain escape probabilities up to a $1+o_M(1)$ factor and achieves $O(K)$ hitting time after time rescaling. The hardness half introduces a statistical query dimension with additional information $I_p$ and shows that with no access, path-only access, or local-neighborhood access, the logical reasoning concept class has SQ dimension $e^{\Omega(K)}$, so polynomial-time learning requires full graph access.

Load-bearing premise

The load-bearing premise is that hard reasoning steps are spread evenly enough that every cluster is reachable from every other cluster with probability at least a constant times $\varepsilon/M$; if some cluster pairs are effectively isolated before the chain returns, the $\widetilde{\Theta}(KM/\varepsilon)$ hitting time and the claimed speedups collapse.

Editorial extensions

If this is right

A search protocol that rewards sparse edges reduces the expected hitting time from $\widetilde{\Theta}(KM/\varepsilon)$ to $\widetilde{\Theta}(KM/\varepsilon_{\max})$, and the search cost is comparable to solving one instance without search.
RL fine-tuning with PPO-Clip can install the improved sparse-edge probabilities with $\varepsilon'=(1-o(1))\varepsilon_{\max}$ while keeping the total variation change to the base model below $o(1/M)$, so the pretrained model's other capabilities are largely preserved.
A distilled $K$-state meta-chain trained on cluster-transition frequencies recovers escape probabilities up to a $1+o_M(1)$ multiplicative factor and reaches any target cluster in $O(K)$ steps, independent of $\varepsilon$, explaining why distillation into smaller models can preserve reasoning dynamics.
For the logical reasoning task, learners with only the generated CoT path or a local neighborhood of it require $e^{\Omega(K)}$ statistical queries; global search is necessary for polynomial-time solvability.
The pretrained linear softmax model converges to the true transition kernel with exponentially small error after thresholding, so the qualitative conclusions transfer to an exactly learned base model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: If this model transfers to real LLMs, the $\varepsilon_{\max}/\varepsilon$ speedup predicts diminishing returns once search has already identified most hard edges, shifting the practical bottleneck from discovering hard steps to verifying them.
Editorial inference: The meta-chain distillation suggests a concrete recipe for compressing reasoning traces into cluster-level transition counts; one could test it by comparing a distilled model on novel multi-step tasks against an equally sized model trained on full token-level traces.
Editorial inference: The statistical query lower bound implies that logical attributes such as 'which step is the key idea' cannot be learned from local edits to a proof, so search-based data collection, not just longer CoT, may be required for such reasoning abilities.
Editorial inference: The same metastable hitting-time analysis could be extended to backtracking and revision protocols, where the chain is allowed to return to earlier clusters; the paper hints at this but does not prove bounds for it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know this paper before the next reading group: it's a real theoretical contribution, but the headline number—Θ(KM/ε) hitting time for CoT—is conditional on Assumption 4, and that assumption is not as innocent as the paper suggests. The stress-test note is correct. On an undirected cycle of clusters with sparse edges of probability ε, the meta-chain escape probability to a far cluster is about ε/(MK), not Ω(ε/M), so Assumption 4 fails and the hitting time is closer to K²M/ε. The paper's own cycle example is ambiguous; if it's a directed cycle, the assumption might hold, but for undirected cycles it doesn't. This is a load-bearing flaw for the claim that search complexity equals the single-instance cost. The conditional theorem itself is proven, but the quantitative 'provable benefit' is really 'benefit under a uniform exploration hypothesis'.

What's genuinely good: the quantitative perturbative analysis of metastable chains is new, the SDA measure for restricted access is a clean way to formalize the necessity of global search, and the hardness results (Theorem 5.3) are independent lower bounds that don't rely on the questionable assumption. The paper also does the honest work of stating assumptions explicitly and deferring proofs rather than hiding difficulties. Credit where it's due: the appendices contain real proofs (even if one is omitted), and the lower-bound constructions are standard and solid.

Soft spots, in proportion: (1) Assumption 4 is the big one—it's not implied by the cluster structure, and the paper's justification is insufficient. (2) Proposition 4.2's convergence proof is literally 'details are omitted'—that needs to be supplied before the distillation claim is fully backed. (3) The PPO analysis is for sign-gradient descent, not actual PPO-Clip; that's a modeling choice but should be flagged. (4) The model is abstract; there's no empirical check that real LLM reasoning dynamics look metastable. That limits significance if you care about practical claims, but not the internal math.

Who this is for: theorists working on CoT, Markov-chain models of reasoning, or inference-time compute. It gives a useful vocabulary and some solid lower bounds. The central theorem's quantitative form should be treated as conditional. A serious referee should run the paper through review, but they should demand a clearer treatment of Assumption 4 and a complete proof of Proposition 4.2. I'd bring it to a reading group for the discussion.

Referee Report

3 major / 4 minor

Summary. This paper introduces a metastable Markov chain model for chain-of-thought reasoning, where easy reasoning steps form dense clusters and hard steps are sparse edges of probability ε. The central result (Theorem 3.2) states that, under Assumptions 1-4, the expected hitting time from a random input state to the output state is ~Θ(KM/ε). The paper then uses this estimate to argue that search (boosting sparse edges toward ε_max), RL fine-tuning (PPO-Clip), and distillation to a coarse meta-chain (with O(K) hitting time) all provably improve reasoning. A final section defines a statistical-query-with-access dimension and proves lower bounds showing that logical reasoning is hard without global search.

Significance. The paper's systematic use of metastability theory to analyze CoT is novel, and the appendix contains a substantial body of quantitative estimates (escape times, perturbation bounds, mixing, stationary distribution) that go beyond purely heuristic modeling. The SDA framework in Section 5 is an interesting extension of the SQ dimension to restricted information. However, the central quantitative claim is conditional on Assumption 4 (uniform escape of the meta-chain), which is not derived from the metastable structure; moreover, the paper's own example illustrating the assumption (a cycle of clusters) is incorrect, since a diffusive random walk on a cycle does not escape uniformly to far clusters. The missing proof of Proposition 4.2 also undercuts the distillation contribution. These issues are fixable in revision but currently overstate the universality of the Θ(KM/ε) hitting-time bound.

major comments (3)

[Section 2.3, Assumption 4 (Eq. (3))] The cycle example used to justify Assumption 4 is incorrect. If the sparse edges form an undirected cycle on the cluster graph, the meta-chain is a random walk on a cycle with transition probability Θ(ε/M) to each neighbor. For a far cluster at distance d = Θ(K), the probability q*_ε(C_l|C_k) is Θ(ε/(M K)) up to logarithmic factors, not Ω(ε/M). Consequently, Assumption 4 fails by a factor K, and the expected hitting time between far clusters is ~Θ(K²M/ε), a factor K larger than the claim of Theorem 3.2. The statement that 'escaping C_k implies all other clusters C_l will be hit before the process returns to C_k' is false for a diffusive random walk: the process may turn back and return to C_k without reaching a far cluster. The paper should correct this example and either add explicit structural conditions (e.g., the meta-chain is complete or an expander) under which Assumption 4 is guaranteed, or explicitly state that the Θ(KM/ε) bound and the associated search-complexity equality in Section 3.3 apply only when Assumption 4 holds.
[Section 4.2 / Proposition 4.2] The proof of Proposition 4.2 is not provided; Appendix D.3 states 'The details are omitted.' This proposition is load-bearing for the distillation contribution, and the claimed convergence rate and complexity T_dist = ~O(M²ε⁻²) are not obviously implied by the referenced 'repetition' of Theorem D.1. In particular, substituting the suggested replacements (state space size K, outgoing edges d_out, probability threshold Θ(ε/M)) into the bounds of Theorem D.1 yields a different ε-dependence for the initial phase than the claimed O(log(KT)/T). Please provide a complete proof or a detailed derivation of the stated complexity.
[Section 3.3 / Proposition 3.4] The convergence guarantee is proved for sign-gradient descent on a clipped objective, not for the standard PPO-Clip update (Algorithm 3 uses sign gradients and a simplified advantage). While the paper acknowledges this, the proposition is stated as a convergence result for 'PPO-Clip', which is misleading. Please either reformulate Proposition 3.4 as a statement about sign-gradient descent with the simplified objective, or provide the analysis for the standard PPO-Clip surrogate.

minor comments (4)

[Section 3.2] There is a typo: 'This continues until until all paths are terminated' should read 'until all paths are terminated'.
[Throughout] The notations ~Θ, ~O, and ~Ω are used extensively without definition; please define them (e.g., Θ up to polylogarithmic factors) at first use.
[Section 3.2] The sentence 'modifying the underlying probabilities to increase the denominator ε' is confusing because ε is not a denominator; it should say 'increasing ε'.
[Section 4.2 / Algorithm 4] In Algorithm 4, the thresholding step at line 22 uses c_thres ε/M, but the corresponding text in Proposition 4.2 and Appendix D.3 should clarify whether this threshold is applied to the distilled chain q^ε_◦ or to the trained model; the notation q̂^(T_thres) should be defined.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction: the central results are conditional theorems under explicitly stated assumptions; at most one non-load-bearing self-citation appears in related work.

full rationale

The paper's derivation chain is a self-contained conditional mathematical analysis, not a fit disguised as a prediction. Theorem 3.2's Θ(KM/ε) hitting-time bound is proved from Assumptions 1–4: the upper bound uses Corollary C.9 together with Assumption 4 (Eq. (3)) and the lower bound uses Assumption 3 with Lemma C.12; the rate is not obtained by fitting a parameter to the hitting time, nor by redefining the meta-chain q^ε_* as the reciprocal of a target time. The claimed benefits of search and RL compare p^ε with p^{ε_max} under the same stated assumptions, and the improvement factor ε_max/ε follows from the explicit rescaling, not from an assumption that search works. Assumption 4 is openly stated as an assumption, and the paper even acknowledges in footnote 1 that poorly connected meta-chains would require a hierarchy of metastable representations; the reader's concern about Assumption 4 failing on a cycle-like arrangement is a legitimate correctness or robustness criticism, but it is not a circularity because the paper never claims Assumption 4 is implied by Assumptions 1–3. Similarly, the distillation hitting-time result O(K) in Theorem 4.3 is a designed consequence of the explicit time rescaling β = Θ(log(M/ε)) in Algorithm 4 and Theorem D.8, not a hidden restatement of the input. The hardness result in Theorem 5.3 is an independent SQ-dimension lower bound built from explicit graph constructions with isomorphic local neighborhoods. The only self-citation (Kim and Suzuki 2024, Appendix A) appears in a related-work list and is not load-bearing for any theorem. No circular step can be exhibited from the paper's own equations, so the appropriate finding is a low, non-circular score of 2.

Assumptions & free parameters 5 free parameters · 7 assumptions · 0 invented entities

The central claim is conditional on a set of abstract modeling assumptions (Assumptions 1-5) plus the Markov chain model. The paper does not validate these assumptions on real LLM data. The results are therefore conditional on the model being an accurate representation of CoT reasoning.

free parameters (5)

epsilon (sparse edge probability) = unknown small value
The scale of hard reasoning steps. All main results and algorithm parameters (Tmax, thresholds, beta) depend on it. The paper assumes epsilon is known to set these parameters.
epsilon_max = Theta(M^{-1}(log M)^{-4})
The upper regime for the perturbation analysis; also the target boost level for RL. Chosen by the analysis, not by data.
c_thres = constant (unspecified)
Threshold for pruning edges in pretraining (Algorithm 1) and distillation (Algorithm 4). Its value is not specified and is assumed known.
beta = Theta(log(M/epsilon))
Time rescaling parameter in distillation (Algorithm 4), chosen to make sparse transitions Theta(1).
R, N, T0, Tmax (Algorithm 2 parameters) = Theta(K log K), Theta(log K), Theta(M(log M)^2), Theta(M/epsilon)
Search algorithm parameters set as functions of M, K, epsilon to guarantee success; require knowing epsilon.

assumptions (7)

domain assumption Assumption 1: dense clusters (pseudo-spectral gap gamma > 0, stationary measure ~1/M on each cluster)
States that easy reasoning steps mix rapidly within clusters. Cited at Section 2.1.
domain assumption Assumption 2: sparse edge structure (at most d_out sparse edges per source, at most one between clusters, p ~ epsilon on sparse edges)
Defines hard reasoning steps as rare edges. Section 2.1.
domain assumption Assumption 3: task difficulty (average min |path intersects E_s| = Omega(K))
Ensures that reaching the target requires many hard steps. Section 2.2.
ad hoc to paper Assumption 4: uniform escape of the meta-chain (q* = Omega(epsilon/M))
Introduced to guarantee the Theta(KM/epsilon) hitting time; not a standard assumption and only illustrated with examples. Section 2.3, equation (3).
ad hoc to paper Assumption 5: inbound sparse edges terminate at fixed points
Technical condition for the distillation data collection to avoid skipped representatives. Section 4.2.
domain assumption Domain assumption: CoT is a stationary Markov chain on a finite graph of logical assertions
The overarching model; not validated on real LLM traces. Section 2.1.
domain assumption Domain assumption: logical action well-separated (E_g[phi(g*r)] = 0)
Standard balancedness condition for random classifiers in the hardness proof. Section 5.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation." pith.science (2026). https://pith.science/paper/UVR655QA

@misc{pith2026250201694,
  author       = {Pith},
  title        = {Pith review of: Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UVR655QA}},
  note         = {Machine review of arXiv:2502.01694}
}

read the original abstract

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.

Figures

Figures reproduced from arXiv: 2502.01694 by the authors.

**Figure 1.** (Left) Example of metastable graph with three clusters. Each state represents a logical assertion and edges correspond to reasoning steps. Solid and dashed arrows indicate easy (withincluster) and hard (inter-cluster) reasoning steps, respectively. The goal of the reasoner is to retrieve a valid CoT path from Xin to Xout (highlighted). Search aims to use CoT generated from the pretrained model to explore the lingui… view at source ↗

**Figure 2.** Sparse edge construction for the no-search scenar [PITH_FULL_IMAGE:figures/full_fig_p053_2.png] view at source ↗

**Figure 3.** Graph construction for the local search scenario ( [PITH_FULL_IMAGE:figures/full_fig_p054_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

78 extracted references · 39 canonical work pages

[1]

How far can transformers reason? T he locality barrier and inductive scratchpad

Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can transformers reason? T he locality barrier and inductive scratchpad. In Advances in Neural Information Processing Systems, 2024

work page 2024
[2]

Constitutional AI : harmlessness from AI feedback

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

arXiv 2022
[3]

Beltr\' a n and C

J. Beltr\' a n and C. Landim. Metastability of reversible finite state M arkov processes. Stochastic Processes and their Applications, 121 0 (8): 0 1633--1677, 2011

work page 2011
[4]

Graph of thoughts: solving elaborate problems with large language models

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 Intelligence, 2024

work page 2024
[5]

Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed M arkov chains

Volker Betz and St\' e phane Le Roux . Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed M arkov chains. Stochastic Processes and their Applications, 126 0 (11): 0 3499--3526, 2016

work page 2016
[6]

Understanding in-context learning in transformers and LLM s by learning to learn discrete functions

Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade. Understanding in-context learning in transformers and LLM s by learning to learn discrete functions. In International Conference on Learning Representations, 2024

2024
[7]

Metastable states, quasi-stationary distributions and soft measures

Alessandra Bianchi and Alexandre Gaudilli\` e re. Metastable states, quasi-stationary distributions and soft measures. Stochastic Processes and their Applications, 126, 2016

work page 2016
[8]

Metastability and low lying spectra in reversible M arkov chains

Anton Bovier, Michael Eckhoff, V\' e ronique Gayrard, and Markus Klein. Metastability and low lying spectra in reversible M arkov chains. Communications in Mathematical Physics, 228: 0 219--255, 2002

work page 2002

Show all 78 references

[9]

On using extended statistical queries to avoid membership queries

Nader Bshouty and Vitaly Feldman. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research, 2: 0 529--545, 09 2001

2001
[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

2018
[11]

Exploration by random network distillation

Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019

2019
[12]

Tighter bounds on the expressivity of transformer encoders

David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, 2023

2023
[13]

Metastability for general dynamics with rare transitions: escape time and critical configurations

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

2014
[14]

The L lama 3 herd of models

Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The L lama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024

2024 arXiv
[15]

Edelman, eran malach, and Surbhi Goel

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

2024
[16]

Konstantin Fackeldey, Alexander Sikorski, and M. Weber. Spectral clustering for non-reversible M arkov chains. Computational and Applied Mathematics, 37, 2018

2018
[17]

A general characterization of the statistical query complexity

Vitaly Feldman. A general characterization of the statistical query complexity. Proceedings of Machine Learning Research, 65: 0 785--830, 2017

2017
[18]

Towards revealing the mystery behind chain of thought: a theoretical perspective

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, 2023 a

2023
[19]

Alphazero-like tree-search can guide large language model decoding and training

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, 2023 b

2023 arXiv
[20]

Fernandez, F

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 0 (2): 0 760--793, 2016

2016
[21]

Asymptotically exponential hitting times and metastability: A pathwise approach without reversibility

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

2014
[22]

An SVD approach to identifying metastable states of Markov chains

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: 0 46--69, 2008

2008
[23]

Stream of search ( SoS ): learning to search in language

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

2024 arXiv
[24]

DeepSeek-R1: incentivizing reasoning capability in LLMs via reinforcement learning

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

2025 arXiv
[25]

Training compute-optimal large language models

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

2022 arXiv
[26]

Distilling step-by-step! O utperforming larger language models with less training data and smaller model sizes

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! O utperforming larger language models with less training data and smaller model sizes. arXiv preprint arXiv:...

2023 arXiv
[27]

Unveiling the statistical foundations of chain-of-thought prompting methods

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

2024 arXiv
[28]

From self-attention to M arkov models: unveiling the dynamics of generative transformers

Muhammed Emrullah Ildiz, Yixiao Huang, Yingcong Li, Ankit Singh Rawat, and Samet Oymak. From self-attention to M arkov models: unveiling the dynamics of generative transformers. In International Conference on Machine Learning, 2024

2024
[29]

A robust spectral method for finding lumpings and meta-stable states of non-reversible M arkov chains

Martin Nilsson Jacobi. A robust spectral method for finding lumpings and meta-stable states of non-reversible M arkov chains. Electronic Transactions on Numerical Analysis, 37: 0 296--306, 2010

2010
[30]

OpenAI o1 system card

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

2024 arXiv
[31]

Risk and parameter convergence of logistic regression

Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:1803.07300, 2019

2019 arXiv
[32]

Scaling scaling laws with board games

Andy L Jones. Scaling scaling laws with board games. arXiv preprint arXiv:2104.03113, 2021

2021 arXiv
[33]

Thinking, fast and slow

Daniel Kahneman. Thinking, fast and slow. Farrar, Straus and Giroux, 2011

2011
[34]

Scaling laws for neural language models

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

2001 arXiv
[35]

Efficient noise-tolerant learning from statistical queries

Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45 0 (6): 0 983--1006, November 1998

1998
[36]

Transformers provably solve parity efficiently with chain of thought

Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought. arXiv preprint arXiv:2410.08633, 2024

2024 arXiv
[37]

Kimi k1.5: scaling reinforcement learning with LLM s

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 LLM s. arXiv preprint arXiv:2501.12599, 2025

2025 arXiv
[38]

Training language models to self-correct via reinforcement learning

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

2024 arXiv
[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

2012
[40]

C. Landim. Metastable M arkov chains. arXiv preprint arXiv:1807.04144, 2018

2018 arXiv
[41]

Metastability of finite state M arkov chains: A recursive procedure to identify slow variables for model reduction

Claudio Landim and Tiecheng Xu. Metastability of finite state M arkov chains: A recursive procedure to identify slow variables for model reduction. Latin American Journal of Probability and Mathematical Statistics, 13, 2015

2015
[42]

Markov Chains and Mixing Times

David Asher Levin, Yuval Peres, and Elizabeth Lee Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2nd edition, 2009

2009
[43]

How do nonlinear transformers acquire generalization-guaranteed CoT ability? In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning, 2024 a

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, 2024 a

2024
[44]

Dissecting chain-of-thought: compositionality through in-context filtering and learning

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

2023
[45]

Chain of thought empowers transformers to solve inherently serial problems

Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402.12875, 2024 b

2024 arXiv
[46]

Let's verify step by step

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

2023 arXiv
[47]

Markov chain decomposition for convergence rate analysis

Neal Madras and Dana Randall. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, 12, 2001

2001
[48]

Attention with M arkov: A framework for principled analysis of transformers via M arkov chains

Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Martin Jaggi, Hyeji Kim, and Michael Gastpar. Attention with M arkov: A framework for principled analysis of transformers via M arkov chains. arXiv preprint arXiv:2402.04161, 2024

2024 arXiv
[49]

The expresssive power of transformers with chain of thought

William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023

2023 arXiv
[50]

Carl D. Meyer. Stochastic complementation, uncoupling M arkov chains, and the theory of nearly reducible systems. SIAM Review, 31 0 (2): 0 240--272, 1989

1989
[51]

The dondition of a finite M arkov chain and perturbation bounds for the limiting probabilities

Carl Dean Meyer. The dondition of a finite M arkov chain and perturbation bounds for the limiting probabilities. SIAM J. Algebraic Discret. Methods, 1: 0 273--283, 1980

1980
[52]

Eshaan Nichani, Alex Damian, and Jason D. Lee. How transformers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735, 2024

2024 arXiv
[53]

Show your work: scratchpads for intermediate computation with language models

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

2021 arXiv
[54]

Spinning up: proximal policy optimization ( PPO ), 2018

OpenAI. Spinning up: proximal policy optimization ( PPO ), 2018. URL https://spinningup.openai.com/en/latest/algorithms/ppo.html. Accessed: 2025-01-26

2018
[55]

Concentration inequalities for Markov chains by Marton couplings and spectral methods

Daniel Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods . Electronic Journal of Probability, 20: 0 1--32, 2015

2015
[56]

Improving language understanding by generative pre-training

Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. OpenAI Blog, 2018

2018
[57]

Understanding transformer reasoning capabilities via graph algorithms

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, 2024 a

2024 arXiv
[58]

Transformers, parallel computation, and logarithmic depth

Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. In International Conference on Machine Learning, 2024 b

2024
[59]

Proximal policy optimization algorithms

John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017

2017 arXiv
[60]

Failures of gradient-based deep learning

Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. In International Conference on Machine Learning, 2017

2017
[61]

Distribution-specific hardness of learning neural networks

Ohad Shamir. Distribution-specific hardness of learning neural networks. Journal of Machine Learning Research, 19: 0 32:1--32:29, 2018

2018
[62]

Distilling reasoning capabilities into smaller language models

Kumar Shridhar, Alessandro Stolfo, and Mrinmaya Sachan. Distilling reasoning capabilities into smaller language models. arXiv preprint arXiv:2212.00193, 2022

2022 arXiv
[63]

A general reinforcement learning algorithm that masters chess, shogi, and G o through self-play

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 G o through self-play. Science, 362 0...

2018
[64]

Scaling LLM test-time compute optimally can be more effective than scaling model parameters

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

2024 arXiv
[65]

On an SVD-based algorithm for identifying meta-stable states of Markov chains

Ryan Tifenbach. On an SVD-based algorithm for identifying meta-stable states of Markov chains . Electronic Transactions on Numerical Analysis, 38: 0 17--33, 2011

2011
[66]

Solving olympiad geometry without human demonstrations

Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong. Solving olympiad geometry without human demonstrations. Nature, 625 0 (7995): 0 476--482, 2024

2024
[67]

Solving math word problems with process-and outcome-based feedback

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

2022 arXiv
[68]

Chain-of-thought prompting elicits reasoning in large language models

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: 0 24824--24837, 2022

2022
[69]

From sparse dependence to sparse attention: unveiling how chain-of-thought enhances transformer sample efficiency

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

2024 arXiv
[70]

An algorithm for computing stochastically stable distributions with applications to mltiagent learning in repeated games

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

2005
[71]

Estimating the mixing time of ergodic M arkov chains

Geoffrey Wolfer and Aryeh Kontorovich. Estimating the mixing time of ergodic M arkov chains. arXiv preprint arXiv:1902.01224, 2022

1902 arXiv
[72]

Inference scaling laws: An empirical analysis of compute-optimal inference for problem-solving with language models

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

2024 arXiv
[73]

Towards System 2 reasoning in LLMs: learning how to think with meta chain-of-thought

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

2025 arXiv
[74]

Lillicrap, Kenji Kawaguchi, and Michael Shieh

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

2024 arXiv
[75]

What can neural networks reason about? arXiv preprint arXiv:1905.13211, 2019

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

1905 arXiv
[76]

Tree of thoughts: deliberate problem solving with large language models

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

2024
[77]

Large language models as M arkov chains

Oussama Zekri, Ambroise Odonnat, Abdelhakim Benechehab, Linus Bleistein, Nicolas Boullé, and Ievgen Redko. Large language models as M arkov chains. arXiv preprint arXiv:2410.02724, 2024

2024 arXiv
[78]

Star: bootstrapping reasoning with reasoning

Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35: 0 15476--15488, 2022

2022

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

How far can transformers reason? T he locality barrier and inductive scratchpad

Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can transformers reason? T he locality barrier and inductive scratchpad. In Advances in Neural Information Processing Systems, 2024

work page 2024

[2] [2]

Constitutional AI : harmlessness from AI feedback

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

arXiv 2022

[3] [3]

Beltr\' a n and C

J. Beltr\' a n and C. Landim. Metastability of reversible finite state M arkov processes. Stochastic Processes and their Applications, 121 0 (8): 0 1633--1677, 2011

work page 2011

[4] [4]

Graph of thoughts: solving elaborate problems with large language models

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 Intelligence, 2024

work page 2024

[5] [5]

Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed M arkov chains

Volker Betz and St\' e phane Le Roux . Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed M arkov chains. Stochastic Processes and their Applications, 126 0 (11): 0 3499--3526, 2016

work page 2016

[6] [6]

Understanding in-context learning in transformers and LLM s by learning to learn discrete functions

Satwik Bhattamishra, Arkil Patel, Phil Blunsom, and Varun Kanade. Understanding in-context learning in transformers and LLM s by learning to learn discrete functions. In International Conference on Learning Representations, 2024

2024

[7] [7]

Metastable states, quasi-stationary distributions and soft measures

Alessandra Bianchi and Alexandre Gaudilli\` e re. Metastable states, quasi-stationary distributions and soft measures. Stochastic Processes and their Applications, 126, 2016

work page 2016

[8] [8]

Metastability and low lying spectra in reversible M arkov chains

Anton Bovier, Michael Eckhoff, V\' e ronique Gayrard, and Markus Klein. Metastability and low lying spectra in reversible M arkov chains. Communications in Mathematical Physics, 228: 0 219--255, 2002

work page 2002