arXiv · AI· Xutao Ma, Somayeh Sojoudi·· 9 天前AI 评分36
论文证明 Transformer 可学习图搜索:训练动力学及深度指数优势
Transformers Provably Learn Graph Search: Training Dynamics and the Exponential Power of Depth
AI 导读
研究证明两层 Transformer 需 $O(N\log N)$ 规模实现完整 DFS,比单层高效。 对于 $k\geq3$ 的模型,可达范围随深度呈指数增长,前视视野为 $1+2^{k-3}$。 该结果揭示了 Transformer 实现图搜索的机制,证明算法可通过梯度流学习并泛化。
来源:arXiv · AI · arxiv.org