Understanding Transformer Reasoning Capabilities via Graph Algorithms

哪些Transformer缩放方案能够完美解决不同类别的算法问题？虽然基于Transformer的神经网络已经取得了巨大的经验性进展，但是对于它们在现实参数范围内的算法推理能力的理论理解还很缺乏。我们从网络的深度、宽度和算法执行所需的额外令牌数量等方面来探究这个问题。我们的新型表征层次将9个算法推理问题分成了不同的类别，这些类别可以在不同的现实参数缩放方案下由Transformer解决。我们证明对于图连通性等任务，对数深度是必要且充分的，而具有小的嵌入维度的单层Transformer可以解决上下文检索任务。我们还使用GraphQA基准测试对我们的理论分析进行了充分的经验证据支持。这些结果表明，Transformer在许多图形推理任务上表现出色，甚至优于专门的图形神经网络。

论文探讨transformer模型在不同参数规模下解决不同算法问题的能力，旨在提供理论支持

通过网络的深度、宽度和额外token数目的不同组合，将9个算法推理问题分为不同的类别，证明对于图连通性等任务，对数深度是必要且充分的，而具有小嵌入维度的单层transformer可以解决上下文检索任务

使用GraphQA基准测试，论文提供了大量实证证据支持理论分析，表明transformer在许多图推理任务上表现出色，甚至优于专门的图神经网络

相关研究包括《Attention Is All You Need》、《Graph Attention Networks》等