Performer核近似：让Transformer跑出线性速度

可视化演示

展示Performer通过随机特征将softmax注意力从O(n²)降至O(n)的核近似过程，对比标准Transformer与Performer的复杂度曲线与长序列加速效果。

问题背景：标准注意力的平方瓶颈

在传统的“直接翻书”图书馆里，读者找书的方式很笨拙：他们必须把书架上的每本书依次抽出来，和书背上的“需求标签”比对一遍，才能确定这本书值不值得读。Transformer 的注意力机制干的正是这件事——每个词（读者）都要与序列中的每一个词（书）计算相似度（翻封面），然后按相似度加权提取信息（读内容）。序列中有 n 个词，每个词都要执行 n 次比对，总工作量就是 n×n 次。这听起来还算合理，直到序列变长：处理一篇 1000 字的短文需要 100 万次比对，而处理一篇 10 万字的报告就需要 100 亿次——笔记本的计算力瞬间告急。

这个“逐本翻书”的过程在数学上就是 Softmax 注意力公式。它分为三步：每个查询（Query）去匹配所有键（Key）得到分数，分数经过软组织归一化成权重，最后按权重混合值（Value）的内容。问题恰恰出在第一步和第三步之间的那个 n×n 的矩阵上。

回到我们的图书馆：当藏书量 n 从 1 万涨到 10 万，读者的翻书次数从 1 亿次暴涨到 100 亿次——这就是平方级增长的可怕之处。Performer 要做的，就是派来一位聪明的新管理员，彻底改变这套“翻书”流程。

核近似思想：用简介卡代替逐本翻书

新管理员提出了一个大胆的想法：与其让每位读者翻遍所有书，不如先为每本书做一张“简介卡”，卡上只写几个最能代表书本主题的关键词。读者拿需求标签与简介卡上的关键词做快速比对，就能判断这本书是否值得深读。这里的关键洞察是：Softmax 注意力中那套复杂的相似度计算，本质上是一个“内核函数”（kernel function），它衡量两个向量的相似程度。管理员发现，这个内核函数可以被拆解成“简介卡”的匹配形式——用两个低维特征的普通点积，去近似那个昂贵的相似度计算。

这个“拆解”在数学上就是核近似：把 Softmax 的内核 exp(x·y) 分解成两个特征向量 φ(x) 和 φ(y) 的内积。φ 就像一个“关键词提取器”，把一本书（向量 x）浓缩成一张简介卡（特征向量 φ(x)）。两张卡片的内积，就近似等于两本书原本的相似度。

管理员意识到，只要简介卡做得足够好，读者就再也不需要逐本翻书了。但一个新问题摆在眼前：这张“简介卡”究竟应该怎么写？写哪些关键词？这引出了 Performer 的核心技术——随机特征映射。

随机特征映射：简介卡怎么制作

管理员翻阅了大量图书分类学著作，最终找到一套巧妙的方案：随机抽取关键词。他准备了一组随机主题词（比如“恒星”、“深海”、“量子”、“烘焙”），每本书都和这些主题词做内积，得到一个“该主题的相关度得分”。得分高就记在卡上。为了让卡片信息完整，他还会减去每个关键词的“噪声基底”（书的自身长度），最后套上一个指数函数保证所有得分为正——毕竟“不相关”和“稍有关联”都是正面信号，不能出现负数。这就是 FAVOR+ 的随机特征构造方法。

数学上，随机特征 φ(x) 的构造方式如下：先生成一个随机矩阵 W（相当于那组随机主题词），把向量 x 投影到 m 个随机方向上，再经过指数变换。最关键的性质是：如果我们抽取足够多的随机方向，这些简介卡的内积在期望意义下恰好等于原版的内核值——这就是无偏性。抽的关键词越多（m 越大），简介卡越接近原书。

简介卡制作完成了，但管理员立刻发现了一个新机会：既然所有书都有了简介卡，为什么还要让每个读者逐张翻卡呢？为什么不把所有卡片汇总成一本“主题索引册”？

计算顺序：先合成索引表再查询

传统流程中，即使有了简介卡，读者还是要逐一比对每张卡片（对应计算完整的 n×n 近似注意力矩阵）。管理员灵机一动：矩阵乘法满足结合律——就像 3×(4×5) 和 (3×4)×5 结果一样，我们可以改变乘法的先后顺序！如果先把所有书的内容（V）按关键词（φ(K)）汇总成一本“主题索引册”（一个很小的 m×d 矩阵），读者只需要把自己的需求标签（φ(Q)）与索引册做一次比对，就能直接得到答案。这样，书的数量 n 再大，读者也只需要查索引，而不是翻遍 n 张卡。

