Research map / Large language models / Language, safety and interpretability
Limits of Transformer Language Models on Learning to Compose Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that LLaMA models trained from scratch need more samples to learn compositions of pointer-execution, HSS and multiplication sub-tasks than the sum needed for the sub-tasks, backs this with a theoretical sample-inefficiency bound for gradient descent, and finds GPT-4 and Gemini-Pro fail at these compositions via prompting.
Problem
Whether Transformer language models learn compositions of discrete sub-tasks sample-efficiently, reusing primitives learned from sub-tasks, instead of relearning the composition from scratch.
Approach
Defines four hypotheses (H1-H4) on sample efficiency of composition learning, introduces two new pointer-execution tasks (PEN, PERM) with independently observable sub-tasks, and combines LLaMA training experiments, prompting experiments on GPT-4 and Gemini-Pro, and a complexity-theoretic bound on gradient descent memorization.
Key results
- LLaMA (150M) needs about 1000K samples to learn PEN, roughly 10x the sum of the sub-task sample requirements, and its composition is not reused from sub-tasks.
- GPT-4 with sub-task CoT reaches 42% task accuracy on PERM, while all prompting variants score 0% on PEN except one setting reaching 19% with a code interpreter and hand-crafted hints.
- A discrete hill-climbing learner with 121 parameters can learn PEN from a single sample given the sub-tasks as primitives.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add task description to few-shot examples | GPT-4 and Gemini-Pro · PEN | task accuracy: 0.00 -> 0.00 | No clear effect |
| Add standard chain-of-thought prompting | GPT-4 and Gemini-Pro · PEN | task accuracy: 0.00 -> 0.00 | No clear effect |
| Use Few-shot CoT examples that demonstrate each pointer-matching step | GPT-4 and Gemini-Pro · PEN | task accuracy: 0.00 | No clear effect |
| Use Sub-task CoT examples that separate matching from neighbor output | Gemini-Pro · PEN | match accuracy: 0.03 -> 0.33 | Helped |
| Remove additional attention traps (ablation) | GPT-4 · PEN | match accuracy: 0.23 -> 0.39 | Helped |
| Remove additional attention traps (ablation) | GPT-4 · PEN | task accuracy: 0.00 -> 0.00 | No clear effect |
| Use hand-crafted Sub-task CoT to enumerate words and explicitly compute multicounts | GPT-4 · PERM | task accuracy: 0.14 -> 0.42 | Helped |
| Train on the sub-tasks alongside the main task (ablation) | LLaMA · PEN | task accuracy | No clear effect |
| Train on the sub-tasks alongside the main task (ablation) | LLaMA · PERM | task accuracy | No clear effect |
| Train on the sub-tasks alongside the main task (ablation) | LLaMA · HSS and MUL | task accuracy | No clear effect |
| Add auxiliary prediction heads and auxiliary losses (ablation) | 28 M-parameter LLaMA · PEN | accuracy: 0% -> learn PEN with 300 K samples | Helped |
| Fine-tune a PEN-pretrained model on PEV | LLaMA · PEV | accuracy | Helped |
Surprising findings
- Training with sub-task data gives LLaMA little to no benefit over training on the composed task alone.
- GPT-4 code interpreter outputs executable code but in 65% of sampled cases gives a wrong answer and often fails to self-correct, never using the provided example to verify its solution.
Limitations
- Does not propose practical methods to fix the identified compositional learning inefficiency.
- Evaluated on a limited collection of synthetic algorithmic tasks rather than natural tasks.
- Theoretical bound assumes constant-step memorization and fixed-depth feedforward models, and applies asymptotically.
Experimental setup
Datasets: PEN PERM HSS MUL PEV Cpy RCpy PE PER PEM SSE ADD
Benchmarks: PEN PERM HSS MUL
Metrics: task accuracy match accuracy termination accuracy
Baselines: GPT-4 Gemini-Pro LLaMA w/o sub-tasks auxiliary loss LLaMA
Builds on: chain-of-thought prompting Pointer Value Retrieval C-PVR Universal Transformer
Closest papers by meaning
- Task Generalization with Autoregressive Compositional Structure: Can Learning from $D$ Tasks Generalize to $D^T$ Tasks? (ICML 2025 · similarity 0.89)
- Assign and Add: A Mechanistic Study of Compositional Arithmetic (NeurIPS 2026 · similarity 0.88)
- In-Context Compositional Learning vis Sparse Coding Transformer (NeurIPS 2025 · similarity 0.88)
- Learning to grok: Emergence of in-context learning and skill composition in modular arithmetic tasks (NeurIPS 2024 · similarity 0.88)
- Compositional Reasoning in Language Models under Reinforcement Learning Post-Training (NeurIPS 2026 · similarity 0.88)
- Compositional Capabilities of Autoregressive Transformers: A Study on Synthetic, Interpretable Tasks (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.