NLP——线性注意力相关总结

Linear Attention 演进整体总结

  • 注意力机制的演进可视为一条从“精确但昂贵”到“高效且智能”的路径
  • 核心矛盾始终是：如何在有限的计算和内存预算下，让模型有效地处理和使用无限长的上下文信息

普通 Attention（Softmax Attention），精确但昂贵的回忆

  • 原始论文：Attention Is All You Need, Google Brain, NIPS 2017
  • 核心机制 ：标准 Transformer 的 Self-Attention 通过计算 Query 与所有 Key 之间的点积相似度，经 Softmax 归一化后作为权重，对 Value 进行加权求和：
    $$\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{softmax}\left(\frac{\mathbf{Q}\mathbf{K}^\top}{\sqrt{d_k} }\right)\mathbf{V}$$
    • \(\mathbf{Q}\in\mathbb{R}^{L\times d_k}\)、\(\mathbf{K}\in\mathbb{R}^{L\times d_k}\)、\(\mathbf{V}\in\mathbb{R}^{L\times d_v}\) 分别为 Query、Key、Value 矩阵
    • \(L\) 为序列长度
    • \(d_k\) 为 Key 维度
  • 这是一种内容寻址的联想记忆 ：每个 Query 可以“看到”所有历史 Token，并通过 Softmax 分配注意力权重，实现精准的信息检索
    • KV Cache 在生成时随序列长度线性增长，存储所有历史 Key 和 Value 以供后续 Token 使用
  • 核心瓶颈 ：处理长序列（如百万 Token 级）时，计算和内存开销迅速失控
    • 计算瓶颈：时间复杂度为 \(\mathcal{O}(L^2 \cdot d)\)
      • 注意：\(\mathcal{O}(L^2 \cdot d)\) 是处理整个序列的时间复杂度，如果仅处理一个 Query（一维向量，一个 Token），则时间复杂度为 \(\mathcal{O}(L \cdot d)\)
    • 存储瓶颈：KV Cache 随 \(L\) 线性增长

Linear Attention，线性复杂度的代价

  • 原始论文：Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, ICML 2020
  • Linear Attention 将 Softmax 替换为一个可分解的核函数 \(\phi(\cdot)\)，使得 \(\phi(\mathbf{q}_i)^\top\phi(\mathbf{k}_j)\) 近似 \(\exp(\mathbf{q}_i^\top\mathbf{k}_j)\)
  • 由此，Attention 可以改写为：
    $$\mathbf{O}_t = \frac{\phi(\mathbf{Q}_t)^\top\sum_{i=1}^t\phi(\mathbf{K}_i)\mathbf{V}_i^\top}{\phi(\mathbf{Q}_t)^\top\sum_{i=1}^t\phi(\mathbf{K}_i)}$$
    • 注：进针对 Q 和 K 做核函数变换（V 不做变换）的原因是这里的核函数是用于近似 Softmax 的
  • 利用矩阵乘法的结合律，可将计算复杂度从 \(\mathcal{O}(L^2)\) 降至 \(\mathcal{O}(L)\)
  • 从在线学习 的视角看，Linear Attention 维护一个矩阵值记忆状态 \(\mathbf{S}_t \in \mathbb{R}^{d_k\times d_v}\)，其更新规则为：
    $$
    \begin{align}
    \mathbf{S}_t &= \mathbf{S}_{t-1} + \mathbf{k}_t\mathbf{v}_t^\top \\
    \mathbf{o}_t &= \mathbf{S}_t^\top\mathbf{q}_t
    \end{align}
    $$
    • \(\mathbf{k}_t, \mathbf{q}_t \in \mathbb{R}^{d_k}\)
      • \(\mathbf{k}_t\mathbf{v}_t^\top\) 的本质是外积：
        $$ \mathbf{k}_t\mathbf{v}_t^\top = \mathbf{k}_t \otimes \mathbf{v}_t $$
      • 这里常用的是 \(\mathbf{o}_t = \mathbf{S}_t^\top\mathbf{q}_t\)，即使用的是转置 \(\mathbf{S}_t^\top\)，所以部分文章中会使用类似下面的写法（不用转置）：
        $$
        \begin{align}
        \mathbf{S}_t &= \mathbf{S}_{t-1} + \mathbf{v}_t \otimes \mathbf{k}_t \\
        \mathbf{o}_t &= \mathbf{S}_t \mathbf{q}_t
        \end{align}
        $$
    • \(\mathbf{v}_t, \mathbf{o}_t \in \mathbb{R}^{d_v}\)
  • 优点：
    • 计算复杂度下降至 \(\mathcal{O}(L \cdot d^2)\)
    • KV Cache 不需要缓存了
  • 核心局限 ：
    • Linear Attention 采用的 Hebbian 式加性更新（\(\mathbf{S}_t = \mathbf{S}_{t-1} + \mathbf{k}_t\mathbf{v}_t^\top\)）缺乏遗忘机制，导致记忆中旧信息不断累积、相互干扰
      • 直觉理解 ：
        • 快速权重 \(\mathbf{S}_t \in \mathbb{R}^{d \times d}\) 是一个有限秩的矩阵
          • 若要无干扰地检索记忆，存储的键向量 \(\phi(\mathbf{k}_t)\) 必须彼此正交
        • 在 \(d\) 维空间中，最多只能有 \(d\) 个正交向量
          • 因此，当序列长度 \(L > d\) 时，模型进入过容量（Overcapacity） 状态，检索时会出现串扰（Crosstalk）误差
    • 相互干扰会使得模型在精确复制和长程检索等任务上表现不佳

