Transformer, 并行计算，和对数深度
内容提要
该文综述Transformer计算能力研究：证明其可由常深度对数空间电路模拟，若L≠P则无法精确求解线性等式或上下文无关语法成员问题，揭示并行化模型的固有局限；并探讨注意力复杂度、线性注意力、门控注意力及通用逼近性等改进方向。
延伸解读
理论限制：Transformer 的并行计算瓶颈
文章指出，若 L≠P，Transformer 无法精确求解线性等式或上下文无关语法成员问题。这揭示了其作为并行模型的固有局限：常深度对数空间电路模拟意味着某些串行计算任务难以高效处理。读者需注意，这一结论基于计算复杂性假设，并非实际性能的绝对上限，但提示了模型在需要精确推理任务上的潜在弱点。
效率改进：线性注意力与门控机制
为降低标准注意力的二次复杂度，文章提及线性注意力、Performers 等方案，其中 Performers 训练时仅需 O(1) 内存。FLASH 模型结合门控注意力与线性近似，在长序列上训练速度提升近 5 倍。这些改进在保持性能的同时提升了计算效率，但需权衡表达能力和任务适配性，并非所有场景都适用。
表示能力：稀疏平均与三元组检测的对比
文章通过两个任务对比 Transformer 与循环/前馈网络：稀疏平均任务中，Transformer 复杂度随输入对数增长，而其他网络多项式增长；三元组检测任务中，注意力层复杂度线性增长。这表明 Transformer 在特定任务上具有优势，但并非万能。读者应关注任务结构对模型选择的影响，以及通信复杂度在分析中的价值。
Q&A
Transformer模型在计算能力上有什么理论限制？
研究表明，如果L≠P，Transformer神经网络无法精确解决线性等式或检查产生空符号的任意上下文无关语法的成员身份。这是因为Transformer可以被常深度对数空间均匀阈值电路模拟，从而受到并行计算模型的固有局限。
为什么说Transformer的并行化架构存在固有弱点？
因为与Transformer一样并行化的任何模型体系结构都将遵守类似的限制，即无法高效解决某些串行计算问题。这暗示了放大模型范式的潜在固有弱点。
Transformer模型在哪些任务上表现出对数复杂度优势？
在稀疏平均任务上，循环网络和前馈网络的复杂性随输入规模多项式增长，而Transformer的复杂性仅随输入规模对数增长。
有哪些改进方法可以降低Transformer的计算成本？
可以使用线性自我关注机制（如Performers，训练时仅需O(1)内存）、门控注意力单元和线性近似方法（如FLASH模型，训练速度提升最多4.9倍）、以及可训练的核方法逼近自注意机制。
Transformer在通用逼近性方面有什么理论结果？
具有低秩权重矩阵的自注意力单层能完美捕获整个输入序列上下文，表明单层Transformer具有有限样本的记忆能力；由一个自注意力层和两个前馈神经网络组成的Transformer是紧致域上连续函数的通用逼近器。
Transformer模型能否作为通用计算机使用？
可以，有研究提出了使用Transformer网络作为通用计算机的框架，演示了将迭代算法映射为循环可执行程序的方法，并展示了注意力机制的多种用途。
