研究证明Transformer可学习图搜索DFS
热点事件持续更新
研究证明Transformer可学习图搜索DFS
1 篇报道1 个报道来源2 小时前更新
先了解这件事
AI 综述
Xutao Ma与Somayeh Sojoudi发布arXiv论文（2611.13594），以有向图上的路径查找作为多步推理的符号抽象，从理论上证明Transformer可以学习图搜索。具体结论是：单层Transformer在稠密图上实现DFS子节点选择原语需要Ω(N²)规模，两层Transformer只需O(N log N)规模即可完成完整DFS；k层模型可达的前瞻视野为1+2^(k-3)，随深度呈指数增长。
AI 根据报道生成 · 1 小时前更新
最新进展11月11日 13:00
研究证明 Transformer 可学习图搜索：训练动力学与深度的指数级威力报道时间线
沿着报道，了解事件的不同侧面。
11月11日
- arXiv cs.AI研究证明 Transformer 可学习图搜索：训练动力学与深度的指数级威力
一项 arXiv 理论研究以有向图上的路径查找为多步推理的符号抽象，分析 Transformer 实现图搜索的机制。结果证明单层 Transformer 在稠密图上实现 DFS 子节点选择原语需要 Ω(N²) 规模，而两层 Transformer 只需 O(N log N) 规模即可完成完整 DFS；且 k 层模型的可达前瞻视野为 1+2^(k-3)，随深度呈指数增长。
本事件热度走势
还没有足够的连续观测数据，暂不绘制趋势。