跳到正文
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