【Transformer 与注意力机制】43｜稀疏与局部注意力：Longformer、BigBird、Sparse Transformer

42｜FlashAttention 讲清楚了一件事：FlashAttention 不改 attention 的语义，它优化的是标准 attention 这张完全图在 GPU 内存层级里的搬运路径——FLOP 仍是 \(\Theta(N^2 d)\)，变的是数据从 HBM 到 SRAM 的调度。稀疏 attention 问的是另一个问题：这张完全图本身要不要存在？如果大多数 token 对之间的注意力权重贡献很小，能不能在设计阶段就把这些边删掉，把 \(O(n^2)\) 条边降到 \(O(n)\) 或 \(O(n\sqrt n)\)？

这不是选择题。42 篇末尾已经把”要不要继续稀疏化”的争论摆出来了：exact 路径把 HBM 流量压到 \(\Theta(N)\) 之后，多数预训练默认继续用 full attention 换 kernel；但 \(O(N^2)\) 的 token 对关系没有消失，极长上下文、算力紧张的场景里，改连接图仍是有文献支撑的路线。本篇不重复这个立场判断，而是把”怎么设计连接图”这件事钉死：Longformer、BigBird、Sparse Transformer 各自基于什么图论直觉选边，这些 pattern 在真实 GPU 上要付出什么工程代价，以及为什么这条路线至今没有吃掉 full attention 的份额。

本篇能让你学会四件事：

1. 用一张邻接矩阵统一理解三种 pattern 的选边逻辑，而不是记住”local/global/random”三个词；
2. Longformer 为什么要自己写一整套 CUDA kernel，BigBird 为什么把随机边做成 block 级别；
3. 不规则 mask、变长序列、批处理三件事为什么让稀疏 attention 在生产里比论文里难落地；
4. 固定 pattern 的归纳偏置和学习型 sparsity（Reformer、Routing Transformer、NSA）之间，目前争论卡在哪。

一、把稀疏定义钉死成一张邻接矩阵

BigBird 论文给出的形式化很有用（Zaheer et al., NeurIPS 2020，§2）：把 attention 看成一张有向图 \(D\)，顶点集是 \(n\) 个 token，\(D\) 的邻接矩阵 \(A \in \{0,1\}^{n\times n}\)，\(A(i,j)=1\) 表示 query \(i\) 会看 key \(j\)。当 \(A\) 是全 1 矩阵时，就是标准 self-attention——\(D\) 是完全图。稀疏 attention 的设计问题，等价于图稀疏化（graph sparsification）问题：在保留多少条边、边怎么摆之间做选择。

这个视角把三个看似不同的方案统一到同一个坐标系里：

• 删去多少边决定了复杂度能降到 \(O(n\sqrt n)\)（Sparse Transformer）还是 \(O(n)\)（Longformer、BigBird）；
• 怎么摆边决定了图的连通性——任意两个 token 之间的最短路径长度（graph diameter），这直接对应”信息能不能跨窗口传播”；
• 谁来决定连边决定了这是一个固定的架构先验（本篇三种方法），还是一个训练/推理时才确定的路由（八节要谈的学习型 sparsity）。

full attention 的直径是 1：任意两点一步可达。稀疏 attention 的核心矛盾是：边数降到 \(o(n^2)\) 之后，图的直径几乎不可能仍然是 1，除非某些节点度数很高（充当中转站）。三家方案对这个矛盾给出了三种几何方案。

二、Sparse Transformer：结构化稀疏与两步可达

Sparse Transformer（Child, Gray, Radford, Sutskever, arXiv:1904.10509, 2019，未经 peer review）最早把 attention 矩阵做因子分解（factorization）：不是随便删边，而是把全连接拆成 \(p\) 个稀疏的子 attention，组合起来复杂度是 \(O(n \cdot n^{1/p})\)；论文主要用 \(p=2\)，即 \(O(n\sqrt n)\)。

论文给了两种具体的分解模式：

