[2603.00306] When does Chain-of-Thought Help: A Markovian Perspective

Computer Science > Machine Learning arXiv:2603.00306 (cs) [Submitted on 27 Feb 2026] Title:When does Chain-of-Thought Help: A Markovian Perspective Authors:Zihan Wang, Yijun Dong, Qi Lei View a PDF of the paper titled When does Chain-of-Thought Help: A Markovian Perspective, by Zihan Wang and 2 other authors View PDF HTML (experimental) Abstract:Chain-of-Thought (CoT) prompting is a widely used inference-time technique for improving reasoning, yet its gains are uneven across tasks. We analyze when and why CoT helps by modeling the step-wise reasoning trajectory as a Markov chain. Each intermediate step is a state and the dependence between steps is captured by a transition kernel. Our theory identifies transition alignment, whether instances share a common step-wise transition kernel, as the key determinant of CoT's effectiveness. When transitions are identical across steps, CoT reduces inference-time sample complexity: fewer context sample trajectories suffice to recover the final decision. In contrast, when transitions differ across steps, these gains can vanish. We further quantify how noise in intermediate steps modulates CoT's benefit. Beyond theory, we design synthetic benchmarks that isolate these factors to complement prior results on real-world tasks and to empirically validate our predictions. Subjects: Machine Learning (cs.LG) Cite as: arXiv:2603.00306 [cs.LG]   (or arXiv:2603.00306v1 [cs.LG] for this version)   https://doi.org/10.48550/arXiv.2603.00306 Focus to...