想象你站在大学食堂门口，肚子饿得咕咕叫。标准 Attention 的工作方式是：你作为新生（query），挨个跑到每个窗口师傅（key）面前问“你这有什么菜？”，师傅报完菜名（value），你掂量一下再决定打什么。N 个学生 × N 个窗口，就得进行 N² 次对话。窗口少无所谓，可当食堂开到了 10 万人（长序列），这对话量立刻把大厅挤爆。Linear Attention 的思路很朴素：食堂干脆在门口立一块大黑板，师傅们提前把拿手菜的口味标签汇总上去，每个学生只需要看一眼黑板（全局聚合一次），就知道自己该找谁。于是 N² 次问询变成了 2N 次“看黑板 + 取餐”。这就是线性注意力——把注意力计算的平方复杂度硬生生拉到线性，代价是黑板上的“口味摘要”可能丢了一点细节。本文从食堂的排队困境讲起，带你搞懂线性化的数学技巧、典型方法、精度权衡、位置编码配合，以及到底什么场景下这招才划算。

岗位关联

对大模型从业者来说，这是处理长文本、降低推理成本的核心武器之一：搞懂 Linear Attention，你就能在 KV Cache 膨胀和上下文长度之间找到新的工程平衡点。

目录
  1. 可视化演示
  2. 瓶颈剖析：食堂里爆掉的对话量
  3. 线性化核心：先把菜谱汇总好
  4. 核技巧近似：用口味标签代替亲自尝菜
  5. 典型方法：两种主流黑板方案
  6. 状态空间视角：随身携带的账本
  7. 精度权衡：摘要的代价
  8. 位置编码配合：别让顺序信息走丢
  9. 应用落地：什么时候这招才划算
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示标准注意力O(n²)矩阵计算、线性注意力核分解O(n)流程与复杂度对比，支持模式切换与参数调节。

本节配有交互动效（进入视口后自动加载，约 3KB）。

标准注意力O(n²)矩阵 Q×K^T生成n×n注意力矩阵 平方复杂度限制长序列 softmax(QK^T/√d)V 标准注意力需计算完整n×n注意力矩阵

瓶颈剖析：食堂里爆掉的对话量

食堂开饭了。标准 Attention 的工作方式，是每个新生（query）挨个跑到每个窗口师傅（key）面前问：“你这里有什么菜？” 师傅报菜名（value），新生听完再决定是否取餐。为了公平，每个新生都必须问遍所有窗口。于是 N 个新生和 N 个窗口之间，总共要进行 N×N 次对话。食堂有 100 个窗口、100 个学生时，是 1 万次问候；可当食堂变成“长文本大模型”，N 从几百涨到几万，对话次数就是亿级别的，食堂立刻水泄不通。

这就是标准 Attention 的平方复杂度瓶颈。你输入一句话，模型把它切成 N 个 token；每个 token 作为 query，都要去和全部 N 个 token 算相似度，得到 N×N 的注意力矩阵。这不仅是计算量的墙，更是显存的墙——矩阵要存在内存里，N 翻一倍，内存翻四倍。处理一万 token 的文本，注意力矩阵就有 1 亿个格子，GPU 都喊疼。

回到食堂，问题很清楚：N 越大，两两问询越致命。想接待上万人的食堂，必须想办法把“挨个问”变成“看黑板”。

Attention(Q,K,V)=softmax ⁣(QK⊤d)V∈RN×d\displaystyle \text{Attention}(Q,K,V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d}}\right)V \in \mathbb{R}^{N\times d}
这个公式说明：Q 和 K 先乘出一个 N×N 的大矩阵，这是处理长序列时计算量爆炸的根源。
  1. 生成问询表 QKᵀ把 N 个 query 与 N 个 key 做点积，得到 N×N 的相似度矩阵。相当于每个新生跑遍每个窗口，记下“我和这位师傅合不合”。
    QK⊤∈RN×NQK^\top \in \mathbb{R}^{N\times N}
  2. 缩放防溢出 √d除以特征维度 d 的平方根，防止点积数值太大，把后续的 softmax 推向饱和区。
    QK⊤d\frac{QK^\top}{\sqrt{d}}
  3. 归一化成权重 softmax对每一行做归一化，让相似度变成“和为 1”的权重，保证哪个窗口都不被饿死。
    softmax ⁣(QK⊤d)\text{softmax}\!\left(\frac{QK^\top}{\sqrt{d}}\right)
  4. 加权取餐乘 V用权重矩阵去加权求和所有 value，得到每个 token 的最终表示，复杂度是 O(N²d)。
    softmax ⁣(QK⊤d)V\text{softmax}\!\left(\frac{QK^\top}{\sqrt{d}}\right)V

