在自然语言处理、计算机视觉等深度学习任务中，Transformer 架构凭借其强大的注意力机制取得了巨大成功。然而，其核心组件——自注意力（Self-Attention）的计算复杂度与序列长度的平方成正比，即 O(n²)。当处理长序列（如长文档、高分辨率图像、基因序列）时，巨大的内存和计算开销成为模型训练和部署的瓶颈。这使得 Transformer 模型在处理长上下文时显得笨重且昂贵。

为了解决这一根本性挑战，研究者们提出了多种线性化注意力（Linear Attention）方案，旨在将 O(n²) 的复杂度降低到 O(n) 或 O(n log n)。其中，Linformer 和 Performer 是两种具有代表性且思路迥异的方案。Linformer 通过低秩投影直接压缩注意力矩阵的维度，而 Performer 则通过核化（Kernelization）和结合律（Associative Property）重构了注意力计算的过程。理解这两种方法，不仅能帮助我们在实际项目中根据场景选择合适的长序列处理工具，更能深入理解注意力机制的本质与优化空间。

本文将从自注意力的计算瓶颈出发，详细拆解 Linformer 和 Performer 的核心思想、实现原理、关键步骤以及工程实践中的注意事项。我们将通过概念解释、伪代码、配置对比和常见问题排查，构建一个完整的认知和实践框架。无论你是希望优化现有模型性能的工程师，还是对高效 Transformer 架构感兴趣的研究者，这篇文章都将提供从理论到落地的清晰路径。

1. 重温自注意力瓶颈：为什么 O(n²) 是问题

在深入 Linformer 和 Performer 之前，必须清晰理解标准自注意力（Scaled Dot-Product Attention）的计算过程及其瓶颈所在。这是所有优化工作的起点。

1.1 标准自注意力计算流程

给定一个输入序列 $X \in \mathbb{R}^{n \times d}$，其中 $n$ 是序列长度，$d$ 是特征维度。通过线性变换得到查询（Query）、键（Key）、值（Value）矩阵： $Q = XW^Q, K = XW^K, V = XW^V$，其中 $W^Q, W^K, W^V \in \mathbb{R}^{d \times d_k}$（为简化，常设 $d_k = d$）。

标准注意力计算如下： $Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d_k}})V$

让我们逐步分析其计算复杂度：

1. 矩阵乘法 $QK^T$：$Q \in \mathbb{R}^{n \times d_k}$, $K^T \in \mathbb{R}^{d_k \times n}$。结果矩阵 $S = QK^T \in \mathbb{R}^{n \times n}$。这一步的复杂度是 $O(n^2 d_k)$，由于 $d_k$ 是固定维度，我们通常关注与 $n$ 相关的部分，即 $O(n^2)$。
2. Softmax 与缩放：对 $S$ 的每一行进行 softmax 操作，复杂度为 $O(n^2)$。
3. 加权求和 $AV$：注意力权重矩阵 $A = softmax(S) \in \mathbb{R}^{n \times n}$ 与 $V \in \mathbb{R}^{n \times d_v}$ 相乘，得到输出 $O \in \mathbb{R}^{n \times d_v}$，复杂度为 $O(n^2 d_v)$，同样可视为 $O(n^2)$。

因此，整个注意力计算的核心瓶颈在于生成和操作那个 $n \times n$ 的注意力矩阵 $A$。当 $n$ 很大时（例如 4096, 8192 甚至更长），这个矩阵将消耗巨大的内存（存储 $n^2$ 个浮点数）并需要海量的计算。

1.2 瓶颈带来的实际问题

在实际工程中，O(n²) 复杂度会引发一系列具体问题：

• 内存溢出（OOM）：这是训练长序列模型时最常见的错误。例如，当 $n=8192$, $d_k=64$ 时，$QK^T$ 矩阵（float32）将占用大约 $8192 * 8192 * 4 bytes ≈ 268 MB$。这只是一个注意力头的一次前向传播。多层、多头、批处理（batch）会迅速将内存需求推向数百 GB，远超常见 GPU 显存容量。
• 训练速度缓慢：即使内存足够，平方级的计算量也会导致训练一个 epoch 的时间呈指数增长，使得模型迭代和调参成本极高。
• 推理延迟高：在生产环境中，高延迟直接影响用户体验和系统吞吐量。
• 无法处理超长序列：许多重要场景，如整本书的摘要、长视频理解、基因组分析，序列长度可能达到数万甚至百万级，标准 Transformer 完全无法处理。

