Transformer模型一经问世，便迅速刷新了机器翻译领域的性能上限。尽管最初是为特定任务设计，但这一革命性架构很快被证明能够轻松迁移至多种场景。不久之后，Transformer便成为行业标配——甚至被应用于原本未曾考虑的数据类型，例如图像及其他序列数据。
与此同时，研究者们持续探索如何优化该架构并寻找替代方案，核心目标在于降低计算成本——自注意力机制那令人头疼的二次方复杂度。究竟哪种架构在计算效率上更具优势，至今尚无定论。不过，有一点已十分明确：Transformer真正的杀手锏，在于其展现出的强大推理能力。
如何分析神经网络的推理能力？
最常用的方法之一，是研究架构内部表征所能执行的算法。整个领域为此已开辟出专门分支：神经算法推理（Neural Algorithmic Reasoning）。Transformer能否实现泛化？能否通过规模扩展解决更多问题？这些至今仍是悬而未决的热门议题。有人认为Transformer具备普适推理能力，也有人视其为通往人工通用智能的关键钥匙——前提是能够将其扩展至足够规模。目前，Transformer在自然语言处理、时间序列甚至计算机视觉领域均交出了亮眼成绩单，但测试其极限同样重要：不仅要与其他架构对比，还需为未来建立基准。近期一项研究便将焦点对准了图神经网络这一特定方向。今天要介绍的论文，题为“Understanding Transformer Reasoning Capabilities via Graph Algorithms”。
这听起来或许有些奇怪，但近两年Transformer（以及大语言模型）与图（Graphs）的关系愈发紧密。首先，自注意力机制本身即可视为一种图结构。其次，图（尤其是知识图谱）可用于扩展Transformer的能力。第三，图是复杂推理的理想抽象——思维链及其他技术，本质上也可理解为图的某种抽象。此外，许多图问题可通过简单架构解决，但另一些则需要复杂推理和先进的图神经网络（GNNs）才能胜任。
图计算在过去的人工智能与计算领域，已成为多个成功设计的基石，例如蛋白质预测领域的AlphaFold。众多推理任务均可转化为图的推理问题——这也是Tree of Thoughts、Graph of Thoughts等方法得以成功的原因。从这一角度看，图确实是测试Transformer能力的最佳试金石。然而，尽管理论前提已明确，严格分析仍非易事：图推理任务可归类至已知的计算类别，但当我们评估神经网络解决这些任务的实际能力时，情况变得复杂得多。对于Transformer而言，我们不仅关心固定深度下的表现，还关注通过改变层数，模型能否学到更简单或更复杂的表征——深度变化至关重要。同样，Transformer也能在宽度上增长，这在重新关注上下文长度时尤为相关。论文作者将任务分为三类，难度逐级递增，需要越来越复杂的模型才能完成：1. 检索任务。节点计数、边计数、边存在性检查、节点度数等，基本一次查找即可完成，仅需一个Transformer层和一个小型嵌入。2. 可并行化任务。连通性、连接节点、循环检查（以及更复杂的二分性、平面性等），使用对数深度的Transformer即可解决。3. 搜索任务。最短路径及其他需要更多推理的任务，这便依赖于模型的扩展能力。
论文中进行了多项理论分析，展示了Transformer如何解决这些任务，以及解决它们所需的维度要求。另一个值得关注的点是，作者还分析了“暂停标记（pause tokens）”带来的影响。
结果
在对Transformer的推理能力进行实证分析后，他们采用了不同的实验方式：使用从头训练的模型（最多60M参数），对预训练的Transformer（T5，11B参数）进行微调，再测试提示技巧，同时与图神经网络（GNNs）进行对比。所有实验均在GraphQA基准任务上完成。
图推理算法可分为局部和全局两类。前者在局部聚合信息（节点及其邻居），后者则模拟节点之间可能的长距离全局连接。论文主要聚焦全局任务，例如评估连通性或计算最短路径——这些都需要分析图的整体结构。在少量样本的情况下，图神经网络（GNNs）在这些任务中效率更高；但随着样本数量增加，Transformer的表现反超——Transformer的归纳偏置较弱，需要更多示例才能达到最佳学习效果。对预训练的Transformer进行微调，也带来了显著的正面影响。
此前研究已指出，对于GNN而言，以参数效率方式解决连通性存在固有局限。而微调后的Transformer在该任务上表现更佳，对最短路径同样有效。不过，尽管Transformer在全局任务上更具优势，但GNN在需要局部推理的任务中似乎更胜一筹：
“这表明，GNN对于学习那些可以通过专门关注局部启发式解决的图推理任务，具有有益的归纳偏见。”（论文原文翻译）
在GNN中，消息传递框架使得节点与邻居之间的信息交换十分顺畅（每增加一层，相当于在图里多跳一步）。相比之下，注意力机制会计算每对标记之间的关系，因此它在全局任务上表现更好，但在数据量较少的情况下，识别重要的局部关系反而更为困难。
作者还测试了大语言模型（LLM）的情况：对表现优异的Transformer进行微调，效果比直接使用提示方法更好。尽管在训练过程中，LLM已从语料库中见过图数据（并非完全陌生），但结果仍表明，针对特定任务，专业化的小模型更为可靠，且微调比直接使用提示效果显著更优。
总结这篇论文系统展示了Transformer在图推理上的能力，涵盖了不同的参数缩放模式。许多问题均可重新表述为图问题，因此这篇文章值得深入阅读。论文还指出，某些能力的展现需要足够的网络深度——Transformer必须达到一定层数才能解决问题。例如，在需要全局推理的任务中，Transformer超越了GNN，这得益于自注意力机制允许高效评估长距离依赖关系。这些发现为使用Transformer处理具有复杂全局依赖性的图推理任务，提供了扎实的理论与实证支撑。