线性化核心：先把菜谱汇总好

既然挨个问太累，聪明的食堂管理员想出一招：与其让每个新生去问师傅，不如让师傅们先把“拿手菜摘要”集中写到一张大黑板上。新生只要扫一眼黑板，就知道哪个窗口合自己口味，然后直接去取餐。关键是——“汇总菜谱”这件事只用做一次，窗口再多也只是汇总一次，而不是每个新生重复做一遍。

这个操作在数学上，就是矩阵乘法的结合律重排。标准 Attention 里，必须先算 Q 和 K 的相似度矩阵（N×N），再乘 V。但如果相似度能写成 φ(q) 和 φ(k) 的点积形式，那乘法的顺序就可以倒过来：先算 φ(K)ᵀV 这个 d×d 的小矩阵，再让它和每个 φ(q) 相乘。d 是隐藏维度，通常远小于 N，于是大头成本从“N² 次两两对话”变成“N 次看黑板 + 一次 d×d 汇总”。

食堂因此清净了：黑板挂一次，万人共享。这里的核心洞察就是“聚合先行、查询后至”，把平方级的两两问询压缩成线性的看黑板。

∑j=1N(ϕ(qi)⊤ϕ(kj))vj=ϕ(qi)⊤∑j=1Nϕ(kj)vj⊤⏟d×d 记忆矩阵\displaystyle \sum_{j=1}^{N} \left(\phi(q_i)^\top \phi(k_j)\right)v_j = \phi(q_i)^\top \underbrace{\sum_{j=1}^{N} \phi(k_j) v_j^\top}_{d\times d\ \text{记忆矩阵}}
这个等式把“每个 query 都要遍历所有 key”变成“先把所有 key 和 value 汇总成一个 d×d 的记忆矩阵，再让每个 query 去查它”。
  1. 相似度分解把 q 与 k 的相似度拆成 φ(q)ᵀφ(k)，这是后面一切换序的前提——只有乘积可分离，才能调换求和顺序。
    ϕ(qi)⊤ϕ(kj)\phi(q_i)^\top \phi(k_j)
  2. 求和换序利用乘法的分配律，把对 j 的求和挪到 φ(q)ᵀ 的右边。就像抄菜谱这件事挪到“每个学生看菜谱”之前。
    ∑j=1Nϕ(qi)⊤ϕ(kj)vj=ϕ(qi)⊤∑j=1Nϕ(kj)vj⊤\sum_{j=1}^{N} \phi(q_i)^\top \phi(k_j) v_j = \phi(q_i)^\top \sum_{j=1}^{N} \phi(k_j) v_j^\top
  3. 先做汇总内部那一坨 \sum φ(k_j)v_jᵀ 是 d×d 的矩阵，只跟 k、v 有关，跟 N 个 query 都没关系，全局只算一次。
    ∑j=1Nϕ(kj)vj⊤∈Rd×d\sum_{j=1}^{N} \phi(k_j) v_j^\top \in \mathbb{R}^{d\times d}
  4. 逐个查询每个 query 只需要做一次 d 维向量乘 d×d 矩阵的乘法，成本 O(Nd²)，不再有 N² 项。
    ϕ(qi)⊤⋅(… )\phi(q_i)^\top \cdot (\dots)

核技巧近似：用口味标签代替亲自尝菜

上节有个关键前提：相似度得能写成 φ(q)ᵀφ(k) 这种分解形式。可标准 softmax 里带着指数函数和归一化分母，天生拒绝拆开。怎么办？食堂的做法是：不再让师傅报完整菜名，而是给每道菜贴三个口味标签——辣度、甜度、咸度。新生也把自己的偏好写成标签，两边一对比，就能近似估算“合不合口味”。

这个“贴标签”在数学上叫核技巧（kernel trick）。找一个特征映射函数 φ，使得 φ(q) 和 φ(k) 的点积，能近似等于原来的 softmax 相似度。因为 φ 是逐 token 独立的，所以 q 和 k 完全可以分开计算，结合律立刻恢复。

这就像食堂从“挨个试吃”退化成“看标签点菜”：标签描述得再细致，也替代不了尝一口，但胜在快。只要标签设计得够好（核函数选得妙），损失就能压到很小。

