滑动窗口解决了一类稀疏模式，但自然引出一个更一般的问题：注意力矩阵的稀疏模式本身该如何设计？稀疏化不是免费的午餐——mask 掉的位置直接拿不到信息，梯度也不流经那里（掩码项的梯度恒为零），稀疏模式的拓扑决定了信息能沿什么样的图流动。这一篇把 2019–2020 年的几个代表方案连成谱系，最后落在 BigBird 的表达力证明上。
谱系：三种稀疏原语
稀疏注意力的设计空间可以归纳为三族原语，几乎所有方案都是它们的组合：
- 局部模式（banded / block-local）：每个位置只看邻居。代表是 Longformer 的滑动窗口（上篇）。优点是和卷积共享归纳偏置、kernel 友好；缺点是感受野靠层间接力，图直径 $O(n/w)$。
- 步长模式（strided）：Sparse Transformer（Child et al. 2019，OpenAI）用按固定步长取列的方式：一半 head 看前一行，另一半看每第 $\sqrt n$ 个位置，等效于一维卷积的 dilation 结构。它让 $O(\sqrt n)$ 距离内两跳可达，是给图像和音频这类规则网格数据设计的。
- 随机模式（random）：每个位置随机连 $r$ 条边。单独看似乎最不可理喻——随机边既不偏置局部性也不保证任何确定通路，但它有个图论性质后面要用：随机图是扩展图（expander），任意子集都有大量边连向外部，信息扩散快。
加上全局 token（对全体可见、全体对它可见的枢纽行/列），就有了设计的积木。Longformer = 局部 + 全局；BigBird = 局部 + 全局 + 随机；ETC（Extended Transformer Construction）= 局部 + 全局，但把全局侧做成显式的"记忆槽"（memory tokens）而非复用输入里的 CLS。
BigBird 的结构与账本
BigBird（Zaheer et al. 2020）的每个 query 位置 i 允许 attend 的 key 集合固定为：
$$ \mathcal{A}(i) = \underbrace{[i-w/2,\ i+w/2]}_{\text{窗口}\,w\text{ 个}} \cup \underbrace{\{g_1,\dots,g_g\}}_{\text{全局}} \cup \underbrace{\mathcal{R}(i)}_{\text{随机}\,r\text{ 条}}, $$
其中 $\mathcal{R}(i)$ 在实现上是"列 j 以步长 $(n/r)$ 周期性地连向 i"，即 block-random 的确定性版本，比真随机更利于 kernel 化。每行非零元数 $w + g + r$ 是常数，总 pair 数 $O(n)$，attention 的 FLOPs 和物化矩阵都从 $n^2$ 降到 $n$。
账面收益之前都见过，真正的新贡献是论文里的理论结果：这种稀疏注意力仍保留 full self-attention 的两个关键性质。
表达力：稀疏模式什么时候够用
BigBird 证明了两条定理（完整证明在附录，这里给直觉）。设注意力稀疏模式对应的图 $G$（位置为节点，允许 attend 为边）：
序列 universal 逼近。 若 G 包含全局 token（有常数个节点与所有节点相连），则堆叠的 BigBird 层是序列到序列连续函数的 universal approximator。直觉：全局 token 是信息汇聚点——任意位置的值可以（经足够多层）通过全局节点传到任意其他位置，和全连接的"谁都能看谁"在表达能力上等价，差的只是路径长度（两步而非一步）。这解释了 Longformer 为什么加全局行：不是为了性能技巧，是为了保住逼近能力。
Turing 完全。 若 G 直径为 $O(1)$、且每个节点的度数有常数下界，则对应的 transformer 计算模型是 Turing 完全的，可模拟任意图灵机（在"输入可放在 attention 的精度内"的标准假设下）。这两个条件恰好是随机边保证的：随机图（度 ≥ 2 的随机正则图）以高概率直径 $O(\log n)$，BigBird 论文里用 block-random 结构拿到常数直径的结论。换言之，随机边不是噪声，是把图的直径压到常数的构造性工具——窗口给局部精度，全局给汇聚点，随机边给常数直径，三者各司其职，拿掉任何一族，性质证明就过不去。
这两条定理的价值不在"BigBird 因此更好"，而在给稀疏注意力设计立了验收标准：你的稀疏模式对应的图，直径是多少？有没有汇聚节点？这比"在任务上掉不掉点"的纯经验判据更根本——经验掉点可能是训练问题，拓扑缺陷却是结构性的。
小结
从 Sparse Transformer 的步长模式，到 Longformer 的窗口加全局，再到 BigBird 补上随机边并给出表达力证明，稀疏注意力的演进不是"谁 mask 得更狠"，而是对稀疏图拓扑性质的认识逐步精确：窗口保证局部归纳偏置，全局节点提供信息汇聚，随机边保证常数直径。BigBird 的定理把设计标准从经验榜分抬高到结构性质——检查你的稀疏图直径和连通性，再谈长文本。当然，理论保证的是表达能力上限，实际任务收益仍受 kernel 效率、训练稳定性制约，这也是稀疏路线最终在与长上下文外推（RoPE 缩放）的竞争中没有全面胜出的原因之一。