这就是 Performer 最核心的计算技巧：把 (φ(Q)φ(K)ᵀ)V 重写为 φ(Q)(φ(K)ᵀV)。先算 φ(K)ᵀV，得到一个维度仅为 m×d 的小矩阵（m 是关键词数量，通常几百），再让 φ(Q) 与这个小矩阵相乘。整个流程的计算量从 n² 降到了 n·m。

主题索引册制度让图书馆的效率突飞猛进。但管理员并不满足，他注意到随机抽取关键词有个隐患：有时会抽出两个意思重复的词（比如“巴黎”和“法国首都”），白白浪费卡片空间。有没有办法让每张卡都是独一无二的呢？

正交特征：关键词去重降方差

随机抽取主题词时，管理员发现了一个问题：随机方向之间常常“撞车”。比如随机选了 64 个方向，其中 10 个都指向“欧洲城市”这个主题，真正覆盖新主题的方向只有 54 个——这就像简介卡上塞满了重复的关键词，信息密度大大降低。更糟的是，随机方向之间的相关性会让简介卡的估计结果忽高忽低（方差大），同样的书今天做出这样的卡，明天做出那样的卡。

解决方案来自线性代数：管理员把随机方向矩阵做了一次 QR 分解——就像把一堆杂乱无章的抽签棒理成互相垂直的坐标轴。正交矩阵中的每一列都与其他所有列垂直，保证每个关键词覆盖完全独立的主题，互不重叠。实验表明，同样的关键词数量下，正交方案产生的简介卡信息量更大、估计更稳定，方差大幅降低。

有了正交的关键词体系，同样的卡片数量能承载更多独立信息。那么问题来了：关键词数量 m 到底取多少才合适？抽取太多，制作卡片成本高；抽取太少，简介卡又不够准确。这就进入了工程权衡的领域。

精度权衡：卡片精度与制作成本

管理员的简介卡制度虽然高效，但并非没有代价。每张卡片上的关键词数量 m 直接决定了信息的完整度：m 越大，简介卡越接近原书，读者判断越准确；但 m 越大，制作和比对卡片的时间成本也越高。这就像为一个 1000 页的巨著写简介——写 10 个关键词省时省力但可能漏掉关键情节，写 500 个关键词面面俱到却失去了“简介”的意义。

数学上，核近似的误差与特征数量 m 的关系非常优雅：均方误差以 O(1/m) 的速度递减。也就是说，m 每翻一倍，近似误差就减半。但由于 Performer 使用了正交随机特征，误差的常数因子大大缩小——论文实验显示，正交方案下 m 取几百维就能达到令人满意的精度，而普通高斯特征可能需要数千维。误差公式如下：

给 1000 本书做 10 个关键词的简介卡，能快速给读者一个大致方向；给 100 本重点书做 100 个关键词的精读卡，则能保证高精度检索。Performer 的使用者正是这样：面对不同长度的序列和精度要求，灵活调节特征数 m，在速度与质量之间走出最经济的路线。

性能效率：指数差距的实测

让我们回到那座图书馆，用数字感受新人管理员的改革成果。假设图书馆有 n 本书，每本书有 d 个主题类别，管理员制作 m 个关键词（m 是固定常数，如 256）。传统“逐本翻书”制度的总工作量是 n²d 次操作——书一多就爆炸；新制度的总工作量是 nmd 次操作——书再多也只是线性增长。以 n=1024、d=64、m=64 为例：旧制度需要约 6700 万次操作，新制度只需约 420 万次，快了 16 倍。当 n 变成 1 万时，差距将扩大到 156 倍！

同时，内存占用也天差地别。标准注意力需要在内存中存储 n×n 的注意力矩阵——n=1 万时，光是这个矩阵就需要 400MB 内存；而 Performer 只需要保存 m×d 的索引矩阵，仅 16KB。内存的大幅节省让训练更深的模型、处理更长的序列成为可能。

新制度的优越性在藏书量大的图书馆里体现得淋漓尽致。1000 本的小图书馆里，逐本翻书和查索引的差别不大；但当藏书量达到百万级，查索引几乎是唯一可行的方案——这正是 Performer 在超长序列场景中不可替代的原因。

