标准注意力的 $n^2$ 来自 $S=QK^\top$ 物化了所有两两交互。线性注意力的洞察是：如果把 softmax 核 $\exp(q^\top k)$ 换成一个可分解的核 $\phi(q)^\top\phi(k)$，结合律就能让我们永远不需要显式构造 $n\times n$ 矩阵。这篇推导整个改写，并诚实讨论代价。
改写：结合律是唯一的主角
先把注意力写成核形式。softmax 注意力输出为
$$ o_i = \frac{\sum_j \exp(q_i^\top k_j)v_j}{\sum_j \exp(q_i^\top k_j)}. $$
分子分母同除以 $e$ 的任意因子，可以把 softmax 核显式写成 $\kappa(q,k)=\exp(q^\top k)$（配平细节见注）。关键假设：存在特征映射 $\phi:\mathbb{R}^d\to\mathbb{R}^r$ 使核可分解：
$$ \kappa(q,k) \approx \phi(q)^\top\phi(k). $$
代入并展开分子（$\phi_i=\phi(q_i)$）：
$$ \sum_j \phi(q_i)^\top\phi(k_j)\,v_j = \phi(q_i)^\top \underbrace{\sum_j \phi(k_j)\,v_j^\top}_{=:S_r\ \in\,\mathbb{R}^{r\times d_v}} = \phi(q_i)^\top S_r. $$
结合律完成全部魔法：原来是 $(n\times r)(r\times n)$ 再乘 $(n\times d_v)$——先算 $n\times n$；现在是先算 $K_r^\top V$（$r\times n$ 乘 $n\times d_v$ 得 $r\times d_v$），再左乘 $\phi(Q)$（$n\times r$ 乘 $r\times d_v$）。总复杂度从 $O(n^2 r)$ 降为 $O(n r d_v)$，只要 $r \ll n$，这就是 $O(n)$。分母同理：$\phi(q_i)^\top \sum_j \phi(k_j)$，用 $S_r$ 的"行和版"向量。实现只要五行：
Kp = phi(K) # (n, r)
Qp = phi(Q) # (n, r)
S = Kp.T @ V # (r, d_v)——唯一的中间矩阵，与 n 无关
z = Kp.sum(0) # (r,)
O = (Qp @ S) / (Qp @ z).unsqueeze(-1)
φ 的选择：近似精度 vs 特征维度
softmax 核本身没有有限的精确特征分解（$\exp(q^\top k)$ 作为核的秩是无限的），所以 $\phi$ 全是近似，取舍在精度与 $r$：
- 正特征映射：$\phi(x)=\mathrm{elu}(x)+1$（Katharopoulos et al. 2020 的原始配方）或 ReLU。正性保证核值非负，避免分子分母出现解释不了的抵消；缺点是对 $\exp$ 的近似很粗，$r=d$ 时没有维度收益，纯粹靠"正 ELU 核在实践中够好"。
- 随机特征：用随机傅里叶特征（RFF）逼近高斯核 $\exp(-\|q-k\|^2/2)$，而 $\exp(q^\top k)$ 配平后正是未归一化高斯核：$\exp(q^\top k)=\exp(\|q\|^2/2)\exp(\|k\|^2/2)\exp(-\|q-k\|^2/2)$，两个范数因子可以提到分子分母外面约掉。Performer 用正负随机特征把逼近误差压到 $\epsilon$ 级别只需 $r=O(d\log d)$ 量级——数学上漂亮，工程上多一次随机投影的成本。
- 学习式 φ：把 $\phi$ 参数化进网络端到端学（LambdadNetworks、一些现代变体），让数据自己决定核形状，代价是失去正性保障时需要归一化兜底。
递归形式：RNN 的借尸还魂
改写成 $S_t = S_{t-1} + \phi(k_t)v_t^\top$、$o_t = \phi(q_t)^\top S_t / (\phi(q_t)^\top z_t$ 后，线性注意力就是一个状态维度 $r\times d_v$ 的 RNN：自回归解码每步只需 O(1) 更新状态，彻底甩掉 KV cache——Mamba/RWKV 那条"无注意力"路线的思想源头就在这里。代价要认账：状态是定长的，$S\in\mathbb{R}^{r\times d_v}$ 装不下任意长的历史，这对应前面秩分析里的结论（注意力的 $n^2$ 表达里被压缩进 $r\times d_v$ 的罐子），长程精确检索能力是结构性受损的。
账本的另一页：常数项
$O(n)$ 的胜利有前提。$r$ 通常取 $d$ 量级，线性注意力的单次 FLOPs 约为 $4nd^2$（两个 $n\times d$ 乘 $d\times d$ 的 GEMM），而标准注意力是 $4n^2d$——交叉点仍是 $n\approx d$。短序列（$n\le 2\text{k}$）上线性注意力反而更贵，且没有免费的午餐：近似核在长序列检索任务上系统性输给精确 softmax。工程现实里纯线性注意力少见，混合架构（滑动窗精确注意力 + 线性/状态空间层兜底长程，如 Mamba-2、Jamba）是更常见的落法。
小结
线性注意力的全部内容是三个等式：核分解 $\exp(q^\top k)\approx\phi(q)^\top\phi(k)$、结合律 $\sum_j\phi(q_i)^\top\phi(k_j)v_j=\phi(q_i)^\top(K_r^\top V)$、递归形式 $S_t=S_{t-1}+\phi(k_t)v_t^\top$。复杂度从 $n^2$ 到 $n$ 的跨越由结合律完成，精度损失由 $\phi$ 的近似性买单，表达能力天花板则是定长状态的秩限制。它是"用数学结构换效率"这条主线上最干净的案例，也是 Mamba/RWKV 路线的直接思想源头。