When does Chain-of-Thought Help: A Markovian Perspective

Zihan Wang; Yijun Dong; Qi Lei

cs.LGFeb 27, 2026

When does Chain-of-Thought Help: A Markovian Perspective

Authors: Zihan Wang, Yijun Dong, Qi Lei

Organizations: New York University

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.

Figures & tables

Panel of Figure 1 — Figure 1: (a) Example of Markov-style decomposition. An illustrative instance, where the original text is selected from ( Mavi et al., 2024 ) , is parsed into an initial state $x_{0}$ and a sequence of relations/operators $r_{1:T}$ . The correct intermediate steps $x_{1:T}$ are also included. The example highlights how text data are collapsed into a formalized sequence, making the intermediate operations explicit for CoT demonstrations. (b) Stepwise Markov dynamics. Each $r_{t}$ induces a transition kernel $P^{(t)}$ from $x_{t-1}$ to $x_{t}$ and the next node is generated randomly following the transition. At inference, the ground truth intermediate steps are the nodes with the largest probability $p^{*}$ for each step.

Panel of Figure 2 — Figure 2: Synthetic alignment study (same vs. diff). Left: Accuracy as a function of the number of context samples $n$ comparing CoT (solid) and NonCoT (dashed). CoT yields a consistently larger improvement under same than under diff . Right: Sample-complexity proxy $\Delta n(\tau)$ (CoT $-$ NonCoT) vs. target accuracy $\tau$ . More negative values indicate fewer samples required by CoT. The widening gap in the same condition is consistent with the theoretical $1/T$ -type gain for aligned kernels. Shaded regions denote mean $\pm$ SE.

Panel of Figure 3 — Figure 3: Noise ablation under aligned transitions. Left: Accuracy vs. $n$ for CoT/NonCoT under small and large intermediate-step noise. Right: $\Delta n(\tau)$ vs. $\tau$ . CoT reduces the required context budget more when noise is higher, reflecting that the global margin $\Delta_{Q}$ shrinks faster than the local margin $\Delta_{P}$ as stochasticity increases. Shaded regions denote mean $\pm$ SE.

Figure 4: Multi-step modular addition (practical check). Accuracy vs.

n

for CoT and NonCoT when both steps add the same number versus different numbers (fixed modulus). The larger CoT gain in the aligned ( same ) case corroborates the synthetic findings in a more realistic arithmetic setting. Error bands show mean

\pm

SE.

Figure 5: City–State rankings. Accuracy vs.

n

(left) and CoT gain

\Delta\text{Acc}

(right) under same-skill vs. diff-skill . Error bands: mean

\pm

SE.

Markov Chains

See all 29 papers

On the Cost and Benefit of Chain of Thought: A Learning-Theoretic Perspective
May 20, 2026Yue Zhang, Zhiyi Dong, Tommaso Cesari +1CoT Reasoning
University of Ottawa, Ottawa, Canada
Efficient Reasoning Training Does Not Always Harm CoT Faithfulness and Monitorability
Oct 2, 2026Samuel Lewis-Lim, Xingwei Tan, Mario Sanger +2Faithfulness of Language Model Reasoning Efficient Language Model Reasoning
School of Computer Science, University of Sheffield · AstraZeneca
When Chain-of-Thought Fails, the Solution Hides in the Hidden States
Apr 25, 2026Houman Mehrafarin, Amit Parekh, Ioannis KonstasTransformer Interpretability CoT Reasoning
Heriot-Watt University, Edinburgh, United Kingdom · University of Edinburgh, Edinburgh, United Kingdom

May 20, 2026J/K move · Enter open · S save

On the Cost and Benefit of Chain of Thought: A Learning-Theoretic Perspective

Yue Zhang, Zhiyi Dong, Tommaso Cesari, Yongyi Mao

University of Ottawa, Ottawa, Canada

CoT Reasoning

Open paper AskPDF arXiv

We develop a learning-theoretic framework for understanding Chain of Thought (CoT). We model CoT as the interaction between an answer map and a chain rule that generates intermediate questions autoregressively, and define the reasoning risk of a hypothesis under this interaction. Our first result is a tight canonical decomposition of this risk into two terms with opposing roles: an oracle-trajectory risk (OTR), which captures the benefit of CoT and reduces to a target-domain risk in a domain adaptation problem, and a trajectory-mismatch risk (TMR), which captures the cost of CoT through error accumulation along mismatched reasoning trajectories. We then show that this cost is unavoidable without structure: if any one of the loss, the hypothesis answer map, or the chain rule lacks stability, the TMR can be arbitrarily large even when the OTR is zero and the hypothesis is uniformly close to the ground truth. Conversely, under stability, we prove a tight upper bound on the TMR governed by an exact amplification factor that identifies bounded, linear, and exponential error-growth regimes. Together, these results give a precise theory of when CoT helps, when it hurts, and what controls the transition between the two.

Abstract

Markov Chains

Explore similar work

On the Cost and Benefit of Chain of Thought: A Learning-Theoretic Perspective

Efficient Reasoning Training Does Not Always Harm CoT Faithfulness and Monitorability

When Chain-of-Thought Fails, the Solution Hides in the Hidden States