# On Provable Length and Compositional Generalization

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 73 references that are in the map.
- First posted on arXiv 7 Feb 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Invariant Risk Minimization](https://mlsanity.com/paper/1907.02893/) (2019)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Textbooks Are All You Need](https://mlsanity.com/paper/2306.11644/) (2023)
- [Causal inference using invariant prediction: identification and confidence intervals](https://mlsanity.com/paper/1501.01332/) (2015)
- [Variational Autoencoders and Nonlinear ICA: A Unifying Framework](https://mlsanity.com/paper/1907.04809/) (2019)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Resurrecting Recurrent Neural Networks for Long Sequences](https://mlsanity.com/paper/2303.06349/) (2023)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection](https://mlsanity.com/paper/2306.04637/) (2023)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Invariance Principle Meets Information Bottleneck for Out-of-Distribution Generalization](https://mlsanity.com/paper/2106.06607/) (2021)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Transformer Quality in Linear Time](https://mlsanity.com/paper/2202.10447/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Diverse Weight Averaging for Out-of-Distribution Generalization](https://mlsanity.com/paper/2205.09739/) (2022)
- [A Theory for Emergence of Complex Skills in Language Models](https://mlsanity.com/paper/2307.15936/) (2023)
- [Can Large Language Models Really Improve by Self-critiquing Their Own Plans?](https://mlsanity.com/paper/2310.08118/) (2023)
- [On Linear Identifiability of Learned Representations](https://mlsanity.com/paper/2007.00810/) (2020)
- [GPT-4 Doesn't Know It's Wrong: An Analysis of Iterative Prompting for Reasoning Problems](https://mlsanity.com/paper/2310.12397/) (2023)

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

- [Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structure](https://mlsanity.com/paper/2405.20671/) (2024)
- [Position: Understanding LLMs Requires More Than Statistical Generalization](https://mlsanity.com/paper/2405.01964/) (2024)
- [Interaction Asymmetry: A General Principle for Learning Composable Abstractions](https://mlsanity.com/paper/2411.07784/) (2024)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Position: An Empirically Grounded Identifiability Theory Will Accelerate Self-Supervised Learning Research](https://mlsanity.com/paper/2504.13101/) (2025)
- [The Role of Sparsity for Length Generalization in Transformers](https://mlsanity.com/paper/2502.16792/) (2025)
- [Quantitative Bounds for Length Generalization in Transformers](https://mlsanity.com/paper/2510.27015/) (2025)
- [From Isolation to Entanglement: When Do Interpretability Methods Identify and Disentangle Known Concepts?](https://mlsanity.com/paper/2512.15134/) (2025)
- [Interpret Your Decision: Logical Reasoning Regularization for Generalization in Visual Classification](https://mlsanity.com/paper/2410.04492/) (2024)
- [Neural Networks Generalize on Low Complexity Data](https://mlsanity.com/paper/2409.12446/) (2024)
- [Compositional Hardness of Code in Large Language Models -- A Probabilistic Perspective](https://mlsanity.com/paper/2409.18028/) (2024)
- [The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner](https://mlsanity.com/paper/2507.13332/) (2025)
- [Rule Extrapolation in Language Models: A Study of Compositional Generalization on OOD Prompts](https://mlsanity.com/paper/2409.13728/) (2024)
- [Low-Dimension-to-High-Dimension Generalization And Its Implications for Length Generalization](https://mlsanity.com/paper/2410.08898/) (2024)
- [Out-of-distribution Tests Reveal Compositionality in Chess Transformers](https://mlsanity.com/paper/2510.20783/) (2025)
- [Boule or Baguette? A Study on Task Topology, Length Generalization, and the Benefit of Reasoning Traces](https://mlsanity.com/paper/2602.14404/) (2026)
- [Universal priors: solving empirical Bayes via Bayesian inference and pretraining](https://mlsanity.com/paper/2602.15136/) (2026)
- [When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning](https://mlsanity.com/paper/2607.06720/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [A Theoretical Analysis of Provable Compositional Generalization in Neural Networks: A Necessary and Sufficient Condition](https://mlsanity.com/paper/2505.02627/) (2025)
- [Generalization in LLM Problem Solving: The Case of the Shortest Path](https://mlsanity.com/paper/2604.15306/) (2026)
- [Compositional Reasoning in Language Models under Reinforcement Learning Post-Training](https://mlsanity.com/paper/2609.19465/) (2026)

## Abstract (arXiv)

Out-of-distribution generalization capabilities of sequence-to-sequence models can be studied from the lens of two crucial forms of generalization: length generalization -- the ability to generalize to longer sequences than ones seen during training, and compositional generalization: the ability to generalize to token combinations not seen during training. In this work, we provide first provable guarantees on length and compositional generalization for common sequence-to-sequence models -- deep sets, transformers, state space models, and recurrent neural nets -- trained to minimize the prediction error. We show that limited capacity versions of these different architectures achieve both length and compositional generalization provided the training distribution is sufficiently diverse. In the first part, we study structured limited capacity variants of different architectures and arrive at the generalization guarantees with limited diversity requirements on the training distribution. In the second part, we study limited capacity variants with less structural assumptions and arrive at generalization guarantees but with more diversity requirements on the training distribution. Further, we also show that chain-of-thought supervision enables length generalization in higher capacity counterparts of the different architectures we study.