mlsanityData to 7 Oct 2026

A Theory for Length Generalization in Learning to Reason

arXiv 2404.00560 ↗First posted 31 Mar 2024cs.AIcited by 11

Not on the map. Why?

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.

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

Builds on

69 of 79 references.

References · 69

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2020Language Models are Few-Shot Learnerscited by 32,199
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  4. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  5. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Modelscited by 3,155
  6. 2022Scaling Instruction-Finetuned Language Modelscited by 2,997
  7. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Themcited by 1,767
  8. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,085
  9. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Taskscited by 1,057
  10. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  11. 2023Distilling Step-by-Step! Outperforming Larger Language Models with Less Training Data and Smaller Model Sizescited by 710
  12. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
38 more
  1. 2022PAL: Program-aided Language Modelscited by 635
  2. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  3. 2023Orca: Progressive Learning from Complex Explanation Traces of GPT-4cited by 369
  4. 2022Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thoughtcited by 334
  5. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 319
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  7. 2023Faithful Chain-of-Thought Reasoningcited by 285
  8. 2023Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Taskscited by 243
  9. 2022Binding Language Models in Symbolic Languagescited by 224
  10. 2022Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matterscited by 221
  11. 2023Large Language Model Guided Tree-of-Thoughtcited by 218
  12. 2022Exploring Length Generalization in Large Language Modelscited by 204
  13. 2023Evaluating the Logical Reasoning Ability of ChatGPT and GPT-4cited by 202
  14. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 198
  15. 2023ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Modelscited by 174
  16. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 136
  17. 2018ListOps: A Diagnostic Dataset for Latent Tree Learningcited by 128
  18. 2022A Length-Extrapolatable Transformercited by 123
  19. 2023Deductive Verification of Chain-of-Thought Reasoningcited by 122
  20. 2023Teaching Arithmetic to Small Transformerscited by 121
  21. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  22. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  23. 2023Why think step by step? Reasoning emerges from the locality of experiencecited by 103
  24. 2023Chain-of-Thought Hub: A Continuous Effort to Measure Large Language Models' Reasoning Performancecited by 102
  25. 2023Cumulative Reasoning with Large Language Modelscited by 94
  26. 2023Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Taskscited by 84
  27. 2023Boosting Language Models Reasoning with Chain-of-Knowledge Promptingcited by 77
  28. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  29. 2022Limitations of Language Models in Arithmetic and Symbolic Inductioncited by 71
  30. 2023Length Generalization in Arithmetic Transformerscited by 64
  31. 2023Large Language Models are In-Context Semantic Reasoners rather than Symbolic Reasonerscited by 63
  32. 2023Making Large Language Models Better Reasoners with Alignmentcited by 63
  33. 2023Measuring and Improving Chain-of-Thought Reasoning in Vision-Language Modelscited by 45
  34. 2022Directed Acyclic Transformer for Non-Autoregressive Machine Translationcited by 44
  35. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
  36. 2023Towards Benchmarking and Improving the Temporal Reasoning Capability of Large Language Modelscited by 37
  37. 2022Chain of Thought Imitation with Procedure Cloningcited by 30
  38. 2023Counterfactual reasoning: Testing language models' understanding of hypothetical scenarioscited by 27

50 most cited of 69 All 69 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 5; 2026: 1.

11 papers.

  1. 2024Unlocking the Capabilities of Thought: A Reasoning Boundary Framework to Quantify and Optimize Chain-of-Thoughtcited by 56
  2. 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 22
  3. 2025The Lookahead Limitation: Why Multi-Operand Addition is Hard for LLMscited by 13
  4. 2024Interpret Your Decision: Logical Reasoning Regularization for Generalization in Visual Classificationcited by 5
  5. 2024RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasonercited by 4
  6. 2024Unraveling Arithmetic in Large Language Models: The Role of Algebraic Structurescited by 4
  7. 2025A Theoretical Framework for OOD Robustness in Transformers using Gevrey Classescited by 4
  8. 2025RBF++: Quantifying and Optimizing Reasoning Boundaries across Measurable and Unmeasurable Capabilities for Chain-of-Thought Reasoningcited by 4
  9. 2025Language Models, Graph Searching, and Supervision Adulteration: When More Supervision is Less and How to Make More Morecited by 3
  10. 2026Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Tracescited by 1
  11. 2025Learning Model Successorscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023Conditions for Length Generalization in Learning Reasoning Skills
  2. 2025Long Is More Important Than Difficult for Training Reasoning Models
  3. 2025Shorter but not Worse: Frugal Reasoning via Easy Samples as Length Regularizers in Math RLVR
  4. 2025OMEGA: Can LLMs Reason Outside the Box in Math? Evaluating Exploratory, Compositional, and Transformative Generalization
  5. 2025Does Learning Mathematical Problem-Solving Generalize to Broader Reasoning?
  6. 2026Learning to Reason with Curriculum II: Compositional Generalization
  7. 2025Improving LLMs' Generalized Reasoning Abilities by Graph Problems
  8. 2024Language Models Need Inductive Biases to Count Inductively