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

arXiv: https://arxiv.org/abs/2511.07378 · HTML: https://mlsanity.com/paper/2511.07378/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning.
- Builds on 62 of its 115 references that are in the map.
- First posted on arXiv 10 Nov 2025.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 30 of 62)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [YaRN: Efficient Context Window Extension of Large Language Models](https://mlsanity.com/paper/2309.00071/) (2023)
- [Textbooks Are All You Need](https://mlsanity.com/paper/2306.11644/) (2023)
- [Reinforced Self-Training (ReST) for Language Modeling](https://mlsanity.com/paper/2308.08998/) (2023)
- [Training Language Models to Self-Correct via Reinforcement Learning](https://mlsanity.com/paper/2409.12917/) (2024)
- [Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Models](https://mlsanity.com/paper/2312.06585/) (2023)
- [Large Language Models Are Reasoning Teachers](https://mlsanity.com/paper/2212.10071/) (2022)
- [LongRoPE: Extending LLM Context Window Beyond 2 Million Tokens](https://mlsanity.com/paper/2402.13753/) (2024)
- [Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning](https://mlsanity.com/paper/2012.09816/) (2020)
- [Teaching Small Language Models to Reason](https://mlsanity.com/paper/2212.08410/) (2022)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Imitate, Explore, and Self-Improve: A Reproduction Report on Slow-thinking Reasoning Systems](https://mlsanity.com/paper/2412.09413/) (2024)
- [O1 Replication Journey: A Strategic Progress Report -- Part 1](https://mlsanity.com/paper/2410.18982/) (2024)
- [Text and Patterns: For Effective Chain of Thought, It Takes Two to Tango](https://mlsanity.com/paper/2209.07686/) (2022)
- [Evaluation of OpenAI o1: Opportunities and Challenges of AGI](https://mlsanity.com/paper/2409.18486/) (2024)
- [A Survey of Context Engineering for Large Language Models](https://mlsanity.com/paper/2507.13334/) (2025)
- [How Transformers Learn Causal Structure with Gradient Descent](https://mlsanity.com/paper/2402.14735/) (2024)
- [Unveiling Transformers with LEGO: a synthetic reasoning task](https://mlsanity.com/paper/2206.04301/) (2022)
- [Self-Improvement in Language Models: The Sharpening Mechanism](https://mlsanity.com/paper/2412.01951/) (2024)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)

## Built on by (most cited first, 14 of 14)

- [SWE-World: Building Software Engineering Agents in Docker-Free Environments](https://mlsanity.com/paper/2602.03419/) (2026)
- [Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Data](https://mlsanity.com/paper/2601.15158/) (2026)
- [Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End](https://mlsanity.com/paper/2604.12013/) (2026)
- [Can Vision-Language Models Solve the Shell Game?](https://mlsanity.com/paper/2603.08436/) (2026)
- [Learning to Think from Multiple Thinkers](https://mlsanity.com/paper/2604.24737/) (2026)
- [A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.06819/) (2026)
- [Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridge](https://mlsanity.com/paper/2602.02470/) (2026)
- [Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Traces](https://mlsanity.com/paper/2602.14404/) (2026)
- [On the Expressive Power and Limitations of Multi-Layer SSMs](https://mlsanity.com/paper/2604.14501/) (2026)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [The Power of Power Law: Asymmetry Enables Compositional Reasoning](https://mlsanity.com/paper/2604.22951/) (2026)
- [Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation](https://mlsanity.com/paper/2606.31184/) (2026)
- [When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signal](https://mlsanity.com/paper/2607.11953/) (2026)
- [ALoDLM: Adaptively Looped Diffusion Language Models](https://mlsanity.com/paper/2610.04198/) (2026)

## Abstract (arXiv)

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 mathsfNC1-complete problems with CoT, significantly going beyond prior art confined in mathsfTC0, unless the widely held conjecture mathsfTC0 neq mathsfNC1 fails. Finally, we present a broad set of experiments supporting our theoretical results, confirming the length generalization behaviors and the mechanism of attention concentration.