正是这些切实的工程难题，催生了 Linformer 和 Performer 等线性注意力机制。

2. Linformer：基于低秩假设的注意力矩阵压缩

Linformer 的核心思想非常直观：既然注意力矩阵 $A$（$n \times n$）是瓶颈，而实践中发现该矩阵往往是低秩的，那么我们可以通过一个低秩投影，先将 $K$ 和 $V$ 从 $n$ 维压缩到一个更小的 $k$ 维（$k << n$），从而避免生成巨大的 $n \times n$ 中间矩阵。

2.1 核心思想与数学推导

Linformer 的作者通过经验观察和理论分析发现，在训练好的 Transformer 模型中，自注意力矩阵的奇异值衰减很快，即其有效秩远小于序列长度 $n$。这意味着我们可以用一个小得多的矩阵来近似它。

具体做法是引入两个投影矩阵 $E_i, F_i \in \mathbb{R}^{k \times n}$，分别作用于键（K）和值（V）的序列长度维度。注意，这里的投影是沿着序列长度方向，而不是特征维度。

原始注意力计算：$Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d_k}})V$

Linformer 修改后的计算： $LinformerAttention(Q, K, V) = softmax(\frac{Q (E K)^T}{\sqrt{d_k}}) (F V)$

让我们分析维度的变化：

1. $K \in \mathbb{R}^{n \times d_k}$, $E \in \mathbb{R}^{k \times n}$。则 $E K \in \mathbb{R}^{k \times d_k}$。相当于将键序列从长度 $n$ 压缩到了长度 $k$。
2. 同理，$V \in \mathbb{R}^{n \times d_v}$, $F \in \mathbb{R}^{k \times n}$。则 $F V \in \mathbb{R}^{k \times d_v}$。
3. 现在计算 $Q (E K)^T$：$Q \in \mathbb{R}^{n \times d_k}$, $(E K)^T \in \mathbb{R}^{d_k \times k}$。结果矩阵 $P = Q (E K)^T \in \mathbb{R}^{n \times k}$。注意，这里得到的 $P$ 是 $n \times k$，而不是原来的 $n \times n$！
4. 对 $P$ 的每一行做 softmax，得到 $\tilde{A} \in \mathbb{R}^{n \times k}$。
5. 最后计算输出：$O = \tilde{A} (F V)$，其中 $\tilde{A} \in \mathbb{R}^{n \times k}$, $F V \in \mathbb{R}^{k \times d_v}$，结果 $O \in \mathbb{R}^{n \times d_v}$。

复杂度分析：关键步骤 $Q (E K)^T$ 的复杂度是 $O(n k d_k)$，最终加权求和 $\tilde{A} (F V)$ 的复杂度是 $O(n k d_v)$。由于 $k$ 是一个固定的超参数（如 256），复杂度从 $O(n^2)$ 成功降为 $O(n)$。

2.2 工程实现关键点

在代码实现中，Linformer 通常作为一个独立的注意力层模块。以下是其关键实现步骤的伪代码和解释。

