Chain-of-thought solves unseen multi-step tasks by reusing one step predictor, with error growing sublinearly in depth

Chain-of-thought models handle multi-step tasks never seen whole in training because they break a complex mapping into reusable single-step transitions and call the same single-step predictor repeatedly at inference. Earlier theory was largely qualitative, confined to two-step or narrow settings, and gave no explicit generalization bound for autoregressive next-token prediction; learning the composite mapping directly lacks target-task input-output samples. On Atom-Task, a chain-of-thought model trained only on single-step data shows some compositionality but degrades at longer test steps, while models trained on 3-step or mixed 3+5 short chains perform well on longer 3-, 5-, 7- and 9-step test sets, and a model trained without intermediate steps degrades on long chains.

Error growth with reasoning depth splits into two parts: a multiplicative price for inference errors set by the token block length per step and independent of depth, and a statistical estimation cost that shrinks as the inverse square root of depth because all steps share one predictor. Analyzing each step separately makes the generalization gap grow linearly in depth; pooling the step samples under one uniformly capacity-controlled hypothesis class improves both the deviation and complexity terms from linear to sublinear. In Atom-Task depth-scaling experiments, error rises with depth but with diminishing increments under single-step training; increasing sample size lowers test error, especially for long chains, consistent with estimation error shrinking with more samples.

In the next-token prediction setting, final-task risk is bounded by the best in-class step-level risk times the same depth-independent coefficient, plus an estimation term of order the inverse square root of depth. The bound keeps the best in-class step-level risk explicit in the final risk and gives dependence on reasoning depth, sample size and decoder capacity; a parity-coupled construction shows this dependence cannot be improved for the sub-task empirical risk minimizer. On GSM8K, Llama2-7B and Qwen2.5-3B fine-tuned on MetaMathQA show only mild accuracy fluctuation under topic, complexity and answer-scale distribution shifts, supporting transfer of compositional patterns to real mathematical reasoning.

The analysis covers explicit chain-of-thought under supervised next-token-style training, where intermediate states and step-level transitions are observable; experiments fine-tune Qwen3-4B on the custom Atom-Task symbolic sequence task and validate on GSM8K with Llama2-7B and Qwen2.5-3B using 30,000 MetaMathQA samples. The authors propose extending the decomposition framework to reinforcement fine-tuning and test-time search as a natural next direction.

The theory excludes adaptive paradigms such as reinforcement fine-tuning and test-time search, where trajectories may be selected, refined or rewarded; drift of the model's own generated trajectory is handled only through the hard-decoding reduction and is not itself a distributional guarantee; the GSM8K experiments evaluate a controlled within-family shift from MetaMathQA to GSM8K rather than source-disjoint transfer.