softmax(q⊤k)≈ϕ(q)⊤ϕ(k)=1m∑r=1mf(ωr⊤q) f(ωr⊤k)\displaystyle \text{softmax}(q^\top k) \approx \phi(q)^\top \phi(k) = \frac{1}{m}\sum_{r=1}^{m} f(\omega_r^\top q)\, f(\omega_r^\top k)
softmax 相似度被近似成了“两个特征向量的点积”；m 是标签维度，可理解为黑板上有 m 个口味维度供对比。
  1. 标签投影 ω_r随机抽取 m 个方向向量 ω_r，把 q 和 k 分别投影上去。就像找了 m 位吃过百家饭的“品鉴官”，每人给菜打一个维度的分。
    ωr⊤q,ωr⊤k\omega_r^\top q,\quad \omega_r^\top k
  2. 非线性打分 f对投影结果套一个非线性函数 f（如指数或余弦），保证打分组装后能逼近 softmax 的形状。
    f(ωr⊤q),f(ωr⊤k)f(\omega_r^\top q),\quad f(\omega_r^\top k)
  3. 点积近似m 个维度得分对应相乘再求和，得到相似度估计。品鉴官越多，估算越接近真实口味。
    1m∑r=1mf(ωr⊤q) f(ωr⊤k)\frac{1}{m}\sum_{r=1}^{m} f(\omega_r^\top q)\, f(\omega_r^\top k)

典型方法：两种主流黑板方案

食堂改革的方案不止一种。第一种是 Linear Transformer，它用的标签函数最简单粗暴：φ(x) = elu(x) + 1。这个映射的好处是计算零成本、天然为正数，但近似 softmax 的精度一般，适合对精度要求不苛刻的场景。第二种是 Performer，它把“品鉴官”这一套做到了理论极致：用随机特征（random features）无偏地近似 softmax 核。方向向量 ω 从高斯分布里采样，再对每个 token 做指数变换，从理论上保证期望值正好等于 softmax。

FAVOR+ 是 Performer 的核心机制，全称是“通过正交随机特征实现无偏注意力估计”。它给每个 token 生成 m 维特征（m 是超参数），然后把 m 维特征喂进我们之前说的“先聚合再查询”流程。m 越大，近似越准，但黑板上要写的标签越多，计算量也随之上涨。

两类方法各有拥趸：Linear Transformer 图便宜省事，Performer 图理论严谨。实际选型时，就像食堂选黑板——预算紧就贴张纸，要求高就上真液晶屏，取决于你要服务的食客规模。

ϕ(x)=exp⁡ ⁣(−∥x∥22)m[exp⁡(ω1⊤x), exp⁡(ω2⊤x), …, exp⁡(ωm⊤x)]\displaystyle \phi(x) = \frac{\exp\!\left(-\dfrac{\|x\|^2}{2}\right)}{\sqrt{m}} \left[\exp(\omega_1^\top x),\ \exp(\omega_2^\top x),\ \dots,\ \exp(\omega_m^\top x)\right]
这是 Performer 的特征映射：它把每个 token 投影成 m 维，让 φ(q)ᵀφ(k) 的期望恰好等于 softmax(qᵀk)。
  1. 范数惩罚因子乘上 exp(-‖x‖²/2)，用来抵消后面指数项里引入的 x 自身范数，保证期望不偏。
    exp⁡ ⁣(−∥x∥22)\exp\!\left(-\frac{\|x\|^2}{2}\right)
  2. 随机投影 ω_rω_r 从标准正态分布采样，相当于随机雇佣 m 位品鉴官，每人给出一道菜一个维度上的原始分。
    ωr∼N(0,I)\omega_r \sim \mathcal{N}(0, I)
  3. 指数打分对投影结果取指数，配合前一项，恰好配出高斯核；m 个维度拼成一个向量。
    1mexp⁡ ⁣(−∥x∥22)[exp⁡(ω1⊤x),…,exp⁡(ωm⊤x)]\frac{1}{\sqrt{m}}\exp\!\left(-\frac{\|x\|^2}{2}\right)\bigl[\exp(\omega_1^\top x),\dots,\exp(\omega_m^\top x)\bigr]
  4. 内积即核两个 φ 做内积后取期望，正好还原 softmax 的行归一化形状，所以是无偏估计。
    E[ϕ(q)⊤ϕ(k)]=exp⁡ ⁣(∥q+k∥2−∥q∥2−∥k∥22)=exp⁡(q⊤k)\mathbb{E}\bigl[\phi(q)^\top \phi(k)\bigr] = \exp\!\left(\frac{\|q+k\|^2 - \|q\|^2 - \|k\|^2}{2}\right) = \exp(q^\top k)

状态空间视角：随身携带的账本

