Higher-order Linear Attention

📄 arXiv: 2510.27258v1 📥 PDF

作者: Yifan Zhang, Zhen Qin, Quanquan Gu

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

发布日期: 2025-10-31

备注: Project Page: https://github.com/yifanzhang-pro/HLA

🔗 代码/项目: GITHUB

💡 一句话要点

提出高阶线性注意力机制，解决自回归语言模型长文本处理的二次复杂度问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 线性注意力 高阶交互 自回归模型 长文本建模 前缀统计 流式处理 因果注意力

📋 核心要点

  1. 传统注意力机制在处理长文本时面临二次复杂度挑战，限制了自回归语言模型的扩展能力。
  2. HLA通过紧凑的前缀充分统计量实现高阶交互，在二阶情况下保持常数状态并线性计算输出。
  3. 论文提出了闭式流式恒等式、因果掩码变体和块并行训练方案，并扩展到更高阶。

📝 摘要（中文）

缩放点积注意力的二次复杂度是自回归语言模型扩展到长上下文的一个主要障碍。线性时间注意力和状态空间模型（SSM）提供了可扩展的替代方案，但通常仅限于一阶或基于核的近似，这可能会限制表达能力。我们引入了高阶线性注意力（HLA），这是一种因果、流式机制，通过紧凑的前缀充分统计量实现更高阶的交互。在二阶情况下，HLA 保持一个恒定大小的状态，并在线性时间内计算每个 token 的输出，而无需物化任何 $n imes n$ 矩阵。我们给出了闭式流式恒等式，一种使用两个附加摘要的严格因果掩码变体，以及一种基于结合扫描的块并行训练方案，该方案精确地再现了串行递归的激活。我们进一步概述了对三阶和更高阶的扩展。总的来说，这些结果将 HLA 定位为一个原则性的、可扩展的构建块，它将类似注意力的、数据相关的混合与现代循环架构的效率相结合。

🔬 方法详解

问题定义：现有缩放点积注意力机制的计算复杂度随序列长度呈二次方增长，这使得将其应用于长文本建模变得非常困难。线性注意力机制和状态空间模型虽然降低了计算复杂度，但通常只能进行一阶或基于核的近似，限制了模型的表达能力。

核心思路：论文的核心思路是通过维护紧凑的前缀充分统计量来实现高阶交互，从而在不牺牲表达能力的前提下，将计算复杂度降低到线性级别。具体来说，就是设计一种能够捕捉序列中不同位置之间高阶关系的线性注意力机制。

技术框架：HLA 的整体框架是一个流式处理架构，它逐个 token 地处理输入序列。对于每个 token，HLA 首先更新其内部状态（前缀充分统计量），然后基于该状态计算输出。该框架包含以下主要模块：状态更新模块、输出计算模块和掩码模块（用于保证因果性）。论文还提出了一个块并行训练方案，以加速训练过程。

关键创新：HLA 的关键创新在于它使用前缀充分统计量来表示序列中的高阶信息。与传统线性注意力机制只考虑一阶关系不同，HLA 可以捕捉更高阶的关系，从而提高模型的表达能力。此外，HLA 的流式处理架构使其能够高效地处理长序列。

关键设计：HLA 的关键设计包括：1) 前缀充分统计量的具体形式，它决定了模型能够捕捉到的高阶关系的类型；2) 状态更新模块的实现方式，它需要保证状态能够有效地捕捉序列中的信息；3) 输出计算模块的实现方式，它需要能够基于状态计算出准确的注意力权重。论文给出了二阶 HLA 的具体实现，并讨论了如何将其扩展到更高阶。

📊 实验亮点

论文提出了二阶 HLA 的具体实现，并在实验中验证了其有效性。实验结果表明，二阶 HLA 在保持线性复杂度的同时，能够达到与传统注意力机制相近的性能。此外，论文还展示了 HLA 的块并行训练方案能够有效地加速训练过程。项目页面提供了代码和更多实验细节。

🎯 应用场景

高阶线性注意力机制 (HLA) 具有广泛的应用前景，尤其是在需要处理长序列数据的领域，如自然语言处理中的长文本建模、语音识别中的长语音处理、以及视频分析中的长视频理解。HLA 的高效性和可扩展性使其能够应用于资源受限的设备上，例如移动设备和嵌入式系统。此外，HLA 还可以作为一种通用的序列建模模块，应用于各种机器学习任务中。

📄 摘要（原文）

The quadratic cost of scaled dot-product attention is a central obstacle to scaling autoregressive language models to long contexts. Linear-time attention and State Space Models (SSMs) provide scalable alternatives but are typically restricted to first-order or kernel-based approximations, which can limit expressivity. We introduce Higher-order Linear Attention (HLA), a causal, streaming mechanism that realizes higher interactions via compact prefix sufficient statistics. In the second-order case, HLA maintains a constant-size state and computes per-token outputs in linear time without materializing any $n \times n$ matrices. We give closed-form streaming identities, a strictly causal masked variant using two additional summaries, and a chunk-parallel training scheme based on associative scans that reproduces the activations of a serial recurrence exactly. We further outline extensions to third and higher orders. Collectively, these results position HLA as a principled, scalable building block that combines attention-like, data-dependent mixing with the efficiency of modern recurrent architectures. Project Page: https://github.com/yifanzhang-pro/HLA.