为什么 Self-Attention 的复杂度是 O(n²·d)?在 n 很大时有什么替代方案?
题目
为什么 Self-Attention 的复杂度是 O(n²·d)?在 n 很大时有什么替代方案?
参考答案
点击展开参考答案
- 复杂度来源:QK^T 是 n×n 矩阵乘法(O(n²·d)),softmax 也是 n×n,再乘 V 又是 n²·d;序列长度 n 的平方项是主要瓶颈。
-
- 稀疏注意力:只计算部分 token 对(如 Longformer 的滑动窗口+全局 token)。
-
- 低秩近似:Linformer 把 K/V 投影到低维,将 n 压到 k(k<<n)。
-
- 线性注意力:将 softmax 近似为核函数,分解为 φ(Q)·(φ(K)^T·V),变为 O(n·d²)。
-
- 状态空间模型:Mamba/SSM,完全回避注意力,O(n·d) 复杂度。
- 现状:精确注意力 + FlashAttention 在工程上已经够用(128K~1M),线性注意力和 SSM 仍在追赶精度。
- 追问:Mamba 和 Transformer 比有什么优缺点?(答:优点是推理时 O(1) 状态、长序列极快;缺点是精确回忆能力弱于注意力、目前精度仍略逊于同规模 Transformer)