食堂里还有一类更极端的做法：新生根本不看黑板，而是从进门开始随身带一本小账本（S）。每路过一个窗口，就把师傅的招牌菜口味和菜量记进账本（累加 φ(k)vᵀ），全程只记摘要、不抄全文。走到自己想吃的窗口前，翻开账本，心里就有数了。这个视角叫状态空间视角——注意力不再是“回头看整段序列”，而是“边走边记，账本永只一页”。

这个递推过程写下来非常漂亮：每来一个新的 k、v 对，就把 φ(k)vᵀ 累加进 S 矩阵；同时另一个计数器 z 累加 φ(k)，用来做归一化。处理完当前位置后，输出 o 只需要当前 query 和账本 S。这意味着从头到尾，你只需要保留一份 d×d 的记忆矩阵加一个 d 维计数器，与序列长度 N 彻底无关。

这个视角直接催生了一族“线性递归模型”。推理时不管序列多长，账本只有一页，内存开销恒定，很适合流式生成——大模型边说边记，不再为整段历史缓存 KV。

Si=Si−1+ϕ(ki) vi⊤,zi=zi−1+ϕ(ki),oi=ϕ(qi)⊤Siϕ(qi)⊤zi\displaystyle S_i = S_{i-1} + \phi(k_i)\, v_i^\top,\qquad z_i = z_{i-1} + \phi(k_i),\qquad o_i = \frac{\phi(q_i)^\top S_i}{\phi(q_i)^\top z_i}
递推式说明：新状态 = 旧状态 + 当前 token 的增量；输出只与当前 query 和固定大小的状态有关，推理时内存 O(1)。
  1. 账本更新S_i 由上一时刻的 S_{i-1} 加上外积 φ(k_i)v_iᵀ 得到，新来的 k、v 信息被“压缩”进固定的 d×d 矩阵。
    Si=Si−1+ϕ(ki)vi⊤S_i = S_{i-1} + \phi(k_i) v_i^\top
  2. 分母累计z_i 每步累加 φ(k_i)，它在最终输出里起 softmax 分母的作用，保证权重之和合理。
    zi=zi−1+ϕ(ki)z_i = z_{i-1} + \phi(k_i)
  3. 当前输出o_i 用当前 query 去查账本 S_i，再除以 z 的投影做归一化，不需要回头访问任何历史 token。
    oi=ϕ(qi)⊤Siϕ(qi)⊤zio_i = \frac{\phi(q_i)^\top S_i}{\phi(q_i)^\top z_i}

精度权衡：摘要的代价

黑板和账本都带来同一个问题：摘要毕竟不是原话。师傅的招牌菜“宫保鸡丁”可能还有“花生米必须是现炸的”这种讲究，黑板上的口味标签根本写不下。这就是线性注意力的精度损失根源——核近似不是精确等于 softmax，而是有偏估计，偏差大小与标签维度 m 有关。m 越大，黑板上的标签分得越细，近似越准。

具体来说，随机特征近似的方差和 m 成反比。如果你把 m 设得很大，精度确实能逼近标准注意力，但计算量也涨回去，线性优势被吃掉；m 设小了，速度快了，但模型可能“点错菜”。这是一个此消彼长的拔河：效率和精度在天平两端，你要根据任务自己找平衡点。

所以别指望线性注意力是免费的午餐。你得想清楚：你的食堂是来十万人的大排档，还是只服务几十人的私房菜馆？前者用摘要能救急，后者还是老老实实挨个问。

Var ⁣[ϕ(q)⊤ϕ(k)]∝1m\displaystyle \text{Var}\!\left[\phi(q)^\top \phi(k)\right] \propto \frac{1}{m}
特征维度 m 越大，相似度估计的方差越小、越稳定；代价是计算量随 m 线性上升。
  1. 方差含义多次独立采样特征时，φ(q)ᵀφ(k) 的估计值波动幅度。方差大 = 品位鉴官不同，菜谱预测忽高忽低。
    Var ⁣[ϕ(q)⊤ϕ(k)]\text{Var}\!\left[\phi(q)^\top \phi(k)\right]
  2. 反比关系方差 ∝ 1/m，说明每多请一位品鉴官，波动就小一分；但请太多人，打分的开销也上去了。
    ∝1m\propto \frac{1}{m}
  3. 工程选择实践里 m 常取 64~256，是“够用就好”的经验值，过犹不及。
    m∈[64,256]m \in [64, 256]

位置编码配合：别让顺序信息走丢

黑板摘要什么都好，但有个致命毛病：它容易丢掉“上菜顺序”。食堂里“先喝汤再吃主菜”是有讲究的，可标签汇总时，师傅们把自己的菜一股脑贴上去，谁先谁后全乱了。标准 Attention 里，位置信息靠 Q、K 的点积携带；而线性注意力把相似度改写成了 φ(q)ᵀφ(k)，原本点积里能自然融合的旋转位置编码（RoPE），在特征空间里不一定还能保持相对位置的几何意义。

