Transformers Provably Learn Graph Search: Training Dynamics and the Exponential Power of Depth
Organizations: UC Berkeley
Abstract
Large Language Models (LLMs) have achieved remarkable progress on complex reasoning tasks, yet the mechanisms by which they acquire reasoning capabilities and the efficiency of their reasoning remain poorly understood. In this paper, we investigate the path-finding problem over directed graphs, a symbolic abstraction of multi-step reasoning. We first characterize the architectural requirements for this task, proving that one-layer transformers require size on dense graphs to implement the key DFS child-selection primitive. While a two-layer transformer implements full DFS with size. Thus, a second layer is necessary and sufficient for near-linear DFS reasoning. We then extend this expressivity analysis to deeper models: for every , a -layer transformer implements a bounded-reachability DFS policy with look-ahead horizon , establishing an exponential increase in reachability horizon with depth. Finally, going beyond expressivity, given appropriately curated training data, we show that two-layer transformers can provably learn to execute DFS via gradient flow and generalize to unseen graphs. Together, our results provide a mechanistic account of how transformers implement graph search, how depth expands bounded look-ahead, and how such reasoning algorithms can emerge through training.
Figures & tables
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
| Node type ( ) | Node logits |
|---|---|
| Unvisited child of ( ) | |
| Visited child of ( ) | |
| Non-child |
| Node type | If ? | Node logits |
|---|---|---|
| Parent of | No | |
| Parent of | Yes | |
| Tree child of (entered from ) | No | |
| , neither parent nor | Yes | |
| Any other | No | |
| No |
LLM Reasoning with Graphs
Large language model reasoning with graphs uses structured relationships to support multi-step inference, evidence retrieval, and planning.
See all 227 papers