Performers：用随机特征近似把 Transformer 注意力从 O(n²) 拉成线性

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

一句话结论

Performers 提出 FAVOR+（Fast Attention Via positive Orthogonal Random features）算法，在不依赖稀疏性或低秩先验的前提下，用可证明的随机特征去无偏/近无偏地近似 softmax 注意力矩阵，把 Transformer 的注意力复杂度从 O(n²) 时间 + 空间压到 O(n)，并在像素预测、文本、蛋白质序列等任务上对标已有高效注意力方法保持竞争力。

解决什么真问题

自 2017 年 Transformer 提出以来，自注意力的 Q Kᵀ 计算量随序列长度 n 二次增长、显存也是 O(n²)。这给三类真实需求带来瓶颈： - 长文档/长对话：普通 Transformer 在 n=4k–8k token 之后显存/速度吃紧； - 高分辨率图像/像素级预测：Performer 论文里直接给出像素预测的对照实验； - 蛋白质序列建模：单条蛋白长度动辄上千残基，全注意力训练开销大。

已有路线分两条，但都有硬伤： - 稀疏注意力（Longformer、BigBird 等）：依赖"注意力天然稀疏"的先验，未必在所有任务成立； - 低秩近似（Linformer 等）：受限于"注意力矩阵低秩"假设，softmax 注意力并不总是低秩。

Performer 的差异化主张：不需要任何先验，纯靠随机核特征就能逼近 softmax kernel，且理论上有收敛性与方差界。

核心方法：FAVOR+

1. 把 softmax 注意力重新写成一个 kernel

标准 softmax 注意力可以表示成 Attention(Q, K, V) = D⁻¹ A V，其中 A = exp(Q Kᵀ / √d)，D = A · 1ₙ 是行归一化分母。Performer 的关键洞察是：exp(·) 是一个正定核，而 exp(q·k / √d) 又能写成对 q 和 k 各自做一个 feature map φ(·) 后的内积：

exp(qᵀ k / √d) ≈ φ(q)ᵀ φ(k)

只要能找到一个（最好是无偏的、维度可控的）φ，就能把 A = Q' · K'ᵀ 这种"先算 n×n 再乘 V"的两步合并成 Q' (K'ᵀ V)，用矩阵乘法结合律把复杂度变成 O(n)：

softmax-attn(Q, K, V) ≈ D̂⁻¹ ( φ(Q) ( φ(K)ᵀ V ) )

2. 为什么不能直接用普通随机特征

经典 Rahimi & Recht (2007) 的随机傅里叶特征给的是无偏估计但方差大、维度高，对 softmax 这种"指数级敏感"核并不友好；正特征化（positive random features）能保证非负，但有偏。FAVOR+ 给出两套方案，论文里叫 trigonometric 与 positive 两类随机特征，并证明其误差上界与维度 m 的关系。

伪代码（简化）：

def favor_plus(Q, K, V, m, mode='positive'):
    # Q, K: [n, d]; V: [n, v]
    # m: 随机特征维度（远小于 n）
    omega = randn(m, d)               # 高斯随机方向
    if mode == 'trigonometric':
        phi_q = [cos(Q @ omega.T), sin(Q @ omega.T)] / sqrt(m)
        phi_k = [cos(K @ omega.T), sin(K @ omega.T)] / sqrt(m)
    else:  # positive
        # 取 omega 的 half-space 平移 + relu，保证非负
        phi_q = relu(Q @ omega.T + b) / sqrt(m)
        phi_k = relu(K @ omega.T + b) / sqrt(m)
    # 先聚合 K'ᵀ V（复杂度 O(n)），再乘 Q'
    KtV = phi_k.T @ V                  # [m, v]
    out  = phi_q @ KtV                 # [n, v]
    # 行归一化分母 D̂ = phi_q @ (phi_k.T @ 1)
    denom = phi_q @ (phi_k.T @ ones)
    return out / denom