DeltaNet，引入误差修正的 Delta Rule

  • 原始论文：(FWP, DeltaNet, Delta Network)Linear Transformers Are Secretly Fast Weight Programmers, ICML 2021
  • 这篇论文提到：Linear Attention 本质上是一个 Fast Weight Programmer (FWP)
    • 一个“慢”神经网络通过梯度下降学习去编程另一个“快”网络的权重，这些权重通过 Key-Value 外积的加性更新来动态变化
    • 从 RNN 视角看，Linear Attention 是一个固定大小的状态（\(d_k \times d_v\)），与序列长度无关
  • DeltaNet 将记忆更新从加性 Hebbian 规则 改为 Delta Rule（增量规则）
    • DeltaNet 的核心思路是：不盲目累加所有 Key-Value 对，而是只存储当前 Key 与已有记忆之间的“误差”
  • DeltaNet 将状态更新重新解释为对重构损失的在线梯度下降：
    $$\mathcal{L}_t(\mathbf{S}) = \frac{1}{2}|\mathbf{S}^\top\mathbf{k}_t - \mathbf{v}_t|^2$$
  • 对 \(\mathbf{S}_{t-1}\) 取一个梯度步长（学习率 \(\beta_t\)），得到：
    $$\mathbf{S}_t = \mathbf{S}_{t-1} - \beta_t\nabla_{\mathbf{S} }\mathcal{L}_t(\mathbf{S}_{t-1}) = (\mathbf{I} - \beta_t\mathbf{k}_t\mathbf{k}_t^\top)\mathbf{S}_{t-1} + \beta_t\mathbf{k}_t\mathbf{v}_t^\top$$
  • DeltaNet 将记忆状态 \(\mathbf{S}\) 视为一个可学习的联想记忆 ，不断向映射 \(\mathbf{k}_t \mapsto \mathbf{v}_t\) 的方向自我修正
  • DeltaNet 更新由两部分组成：
    • 遗忘项
      $$ (\mathbf{I} - \beta_t\mathbf{k}_t\mathbf{k}_t^\top)\mathbf{S}_{t-1} $$
    • 新增项
      $$ \beta_t\mathbf{k}_t\mathbf{v}_t^\top$$
    • 这种秩-1 校正更新等价于广义 Householder 变换，支持硬件高效的 Chunkwise 并行化
  • 优点：
    • DeltaNet 比加性 Linear Attention 更稳定
  • 核心局限 ：
    • DeltaNet 缺乏遗忘机制 ，旧关联会无限期保留，导致记忆干扰

