Chain-of-thought prompting helps language models solve problems they cannot solve directly. The intuition: intermediate reasoning steps decompose a hard problem into easier subproblems, each within the model's capability. More steps, more decomposition, better performance.
The Markovian analysis shows this intuition is incomplete. Chain-of-thought helps only when the problem has a specific dependency structure: each reasoning step must depend on a bounded window of previous steps, not on the entire history. This is the Markov property — the future depends on the present, not the past.
When the problem is Markovian, chain-of-thought converts a non-Markovian direct computation (the answer depends on all inputs simultaneously) into a sequence of Markovian steps (each step depends on a fixed-size window). The decomposition works because the intermediate steps carry forward exactly the information needed for the next step, discarding the rest. The chain is a compression pipeline: each step compresses the history into a sufficient statistic for the future.
When the problem is not Markovian — when step n genuinely depends on step 1 regardless of what happened in between — chain-of-thought cannot help. The intermediate steps must carry the entire history forward, and the chain becomes as expensive as the direct computation. The steps are not decomposing the problem; they are merely serializing it.
The practical consequence: chain-of-thought is not a general reasoning enhancer. It is a tool for problems with a specific structure — bounded dependency, compressible state. For problems where the answer depends on distant, non-summarizable context (certain logical puzzles, long-range entailments), chain-of-thought adds tokens without adding capability.
The structural lesson: the benefit of intermediate steps is not their number but their Markov order — how far back each step needs to look. If the order is bounded, chain-of-thought compresses the problem exponentially. If the order grows with problem size, the chain provides no compression and no benefit. The question is not “does this problem need reasoning?” but “does this problem have bounded-order dependencies?”