Transformer 何时学习图连通性的启发式算法？

Transformer 通常无法学习可泛化的算法，而是依赖脆弱的启发式方法。 我们以图连通性为测试平台，从理论和经验上解释了这一现象。 我们考虑了一个简化的 Transformer 架构，即解耦 Transformer， 并证明 L 层模型具有解决直径恰好达到 3^L 的图的能力，实现了一个等同于计算邻接矩阵幂的算法。 我们分析了训练动力学，并表明所学策略取决于大多数训练实例是否在模型容量之内。 容量内图（直径 ≤ 3^L）驱动正确算法解决方案的学习，而容量外图驱动基于节点度的简单启发式方法的学习。 最后，我们通过实验证明，将训练数据限制在模型容量之内可以使标准 Transformer 和解耦 Transformer 都学习精确算法，而不是基于度的启发式方法。