RoPE 的思想很优雅：把每个 token 的 q、k 向量旋转一个与位置成比例的角度，两个向量做点积时，角度差正好编码相对位置。可问题在于，线性注意力里真正参与点积的是 φ(q)、φ(k) 而不是 q、k。旋转矩阵作用在 q、k 上的性质，作用在 φ(q)、φ(k) 上就未必成立了——除非重新设计特征映射，或者在聚合过程中显式注入位置偏置。

实践中常用的补救方案有：在特征 φ 上叠加绝对位置编码，或者在聚合时用局部窗口混合位置信息。总之，给线性注意力加位置信息，不能想当然地照搬标准 Transformer 的做法，得专门设计。

(Riqi)⊤(Rjkj)=qi⊤Rj−i kj\displaystyle (R_i q_i)^\top (R_j k_j) = q_i^\top R_{j-i}\, k_j
R 是旋转矩阵：q_i 和 k_j 各自旋转后点积，等价于原始点积乘一个与相对位置 j−i 有关的旋转矩阵。
  1. 旋转注入位置把第 i 个位置的 q 旋转 R_i 角度，第 j 个位置的 k 旋转 R_j 角度，位置信息就藏进了向量方向。
    (Riqi)⊤(Rjkj)(R_i q_i)^\top (R_j k_j)
  2. 合并旋转矩阵利用旋转矩阵的正交性，R_iᵀR_j 可以合并成 R_{j−i}，于是点积只依赖位置差。
    qi⊤Rj−i kjq_i^\top R_{j-i}\, k_j
  3. 线性注意力的难题φ(q)ᵀφ(k) 里没有直接的 qᵀk 项，R_{j−i} 无法这样简单地“夹”进去，所以需要特殊改造。
    ϕ(q)⊤ϕ(k)≠q⊤Rj−ik\phi(q)^\top \phi(k) \neq q^\top R_{j-i} k

应用落地：什么时候这招才划算

食堂改革到底值不值？答案是：小食堂不值，大食堂真香。当 N 很小（比如一句短对话），线性注意力的黑板成本和标签开销甚至比直接问询还高；只有 N 远超 d（隐藏维度）时，“先聚合再查询”的优势才真正爆发。复杂度对比一目了然：标准注意力约 2N²d 次乘法，线性注意力约 2Nd² 次，两者之比正比于 N/d。N 是 d 的百倍时，线性方案快两个数量级。

在真实产业里，最典型的场景是大模型长文本推理。推理是自回归的，标准注意力必须缓存全部历史 KV；序列一长，缓存撑爆显存。线性注意力靠递推账本，只需一份 d×d 的状态，显存恒定，吞吐自然就上去了。另一个场景是流式处理——语音识别、实时字幕、长视频理解，输入源源不断，线性注意力可以“边听边记”，不用回头重算。

一句话总结：食堂够大（N 够长）才值得上黑板。选型时要同时看精度敏感度和部署硬件——机器够猛、任务够长，线性注意力就是你的长文本利器。

标准Attention乘法数Linear Attention乘法数≈2N2d2Nd2=Nd\displaystyle \frac{\text{标准Attention乘法数}}{\text{Linear Attention乘法数}} \approx \frac{2N^2 d}{2Nd^2} = \frac{N}{d}
当序列长度 N 远大于隐藏维度 d 时，线性注意力的加速比约为 N/d；反之若 N 和 d 差不多，优势不大。
  1. 标准复杂度N×N 的注意力矩阵生成和相乘，共约 2N²d 次乘法。
    标准≈2N2d\text{标准} \approx 2N^2 d
  2. 线性复杂度φ(K)ᵀV 花 N 次外积聚合，Q 再乘 d×d 矩阵花 N 次内积，共约 2Nd² 次乘法。
    线性≈2Nd2\text{线性} \approx 2Nd^2
  3. 加速比两者相除，N 和 d 各约掉一个，得到 N/d 这一关键比值。
    2N2d2Nd2=Nd\frac{2N^2 d}{2Nd^2} = \frac{N}{d}

AI 应用场景

大模型长文本推理服务

阶段：模型推理与部署优化

解决的问题：标准 Attention 在长序列推理时，KV Cache 随序列长度线性增长，显存爆炸，长对话和长文档生成经常 OOM。线性注意力把 KV 压缩成固定大小的状态矩阵，显存开销恒定，可以持续生成数万 token 的长文本。