补充1：从 Linear Transformer 到 FWP 的简要理解

  • 在 Linear Transformer 的语境下，快速权重编程器（Fast Weight Programmers, FWP） 的架构能明确映射到具体的网络组件中
  • 注：这种技术可称为 Fast Weight Programming
FWP 的原本定义
  • FWP 最初被定义为一种由两个网络协同工作的架构
  • 慢网络（Slow Network） ：作为 “Programmers”，其权重在训练阶段通过梯度下降缓慢更新，训练完成后固定
    • 它负责制定“学习规则”或生成控制信号
  • 快网络（Fast Network） ：其权重（即快速权重, Fast Weights）会快速动态变化，充当网络的短期记忆存储器
    • 它在推理时（每个时间步）根据慢网络给出的规则进行快速更新，充当模型的短期记忆
Linear Transformer 中的 FWP 定义及快慢网络映射
  • 在 Linear Transformer 的语境下，FWP 被形式化为一种基于外积和加性更新的键-值（Key-Value）关联记忆模型，其快慢网络被明确定义如下：
  • 慢网络（SlowNet） ：
    • 对应于 Linear Transformer 中的前馈层（或线性投影层）
    • 它接收当前输入 \( X(t) \)，并通过固定的线性投影生成键向量 \( k(t) \) 和值向量 \( v(t) \)，即
      $$
      k(t) = W_k X(t), \quad v(t) = W_v X(t).
      $$
  • 快网络（FastNet） ：
    • 对应于动态的快速权重矩阵 \( W(t) \)
    • 它在每个时间步根据慢网络生成的 \( k(t) \) 和 \( v(t) \) 进行秩‑1 的外积叠加更新，即
      $$
      W(t) = W(t-1) + v(t) \otimes k(t).
      $$
对外积 \( (v(t) \otimes k(t)) q(t) \) 的含义理解
  • \( (v(t) \otimes k(t)) q(t) \) 代表了 FWP 机制中“读取记忆”的微观物理过程，即单步的内容检索操作，根据线性代数结合律，它可以被拆解为
    $$
    (v(t) \otimes k(t)) q(t) = v(t) \bigl(k(t)^T q(t)\bigr),
    $$
    • \( k(t)^T q(t) \)（内积）：计算当前查询向量 \( q(t) \) 与当前键向量 \( k(t) \) 的相似度分数（标量）
    • \( v(t) \cdot \text{标量} \)（标量乘法）：用上述相似度分数对当前的值向量 \( v(t) \) 进行加权提取
  • 总结 ：
    • \( (v(t) \otimes k(t)) q(t) \) 精确描述了模型在单个时间步内，如何利用刚刚写入记忆的键值对，对当前的查询 \( q(t) \) 做出响应
    • 它是整个长序列记忆检索过程中的一个“切片”，所有历史时间步的该操作叠加起来，就构成了完整的注意力聚合机制

补充2：从 Linear Transformer 到 FWP 的更多相关理解

  • 本节以因果自回归（Causal Autoregressive） 场景为例，这是 Linear Transformer 和 FWP 最契合的应用设定
推导设定
  • 在时刻 \( t \)，输入序列为 \(\{x(1), x(2), \dots, x(t)\}\)
  • 对每个输入 \( x(i) \)，通过慢网络（线性投影层）生成原始键 \( k(i) \)、值 \( v(i) \) 和查询 \( q(i) \)
  • 为了将点积相似度替换为可线性化的核函数，引入特征映射 \( \phi(\cdot) \)，使得核相似度定义为：
    $$
    \text{sim}(q, k) = \phi(q)^T \phi(k)
    $$
    • 注：在 Linear Transformer 原论文中，通常取 \( \phi(x) = \text{elu}(x) + 1 \)