import torch import torch.nn as nn import torch.nn.functional as F class LinformerAttention(nn.Module): def __init__(self, d_model, n_heads, seq_len, k=256, dropout=0.1): super().__init__() assert d_model % n_heads == 0 self.d_model = d_model self.n_heads = n_heads self.d_k = d_model // n_heads self.seq_len = seq_len self.k = k # 压缩后的序列长度 # 标准的 Q, K, V 投影 self.w_q = nn.Linear(d_model, d_model) self.w_k = nn.Linear(d_model, d_model) self.w_v = nn.Linear(d_model, d_model) self.w_o = nn.Linear(d_model, d_model) # Linformer 特有的投影矩阵 E 和 F，将 n 维压缩到 k 维 # 注意：这里 E 和 F 是参数，可学习。也可以选择固定（如随机高斯初始化）。 self.E = nn.Parameter(torch.randn(k, seq_len)) self.F = nn.Parameter(torch.randn(k, seq_len)) self.dropout = nn.Dropout(dropout) def forward(self, x, mask=None): # x: [batch_size, seq_len, d_model] batch_size, seq_len, _ = x.shape assert seq_len == self.seq_len, f"输入序列长度{seq_len}与初始化长度{self.seq_len}不符" # 1. 计算 Q, K, V Q = self.w_q(x) # [B, n, d_model] K = self.w_k(x) # [B, n, d_model] V = self.w_v(x) # [B, n, d_model] # 2. 多头切分 Q = Q.view(batch_size, seq_len, self.n_heads, self.d_k).transpose(1, 2) # [B, h, n, d_k] K = K.view(batch_size, seq_len, self.n_heads, self.d_k).transpose(1, 2) # [B, h, n, d_k] V = V.view(batch_size, seq_len, self.n_heads, self.d_k).transpose(1, 2) # [B, h, n, d_k] # 3. Linformer 关键步骤：压缩 K 和 V 的序列维度 # E, F: [k, n] # 为了批量处理，需要扩展维度并转置 E_batch = self.E.unsqueeze(0).unsqueeze(0) # [1, 1, k, n] F_batch = self.F.unsqueeze(0).unsqueeze(0) # [1, 1, k, n] # 压缩 K: [B, h, n, d_k] -> [B, h, k, d_k] K_compressed = torch.matmul(E_batch, K) # 在最后两个维度做矩阵乘 # 压缩 V: [B, h, n, d_k] -> [B, h, k, d_k] V_compressed = torch.matmul(F_batch, V) # 4. 计算压缩后的注意力得分 # Q: [B, h, n, d_k], K_compressed: [B, h, k, d_k] # scores: [B, h, n, k] scores = torch.matmul(Q, K_compressed.transpose(-2, -1)) / (self.d_k ** 0.5) if mask is not None: # mask 需要适配新的维度 [B, 1, n, k] 或 [B, n, k] scores = scores.masked_fill(mask == 0, -1e9) attn_weights = F.softmax(scores, dim=-1) attn_weights = self.dropout(attn_weights) # 5. 应用注意力权重到压缩后的 V 上 # attn_weights: [B, h, n, k], V_compressed: [B, h, k, d_k] context = torch.matmul(attn_weights, V_compressed) # [B, h, n, d_k] # 6. 合并多头，输出投影 context = context.transpose(1, 2).contiguous().view(batch_size, seq_len, self.d_model) output = self.w_o(context) return output

关键解释：

• 投影矩阵 E 和 F：它们是可学习的参数，形状为[k, n]。这意味着模型需要学习如何将长序列的信息有效地总结到 $k$ 个“摘要”向量中。也可以将其初始化为固定矩阵（如随机正交矩阵）并冻结，以节省参数。
• 序列长度固定：注意__init__中需要seq_len。经典的 Linformer 实现假设输入序列长度是固定的。对于可变长度序列，需要更复杂的处理（如池化或自适应投影）。
• 复杂度：计算scores时，矩阵乘法是[n, d_k]与[d_k, k]，复杂度为 $O(n k d_k)$，是线性的。

2.3 Linformer 的优缺点与适用场景

3. Performer：通过核化与结合律重构注意力计算

Performer（FAVOR+， Fast Attention Via positive Orthogonal Random features）采用了与 Linformer 完全不同的思路。它不直接压缩注意力矩阵，而是利用数学变换，将注意力计算顺序重排，从而避免显式构造 $n \times n$ 矩阵。其核心是核函数（Kernel）和结合律（Associative Property）。

3.1 核心思想：将注意力重写为核函数形式

回顾标准注意力公式：$A = softmax(\frac{QK^T}{\sqrt{d_k}})$。Softmax 可以看作一个函数，作用于 $Q$ 和 $K$ 的每一对行向量的点积：$exp(q_i \cdot k_j^T)$。

