# A Theory for Length Generalization in Learning to Reason

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 69 of its 79 references that are in the map.
- First posted on arXiv 31 Mar 2024.

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizes](https://mlsanity.com/paper/2305.02301/) (2023)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [PAL: Program-aided Language Models](https://mlsanity.com/paper/2211.10435/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Orca: Progressive Learning from Complex Explanation Traces of GPT-4](https://mlsanity.com/paper/2306.02707/) (2023)
- [Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thought](https://mlsanity.com/paper/2210.01240/) (2022)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Faithful Chain-of-Thought Reasoning](https://mlsanity.com/paper/2301.13379/) (2023)
- [Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Tasks](https://mlsanity.com/paper/2307.02477/) (2023)
- [Binding Language Models in Symbolic Languages](https://mlsanity.com/paper/2210.02875/) (2022)
- [Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matters](https://mlsanity.com/paper/2212.10001/) (2022)
- [Large Language Model Guided Tree-of-Thought](https://mlsanity.com/paper/2305.08291/) (2023)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Evaluating the Logical Reasoning Ability of ChatGPT and GPT-4](https://mlsanity.com/paper/2304.03439/) (2023)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Models](https://mlsanity.com/paper/2305.18323/) (2023)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [ListOps: A Diagnostic Dataset for Latent Tree Learning](https://mlsanity.com/paper/1804.06028/) (2018)
- [A Length-Extrapolatable Transformer](https://mlsanity.com/paper/2212.10554/) (2022)

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

- [Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thought](https://mlsanity.com/paper/2410.05695/) (2024)
- [Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure](https://mlsanity.com/paper/2405.20671/) (2024)
- [The Lookahead Limitation: Why Multi-Operand Addition is Hard for LLMs](https://mlsanity.com/paper/2502.19981/) (2025)
- [Interpret Your Decision: Logical Reasoning Regularization for Generalization in Visual Classification](https://mlsanity.com/paper/2410.04492/) (2024)
- [RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasoner](https://mlsanity.com/paper/2410.23912/) (2024)
- [Unraveling Arithmetic in Large Language Models: The Role of Algebraic Structures](https://mlsanity.com/paper/2411.16260/) (2024)
- [A Theoretical Framework for OOD Robustness in Transformers using Gevrey Classes](https://mlsanity.com/paper/2504.12991/) (2025)
- [RBF++: Quantifying and Optimizing Reasoning Boundaries across Measurable and Unmeasurable Capabilities for Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.13307/) (2025)
- [Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More More](https://mlsanity.com/paper/2503.10542/) (2025)
- [Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Traces](https://mlsanity.com/paper/2602.14404/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)

## Abstract (arXiv)

Length generalization (LG) is a challenging problem in learning to reason. It refers to the phenomenon that when trained on reasoning problems of smaller lengths or sizes, the resulting model struggles with problems of larger sizes or lengths. Although LG has been studied by many researchers, the challenge remains. This paper proposes a theoretical study of LG for problems whose reasoning processes can be modeled as DAGs (directed acyclic graphs). The paper first identifies and proves the conditions under which LG can be achieved in learning to reason. It then designs problem representations based on the theory to learn to solve challenging reasoning problems like parity, addition, and multiplication, using a Transformer to achieve perfect LG.