具体案例：某智能客服系统需要基于 50 万字的企业知识库做流式问答。传统 Transformer 加载完整上下文需要 8 张 A100，切到 Performer 风格线性注意力后，压缩到 1 张卡即可承载，首 token 延迟从 4.2 秒降到 1.8 秒。代价是回答的细节忠实度略有下降，需配合检索增强来弥补。

长文档摘要与检索增强

阶段：模型训练与微调

解决的问题：对论文、合同、书籍做全量阅读理解时，标准 Attention 的平方复杂度让训练窗口难以突破 32k。线性注意力允许把训练窗口拉到 128k 甚至更长，让模型一次看完整本书再写摘要。

具体案例：法律科技公司用 Linear Transformer 微调领域模型，把一份 300 页的合同全文编码后直接生成风险摘要。相比先切片再拼接的旧方案，遗漏关键条款的风险降低 37%，训练成本下降 60%。

实时流式语音与视频理解

阶段：在线推理与流式处理

解决的问题：语音识别、实时字幕这类任务要求“边说边出结果”，不能等整段说完再处理。标准 Attention 每来一个语音帧就要回头重算整段历史，延迟高；线性注意力的递推账本天然支持增量更新。

具体案例：实时会议转写系统将音频按 0.5 秒切片送入线性注意力解码器，状态随讲话人不断滚动更新，字幕延迟稳定在 1 秒以内，长会议连续转写 3 小时不触发显存溢出。

Python 演示

python52 行
import numpy as npimport time def elu_plus_one(x):    return np.where(x > 0, x, np.exp(x) - 1.0) + 1.0 def standard_attention(q, k, v):    d = q.shape[-1]    scores = q @ k.T / np.sqrt(d)    scores = scores - scores.max(axis=-1, keepdims=True)    probs = np.exp(scores)    probs = probs / probs.sum(axis=-1, keepdims=True)    return probs @ v def linear_attention(q, k, v):    phi_q = elu_plus_one(q)    phi_k = elu_plus_one(k)    s = phi_k.T @ v    z = phi_k.sum(axis=0)    return (phi_q @ s) / (phi_q @ z) def recurrent_linear_attention(q, k, v):    d = q.shape[-1]    s = np.zeros((d, d))    z = np.zeros(d)    outs = []    for i in range(len(q)):        s = s + np.outer(elu_plus_one(k[i]), v[i])        z = z + elu_plus_one(k[i])        p = elu_plus_one(q[i])        outs.append((p @ s) / (p @ z))    return np.stack(outs) N, D = 128, 16np.random.seed(0)q = np.random.randn(N, D)k = np.random.randn(N, D)v = np.random.randn(N, D) start = time.time()out_std = standard_attention(q, k, v)time_std = time.time() - start start = time.time()out_lin = linear_attention(q, k, v)time_lin = time.time() - start out_rec = recurrent_linear_attention(q, k, v)diff = np.abs(out_std - out_lin).mean()print("standard time: %.4fs, linear time: %.4fs" % (time_std, time_lin))print("mean abs diff with softmax: %.4f" % diff)print("recurrent matches chunked:", np.allclose(out_lin, out_rec, atol=1e-6))
目的：用纯 NumPy 实现标准 Attention、矩阵形式的线性注意力以及递推形式，对比输出差异与耗时，验证“结合律换序”和“状态递推”确实等价。
  1. elu_plus_one(x)定义特征映射 φ(x) = elu(x) + 1，对应 Linear Transformer 的核函数。加 1 保证特征恒为正，分母不会除零。
  2. scores = q @ k.T / np.sqrt(d)标准注意力的第一步：生成 N×N 相似度矩阵，这就是平方复杂度的来源。
  3. probs / probs.sum(axis=-1, keepdims=True)按行做 softmax 归一化，标准注意力必须逐行算，无法与 V 交换顺序。
  4. s = phi_k.T @ v线性注意力核心一步：先把所有 key 的特征和 value 聚合成 d×d 记忆矩阵，这一步与 query 无关。
  5. z = phi_k.sum(axis=0)累计归一化常数，等价于 softmax 分母在特征空间里的投影。
  6. (phi_q @ s) / (phi_q @ z)每个 query 只查一次记忆矩阵，复杂度从 O(N²d) 降到 O(Nd²)。
  7. s = s + np.outer(elu_plus_one(k[i]), v[i])递推形式的账本更新：新 token 到达只做一次外积累加，历史信息全部压缩进固定矩阵。
  8. outs.append((p @ s) / (p @ z))当前输出只依赖当前 query 和状态，推理时无需缓存任何历史 token。
  9. np.allclose(out_lin, out_rec, atol=1e-6)验证矩阵形式与逐 token 递推形式完全相等，说明两种实现是同一数学的两种写法。

