# ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 32 references that are in the map.
- First posted on arXiv 15 May 2024.

## Builds on (most cited first, 26 of 26)

- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [Voyager: An Open-Ended Embodied Agent with Large Language Models](https://mlsanity.com/paper/2305.16291/) (2023)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Trained Transformers Learn Linear Models In-Context](https://mlsanity.com/paper/2306.09927/) (2023)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Physics of Language Models: Part 3.1, Knowledge Storage and Extraction](https://mlsanity.com/paper/2309.14316/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [GraphGPT: Graph Instruction Tuning for Large Language Models](https://mlsanity.com/paper/2310.13023/) (2023)
- [GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking](https://mlsanity.com/paper/2305.15066/) (2023)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [Physics of Language Models: Part 3.3, Knowledge Capacity Scaling Laws](https://mlsanity.com/paper/2404.05405/) (2024)
- [Physics of Language Models: Part 3.2, Knowledge Manipulation](https://mlsanity.com/paper/2309.14402/) (2023)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [GraphLLM: Boosting Graph Reasoning Ability of Large Language Model](https://mlsanity.com/paper/2310.05845/) (2023)
- [Unveiling Transformers with LEGO: a synthetic reasoning task](https://mlsanity.com/paper/2206.04301/) (2022)
- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [ToolNet: Connecting Large Language Models with Massive Tools via Tool Graph](https://mlsanity.com/paper/2403.00839/) (2024)
- [ControlLLM: Augment Language Models with Tools by Searching on Graphs](https://mlsanity.com/paper/2310.17796/) (2023)
- [GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability](https://mlsanity.com/paper/2403.04483/) (2024)
- [Do Efficient Transformers Really Save Computation?](https://mlsanity.com/paper/2402.13934/) (2024)
- [How to build a cognitive map: insights from models of the hippocampal formation](https://mlsanity.com/paper/2202.01682/) (2022)

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

- [Theoretical limitations of multi-layer Transformer](https://mlsanity.com/paper/2412.02975/) (2024)
- [Unlocking the Future: Exploring Look-Ahead Planning Mechanistic Interpretability in Large Language Models](https://mlsanity.com/paper/2406.16033/) (2024)
- [Density Measures for Language Generation](https://mlsanity.com/paper/2504.14370/) (2025)
- [Generative Models in Decision Making: A Survey](https://mlsanity.com/paper/2502.17100/) (2025)
- [Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations](https://mlsanity.com/paper/2511.05295/) (2025)
- [Transformers Can Navigate Mazes With Multi-Step Prediction](https://mlsanity.com/paper/2412.05117/) (2024)
- [Revisiting the Graph Reasoning Ability of Large Language Models: Case Studies in Translation, Connectivity and Shortest Path](https://mlsanity.com/paper/2408.09529/) (2024)
- [Understanding and Enhancing the Planning Capability of Language Models via Multi-Token Prediction](https://mlsanity.com/paper/2509.23186/) (2025)
- [Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective](https://mlsanity.com/paper/2509.22613/) (2025)
- [Efficient Estimation of Kernel Surrogate Models for Task Attribution](https://mlsanity.com/paper/2602.03783/) (2026)
- [Uncovering Graph Reasoning in Decoder-only Transformers with Circuit Tracing](https://mlsanity.com/paper/2509.20336/) (2025)
- [A Taxonomy of Transcendence](https://mlsanity.com/paper/2508.17669/) (2025)
- [Internal Planning in Language Models: Characterizing Horizon and Branch Awareness](https://mlsanity.com/paper/2509.25260/) (2025)
- [Understanding Parallel Samplers in Masked Diffusion via Random Walks on Graphs](https://mlsanity.com/paper/2606.22976/) (2026)
- [SWI: Speaking with Intent in Large Language Models](https://mlsanity.com/paper/2503.21544/) (2025)
- [Understanding the learned look-ahead behavior of chess neural networks](https://mlsanity.com/paper/2505.21552/) (2025)
- [GraphGhost: Tracing Structures Behind Large Language Models](https://mlsanity.com/paper/2510.08613/) (2025)
- [When Do Hallucinations Arise? A Graph Perspective on the Evolution of Path Reuse and Path Compression](https://mlsanity.com/paper/2604.03557/) (2026)

## Abstract (arXiv)

Planning is a crucial element of both human intelligence and contemporary large language models (LLMs). In this paper, we initiate a theoretical investigation into the emergence of planning capabilities in Transformer-based LLMs via their next-word prediction mechanisms. We model planning as a network path-finding task, where the objective is to generate a valid path from a specified source node to a designated target node. Our mathematical characterization shows that Transformer architectures can execute path-finding by embedding the adjacency and reachability matrices within their weights. Furthermore, our theoretical analysis of gradient-based learning dynamics reveals that LLMs can learn both the adjacency and a limited form of the reachability matrices. These theoretical insights are then validated through experiments, which demonstrate that Transformer architectures indeed learn the adjacency and an incomplete reachability matrices, consistent with our theoretical predictions. When applying our methodology to the real-world planning benchmark Blocksworld, our observations remain consistent. Additionally, our analyses uncover a fundamental limitation of current Transformer architectures in path-finding: these architectures cannot identify reachability relationships through transitivity, which leads to failures in generating paths when concatenation is required. These findings provide new insights into how the internal mechanisms of autoregressive learning facilitate intelligent planning and deepen our understanding of how future LLMs might achieve more advanced and general planning-and-reasoning capabilities across diverse applications.