Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization

Yu Huang, Zixin Wen, Aarti Singh, Yuejie Chi, Yuxin Chen

TL;DR

This paper provides the first theoretical proof that Transformers can learn complex, sequential reasoning (Chain-of-Thought) using standard gradient descent. The researchers demonstrate that a model's ability to solve problems longer than those it was trained on—known as length generalization—is fundamentally governed by the algebraic structure of the task and a mechanism called attention concentration.

What Problem Does This Paper Address?

While Large Language Models (LLMs) like OpenAI’s o1 or DeepSeek-R1 have shown remarkable "reasoning" capabilities through Chain-of-Thought (CoT), our theoretical understanding of how they learn these skills is lagging.

There are two major gaps in the literature:

  1. Expressivity vs. Optimization: We know Transformers can represent complex logic (expressivity), but we haven't proven that standard training (gradient descent) actually finds these solutions.
  2. Length Generalization: Reasoning often requires long sequences of steps. Can a model trained on short reasoning chains extrapolate to much longer ones? This is often hindered by "context rot," where performance drops as the input length increases.

The authors tackle these by analyzing a one-layer Transformer on a synthetic state-tracking task called LEGO (Learning Equality and Group Operations).

Methods

The authors analyze a "minimally viable" Transformer: a one-layer block with softmax attention and a feed-forward network (FFN), trained via gradient descent with No Positional Encoding (NoPE).

They study the training dynamics on two types of algebraic structures within the LEGO task:

  • Simply Transitive Actions: Think of a cyclic group (like a clock). For any two states, there is exactly one unique action that moves you from one to the other.
  • Symmetry Group Actions: These are more complex (like permutations). Multiple different actions can result in the same state transition, creating "distractors" during training.

To solve the harder symmetry tasks, they introduce a recursive self-training scheme. The model is first trained on short chains, then uses its own outputs to label slightly longer chains, progressively "bootstrapping" its reasoning length.

Datasets

The study uses the LEGO benchmark, a synthetic dataset designed to test entity tracking and state updates.

  • Format: A sequence of "predicate clauses" (e.g., $x_1 = g_1(x_0)$) followed by "answer clauses" (e.g., $x_0 = y_0$).
  • Goal: Predict the final state $y_L$ by following the chain.
  • Complexity: For symmetry groups, this task is $\mathsf{NC}^1$-complete, meaning it represents a class of problems that are inherently serial and difficult to parallelize.

Key Insights and Ideas

  • Attention Concentration: The "aha moment" of the paper is that length generalization depends on how sharply the attention layer focuses on relevant tokens. In simply transitive tasks, the unique relationship between actions and states allows the model to learn a "pure" retrieval signal, making it robust to the "noise" of longer contexts.
  • Algebraic Structure as a Governor: The degree of extrapolation isn't random; it's dictated by the math of the task. Simply transitive actions allow for exponential length generalization ($d^{c^*}$), while symmetry actions are limited to a constant factor unless self-training is used.
  • Division of Labor: During training, the FFN learns the "local rule" (how to apply an action), while the attention layer learns the "routing" (where to look for the next step).
  • Breaking the $\mathsf{TC}^0$ Barrier: Most prior theoretical work was confined to simple, parallelizable tasks ($\mathsf{TC}^0$). This work provides the first optimization guarantee for learning inherently sequential problems ($\mathsf{NC}^1$).

Key Results

The theoretical results were backed by extensive experiments:

  • Direct Generalization: For cyclic groups ($C_6$), a model trained on length $L=5$ achieved near-perfect accuracy on lengths up to $L=160$.
  • Self-Improvement: For symmetry groups ($S_5$), standard training failed to generalize far. However, the recursive self-training curriculum successfully shifted the accuracy curve, eventually matching the performance of the simpler cyclic tasks.
Figure 1: (a) Cyclic tasks generalize well; Symmetry tasks do not. (b) Self-training bootstraps symmetry task performance.
  • Visualizing Concentration: Heatmaps confirm that at convergence, the model develops sharp "diagonal" attention patterns, focusing exactly on the current state and the next required action.
Figure 2: Attention concentration at convergence for LEGO task with length L = 5. The heatmap places the query clause index on the y-axis (keys on the x-axis). For a task of length L, the LEGO sequence prior to the final answer clause has length 2L; we focus on query positions L + 1 to 2L, corresponding to answer clauses Zans,0 to Zans,L−1. Two diagonal bands in the upper region indicate attention concentrating on the answer clause Zans,ℓand the predicate clause Zpred,ℓ+1 when the query is Zans,ℓ.

Limitations and Future Work

While groundbreaking, the study has a few constraints:

  • Single Layer: The analysis focuses on a one-layer Transformer. While this captures the core mechanism of CoT, real-world models are much deeper.
  • Synthetic Data: LEGO is a powerful abstraction, but it lacks the semantic complexity and ambiguity of natural language reasoning.
  • NoPE Assumption: The results rely on the absence of positional encodings. The authors suggest that positional encodings might actually hinder length generalization by tying computation to specific absolute positions.

Future work could extend these proofs to multi-layer architectures and explore how these mechanisms behave in the presence of more complex, non-algebraic reasoning patterns.

Summary updated

Abstract

The ability to reason lies at the core of artificial intelligence (AI), and challenging problems usually call for deeper and longer reasoning to tackle. A crucial question about AI reasoning is whether models can extrapolate learned reasoning patterns to solve harder tasks with longer chain-of-thought (CoT). In this work, we present a theoretical analysis of transformers learning on synthetic state-tracking tasks with gradient descent. We mathematically prove how the algebraic structure of state-tracking problems governs the degree of extrapolation of the learned CoT. Specifically, our theory characterizes the length generalization of transformers through the mechanism of attention concentration, linking the retrieval robustness of the attention layer to the state-tracking task structure of long-context reasoning. Moreover, for transformers with limited reasoning length, we prove that a recursive self-training scheme can progressively extend the range of solvable problem lengths. To our knowledge, we provide the first optimization guarantee that constant-depth transformers provably learn $\mathsf{NC}^1$-complete problems with CoT, significantly going beyond prior art confined in $\mathsf{TC}^0$, unless the widely held conjecture $\mathsf{TC}^0 \neq \mathsf{NC}^1$ fails. Finally, we present a broad set of experiments supporting our theoretical results, confirming the length generalization behaviors and the mechanism of attention concentration.
BibTeX
@inproceedings{huang2025transformers,
  author = {Yu Huang and Zixin Wen and Aarti Singh and Yuejie Chi and Yuxin Chen},
  title = {{Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=aE0bCvXXBt},
}
Figure