常见误区

误区我觉得线性注意力只是换了个计算顺序，结果应该和标准 Attention 一模一样，可以随便替换，反正效果不变。

正解顺序确实可以换，但前提是相似度得写成 φ(q)ᵀφ(k) 这种可分解形式。标准 softmax 含指数和归一化分母，任何核近似都是近似而非等价。就像口味标签永远替代不了亲自尝菜——偏差是内生的。Linear Transformer 的简单核偏差尤其明显，Performer 虽是无偏估计，但方差依然存在，实践中通常会有 0.5~2 个点的精度损失。

为何常见：很多人看到矩阵结合律的推导，以为只是“重新分配括号”，忽略了第一步的 softmax 近似本身就是有损的。

误区既然复杂度从 O(N²) 降到 O(N)，那无论什么场景它都应该更快，直接用就完了。

正解复杂度说的是渐近行为，不是绝对速度。当序列长度 N 接近甚至小于隐藏维度 d 时，黑板加标签的开销比直接问询还高。工程实测里，N < 1024 时线性注意力往往更慢，只有 N 明显大于 d 才划算。选型要看 N/d 的比值，不是无脑换。

为何常见：把“渐进复杂度更优”误解为“所有输入规模下都更快”，忽略了常数项和特征映射的额外开销。

误区反正它已经把序列压成摘要了，位置可能不重要了；或者我直接照搬标准 Transformer 的 RoPE 就行。

正解恰恰相反，线性注意力通常比标准注意力更需要位置信息。标准 softmax 的指数归一化天然对“附近 token”更敏感，而线性注意力的全局聚合会把所有位置一视同仁地揉进账本，顺序信息损失更严重。更麻烦的是，RoPE 的旋转矩阵作用在 q、k 上没问题，但换成 φ(q)、φ(k) 后数学性质要重新验证，不能直接套。

为何常见：把位置编码当成“附加组件”，而不是与注意力机制数学性质深度绑定的结构，容易忽略线性化后编码方式不再兼容。

误区只要选一个能分解的相似度函数 φ(q)ᵀφ(k)，线性注意力就成了，反正效果差不多。

正解核函数的选择直接决定近似质量和数值稳定性。elu+1 核简单但没有理论保证；Performer 的随机特征经过精心推导，保证无偏。核选不好，轻则训练不稳定，重则注意力分布退化、模型不收敛。此外还要考虑分母归一化设计，否则输出幅度会漂移。

为何常见：只看到“可分解”这个形式要求，忽略了核函数本身对 attention 分布形态的塑造，以及数值稳定性的工程细节。

误区经常听人说什么低秩注意力、线性注意力，感觉它们是同一个东西，随便混用。

正解两者动机不同。线性注意力从“核函数可分解”出发，通过特征映射换序降复杂度；低秩近似则假设 N×N 的注意力矩阵本身就低秩，用矩阵分解直接逼近。Performer 的特征空间其实是高维的（m 维），并不假设注意力矩阵低秩。只是某些实现最后殊途同归，但分析路径和适用条件有区别。

为何常见：两者都能把复杂度降下来，且论文里常互相引用，初学者容易把“效果类似”当成“原理相同”。

面试题

Q1. 标准 Attention 的时间复杂度是多少？

单选题 · mid

  • A.O(N·d)
  • B.O(N²·d)← 正确答案
  • C.O(N·d²)
  • D.O(N²·d²)

答案：B。标准 Attention 需要先算 QKᵀ 生成 N×N 相似度矩阵，再乘 V，总复杂度 O(N²d)。A 是很多线性注意力论文的目标复杂度，C 是线性注意力交换顺序后的复杂度。食堂里每个学生都要问遍每个窗口，对话次数必然是 N²。

Q2. 线性注意力降低复杂度采用了哪些手段？

多选题 · mid

  • A.用特征映射近似 softmax← 正确答案
  • B.利用矩阵乘法结合律换序← 正确答案
  • C.对注意力矩阵做奇异值分解
  • D.先聚合 KV 再逐个查询← 正确答案

答案：ABD。线性注意力先用核技巧把 softmax 分解成 φ(q)ᵀφ(k)，再交换乘法顺序，先算 φ(K)ᵀV 聚合矩阵，最后让每个 query 查询。C 是低秩近似的思路，不属于线性注意力的标准路径。就像先汇总菜谱再让学生查，而不是复现 N² 次问询。

Q3. 从 O(N²d) 降到 O(Nd²)，关键的读写顺序变化是什么？

