Fundamental Limitations on Subquadratic Alternatives to Transformers

Transformer架构被广泛应用于许多流行且有影响力的大型语言模型中。其核心是用于计算token对之间关联的注意力机制。执行注意力计算需要输入大小的平方时间，已成为Transformer操作的时间瓶颈。为了规避这个问题，研究人员采用了各种方法，包括设计启发式算法以更快地执行注意力计算，并提出了可以更快地计算的注意力机制的替代方案。例如，状态空间模型（如Mamba）旨在用几乎线性时间的替代方案替换注意力。 在本文中，我们证明了任何这样的方法都不能执行Transformer能够执行的重要任务（假设来自细粒度复杂性理论的一种流行的猜想）。我们关注文档相似性任务，其中输入了许多文档，并希望找到一对（近似）最相似的文档。我们证明了Transformer能够执行此任务，并且证明了任何算法都无法在真正的次二次时间内执行此任务。因此，任何可以在次二次时间内进行评估的模型-无论是因为注意力的次二次时间启发式，更快的注意力替代品（如Mamba）还是其他任何原因-都无法执行此任务。换句话说，为了执行（隐含或明确）涉及文档相似性的任务，可以使用Transformer，并且无法避免其二次运行时间。

论文探讨了Transformer架构在处理文档相似性任务中的优越性，并证明了任何能够在次二次时间内运行的算法无法完成此任务。

Transformer架构的注意力机制是处理文档相似性任务的关键，任何替代方案都无法在次二次时间内完成此任务。

论文证明了Transformer架构在处理文档相似性任务中的优越性，并提出了任何替代方案都无法在次二次时间内完成此任务。实验使用多个数据集进行验证，并且论文提供了开源代码。

最近的相关研究包括使用不同的注意力机制和采用更快的算法来加速Transformer架构的运行速度。