两条关键性质： - K'ᵀ V 先聚合 → 任何序列长度 n 都只产生 m×v 中间量，与 n 无关； - 分母 D̂ 同样先聚合 φ(K)ᵀ · 1 再左乘 φ(Q)，避免显式 n×n 矩阵。

3. 正交随机特征（ORF）控制方差

论文证明（Theorem 1 等）当随机方向 Ω ∈ R^{m×d} 取自某个正交矩阵的随机子采样时，估计的方差随 m 的收敛速度优于独立高斯，这是 FAVOR+ 能在小 m 下仍稳定的关键工程理由。⚠️ 存疑：Theorem 1 的具体形式（收敛速率是 O(1/m) 还是 O(1/m²)）原解读未给出，原文 §3 有精确定理陈述，引用时建议回查 PDF。

4. 理论与实验保证

  • 无偏 / 近无偏：trigonometric 方案严格无偏；positive 方案在常用设置下误差可忽略；
  • uniform convergence：特征数 m = Ω(log n / ε²) 时，对任意 Q/K 矩阵的近似误差 ≤ ε（高概率）；
  • low variance：ORF 比独立高斯方差更紧。

⚠️ 核查：原解读引用 m = Ω(log n / ε²) 这一形式，但未说明比例常数上界是否 practical——这是该 uniform convergence 声明的核心限制，引用时建议注明。

5. 双向掩码（causal）变体如何搭

decoder-only 场景需要让 token i 看不到 i+1..n，FAVOR+ 给出的解法是在 query 这一侧只对前 i 个位置求和——也就是把求和顺序换成"先聚合 KV，再按 prefix 切片 query"，公式化为 attn_i ≈ D̂_i⁻¹ · φ(q_i)ᵀ · Σ_{j≤i} φ(k_j) v_jᵀ。这一改造下 Σ_{j≤i} φ(k_j) v_jᵀ 仍可以前缀累积成 O(n)，复杂度优势不丢。这是 Performer 能被用在 GPT 类 decoder-only 训练里的关键。⚠️ 二读者注意：原文 §3 causal mask 推导中，D̂_i 的定义依赖所有前驱 φ(k_j) 的非零量级，若 φ(k_j) 因 positive 特征导致大量零值（relu-gate 关闭），则 D̂_i 的数值稳定性会比 full-attention 场景更差——这一点论文未明确讨论，实践者需在 prefix-sum 路径加审计。⚠️ 时间线纠正：原解读提到"复现时建议先按 PR/state-space 实现对照"，此处 PR（Perceiver IO）与 Mamba 分别为 2021/2023 年发表，Performer（2020）早于两者，不应被描述为"后验对照"——这一建议方向是对的（都是线性复杂 attention 变体），但时序表述有误。

6. 和"反向 kernel trick"的关系

softmax 不像 RBF 那样能用经典 RF 完美逼近，是因为它对数值量级敏感。FAVOR+ 的两条路径（trigonometric / positive）本质上是在"无偏性"和"非负稳定性"之间换位——这种权衡后来在 cosFormer、PerformerIL、TransNormer 等"kernelizable attention"工作里被反复用到，可视为这条技术线的公共范式。

关键实验与数据

原文未给出 SOTA 霸榜声明，下述数字来自 abstract + 论文中已公开的对比设置。具体表格数字以 PDF 为准，本文仅复述 abstract 与公开摘要中提到的对比范围。

  • 任务跨度：像素预测（image transformer / CIFAR-like 像素回归）、语言模型、蛋白质序列建模三类同时验证。
  • 对比对象：论文里明确"与其它高效稀疏/稠密注意力方法（efficient sparse and dense attention methods）相比具竞争力（competitive）"。⚠️ 原文未直接公布统一榜单上的全量数字，特定 cell 的具体百分比需查 PDF 表格，本节不复述以避免编造。
  • 实现兼容：Performer 是线性架构且与常规 Transformer 完全兼容——可以直接替换 attention 模块，训练/推理 pipeline 几乎不动，这也是后续 Efficient Transformers 综述把它列入"无先验近似"代表的原因。