• Strided attention：一个 head 只看前面 \(l\) 个位置（局部），另一个 head 只看每隔 \(l\) 个位置的 token（\(A_i^{(2)} = \{j : (i-j) \bmod l = 0\}\)），\(l\) 取接近 \(\sqrt n\)。这等价于把序列摆成二维网格后，分别沿行和列做 attention——对有网格结构的数据（图像、部分音乐）很自然，因为空间相邻性本身就有意义。
• Fixed attention：把序列切成长度 \(l\) 的块，每块最后 \(c\) 个位置充当”摘要 cell”，未来所有块都可以看这些摘要位置（\(A_i^{(1)} = \{j : \lfloor j/l \rfloor = \lfloor i/l \rfloor\}\)，\(A_i^{(2)}\) 是每块的固定摘要区间）。论文明确说明原因：文本没有周期结构，token 的空间坐标和它未来被需要的位置没有必然关系，strided pattern 在文本上会”路由失败”，所以要退化成”少数固定位置汇聚信息”的方案。

关键的图论结论是：把两种 head 的连接图叠加，任意两个位置之间只需要经过 2 跳就能连通——这不是巧合，是因子分解的设计目标（论文称之为”在常数步内到达任意输出位置”）。这和 BigBird 后面用随机图论证连通性是同一个问题的两种答案：Sparse Transformer 用确定性的结构保证 2 跳可达，BigBird 用随机边把期望路径长度压到 \(O(\log n)\)。

还有一处值得单独记一笔：Sparse Transformer 论文的贡献列表里明确写了”attention 矩阵的重计算（recomputation）以节省显存”和”训练用的快速 attention kernel”。这正是三年后 FlashAttention 用”算力换 HBM 流量”这套思路的前身——只是 2019 年这套重计算是为了给稀疏 pattern 省显存，2022 年 Dao et al. 把同一个想法用在了 exact full attention 的 backward 上（见 42｜FlashAttention 第六节）。两条路线在”用重算换显存”这一点上是同源的，只是重算的对象不同。

三、Longformer：local + global，以及为什么必须自己写 kernel

Longformer（Beltagy, Peters, Cohan，arXiv:2004.05150，2020，未经 peer review）把邻接矩阵设计成两部分：固定宽度 \(w\) 的滑动窗口（每个 token 只看左右各 \(w/2\) 个位置），加上少量被指定为 global 的 token（这些 token 看所有位置，也被所有位置看到）。

滑动窗口解决的是复杂度，但它单独存在时的图直径很差——两个相距 \(D\) 的 token 之间的最短路径是 \(D/w\) 跳。Longformer 用堆叠层数弥补：论文明确给出感受野公式，\(\ell\) 层、窗口 \(w\) 的堆叠后，顶层的感受野是 \(\ell \times w\)；如果对部分 head 加膨胀（dilation，间隔 \(d\) 取样），感受野变成 \(\ell \times d \times w\)，可以在不增加计算量的前提下把有效跨度做到几万 token。这个思路和 CNN 用堆叠卷积层扩大感受野完全一致——局部窗口本身不解决远距离依赖，是多层叠加把窗口变成了感受野。

global token 才是真正解决”图直径”问题的机制：把它们设为度数为 \(n\) 的枢纽节点，任意两个普通 token 之间就有了一条经过某个 global token 的 2 跳路径，不用等到顶层才连通。这和 Sparse Transformer 的”摘要 cell”是同一个招——少数高连接度节点承担长距离信息中转，区别只是 Longformer 让任务决定哪些位置是枢纽（[CLS]、问题 token），Sparse Transformer 让固定的块边界位置充当枢纽。

Longformer 论文里还有一个真正决定它能不能落地的细节，很多复述文章会跳过：滑动窗口 attention 在当时的 PyTorch/TensorFlow 里没有原生支持，因为它本质是一种带状矩阵乘法（banded matrix multiplication），标准 dense matmul 不知道怎么只算非零对角线。论文对比了三种实现：

cuda 版本不是调用现成算子拼出来的，是作者用 TVM（一个深度学习编译器栈）从头描述带状矩阵乘法的计算模式，再由 TVM 生成并编译成 GPU device code。也就是说，Longformer 的复杂度优势要落到真实吞吐上，代价是从头写一个专用编译产物，而不是像 FlashAttention 那样提供一个可以无脑替换的 kernel。这也是它后来在实际训练中，autoregressive LM 场景要用分阶段训练（5 个阶段，序列长度从 2,048 逐步翻倍到 23,040，窗口从底层 32 到顶层 8,192 同步增长）的原因之一：kernel 和训练策略要一起为这个特定 pattern 定制，不是配置文件里改一个数字就完事。

