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

• URL: http://arxiv.org/abs/2603.00306v1
• Date: Fri, 27 Feb 2026 20:43:34 GMT
• Title: When does Chain-of-Thought Help: A Markovian Perspective
• Abstract summary: Chain-of-Thought (CoT) prompting is a widely used inference-time technique for improving reasoning.<n>We analyze when and why CoT helps by modeling the step-wise reasoning trajectory as a Markov chain.
• Score: 25.903929237215333
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Think Wider: Mitigating Latent Rank Collapse in Implicit Chain-of-Thought Reasoning [3.216436532980238]
  Chain-of-thought (CoT) reasoning improves the reasoning ability of large language models by introducing intermediate computation.<n>However, explicit rationales increase decoding length, latency, and context cost.<n>Implicit CoT offers a more efficient alternative by moving intermediate reasoning into continuous latent states.
  arXiv  Detail & Related papers  (2026-09-07T12:18:51Z)
• How Hard Does It Think? Analyzing Step-Aware Reasoning Energy in LLM Chain-of-Thought Trajectories [51.16651846289446]
  We propose Step-Aware Reasoning Energy (SARE), a geometric framework that quantifies effort at the granularity of individual CoT steps.<n>We find that reasoning energy is highly non-uniform across step types, exhibiting phase-like transitions invisible to trajectory-level metrics.<n>SARE-based features match or outperform output-based confidence baselines in most settings.
  arXiv  Detail & Related papers  (2026-07-28T06:15:51Z)
• Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
  Implicit Chain-of-Thought (ICoT) trains models to internalize intermediate steps within their hidden states.<n>Log-ICoT removes thinking tokens one at a time, reducing the number of stages from linear in $k$ to logarithmic.<n>Experiments on multi-layer transformers confirm the theory and visualize how reasoning is progressively absorbed into deeper layers.
  arXiv  Detail & Related papers  (2026-05-27T15:17:06Z)
• Dynamics Within Latent Chain-of-Thought: An Empirical Study of Causal Structure [58.89643769707751]
  We study latent chain-of-thought as a manipulable causal process in representation space.<n>We find that latent-step budgets behave less like homogeneous extra depth and more like staged functionality with non-local routing.<n>These results motivate mode-conditional and stability-aware analyses as more reliable tools for interpreting and improving latent reasoning systems.
  arXiv  Detail & Related papers  (2026-02-09T15:25:12Z)
• Decoupling the Effect of Chain-of-Thought Reasoning: A Human Label Variation Perspective [60.45433515408158]
  We show that long Chain-of-Thought (CoT) serves as a decisive decision-maker for the top option but fails to function as a granular distribution calibrator for ambiguous tasks.<n>We observe a distinct "decoupled mechanism": while CoT improves distributional alignment, final accuracy is dictated by CoT content.
  arXiv  Detail & Related papers  (2026-01-06T16:26:40Z)
• Fractured Chain-of-Thought Reasoning [61.647243580650446]
  We introduce Fractured Sampling, a unified inference-time strategy that interpolates between full CoT and solution-only sampling.<n>We show that Fractured Sampling consistently achieves superior accuracy-cost trade-offs, yielding steep log-linear scaling gains in Pass@k versus token budget.
  arXiv  Detail & Related papers  (2025-05-19T11:30:41Z)
• Reasoning by Superposition: A Theoretical Perspective on Chain of Continuous Thought [64.43689151961054]
  We prove that a two-layer transformer with $D$ steps of continuous CoTs can solve the directed graph reachability problem.<n>In our construction, each continuous thought vector is a superposition state that encodes multiple search frontiers simultaneously.
  arXiv  Detail & Related papers  (2025-05-18T18:36:53Z)
• Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent [9.69064563836298]
  The convergence behavior of Gradient Descent (SGD) crucially depends on the stepsize configuration.<n>We propose a novel coupling-based diagnostic procedure, which is shown to track the transition from transience stationarity theoretically.
  arXiv  Detail & Related papers  (2024-12-15T23:50:23Z)
• Transformers Provably Solve Parity Efficiently with Chain of Thought [40.78854925996]
  This work provides the first theoretical analysis of training transformers to solve complex problems.<n>We consider training a one-layer transformer to solve the fundamental $k$-parity problem.
  arXiv  Detail & Related papers  (2024-10-11T08:55:17Z)
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis [82.51626700527835]
  Chain-of-shift (CoT) is an efficient method that enables the reasoning ability of large language models by augmenting the query using examples with multiple intermediate steps.<n>We show that despite the theoretical success of CoT, it fails to provide an accurate generalization when CoT does.
  arXiv  Detail & Related papers  (2024-10-03T03:12:51Z)
• Learning Iterative Robust Transformation Synchronization [71.73273007900717]
  We propose to use graph neural networks (GNNs) to learn transformation synchronization. In this work, we avoid handcrafting robust loss functions, and propose to use graph neural networks (GNNs) to learn transformation synchronization.
  arXiv  Detail & Related papers  (2021-11-01T07:03:14Z)
• Ergodicity Breaking Transition in Finite Disordered Spin Chains [0.0]
  We study disorder-induced ergodicity breaking transition in high-energy eigenstates of interacting spin-1/2 chains. We consistently find that an (infinite-order) Kosterlitz-Thouless transition yields a lower cost function when compared to a finite-order transition.
  arXiv  Detail & Related papers  (2020-04-03T18:00:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.