mlsanityData to 7 Oct 2026

What Algorithms can Transformers Learn? A Study in Length Generalization

arXiv 2310.16028 ↗First posted 24 Oct 2023cs.LG cs.AI cs.CLcited by 198

Not on the map. Why?

Cited by 26 in LLM reasoning, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Large language models exhibit surprising emergent generalization properties, yet also struggle on many simple reasoning tasks such as arithmetic and parity. This raises the question of if and when Transformer models can learn the true algorithm for solving a task. We study the scope of Transformers' abilities in the specific setting of length generalization on algorithmic tasks. Here, we propose a unifying framework to understand when and how Transformers can exhibit strong length generalization on a given task. Specifically, we leverage RASP (Weiss et al., 2021) -- a programming language designed for the computational model of a Transformer -- and introduce the RASP-Generalization Conjecture: Transformers tend to length generalize on a task if the task can be solved by a short RASP program which works for all input lengths. This simple conjecture remarkably captures most known instances of length generalization on algorithmic tasks. Moreover, we leverage our insights to drastically improve generalization performance on traditionally hard tasks (such as parity and addition). On the theoretical side, we give a simple example where the "min-degree-interpolator" model of learning from Abbe et al. (2023) does not correctly predict Transformers' out-of-distribution behavior, but our conjecture does. Overall, our work provides a novel perspective on the mechanisms of compositional generalization and the algorithmic capabilities of Transformers.

Key facts. Cited by 198 papers in the map (data through 7 Oct 2026). Builds on 46 of its 62 references that are in the map. First posted on arXiv 24 Oct 2023.

Builds on

46 of 62 references.

References · 46

  1. 2017Attention Is All You Needcited by 59,932
  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. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  5. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  6. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  7. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  8. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  9. 2022Solving Quantitative Reasoning Problems with Language Modelscited by 1,359
  10. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,085
  11. 2022Measuring and Narrowing the Compositionality Gap in Language Modelscited by 1,054
  12. 2022In-context Learning and Induction Headscited by 930
34 more
  1. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
  2. 2023Progress measures for grokking via mechanistic interpretabilitycited by 822
  3. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 700
  4. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  5. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 496
  6. 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 319
  7. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  8. 2023Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Taskscited by 243
  9. 2022Exploring Length Generalization in Large Language Modelscited by 204
  10. 2023How does GPT-2 compute greater-than?: Interpreting mathematical abilities in a pre-trained language modelcited by 199
  11. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 191
  12. 2021Thinking Like Transformerscited by 182
  13. 2023The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networkscited by 153
  14. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  15. 2021Investigating the Limitations of Transformers with Simple Arithmetic Taskscited by 136
  16. 2023Representational Strengths and Limitations of Transformerscited by 132
  17. 2022Faithful Reasoning Using Large Language Modelscited by 130
  18. 2022Text and Patterns: For Effective Chain of Thought, It Takes Two to Tangocited by 128
  19. 2015Neural GPUs Learn Algorithmscited by 118
  20. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  21. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 110
  22. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 99
  23. 2020Compositional Generalization in Semantic Parsing: Pre-training vs. Specialized Architecturescited by 95
  24. 2021Neural Algorithmic Reasoningcited by 92
  25. 2023Testing the General Deductive Reasoning Capacity of Large Language Models Using OOD Examplescited by 84
  26. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  27. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  28. 2021Linear algebra with transformerscited by 62
  29. 2020How Can Self-Attention Networks Recognize Dyck-n Languages?cited by 51
  30. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 29
  31. 2021Symbolic Brittleness in Sequence Models: on Systematic Generalization in Symbolic Mathematicscited by 27
  32. 2023Transformer Working Memory Enables Regular Language Reasoning and Natural Language Length Extrapolationcited by 13
  33. 2022Benchmarking Compositionality with Formal Languagescited by 12
  34. 2023Improving Length-Generalization in Transformers via Task Hintingcited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 80; 2025: 66; 2026: 48.

198 papers.

Sort:

By area:

  1. 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 533
  2. 2024CRUXEval: A Benchmark for Code Reasoning, Understanding and Executioncited by 294
  3. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 208
  4. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  5. 2024Tokenization counts: the impact of tokenization on arithmetic in frontier LLMscited by 112
  6. 2023Mechanistically analyzing the effects of fine-tuning on procedurally defined taskscited by 110
  7. 2024Rethinking Interpretability in the Era of Large Language Modelscited by 110
  8. 2024Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Processcited by 107
  9. 2024Can Mamba Learn How to Learn? A Comparative Study on In-Context Learning Taskscited by 104
  10. 2024A Primer on the Inner Workings of Transformer-based Language Modelscited by 83
  11. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 82
  12. 2024Transformers Can Do Arithmetic with the Right Embeddingscited by 77
38 more
  1. 2024Why are Sensitive Functions Hard for Transformers?cited by 74
  2. 2024Premise Order Matters in Reasoning with Large Language Modelscited by 71
  3. 2025All Roads Lead to Likelihood: The Value of Reinforcement Learning in Fine-Tuningcited by 58
  4. 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
  5. 2024Physics of Language Models: Part 2.2, How to Learn From Mistakes on Grade-School Math Problemscited by 49
  6. 2024Why Larger Language Models Do In-context Learning Differently?cited by 44
  7. 2024Neural Redshift: Random Networks are not Random Functionscited by 43
  8. 2024Number Cookbook: Number Understanding of Language Models and How to Improve Itcited by 41
  9. 2024The Unreasonable Effectiveness of Easy Training Data for Hard Taskscited by 40
  10. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  11. 2024Talking Heads: Understanding Inter-layer Communication in Transformer Language Modelscited by 39
  12. 2025Between Circuits and Chomsky: Pre-pretraining on Formal Languages Imparts Linguistic Biasescited by 36
  13. 2024How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpadcited by 35
  14. 2023Length Extrapolation of Transformers: A Survey from the Perspective of Positional Encodingcited by 32
  15. 2024DAPE: Data-Adaptive Positional Encoding for Length Extrapolationcited by 30
  16. 2025Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challengescited by 30
  17. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  18. 2024The CLRS-Text Algorithmic Reasoning Language Benchmarkcited by 28
  19. 2024Out-of-distribution generalization via composition: a lens through induction heads in Transformerscited by 28
  20. 2025LongProc: Benchmarking Long-Context Language Models on Long Procedural Generationcited by 28
  21. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  22. 2024Selective Attention Improves Transformercited by 26
  23. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  24. 2024Universal Length Generalization with Turing Programscited by 25
  25. 2024Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregationcited by 22
  26. 2024On Provable Length and Compositional Generalizationcited by 22
  27. 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 22
  28. 2023Compositional Capabilities of Autoregressive Transformers: A Study on Synthetic, Interpretable Taskscited by 21
  29. 2024Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannotcited by 21
  30. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 21
  31. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21
  32. 2025FoNE: Precise Single-Token Number Embeddings via Fourier Featurescited by 21
  33. 2024Mixture of Parrots: Experts improve memorization more than reasoningcited by 20
  34. 2024What Can Transformer Learn with Varying Depth? Case Studies on Sequence Learning Taskscited by 19
  35. 2024Representation Shattering in Transformers: A Synthetic Study with Knowledge Editingcited by 18
  36. 2025Long-Context Generalization with Sparse Attentioncited by 18
  37. 2024A Philosophical Introduction to Language Models - Part II: The Way Forwardcited by 17
  38. 2025Finite State Automata Inside Transformers with Chain-of-Thought: A Mechanistic Study on State Trackingcited by 17

50 most cited of 198 All 198 (JSON)