Transformers Provably Solve Parity by Internalizing Chain-of-Thought

Chain-of-thought (CoT) improves the performance of transformers on complex reasoning tasks. However, generating explicit reasoning traces incurs substantial inference overhead. Implicit CoT (ICoT) aims to internalize these reasoning steps by gradually removing intermediate CoT tokens during training, yet the learning dynamics of this process remain poorly understood. We provide a theoretical analysis of ICoT for parity learning in a one-layer transformer with multi-head softmax attention. We prove that removing one intermediate token at a time enables ordinary gradient descent (GD) to solve parity with polynomially many samples and updates under suitable initialization. Our analysis characterizes a race among attention heads in which each newly missing parity bit recruits a new head while previously learned assignments are preserved. In contrast, we show that direct training from final-answer supervision alone leaves GD with high prediction error. Numerical experiments support our theoretical findings. Together, these results provide a mechanistic explanation for how a curriculum with intermediate supervision can enable efficient learning without explicit CoT at inference time.