14.1 高效注意力：突破平方复杂度的瓶颈

标准自注意力的 $O(n^2)$ 复杂度（2.5 节已详细分析）是 Transformer 处理超长序列的根本瓶颈。本节讨论针对这一瓶颈的各种高效注意力方案。

14.1.1 稀疏注意力

稀疏注意力的核心思想是：不是让每个位置关注所有位置，而是只关注一个精心选择的子集。

局部窗口注意力：每个词元只关注前后固定大小窗口内的邻近词元。代表模型：Longformer（12.3 节）。复杂度 $O(n \cdot w)$。

分块注意力：将序列分为固定大小的块，块内使用标准全注意力，块间使用选择性注意力或完全不交互。FlashAttention 的分块策略虽然不改变数学性质，但体现了类似的分块思想。

哈希注意力：Reformer 提出使用局部敏感哈希（LSH）将相似的 Q 和 K 分到同一个桶中，只在桶内计算注意力。复杂度 $O(n \log n)$。

14.1.2 线性注意力

线性注意力的目标更激进——将 $O(n^2)$ 降至 $O(n)$。关键转换是避免显式计算 $n \times n$ 的注意力矩阵。

标准注意力：$\text{Attn} = \text{softmax}(QK^T)V$，需要先计算 $QK^T$（$O(n^2)$）。

线性注意力通过核函数近似将 Softmax 分解为特征映射 $\phi$ 的乘积：

$\text{Attn} \approx \phi(Q)(\phi(K)^T V)$

通过先计算括号内部分 $\phi(K)^T V$（$O(n \cdot d^2)$），再左乘 $\phi(Q)$，避免了 $O(n^2)$ 的中间矩阵。

Performer（Choromanski 等人，2021 年）使用随机特征映射近似 Softmax 核。Linear Transformer 直接使用 ELU 激活函数替代 Softmax。

线性注意力的主要限制是精度——在标准长度序列上，它通常不如精确的 Softmax 注意力。因此实际采用率有限，更多用于需要处理数万到数十万词元的特殊场景。

14.1.3 混合方案

实际最有效的策略往往是混合方案——在不同层使用不同类型的注意力。例如，底层使用全注意力（精细的局部特征提取），高层使用稀疏或线性注意力（高效的全局信息聚合）。这种分层设计在保持质量的同时降低了总体复杂度。