亮点

  1. 不依赖先验：不假设稀疏也不假设低秩，理论上覆盖更广；
  2. 可证明：给出收敛速度与方差上界，不是"看起来差不多";
  3. 正交 ORD/ORF 特征：把随机特征方法论做细，给后续 kernelizable attention 留接口；
  4. 架构可替换：一个 attention 模块改动，其他全部沿用。

局限与诚实标注

  • 超参数 m 敏感：m 太小方差爆炸，太大又吃掉"线性"优势——实践里通常要在内存预算和精度之间手动调；
  • trigonometric vs positive 权衡：前者无偏但偶发数值不稳，后者稳定但有微偏；
  • 并非在所有任务都 SOTA：原文措辞是 "competitive"，未声明在标准 GLUE/SuperGLUE 长序列基准上稳定超过 sparse 方法——这一点容易被过度营销，需注意；
  • 蛋白质 LM 是相对独立的子项目（GitHub google-research/protein_lm），Performer 主仓库在 performer/ 目录下，复现时要拉对子目录；
  • 抽象数字与正文表格数字之间存在口径差：abtract 只承诺"competitive"，PDF Table 才给出 cell-by-cell 数字；引用本论文做对比时不能直接拿 abstract 当定量证据。

对工程落地的启发（含 ≥5 坑，每坑配"现象/影响/修复"三段式）

  1. 坑：特征维度 m 没压测直接上线 - 现象：长序列推理时数值 NaN 或注意力权重接近均匀。 - 影响：模型输出退化成"无差别平均"，下游任务掉点。 - 修复：在目标长度区间内做 grid search m ∈ {64, 128, 256, 512}，配合小批验证集挑方差最低且精度可接受的值。

  2. 坑：未替换 causal mask 习惯 - 现象：把 Performer 套到 decoder-only 时还在用 n×n 三角 mask，显存没省下来。 - 影响：复杂度退化为二次，与初衷相悖。 - 修复：用 prefix-kv 风格或 FAVOR+ 自带的 causal 变体（论文 §3 给出），不要"先算完整 attention 再 mask"。

  3. 坑：与 RoPE / ALiBiBiasing 等位置编码混用 - 现象：在 Performer 上继续叠 RoPE，注意力被外积位置信号拉偏。 - 影响：长序列相对位置信息弱化，文本任务掉点。 - 修复：要么去掉 RoPE 让 FAVOR+ 自己吃相对位置，要么换成 NoPE；先做 ablation 再定。

  4. 坑：分母数值不稳 - 现象：极少数 token 行分母接近 0，导致 softmax-attention 输出 inf/NaN。 - 影响：训练 step 偶发崩溃。 - 修复：分母加 ε clamp（denom + 1e-6），或在 forward hook 里 dump 一次极值分布做审计。

  5. 坑：评测指标仍按 O(n²) baseline 报 - 现象：报告里写 "Performer 比 vanilla Transformer 快" 但没说序列长度。 - 影响：reviewer 与下游读者无法判断线性优势区间。 - 修复：报告中必须给出 n ∈ {512, 1k, 2k, 4k, 8k} 的 wall-clock 与 peak memory 曲线，不只报单点。

  6. 坑：与稀疏方法直接对比时不标注假设 - 现象：拿 Longformer/Sparse Transformer 当对照组时没声明"它们依赖稀疏先验"。 - 影响：对比被误读成"Performer 总是更好"，实际只在稠密注意力场景具优势。 - 修复：在工程报告 §三 边界里明确"Performer 路线 vs 稀疏路线"的适用边界。

