Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization
Yu Huang, Zixin Wen, Aarti Singh, Yuejie Chi, Yuxin Chen
The ability to reason lies at the core of artificial intelligence, and tough problems usually call for deeper, more extended reasoning to tackle. A crucial question about AI reasoning is whether models can extrapolate from learned reasoning patterns to solve harder tasks that require longer chain-of-thoughts (CoT).In this work, we present a theoretical analysis of transformers trained via gradient descent on synthetic data for various state tracking tasks, revealing how length-generalizable reasoning can emerge.Specifically, we prove that 1) for tasks with simple algebraic structure, e.g., composition in a cyclic group,  transformers learn a solution pattern that generalizes to polynomial-length CoT; 2) for more complex tasks like composition in a symmetric group, a recursive self-training curriculum enables transformers to bootstrap longer reasoning and achieve polynomial generalization.Intuitively, our results demonstrate that transformers can learn sequential reasoning skills that scale with problem complexity. Moreover, we provide the first provable optimization-based  guarantee for constant-depth transformers on the state tracking problems beyond circuit complexity class $\mathsf{TC}^0$: we prove that they can learn problems in $\mathsf{NC}^1$, which goes beyond prior results that consider problems within $\mathsf{TC}^0$, unless the famous conjecture $\mathsf{TC}^0 \neq \mathsf{NC}^1$ is false.