第 1 步：外积更新规则的展开
  • 定义快速权重矩阵 \( W(t) \) 的初始状态为零矩阵：
    $$
    W(0) = \mathbf{0}.
    $$
  • 在每个时间步 \( t \)，慢网络生成当前的特征化键 \( \phi(k(t)) \) 和值 \( v(t) \)，快网络执行秩‑1 外积叠加更新 ：
    $$
    \begin{align}
    W(t) &= W(t-1) + v(t) \otimes \phi(k(t)) \\
    &= W(t-1) + v(t) \phi(k(t))^T
    \end{align}
    $$
    • 注意：\(v(t) \phi(k(t))^T\) 的本质是外积 \(v(t) \otimes \phi(k(t))\)
  • 将上式从 \( 1 \) 到 \( t \) 递归展开，得到累积的记忆矩阵：
    $$
    W(t) = \sum_{i=1}^{t} v(i) \phi(k(i))^T. \tag{1}
    $$
  • 这个矩阵显式地存储了所有历史时刻的“键特征 → 值”的关联
第 2 步：用快速权重读取记忆
  • 在时刻 \( t \)，当前查询经过同样的特征映射后为 \( \phi(q(t)) \)
  • 快网络通过矩阵乘法“读取”记忆，得到未归一化的输出向量：
    $$
    \tilde{o}(t) = W(t) \phi(q(t)).
    $$
  • 将 (1) 式代入，并利用矩阵乘法对加法的分配律：
    $$
    \begin{align}
    \tilde{o}(t) &= \left( \sum_{i=1}^{t} v(i) \phi(k(i))^T \right) \phi(q(t)) \\
    = \sum_{i=1}^{t} v(i) \left( \phi(k(i))^T \phi(q(t)) \right)
    \end{align}
    \tag{2}
    $$
  • 因为 \( \phi(k(i))^T \phi(q(t)) \) 是一个标量，所以上式右侧就是所有历史值向量 \( v(i) \) 按当前核相似度加权后的总和
第 3 步：引入归一化，得到标准线性注意力
  • 标准 Linear Transformer 为了替代 Softmax，会对上述加权和进行除以核相似度之和的归一化处理
  • 定义归一化标量：
    $$
    Z(t) = \sum_{i=1}^{t} \phi(k(i))^T \phi(q(t)).
    $$
  • 于是最终输出为：
    $$
    o(t) = \frac{\tilde{o}(t)}{Z(t)}
    = \frac{\sum_{i=1}^{t} v(i) \left( \phi(k(i))^T \phi(q(t)) \right)}{\sum_{i=1}^{t} \phi(k(i))^T \phi(q(t))}. \tag{3}
    $$
  • 由于标量转置不变，\( \phi(k(i))^T \phi(q(t)) = \phi(q(t))^T \phi(k(i)) \)，因此 (3) 式完全等价于 Linear Transformer 的因果注意力公式：
    $$
    o(t) = \frac{\sum_{i=1}^{t} \left( \phi(q(t))^T \phi(k(i)) \right) v(i)}{\sum_{i=1}^{t} \phi(q(t))^T \phi(k(i))}.
    $$
第 4 步：外积更新 → 线性注意力的等价性总结
  • 将第 2 步和第 3 步合并，作者可以把完整的因果线性注意力机制简洁地重写为两个递归累加器的形式 ：
  • 1）快速权重矩阵（记忆累加器），按外积更新：
    $$
    W(t) = W(t-1) + v(t) \otimes \phi(k(t)), \quad W(0) = \mathbf{0}.
    $$
  • 2）归一化标量（权重和累加器），按内积更新：
    $$
    Z(t) = Z(t-1) + \phi(k(t))^T \phi(q(t)), \quad Z(0) = 0.
    $$
  • 3）当前时刻的最终输出 ：
    $$
    o(t) = \frac{W(t) \phi(q(t))}{Z(t)}. \tag{4}
    $$
  • 公式 (4) 便是外积更新规则与线性注意力之间的直接数学等价桥梁
