用随机特征"骗"过 softmax，Transformer 注意力也能跑成线性？

  • 关联论文：2009.14794
  • 作者：flyP
  • 更新：2026-10-17

一句话结论

Performer 提出 FAVOR+ 算法，用可证明的随机特征去近似 softmax 注意力矩阵，在不依赖稀疏或低秩先验的前提下，把 Transformer 注意力从 O(n²) 拉到 O(n)，并在像素预测、文本、蛋白质序列上验证有效。

为什么这件事重要

Transformer 的 Q Kᵀ 让序列长度 n 一变长，显存和算力就跟着平方级爆炸——4k token 之后就开始吃紧，8k、16k 几乎是普通消费卡跑不动的门槛。这条"二次墙"卡住了三类真实需求：高分辨率像素预测、长文档对话、动辄上千残基的蛋白质建模。

已有的破墙思路有两类硬伤：稀疏注意力（Longformer 等）赌"注意力天然稀疏"，低秩近似（Linformer）赌"矩阵天然低秩"——两个赌注未必每次都赢。Performer 的差异化主张是：我什么都不赌，用数学上可证明的随机核特征，去无偏地逼近 softmax 这个指数核本身。

核心机制：FAVOR+

softmax 注意力可以写成 Attention = D⁻¹ · A · V，其中 A = exp(QKᵀ/√d) 是 n×n 矩阵。Performer 的关键洞察是：exp(·) 本身是一个正定核，可以拆成对 q 和 k 各自的特征映射 φ(·) 的内积：exp(qᵀk/√d) ≈ φ(q)ᵀφ(k)。

只要找到这样一个 φ，就能用矩阵乘法结合律反转顺序：先聚合 φ(K)ᵀV 得到 m×v 中间量（m 是随机特征维度，远小于 n），再左乘 φ(Q)。全程不出现 n×n 矩阵——这就是 O(n) 时间复杂度的来源，行归一化分母 D̂ = φ(Q)·(φ(K)ᵀ·1) 同样先聚合再左乘，避免显式构造 A。

论文给了两条工程路径：trigonometric 模式用 cos/sin 配对，估计严格无偏但偶发数值不稳；positive 模式对随机方向做 half-space 平移 + relu，保证非负、微偏但数值稳定。两者都脱胎于经典 Rahimi-Recht 随机傅里叶特征，并配合正交随机方向（ORF）——把随机方向矩阵 Ω 约束在某个正交矩阵的随机子采样中——把估计方差压到比独立高斯更紧，这是 Performer 在小 m 下仍能稳定逼近 softmax 的关键工程理由。论文还给出 causal 掩码变体：在 decoder-only 场景里让 Σ_{j≤i} φ(k_j)v_jᵀ 前缀累积成 O(n)，复杂度优势不丢——这是它能被放进 GPT 类训练管线的前提。

证据边界与工程局限

  • 论文承诺的是"competitive"，不是 SOTA 霸榜：abstract 没在 GLUE/SuperGLUE 等榜单上宣称稳定超过 sparse 方法，这点容易被过度营销——读 abstract 当定量证据会出错；
  • 特征维度 m 是核心超参：太小方差爆炸导致注意力权重接近均匀，太大又吃掉"线性"优势，需要在 m ∈ {64, 128, 256, 512} 之间手动 grid search；
  • 与 RoPE/ALiBi 等位置编码混用会拉偏外积位置信号，长序列相对位置信息弱化；
  • 在现代推理引擎中 Performer 无法利用 flash attention 的 IO-aware 调度，因为 FAVOR+ 的 prefix-sum 交互与 flash attention 的分块策略不兼容；
  • 2025–2026 年的工具链里 Performer 已让位于 flash attention + Longformer 的组合与 SSM/Mamba，但作为"无先验线性近似"理论锚点仍然有效——任何讨论"线性注意力为什么会 work / 何时掉点"的论文，几乎都要引用 Choromanski et al.。

一句话复盘

Performer 不是 2026 年的落地方案，但它是漂亮的理论锚点：把"随机特征 + 核方法"带进 Transformer 注意力，让后续 RetNet/RWKV/Mamba 的误差分析有了对照基线。

三个标题变体

  1. A. 把 Transformer 注意力"算开"——FAVOR+ 如何用随机特征把 O(n²) 拉成 O(n)
  2. B. 不赌稀疏也不赌低秩：Performer 的"无先验"线性注意力是怎么做出来的
  3. C. 当 Transformer 卡在 4k token——一个 2020 年的数学技巧为何还在被引用

小红书卡片文案

姐妹们👀 Transformer 一跑长文本就卡的痛懂吗？2020 年这篇 Performer 给了一个超优雅的解法：不用稀疏假设也不用低秩假设，纯靠随机核特征把注意力算成线性。原理一句话——把 softmax 这个指数核拆成两组随机特征的内积，再用矩阵结合律反转计算顺序，全程不出现那个让人窒息的 n×n 矩阵。代价是要调一个"随机特征维度 m"的超参，调好了就能在 8k token 上跑得飞起。划重点：2026 年它已经不是首选方案，但任何讨论"线性注意力为什么会 work"的论文都要引用它——属于理论锚点级别的存在 🌟 #AI科普 #Transformer #大模型 #机器学习 #深度学习