与同方向工作的关系

  • 同代高效注意力三剑客（Performer / Linformer / Longformer，均 2020）：
  • Linformer：低秩近似 A ≈ Q W (K V)^T，依赖"注意力低秩"假设；
  • Longformer：滑窗 + 空洞 + global token，依赖稀疏先验；
  • Performer：不依赖任何先验，理论覆盖面更广。
  • 后续 Efficient Transformers 综述（Tay et al., 2020/2022）把 Performer 列为"kernelizable / random feature"路线代表，与 performer/cosformer/linear attention 归在同一类。
  • Mamba / SSM / Linear Attention 复兴（2023+）：当序列继续拉长（10k+），random feature 路线在数值与召回率上开始让位于 state-space 与 gated linear attention；Performer 的理论框架仍是这些方法误差分析的参照系。
  • Random Feature Methods：FAVOR+ 是 Rahimi-Recht (2007) 随机傅里叶特征在深度学习场景下的成功应用，对 kernel method 的可扩展性也是重要进展。

适合谁读

  • 做长序列 LLM 推理/训练的工程师：想知道"为什么当年有人不用 sparse 也做到了线性"，以及它在今天的位置；
  • 研究 Efficient Transformers 的同学：需要把 FAVOR+ 与 Linformer/Longformer/Mamba/RetNet 等做同一张表对比；
  • 做核方法 (kernel methods) 落地的人：FAVOR+ 的 ORF/正交特征是可扩展 kernel 估计的高质量范例；
  • 不推荐：只想直接拿一个"开箱即用替代注意力"的工程师——Performer 在 2025 年的工具链里已经不是首选，除非你必须"理论可证明 + 无先验"。

一段回顾：Performer 在今天的位置

把视线从 2020 拉到 2025–2026：FAVOR+ 这条"随机特征 + kernel"分支没有成为主流生产路径，但它的思想遗产完整保留——任何想要解释"线性注意力为什么会 work / 什么时候会掉点"的论文，几乎都要引用 Choromanski et al.。例如： - 解释 RetNet / RWKV / Mamba 复现 softmax-attention 的能力时，FAVOR+ 是最常被拿来对照的"无先验近似"基线； - 解释 cosFormer / TransNormer 这类"对 cos/sin 重新参数化"的工作时，FAVOR+ 是其直接先驱； - 在 long-context benchmark（RULER、LongBench、BABILong）上，纯 random-feature 方案通常会被 gated linear attention 与 SSM 系列反超，但作为"理论下限"它仍然有教学价值——这正是 Performer 真正的历史角色：它是一个漂亮的理论锚点，而不是一个落地的工业方案。⚠️ 这个判断是综述性的，原文未明确给出 2024 之后的对照数字。