应用场景：长序列的主场之战

简介卡制度很快从普通图书馆推广到了各个专业分馆。在医学文献馆，研究人员需要对上万字的论文进行阅读理解与摘要生成——Performer 能线性处理这些长文本，而标准 Transformer 早已因内存爆炸而崩溃。在基因序列馆，生物信息学家用 Performer 对长达数万 token 的蛋白质序列进行结构预测，每个氨基酸都能高效地与全序列的其他氨基酸建立关联。在地图馆（图数据场景），图 Transformer 用 Performer 处理包含上百万节点的大图，每个节点都能感知全图信息而无需逐对计算。

这些场景有一个共同点：序列长度 n 远大于特征数 m，Performer 的加速比 n/m 极其可观。更令人惊喜的是，Performer 的核近似在理论上保证了无偏性，加上正交特征的低方差，其精度在许多任务上非常逼近标准 Transformer。论文中的实验表明，在蛋白质序列建模、文本分类等任务上，Performer 的准确率与标准 Transformer 相差无几，而训练和推理速度却快了一个数量级。

从逐本翻书到查索引册，Performer 的核近似从根本上改变了长序列处理的游戏规则。当然，简介卡制度也并非万能——它牺牲了部分精度换来了效率，理解这种权衡才能在实际项目中作出正确选择。

AI 应用场景

Python 演示

import numpy as npimport time def softmax_attention(Q, K, V):    """标准 Softmax 注意力：复杂度 O(n^2)"""    d = Q.shape[-1]    scores = np.matmul(Q, K.transpose(0, 2, 1)) / np.sqrt(d)    weights = np.exp(scores - scores.max(axis=-1, keepdims=True))    weights /= weights.sum(axis=-1, keepdims=True)    return np.matmul(weights, V) class RandomFeatureAttn:    """Performer 线性注意力：正交随机特征 + 结合律换序"""    def __init__(self, d_model, m=64, seed=42):        rng = np.random.RandomState(seed)        W = rng.randn(d_model, m)        Q, _ = np.linalg.qr(W)        self.W = Q.astype(np.float32)        self.m = m     def phi(self, X):        proj = np.matmul(X, self.W)        norm = 0.5 * np.sum(X * X, axis=-1, keepdims=True)        return np.exp(proj - norm) / np.sqrt(self.m)     def __call__(self, Q, K, V):        phi_q = self.phi(Q)        phi_k = self.phi(K)        kv = np.matmul(phi_k.transpose(0, 2, 1), V)        return np.matmul(phi_q, kv) if __name__ == "__main__":    np.random.seed(0)    head = RandomFeatureAttn(d_model=64, m=64)    for n in [64, 128, 256, 512]:        d = 64        X = np.random.randn(1, n, d).astype(np.float32)        t0 = time.perf_counter()        out_std = softmax_attention(X, X, X)        t1 = time.perf_counter()        out_fast = head(X, X, X)        t2 = time.perf_counter()         err = np.abs(out_std - out_fast).mean()        print(f"n={n:4d}  标准={t1-t0:.4f}s  Performer={t2-t1:.4f}s  "              f"加速={(t1-t0)/max(t2-t1,1e-6):.1f}x  平均误差={err:.4f}")

1. scores = np.matmul(Q, K.transpose(0, 2, 1)) / np.sqrt(d)标准注意力计算 n×n 相似度矩阵，这就是平方复杂度的来源
2. Q, _ = np.linalg.qr(W)对随机矩阵做 QR 分解，得到正交随机特征矩阵，降低方差
3. proj = np.matmul(X, self.W)把输入的 Q/K 投影到 m 个正交随机方向上
4. norm = 0.5 * np.sum(X * X, axis=-1, keepdims=True)计算 ||x||²/2 去偏置项，保证无偏性
5. return np.exp(proj - norm) / np.sqrt(self.m)指数变换 + 归一化，构造正随机特征 φ(x)
6. kv = np.matmul(phi_k.transpose(0, 2, 1), V)关键一步：先聚合 K 与 V，得到 m×d 的“索引表”
7. return np.matmul(phi_q, kv)查询与索引表相乘，复杂度与 n 线性相关
8. for n in [64, 128, 256, 512]:扫描不同序列长度，观察标准版的耗时增速远快于 Performer

常见误区

面试题