四、BigBird：随机连接、两个理论结果与一条硬件让步

BigBird（Zaheer et al., NeurIPS 2020）在 local + global 之外加了随机边：每个 query 额外看 \(r\) 个随机选中的 key。论文给出的动机不是”随便加点噪声提高鲁棒性”，而是两条具体的图论依据（§2）：

• Erdős–Rényi 随机图：只要有 \(\tilde\Theta(n)\) 条边，随机图中任意两点的最短路径就是 \(O(\log n)\) 级别，图的谱性质也逼近完全图（第二特征值远离第一特征值，意味着随机游走混合得快，信息能快速在任意两点间流动）。这是”加随机边”能替代”全连接”的理论依据。
• Watts–Strogatz 小世界模型：纯随机图连通性好，但聚类系数（衡量局部性的指标）低，不符合语言/生物序列里”邻近 token 强相关”的先验。小世界模型的做法是从规则环形网格（对应滑动窗口）出发，再把其中一部分边替换成随机边，兼顾局部聚类和全局连通。

这里有一处论文明确写出来的工程让步：按 Watts–Strogatz 的原始构造，随机化应该是”删掉一部分局部边，换成随机边”；但论文原文写道，删边这种操作在现代硬件上效率不高（inefficient on modern hardware），所以 BigBird 选择保留全部局部窗口边，随机边是纯叠加上去的，不做删除替换。这不影响理论性质，却直接是”图论上更优雅的方案”向”GPU 上好实现的方案”让步的例子——random attention 因此被现成的三个 building block（random / window / global）并列组合，而不是按小世界模型精确复刻的”重连”过程。

BigBird 的理论部分给了两个结果，一正一反：

正的一面：BigBird 是序列到序列函数的通用近似器（universal approximator），并且在标准精度假设下是 Turing complete——这两条本来是 Yun et al.（2020）和 Pérez et al.（2019）对full attention证明的性质，BigBird 论文证明稀疏版本同样满足，前提是保留了 \(O(1)\) 个 global token。证明思路是：随机连接可以模拟一个星图（star graph，一个中心节点连所有其他节点），星图又可以模拟 full attention 的信息传播——这也是为什么”加 \(O(1)\) 个全局 token”在论文的理论分析里比”多加多少随机边”更关键。

反的一面（论文 §3.4 “Limitations”）：作者构造了一个具体任务——给定 \(n\) 个单位向量，找出每个向量对应的最远向量（“finding the corresponding furthest vector”）。这个任务用 full attention 只需要 \(O(1)\) 层就能解（算出所有两两内积即可）；但论文证明，任何边数为 \(\tilde O(n)\) 的稀疏 attention 图（不只是 BigBird），要解这个任务都需要 \(\tilde\Omega(n^{1-o(1)})\) 层。证明依据是细粒度复杂度理论里的正交向量猜想（Orthogonal Vector Conjecture，一个被广泛使用、尚未被证明也未被推翻的假设）：如果稀疏 attention 能在少层内解决这个任务，就能在亚二次时间内解正交向量问题，而 OVC 断言这是不可能的。

这个结果比”稀疏可能损失精度”这种模糊说法精确得多：它说明存在具体、可构造的任务，任何固定边数的稀疏图都在深度上比 full attention 吃亏，而且这个下界不是 BigBird 设计得不好，是任何 \(\tilde O(n)\) 边的方案都逃不掉的复杂度代价。三种方案的选边逻辑放在一起看：

五、生产现场：不规则 mask、变长序列、batch 为什么难喂 GPU

论文里的复杂度分析假设的是”理想执行”：边少了，计算就该少。真实 GPU 更喜欢规则、密集、能对齐 Tensor Core tile 大小的矩阵运算，稀疏 pattern 想要把理论收益变成实际吞吐，要越过三道坎。

