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

Thank you for your detailed review and suggestions! Our responses are as follows.

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.

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.

For 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.

Nonetheless, 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.

Another 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.

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.

[SRLK25] Scaling test-time compute without verification or RL is suboptimal. Amrith Setlur, Nived Rajaraman, Sergey Levine, Aviral Kumar. arXiv preprint arXiv:2502.12118.

[KS24] Transformers provably solve parity efficiently with chain of thought. Juno Kim, Taiji Suzuki. ICLR 2025.

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

Thank you for your positive assessment of our contributions and helpful suggestions! Our responses are as follows; typos have been fixed.

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).

We 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.

Questions

1. 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}$.
2. 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.

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.