第 5 步：回看单步“切片” \( (v(t) \otimes k(t))q(t) \)
  • 在引入特征映射 \( \phi \) 后，单步写入-读取操作变为：
    $$
    \bigl(v(t) \otimes \phi(k(t))\bigr) \phi(q(t))
    = v(t) \left( \phi(k(t))^T \phi(q(t)) \right).
    $$
  • 这正是第 \( t \) 个时间步对未归一化总输出 \( \tilde{o}(t) \) 的增量贡献
  • 将所有时间步的该增量累加，并除以累加的归一化标量 \( Z(t) \)，即得到完整的线性注意力聚合结果
计算复杂度评估
  • 传统点积注意力在时刻 \( t \) 的计算复杂度为 \( O(t \cdot d) \)（\( d \) 为特征维度），因为需要逐一计算当前查询与所有历史键的点积
  • 在上述 FWP 等价框架中，更新 \( W(t) \) 和 \( Z(t) \) 仅需常数时间 \( O(d) \)，读取输出也仅需一次矩阵乘向量 \( O(d^2) \)（若采用对角/低秩特征映射可进一步优化）
    • 因此，整个序列的推理复杂度从 \( O(T^2 d) \) 降至 \( O(T d^2) \) ，这正是 Linear Transformer 获得线性复杂度的核心原因，而其背后的记忆更新机制，正是由 FWP 的外积规则精确描述的

Gated DeltaNet (GDN)，引入标量遗忘门

  • 原始论文：(Gated DeltaNet)Gated Delta Networks: Improving Mamba2 with Delta Rule, ICLR 2025, NVIDIA
  • GDN 在 DeltaNet 的基础上引入一个标量遗忘门 \(\alpha_t \in [0,1]\)：
    $$
    \begin{align}
    \mathbf{S}_t &= \alpha_t(\mathbf{I} - \beta_t\mathbf{k}_t\mathbf{k}_t^\top)\mathbf{S}_{t-1} + \beta_t\mathbf{k}_t\mathbf{v}_t^\top\\
    \mathbf{o}_t &= \mathbf{S}_t^\top\mathbf{q}_t
    \end{align}
    $$
  • Gating 机制使模型能够快速擦除记忆 ，而 Delta Rule 则实现精准的定向更新 ，两者具有天然的互补性
    • \(\alpha_t\) 充当权重衰减的角色，实现了类似数据依赖的 \(L_2\) 正则化，为记忆生命周期提供了可控的遗忘机制
  • GDN 统一了 Mamba2 的自适应衰减与 DeltaNet 的定向记忆更新
  • 核心局限 ：
    • GDN 的遗忘门 \(\alpha_t\) 是逐头（per-head）的标量 ，缺乏特征维度的多样性
      • 相比之下，RoPE 通过为每个维度对分配不同的旋转频率，实现了精细的位置编码
    • GDN 的这种粗粒度衰减限制了其表达能力和位置感知能力