不规则 mask。 Longformer 的三种实现（loop/chunks/cuda）本质是在”内存效率”和”能否用现成矩阵乘法”之间反复取舍：chunks 靠一次 PyTorch matmul 就能跑，代价是重叠分块导致算了 2 倍不必要的零值；真正省内存又快的 cuda 版本必须自己描述带状矩阵乘法、自己生成 CUDA 代码。BigBird 走的是另一条路：把随机连接的粒度定在 block 级别而不是 token 级别（论文原文强调其内存效率来自”高效的 blocking 与稀疏结构”），这样随机采样出来的是几个完整的 block，可以用类似分块 GEMM 的方式批量搬运，而不是对每个 token 单独发起一次不规则 gather。这条设计选择直接继承自更早的 GPU block-sparse kernel 工程（Gray, Radford & Kingma, “GPU Kernels for Block-Sparse Weights”, OpenAI, 2017）——不规则的 per-token 稀疏几乎注定拖垮 GPU，block 级别的稀疏才勉强够格接近 dense kernel 的效率。

变长序列。 一套针对固定窗口宽度 \(w\)、固定 block size、固定随机 block 数 \(r\) 编译出来的 kernel，天然假设这些超参数在一次调用里是常量。真实请求的长度千差万别，工程上要么把整批 padding 到公共长度（浪费掉 pad 位置本该省下的计算，还要小心 global token 的下标不能被 padding 打乱），要么为不同长度维护多套 kernel 变体。这和 FlashAttention 系列原生支持的 varlen/cu_seqlens 接口（一个 kernel 用累积长度数组处理任意变长 batch，见 长上下文工程 第五节 sample packing 的讨论）形成直接对比：exact kernel 不改变连接图，长度只影响 tile 循环的次数；固定 pattern 的 kernel 连接图本身依赖窗口/block 配置，配置一变，能否复用同一份编译产物就要打问号。

batch 内的不均匀。 BigBird 的随机 block 是按位置随机采样的，同一 batch 里不同样本抽到的随机 block 通常不同，没法用一次统一的切片操作取出来，需要额外的 index 张量做 gather/scatter。微软 MInference（Jiang et al., NeurIPS 2024 Spotlight）在推理阶段走的是另一条务实路线：先离线判断每个 attention head 属于三种规则稀疏形状之一——A-shape（关注开头若干 token，类似 attention sink）、Vertical-Slash（若干固定列 + 对角线附近）、Block-Sparse（block 级别选择）——再对每种形状分别写优化过的 GPU kernel，运行时只需要按 head 归类、动态定位索引，而不是让每个 token 各自决定看哪里。这个设计的取舍很直白：宁可放弃”完全按内容自由选择连接”的灵活度，把可能的连接形状收窄到少数几种规则模式，用规则换回可以被 GPU 结构化执行的 sparse GEMM。稀疏 attention 的工程史基本都在重复这一条：能不能落地，往往取决于选边规则是否恰好还是”规则”的。

六、为什么稀疏没有全面取代 full attention

三个原因叠在一起，而不是单一瓶颈：

kernel 生态不对等。 FlashAttention / FA2 / FA3 是一个通用、exact、可作为 drop-in 替换的 kernel，已经内置进 PyTorch SDPA、Hugging Face、vLLM 等几乎所有主流栈——因为它不改变语义，框架只需要换一次算子实现。稀疏 pattern 没有这种”一个 kernel 打天下”的待遇：Longformer 需要自建 TVM 编译产物，BigBird 需要 block 级别的稀疏 GEMM，NSA 需要专门的 Triton kernel（Yuan et al., ACL 2025 最佳论文）分别处理压缩、选择、滑窗三个分支。每换一种 pattern，几乎等于重新做一次 kernel 工程，而不是调一个开关。

训练配方是路径依赖的。 大规模预训练团队已经在 full attention + FlashAttention 这条组合上验证过 scaling 行为、超参数、数据配比；换成一种新的稀疏 pattern，等于同时改变模型的归纳偏置和可训练性假设，需要重新验证整套 scaling law 是否还成立。NSA 论文特意强调自己是”natively trainable”——用可微分算子把压缩/选择/滑窗三个分支端到端接入训练，而不是像很多早期稀疏方案那样只能在训练后打补丁——这个强调本身说明了行业默认预期：post-hoc 稀疏化通常要以精度换速度，只有从预训练第一步就原生引入稀疏，才有机会不掉点。多数团队没有动机为一个尚未验证过 scaling 行为的架构决策承担这个风险。

