研究证明 Transformer 可学习图搜索：训练动力学与深度的指数级威力
Transformers Provably Learn Graph Search: Training Dynamics and the Exponential Power of Depth
AI 导读
一项 arXiv 理论研究以有向图上的路径查找为多步推理的符号抽象，分析 Transformer 实现图搜索的机制。结果证明单层 Transformer 在稠密图上实现 DFS 子节点选择原语需要 Ω(N²) 规模，而两层 Transformer 只需 O(N log N) 规模即可完成完整 DFS；且 k 层模型的可达前瞻视野为 1+2^(k-3)，随深度呈指数增长。
正文 · 原文
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 $\Omega(N^2)$ size on dense graphs to implement the key DFS child-selection primitive. While a two-layer transformer implements full DFS with $O(N\log(N))$ 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 $k\geq3$, a $k$-layer transformer implements a bounded-reachability DFS policy with look-ahead horizon $1+2^{k-3}$, 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.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.13594 [cs.AI] |
| (or arXiv:2611.13594v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2611.13594 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Xutao Ma [view email]
[v1]
Tue, 10 Nov 2026 05:09:36 UTC (168 KB)
来源：arXiv cs.AI · arxiv.org