Performer 的关键洞察是，可以将 $exp(q \cdot k^T)$ 近似表示为某个特征映射 $\phi(\cdot)$ 的内积： $exp(q \cdot k^T) \approx \phi(q) \cdot \phi(k)^T$ 其中 $\phi: \mathbb{R}^{d} \to \mathbb{R}^{m}$ 是一个将 $d$ 维向量映射到 $m$ 维（$m$ 通常远小于 $n$）特征空间的函数。这个技巧在机器学习中称为“核技巧”（Kernel Trick）。

如果这个近似成立，那么注意力输出 $O_i$（第 $i$ 个位置的输出）的计算可以重写： $O_i = \sum_{j=1}^{n} \frac{exp(q_i \cdot k_j^T)}{\sum_{l=1}^{n} exp(q_i \cdot k_l^T)} v_j = \frac{\sum_{j=1}^{n} exp(q_i \cdot k_j^T) v_j}{\sum_{j=1}^{n} exp(q_i \cdot k_j^T)}$ 代入核近似： $O_i \approx \frac{\sum_{j=1}^{n} [\phi(q_i) \cdot \phi(k_j)^T] v_j}{\sum_{j=1}^{n} [\phi(q_i) \cdot \phi(k_j)^T]} = \frac{\phi(q_i) \cdot [\sum_{j=1}^{n} \phi(k_j)^T \otimes v_j]}{\phi(q_i) \cdot [\sum_{j=1}^{n} \phi(k_j)^T]}$

这里 $\otimes$ 表示外积。注意看，分子分母中与 $i$ 无关的部分 $\sum_{j=1}^{n} \phi(k_j)^T \otimes v_j$ 和 $\sum_{j=1}^{n} \phi(k_j)^T$可以在遍历所有 $i$ 之前一次性计算出来！计算这两个聚合项的复杂度是 $O(n m d_v)$。然后对于每个 $i$，我们只需要计算 $\phi(q_i)$ 与这两个聚合项的内积，复杂度是 $O(m d_v)$，对于所有 $i$ 就是 $O(n m d_v)$。因此，总复杂度从 $O(n^2 d)$ 降为 $O(n m d)$。由于 $m$ 是固定超参数（如 256），复杂度是线性的 $O(n)$。

3.2 关键实现：随机特征映射（Random Feature Map）

如何构造这个特征映射 $\phi$ 呢？Performer 使用了随机傅里叶特征（Random Fourier Features, RFF）的一种变体，来近似高斯核，进而近似 softmax 中的指数函数。具体来说，使用以下映射： $\phi(x) = \frac{1}{\sqrt{m}} exp(Wx + b)$ 其中：

• $W \in \mathbb{R}^{m \times d}$ 的每一行从正态分布 $N(0, 1)$ 中采样。
• $b \in \mathbb{R}^{m}$ 的每个元素从均匀分布 $U(0, 2\pi)$ 中采样。
• $exp$ 是逐元素的指数函数（对复数取实部，但实现中常用cos和sin组合）。

在训练时，$W$ 和 $b$ 通常是固定的、随机的、不参与训练的。这就是“随机特征”。也有研究尝试让其可学习。

以下是 Performer 注意力层的简化 PyTorch 实现核心部分：

