Transformer学算法解图连通性，数据范围决定能否学会真正方法
Transformers Provably Learn Algorithmic Solutions for Graph Connectivity, But Only with the Right Data
- 用解耦Transformer证明层数L可处理直径≤3^L的图
- 训练数据在容量内时模型学到矩阵幂算法，否则只学度数启发式
- 限定训练数据范围能让模型准确学会算法，适合研究模型学习机制者
Transformer常无法学习可泛化的算法，而是依赖脆弱的启发式策略。以图连通性为测试场景，我们从理论和实证两方面解释该现象。考虑一种简化版Transformer——解耦Transformer，证明一个L层模型能处理直径不超过3^L的图，其计算方式等价于反复计算邻接矩阵的幂。通过分析训练动态发现，模型是否学习到此算法，取决于多数训练样本是否在模型容量范围内。容量内的图（直径≤3^L）促使模型学习算法解，而超出容量的图则诱导其学习基于节点度数的简单启发式。最后，实验表明：若限制训练数据始终在模型容量内，标准与解耦Transformer均能学会精确算法。
原文摘要 · Abstract (English)
Transformers often fail to learn generalizable algorithms, instead relying on brittle heuristics. Using graph connectivity as a testbed, we explain this phenomenon both theoretically and empirically. We consider a simplified Transformer architecture, the Disentangled Transformer, and prove that an $L$-layer model can compute connectivity in graphs with diameters up to $3^L$, implementing an algorithm equivalent to computing powers of the adjacency matrix. By analyzing training dynamics, we prove that whether the model learns this strategy hinges on whether most training instances are within this model capacity. Within-capacity graphs (diameter $\leq 3^L$) drive the learning of the algorithmic solution while beyond-capacity graphs drive the learning of a simple heuristic based on node degrees. Finally, we empirically show that restricting training data to stay within a model's capacity makes both standard and Disentangled Transformers learn the exact algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。