mlsanityData to 7 Oct 2026

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

arXiv 2511.07378 ↗First posted 10 Nov 2025cs.LG cs.AI math.OCcited by 12

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

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.

Key facts. Cited by 12 papers in the map (data through 7 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.

Builds on

62 of 115 references.

Closest ancestors · 14

Same direction, newest first

  1. 2025Exact Expressive Power of Transformers with Padding25 May
  2. 2025A Theory of Learning with Autoregressive Chain of Thought11 Mar
  3. 2025Transformers Learn to Implement Multi-step Gradient Descent with Chain of Thought28 Feb
  4. 2025Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation2 Feb
  5. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought11 Oct
  6. 2024From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency7 Oct
  7. 2024Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods25 Aug
  8. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  9. 2023The Expressive Power of Transformers with Chain of Thought11 Oct
  10. 2022Large Language Models Are Reasoning Teachers20 Dec
  11. 2022Teaching Small Language Models to Reason16 Dec
  12. 2022Text and Patterns: For Effective Chain of Thought, It Takes Two to Tango16 Sep
2 more
  1. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Models21 May
  2. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Models21 Mar

Other references · 48

  1. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  2. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  3. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  4. 2024RULER: What's the Real Context Size of Your Long-Context Language Models?cited by 1,270
  5. 2018Self-Attention with Relative Position Representationscited by 1,112
  6. 2023YaRN: Efficient Context Window Extension of Large Language Modelscited by 584
  7. 2023Textbooks Are All You Needcited by 561
  8. 2023Reinforced Self-Training (ReST) for Language Modelingcited by 486
  9. 2024Training Language Models to Self-Correct via Reinforcement Learningcited by 405
  10. 2023Beyond Human Data: Scaling Self-Training for Problem-Solving with Language Modelscited by 325
  11. 2024LongRoPE: Extending LLM Context Window Beyond 2 Million Tokenscited by 302
  12. 2020Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learningcited by 292
36 more
  1. 2022Transformers Learn Shortcuts to Automatacited by 260
  2. 2024Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learningcited by 238
  3. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  4. 2024The Illusion of State in State-Space Modelscited by 181
  5. 2024Imitate, Explore, and Self-Improve: A Reproduction Report on Slow-thinking Reasoning Systemscited by 162
  6. 2024O1 Replication Journey: A Strategic Progress Report -- Part 1cited by 140
  7. 2024Evaluation of OpenAI o1: Opportunities and Challenges of AGIcited by 127
  8. 2025A Survey of Context Engineering for Large Language Modelscited by 120
  9. 2024How Transformers Learn Causal Structure with Gradient Descentcited by 114
  10. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  11. 2024Self-Improvement in Language Models: The Sharpening Mechanismcited by 102
  12. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
  13. 2023Length Generalization in Arithmetic Transformerscited by 64
  14. 2025InftyThink: Breaking the Length Limits of Long-Context Reasoning in Large Language Modelscited by 53
  15. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 49
  16. 2025Large Language Models Pass the Turing Testcited by 48
  17. 2025LongReason: A Synthetic Long-Context Reasoning Benchmark via Context Expansioncited by 47
  18. 2023Entity Tracking in Language Modelscited by 44
  19. 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 44
  20. 2024Theoretical limitations of multi-layer Transformercited by 43
  21. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  22. 2025Learning Compositional Functions with Transformers from Easy-to-Hard Datacited by 34
  23. 2025Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challengescited by 30
  24. 2024Universal Length Generalization with Turing Programscited by 25
  25. 2024On Provable Length and Compositional Generalizationcited by 22
  26. 2024Mind the Gap: Examining the Self-Improvement Capabilities of Large Language Modelscited by 16
  27. 2024Explicitly Encoding Structural Symmetry is Key to Length Generalization in Arithmetic Taskscited by 10
  28. 2025A Comparison of DeepSeek and Other LLMscited by 10
  29. 2025How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Biascited by 10
  30. 2021Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributionscited by 9
  31. 2025The Role of Sparsity for Length Generalization in Transformerscited by 8
  32. 2025Longer Context, Deeper Thinking: Uncovering the Role of Long-Context Ability in Reasoningcited by 7
  33. 2025Multi-head Transformers Provably Learn Symbolic Multi-step Reasoning via Gradient Descentcited by 7
  34. 2025Theoretical Modeling of Large Language Model Self-Improvement Training Dynamics Through Solver-Verifier Gapcited by 6
  35. 2024Provable Length Generalization in Sequence Prediction via Spectral Filteringcited by 3
  36. 2025Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Informationcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 12.

12 papers.

  1. 2026SWE-World: Building Software Engineering Agents in Docker-Free Environmentscited by 21
  2. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 5
  3. 2026Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridgecited by 2
  4. 2026Can Vision-Language Models Solve the Shell Game?cited by 2
  5. 2026Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-Endcited by 2
  6. 2026Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Tracescited by 1
  7. 2026On the Expressive Power and Limitations of Multi-Layer SSMscited by 1
  8. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)cited by 1
  9. 2026A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoningcited by 1
  10. 2026The Power of Power Law: Asymmetry Enables Compositional Reasoningcited by 0
  11. 2026Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimationcited by 0
  12. 2026When Does Reward Teach State? A Hidden-Automaton Instrument and a Group-Language Warning Signalcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025The Kinetics of Reasoning: How Chain-of-Thought Shapes Learning in Transformers?
  2. 2026Beyond the Training Horizon: Mechanisms and Limits of Length Generalization in Looped Transformers
  3. 2024Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis
  4. 2026Transformers Provably Learn to Internalize Chain-of-Thought
  5. 2025Analyzing the Power of Chain of Thought through Memorization Capabilities
  6. 2026Adaptive Loops and Memory in Transformers: Think Harder or Know More?
  7. 2025ShorterBetter: Guiding Reasoning Models to Find Optimal Inference Length for Efficient Reasoning
  8. 2026An Asymptotic Theory of Chain-of-Thought in In-Context Learning