任务敏感性无法提前判断。 BigBird 的 \(\tilde\Omega(n^{1-o(1)})\) 层下界证明的是”存在”这样的任务，不是”所有”任务都吃亏——但反过来，一个团队在训练前几乎没有办法判断自己的下游任务是不是恰好落在这类”稀疏必吃亏”的复杂度类里。等到线上发现某类长距离推理效果变差，再去追溯是不是 attention pattern 的问题，排查成本远高于一开始就用 full attention 打底。

这三条共同的结果是：稀疏 attention 的价值集中在”上下文已经长到 exact 路径连 IO 优化都扛不住”的场景，而不是全面替代方案。

七、与 Ring Attention、分块长上下文的边界

容易混淆的另一对概念是稀疏 attention 和 Ring Attention / chunked prefill。二者回答的是完全不同的问题：

• 稀疏 attention 回答”要不要保留这条边”——它改的是邻接矩阵 \(A\) 本身，边数从 \(O(n^2)\) 降下来。
• Ring Attention（Liu et al., UC Berkeley, 2023）和 context parallel、chunked prefill 回答”同一张完全图，怎么在算力/显存装不下的情况下算出来”——它们不删任何边，只是把 \(Q,K,V\) 按序列维切到多张卡或多个 chunk 上，靠环形通信或分批处理把 exact full attention 的计算过程重新排布。见 长上下文工程 第六节对 Ring Attention 环形传递 \(K,V\) 步骤的展开，以及第七节 chunked prefill 的调度方式——这些机制的正确性完全建立在”结果必须和单卡跑出的 full attention 一致”上，属于分布式执行策略，不属于架构改动。

这两条轴是正交的，生产系统经常同时用：Qwen2.5-Turbo-1M 用 YaRN 做位置编码外推，同时混合稀疏 + 滑动窗口 + 全局 attention 层；DeepSeek 的 NSA 是训练原生稀疏，落地时仍要配合分布式执行策略处理超长序列的显存分布（细节见 16-long-context 第四、六节，本篇不重复其分布式实现）。判断一个长上下文方案在做什么，先问它改没改邻接矩阵——这是本篇和 Ring Attention 之间最清楚的分界线。

八、争论与开放问题：固定 pattern 的归纳偏置 vs 学习 sparsity

争论：连接图应该由设计者的先验决定，还是由数据/训练决定？

Longformer、BigBird、Sparse Transformer 的共同点是：连接规则在架构设计阶段就写死了——局部窗口宽度、哪些位置是 global、随机采样的边数，都是超参数，训练过程不会改变”哪类边存在”这个宏观结构（BigBird 的随机边逐步/逐 step 重新采样，但”存在 \(r\) 条随机边”这个规则本身不变）。这是一种归纳偏置：假设”局部性 + 少量全局锚点 + 随机桥接”这套几何结构，对大多数任务都是足够的连接方式。BigBird 的通用近似/Turing 完备定理是这一派最强的理论支撑——只要有 \(O(1)\) 个全局 token，稀疏图理论上不比 full attention 弱。

另一派的方案让”连哪些边”部分或完全由内容决定：

• Reformer（Kitaev, Kaiser, Levskaya, ICLR 2020）用局部敏感哈希（LSH）把 query 和 key 按相似度分桶，只在同桶内做 attention，复杂度 \(O(n\log n)\)；
• Routing Transformer（Roy, Saffar, Vaswani, Grangier, TACL 2021）用在线球面 k-means 把 query/key 聚类，同一簇内才计算注意力，复杂度 \(O(n^{1.5}d)\)；
• NSA（Yuan et al., ACL 2025 最佳论文）把压缩、选择、滑窗三个分支都设计成可微分算子，训练时端到端学会该压缩哪些块、选哪些块，是”选边规则”本身参与梯度更新的方案；
• MInference（Jiang et al., NeurIPS 2024 Spotlight）在推理时按每个 attention head 的实际得分分布动态判断稀疏索引，选边过程完全在运行时发生。

