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 推理既必要又充分。
正文 · AI 翻译
摘要：大型语言模型（LLMs）在复杂推理任务上取得了显著进展，但它们获得推理能力的机制以及推理效率仍鲜为人知。本文研究有向图上的路径查找问题，这是多步推理的一种符号抽象。我们首先刻画该任务对架构的要求，证明单层 transformer 在稠密图上需要 $\Omega(N^2)$ 的规模才能实现关键的 DFS 子节点选择原语。而两层 transformer 以 $O(N\log(N))$ 的规模实现完整的 DFS。因此，第二层对于近线性 DFS 推理是必要且充分的。随后我们将这一表达能力分析扩展到更深的模型：对于每个 $k\geq3$，$k$ 层 transformer 实现具有前瞻视野 $1+2^{k-3}$ 的有界可达性 DFS 策略，从而确立了可达性视野随深度呈指数增长。最后，超越表达能力，在给定适当整理的训练数据下，我们证明两层 transformer 可以通过梯度流可证明地学会执行 DFS，并泛化到未见过的图。总之，我们的结果提供了关于 transformer 如何实现图搜索、深度如何扩展有界前瞻，以及此类推理算法如何通过训练涌现的机制性解释。
| 主题： | 人工智能（cs.AI） |
| 引用为： | arXiv:2611.13594 [cs.AI] |
| （或 arXiv:2611.13594v1 [cs.AI] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.13594 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Xutao Ma [查看邮箱]
[v1]
2026年11月10日 星期二 05:09:36 UTC（168 KB）
来源：arXiv cs.AI · arxiv.org