Research map / Large language models / Agents, code and math
ALPINE: Unveiling The Planning Capability of Autoregressive Learning in Language Models
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.
Theoretically and empirically studies how autoregressively trained Transformers learn path-finding (a planning proxy), showing they encode adjacency and observed reachability but fail on transitive reachability requiring path concatenation.
Problem
How next-word prediction Transformers acquire planning ability, modeled as path-finding in directed graphs, and what limits their learning of reachability.
Approach
Models planning as path-finding on graphs; proves a 1-layer Transformer can encode adjacency and reachability matrices, and shows via gradient-dynamics analysis of a simplified 1-layer model that cross-entropy training learns only observed (non-transitive) reachability, so it fails on paths requiring concatenation of training segments.
Key results
- Transformers with embedding size 120 achieve high path-finding accuracy on 100-node graphs, and accuracy drops with more nodes relative to embedding size.
- Accuracy on degree-2 and degree-3+ source-target pairs (requiring concatenation of training path segments) is much lower than on degree-0 and degree-1 pairs in most settings, even for 6-layer 6-head models.
- Learned W^V matches observed reachability but shows no weight gap for real-minus-observed (unobserved transitive) reachability pairs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of graph nodes | Transformer path-finding models · Path-finding test datasets | accuracy | Hurt |
| Increase the number of attention heads (ablation) | Transformer path-finding models · Path-finding test datasets | accuracy | No clear effect |
| Increase the number of layers (ablation) | Transformer path-finding models · Path-finding test datasets | accuracy | Helped |
| Increase embedding size relative to graph size (ablation) | Transformer path-finding models · Path-finding test datasets | accuracy | Helped |
| Use degree-2-or-higher source-target pairs requiring concatenation of path segments | Transformer path-finding models · Path-finding test dataset, high-degree pairs | accuracy | Hurt |
Surprising findings
- Even 6-layer, 6-head Transformers fail to generate paths for pairs connected only via concatenated training path segments.
Limitations
- Theoretical analysis uses a simplified 1-layer, 1-head Transformer with removed layer norms and fixed attention on the target token.
- Accuracy degrades for larger graphs when embedding size is small relative to node count.
- Blocksworld results are only summarized as consistent with the path-finding findings.
Experimental setup
Datasets: synthetic random DAG path-finding data Blocksworld
Benchmarks: synthetic path-finding test set Blocksworld
Metrics: accuracy of valid path generation accuracy by reachability degree
Builds on: GPT architecture Algorithm simulation with Transformers
Closest papers by meaning
- Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Tasks (NeurIPS 2026 · similarity 0.90)
- LLMs Can Plan Only If We Tell Them (ICLR 2025 · similarity 0.89)
- Language Control Diffusion: Efficiently Scaling through Space, Time, and Tasks (ICLR 2024 · similarity 0.89)
- Non-myopic Generation of Language Models for Reasoning and Planning (ICLR 2025 · similarity 0.88)
- Large Language Models as Planning Domain Generators (Student Abstract) (AAAI 2024 · similarity 0.88)
- TravelPlanner: A Benchmark for Real-World Planning with Language Agents (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.