这一派的证据是：BigBird 自己证明的 \(\tilde\Omega(n^{1-o(1)})\) 层下界，恰好说明了”设计者固定选边规则”必然把某一类真实存在的关系设为结构性不可达——如果任务需要的关系恰好落在被设计者砍掉的边上，加多少层都补不回来（这是复杂度下界，不是优化问题）。让选择过程依赖内容，理论上更贴近任务真正需要的连接，代价是选择本身变成了新的计算与工程负担：k-means 簇分配、LSH 分桶、NSA 的路由与打分都需要额外训练稳定性保证，而 MInference 式的运行时近似则要接受”离线判断的 pattern 类别不一定适配每个具体输入”的近似误差。

共识边界：没有证据表明固定 pattern 或学习型 sparsity 哪一派已经”赢了”。BigBird 的理论结果证明的是存在性（某些任务稀疏必吃亏），不是普遍性（所有任务都吃亏）；NSA 证明的是”在特定 27B 参数、260B token 的预训练配置下不掉点”，不是”任意规模下学习型稀疏都优于固定 pattern”。

开放问题（可检验，非展望式）：

1. 通用 kernel 能否消解 pattern 切换成本？ FlexAttention 之类的方案让研究者用 Python 描述任意 score_mod/mask，交给编译器生成 Triton kernel（见 长上下文工程 第四节代码示例）。这能否把”设计一种新 pattern”的工程成本降到接近”换一个 kernel”的量级，还是固定、规则的 pattern（block-sparse、sliding window）永远比运行时动态确定的 pattern 更容易吃满 Tensor Core？目前没有系统性的跨 pattern 基准回答这个问题。
2. BigBird 的下界具体覆盖哪些真实任务？ “找最远向量”是一个构造性任务，用于证明下界存在。哪些真实的长文档 QA、代码理解、多跳推理子任务落在这类”任何 \(\tilde O(n)\) 边稀疏图都要付出 \(\tilde\Omega(n^{1-o(1)})\) 层代价”的复杂度类里，目前没有公开的系统刻画，这也是为什么”任务敏感性无法提前判断”（六节）会成为工程团队回避稀疏化的理由之一。
3. 学习型 sparsity 的训练稳定性能否独立复现？ NSA 的结果目前来自单篇论文、单一规模配置；k-means 式路由（Routing Transformer）和可微分路由（NSA）是否会在更大规模、不同数据分布下遇到类似 MoE 的负载不均问题（路由塌缩、部分簇/专家过载），还缺乏独立团队在不同规模上的复现证据。MoE 恰好也要面对”路由决定走哪条路径”的同类问题，下一篇会展开。

九、关键概念回顾

• 邻接矩阵 \(A\)：把 attention 形式化为有向图，\(A(i,j)=1\) 表示 query \(i\) 看 key \(j\)；full attention 对应完全图，稀疏 attention 对应图稀疏化后的子图。
• 图直径 / 连通性：任意两个 token 之间的最短路径长度。稀疏化的核心矛盾是边数下降后直径必然变大，除非引入高连接度的枢纽节点（global token、摘要 cell）。
• 结构化稀疏（Sparse Transformer）：确定性因子分解（strided/fixed pattern），用固定规则保证少数步内可达。
• local + global（Longformer）：滑动窗口负责局部，少量全局 token 负责跨窗口中转，堆叠层数扩大感受野。
• local + global + random（BigBird）：叠加随机边，借随机图/小世界图的连通性结论，把稀疏图的表达力理论上拉平到 full attention。
• OVC 下界：BigBird 证明的复杂度分离结果——存在任务，任何 \(\tilde O(n)\) 边的稀疏 attention 都需要比 full attention 多得多的层数才能解决。
• 学习型 sparsity：LSH 分桶（Reformer）、内容聚类路由（Routing Transformer）、端到端可微分路由（NSA）、运行时动态检测（MInference）——选边规则部分或完全由数据/训练决定，而非架构先验。

十、常见误解

10.1 “稀疏 attention 一定更快”

理论边数减少不等于实际吞吐提升。不规则 mask、变长 batch、per-token gather 都可能让稀疏 kernel 的实际执行效率远低于理论复杂度暗示的水平——这正是 Longformer 需要自建 TVM kernel、MInference 要把 pattern 收窄成三种规则形状的原因。

10.2 “稀疏 attention 一定损失表达能力”