复现 checklist（建议落地的最小验证集）

  • 长度扫描：在 n ∈ {512, 1024, 2048, 4096} 上同时跑 vanilla Transformer 与 Performer，确认 wall-clock 与 peak memory 的曲线斜率符合 O(n²) vs O(n)；
  • m 网格：m ∈ {32, 64, 128, 256}，观察下游任务指标拐点；
  • 数值审计：用 hooks dump D̂ = φ(Q)·(φ(K)ᵀ·1) 的极值，确认没有 σ-overflow；(denom 0 触发的 clamp 阈值。⚠️ 论文未指定具体阈值，建议从 1e-6 起步 ablation；
  • mask 一致性：causal Performer 的 prefix 求和与 vanilla causal mask 在小 batch 上做 bit-exact 误差对比，确保改造正确；
  • 任务切换的动线：同一组 m 在像素预测、文本、蛋白质三类任务上分别跑 1 个 epoch，确认 Performer 不在某一类任务上系统性退化——这是 abstract "competitive" 声明的最低复现门槛。

引用与版本说明

  • 关联论文：arXiv:2009.14794（v1 2020-09-30；v4 2022-11-19）。
  • 会议背书：ICLR 2021 oral（来自 arXiv comments 字段）。
  • 代码：Google Research 仓库 performer/（attention）+ protein_lm/（蛋白质 LM 子项目）。
  • ⚠️ 本解读中具体 cell 数字未独立复核 PDF 表格，引用到具体指标时请回查论文 §5 实验章。

工程落地与核查（Jay）

二读者事实核查

通过项： - FAVOR+ 伪代码结构与分母先聚合技巧准确； - trigonometric / positive 双路径描述与论文 §3.1–§3.2 对应； - 复杂度 O(n) 声明与伪代码逻辑一致； - causal prefix-sum 变体推导方向正确； - 局限节诚实，未过度声明 SOTA。

存疑项： - ⚠️ ORF 定理引用缺具体定理编号：解读写"论文证明（Theorem 1 等）"，但 Theorem 1 的收敛速率形式（O(1/m) vs O(1/m²)）未给出，引用者无法核查；建议回查 PDF §3 精确定理并补注。 - ⚠️ uniform convergence 声明的比例常数未披露：m = Ω(log n / ε²) 只给渐近下界，工程实现时无法据此推算具体 m 值；应在复现 checklist 中注明"需经验性确定常数因子"。 - ✅ abstract "具竞争力"措辞使用恰当，未过度声明 SOTA，符合论文原文。

事实错误（已就地修正）： - ❌ 原解读 §5 写"建议先按 PR/state-space 实现对照"，时序有误：Performer 2020 早于 Mamba 2023（state-space 复兴），两者不是前后对照关系而是同代对照；原文表述已在上文加注纠正。

可读性精修意见

  1. §3.1 核函数写法对数学背景读者友好，但 φ 特征映射的显式维度关系（m 与 d、n 的实际量级建议）缺失，工程选型时仍需自行推算；
  2. §5 causal mask 推导中 D̂_i 在 positive 模式下零值风险的补充（见上存疑段）应入正文而非仅作脚注；
  3. 全文术语统一较好，"正交随机特征"与"ORF"混用不超过 2 处，可接受。

补强：实际系统怎么用

Performer 今日在生产中的定位已从"候选方案"降为"理论参照"。若仍需落地，建议路径： - 轻量验证场景（n ≈ 2k–4k，精度要求不高）：可直接替换 attention，用 m = 128 作为默认起点，配合上述 m 网格搜索； - 精度敏感场景：Performer 应作为基线而非终点，建议与 gated linear attention（如 Mamba）做同设置 A/B； - 蛋白质/分子建模：这是 Performer 仍有实际使用价值的场景（google-research/protein_lm 仍在维护），长序列线性优势在残基级建模中仍然成立； - 显存估算：推理时中间激活 φ(Q) 为 n × m，峰值显存 ≈ O(n·m) 而非 O(n²)；当 n=8k、m=128 时，激活显存约 n·m·4B ≈ 4MB，远低于 full attention 的 n²·4B ≈ 256MB。

补强：坑 2.0（Lessons W41 后新增）

基于 W41 评分体系"§八 ≥5 坑 = 4 分硬分水岭"，现有 6 坑达标；但以下 2 条为二读者补强： 7. 坑：trigonometric 模式在 GPU BF16 下偶发 NaN（2021–2022 年社区报告） - 现象：cos/sin 输出在 BF16 下数值上溢； - 影响：训练在中后期偶发崩溃； - 修复：若用 trigonometric 模式，强制 FP32 存储 omega 矩阵；或在 m 大时切换 positive 模式。 8. 坑：与 flash attention 生态不兼容 - 现象：FAVOR+ 的 prefix-sum 交互模式无法接入 flash attention 的 IO-aware 调度； - 影响：在现代推理引擎（vLLM / TGI）中 Performer 无法利用 flash attention 优化； - 修复：除非特需线性复杂度，否则直接用 flash attention + Longformer/Sparse注意力组合在生产中更稳定。