Fundamental Limitations on Subquadratic Alternatives to Transformers

📄 arXiv: 2410.04271v2 📥 PDF

作者: Josh Alman, Hantao Yu

分类: cs.LG, cs.CC, cs.CL

发布日期: 2024-10-05 (更新: 2025-05-23)

💡 一句话要点

证明Transformer的子二次替代方案在文档相似性任务中存在根本性局限

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Transformer 注意力机制 文档相似性 亚二次时间复杂度 细粒度复杂度 理论证明 语言模型

📋 核心要点

  1. Transformer的注意力机制复杂度高，成为性能瓶颈，现有方法试图通过启发式算法或替代机制降低复杂度。
  2. 论文证明，在文档相似性任务中，任何亚二次时间复杂度的Transformer替代方案都无法达到Transformer的性能。
  3. 该研究表明，对于涉及文档相似性的任务，Transformer的二次时间复杂度是不可避免的，其他方法无法绕过。

📝 摘要（中文）

Transformer架构广泛应用于大型语言模型中，其核心是用于计算token之间相关性的注意力机制。注意力计算的时间复杂度是输入大小的二次方，成为Transformer操作的瓶颈。为了解决这个问题，研究人员提出了各种方法，包括设计用于更快执行注意力计算的启发式算法，以及提出可以更快计算的注意力机制替代方案，例如Mamba等状态空间模型。本文证明，假设细粒度复杂度理论中的一个流行猜想成立，那么任何此类方法都无法执行Transformer能够执行的重要任务。我们关注文档相似性任务，即给定多个文档作为输入，找到一对最相似的文档（或近似最相似的文档）。我们证明Transformer能够执行此任务，并且证明任何算法都无法在真正的亚二次时间内执行此任务。因此，任何可以在亚二次时间内评估的模型——无论是由于注意力的亚二次时间启发式算法、更快的注意力替代方案（如Mamba）还是任何其他原因——都无法执行此任务。换句话说，为了执行（隐式或显式地）涉及文档相似性的任务，最好使用Transformer，并且无法避免其二次运行时间。

🔬 方法详解

问题定义：论文关注Transformer中注意力机制的二次时间复杂度问题，以及现有方法试图通过亚二次时间复杂度的替代方案来解决该问题。现有方法的痛点在于，虽然降低了计算复杂度，但可能牺牲了模型在某些重要任务上的性能，例如文档相似性计算。

核心思路：论文的核心思路是证明，在文档相似性任务中，任何亚二次时间复杂度的算法都无法达到Transformer的性能水平。这意味着，如果一个模型能够在亚二次时间内运行，那么它在执行文档相似性任务时必然会存在局限性。因此，对于需要处理文档相似性的任务，Transformer的二次时间复杂度是无法避免的。

技术框架：论文并没有提出一个新的模型或算法，而是通过理论证明的方式来分析现有方法的局限性。其技术框架主要包括：1）定义文档相似性任务；2）证明Transformer能够有效执行该任务；3）证明任何亚二次时间复杂度的算法都无法有效执行该任务（基于细粒度复杂度理论中的一个流行猜想）。

关键创新：论文的关键创新在于，它从理论上证明了Transformer的子二次替代方案在文档相似性任务中存在根本性局限。这意味着，在追求更低计算复杂度的同时，必须权衡模型在某些重要任务上的性能。

关键设计：论文主要关注理论证明，没有涉及具体的参数设置、损失函数或网络结构设计。其关键在于选择合适的文档相似性任务，并利用细粒度复杂度理论来证明亚二次时间算法的局限性。

📊 实验亮点

论文通过理论证明，揭示了Transformer的子二次替代方案在文档相似性任务中存在根本性局限。该研究表明，即使采用亚二次时间复杂度的启发式算法或注意力机制替代方案（如Mamba），也无法在文档相似性任务中达到Transformer的性能水平。这意味着，对于涉及文档相似性的任务，Transformer的二次时间复杂度是不可避免的。

🎯 应用场景

该研究成果对自然语言处理领域具有重要意义，尤其是在需要处理大量文档相似性计算的场景中，例如信息检索、文本聚类、文档去重等。它提醒研究人员在设计Transformer替代方案时，需要充分考虑模型在关键任务上的性能，避免过度追求低计算复杂度而牺牲了模型的能力。未来的研究可以探索如何在保证模型性能的同时，进一步降低Transformer的计算复杂度。

📄 摘要（原文）

The Transformer architecture is widely deployed in many popular and impactful Large Language Models. At its core is the attention mechanism for calculating correlations between pairs of tokens. Performing an attention computation takes quadratic time in the input size, and had become the time bottleneck for transformer operations. In order to circumvent this, researchers have used a variety of approaches, including designing heuristic algorithms for performing attention computations faster, and proposing alternatives to the attention mechanism which can be computed more quickly. For instance, state space models such as Mamba were designed to replace attention with an almost linear time alternative. In this paper, we prove that any such approach cannot perform important tasks that Transformer is able to perform (assuming a popular conjecture from fine-grained complexity theory). We focus on document similarity tasks, where one is given as input many documents and would like to find a pair which is (approximately) the most similar. We prove that Transformer is able to perform this task, and we prove that this task cannot be performed in truly subquadratic time by any algorithm. Thus, any model which can be evaluated in subquadratic time - whether because of subquadratic-time heuristics for attention, faster attention replacements like Mamba, or any other reason - cannot perform this task. In other words, in order to perform tasks that (implicitly or explicitly) involve document similarity, one may as well use Transformer and cannot avoid its quadratic running time.