Sparse Transformer (2019, Child et al.)

12. Sparse Transformer (2019, Child et al.)

arxiv: 1904.10509

核心问题：Attention 的 O(n²) 复杂度是 Transformer 的阿喀琉斯之踵。当序列长度到 10K、100K 时，attention 矩阵变成 100K × 100K，存储和计算都不可行。有没有办法让 attention "稀疏化"——只计算一部分，而不是全矩阵？

方法创新：
Sparse Transformer 的核心是attention 矩阵的稀疏分解。

原始 attention：

Attention(Q, K, V) = softmax(QK^T / √d) V

复杂度 O(n²)。

Sparse Transformer 提出两种稀疏模式，交替使用：

1. Strided attention：每个位置只关注固定步长间隔的位置（如每隔 1 个、2 个）。类似棋盘的黑白格。
2. Fixed local attention：每个位置只关注周围固定窗口内的位置。

通过巧妙的分解，稀疏 attention 可以在 O(n√n) 或 O(n log n) 复杂度内计算。论文还引入了：

• 更深的网络架构和特殊的初始化
• Attention 矩阵重计算（recomputation）节省内存
• 高效的 attention 核函数

关键数字：

• 可以建模 tens of thousands of timesteps 的序列
• 用数百层网络
• 在 Enwik8、CIFAR-10、ImageNet-64 上设置密度建模新 SOTA
• 展示了"million-length sequences"的可能性

影响评估：
Sparse Transformer 是长序列建模的里程碑。它证明了 attention 不必是全连接的——有结构的稀疏化可以在保持质量的同时处理极长序列。后续的长模型（Longformer、BigBird、Performer）都沿用了"稀疏 attention"的思想。它也为后来的线性 attention、Mamba 等亚二次复杂度架构铺平了道路。

费曼点评：

Sparse Transformer 的思维方式是"不要算不需要算的东西"。全 attention 假设每个词和所有其他词都相关——但语言中真正相关的词其实很少（语法上的近邻、语义上的共指）。Sparse Transformer 像一个好的编辑：不是读完整本书再做摘要，而是先读章节标题（strided）和关键段落（local）。论文的真正价值是证明了一件事：稀疏性不必然导致信息丢失——关键是稀疏的"模式"要匹配数据的"结构"。

arxiv: 1904.10509

#论文深度研究 #小凯