# Conditions for Length Generalization in Learning Reasoning Skills

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

## Key facts

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

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [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)
- [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)
- [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)
- [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)
- [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)
- [Evaluating the Logical Reasoning Ability of ChatGPT and GPT-4](https://mlsanity.com/paper/2304.03439/) (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)
- [Deductive Verification of Chain-of-Thought Reasoning](https://mlsanity.com/paper/2306.03872/) (2023)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Unveiling Transformers with LEGO: a synthetic reasoning task](https://mlsanity.com/paper/2206.04301/) (2022)
- [Chain-of-Thought Hub: A Continuous Effort to Measure Large Language Models' Reasoning Performance](https://mlsanity.com/paper/2305.17306/) (2023)
- [Cumulative Reasoning with Large Language Models](https://mlsanity.com/paper/2308.04371/) (2023)
- [A Mechanistic Interpretation of Arithmetic Reasoning in Language Models using Causal Mediation Analysis](https://mlsanity.com/paper/2305.15054/) (2023)
- [Goat: Fine-tuned LLaMA Outperforms GPT-4 on Arithmetic Tasks](https://mlsanity.com/paper/2305.14201/) (2023)
- [Boosting Language Models Reasoning with Chain-of-Knowledge Prompting](https://mlsanity.com/paper/2306.06427/) (2023)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [Limitations of Language Models in Arithmetic and Symbolic Induction](https://mlsanity.com/paper/2208.05051/) (2022)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Recent Advances in Natural Language Inference: A Survey of Benchmarks, Resources, and Approaches](https://mlsanity.com/paper/1904.01172/) (2019)

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

- [Ignore the KL Penalty! Boosting Exploration on Critical Tokens to Enhance RL Fine-Tuning](https://mlsanity.com/paper/2502.06533/) (2025)
- [Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure](https://mlsanity.com/paper/2405.20671/) (2024)
- [Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation](https://mlsanity.com/paper/2402.03268/) (2024)
- [On Provable Length and Compositional Generalization](https://mlsanity.com/paper/2402.04875/) (2024)
- [Enhancing Auto-regressive Chain-of-Thought through Loop-Aligned Reasoning](https://mlsanity.com/paper/2502.08482/) (2025)
- [Your Context Is Not an Array: Unveiling Random Access Limitations in Transformers](https://mlsanity.com/paper/2408.05506/) (2024)
- [Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalization](https://mlsanity.com/paper/2410.08898/) (2024)

## 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.