单选题 · hard

  • A.先算 QVᵀ 再乘 K
  • B.先算 φ(K)ᵀV 再乘 φ(Q)← 正确答案
  • C.先算 VKᵀ 再乘 Q
  • D.对 Q 做低秩分解

答案：B。核心是把 φ(K)ᵀV 这个 d×d 矩阵提前算好，每个 φ(q) 来查一次账本，复杂度变成 O(Nd²)。A 和 C 的乘法尺寸不对，D 是矩阵分解的思路。相当于师傅们先把菜谱汇总到大黑板，学生只扫一眼而不是挨个问。

Q4. Performer 用什么技巧近似 softmax 注意力？

单选题 · easy

  • A.低秩矩阵分解
  • B.随机特征映射← 正确答案
  • C.稀疏注意力采样
  • D.哈希分桶近似

答案：B。Performer 的核心 FAVOR+ 用随机特征（random features）把 softmax 核写成 φ(q)ᵀφ(k)，保证期望无偏。A 是线性低秩近似思路，C 是 BigBird 等稀疏注意力的思路，D 是 Reformer 的思路。食堂里 Performer 的做法是雇一批随机品鉴官给菜打分。

Q5. 线性注意力的递推形式在自回归推理时，缓存占用是多少？

单选题 · mid

  • A.O(N²) KV Cache
  • B.O(N) KV Cache
  • C.O(d²) 固定状态← 正确答案
  • D.O(Nd) KV Cache

答案：C。递推形式只维护一份 d×d 的记忆矩阵 S 和 d 维的归一化计数器 z，与序列长度 N 无关，因此是 O(d²) 常数内存。A 是标准 Attention 的显存噩梦，B 是部分 KV 压缩方案，D 接近标准量化缓存。就像随身账本永远只有一页，随走随记。

Q6. 线性注意力会带来哪些精度的代价？

多选题 · easy

  • A.softmax 被核函数近似← 正确答案
  • B.位置信息可能丢失← 正确答案
  • C.模型尺寸会变小
  • D.随机特征带来方差← 正确答案

答案：ABD。线性注意力的近似误差来自核函数替换 softmax 的偏差，以及随机特征估计的方差；全局聚合又容易稀释位置信息，可能需要额外位置编码方案。C 是参数量问题，与精度无关。口味标签再细，也不如亲自尝一口。

Q7. 随机特征维度 m 与近似精度的关系是？

单选题 · hard

  • A.方差正比于 m²
  • B.方差反比于 m← 正确答案
  • C.偏差正比于 m
  • D.与 m 无关

答案：B。随机特征近似的方差 ∝ 1/m，m 越大估计越稳定，但计算量也线性增加。A、C 方向反了，D 忽略了 m 的本质作用。品鉴官越多，菜谱预测越稳定，但请人的成本也越高。

Q8. 为什么 RoPE 不能直接套用到线性注意力？

单选题 · mid

  • A.RoPE 要求序列必须是偶数长度
  • B.线性注意力使用绝对值位置
  • C.φ(q)ᵀφ(k) 不保留 qᵀk 的旋转不变性← 正确答案
  • D.RoPE 仅适用于卷积网络

答案：C。RoPE 的优雅来自旋转矩阵可以合并成 R_{j−i}，这依赖原始点积 qᵀk。线性注意力中参与点积的是 φ(q)、φ(k)，旋转矩阵的性质不再成立，需要专门改造特征映射或换位置编码方案。就像标签上没法体现“上菜顺序”。

Q9. 以下哪些场景更适合使用线性注意力？

多选题 · mid

  • A.处理 10 万 token 的长文档← 正确答案
  • B.实时语音流式识别← 正确答案
  • C.短文本情感分类
  • D.自回归长文本生成← 正确答案

答案：ABD。线性注意力适合 N 远大于 d 的长序列、流式输入、自回归推理等场景。C 这类短任务 N 很小，线性注意力反而有额外的特征映射开销，不划算。大食堂才值得上黑板，小窗口直接问更快。

Q10. Linear Transformer 中常用的核函数 φ(x) 是？

单选题 · easy

  • A.φ(x) = elu(x) + 1← 正确答案
  • B.φ(x) = sigmoid(x)
  • C.φ(x) = tanh(x)
  • D.φ(x) = x²

答案：A。Linear Transformer 论文采用 elu(x) + 1 作为特征映射，计算简单且输出恒正，利于数值稳定。B、C 会输出负值或零附近的值，D 缺乏非线性表达能力。这相当于食堂选的“最省事标签纸”，便宜但精度一般。