mlsanityData to 7 Oct 2026

Conditions for Length Generalization in Learning Reasoning Skills

arXiv 2311.16173 ↗First posted 22 Nov 2023cs.AI cs.CL cs.LGcited by 7

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

Reasoning is a fundamental capability of AI agents. Recently, large language models (LLMs) have shown remarkable abilities to perform reasoning tasks. However, numerous evaluations of the reasoning capabilities of LLMs have also showed some limitations. An outstanding limitation is length generalization, meaning that when trained on reasoning problems of smaller lengths or sizes, the resulting models struggle with problems of larger sizes or lengths. This potentially indicates some theoretical limitations of generalization in learning reasoning skills. These evaluations and their observations motivated us to perform a theoretical study of the length generalization problem. This work focuses on reasoning tasks that can be formulated as Markov dynamic processes (MDPs) and/or directed acyclic graphs (DAGs). It identifies and proves conditions that decide whether the length generalization problem can be solved or not for a reasoning task in a particular representation. Experiments are also conducted to verify the theoretical results.

Key facts. Cited by 7 papers in the map (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 55 of its 74 references that are in the map. First posted on arXiv 22 Nov 2023.

Builds on

55 of 74 references.

Closest ancestors · 5

Same direction, newest first

  1. 2023Auto-Regressive Next-Token Predictors are Universal Learners13 Sep
  2. 2023Making Large Language Models Better Reasoners with Alignment5 Sep
  3. 2023Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models12 Jun
  4. 2023Tree of Thoughts: Deliberate Problem Solving with Large Language Models17 May
  5. 2023Large Language Model Guided Tree-of-Thought15 May

Other references · 50

  1. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  2. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  3. 2022Scaling Instruction-Finetuned Language Modelscited by 2,997
  4. 2022Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Themcited by 1,767
  5. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Taskscited by 1,057
  6. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  7. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  8. 2023Orca: Progressive Learning from Complex Explanation Traces of GPT-4cited by 369
  9. 2022Language Models Are Greedy Reasoners: A Systematic Formal Analysis of Chain-of-Thoughtcited by 334
  10. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  11. 2023Faithful Chain-of-Thought Reasoningcited by 285
  12. 2023Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Taskscited by 243
38 more
  1. 2022Towards Understanding Chain-of-Thought Prompting: An Empirical Study of What Matterscited by 221
  2. 2023Evaluating the Logical Reasoning Ability of ChatGPT and GPT-4cited by 202
  3. 2023ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Modelscited by 174
  4. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 136
  5. 2023Deductive Verification of Chain-of-Thought Reasoningcited by 122
  6. 2023Teaching Arithmetic to Small Transformerscited by 121
  7. 2022Unveiling Transformers with LEGO: a synthetic reasoning taskcited by 105
  8. 2023Chain-of-Thought Hub: A Continuous Effort to Measure Large Language Models' Reasoning Performancecited by 102
  9. 2023Cumulative Reasoning with Large Language Modelscited by 94
  10. 2023A Mechanistic Interpretation of Arithmetic Reasoning in Language Models using Causal Mediation Analysiscited by 88
  11. 2023Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Taskscited by 84
  12. 2023Boosting Language Models Reasoning with Chain-of-Knowledge Promptingcited by 77
  13. 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
  14. 2022Limitations of Language Models in Arithmetic and Symbolic Inductioncited by 71
  15. 2023Are Large Language Models Really Good Logical Reasoners? A Comprehensive Evaluation and Beyondcited by 65
  16. 2019Recent Advances in Natural Language Inference: A Survey of Benchmarks, Resources, and Approachescited by 64
  17. 2023Large Language Models are In-Context Semantic Reasoners rather than Symbolic Reasonerscited by 63
  18. 2023Natural Language Reasoning, A Surveycited by 61
  19. 2023Large Language Models Are Not Strong Abstract Reasonerscited by 52
  20. 2023Beyond Chain-of-Thought, Effective Graph-of-Thought Reasoning in Language Modelscited by 51
  21. 2023Measuring and Improving Chain-of-Thought Reasoning in Vision-Language Modelscited by 45
  22. 2023GPT-4 Can't Reasoncited by 39
  23. 2023Towards Benchmarking and Improving the Temporal Reasoning Capability of Large Language Modelscited by 37
  24. 2023Logical Reasoning over Natural Language as Knowledge Representation: A Surveycited by 32
  25. 2023Counterfactual reasoning: Testing language models' understanding of hypothetical scenarioscited by 27
  26. 2023Thinking Like an Expert:Multimodal Hypergraph-of-Thought (HoT) Reasoning to boost Foundation Modalscited by 24
  27. 2023The Art of SOCRATIC QUESTIONING: Recursive Thinking with Large Language Modelscited by 22
  28. 2023Dissecting Chain-of-Thought: Compositionality through In-Context Filtering and Learningcited by 19
  29. 2023When Do Program-of-Thoughts Work for Reasoning?cited by 19
  30. 2023ScoNe: Benchmarking Negation Reasoning in Language Models With Fine-Tuning and In-Context Learningcited by 17
  31. 2023Tree-of-Mixed-Thought: Combining Fast and Slow Thinking for Multi-hop Visual Reasoningcited by 17
  32. 2023Code Prompting: a Neural Symbolic Method for Complex Reasoning in Large Language Modelscited by 16
  33. 2023A Symbolic Framework for Evaluating Mathematical Reasoning and Generalisation with Transformerscited by 15
  34. 2022Chaining Simultaneous Thoughts for Numerical Reasoningcited by 14
  35. 2023Evaluating Large Language Models with NeuBAROCO: Syllogistic Reasoning Ability and Human-like Biasescited by 14
  36. 2023Certified Deductive Reasoning with Language Modelscited by 8
  37. 2023Invalid Logic, Equivalent Gains: The Bizarreness of Reasoning in Language Model Promptingcited by 8
  38. 2023Exploring Equation as a Better Intermediate Meaning Representation for Numerical Reasoningcited by 7

Built on by

Cited by year

Citing papers per year: 2024: 5; 2025: 2.

7 papers.

  1. 2025Ignore the KL Penalty! Boosting Exploration on Critical Tokens to Enhance RL Fine-Tuningcited by 33
  2. 2024Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregationcited by 22
  3. 2024On Provable Length and Compositional Generalizationcited by 22
  4. 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 22
  5. 2025Enhancing Auto-regressive Chain-of-Thought through Loop-Aligned Reasoningcited by 19
  6. 2024Your Context Is Not an Array: Unveiling Random Access Limitations in Transformerscited by 11
  7. 2024Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalizationcited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2025Long Is More Important Than Difficult for Training Reasoning Models
  2. 2024A Theory for Length Generalization in Learning to Reason
  3. 2026On the Optimal Reasoning Length for RL-Trained Language Models
  4. 2024Language Models Need Inductive Biases to Count Inductively
  5. 2025From General Reasoning to Domain Expertise: Uncovering the Limits of Generalization in Large Language Models
  6. 2026Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Traces
  7. 2025Bridging the Reasoning Gap: Small LLMs Can Plan with Generalised Strategies
  8. 2026Generalization in LLM Problem Solving: The Case of the Shortest Path