import torch import torch.nn as nn import math def orthogonal_random_matrix(num_rows, num_cols): """生成正交随机矩阵，比纯随机高斯矩阵方差更小，近似更好。""" q, _ = torch.linalg.qr(torch.randn(num_rows, num_cols)) return q.T # 返回 [num_cols, num_rows]? 注意维度匹配，这里仅为示意。 class PerformerAttention(nn.Module): def __init__(self, d_model, n_heads, m=256, dropout=0.1): super().__init__() assert d_model % n_heads == 0 self.d_model = d_model self.n_heads = n_heads self.d_k = d_model // n_heads self.m = m # 随机特征维度 self.dropout = nn.Dropout(dropout) # 标准的 Q, K, V 投影 self.w_q = nn.Linear(d_model, d_model) self.w_k = nn.Linear(d_model, d_model) self.w_v = nn.Linear(d_model, d_model) self.w_o = nn.Linear(d_model, d_model) # 随机特征映射的参数 W 和 b (固定，不训练) # 为每个注意力头单独生成？通常共享。 self.register_buffer('W', torch.randn(m, self.d_k) / (d_model ** 0.25)) # 缩放 self.register_buffer('b', torch.rand(m) * 2 * math.pi) def random_feature_map(self, x): """计算随机特征映射 phi(x)。x: [..., d_k]""" # 计算 Wx + b proj = torch.matmul(x, self.W.T) + self.b # [..., m] # 使用 cos 和 sin 组合，对应 exp(i * (Wx+b)) 的实部和虚部，然后拼接 # 这是 FAVOR+ 算法中的一种稳定实现 cos_part = torch.cos(proj) sin_part = torch.sin(proj) # 拼接后特征维度变为 2*m return torch.cat([cos_part, sin_part], dim=-1) / (self.m ** 0.5) # [..., 2*m] def forward(self, x, mask=None): batch_size, seq_len, _ = x.shape # 1. 计算 Q, K, V Q = self.w_q(x) K = self.w_k(x) V = self.w_v(x) # 2. 多头切分 Q = Q.view(batch_size, seq_len, self.n_heads, self.d_k).transpose(1, 2) # [B, h, n, d_k] K = K.view(batch_size, seq_len, self.n_heads, self.d_k).transpose(1, 2) V = V.view(batch_size, seq_len, self.n_heads, self.d_k).transpose(1, 2) # 3. 应用随机特征映射 Q_prime = self.random_feature_map(Q) # [B, h, n, 2*m] K_prime = self.random_feature_map(K) # [B, h, n, 2*m] # 4. 线性注意力核心计算：利用结合律 # 计算分母项：sum(K_prime, dim=2) -> [B, h, 2*m] denominator = torch.sum(K_prime, dim=2, keepdim=False) # [B, h, 2*m] # 计算分子项：sum(K_prime^T * V)，利用广播和矩阵乘 # K_prime: [B, h, n, 2*m] -> 转置最后两维？我们需要 [B, h, 2*m, n] # V: [B, h, n, d_k] # 更高效的做法： (K_prime.transpose(-2, -1) @ V) -> [B, h, 2*m, d_k] numerator = torch.matmul(K_prime.transpose(-2, -1), V) # [B, h, 2*m, d_k] # 5. 计算输出 # 对于每个查询位置 i: output_i = (Q_prime_i @ numerator) / (Q_prime_i @ denominator) # 使用矩阵乘一次性计算所有 i # Q_prime: [B, h, n, 2*m], numerator: [B, h, 2*m, d_k] context = torch.matmul(Q_prime, numerator) # [B, h, n, d_k] # 归一化因子： Q_prime: [B, h, n, 2*m], denominator: [B, h, 2*m] -> 需要扩展维度 norm = torch.matmul(Q_prime, denominator.unsqueeze(-1)) # [B, h, n, 1] context = context / (norm + 1e-8) # 防止除零 # 6. 合并多头，输出投影 context = context.transpose(1, 2).contiguous().view(batch_size, seq_len, self.d_model) output = self.w_o(context) return output

关键解释：

• 随机特征映射：random_feature_map函数是核心。它将 $d_k$ 维的 $q$ 或 $k$ 向量映射到 $2*m$ 维空间。这里的 $W$ 和 $b$ 是固定的随机参数，使用register_buffer注册，不参与梯度更新。
• 结合律的运用：注意第4步，我们一次性计算了denominator（所有 $K$ 的随机特征之和）和numerator（所有 $K$ 的随机特征与 $V$ 的加权外积之和）。这两个张量的大小与序列长度 $n$ 无关，只与 $m$ 和 $d_k$ 有关。
• 线性复杂度：后续计算context和norm时，主要的矩阵乘法是[n, 2*m]与[2*m, d_k]，复杂度为 $O(n m d_k)$，是线性的。

3.3 Performer 的优缺点与适用场景

4. 对比、选型与工程实践指南

理解了两种机制的原理后，我们需要在具体项目中做出选择。下表从多个维度对比 Linformer 和 Performer：

4.1 如何选择：决策清单

面对一个长序列任务时，可以按以下清单决策：

