A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention

📄 arXiv: 2602.01763v1 📥 PDF

作者: Xiaowei Ye, Xiaoyu He, Chao Liao, Chen Wu, Pinyan Lu

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

发布日期: 2026-02-02

💡 一句话要点

证明混合线性-全注意力机制表达能力存在层级差异

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

关键词: 注意力机制 Transformer 表达能力 线性注意力 混合注意力

📋 核心要点

  1. 现有高效注意力机制（如线性注意力）缺乏与全注意力机制在表达能力上的严格理论比较。
  2. 论文通过理论分析，证明了全注意力网络在特定任务上优于混合线性-全注意力网络。
  3. 研究表明，在序列函数组合任务中，全注意力网络所需层数远少于混合网络，揭示了表达能力差异。

📝 摘要（中文）

Transformer是现代大型语言模型的基础。为了缓解标准全注意力的二次复杂度，人们开发了各种高效的注意力机制，如线性注意力和混合注意力。然而，它们相对于全注意力的表达能力缺乏严格的理论表征。本文从理论上刻画了这些注意力机制之间的性能差异。我们的理论适用于所有可以公式化为递归的线性注意力变体，包括Mamba、DeltaNet等。具体而言，我们建立了一个表达能力层级：对于序列函数组合——一种必须在模型前向传递中发生的多步推理任务，一个(L+1)层全注意力网络就足够了，而任何将L-1层全注意力与数量显著更大的（2^(3L^2)）线性注意力层交错的混合网络都无法解决它。这一结果证明了这两种注意力类型之间存在明显的表达能力分离。我们的工作提供了混合注意力和标准全注意力之间的第一个可证明的分离，为理解不同注意力机制的基本能力和局限性提供了理论视角。

🔬 方法详解

问题定义：论文旨在解决现有高效注意力机制（如线性注意力）与全注意力机制在表达能力上缺乏严格理论刻画的问题。现有方法虽然降低了计算复杂度，但其表达能力是否受损，以及受损程度如何，尚不明确。尤其是在需要多步推理的复杂任务中，不同注意力机制的性能差异缺乏理论支撑。

核心思路：论文的核心思路是通过构造一个特定的序列函数组合任务，证明全注意力网络在解决该任务时具有更高的表达效率。具体而言，证明了在解决该任务时，全注意力网络所需的层数远少于混合线性-全注意力网络。这种层数上的差异直接反映了表达能力的差异。

技术框架：论文采用理论证明的方法，而非实验验证。首先，定义了序列函数组合任务，该任务需要模型在forward pass中进行多步推理。然后，分别分析了全注意力网络和混合线性-全注意力网络解决该任务所需的最小层数。通过数学推导，证明了全注意力网络可以用较少的层数解决该任务，而混合网络则需要指数级别的层数。

关键创新：论文最重要的技术创新点在于，它提供了混合注意力和标准全注意力之间第一个可证明的分离。以往的研究主要集中在计算效率的优化上，而忽略了表达能力的理论分析。该论文通过构造特定的任务，证明了混合注意力在表达能力上存在局限性，为理解不同注意力机制的优劣提供了新的视角。

关键设计：论文的关键设计在于序列函数组合任务的构造。该任务需要模型进行多步推理，从而放大了不同注意力机制在表达能力上的差异。此外，论文还对线性注意力机制进行了泛化，使其理论结果适用于包括Mamba、DeltaNet等在内的多种线性注意力变体。论文通过数学归纳法等方法，严格证明了全注意力网络和混合网络解决该任务所需的最小层数。

📊 实验亮点

论文证明了对于序列函数组合任务，一个(L+1)层全注意力网络就足够了，而任何将L-1层全注意力与数量显著更大的（2^(3L^2)）线性注意力层交错的混合网络都无法解决它。这一结果表明，在特定任务上，全注意力网络具有更高的表达效率。

🎯 应用场景

该研究成果有助于指导Transformer模型的架构设计，例如在计算资源有限的情况下，可以根据任务的复杂程度选择合适的注意力机制。此外，该研究也为理解大型语言模型的内在机制提供了理论基础，有助于开发更高效、更强大的模型。

📄 摘要（原文）

Transformers serve as the foundation of most modern large language models. To mitigate the quadratic complexity of standard full attention, various efficient attention mechanisms, such as linear and hybrid attention, have been developed. A fundamental gap remains: their expressive power relative to full attention lacks a rigorous theoretical characterization. In this work, we theoretically characterize the performance differences among these attention mechanisms. Our theory applies to all linear attention variants that can be formulated as a recurrence, including Mamba, DeltaNet, etc. Specifically, we establish an expressiveness hierarchy: for the sequential function composition-a multi-step reasoning task that must occur within a model's forward pass, an ($L+1$)-layer full attention network is sufficient, whereas any hybrid network interleaving $L-1$ layers of full attention with a substantially larger number ($2^{3L^2}$) of linear attention layers cannot solve it. This result demonstrates a clear separation in expressive power between the two types of attention. Our work provides the first provable separation between hybrid attention and standard full attention, offering a theoretical perspective for understanding the fundamental capabilities and limitations of different attention mechanisms.