Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation
Authors: Juno Kim
Denny Wu
Jason D. Lee
Taiji Suzuki
Venue: ICML 2025 poster (2025)
Keywords: large language model
reasoning
search
distillation
metastability
Primary area: theory->learning_theory

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 computation 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 \emph{metastable representation} of the reasoning dynamics can be distilled into a smaller, more efficient model.

Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation
Juno Kim
Denny Wu²
Jason D. Lee
Taiji Suzuki
1
Abstract
ford et al., 2018), is well known for its high computational demands, and its scaling behavior has been extensively stud- ied (Kaplan et al., 2020; Hoffmann et al., 2022; Dubey et al., 2024). On the other hand, inference (running the trained model to generate responses) was traditionally considered computationally inexpensive, until recent paradigm shift demonstrating that model reasoning capabiliites can drasti- cally improve by allocating more computational resources during inference time (Jaech et al., 2024; Guo et al., 2025; Kimi et al., 2025). Hence is crucial to understand the ad- vantages scaling inference computation can provide beyond those achieved through pretraining (Jones, 2021; Snell et al., 2024; Wu al., 2024).
A key paradigm improve the reasoning capa- bilities 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-tine compute by viewing chain-of-thought (CoT) gen- eration as metastable Markov process: easy rea- soning steps (e.g., algebraic manipulations) form densely connected clusters, while hard reasoning steps (e.g.. applying a relevant theorem) create sparse, low-probayility edges between clusters, leading to phase transitions at longer timescales. Under this framework, we prove that implement- ing search protocol that rewards sparse edges improves CoT by decreasing the expected num- ber of steps to reach different clusters. In contrast, we establish a limit on reasoning capability when the model restricted to local information of the pretrained graph. We also show that the informa- tion gained by search can be utilized to obtain a better reasoning model: (1) the pretrained model can be directly finetuned favor sparse edges via policy gradient methods, and moreover (2) a compressed metastable representation of the rea- soning dynamics can be distilled into a smaller, more efficient model.
Reasoning LLMs follow the chain-of-thouglh (CoT) (Nye et al., 2021; Wei et al., 2022) format where intermediate reasoning steps are iteratively generated before arriving at a final answer. Various reinforcement learning (RL) based approaches (Bai et al., 2022) have been proposed to improve CoT quality inference time, such as process reward model- ing (Lightman al., 2023; Uesato et al., 2022), Monte-Carlo Tree Search (MCTS) (Silver al., 2018; Feng al., 2023b; Trinh et al., 2024; Xie et al., 2024), and data self-generation (Zelikman et al., 2022; Kumar et al., 2024). Theoretically, the benefit of (sufficiently long) CoT has been studied in terms of expressive power and statistical efficiency (Merrill & Sabharwal, 2023; Li et al., 2024b; Kim & Suzuki, 2024; Wen al., 2024).
Motivated by the discrete and sequential nature of CoT, we follow Xu et al. (2019); Sanford et al. (2024a); Abbe et al. (2024); Besta et al. (2024) and consider learning on graphs as an ideal abstraction of complex reasoning tasks. We model pretraining as the process of discovering the graph structure, or the linguistic (world) model, upon which a reasoning (inference) component implemented to search for valid path between states (at high level, this division parallels the System 1 vs. System 2 distinction discussed in Kahneman (2011), Xiang et al. (2025)). Building on the ob- servation that intermediate reasoning steps vary in difficulty, we assume the underlying graph consists of dense clusters connected by sparse, low-probability edges representing "hard" reasoning steps. We further model CoT generation Markov process and characterize hitting/sscape times
1. Introduction
Pretraining and inference constitute two distinct computa- tional phases in large language models (LLMs). The pre- training phase, during which the model learns from vast amounts of text data through next-token prediction (Rad-
University of Tokyo and RIKEN AIP NNew York University and Flatiron Institute 'Princeton University. Correspondence to: Juno Kim <junokim berkeley.cdu>>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Metastable Dynamies of Chain-of- -Thoughht Reasoning
X
distillation
X out
Figure 1. (Left) Example of metastable graph with three clusters. Each state represents logical assertion and edges correspond reasoning steps. Solid and dashed arrows indicate easy (within-clusie and hard (inter-cluster) reasoning steps, respectively. The goal of the reasoner is to retrieve valid CoT path from Xi. Xour (highlighted). Search aims CoT generated from the pretrained model to explore the linguistic model and identify hard steps, which can then be used to fine-tune the pretrained model via RL to improve its generation. (Right) The coarse-grained dynamics of CoT long timescales can be represented by a meta-chain on the of clusters and distilled into smaller model, which can generate reasoning paths more efficiently.
by leveraging metastability theory (Bovier et al., 2002; Betz & Le Roux, 2016), which describes systems with multi- ple locally stable states separated by high energy barriers, leading to a timescale separation between local and global transitions (c.g., a reasoner may become stuck at critical reasoning step for an extended period). Our toy model cap- tures key phenomena observed in the training of reasoning LLMs:
based intrinsic reward improves hitting times by iden- tifying key reasoning steps, whose generation can be en- hanced directly or by fine-tuning the base model with RL. Moreover, optimization guarantees for pretraining and RL (PPO-Clip) are provided for a simple softmax model.
In Section 4, we show that compressed version of the CoT dynamics can be distilled to smaller model by only learning the macroscopic cluster transitions. We prove that this representation efficiently maps out paths through clusters while preserving essential dynamical quantities of the original chain.
Benefit of search and RI. Inference-time search elicits reasoning capabilities beyond pretraining (Jones, 2021; Yao al., 2024; Snell al., 2024). Roughly speaking, running search on the pretrained graph identifies impor- tant reasoning steps, and then RL improve the base linguistic model by modifying the graph and reweighting the corresponding transition probabilities.
Finally, in Section 5 we prove that large test time compute (unbounded search) is necessary to solve a computational version of the path-finding task, by introducing a new statistical query (SQ) complexity measure that accounts for additional information the learner can access (e.g.. CoT path, local search data).
Benefit of distillation. Reasoning patterns can be distilled into a smaller model (Hsieh et al., 2023; Gandhi et al., 2024; Guo et al., 2025). By training on curated CoT data of the larger model, we can efficiently represent the reasoning dynamies with much smaller meta-chain that compresses the dense clusters (representing "easy" steps).
All proofs are deferred to the appendix. A discussion of addi- tional related works is provided in Appendix A. Metastable dynamics and hitting times are studied in Appendices B-C, optimization dynamics are analyzed in Appendix D, and learning-theoreti lower bounds are given in Appendix E.
1.1. Our Contributions
We study the metastable Markov process underlying CoT generation (see Figure 2) which provides insights into the roles of pretraining, search, RL, and distillation. Our contri- butions are summarized as follows.
2. Metastable Dynamics and Reasoning
2.1. CoT as Markov Chains
Our key insight to understanding inference-time search to frame CoT reasoning as metastable Markov process over an underlying linguistic model. Each state represents logical assertion (e.g., sentence mathematical ex- pression rather than a single token), and state transitions correspond to reasoning steps. The model distinguishes be- tween easy/trivial reasoning steps, which form dense local clusters of roughly equivalent meaning, and hard/crucial reasoning steps, which form sparse connections between
In Section we introduce perturbed Markov chain model for CoT reasoning that differentiates between easy and hard reasoning steps through dense-sparse structure. We develop a quantitative analysis of its metastable dy- namics over long timescales by deriving tight bounds on the expected hitting times target states.
Section we demonstrate that inference-time search
2

---

Metastable Dynamies of Chain-of-Thoughhe Reasoning
clusters of small probability Oe)). Reasoning paths sam- pled from this process typically spend long time in each cluster before making nontrivial jump to another cluster. This leads to dynamical separation between fast and slow timescales, which we quantitatively study by tuning the degree e of perturbation.
is the QED symbol; when asked a "why" question, Xout could be the conclusion, "That is why..." Nonetheless, for many reasoning problems the answer is unknown and must be deduced or computed. We incorporate this aspect by introducing a 'logical computation' task in Section 5.
2.3. Metastable Dynamics
The setup is formalized as follows. Let X (x)) 1220 be a perturbed family of discrete-time stationary Markov chains (large but finite) state space 5 with transition kernel p², such that yf uniformly converges to pº as -> O. We assume X is recurrent for all 2 0 and irreducible for all ε > O; also, x is reducible and decomposes 5 into K disjoint pd -ergodic components C1. c....... .CK. We set M := max; |Cx:] and assume that ming |C&| = ( and K < (M)) Moreover, we denote the stochastic complement of of corresponding to C& by the matrix S see Appendix B for definitions. The stationary distributions of pf, SA are denoted by x², , and we set [4 == xL.
The hitting time and return time of X to a set A C S are defined as T = inf 2 0: x E A}, v = inf(! > 0 : X E A}, respectively. Probabilities and expectations conditioned on the initial state x are denoted as Fz, Ez, etc.
In the context of perturbed Markov chains, a subset M C S is defined metastable system (Bovier et al., 2002) if
Pa(TMni < +2) PA < 75)
lim 8 8-0 MEM.
sup
(I)
That is, it is much easier to return to M than to transition between different states in M. The following result, ob- tained from our perturbative analysis in Appendices B-C, will motivate the distillation scheme described in Section 4.
Assumption (dense clusters). For each & the pseudo- spectral gap y ( 2 7 > 0 and the stationary measure T satisfies oH = ((1/M) for all x E Ck-
We give verifiable conditions on the unperturbed kernel pd which guarantee Assumption in Proposition B.8.
Proposition 2.1. Any subset S. f=1,-.. , S of cluster representatives 2e C2 constitutes metastable system X in the sense of (1) as M + cc.
We further denote Eg supp pd and assume that E supppf is fixed for all 0. reasoning path Xo.r is termed valid if (Xi-1, X₁) E for all e [T]. The set of sparse edges is denoted by F,, = E Eg.
Meta-chain. The coarse-grained dynamics of X over long timescales is captured by its effective metastable representation X (Wicks & Greenwald, 2005; Betz & Le Roux, 2016), which acts as a compression of the full chain by only retaining information on inter-cluster dynam- ies. This 'meta-chain' is defined on the set of clusters S. (C1, ,Ck) with transition kernel
Assumption 2 (sparse edges). There are at most dou sparse edges from each of at most noutt sources in Cc, and there is at most one sparse edge between any two distinct clusters, with at least one sparse edge from each cluster. Moreover, pf (ylzz) & E for each (2, y) Eg with proportionality constant bounded above and below w.r.t. M, K, and of (z|æ² for (I. z) E Eg all decrease proportionally with e.
(CA(C(()) = Σ (x(x) < F k k (2)
zEC²
2.2. Reasoning Task
and (Cx(Ck) such that the conditional probabilities sum to 1. We emphasize that X faithfully characterizes clus- ter escape probabilities (see Proposition 4.1) but is not a one-to-one copy of the cluster transitions of X which gen- erally cannot be uniquely defined as a Markov chain. For example. qf is asymptotically reversible and always posi- tive regardless of the actual arrangement of sparse edges (Proposition C.8). To provide further intuition, we state and discuss the following assumption.
The reasoner is given a pair of input and output states (Xin, Xout) sampled from a distribution D on S x S. The goal of the reasoner is to find a valid path from Xin to Xout- We are thus interested in the hitting time of CoT generation to understand inference-time computation. The overall dif- ficulty of the task is measured by the minimum number of hard reasoning steps needed to reach Xout from Xini longer reasoning chains will require more sparse transitions. We assume the average difficulty of the task is lower bounded: Assumption 3. For (Xm: Xout) D and any valid path Xo.r with Xo Xin and Xy = Xouts it holds that
Assumption 4 (uniform escape of X;). For all k & e,
((e/M)
(3)
Folmin|Xo:r11
X O E.[] = ((K).
Equation (3) holds if there exists a sparse edge from C' to C₁ (Corollary C.11), but it may well hold even if C2. C2 are not directly connected. For example, if the sparse edges are arranged as a cycle on S., escaping Ct implies that all other
Note that Xout is already known in our setting. For example, for theorem proving, Xi, is the problem statement and Xout
3

---

Metastable Dynamies of Shain-of-Thoughe Reasoning
Algorithm I Two-stage Pretraining
before thresholding. Moreover, after thresholding time Ti =OKMM---)) the error converges as e
1: set ( =0, 17 O)),),
2: T (KM22--) T2 Ō(KME-
Hence after T2 O(KME 2) additional steps, the output of Algorithm 1 has error exp(-9((SS)).
3: for t 1,... .T' do
4: w -W (y(t-1)+//Exxx x., [log Po
Thus the base model ý learns the underlying graph E and all transition probabilities with exponentially small error. Under mild regularity conditions, all assumptions can be verified for P (see Propositions B.8 and C.8); to simplify the discussion, we henceforth assume the base model is exact, i ppp We remark that while the time to converge is quite long compared to the search, RL and distillation methods studied later, this is natural as pretraining is done on much longer timescales compared to test-time compute.
5: end for
6: w
(Ti)
t- -00 if .(2i) < Celurest
Pi)
(thresholding)
7: for 1- T Ti = =1, 1,... T2 do
8:
w(1) = w(t +nVExxx, (o
9: end for
clusters Ce will be hit before the process returns to Ck. and so Assumption 4 is satisfied Hence Assumption 4 naturally guarantees that it is relatively easy to explore the entire state space from any starting cluster.' !
3.2. Learning Sparse Rewards via Search
Having learned the underlying probabilities pf, the base model now performs CoT reasoning by generating each step of the chain (rf) in sequence starting from Xj = Xin- Since the reasoner has no prior knowledge of which steps it must take to progress towards Xout= on average will spend a long time trapped in each cluster before chancing upon a sparse edge (new idea) and moving From our quantitative dynamical analysis, we are able to obtain nearly tight characterization of the average hitting time.
3. Search Improves the Pretrained Model
3.1. Pretraining the Base (World) Model
We equate pretraining the base model with learning the un- derlying transition kernel p². Indeed, if the context window of an LLM is restricted to the tokens in the previous state, next-token prediction recursively defines a distribution over the following state, and further over reasoning chains of arbi- trary length. We encode each state x E S as one-hot vector in |S also denoted by x and write pí, = (e,y le.) For the model, we consider a simple linear softmax predictor:
new cluster.
Theorem 3.2 (expected hitting time). Under Assumptions 1-4, holds for all S Emax == O [ 1 M)-1) that
Pw( (-zz) = softmax (W,z)) WE [S
KM
E(X [Ex.. (amnTTT (Txmxt)
6
The pretraining data consists of random bigram samples (Xo, X1) where X1 ~ (-1oo); we allow Xo to be either uniform over S or distributed according to the stationary measure τO of pf. The latter arises when generating sam- ples (X,-1, X1)221 from the observed transitions of the (unbounded) chain (Xf) The model is trained by gra- dient descent with cross-entropy loss, with an intermediate thresholding step to mask out edges determined to not lie in F. See Algorithm 1 for details and Theorem D.1 for the full statement.
Intuitively, since each cluster is rapidly mixing, the chain will spend roughly (1/MM) of the time in states with out- bound edges, from where it escapes with probability O(e). Such rare events are distributed approximately exponen- tially, and must be repeated ((K) times to reach the cluster containing Xout where the chain will mix fast and likely hit Xout-
This result also illustrates a simple method to improve the hitting time: modifying the underlying probabilities to in- crease the denominator e. This corresponds to guiding CoT or fine-tuning the base model so that (correct) new, difficult reasoning steps are generated more often, ensuring a more efficient exploration of the solution space. However, this cannot be done by simply increasing the likelihood of low- probability edges, as there may be many low-probability edges within clusters as well; want to only boost the generation of sparse edges to preserve the capabilities of the pretrained model. Indeed, we demonstrate in Theorem 5.3 that any updates based on local information is not enough to improve reasoning ability in a precise sense.
Theorem 3.1 (convergence of pretraining). Let Xo ~ US or Xo ~ ne and X1 ~ pf (-1Xo) be random sam- ples from X Then for the gradient descent iterates ((() from Algorithm 1 w.r.t. cross-entropy loss
Lpre () = Exo.xi 1- log Dog@w(C (w (Xo]l.
the learned transition probabilities Pij (T) twwe (eyles)
converge with error supt, 1p! pig = (KM//)
'On the other hand, if the meta-chain has poorly connected re- gions, then X itself is amenable to metastability analysis, leading hierarchy of metastable representations at increasingly faster timescales (Wicks& Greenwald, 2005).
Instead, we run simple tree search protocol to identify
4

---

Metastable Dynamies of Chain-of-Thoupe Reasoning
Algorithm 2 Sparse Edge Search
3.3. Improving the Base Model via RL
Require: pretrained model pw
PRM mode keeps an external process reward 'model' (PRM) throughout the search process, which is simply the set M, which collects the estimated sparse edges over mul- tiple iterations of the outer loop to reconstruct Eg. We prove that the PRM is strongly consistent:
1: set R = ((K log K), N = G(log))
To (Mog 22),, maax = (M/e), M. Ø
2: for==1... R do
3: set Č, Cm E Ø, A [N]
4: sample Xo ~ US or Xo ~ T
5: fort = 1,... ; , maaxx do
Proposition 3.3. PRM mode of Algorithm returns Ms = E, with probability ((1/K).
6: for n E A do
7: generate X ~ pw pw (-1)--1)
Then by increasing the likelihood of transitions (r, E M, when the current state is z by factor of Smax e the PRM can guide CoT to follow pf rather than pf. It is immediate from Theorem 3.2 that the ex- pected hitting time decreases from ((KM/e) to @(K M/Emax). Moreover, the time complexity of Algo- rithm 2 is RTmax = ((KM/E), which is equal to the time to solve a single instance (Xin- Xout) without search, and the memory requirement is only O(M + K). This demonstrates the effectiveness of utilizing search to guide CoT generation.
8:
if < To then
(cluster search)
9:
C" C" (X...)
10:
else if 1 > To, Xpn & C then (edge search)
11:
É + E ((X )}
12:
A - A {n}
13:
end
14:
end for
15:
it =
To then C=n Cn
16:
17:
end if
18:
end for
19:
run Algorithm 3 with fw, É
(if RL mode) (if PRM mode)
However, it is often desirable during search to directly fine-tune the pretrained model, so that maintaining independent PRM is not necessary. RL mode performs online RL updates to Pw at each itera- tion of Algorithm 2; while many policy gradient methods can be applied, we analyze the popular proximal policy optimization algorithm (PPO-Clip, Schulman et al., 2017). Based on the estimate É of sparse edges originating from the initialized cluster, we define the advantage function as A(x, 1 if (2,, y) E É and 0 otherwise. Similarly to pretraining, samples are generated as Xo- ~ Un) or ah and X1 ~ (-) The objective of PPO-Clip to be maximized is (OpenAI, 2018)
the information gained
20:
M, + MM, U
21:
end for
22: return M.
Algorithm 3 PPO-Clip
Require: pretrained model fw. subset of edges E
1: set W(U) = W, TpPo = O(log Emax/E) a
((KM)
2: advantage function Á(x, v) 1 (())))))
3: for = 1,... .Tpro do
4: ((() w(t-1) sgnnn( LLro (VPPoo(WW-)) (W(L-));
5: end for
Zpro(W:4) A)
pw (X1 (X)) IF (X Celip
} |A(Xo. xi)
sparse edges, detailed in Algorithm 2. The method consists of randomly sampling a state Xo and rolling out N random walks in parallel to construct an estimate Ö of the cluster containing X, for time To. After the cluster has been suffi- ciently explored we continue to simulate each walk until transition outside Ö is detected, at which point the edge is marked as a sparse edge (added to É) and the path is termi- nated. This continues until until all paths are terminated or a time horizon Tmax is reached. Since we are not receiving signals from an external oracle but rather recording rare tran- sitions, this is similar to intrinsic rewards such as curiosity or exploration bonuses (Burda et al., 2018 8; 2019).
-xxo.x1
min
The old policy is fixed to p" during Algorithm 2. We use sign gradient ascent for simplicity of analysis (ordinary gradient ascent also guarantees convergence long as 2 e
Proposition 3.4 (convergence of PPO-Clip). By running RL mode of Algorithm 2 with PPO-Clip for a suitable Celip, the base model of is modified to pt where e' = (1-o(1)) (()) with probability 1 ((1/K).
The additional time complexity of running PPO-Clip is Ö(K log(Emaxx/e) /E)) which is small compared to the pretrain- ing time or search process. In particular, it again follows from Theorem 3.2 that the expected hitting time is improved by the factor maxx/s. /s. At the same time, the magnitude (total variation) of change to the pretrained model is negligible:
We consider two versions of this process, PRM mode and RL mode, depending on whether the information gained from search is collected into an external reward model or used to fine-tune the base model. The benefits of both methods for reasoning is discussed in the next subsection.
sup (+|x) - pf (+]x)][TV S s(1//M),
5

---

Metastable Dynamies of Chain-of- -hhougghtt Reasoning
Algorithm 4 Meta-chain Distillation
connecting the clusters containing Xim Xou- In partieular, if the goal is to extract only the connectivity of St, it suffices to take the sparse edge estimate M, of Algorithm 2 and perform a uniform random walk to find path between any two clusters. However, we want the distilled model to also preserve the underlying dynamics of the original chain as best as possible. To this end, we implement the following process, detailed in Algorithm 4.
I: set S. 2, ()) 0. (xx) 0 for all x E S,
2: Taist OOM/2 2) Tthres O(ME
3: " = (KK)
((log(M/e))
4: while L -'(0)) + do
(cluster labeling)
5: draw Xo E (0)
6: S. + S. U (Xah. ((xu)= + Xo
7: for forl= = 1,,... To do
8: generate X²- ~ p=( p (-1XE-1)
We first choose set S. {=1.-.. #xK } of representatives Ty of C2 and assign each state to its representative via the map L: S + S.; this can be done by exploring each cluster similarly to the first To steps of the search process.
9: ((F;) c Xo
10: end for
11: end while
12: for t 2, do
(data collection)
13:
if X E S. then
Data collection. The data for distillation is collected by continually running CoT and recording the frequency of transitions (or non non-transitions) between S., The yields one datum per CoT step, and can also be implemented in parallel for an arbitrary number of independent chains.
yd v y(tuer)) X;
14:
15:
1prov +1
16: else
17: YO r1 f ((xF)
18: end if
19: end for
(1) If Xi E S. and the previous return to S. was X then add (XF (X Xx) Daist-
fprev
20: for = 1,... Tdist do
(distillation)
21:
( = (2--1) 1/ AV..r.n loollllooge P [Y)]
(2) If X & S. (no transition) add (u(Xf): (XF)) to Ddist-
22: if Tuhres then
(Tihree) -00 if Ust 23: 2kg
(Tehrme) Cthrese/M /M
This requires only O(K²) memory for frequency counts; no cache for X is needed. The cluster labels i and parameters Z require O K M) and O ( memory, respectively. We suppose the process is run for arbitrarily long time so that we have access to the population distribution of Daist- We then one-hot embed S, in IR and use the collected data pairs to train a softmax model (zz(|1z) softmax( (tttmax((Z,n))) (Z),)), Z E IR K similarly to pretraining. Finally, we rescale time so that the non-diagonal entries sum to O(1), reducing redundant within-cluster transitions.
24: end if
25: end for
(Taia)
26: #ke- f 2kt
+ for l # k
(time rescaling)
27:
return
so the original capabilities of the base model are generally preserved. Hence RI is also extremely efficient for fine- tuning the pretrained model to improve CoT.
Equivalence with meta-chain. The data (Y, Yi) Daist has been constructed so that the distilled model learns the following kernel o5 on Sa: Yo IF, Yi 25(1)1)) where
4. Distillation to a Smaller Model
A prominent innovation in the LLM development pipeline is to distill CoT of powerful model into smaller, more eff- cient model. This approach has been shown to significantly enhance reasoning ability, especially compared to directly training the smaller model with RL (Shridhar et al., 2022: Hsieh et al., 2023; Gandhi al., 2024: Guo et al., 2025). In this section, we showcase an explicit distillation scheme for our CoT model that efficiently generates the hard rea- soning steps to solve any task while faithfully capturing the metastable dynamics of the original system.
(((e)(())))) = :==]<==/aa +f( Pa, a. (X: 75, = =x), h #
(<<x)(x)) := 1- 1-1- Eeyz (x
This kernel is lazy version of the process obtained from X by deleting all transitions to states outside S., with an additional time rescaling according to the stationary proba- bility oh (2x). This is slightly different from the construction given in Betz & Le Roux (2016), as we do not presume ac- cess to the stationary distribution of the unperturbed chain ph and must sample directly from π². Moreover, L is de- pendent on the choice of representatives and thus different from the 'canonical' meta-chain of in general. Nonetheless, of is faithful to the meta-chain in a rigorous sense:
4.1. Distilling Cluster Transitions
The metastable chain of (Section 2) provides a natural no- tion of compression for the nearly reducible system X= by collapsing each cluster into a single state. For many down- stream tasks (including the logic task studied in Section 5) it may be satisfactory to retrieve only the hard reasoning steps
Proposition 4.1. Denote the return time of of to Fy as To
6

---

Metastable Dynamies of -hoin-of-Thought Reasoning
For all k, l [K] with k: o e, it holds that
5. Logical Reasoning is Hard without Search
5.1. Logical Reasoning Task
Pzx (F < Fo.0)) 1 + (1). 2i (C
In this section, we further investigate the benefits of search for reasoning by adding a quantitative 'logic task' on top of the path-finding task. This provides two benefits. First, hav- ing numerical answer allows us evaluate the hardness of the task from learning-theoretic perspective, separate from the previously obtained hitting time bounds. Second, by having the answer depend only on the sparse edges along a path, the reasoner is required to estimate which edges are sparse - other words, understand which reasoning steps are actually important in order to solve the task. Taking a proof problem for example, we expect an LLM with strong reasoning capability to not only generate plausible solu- tion via next-token prediction but also understand its own proof, so that it can correctly answer logical questions such as "what are the key ideas of this proof?" or "what happens if we replace step with Y?" We attempt to formalize this notion using group actions (Definition E.
That is, the escape probabilities of of converge of with uniformly vanishing relative error. This property is desir- able as it shows the eventual likelihood of escaping to each cluster (i.e.. reaching a certain idea) is consistent across different choices of Se.
4.2. CoT of Distilled Model
To analyze the utility of the trained model pzz,. we make the additional assumption:
Assumption 5 (inbound sparse edges). All sparse edges leading to each cluster Cs terminate a fixed point Tu- For any sparse edge (x', (1) from Cs. there exists from Iy to x! in Cs of probability bounded below.
Then we may specify S. as the set of the points zg- This ensures that representatives will not be skipped; otherwise, a CoT passing through Cz, Ce, Cn in succession may miss Iz and record the wrong transition (x) (although the likelihood of this is o(1) regardless).
Logical actions. Let (G, o) be a finite group with identity eg. The logical value (or simply logic) of a reasoning chain is an element of an abstract space R. equipped with a G- action + 9 -- r. Each edge e E E is assigned a logical action (e) E G' which acts the current logie when the edge is selected. To focus on learning hard steps, we assume that the logical action of edges not in E, are trivial, o ale; == eg. Let sb : S + R be an arbitrary embedding map. For a valid path Xu.r S S, we define the corresponding logic sequence To.T S R as
Now, as with pretraining, the distilled model will converge to of when trained with cross-entropy loss on Daist-
Proposition 4.2 (convergence of distillation). For the gra- dient descent iterates z from Algorithm 4, the learned probabilities converge to of after Taist ((M2s-2)
ro = (Xo). Tt = a==((X-1,XX) -
supk.t (a (2e)2x) To (x) K (1))
For example, if each state is Boolean expression being manipulated according to certain rules, R = G Zz could be used to encode the evaluation of the current expression by switching between (True) and 0 (False) depending on the effect of cach manipulation. G' could also be taken to be a space of functions with the evaluation action g(),, so that the logic computes a repeated composition of functions. When the chain terminates, the final logic 'T =: r(XoT)) is returned. Note that logical values are not unique to states and rr depends the entire path Xo.r.
We point out the time to convergence is much faster than pre- training time O(KM²= ?) (Theorem 3.1), and also more computationally efficient since we are training a size K22 model rather than size (KM)².
Finally, after time rescaling, the model az+ is capable of efficiently finding a path from the cluster containing Xn, to the cluster containing Xout, with hitting time linear in [Sa] and independent of the difficulty parameter E.
Theorem 4.3 (hitting time of distilled CoT), For all k + f, fzz (#e( = @(1) if there exists a sparse edge from Ck to Ct or 0 if not. Moreover, the hitting time Tt, ae E S. by âzi satisfies E.. [ (KK).
Logic Task. Given (Xin; Xout) ~ D, the goal is to output both a valid path Xo.r from Xnn Xout and its logical value r(Xu:r) Since any path can be made simple by deleting loops, here we require valid paths to be simple.
The returned sequence of clusters Co.r indicate the exis- tence of a path from Xin to Xout passing through precisely these clusters in order. Once Co.r is determined, a weaker reasoning agent (c.g., the base model p²) may also efficiently resolve the fine-graine -raiggri dynamies within each cluster.
To establish a rigorous distinction between the use of a search algorithm and lack thereof, we consider models con- sisting of a pretrained base model or linguistic component Mp. responsible for learning p and generating a valid CoT,
7

---

Metastable Dynamies of Mhain-of-Thoughi Reasoning
and reasoning component fe. which predicts the answer r ((oorr based on (limited) information from Mp. As in Section 3, we suppose MM has perfectly learned the kernel and can output arbitrary valid paths MM(Xmm Xour). ). solv- ing the first part of the task. Here we do not consider the time complexity of running Mp. which (as we have seen in Theorem 3.2) can be quite long without search-and- improvement protocol. Thus the main task of the reasoner is to execute logical computations along generated CoT.
To understand learning with this additional (restricted) in- formation, propose the following generalization of the statistical query dimension (Kearns, 1998; Feldman, 2017).
Definition 5.1 (SDA: SQDIM with access). Let P be the set of ground truths and H = {hp X + {+1} | E P} the associated concept class with inner product (-, -hH. Let Ip be any value or any function on X depending on p. Then the statistical query dimension of P with access to I and tolerance is defined
In this section, we assume a stronger uniform lower bound in Assumption 3 on the minimum number of hard steps: otherwise, querying a single sparse edge (Xin, oust) E (p) could immediately reveal its (nontrivial) action.
(P;+ == su : P' PP,, ((hp::hp23 S r. TpL Ip
In this section, we consider T = O and omit its notation. Ex- tending classical analyses (e.g.. Shalev-Shwartz et al., 2017: Shamir, 2018), we prove a general limitation for gradient- based learning when additional information Ip is provided.
Assumption 3'. For any (Xm: Xout) ~ DD and any valid path Xo.r with Xo- = Xin and Xy = Xout, it holds that min [Xo:r O E.I = ((K).
We remark that this condition can be weakened to 2(log K) if IM 2 (KK), in which case our results hold with e -R(K) replaced by K K=1(1),
Theorem 5.2 (SQ learning with additional information). Let fo be any parametric model of the form
+ fo(s, Io())
Concept class. Define P the set of transition kernels on satisfying Assumptions 1, 2 and denote the sparse edge set of p E P as (p).). The logical action a can be seen as generated by sampling A: S x S + G i...d. uniformly from G, then masking out all edges not in E (p) by setting them to eg. Thus A can be regarded as a variable separate from the target and the logic is computed recursively as
Let the loss function be L(0:p) := 1/, fe V soll SDA(P, (D) Then choosing p randomly from a subset P, any iterative algorithm A(O) that makes at most queries the 8-corrupted gradient oracle V has expected loss
felp--elll l3 and set ==
Exp (p(L(A())))) 2 1 SDA((P,)
with probability at least 1 - nd.
(Xo) = ((X),, (Xoa)
Note that we only consider the squared loss in our formu- lation for simplicity. While squared loss only answers cor- relational queries, CSQ-learaabliity is equivalent to SQ- learnability for Boolean concepts (Bshouty & Feldman, 2001).
((( (X.(()())))) Xx) E (p) (X--1, X.) & (p)..
(AAN(Xo:(-1))
Finally, the logic (Xoor) is mapped to scalar out- put via classifier Φ R + {+1, 11. We assume that Eyea (olg r)]] - 0 for all E R. The concept class is thus
5.3. Results on Hardness of Logical Task
H = -1h < ESX ;IEP :
We consider four types of access to the pretrained model. Note that a local neighborhood of subset S' C S in the weighted directed graph defined by p is defined as the sub- graph consisting of states reachable with a bounded number of steps from any state in S
hy Xout, A) @orap (X Xout))
with inner product by E D. Xout; A)hyr (Xins Xout A)}.
equipped
(1) No pretraining, I, = Ø: the learner So (Xin: Xont A) has not been pretrained and does not receive any infor- mation on p.
5.2. A Measure of Hardness with Restricted Access
In previous sections, we have seen that pretraining Mp = fw and running a search or distillation algorithm fo will correctly infer the underlying sparse structure. In this case, computing r' (.A. (Xin, Xomr)) is trivial by concatenat- ing actions along the identified sparse edges. In contrast, we now restrict the reasoning component's ' access to p by only allowing certain queries to Mp. This makes it difficult to infer the sparse structure and true logical actions.
(2) Path-only (no search). I = M: the learner is allowed depend inputs Xin: Xout, and A, and also the generated path Mp(Xin, Xout). That is, the linguistic component (base model) will return a valid CoT for the input at hand, but we cannot simulate different chains from p to execute some search policy or inference algo- rithm.
8

---

Metastable Dynamies of Chain-of-Thoughe Reasoning
(3) Local search, I (b): the learner is allowed full access local neighhorhood of Mp(Xin: xuut) in the graph of p, including connectivity information and transition probabilities. For instance, it can flag low-probability edges as more likely to be sparse, or run bounded-length CoT from X or Xout-
search, RL, and distillation. We showed that search can improve reasoning by identifying critical sparse transitions (hard steps), which can then be leveraged to fine-tune the pretrained model via RL or distilled into more efficient representation, improving hitting times for path generation. We further established learning-theore -teeiingctt limits on reasoning with restricted information and showed that logical reason- ing tasks become intractable without global search.
(4) Full search, I = P: the learner is given full access to the entire graph of p at all times. In this case, Algorithm 2 or 4 can be used infer (p) and generate CoT efficiently, and also perform the desired computation hp
Future directions. We have studied a simple curiosity- based unsupervised reward model; it would be interesting to see how a more complex search process could be guided with outcome rewards. Our framework could also be used to study other inference-time methods such as CoT revision (e.g., backtracking to better locate sparse edges), as well as iterative finetuning of the pretrained model, and explore scaling laws for inference time compute.
Our main negative result states that (1)-3) cannot solve the logic task with polynomial compute, and thus global search is necessary:
Theorem 5.3. SDA(P:P) and
SDA(P; Ø) 2 (DA(P;M) 2 SDA(P;)bd(MM) 2 ea(k)
Remark 5.4. The necessity of global information for certain learning problems (globality harrier) has been conjectured in Abbe et al. (2024), where the hardness of a 'cycle task' is proved. These results are also closely related to classical SQ- hard problems such as subset parity. The precise relationship between SDA, globality and learning is still open.
A Acknowledgements
This research is supported by the National Research Foun- dation, Singapore and the Ministry of Digital Development and Information under the AI Visiting Professorship Pro- gramme (award number LVP-2004-0004. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore and the Ministry of Digital Development and Information.
Remark 5.5. While it suffices to lower bound the strictest term SDA(P: (.))). we exhibit different constructions for each of the three dimensions as they offer increasing levels of generality. In particular, SDA (P; Ø) can be real- ized by P' C P containing any prescribed E P and for any D. Moreover, the difficulty is solely due to the logical part of the task; without pretraining, the reasoner will take exponentially many guesses to even produce a valid path.
The authors thank Jimmy Ba and Yuexiang Zhai for helpful discussions. JK was partially supported by JST CREST (JPMJCR2015). JDL acknowledges support of the NSF CCF 2002272, NSF IIS 2107304, and NSF CAREER Award 2144994. TS was partially supported by JSPS KAKENHI (24K02905, 20H00576) and JST CREST (JPMJCR2115), This research is unrelated to DW's work at xAI.
Corollary 5.6 (hardness without global search). Suppose (Lnnnd((p(X))) (xut)) X).t)); A) is any parametric model with polynomially bounded gradients, that can freely search a local neighborhood of the generated COT. Then any iterative algorithm A()) that makes at most polynomial queries to the e ((())))))) -()())) corrupped gradient oracle L satisfies
Impact Statement
Ep(L(A(0):)) 2 1 -
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
with probability (2(K) for M sufficienily large.
Hence H. cannot be even weakly learned in polynomial time search is not long enough. The key intuition is that if the graph is locally isomorphic, local search cannot distinguish between sparse inter-cluster edges and low -wwobbbbbility but within-cluster edges as it cannot explore the whole cluster. This demonstrates the importance of spending sufficient inference-time compute for improving reasoning ability.
References
Abbe, E.,, Bengio, S., Lotfi, A., Sandon, C., and Saremi, O. How far can transformers reason? The locality barrier and inductive scratchpad. In Advances in Neural Information Processing Systems, 2024.
6. Conclusion
Bai, Y., Kadavath, S., Kundu, S., Askell, A., Kernion, J., Jones, A., Chen, A., Goldie, A., Mirhoseini, A., McKin- non, C., et al. Constitutional AI: harmlessness from AI feedback. arXiv preprins
We introduced a metastable Markov framework for model- ing COT reasoning, revealing the benefits of inference-time
2022.

---

Metastable Dynamics of Chain-of-Thonn Thought Reasoning
Beltrán, J. and Landim, C. Metastability of reversible finite state Markov processes. Stochastic Processes and their Applications, 121(8):163331677 2011.
in-context learning Markov chains. Advances in Neural Information Processing Systems, 2024.
Fackeldey, K., Sikorski, A., and Weber, M. Spectral clus- tering for non-reversible Markov chains. Computational and Applied Mathematics, 37, 2018.
Besta, M., Blach, N., Kubicek, A., Gerstenberger, R., Pod- stawski, M., Gianinazzi, L., Gajda, J.. Lehmann, T., Niewiadomski, H., Nyczyk, P., et al. Graph of thoughts: solving elaborate problems with large language models. In Proceedings of the AAAI Conference on Artificial In- telligence, 2024.
Feldman, V. A general characterization of the statistical query complexity. Proceedings of Machine Learning Research, 65:785 830, 2017.
Betz, V. and Le Roux, S. Multi-scale metastable dynamics and the asymptotic stationary distribution of perturbed Markov chains. Stochastic Processes and their Applica- lions, 126( 3:3499-3526, 2016.
Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L. Towards revealing the mystery behind chain of thought: a theoretical perspective. In Advances in Neural Informa- tion Processing Systems, 2023a.
Bhattamishra, S., Patel, A., Blunsom, P., and Kanade, V. Understanding in-context learning transformers and LLMs by learning to learn discrete functions. In Interna- tional Conference on Learning Representations, 2024.
Feng, X., Wan, Z., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang. J. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint M.Xi::239.117777 2023b.
Bianchi, A. and Gaudillière, A. Metastable states, quasi- stationary distributions and soft measures. Stochastic Processes and their Applications, 126, 2016.
Fernandez, R., Manzo, F., Nardi, F, and Scoppola, E. Asymptotically exponential hitting times and metastabil- ity: A pathwise approach without reversibility, Electronic Journal of Probability, 20, 2014.
Bovier, A., Eckhoff, M., Gayrard, V., and Klein, M. Metasta- bility and low lying spectra in reversible Markov chains. Communications in Mathematical Physics, 228:219-255, 2002.
Fernandez, R., Manzo, F., Nardi, F. R., Scoppola, E., and Sohier, J. Conditioned, quasi-stationary, restricted mea- sures and escape from metastable states. The Annals of Applied Probability, 26(2):760-793, 2016.
Bshouty, N. and Feldman, V. On using extended statistical queries to avoid membership queries. Journal of Machine Learning Research, 2:529 545, 09 2001.
Fritzsche, D., Mehrmann, V., Szyld, D., and Virnik, E. An SVD approach to identifying metastable states of Markov chains. Electronic Transactions on Numerical Analysis, 29:46 69, 2008
Burda, Y., Edwards, H., Pathak, D., Storkey, A., Darrell, T., and Efros, A. A. Large-scale study of curiosity-driven learning. In International Conference Learning Rep- resentations, 2018.
Gandhi, K., Lee, D., Grand, G., Liu, M., Cheng, W., Sharma, A., and Goodman, N. D. Stream of search (SoS): learning to search in language. arXiv preprint wrXiv:2404.03683 2024.
Burda, Y., Edwards, H., Storkey, A., and Klimov, O. Explo- ration by random network distillation. In International Conference on Learning Representations, 2019.
Guo, D., Yang, D.,, Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., et al. DeepSeek-R1: incentivizing reasoning capability in LLMs via reinforce- ment learning. arXiv preprint arXiv:2501.1294 2025.
Chiang, D., Cholak, P., and Pillay, A. Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, 2023.
Hoffmann, J., Borgeaud, S., Mensch, A., Buchatskaya, E., Cai, T., Rutherford. E., Casas, D. d. L., Hendricks, L. A., Welbl, J., Clark, A., et al. Training compute-optimal large language models. arXiv preprint a5X5v 2022.
Cirillo, E., Nardi, F., and Sohier, J. Metastability for general dynamics with rare transitions: escape time and critical configurations. Journal of Statistical Physics, 161, 2014.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The Llama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024.
Hsieh, C.-Y., Li, C.-L., Yeh, C.-K., Nakhost, H., Fujii, Y., Ratner, A., Krishna, R., Lee, C.-Y., and Pfister, T. Distill- ing step-by-step! Outperforming larger language models with less training data and smaller model sizes. arXiv preprint arXiv:2305.0233:0 2023.
Edelman, E., Tsilivis. N., Edelman, B. L., eran malach, and Goel, S. The evolution of statistical induction heads:
10

---

Metastable Dynamics of Shain-of-Thoughe Reasoning
Hu, X., Zhang, F., Chen, S., and Yang, Z. Unveiling the tistical foundations of chain-of-thought prompting meth- ods. arXiv preprint arXiv:2408. 14511, 2024.
Landim, C. Metastable Markov chains. arXiv preprint arXiv:/807.04144 2018.
Landim, C. and Xu, Metastability of finite state Markov chains: recursive procedure to identify slow variables for model reduction. Latin American Journal of Proba- bility and Mathematical Statistics, 13, 2015.
Ildiz, M. E., Huang, Y., Li, Y., Rawat, A. S., and Oymak, S. From self-attention to Markov models: unveiling the dynamics of generative transformers. In International Conference on Machine Learning, 2024.
Levin, A., Peres, Y., and Wilmer, E. L. Markov Chains and Mixing Times. American Mathematical Society, 2nd edition, 2009.
Jacobi, M. N. A robust spectral method for finding lumpings and meta-stable states of non-reversible Markov chains. Electronic Transactions Numerical Analysis, 37:296- 306, 2010.
Li, H., Wang, M., Lu, S.,, Cui, X., and Chen, P.-Y. How do nonlinear transformers acquire generalization-uee guaarattedd CoT ability? In High-dimensional Learning Dynamics 2024: The Emergence of Structure and Reasoning, 2024a.
Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., Beutel, A., Car- ney, A., et al. OpenAl ol system card. arXiv preprint arXiv:2412.16720, 2024.
Li, Y., Sreenivasan, K., Giannou, A., Papailiopoulos, D., and Oymak, S. Dissecting ooain--f-thought compositionality through in-context filtering and learning. In Advances in Neural Information Processing Systems, 2023.
Ji, Z. and Telgarsky, M. Risk and parameter convergence of logistic regression. arXiv preprint arXiv:/803.07350 2019.
Li, Z., Liu, H., Zhou, D., and Ma, T. Chain of thought em- powers transformers solve inherently serial problems. arXiv preprint arXiv:2402.. 12875, 2024b.
Jones, A. L. Scaling scaling laws with board games. arXiv preprint arXiv:2104.03111 2021.
Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. arXiv preprint arXiv:2305.20050 2023.
Kahneman, D. Thinking, fast and slow. Farrar, Straus and Giroux, 2011.
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Madras, N. and Randall, D. Markov chain decomposition for convergence rate analysis. Annals of Applied Probability, 12, 2001.
Kearns, M. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983-1006, November 1998.
Makkuva, A. V., Bondaschi, M., Girish, A., Nagle, A., Jaggi, M., Kim, H., and Gastpar, M. Attention with Markov: A framework for principled analysis of transformers via Markoy chains. arXiv preprint arXiv:2402.0m 40111416,, 2024.
Kim, J. and Suzuki, T. Transformers provably solve par- ity efficiently with chain of thought. arXiv preprint 2rX1v:2410.08633, 2024.
Merrill, W. and Sabharwal, A. The expresssive power of transformers with chain of thought. arXiv preprint arXih:2310.07923, 2023.
Kimi, T., Du, A., Gao, B., Xing, B., Jiang, C., Chen, C., Li, C., Xiao, C., Du, C., Liao, C., et al. Kimi k1.5: scaling reinforcement learning with LLMs. arXiv preprint arXiv:2501.12599 2025.
Meyer, D.
The dondition of finite Markov chain and perturbation bounds for the limiting probabilities. SIAM J. Algebraic Discret. Methods, 1:273-283, 1980.
Meyer, C. Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible sys- tems. SIAM Review, 31(2):240-27 272, 1989.
Kumar, A., Zhuang, V., Agarwal, R., Su, Y., Co-Reyes, D., Singh, A., Baumli, K., Iqbal, S.. Bishop, C., Roelofs, R., et al. Training language models to self-correct via reinforcement learning. arXiv preprint 24X 2024.
Nichani, E., Damian, A., and Lec, J. D. How transform- ers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14733, 2024.
Landim, C. Metastability for non-reversible dynamics: The evolution of the condensate in totally asymmetric zero range processes. Communications in Mathematical Physics, 330, 2012.
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H.,
Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., et al. Show your work: scratchpads for

---

Metastable Dynamics of Seain-of-Thoughee Reasoning
intermediate computation with language models. arXiv preprint
Uesato, J., Kushman, N., Kumar, R., Song, F., Siegel, N., Wang. L.,, Creswell, A., Irving, G., and Higgins, I. Solv- ing math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211 2022.
2021.
OpenAI. Spinning up: proximal policy optimization (PPO), 2018. URL https://spimmingup openai coammaii.oomeeeee www.coom/n.../e /en/ latest/al peteet//lggorrttm/pppppo html. Accessed: 2025-01- 26.
Wei, J., Wang, X., Schuurmans, D., Bosma, M.. Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 24837, 2022.
Paulin, D. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20:1-32, 2015.
Wen, K., Zhang, H., Lin, H., and Zhang, J. From sparse dependence sparse attention: unveiling how chain-of- thought enhances transformer sample efficiency. arXiv preprint arXiv:2410.05459 2024.
Radford, A., Narasimhan, K., Salimans, T., and Sutskever, Improving language understanding by generative pre- training. OpenAl Blog, 2018.
Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B., and Mirrokni, V. Understanding transformer reasoning capabilities via graph algorithms. arXiv preprint arXiv:2405./8512 2024a.
Wicks, and Greenwald, A. An algorithm for computing stochastically stable distributions with applications to mitiagent learning in repeated games. In Conference on Uncertainty in Artificial Intelligence, 2005.
Sanford, C., Hsu, D., and Telgarsky, M. Transformers, paral- lel computation, and logarithmic depth. In International Conference on Machine Learning, 2024b.
Wolfer, G. and Kontorovich, A. Estimating the mix- ing time of ergodic Markov chains. arXiv preprint arXiv: 1902.01224, 2022.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06333 2017.
Wu, Y., Sun, Z., Li, S., Welleck, S., and Yang. Y. Infer- ence scaling laws: An empirical analysis of compute- optimal inference for problem-solving with language models. arXiv preprini arXiv: 2024.
Shalev-Shwartz, S., Shamir, O., and Shammah, S. Fail- ures of gradient-based deep learning. In International Conference on Machine Learning, 2017.
2024.
Xiang, V., Snell, C., Gandhi, K., Albalak, A., Singh, A., Blagden, C., Phung. D., Rafailov, R., Lile, N., Mahan, D., et al. Towards System reasoning in LLMs: learning how to think with meta chain-of-thought. arXiv preprint arXiv:2501.0460 2025.
Shamir, O. Distribution-specffi hardness of learning neural networks. Journal of Machine Learning Research, 19: 32:1-32:29, 2018.
Shridhar, K.. Stolfo, A., and Sachan, M. Distilling reasoning capabilities into smaller language models. arXiv preprint arXiv:2212.00193, 2022.
Xie, Y., Goyal, A., Zheng, W., Kan, M.-Y., Lillicrap, T. P., Kawaguchi, K., and Shieh, M. Monte Carlo tree search boosts reasoning via iterative preference learning. arXiv preprint arXiv:2405.0m 00451,, 2024.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Grae- pel, T., et al. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Sci- ence, 362(64699:11111 140- 1144, 2018.
Xu, K., Li, J., Zhang, M., Du, S. S., Kawarabayashi, K.-i., and Jegelka, S. What neural networks reason about? arXiv preprint 190iv:1905.1300
2019.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36. 2024.
Snell, C., Lee, J., Xu, K., and Kumar, A. Scaling LLM test- time compute optimally can be more effective than seal- ing model parameters. arXiv preprint arXiv:2408.0r 03314, 2024.
Zekri, O., Odonnat, A., Benechehab, A., Bleistein, L., Boullé, N., and Redko, I. Large language models as Markov chains, arXiv preprint 4rXiv:2410.02724, 2024.
Tifenbach, R. On an SVD-based algorithm for identifying meta-stable states of Markov chains. Electronic Transac- tions on Numerical Analysis, 38: 38:17-33, 2011.
Zelikman, F.,, Wu, Y., Mu, J., and Goodman, N. Star: boot- strapping reasoning with reasoning. Advances Neural Information Processing Systems, 35:15476-193 15488, 2022.
Trinh, T. H., WU, Y., Le, Q. V., He, H., and Luong, T. Solv- ing olympiad geometry without human demonstrations. Nature, 625(7995):476 2024.
12

---

Metastable Dynamics of Chain-of-Thonn Thooghtt Reasoning
A. Additional Related Works
Theoretical Analysis of CO'. Some theoretical works have focused on the expressivity of CoT (Feng et al., 2023a; Merrill & Sabharwal, 2023; Chiang et al., 2023; Li et al., 2024b), analysis of optimization and estimation ability (Li et al., 2024a; Hu et al., 2024; Kim & Suzuki, 2024), or in-context learning ability (Li et al., 2023; Bhattamishra al., 2024). More closely related our paper, Sanford et al. (2024b;a); Abbe et al. (2024) study the algorithmic reasoning capabilities of CoT or scratchpad transformers for certain computational or graph-based tasks. Also, Nichani et al. (2024) analyze how simple transformer models learn latent causal structure within the data.
LLMs as Markov processes. Zekri et al. (2024) investigate the equivalence between autoregressive models and general length Markov chains. Makkuva et al. (2024); Edelman et al. (2024) model sequential data as a Markov chain and analyze the properties of single-layer transformer. Iidiz et al. (2024) establish a link between self-attention and condxxt-oondiiooned Markov models. Such works generally focus on interpreting next-token prediction of a specific architecture, and do not consider the abstraction to CoT reasoning.
Metastable Markov chains. The literature on metastable Markov processes is vast (e.g., Madras & Randall, 2001; Bovier et al., 2002; Beltrán & Landim, 2011; Landim, 2018). Here we only mention the results most relevant to our theory. In particular, as reversibility is unrealistic to presume for language or reasoning models, we generally restrict our attention to works on nonreversible processes. Fritzsche et al. (2008); Jacobi (2010): Tifenbach (2011), 1); Fackeldey et al. (2018) study various spectral methods identify metastable states of Markov chains. Landim (2012); Cirillo al. (2014); Fernandez et al. (2014; 2016); Bianchi Gaudillière (2016) analyze critical configurations and escape times for metastable dynamics, while Landim & Xu (2015) propose recursive procedure for model reduction. Most relevant our work, Wicks & Greenwald (2005); Betz& & Le Roux (2016) give complete hierarchical characterization of the effective dynamics of perturbed chains but only in the asymptotic limit; building on their results, we develop new quantitative perturbation analysis throughout Appendix C.
B. Preliminaries
B.1. Pseudo-Spectral Gap and Mixing
By taking Assumption and multiplying by a constant if necessary, we assume that S of (y/ax) for some and all (r,y) v) E E, throughout the appendix.
Definition B.1 (mixing time). For a time- homogenogge ergodic Markov chain X = (X1)120 on finite state space Ω with transition kernel p and stationary distribution the mixing time Imix is defined as
{
mix (c) min
2 Vs t,
(1p) F//V s
zEi
Definition B.2 (hitting and return times). The nthh hitting time and return time of X to set A C S for n E N are defined as
in = inf 2 (0
E A} n),
,,, inf > 0: (0 <t X A} = n].
In particular, we write 7 T2, and F = A.I. We write - = b. etc. for simplicity.
The chain X is reversible if it satisfies the detailed balance equation
(=))(()()) (v)p(aly)
Yz,y E Ω.
While we do not assume reversibility in this paper, it is informative to compare the conditions for rapid mixing. Denote the transition matrix corresponding to p by P and let the eigenvalues of P ordered by absolute value be 1 x > [P2( 2 (P) 2 .... For reversible chains, all eigenvalues are real and the mixing time is closely governed by the (absolute) spectral gap (P) - (P)) (Levin al., 2009):
1
x(P) 11)
1
1 log 7(P)
< Imix (c) S
2 log 2c
T.C'
13

---

Metastable Dynamics of Chain-of-Thought Reasoning
where z minzen π ) is the minimum stationary probability.
For nonreversible chains, the analogous quantity to ((P) is given by the psendo-spectral gap: Definition B.3 (Paulin (2015)). The pseudo-spectral gap of P is given as
((P
(
(P)
max meN
77
where Pl is the time reversal of P, defined as P = TT Pi/me.
When X is reversible, it holds that ((P) < <P) S (P) (Wolfer & Kontorovich, 2022, Lemma 15). Moreover, (PP controls the mixing time similarly to (P))
Proposition B.4 (Paulin (2015), Proposition 3.4). For 0 < <E<l,
1- 2e (e) s 7T(P) 7T(P)
1
+ log 1
[1 2log 2e
na
Denote the maximum row sum norm as ||A||1,0 = max; Ej |ayl for A = (atj).
Lemma B.5. For E I x m holds that ||Al|2 S /m|lAAla.
A 1,,00
Proof. For arbitrary v E Ihm with ||a||| = 1,
Auil
Σ
Σ aijyy
2 $ Σ ΣΣΣ.
Elas) |aisl
mmlAA <m||All,
dij
i
B.2. Stochastic Complementation
We denote the stochastic block matrix P corresponding to the kernel p" and partition $ = k= Ck as
Pi
P
IK
p
P
P
That is, the probability yf (y/rr) is contained in the (x,v) component, and the rows of P all sum to 1. The stochastic complement of P is defined as (Meyer, 1989)
S.G. = P Rk + PI- P.
where P is the kth block row of P with P Rs removed; P is the kth block column of p with P removed; and P is the principal block submatrix Ps with the kth row and column removed. When = 0, it follows that P = when i A j and 50 = od && is the transition matrix of pd restricted to Cg-
The following results are fundamental to the theory of stochastic complementation.
Theorem B.6 (Meyer (1989), Theorem 2.3). P is an irreducible stochastic matrix e >> 0, each stochastic complement Si is also an irreducible stochastic matrix. Moreover, S is equal to the transition matrix of the reduced chain k. on Cz
X Toam
t No
(4)
obtained from X by deleting transitions to states outside of Ck.
We further denote the transition kernel of Xh corresponding to Si sia so that sg, = p'lc,, and its return time to subset C Ct as 7
14

---

Metastable Dynamics of Chain-of-Thoughe Reasoning
Lemma B.7 (Meyer (1989), Theorem 6.1). Denoling the block diagonal matrix S diag Sik holds for all k E [K] that
S P = 1l and | -P-ll1,0 = max
kE(K]
In particular, immediately follows that
K 00 I doute,
| -S-lill S 2dout
(5)
We now exhibit conditions on the unperturbed matrices P which imply the bounds on the spectral gap and stationary distribution of & in Assumption up to constant factor. The argument be repeated to show that Assumption 1 holds for the pretrained model ý of Theorem 3.1, as the error is exponentially small. This also implies that Assumption 4 is robust to perturbation via Proposition C.8.
Proposition B.8. Suppose that each pllc, is reversible with spectral gap ((P ks " and the stationary measure Pk x satisfies p/M S pa (x) S p' /M. Moreover suppose that the eigenvalue matrix VE of Ph has condition number bounded as n( v.) | vll22 V lle S Kov M. and the group inverse A of P satisfies || S 9o for constants Ko- 9o- Then for all E of M
(SEx))
and
P 2M
2p M
Yo E Ck.
Proof. By the proportionality of of in Assumption 2 and (5) we have
S
Ph $ |S PRill,,, + |P
10
S doute + max =ECx yECk
Σ
1p'(y/)) 1² (ulz))
< 2douts,
so that | Palll & 2/ e by Lemma B.5. Then by the Bauer-Fike theorem holds that
(22()) de (PP))) S <(V.) - -Poell S 2ng =(1),
therefore (SE 2 (S 3 for sufficiently large M. Furthermore by the condition number bound in Meyer (1980)
the perturbed stationary distribution satisfies
1 - melloo I
P llal I 2gudout = o(M
proving the second assertion.
With these results in mind, we can prove the following concentration bound for the reduced chain X k.s.
Lemma B.9. For all x, E Ck and d > 0 it holds that P, 2 m) <
long
8M 1 py
M
m
log
loog
(6)
5
Proof. By Proposition B.4, the mixing time of he is bounded above as
1
M
M
6mix tmix
<
1 (1+2 2log
+ log min m
log
2M
7((E
7
p
so that for any x, Ck.
( )mix Amix (y/z) 2 T5(1)) (Tī(T)
(s
Amix (x/lz)) 2 M
11(s5x)) Amix - 2 p 2M
15

---

Metastable Dynamics of Chain-of-Thought Reasoning
&& This implies each step of the mix- skipped chain tmez
well-mixed, and hence
[m//mix
Pa 2 m) suu
II
1 1- 1-Px xp.e
(X = v)
t=1
[m//fmee
1
2M
pm
S exp
S.
2M
as was to be shown.
B.3. Detailed Balance of Escape Probabilities
The following 'detailed balance equation' for hitting times, proved in Proposition 3.1 of Betz & Le Roux (2016) for nonreversible Markov chains, will be useful. We reproduce the proof here for convenience.
Proposition B.10. For an irreducible, positive recurrent Markov chain X on a state space S with unique stationary distribution n. for all v; E S.
(())Px(Fy Fe) = < Fy).
Proof. For arbitrary S, holds that
Eg [Ta] Ex [min FyJ]] [= ( E. [miin +B,l > Fy).
Taking y in (7) gives Ey [min (7a, Ful Ey Fix P. (T < Fy), and substituting this in (7) with I, y swapped and y yields
1
EylTy] Ey [min TgJil Ex Tyl < F.)) (Eylfel E. FT < Fg)
(g)
(F)PP(FF < <tt)
xxx)P22FF <z)
(8)
Ey [T + EE [Ty]
by symmetry.
C. Perturbative Analysis of Metastable Dynamics
C.1. Quantitative Metastable Dynamies
We first show the following useful bound.
Lemma C.1. There exists 0 such that for all & E [K] and distinct states x, y E Cs. the unperturbed chain X satisfies
V
Pa(7 <
log M
Proof. From (8) it holds that
(* (. (T < +9)
(9)
Ey + Ex
By Assumption it holds that (v) (L/M)). Moreover since the skipped chain (XD (Xmm))22 is well-mixed,
Lm [mmis
Px 2 m) S sup
(1-
IP x
(X
Emiit m)) s exp
pm
min (1-1)
(2M
1=1
follows that
Ex 1
Σ
(T m)
<1-exp
P
O log M)
2M
and E, O
O(Mlog M) by symmetry. The statement then follows from (9).
16

---

Metastable Dynamics of Saain-of-Thouhhi Reasoning
To study the cluster transition dynamies, we begin with decomposition of hitting probabilities, which is closely related the theory of stochastic complementation (Meyer, 1989). Here, follow the proof in Betz & Le Roux (2016).
Lemma C.2. For C C ES,r S and y E C such that Pu(TE 00) 1, it holds that
Pa Px T6 =) pf (x, + Σ (T < +C)
PT < -5) (2
(10)
#EC=
Proof. If Xf; y. either X has moved directly from o to y or has first moved to XF -1 C. Conditioning the number of returns to z before transitioning to y yields
(X 6 5) (x,
Σ
ΣΣ
Pa(TT,
< X
sECO nzl
= pf
Σ
PT < Po < (F0
ZEC n21
PT Fo)
= - + Σ
1- P. F5) p (z.y),
SEC
concluding (10). Note that pf (I, 3) must be added separately even for x as the second term only counts returns to æ for time > O.
Definition C.3 (induced path measure). For m E N, define the path measure induced by X on S as
m
pe.m (f1mm)
II i=1
10 (1.( Fi.m E E 30 T.
Similarly to the total variation distance bound between product measures, we have the following result.
Lemma C.4. ||PS... p0.m l| I mdootE.
Proof. Recalling that (-1x)) - --*((=>>)lllllll (+1=)]l S donte for all x E S,
p..m m
p TV
pp (I1:m) - pum (
2
pf (x. (x II (I II 5'c
(xyllay-)
1 m
(x,(0))))) - (2
II
p (xyl-zy-))
2
m
< domn Σ
1 I (xylay-1)
=1'
m.
Proposition C.5. For all & [K] and = S O(M- M)-4), it holds that
PA < - (T < + 2ō
sup sup
(log M)3
v.vEC sES
and
sup sup P. P2
< < - (7
< + <ō
(log M33
a.yEC, #ES
17

---

Metastable Dynamics of Chain-of-Thought Reasoning
for all 0 almost surely for x; y E Ck. the above probabilities well-defined. We prove only the second inequality. Denote the augmented complements Chkiz := C U {z} and Ch....a : C U {y, z} for brevity. We divide the event { < f2) } according to whether the chain has been contained in Cs or has first hit some w E Chyy w + before reaching y. and bound the magnitude of perturbation of each term:
Proof. Since yy
PT <T = Pr < FCha)
E (ECCA(())
Px
WFy < Tg
(11)
ck..
For the first term, we exploit the fast mixing of X within Cs to show concentration result for Ty. then utilize the path measure perturbation bound. Specifically, for m chosen to satisfy (6), the inequality m I Fy < & implies X X for < m, so that
-
P < FC A m)) = Pa (m S < FC...) S Pf 2 m) < 6.
(12)
Moreover, define yy, to be the set of paths contained in C of length equal to m such that y appears, and first appears before any instance of 2, that is
Tv = fo E CF inf E [m] : 7 = v) < (m 1) A inf E [m] : n E c
It follows that
PT Fo.. A m) -pc.00 (T y,²)
and hence
[T < Tcr.: A Am) - PP < =0 A Am)
p y.x) pm (Ty,2)l
pa.m l/lll S mdoute
by Lemma C.4.
For the second term, by Lemma C.2 we have for all w E C {=}
Pa < Fon pf (u, w).
P. (XE. Ckiy.s
=w
(x, w) +
Σ
P. PulFoxnni 71))
uECAM(..))
The denominator can be lower bounded via path measure argument similar to before:
P. Pu(Fornx.
< -
Pu(Ty < F. A m)
2 P. Pu(Fo < + A m) - pp 50.m l
IP Fy < = P. PT( 2 m) pp5.
TV
mdout 2 log M
(13)
log
by Lemma C.I, long as 8, me o(llg -1). It follows that
2 log M
P Ck.N.
=) of (x, w) +
Σ (u,
and
Σ Po(XE
ck..
wECtMs)
Σ
(x, +
2 2oo M
Σ
Σ
pf (u,
WEC)M2)
wEC, \B.=) wEC
18

---

Metastable Dynamics of Shain-of-Thoughee Reasoning
(1 Mout log M
doute.
(14)
Now taking 8 = (Me log M) and s O(M -0a0-1(00 (log 4), verify that ò O((log 3))3) and
O Me 1
log M) =0 (loog
=0
log log M (log M/
ME
Combining (11), (12) and (14), conclude:
PT + (Tg < = S mddout + ô + Ollo M) dout& = =Ō(
=
1 (log M)3
as was to be shown.
As corollary, we obtain:
Corollary C.6 (Proposition restated). Any subset S. = [- ,Kk constitutes a metastable system for X the sense of (1) as M + 20.
c S of cluster representatives os E Ck
Proof. For y E C& \ {xx}. it holds that
PU(TS, < < <
2 llgg M
similarly to (13). On the other hand, for I& E it follows from Proposition C.5 that
Pa, (T3. < Ft) S P.,. (79 (.M
=2++00 (log MY3 (1ogM
and hence (1) follows.
Now let us study the convergence the perturbed stationary distributions. Let nF for 8 >> 0 denote the unique stationary distribution X on S. By the coupling theorem (Meyer, 1989, Theorem 4.1),
T = (ÉITf
{KTK)
(15)
where the coupling factors Çn. = (Cx). We then obtain the following corollary of Proposition C.5. Corollary C.7. For all k E [K], it holds that
sup #EC₁
xz:
log M
We remark that compared to the straightforward perturbation bound in Proposition B.8, this approach does not require reversibility nor an explicit condition number bound.
Proof. For all x, y E Ck. by Proposition 1. applied to X S and X on Ck.
(x)
Py F
(a(x)
Py 79)
T
PA(FE Tg)
(v(
PT(70 70)
Recall that P2( + 2 log M by Lemma C.1 and moreover (.f =5)) 2 2 2 M by repeating the argument in (13). Therefore,
(x)
[x)
(f < )
TH (v)
(v)
Pz(75 < TE)
P Pa 70)
19

---

Metastable Dynamies of Chain-of-Thought Reasoning
Pxy < F - Pa < + Pa < - ( < [
Palty (o) < +
4(log 2)
1/2
(log M)
By Assumption 1 we have that jou (V)/ (x)) is bounded for all x, y E Ck and hence
T x
(x)
Me (v) - m
[ (x)
(z)
ECC,
(k(())
(a)
(c(xz) (x(y)
Σ
(x) (T(
00
(v(
log M
EECa
C.2. Perturbative Analysis of Metastable Chain
We proceed study the behavior of the meta-chain X with transition probabilities of detined in (2). It can be shown that X asymptotically reversible with respect the measure induced by nt: Proposition C.8. For all k, l [K] with l + é it holds that
T (Cn) = =1
(CC
log M
Proof. First note that for x E C2. E C2 with k + e, by Proposition C.5,
P (5 y F
0 1
P F2 < +f)
Σ P2 < Fh X5. = =t) < T5)
(TO
sEC
1
Σ
Pa(to, < frr f
X =) sup P. < Th) P < <r:)
P2
< 7
zcc:
sEC,
5 (log Mr
By the definition of gf, the coupling equation (15) and Corollary C.7, it follows that
* (CAAg((Ca))+) = n (Cx) Σ (x < +
DCC₁
= (Ck) Σ (=) < =
xECk
Σ m2(a)² (1-
(1= Mx(x)
[x(1)
n (Cx)
Po <5t)
xEC
Σ (o) + (G
log M
C
We expand the first term further as
Σ x (OM =9))
ZEC
Σ TEOOOMOEEE
< <F)
20

---

Metastable Dynamics of Mhain-of-Thoughe Reasoning
(() < xx) ( DECh NEC₁
P Fo 72)
Σ
Σ
PT < f5)
Σ
Σ
( <T))
=EC₂ BEC,
Σ
(F -
(log M)3 (1og
+
C
Together, we have shown that
E Σx [OOOMOONRPE <F)) (1+0 (1+0(1Z))) (-1)
log (1)))N)) ))
+CCL) zECx yEC,
and by symmetry
E E FO)AEEMRRB (100
1 log M
DEC DEC
Finally, since
ΣΣ px(x) (C))L <F)
Σ #EC& VEC(
( 55))
R yECx
due to Proposition B.10, we conclude the desired statement.
Together with Assumptions 1, 4 and (15), this immediately implies:
Corollary C.9. For all k E [K] and x E S it holds that x (Cx) O1/K) and Tf (x) O(1/KM).
Moreover, (-([Ck) serves as an approximation of the escape probabilities from any x E Ck2 weighted by the stationary measure.
Proposition C.10. For k, l E [K] with k # it holds that
px(x))== < 7e)
sup xEC,
Ck)
0
log M
(16)
and
pa (x(x) (75 < 71) ti Ck)
sup CCCR
δ
(17)
log M
Proof. Similarly to the proof of Proposition C.8, for any y E C2 we can successively transform via Proposition B.10:
(x(x)Pa(Fé, < (R(T)P ( < ;
(+Ō
log
(x) P. PT <
1+0
1
(C(k)
log M 1
(1)
(1+ō)
P < 7
(CCk)
log M
(Ct)
1
(Cc))) (T() <
log
Since the last term is independent of we also have
(C(C)(Ca) = Σ (a(c))Paato,
<
21

---

Metastable Dynamics of Chain-of-Tine -hhoughhtT Reasoning
(C() (=(c P <
110
log M
= px Po - (1+ Ō
(1+0
1
log M
for any x E Ck. verifying (16). The proof for (17) is identical.
As corollary, we obtain the promised justification of Assumption 4. Corollary C.11. there exists sparse edge from Cj Ct, it holds that of (C(((())) (te/MM)
Proof. Fix x E C& and let (y, 2) E with Ck2 Ct. The event (Fc. + and the edge to is immediately taken, so that
occurs if y is hit before returning
PT < + 2 (2ly))
(T < 2
V/2
2 log M
Hence by Proposition C.10 we obtain
(CelCA) (x)
<tt)
1++
20 Ω
log M
M log M
C.3. Hitting Time Analysis
To prove Theorem 3.2, we first derive the expected escape time of single cluster.
Lemma C.12. For all le E [K] and x E Ck. it holds that
M
E Ex =
Proof. Recall from Lemma B.9 that the mixing time of ki, is fmix Olog M). Also denote the set of states in C₁ with
outbound edges as D3 := {x Cs By Ck (z, v) E E.), so that S [D&] S Yoout By Assumption 2. Since Tēq > m
implies that X = X for S m and that sparse edge was not taken at each state of the skipped subchain k, == [m/tmix]] it follows that
Gmxe up to
[m//hmix]]
PT > m) S sup
Pxe (t- 1942 (X X E C+)
[m/tmix]]
sup
II t=1
(1- Pxx maix 11-1)41
(Eke Emict D&) PP spu (xhe
tmxt+1 & Ck))
[m/[mie]]]
(1- D
II 1=1
CE
2M
posm
< exp
2M
This yields the upper bound
E2
Σ m==
P. (T m) < c1-xxp (-
22Mtmix
PeE
M log M
For the lower bound, consider the partition of (X ) into the union of skipped and shifted subchains (h (mmiet+))s w220 for 0 < u < mmix. Suppose that m 2 21mixe so each subchain has length at least 2, and all transition probabilities of each subchain is (L/MM) by Assumption 1. Since not taking a sparse edge at each step of all subchains implies Tég > m.
(T > m)
22

---

Metastable Dynamics of Chain-of-Thought Reasoning
Imxx
[n/emee]
inf
P Skie fmis (t- altut1
(Xtiee
Aminttu Dx) piie (X tunt & Cx) miiettu
Laii
[m//muxx]
[D&l
doute ))
1-0
1
M
m--mis
Note that while the dependency on mix does not explicitly appear in the bound, mmix still needs to be small enough to argue that the states of each subchain for t 2 1 exist and are sufficiently mixed. Hence it follows that
M (M)
M
Eg Teg
Σ m=0
PT > m) 2
2mmix 2
which concludes the statement.
Theorem C.13 (Theorem 3.2 restated). Under Assumptions 1-4, holds for all & S 6max == O(M- M)- that
KM
E ((m ) [xx xxmll]=
Proof. Suppose X E Ck Xout E C2 with k + l. For the upper bound, by (8) it holds that
E x [T
Ex E1 [xomn] S Ex [x + Exout [xxm_]
T T= (Txmm < <Xxm
Combining (15), Corollary C.7 and Proposition C.10 yields
T (Xin)
n (Ck) #Ckk) tt (Xin) (7x... ==
p4 14x Xin..xx.. (Fxmm (xmm)
M4 (im)
T (CW) (1+0
(10g
(log M )
= =0 ( (KM)
where the last line follows from Corollary C.9 and Assumption For the lower bound, define the sequence of increasing stopping times (a.)n20
σ = O, on == min > an-1 (Xf-,,Xf) E E.).
Then defining the minimum number of cluster transitions to reach Xout as
N = N(Xins Xout) m n E, Xo Xiny Xy Xout, (X,-1, X,) E E VI),
holds that x.m 2 NN. Moreover denoting the cluster containing X as C(t). by Lemma C.12 we have
N Σ
MN
Ex,, [aN]
E Ex
2 2
and hence
KM
Xom Xom Nout 11
θ
since E[N]- = (2(K) by Assumption
23

---

Metastable Dynamics of Chain-of-Thouuee Thought Reasoning
D. Proofs for Optimization Dynamics
D.I. Analysis Pretraining Dynamies
Theorem D.I. Let Xg ~ Unif(S) or Xo ~ nT and X ~ pf (-1Xo) be random from the Markov chain X Then:
(1) The sequence of gradient descent iterates (W(1)) for cross-entropy loss
Lpre (W) X |- log Pw Pw (X1[Xo)]
with initialization W(0) -0 and suitable learning rate converges with respect to the learned transition probabilities as
sup 151J5S
[P
(T) pigl
=0
KM2
log
KT
(18)
ME
(Th) (2) After Ti = O(KM steps, by setting Wij + -0 Pij is below threshold CthresE it holds for the resulting model p that Paj = 0 iff pf, = 0 and
Pij (E s Pis S Pt P o(1)
(19)
holds uniformly for all such that Pig +
(3) After thresholding, the learned transition probabilitiees converge linearly as
(T++T) - pigl exp -xp((((s3T)) O(loge
sup 1SiSs
(20)
Proof. For part (1), we utilize the proof technique of Ji & Telgarsky (2019), Theorem 3.1 for logistic regression. Suppose Xa ~ where is any distribution such that @ K M) for all states i. If === x², we will show that (x) (L/KKM) for all æ E in Corollary C.9. The categorical cross-entropy loss can written as
Lepro (P) =
(X1]Xo)] = Σ (W.))
where
L.WW)) - Epj wiywey + log Σ exp uij.
Note that each L is convex and
inf L. = - loggls H (-le:)
the entropy of X1 given Xo = c₁. The gradient of L; is given as (VL,), = (w(ee)es) Pij. Since the softmax operator is 1-Lipschitz, it follows that V L, is also 1-Lipschitz,
oxp
[V.(W..)) - VI, W 1
Σ 3
exp Wij
< W,, 1
Σg
exp Wike
Σn exp Srpwiaa
Choose the learning rate = O(KM) such that S pm7 S for some gradient descent with respect to Li,
> 0. Then rewriting gradient descent of W s as
L, w (++1) w! L... w mM) L. (W!!))
we have the well-known guarantee
(w((+)) (1+1) < I (w!!) 70 | (W!)) 11
(21)
Define the reference matrix Z E S| componentwise as
Zij == log
(1 -
p +1) +1) 8
8)|5|
24

---

Metastable Dynamics of
Reasoning
for 0 > be determined. It holds that
(1 8)]s
2 Pig + 1 s (M + dout)
log |S| 2
1 1|
Σ
log
j-P >0
and
(1 - 8)151
(1 (1- |1=5) (1-b)1S)
Li(Zi.)
Σ Pij log
Pij + 1
+ log Σ
Pij
+1)
--E Piy log
ΣEs
(1- (1-d)pf) +
5
[S]
Eps
pij log log
- E Diylog log 1 8
< inf Lg +
S5/ v8)
owing to the inequality - log(1 2² 2/x| for small x and the bound pf when pt # 0. Moreover, from the convexity of L, and (21) we have the relation
( (++1) - Zi-1l -/W!! Zi+
- w Z..) + +[VL:(W(
S (Z. L, (w.))
+ (L((W!.) L (W(!
Summing over t = 0,... , 1 and rearranging gives
L(W (w
< (z.))) + (:W)
W (0)
Z,, 112
W (T)
Z
nn
2T
(Z..) + log |S|
11:..
7a
2T
(1
8
M + dout + no
|S| 8
)
inf L1 +0
V8
loo
|S|
2T
Since |S| OKK)), by taking M/T if 2 1/KM and 5 KMP // 1/KM, follows that
KM²
KT 2
L ((W inf L 0
log
T
ME
uniformly for all i. Again by applying (21) we obtain the bound
(VL(( )1 s
2 (L,(W()) w!f- S
2
[I, (I.(W
inf T.i)
N7u
77u
Since
Σ
(ewen)eegess) DE,)2 [VL.(W
this concludes part (1).
For part (2), by running gradient descent for time Ti = Ö(KM2 steps, the bound (18) ensures
sup
1p
(Ti)
- płyl = o(E),
(22)
25

---

Metastable Dynamics of Chain-of-Thought Reasoning
and in particular P.j o(e) if and only pf
Hence defining the thresholded parameter matrix
W E RISIII8I
Wij
-00
(Tt) otherwise
if Ptj Cthres
(Ti)
w
the corresponding softmax scores Pij for all j. & such that P.j. P.kk do not change before/after thresholding. Define the D, = {j E [S] Pij 03 so that [Dy] S M + dout and
pw+ (eyle) are affixed to precisely zero. Moreover, note that the ratios p.j Pty/Ptt Pat
Pij
(n)
Σ
(11)) Pig
pigl S (M- + dam))(ss)= o(1)
JED,
JED:
Therefore we have for all D2,
(T))
P ΣKED, Pik
Pij
(T)) (1 o (1))
( 25 2,208 2
ΣXED Pik
and by comparing with (22) we obtain the desired bound.
Finally for part (3), we utilize the strong convexity of L; on a bounded domain. We treat all entries set to -oo in part (2) as nonexistent, so that for example min; pfy 2 es > 0. Then there exists a set of logits W such that ýw- = pfyi as adding the same constant to all entries in a row does not affect the probabilities fw- we may assume the row sums of W are
equal to W so that (W* w+)1= =0
The Hessian of L; is equal
V L, (W.) diag PiaPi.
and has zero curvature along the direction We claim that in all orthogonal directions (1)+, V is ((t2)-strongly convex. Indeed, for any vector such that ||o||| and 0 and any & have
(Envr) --2t 2t Σ
E -1²
Pijuy +1 min Pij
since nyt $ 0 for at least one j. Then the discriminant must satisfy
2 {nows) mesuss )
{Inestt) iesstt (1- min 11-minns) pis) 50,
Σ
so that
v T Wi.) = Σnno (Eanrs) Bisos 2 EEnnn min Pos 2 min pi
which is O(? due (19). now follows from classical convex analysis that
| (T++T) pf.ll < | (T++)) W
< (1- (( | w
= exp((S((E²T)) Ollog )
where we have again used that softmax 1-Lipschitz and the effective learning rate pad = O(1).
26

---

Metastable Dynamics of Chain-of-Thonn Thought Reasoning
D.2. Analysis of Search and PPO
We first show that the initial cluster exploration phase of the search algorithm is consistent.
Lemma D.2. For each outer loop of Algorithm 2, after To steps, Ò returns the cluster C₁ containing Xo with probability
1 1-K(K33)
Proof. + Cs implies that either some state E C₁ has not been hit by some X by time To, or all chains X have reached some point outside Cg at time To-
Denote the hitting time of C' C S by X as TC n.
Since K S poly(M), by Lemma B.9 holds that
(x, n To) S
Vy E Cx
MK2
by choosing To 2 (log M) Union bounding over y, n gives
log K K2
Fxo max max Ty > To S MN (T > To) S yEC= nSN
Moreover by the argument in Lemma C. since each X is independently generated from pf,
Px, max
nh. S Too
S Pxo
(ThE Tch
To
N
26
N
1 O
M
Toe
S exp
-N exp
-Nexp
-0
M
S exp( NN/2) S K-2
by ensuring that 2 4 log K. Hence we have shown that Px, (Ò + Cx) 1 2(K-2).
Proposition D.3 (Proposition 3.3 restated). PRM mode of Algorithm 2 returns M, Eg with probability Õ(1/K).
Proof. Denote the set of outbound edges from Cj as E. == {(I,)) E. I e Cz. C so that E& S nout dout and fix (x, y) E E, The probability that fixed rollout X1.E takes the edge (ar, y) and terminates within time Tmax is bounded below as
31 < Tmax X xx xx, X! =
Xo
Tiua
1.8 2 t, X11, = x, X,e = y) Px, TCE
1=1
Tiax
Px, (Xtee 1-1 x2) xa (TOE 2 (v/2z)
Le
t=1
Taax
P 1 (1- ((1))
t-x +EE)
2M
M
mix
(
E tmix
| (1-(1- (1-
E
Tinae 2tmix +
2 1 θ
MM
M
2 exp (-0
log M
))
eexp (-o
T (Taax
exp
2 C,
M
M
for some positive constant c. Therefore by union bounding over all edges in Eg.k.
Px, (É # Ead)
Σ
Px, (#t Tmax x/1 2, X1 = y)
(2.
27

---

Metastable Dynamics of Shhin-of-Thougt Reasoning
- (1 <0(1/²2)
by taking N/ log K suitably large. By union bounding again over all R = ( log K) iterations of the outer loop, the probability that the inner loop fails return the correct set of sparse edges for some iteration is at most ((1/K) Finally, the probability that some cluster will be missed during the It iterations is bounded above for suitable choice of R as
K (1 ((1KK) < K exp (-0(0/0((/)))) & (1/KK)
Thus with probability 1 - (1/K) - (11/)) -(1//) all clusters Ck will be explored and the correct set of sparse edges E will always be added to M,. so that the final output satisfies M, = E.
We now prove the convergence of the PPO-Clip algorithm.
Proof. As in the proof of Proposition 3.3, we condition on the event that the correct set of sparse edges is returned for all clusters, and focus single cluster Ck- Again write pi (ewr(eeyee) let Xo ~ l where μ4 ((KM) and denote Da,, E [S) (1,5) E E.) C D.. The objective LPPO reduces to Liec, pily where
(ww(ssle)) Pij
} Aleire))= Colip )
L (W: A) = Ene min
Σ JEDA.
min(fw (eyles), Celip plz..
We will show inductively that either pw (ewleeee) Celip Pij for all j Da,i or (ejle)) 2 Gelip Vig for all j E Da while running Algorithm 3. Assuming the former, that for all j E [S].
(i)
aL; (w A) dwis RED dwy
Σ
(1)
d
exp Wik
Pik
dwys ke keD E. expw
exp (1)
exp (t)
exp Wiy
= =1oEDo.st
Exxx exp w
12
AED
= =P(
Σ Pik
DED
This implies that dls (W(1)) A) if and only jf E Da.i, so sign gradient ascent gives for each the update rule dway
1++1) wig
w + pia
jE Da.i
Wiy pia j $ Da.
In particular, the relative magnitudes of ply for all Da.s preserved starting from Ptj ply, so that the carlier (tt)
(0))
(8) assertion is justified. Furthermore since Pt o exp w!y for all j. we can derive Pij from p by directly multiplying edu
(or 2u and 1) and normalizing afterwards.
(1) Pij
(2uitt pis
E Das
and
Pij
(0)
Pij
(t)
Dig
j E Da,s
Σn
Pik
(1))
By choosing Celip = (1 - o(1)) max & so that
1
Emax
T =
log(1 + o(1))Caup =
log
2p,a0
24²aa
we ensure that gradient ascent has not yet terminated (reached the clip threshold) by time T; and also p < Emax for all j E De..- This implies
1
Σ
11) P3
1 (e2paat 1)
Σ pl $ (2ttat - 1) S 1 0(
JED...
28

---

Metastable Dynamics of Chain-of-Though Reasoning
Thus Pij (1 o(1) vi = vi where e' (1 (( for j E Da.s- Moreover P for all Da, decrease proportionally from pig so that they also equal the corresponding Píş values by Assumption 2.
Now if we take Tppo = max; Tú then this will hold for all states e, in the initialized cluster Cj as each row will stop updating after time T. Finally, since the values Piy for 6, in a different cluster do not affect the above derivation, we may repeat this argument for all explored clusters to obtain the guarantee. We remark that exploring the same cluster multiple times does not affect the outcome since the clipping operation will prevent the weights from being updated from the second time onwards.
D.3. Analysis of Distillation
Lemma D.4. (Yo, Y1) Ddist distributed as Yo n², Y1 ~ (5(((16) where
( := Th (xxx) (Xig. = =x)), k ktb.
(. (Tn) == 1 -
k 16 (zel
Proof. The Yo component of Daist is clearly distributed according to n², Consider samples such that X E Cc. in which case ( Iy and X; x. X; # Tke then y - Zg. X 2k, the following state y is the next return of X to S., so that
P Po (V = x2) = PP Pr.0 1o (y = It, X; = vk) = (x Pa,, (X =xe)
holds for all + k. Comparing with the definition of 4e, this shows that Y1 ~ g6 ()) for (Yo, Y1) Ddist-
Proposition D.5 (Proposition 4.1 restated). Denote the return time of Tf to Fyk as Fo For all k l [K] with + E, holds that
Par, (F < FTo = -1+ log M
Ck)
We remark that the asymptotic version of this result is Theorem 5.3 of Betz & Le Roux (2016). It is also shown that this is the best characterization of the metastable dynamics, as the transition probabilities of themselves cannot be made to be independent the choice of representatives S. even in the asymptotic limit.
Proof. Applying Corollary C.7 and Proposition C.10 to the representatives Ik: Te of Ck Ct gives
PF( ( < Fre
(C(Ce(
log M
Considering the numerator, conditioning the event { < Fax on the first return of X to So, we have that
P.u (Té, < F Pas (X= xx)+ + Σ Puy (X. 12o Em P (F F
m
and multiplying both sides by कं (IFx) gives
(x( (Fe. < = (x
+ Σ (x ( ) am (Fe, < F.e). m
Now note that of is rescaled version of X reduced to S. where only the diagonal elements (z))/2)) have been increased and all other elements have been decreased proportionally. It follows that P Pa..(F < 75 = IP Pam. (Fó < Fo ) for all m + k. f. Therefore applying the same argument to the chain of we obtain
(xx) (F < F of (z)lZx) +
Σ (l (Fe Forze) mzkkl
Pag (Fo < )
concluding the proof.
29

---

Metastable Dynamics of Chain-of- -hoougghth Reasoning
For the convergence of the distilled model iz. first show the following.
Lemma D.6. Under Assumption 5, for any lo + L, (((xe(a)) = (c=/M) if there is a sparse edge from Cs to Ct and Le (mel(a)) otherwise.
Proof. If there is no sparse edge from C Ct, the first return of X S. starting from ag cannot be tt, since X must
first travel to different cluster Cn A Ce to escape Ck where it will inevitably hit In- Thus Pxy, (X 500 xx) 0 and Ef (z) 0.
Suppose there exists a sparse edge (x', xz) where x' Cg. Note that
(xel(m) S (Zx) (F < F - (CelCC) (1+Ō
) - O(E/M)
1 -O(//M)
log M
by Corollary C.7, Proposition C.10 and Assumption 4. Moreover letting I Ze be simple path with positive p¹ -probability in Ck. it holds that
(x 2 o (2x) (T ' x1)
xz) 2 (c/M))
proving the assertion.
The proof of Proposition 4.2 then follows by repeating the analysis of Theorem D.I, replacing dimension |S| by K, the maximum number of outgoing edges M + dout by the number of sparse edges dout, and the probability lower threshold (c)) by (c/M). The learning rate r) = ((K) is justified since P(Y. z*) x² (Cx) ((1/K) by Corollary C.9. This results in a convergence rate of Olog KT/T)) for the initial stage and exp(- ( after thresholding. The details are omitted.
We also require the following dynamical properties of g. Lemma D.7. The stationary distribution Tद. of g. on S. satisfies T5(xx) = (1/K),, moreover, Exg [T. = O(KM/E) for all k,
Proof. By Proposition B.10 and Proposition 4.1, we have that
n. (xxx
Pr (To,z < Fo.e))
(C+(C)))
log M )) =1
)
1+
O(1)
T5 (20))
Par (76,z1 )o,
(C(
due to Assumption Then each m (Ixx) must be of order 1/K. It further follows from an application of (8) that
KM
Egg [T
+
[f(#x)P ay (Fo,as
Fo To
E
Theorem D.8 (Theorem 4.3 restated). For all lo + âz (2e (1) if there exists sparse from Cj. Cş or 0 Of not. Moreover, the hitting time T of xg E S. by 9z+ satisfies Ez, [T O(K).
Proof. The chain of can be retrieved from qz+ by making it 'lazy.' Indeed, note that âz is computed from the distilled model of as
e (g((x)((N))
e k,
g8(xx + ed Evsr 18 (ee(())))
izz (ze(
(6(xx| (T
t= k.
g5(xx/2z) + の Ee 85 (Ze(zx))
Since the sum the denominator over at most dout + nonzero terms, by choosing e = ((M/E) we ensure that
dz (xe(=*) = (1)) for those terms that are nonzero. Conversely, by viewing the logits of of as obtained by subtracting
30

---

Metastable Dynamics of Chain-of-Tine Thought Reasoning
from Z have
p qzz (21g (Tnk
+ k.
Oz (2t)) (2))
e Eerge Oz (Ie(
(x(()(1))= =
iz. (Ih (2k)
e= k.
izz ((nl(RR) - EB yt 1z+ (1))
This may be expressed as
o (x(2)(11)) >x + (1 >x )x)d
where
-
(6(m)(nx)=O(eM))) Oee/M). E'
Σ
@z 226) + Eese 9z+ (re (xx)
Hence o is equivalent to the lazy chain obtained from 0z by inserting additional self-transitions of each 2y with probability is larger than Er, [r by at least factor of ming x (MMM/)).
1- Ag. It follows that the expected hitting time Er, [T Comparing with Lemma D.7 proves the assertion.
E. Proofs for Hardness Results
We first review the definition of group action.
Definition E.1 (group action). Let (G, o) group with identity eg and R any set. G is said to act on R (from the left)
there exists map G + R (the group action) satisfying the following two axioms:
(1) (identity) eg
for all r R.
(2) (composition) 91 (g2 r) (91 o 92) r for all 91, 92 G and r E R.
It follows that the map g is bijection for all g G, with inverse r g_l.r.
E.1. Proof of Theorem 5.2
Let P' C be such that IP'| SPA(P, I). hp are pairwise orthogonal and Ip are equal for p P', This ensures that (I)) is independent of p. Choosing p uniformly randomly from P', the variance of the gradient of L with respect p is computed as
Var, (L(0:p) min Ep (- (-2 Sor f0) u)²]
I E, [4(V fer 11, [3]
4
Σ
fo. hp)
|P'
PEP
V
fo
74
< 83.
|P'
It follows from Chebyshev's inequality that for all 0,
P ((IVL((0))) (( 20.
Thus all queries L are adversarially corrupted with to return E,[V L p)] when (() E < the n successive queries will not reveal any information on the ground truth p with probability 1 nă by union bound. Hence after running the algorithm, the loss is bounded below by the random guessing error with any fixed f. Noting that replacing So with fo(x)= max(ming (f()) 1), -1} does not increase the loss, it follows that
E, [T(O:p)) Ep [l]b Fol1
+ fl 2Rp [hhp Form]
31

---

Metastable Dynamics of Chain-of-Thought Reasoning
+
1
2
Σ
hps
fo
|P'|
DE
H
+
f8
hp
1
Σ
(ppstep'
P
PP'2
pEP
P.P EP!
2
|P'
uniformly for all 0.
E.2. Proof of Theorem 5.3
Note that SDA(P;; P) is trivial. We give three constructions realizing the lower bounds in order of strictness of the additional information constraint.
Lower bounding SDA(P; Ø). Suppose p = pf is any kernel satisfying Assumptions 1, 2 and D is any distribution satisfying Assumption 3'. We first analyze the case where the lower bound of Assumption 3' is 22 K) and M 2 9(K), since the proof is slightly more involved. Let sk,1, SR,(C%, be labeling of all states in Cj such that all nodes with outbound sparse edges are contained in the first nout nodes. Define the quantity
minKeR K |Cxl OMM)
q =
Rout
For vector Z define the corresponding permutation of S (also denoted by v) as
v(*k,) =
8k. litt
mod gNour 1 S i gToout
8k,
qoutt
< S |Ckl-
That is, the first Mout states of C₁ are eyclically shifted by ux-multiples of Nout and the remaining states are left fixed. Denote the pushforward kernel of yf induced by v as
vp (y|z) = (y)lo
is clear that uyp P for all v, moreover, Assumptions 2 hold when replacing E, by E, (vpp") since only permutes states within clusters and does not affect the sparse structure.
Lemma E.2. Let dh denote the Hamming distance on E For any two v, v E 2 holds that
[E((upf) S dout
and
(u(pp)) E. (c(p)) < nont (K d
Proof. Suppose for some x E Cr. y E C₁ with 1: + we have (x, y) E (u(D))). Then v (v)) E E,(p) so that u (x) = sk,i for some 1 < i S nout, hence x = v(Sk.)) = Sk.itug If at the same time (z, y) E (x(pp)) must hold that sk.i+opnou 88,s+0 nout. and so k must satisfy e* = v/-- There are exactly K - dn (v. r') such clusters and at most dour sparse edges leading out of each cluster, concluding the second bound. The first bound follows from the second by setting v'.
We construct well-separated subset of z via the Gilbert-Varshamor bound.
Lemma E.3 -arbbrr-Varrsamov bound), The maximum size Ag(K, d) of a code of length K over an alphabet of size q with minimum Hamming distance satisfies
Kk A₂(K,) 2 Vol, (K, 1) dk)
K (q 1)².
0
32

---

Metastable Dynamics of Soain-of-Thoughe Reasoning
Moreover for E [0, 1/g] it holds that
(ol,(K,<K) - qH
where Hy is the q-ary entropy function
H₂(T) = T logg (g 1) -
1og,, 7 -loog 7) log, 7)
While the classical bound only guarantees the existence of large subsets with linear (at least K/9) overlapping bits, obtain better separation by scaling q (equivalently, .M along with K. In particular, choosing the relative overlap as (log g/9) (note the use of the natural logarithm), we obtain:
Lemma E.4. For C 0,
log // (Cq) and sufficiently large q, it holds that
Ag TK) 2 29 204 K
(23)
Proof. Using the inequality 0 S x - log(1 + +x) S x2² for |x||
1/2, we may bound
Hr(T)
1
logq
log, (g- -1 - 11 log g
log,
log
log q
logg
log
Cq
Cq
Cq
Cq
Ca
log log q
logC
1
logg
(1
log
))
+
+
log
Cq
Cq
log4
Cq
Cy
log log q
log
log y
(log g)²
+
+
+
Cq
Cq
log
Cq
C²
log log 4
S
2C9
for sufficiently large The statement follows from Lemma E.3.
Now denote by V c k the 7 -sepaaratee subset of size TK),, For any distinct v, v/ V. by Lemma E.2 we have g
log
Ex(epp) Es(upp)) S nout (K [K -K) = nouudoou
K.
Cq
On the other hand, it holds that
Miggr (Xiny Xout) n Eu(up)) = Mpp (x ((Xox))) E.(r)) 2 clog K
due to Assumption 3, and similarly for v'. Since M 2 eK, we may choose C' a large enough constant so that
C Noutoout
K llgg
q log K
Then since
Mayp (Xins Xoue) n Es (oyp')) Migne (Xins Xout) n Es(ppp |E((upp) (r(pp))
must hold that
Maga (Xiny Xout) (s(vy)) Magpr (Xin; Xout) n Ea(obp").
Without loss of generality, we may suppose there exists a sparse edge ç = (X,-1,X, of upp that is included in the left-hand side of the above but not the right. Since A(E) included the computation of r A.ugp along Mogr (Xins Xont) but of A.. along Moier (Xin: Xout), denoting A := Alsxsvie) follows that
(Bugp", Dufpr)) )'
= -Ex Nouird Mbagpe (Xiny Xouts Alhuggo (Nins X Xouts A))
33

---

Metastable Dynamics of Chain-of- -hoough Reasoning
Figure 2. Sparse edge construction for the no-search scenario. probability e.
The circles represent the original dense clusters. Dashed edges have
Em. Xout Φ o oa (Moppe (Xi,, oout)) o Anng (Migns (Xins Xout))
Xmm EACESLA- ( A.v (Mugpe (Xims Xout)) Φ r.nuge (Muger (Xins Xout))]
Adopting the shorthand glA- g if A holds and gla EG if not, may write
T' (Mugge (Xin, Xout)) = (AL A(Xi-1, An) (Xin)
where
Al =
..... o (X.
Ar =
2.Xe (HEF)) o... A(Xu, X1) ((x.))))))
Since - Xt) is uniformly distributed on G, the composition Ar. A(X,-1, x,) o Ar is also uniformly distributed on G conditioned on A note that this step relies crucially on the existence of left and right inverses in G. Hence
E AEEEAA [ o r'A.pp (Mogge (Xm,; Xout)]]
for all Xins Xours AT, so that (Brgpe hager /M O. Thus the subset {hrope : v E V} of H. orthogonal with size least
Ag TK 2 q
log Jox 201
2 A-llog log K)
if q = O(K), which grows faster than any polynomial in K. In the case that g/ K + 0o, we may choose a smaller o' = cK at the beginning to obtain the same lower bound. Therefore we have shown that SDA(P:0) 2 K=(1),
Finally, if the minimum length in Assumption is instead set to scale linearly as cK for some c < 1, it suffices to set
C' 1 and choose y (equivalently M) a large enough constant satisfying
log <c
nout
q
to apply the same argument. Then the lower bound (23) becomes exponential in K.
Lower bounding SDA(P:M). We take an arbitrary kernel p E IP and make the following modification, pictured in Figure 2. Each sparse edge (z, is replaced by set of states = x, øı, ..... 2q-1: Rq such that each neighboring pair zt, 21+1 for & E Z. are connected to each other via bidirectional edges of probability O(1). However, one specific pair žt, Ze+1 is to be connected to each other with probability e. Denote this index by Uy where j E [J] numbers the set of directly connected clusters; it holds that E,, O(K) by Assumption The points 2, for t S by and for > Uy appended to the clusters containing and y, respectively. Since this is a bounded number of points all connected by constant probability edges, the extended clusters are still rapidly mixing. Then each vector (v,) E z determines kernel p. P. and
[p(p.) n E.(p:)) = 2(J
holds for all v, of E Zi-- We now repeat the argument from before to show orthogonality: by Lemma E.3 there exists a T ---spppareeed subset V c z of size (J, for = 1- - log g/ q, and by choosing g large enough we can ensure
2 2
[M. p. (Xm, X n E.(ra) ) 2 ck
J [E(pe) n Ex(p:))
q
34

---

Metastable Dynamics of Chain-of- -hhoughhtt Reasoning
Figure 3. Graph construction for the local search scenario 2). Dashed edges have probability e, A local neighborhood of maximum distance one from the original graph is shown in the dashed box. which the learner is assumed to have full access to.
The key aspect of this construction is that the support of Pe does not depend on as only the position of the sparse edge among candidates change with v. This implies that querying the path Mp. (Xin Xout) (and indeed the entire set of edges) does not reveal any information about the ground truth v, and {px : v E V} satisfies the conditions to compute the SQ dimension with access M. Hence we have shown that
SDA(P;M) 2 (J, 2 AKK)
Lower bounding (Dd((M) We construct the graph depicted in Figure 3 as follows. We start with nK clusters of size M laid out in side by side and connect neighboring clusters with bidirectional edges of probability From all states extend a 'rod' of probability (1)) bidirectional edges of bounded length (the vertically arranged states, here r = 2), similarly to Figure 2. Join the endpoints of all rods originating from each cluster into a single 'endpoint' state. For D, we assume that (Xin, ) are sampled only from the original clusters (bottom horizontal line states) and Mp only returns paths along this line.
Choose size K subset B of the low probability edges be sparse edges, viewed as subset of [nK]. For each of the edges (z, v) not in B, identify the endpoint states of the clusters containing æ, y. The identified clusters will merge into single larger rapidly mixing cluster, so that (x, y) is indeed no longer a sparse edge. Denote the resulting kernel as pg. We have the following intersection constraint bound:
Lemma E.5. For any 2 5, there exists size (()) set B of size K subsets of [nK] such that BB n B'| S cK for all B, E B.
Proof. We construct B via greedy algorithm similarly to the Gilbert- Varshamov bound. Start with B = Ø and add any B C [nK] of size K not already to B. Each new element blocks at most
K ck)
nKK ck
cK
elements from being added to B. Hence the maximum size of B is at least
nk K
K
nKK - ck) K ck
(nk)
K
2 O(n
01nKK-1/3)-2 K-1/2)
2- 2(K)
cK
K
ck
f n 2 5.
Then (PB))) (F BB S cK and we can repeat the same argument to show orthogonality. Furthermore by taking 1' sufficiently large, the local neighborhood of any path contained the bottom horizontal line (which must be contained in the dashed area in Figure 3) is isomorphic for all B B, since it cannot query the endpoint states identify which clusters are actually connected. Hence (pp B E B} satisfies the conditions to compute the SQ dimension with access to (bd, and thus
SDA(P;
> B R(K)
35


Reviews:
[{"review_id": "N5oW71EMJq", "reviewer": "Reviewer_QuhA", "summary": "This paper develops a theoretical framework for understanding chain-of-thought (CoT) reasoning in large language models by modeling it as a metastable Markov process. They prove that implementing search protocols that reward sparse edges improves reasoning by decreasing the expected steps to reach different clusters. The authors show that a compressed metastable representation of the reasoning dynamics can be distilled into a smaller, more efficient model that preserves essential properties of the original chain.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment of our contributions! Regarding the simplicity of the Markov model compared to actual reasoning, please see our rebuttal to similar weaknesses pointed out by Reviewer R4eB.", "claims_and_evidence": "The claims in this paper are generally well-supported by mathematical proofs and theoretical analysis.", "methods_and_evaluation_criteria": "The paper is entirely theoretical with no experimental validation.", "theoretical_claims": "I check several key proofs including Theorem 3.2, Propositions 3.3-3.4, and Theorem 4.3. The proofs appear mathematically sound with no substantial errors.", "experimental_designs_or_analyses": "The paper is entirely theoretical with no experimental validation.", "relation_to_broader_scientific_literature": "-", "essential_references_not_discussed": "-", "other_strengths_and_weaknesses": "Strengths:\n1. Proposes a theoretical framework that combines Markov process theory with language model reasoning, providing new insights into reasoning challenges.\n2. Provides principled explanations for empirically observed phenomena in LLM reasoning capabilities.\n\nWeaknesses:\n1. Some assumptions about metastable dynamics may be idealized compared to actual reasoning patterns.", "other_comments_or_suggestions": "See weaknesses.", "questions_for_authors": "See weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GXrZUc42kY", "reviewer": "Reviewer_XmAg", "summary": "The authors propose a theoretical analysis of Chain-of-Thought (CoT) reasoning. Using a graph theoretical approach, they distinguish “easy” reasoning steps as intra-dense cluster connections from harder reasoning steps, which connect different clusters but have low probability of being picked at inference. They analyse a search methodology aiming to increase the probability of transitioning between different clusters (i.e. of CoT exploring harder reasoning steps) in order to improve the efficiency of reasoning. This framing also helps understand how reasoning can be distilled into a simpler model. Finally, this work shows the limitations of reasoning in some settings without global search.\n\n## update after rebuttal\nI maintain my recommendation to accept the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment of our contributions and helpful suggestions! Our responses are as follows; typos have been fixed.\n\n**Response to Weakness** - While we did not conduct any experiments due to time and compute constraints, the formulation and theory do give quantitative predictions that could be empirically studied in a future work. For example, we can measure the length of CoT to solve difficult math problems as a function of the amount of finetuning to validate Theorem 3.2. Another approach is to train a “difficulty” model to score how easy or hard each reasoning step is, and probe the observed sparse-dense dynamics of CoT (e.g. by looking at the density and distribution of hard steps before/after finetuning).\n\nWe also acknowledge that the practical value of our model is limited insofar as it is quite abstract and simplified; please see our rebuttal to Reviewer R4eB on directions to improve this.\n\n**Questions**\n1. In Prop 2.1, $M$ refers to the cluster size $M:=\\max_k |C_k|$ of our setup, not the set $M$. We agree the notation is confusing and will replace the set $M$ with $\\mathcal{M}$.\n2. When $\\mathcal{R}=G=\\mathbb{Z}_2$, the identity element is 0. When $G$ is a space of functions, the identity element is the identity function. In the latter example, functions in $G$ must be necessarily invertible (bijective) to form a group rather than a monoid.", "claims_and_evidence": "Claims are proven in the appendix based on the hypotheses. I think the article does a good job of targeting timely concepts in the field that may seem intuitive but that lacked theoretical grounding.", "methods_and_evaluation_criteria": "This is a theory paper.", "theoretical_claims": "Proofs are provided for the theoretical claims, but **see important caveat about supplemental material**.", "experimental_designs_or_analyses": "This is a theory paper.", "relation_to_broader_scientific_literature": "This paper proposes a theoretical framework for recent methodologies to improve reasoning performance of foundation models, generally based on increasing compute at inference.", "essential_references_not_discussed": "I think the paper discussed existing literature decently well considering the page constraints.", "other_strengths_and_weaknesses": "Generally, I would have liked to see a practical application / outcome of this theoretical analysis. Still, I do understand that there is value in having a theoretical framing/results of intuitive notions, which may help the community build practical methods inspired from this theory.", "other_comments_or_suggestions": "Typos:\n1. “We use sign gradient descent for simplicity of analysis (ordinary gradient descent” should be “ascent” (since you are solving a maximisation problem).", "questions_for_authors": "1. Prop 2.1: what is meant by “M->\\infty”? I assume it’s the definition given in 2.1 of M that should be used here, but if that’s the case I suggest switching “M” for something else in the paragraph preceding prop 2.1 as there, M is a set (more specifically, a subset of a finite state space).\n2. P7: what would be the inverse element in the group G with the example that you gave?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f0Rcn6iZGW", "reviewer": "Reviewer_R4eB", "summary": "This paper models Chain-of-Thought (CoT) reasoning as a metastable Markov process, where dense clusters correspond to easy reasoning steps and sparse edges represent difficult transitions. It provides a theoretical analysis of how search, reinforcement learning (RL), and distillation improve hitting times by identifying and enhancing sparse transitions. The study also employs statistical query (SQ) complexity arguments to establish the necessity of global search.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and suggestions! Our responses are as follows.\n\n**Claims And Evidence** - Thank you for pointing out the possible confusion. We have made sure that the training dynamics is only referred to as \"optimization guarantee\", \"training dynamics\", \"gradient descent iterates\", etc.\n\n**Response to Weakness 1** - While this is true for the basic Markov model in Section 2, the logical reasoning task we introduce in Section 5 is an example of how this model can be easily enriched to include notions of correctness or algorithmic computation. The sequential nature of the logical computation task introduced in line 362 makes it so that each step of the chain must be correct in order to obtain the final answer, which is an intuitive property of CoT and is key to the proof of the SQ lower bound - if any single step is wrong, the final output will be uniformly distributed and contain no useful information.\n\nFor a simple application, suppose the model must execute the logical computation at each step, with a small probability of failure $p$. An immediate corollary of decreased hitting time (Theorem 3.2) is that the overall probability of failure is improved from $1-(1-p)^{|S|/\\varepsilon}$ to $1-(1-p)^{|S|/\\varepsilon_{\\text{max}}}$. Hence while a priori longer CoT can help in reaching target states which are farther away, RL can produce shorter, more efficient CoT for each target, likely resulting in less error accumulation or hallucinations.\n\nNonetheless, we have elected to focus on the Markov model for the majority of the paper and only introduce the logic task towards the end to prove the lower bounds, for simplicity of presentation.\n\nAnother natural extension to incorporate the multi-step nature of CoT is to model reasoning as a Markov decision process rather than a Markov chain, as in [SRLK25]. That is, the full state space $S^*=\\cup_{t\\ge 1} S^t$ is the set of trajectories $(s_1,\\cdots,s_t)\\in S^t$, and each new action (transition) $s_t\\to s_{t+1}$ is concatenated with the previous trajectory to give the next state $(s_1,\\cdots,s_{t+1})$. This subsumes our model by relaxing the memorylessness assumption, which is more realistic since CoT should take into account all previous reasoning steps. Then we can again study clustering behavior and metastable dynamics of the final token $s_t$ in the original state space $S$ under a more sophisticated base model/policy.\n\n**Response to Weakness 2** - In this paper, we devoted our attention to the idea of modeling easy versus hard steps, which led other aspects of the setup being quite abstract/general. However, we agree that more could be derived by studying a concrete class of reasoners. A natural extension to incorporate more CoT-specific behavior is to model the process as an MDP, as described above. This can then be used to study CoT dynamics for specific tasks, for example, the parity task which has been used to show the computational benefits of CoT optimization [KS24] can be understood by taking the state space to be the set of binary strings, and reasoners as executing 2-parities at each step.\n\n[SRLK25] Scaling test-time compute without verification or RL is suboptimal. Amrith Setlur, Nived Rajaraman, Sergey Levine, Aviral Kumar. arXiv preprint arXiv:2502.12118.\n\n[KS24] Transformers provably solve parity efficiently with chain of thought. Juno Kim, Taiji Suzuki. ICLR 2025.\n\n[WZLZ24] From sparse dependence to sparse attention: unveiling how chain-of-thought enhances transformer sample efficiency. Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, Jingzhao Zhang. ICLR 2025.", "claims_and_evidence": "My only concern about the claim is that the use of \"dynamics\" to describe the transition process may lead to confusion with training dynamics of COT.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The proof seems correct.", "experimental_designs_or_analyses": "There is no experiment.", "relation_to_broader_scientific_literature": "The metastable Markov chain abstraction offers a principled framework for formalizing CoT inference dynamics, linking metastability theory (e.g., hitting times) to large language model (LLM) reasoning.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "### **Strengths**  \n1. The metastable Markov chain abstraction offers a principled framework for formalizing CoT inference dynamics, linking metastability theory (e.g., hitting times) to large language model (LLM) reasoning.  \n2. The analysis elucidates why inference-time compute (via search) and fine-tuning (via RL) enhance CoT by prioritizing sparse transitions, while distillation compresses cluster-level dynamics. The SQ lower bound provides a rigorous argument for the necessity of global search.  \n\n---\n\n### **Weaknesses**  \n1. Modeling CoT as a Markov chain reduces reasoning to state transitions, potentially overlooking key aspects such as multi-step logical consistency and algorithmic operations.  \n2. While search, RL, and distillation improve hitting times in the model, the analysis does not establish a direct connection to CoT’s unique characteristics. The results could generalize to any sparse transition system and efficient edge-search algorithm, raising questions about the theory’s specificity to CoT reasoning.", "other_comments_or_suggestions": "Please see above.", "questions_for_authors": "Please see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This theoretical work addresses the problem of finding high-reward trajectories from an LLM models. Posing the "steps" (sentences or expressions) generated by an LLM as nodes in a graph, it proves that biasing the search towards "sparse" edges that connect different clusters shortens the search time.

All reviewers favor the acceptance of this work, which provides direct guidance for a more efficient use of test-time compute. The provided results are novel and seem correct, and provide a principled explanation of phenomena observed in practice in LLM. This work would however be strengthened by the inclusion of experimental results beyond the provided proofs.
Decision: Accept (poster)