# Limits of Transformer Language Models on Learning to Compose Algorithms

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 64 references that are in the map.
- First posted on arXiv 8 Feb 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Deep Equilibrium Models](https://mlsanity.com/paper/1909.01377/) (2019)
- [Winoground: Probing Vision and Language Models for Visio-Linguistic Compositionality](https://mlsanity.com/paper/2204.03162/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Scalable Extraction of Training Data from (Production) Language Models](https://mlsanity.com/paper/2311.17035/) (2023)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [COGS: A Compositional Generalization Challenge Based on Semantic Interpretation](https://mlsanity.com/paper/2010.05465/) (2020)
- [Memorization Without Overfitting: Analyzing the Training Dynamics of Large Language Models](https://mlsanity.com/paper/2205.10770/) (2022)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [PonderNet: Learning to Ponder](https://mlsanity.com/paper/2107.05407/) (2021)
- [Solving Challenging Math Word Problems Using GPT-4 Code Interpreter with Code-based Self-Verification](https://mlsanity.com/paper/2308.07921/) (2023)
- [Can Large Language Models Infer Causation from Correlation?](https://mlsanity.com/paper/2306.05836/) (2023)
- [The Devil is in the Detail: Simple Tricks Improve Systematic Generalization of Transformers](https://mlsanity.com/paper/2108.12284/) (2021)
- [Large Language Models as Analogical Reasoners](https://mlsanity.com/paper/2310.01714/) (2023)
- [The ConceptARC Benchmark: Evaluating Understanding and Generalization in the ARC Domain](https://mlsanity.com/paper/2305.07141/) (2023)
- [Compositional Semantic Parsing with Large Language Models](https://mlsanity.com/paper/2209.15003/) (2022)

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

- [Continuous Chain of Thought Enables Parallel Exploration and Reasoning](https://mlsanity.com/paper/2505.23648/) (2025)
- [MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs](https://mlsanity.com/paper/2410.13502/) (2024)
- [Lost in Transmission: When and Why LLMs Fail to Reason Globally](https://mlsanity.com/paper/2505.08140/) (2025)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (2025)
- [Can Large Reasoning Models do Analogical Reasoning under Perceptual Uncertainty?](https://mlsanity.com/paper/2503.11207/) (2025)
- [Behavioural vs. Representational Systematicity in End-to-End Models: An Opinionated Survey](https://mlsanity.com/paper/2506.04461/) (2025)
- [Benchmarking and Understanding Compositional Relational Reasoning of LLMs](https://mlsanity.com/paper/2412.12841/) (2024)
- [Learning Composable Chains-of-Thought](https://mlsanity.com/paper/2505.22635/) (2025)
- [DecompSR: A dataset for decomposed analyses of compositional multihop spatial reasoning](https://mlsanity.com/paper/2511.02627/) (2025)
- [Understanding the Staged Dynamics of Transformers in Learning Latent Structure](https://mlsanity.com/paper/2511.19328/) (2025)
- [Can Language Models Compose Skills In-Context?](https://mlsanity.com/paper/2510.22993/) (2025)
- [The Communication Bottleneck: A Round-Trip Study of Tree-Structured Expression Serialization in Language Models](https://mlsanity.com/paper/2609.21509/) (2026)
- [Beyond the Training Horizon: Mechanisms and Limits of Length Generalization in Looped Transformers](https://mlsanity.com/paper/2609.33144/) (2026)

## Abstract (arXiv)

We analyze the capabilities of Transformer language models in learning compositional discrete tasks. To this end, we evaluate training LLaMA models and prompting GPT-4 and Gemini on four tasks demanding to learn a composition of several discrete sub-tasks. In particular, we measure how well these models can reuse primitives observable in the sub-tasks to learn the composition task. Our results indicate that compositional learning in state-of-the-art Transformer language models is highly sample inefficient: LLaMA requires more data samples than relearning all sub-tasks from scratch to learn the compositional task; in-context prompting with few samples is unreliable and fails at executing the sub-tasks or correcting the errors in multi-round code generation. Further, by leveraging complexity theory, we support these findings with a theoretical analysis focused on the sample inefficiency of gradient descent in memorizing feedforward models. We open source our code at https://github.com/IBM/limitations-lm-algorithmic-compositional-learning.