1. 序列长度是否固定且已知？

   • 是：Linformer 和 Performer 都可以考虑。如果任务简单，想快速验证，Linformer 实现更简单。
   • 否：优先选择Performer，因为它天然支持可变长度。

2. 对注意力的精确度要求有多高？

   • 要求极高：可能需要谨慎测试。先在标准注意力上取得基线，然后逐步替换为线性注意力，观察性能下降是否在可接受范围内。Performer 可以通过增大 $m$ 来提高精度。
   • 有一定容忍度：两者都可以尝试。Performer 的随机性可能带来轻微波动，但通常平均效果不错。

3. 资源瓶颈主要是内存还是计算？

   • 内存：两者都能极大缓解。Performer 在极长序列下内存优势更明显，因为它完全不构造 $n \times n$ 矩阵。
   • 计算速度：理论上都是 $O(n)$，但实际性能取决于框架优化、硬件和具体实现。需要进行基准测试。

4. 任务类型是编码（Encoder）还是解码（Decoder）？

   • 编码：两者都支持良好。
   • 自回归解码（如 GPT）：需要因果注意力。Performer 有专门的因果掩码实现（FAVOR+ causal）。Linformer 也需要调整投影方式以适应因果性。这部分实现更复杂，建议直接使用成熟的库（如xformers,fast_transformers）。

4.2 工程实践与常见问题排查

环境准备与依赖建议使用 PyTorch 或 TensorFlow 最新稳定版。对于 Performer，可以考虑使用社区维护的高效实现库，如fast_transformers或linear_attention_transformer，它们经过了充分优化。

# 示例：安装一个包含多种高效注意力实现的库 pip install torch # 可以选择性地安装专门库，但本文建议理解原理后自行实现或适配 # pip install fast-transformers # pip install linear-attention-transformer

集成到现有模型以替换 PyTorch Transformer Encoder 中的自注意力层为例：

# 假设我们有一个标准的 TransformerEncoderLayer from torch.nn import TransformerEncoderLayer class CustomTransformerEncoderLayer(TransformerEncoderLayer): def __init__(self, d_model, nhead, dim_feedforward=2048, dropout=0.1, attention_type='performer', **kwargs): super().__init__(d_model, nhead, dim_feedforward, dropout) # 替换掉自注意力模块 del self.self_attn if attention_type == 'performer': self.self_attn = PerformerAttention(d_model, nhead, **kwargs) elif attention_type == 'linformer': # 需要传入 seq_len seq_len = kwargs.pop('seq_len') self.self_attn = LinformerAttention(d_model, nhead, seq_len, **kwargs) else: raise ValueError(f"Unsupported attention type: {attention_type}")

常见问题与排查

生产环境最佳实践

1. 从小规模开始验证：先在小型数据集和模型上验证线性注意力层的效果和速度，再扩展到全量。
2. 进行严格的 A/B 测试：在相同的计算预算（如训练时间、GPU 内存）下，对比线性注意力模型和标准模型在验证集上的性能。
3. 监控注意力分布：可视化或统计标准注意力和线性注意力输出的差异，了解近似引入了何种变化。
4. 考虑混合架构：不必全部替换。可以在模型前半部分（处理局部特征）使用标准注意力或更高效的局部注意力，在后半部分（处理全局信息）使用线性注意力。
5. 利用社区优化：生产环境建议使用xformers、DeepSpeed或flash-attention（其最新版本也包含了线性注意力优化）等经过工业级优化的库，它们通常提供了更高效、更稳定的实现。

Linformer 和 Performer 为我们打开了高效 Transformer 的大门。它们从不同的数学角度（低秩近似与核方法）攻克了平方复杂度的难题。选择哪一种，取决于你的序列特性、精度要求和工程约束。理解其原理，能帮助你在模型优化中做出更明智的决策，而不仅仅是调用一个黑盒 API。在实际应用中，不妨以标准 Transformer 为基线，逐步引入这些线性化技术，并在性能、速度和资源之间找到属于你项目的最佳平衡点。下一步，可以探索其他线性注意力变体，如 Linear Transformer（基于核的另一种形式）、Reformer（基于局部敏感哈希 LSH）等，进一步丰富你的长序列处理工具箱。