Kimi Delta Attention (KDA) ，细粒度通道级门控

  • 原始论文：(KDA)Kimi Linear: An Expressive, Efficient Attention Architecture, 20251030, Kimi
    • 注：KDA 是首次在公平对比下 全面超越 Full Attention 的线性注意力架构
  • KDA 将 GDN 的标量遗忘门 \(\alpha_t\) 升级为对角矩阵 \(\text{Diag}(\alpha_t) \in \mathbb{R}^{d_k\times d_k}\)，实现逐通道（channel-wise）的细粒度门控 ：
    $$
    \begin{align}
    \mathbf{S}_t &= (\mathbf{I} - \beta_t\mathbf{k}_t\mathbf{k}_t^\top)\text{Diag}(\alpha_t)\mathbf{S}_{t-1} + \beta_t\mathbf{k}_t\mathbf{v}_t^\top,\\
    \mathbf{o}_t &= \mathbf{S}_t^\top\mathbf{q}_t
    \end{align}
    $$
    • \(\alpha_t \in [0,1]^{d_k}\) 是每个特征维度独立的遗忘率
    • \(\beta_t \in [0,1]\) 是学习率
  • KDA 设计原理：
    • 1）细粒度记忆控制 ：每个特征维度拥有独立的遗忘率，使模型能够选择性地遗忘无关信息，同时更精确地保留关键记忆。这在 Palindrome 和 MQAR 等合成任务上体现为更快的收敛速度和更高的准确率
    • 2）DPLR 约束与硬件效率 ：KDA 将状态转移矩阵约束为 Diagonal-Plus-Low-Rank (DPLR) 的特殊形式：
      $$\mathbf{S}_t = (\text{Diag}(\alpha_t) - \beta_t\mathbf{k}_t\mathbf{k}_t^\top\text{Diag}(\alpha_t))\mathbf{S}_{t-1} + \beta_t\mathbf{k}_t\mathbf{v}_t^\top$$
      • 通过将 \(\mathbf{a}\) 和 \(\mathbf{b}\) 都绑定到 \(\mathbf{k}\)，KDA 将 Chunkwise 计算中的次级矩阵运算从四个减少到两个，并消除了三个额外的矩阵乘法，算子效率相比通用 DPLR 提升约 100%
    • 3）作为可学习位置编码 ：KDA 的递推形式可展开为：
      $$\mathbf{o}_t = \sum_{i=1}^t\left(\mathbf{q}_t^\top\left(\prod_{j=i+1}^t\mathbf{A}_j(\mathbf{I} - \beta_j\mathbf{k}_j\mathbf{k}_j^\top)\right)\mathbf{k}_i\right)\mathbf{v}_i$$
      • 其中 \(\mathbf{A}_j = \text{Diag}(\alpha_j)\)。这等价于一种数据依赖的乘法位置编码 ，其转移矩阵是可学习的，打破了 RoPE 的正交性约束 ，可能具有更强的表达能力
    • 4）混合架构 ：Kimi Linear 采用 3:1 的 KDA 与 Full Attention 层交替的混合设计，每 3 层 KDA 后接 1 层全局 Full MLA 层。这种设计既保留了 Full Attention 的全局信息流能力，又将 KV Cache 使用量减少高达 75% ，在 1M 上下文长度下实现 6× 的 Decoding 吞吐量提升

整体总结（截止到 KDA 的总结）

  • 线性注意力演进路径的本质是：
    • 在保持线性复杂度的前提下，逐步提升记忆管理的精细度和灵活性
  • 线性 Attention 的演进：
    方法 核心更新规则 关键创新 核心局限
    Softmax Attention \(\text{softmax}(\mathbf{Q}\mathbf{K}^\top)\mathbf{V}\) 精确的内容寻址 \(\mathcal{O}(L^2)\) 复杂度，KV Cache 线性增长
    Linear Attention \(\mathbf{S}_t=\mathbf{S}_{t-1}+\mathbf{k}_t\mathbf{v}_t^\top\) 复杂度降至 \(\mathcal{O}(L)\)，固定大小状态 无遗忘机制，Hebbian 加性更新
    DeltaNet \(\mathbf{S}_t=(\mathbf{I}-\beta\mathbf{k}_t\mathbf{k}_t^\top)\mathbf{S}_{t-1}+\beta\mathbf{k}_t\mathbf{v}_t^\top\) Delta Rule 误差修正 仍无遗忘机制
    Gated DeltaNet \(\mathbf{S}_t=\alpha_t(\mathbf{I}-\beta\mathbf{k}_t\mathbf{k}_t^\top)\mathbf{S}_{t-1}+\beta\mathbf{k}_t\mathbf{v}_t^\top\) 标量遗忘门 粗粒度（逐头），缺乏特征多样性
    KDA \(\mathbf{S}_t=(\mathbf{I}-\beta\mathbf{k}_t\mathbf{k}_t^\top)\text{Diag}(\alpha_t)\mathbf{S}_{t-1}+\beta\mathbf{k}_t\mathbf{v}_t^\top\) 逐通道细粒度门控 + DPLR 硬件优化 —