arXiv cs.AI· Xutao Ma, Somayeh Sojoudi·· 10 小时前AI 评分31
Transformer 可证明学会图搜索：训练动力学与深度的指数级能力
Transformers Provably Learn Graph Search: Training Dynamics and the Exponential Power of Depth
AI 导读
研究证明单层 Transformer 在稠密图上实现 DFS 子节点选择原语需 Ω(N²) 规模，而两层 Transformer 仅需 O(N log(N)) 即可完成完整 DFS，说明第二层对近线性 DFS 推理既必要又充分。
正文 · 原文
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