不一定。BigBird 证明了只要有 \(O(1)\) 个 global token，稀疏图理论上可以是通用近似器、Turing complete，和 full attention 的理论性质一样强。但这不等于”任意任务都不吃亏”——BigBird 自己也证明了存在需要 \(\tilde\Omega(n^{1-o(1)})\) 层才能补回来的具体任务。

10.3 “FlashAttention 和稀疏 attention 是同一种东西”

不是。FlashAttention 是 exact full attention 的 IO 优化，不改变邻接矩阵；稀疏 attention 直接改写邻接矩阵本身。二者可以叠加使用（稀疏 pattern 的每个子计算仍可以用 IO-aware kernel 实现），不是互相替代关系。

10.4 “Ring Attention 是一种稀疏 attention”

不是。Ring Attention 和 chunked prefill 是 exact full attention 的分布式/分批执行策略，不删除任何边，只是把同一张完全图的计算拆到多卡或多个 chunk 上。它和稀疏 attention 是两条正交的轴，解决的是”装不下”而不是”要不要全连接”。

10.5 “学习型 sparsity 天然比固定 pattern 更好”

没有证据支持这个强结论。学习型方案（k-means 路由、可微分选择）理论上更贴近任务真实需要的连接，但引入了新的训练稳定性问题（路由塌缩、簇不均衡），且大规模复现证据仍然有限；固定 pattern 用规则性换来了更简单、更可预测的 kernel 行为。两者目前是权衡关系，不是替代关系。

十一、下一步

稀疏 attention 省的是 token 之间的连接边，同一层里每个 token 依然要经过同样一套参数。下一篇看另一种稀疏：模型的参数量可以很大，但每个 token 只激活其中一小部分——这就是 MoE，它把”稀疏”从 attention 的连接图搬到了 FFN 的参数路径上，而且它同样要面对路由决定”走哪条路”的负载均衡问题，这正是学习型 sparsity 在八节留下的开放问题的另一个变种。详见 44｜MoE。

十二、参考文献

核心论文

1. Child, R., Gray, S., Radford, A., Sutskever, I. “Generating Long Sequences with Sparse Transformers.” arXiv:1904.10509, 2019. 未经 peer review；结构化因子分解（strided/fixed pattern）与 \(O(n\sqrt n)\) 复杂度原始来源。
2. Beltagy, I., Peters, M. E., Cohan, A. “Longformer: The Long-Document Transformer.” arXiv:2004.05150, 2020. 未经 peer review；local + global pattern 与自定义 TVM CUDA kernel 实现细节（§3）。
3. Zaheer, M. et al. “Big Bird: Transformers for Longer Sequences.” NeurIPS 2020. 随机图连通性论证、通用近似/Turing 完备定理（§3）与 OVC 复杂度下界（§3.4）。
4. Kitaev, N., Kaiser, Ł., Levskaya, A. “Reformer: The Efficient Transformer.” ICLR 2020. LSH 分桶，学习型稀疏的早期代表，复杂度 \(O(n\log n)\)。
5. Roy, A., Saffar, M., Vaswani, A., Grangier, D. “Efficient Content-Based Sparse Attention with Routing Transformers.” TACL, Vol. 9, 2021. 在线 k-means 路由，复杂度 \(O(n^{1.5}d)\)。
6. Yuan, J. et al. “Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention.” ACL 2025（最佳论文）. 端到端可微分的压缩/选择/滑窗三分支稀疏。
7. Jiang, H. et al. “MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention.” NeurIPS 2024（Spotlight）. 推理时把动态稀疏收窄为三种规则模式的工程方案。

规范与对照

8. Dao, T. et al. “FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness.” NeurIPS 2022. exact IO-aware 路径的对照基准，见 42｜FlashAttention。
9. Liu, H. et al. “Ring Attention with Blockwise Transformers for Near-Infinite Context.” UC Berkeley, 2023. exact attention 的分布式执行策略，与稀疏 attention 的边界对照，见 长上下文工程 第六节。
10. Gray, S., Radford, A., Kingma, D. P. “GPU Kernels for Block-Sparse Weights.” OpenAI, 2017. block 级稀疏 GPU kernel 的早期工程来源，BigBird 的 blocking 设计承此思路。

← 上一篇：42｜FlashAttention　|　下一篇：44｜MoE →