单层变压器无法解决归纳头任务
内容提要
这篇论文探讨了Transformer模型的电路复杂度及其计算能力，证明了其在形式语言上的限制。研究表明，Transformer的复杂性与输入规模相关，自注意力层的数量影响推理能力。提出了新的计算方法以降低计算复杂度，提高大型语言模型的训练效率。
延伸解读
理论限制与架构选择
文章指出，使用软饱和注意力机制的Transformer可被常数深度阈值电路模拟，这限制了其在形式语言上的能力。同时，单层单注意头的解码器型Transformer在图灵完备性上依赖于词嵌入的稀疏性。这些结论提示，架构的深度和注意力机制的选择会直接影响模型的理论计算能力，并非所有Transformer变体都具备相同的表达能力。
深度与推理能力的权衡
研究表明，只有一个注意力层的Transformer在记忆任务上表现优异，但在推理和泛化方面不足，至少需要两个注意力层才能进行推理和泛化，而上下文泛化可能需要三个注意力层。这意味着在实际应用中，若任务涉及复杂推理，增加注意力层数可能是必要的，但也会带来计算开销。
中间生成扩展计算能力
通过允许Transformer在回答问题前生成中间令牌序列，可以显著扩展其解码器的计算能力，使其能够识别所有正则语言和上下文敏感语言，并解决多项式时间可解问题。这为提升模型推理能力提供了一种思路：在推理阶段引入中间步骤，可能比单纯增加模型规模更有效。
通信复杂度与幻觉根源
文章将大型语言模型中的幻觉归因于通信复杂性，指出Transformer层在函数定义域足够大时无法进行函数组合。这意味着模型在处理需要多步组合推理的任务时可能固有地容易出错，尤其是在定义域较大的情况下。理解这一限制有助于合理评估模型输出，并设计缓解策略。
Q&A
Transformer模型的电路复杂度是什么？
Transformer模型的电路复杂度可以被常数深度阈值电路模拟，限制了其在形式语言上的能力。
单层单注意头的Transformer架构是否图灵完备？
在合理假定下，单层单注意头的解码器型Transformer架构是图灵完备的。
增加中间生成的数量对Transformer有什么影响？
增加中间生成的数量可以显著扩展Transformer解码器的计算能力，使其能够识别所有正则语言和上下文敏感语言。
自注意力层的数量对Transformer的推理能力有何影响？
只有一个注意力层的Transformer在记忆方面表现出色，但推理和泛化能力需要至少两个注意力层。
通信复杂性在大型语言模型中有什么作用？
通信复杂性是大型语言模型中幻觉的根本原因，影响Transformer层在函数组合中的能力。
如何降低Transformer模型的计算复杂度？
提出了一种新的快速梯度计算方法，能够在几乎线性时间内计算多层Transformer模型的梯度，从而显著降低计算复杂度。
