【Transformer 与注意力机制】43｜稀疏与局部注意力：Longformer、BigBird、Sparse Transformer
内容提要
本文通过邻接矩阵统一理解Sparse Transformer、Longformer和BigBird三种固定稀疏注意力模式，分析其图论依据、工程代价及生产落地难点。文章指出稀疏注意力未取代全注意力，原因在于kernel生态、训练配方和任务敏感性限制，并讨论学习型稀疏的争论与开放问题。
延伸解读
稀疏注意力的工程代价：从理论到落地的鸿沟
论文中的复杂度分析假设理想执行，但真实 GPU 更偏好规则、密集的矩阵运算。Longformer 因带状矩阵乘法无原生支持，需用 TVM 自建 CUDA kernel；BigBird 将随机边设为 block 级别以适配分块 GEMM；MInference 则把动态稀疏收窄为三种规则模式。不规则 mask、变长序列和 batch 内不均匀都让稀疏 pattern 难以高效执行，理论收益常被工程开销抵消。
为什么稀疏注意力没有取代全注意力
三个原因叠加：kernel 生态不对等，FlashAttention 可作 drop-in 替换，而稀疏 pattern 需定制 kernel；训练配方路径依赖，预训练团队已验证 full attention 的 scaling 行为，换稀疏需重新验证；任务敏感性无法提前判断，BigBird 证明存在稀疏必吃亏的任务，但训练前难以预知下游任务是否落入此类。因此稀疏注意力主要用于极长上下文场景，而非全面替代。
固定模式与学习型稀疏的争论焦点
固定模式（Longformer、BigBird）依赖设计者先验，有通用近似和 Turing 完备性支撑，但 BigBird 的 OVC 下界表明存在任何稀疏图都需更多层的任务。学习型稀疏（Reformer、Routing Transformer、NSA）让选边由数据决定，理论上更贴近任务需求，但引入训练稳定性问题（如路由塌缩），且大规模复现证据有限。目前两者是权衡关系，无一方胜出。
Q&A
Longformer、BigBird 和 Sparse Transformer 在注意力机制上有什么共同点和区别？
它们都是固定稀疏注意力模式，通过减少注意力矩阵中的边数来降低计算复杂度。共同点是都使用局部窗口和少量全局 token 来保持连通性。区别在于：Sparse Transformer 使用确定性因子分解（strided/fixed pattern），复杂度为 O(n√n)；Longformer 使用滑动窗口加全局 token，复杂度为 O(nw)；BigBird 在局部窗口和全局 token 基础上增加随机边，复杂度为 O(n)。
为什么 Longformer 需要自己编写 CUDA kernel？
因为滑动窗口注意力本质是带状矩阵乘法，标准 PyTorch/TensorFlow 的 dense matmul 无法高效处理。Longformer 作者使用 TVM 编译器从头描述带状矩阵乘法，生成并编译成 GPU device code，以实现最优显存和速度。
BigBird 为什么在局部窗口和全局 token 之外还要加随机边？
随机边基于 Erdős–Rényi 随机图理论，可以保证任意两点间的最短路径长度为 O(log n)，同时保持图的谱性质接近完全图，从而在理论上弥补稀疏化带来的连通性损失。
稀疏注意力在生产环境中落地的主要难点有哪些？
主要难点包括：不规则 mask 导致 GPU 利用率低，变长序列需要 padding 或多套 kernel，batch 内样本的随机 block 不同导致无法统一处理。这些因素使得理论上的复杂度优势难以转化为实际吞吐提升。
为什么稀疏注意力没有全面取代全注意力？
原因有三：一是 kernel 生态不对等，FlashAttention 等通用 kernel 已广泛集成，而稀疏模式需要定制 kernel；二是训练配方路径依赖，大规模预训练已验证 full attention 的 scaling 行为，更换模式风险高；三是任务敏感性无法提前判断，存在某些任务稀疏注意力需要更多层才能解决，但事前难以识别。
稀疏注意力和 Ring Attention 有什么区别？
稀疏注意力修改邻接矩阵，删除部分边以降低复杂度；Ring Attention 不删除任何边，而是通过分布式执行策略将完全图的计算拆分到多卡或 chunk 上，保证结果与单卡 full attention 一致。两者是正交的，可以结合使用。
学习型稀疏注意力（如 Reformer、Routing Transformer、NSA）与固定模式稀疏注意力相比有什么优缺点？
学习型稀疏让连接规则由数据或训练决定，理论上更贴近任务需求，但引入了额外的计算和训练稳定性问题（如路由塌缩、簇不均衡）。固定模式稀疏用规则性换来了更简单、可预测的 kernel 行为，但可能将某些重要关系设为结构性不可达。目前没有证据表明哪一派全面占优。
BigBird 论文中提到的 OVC 下界是什么意思？
BigBird 证明存在一个具体任务（找最远向量），任何边数为 O(n) 的稀疏注意力图都需要 Ω(n^{1-o(1)}) 层才能解决，而 full attention 只需 O(1) 层。这基于正交向量猜想，说明稀疏注意力在深度上存在固有劣势，且该下界适用于所有稀疏方案。
