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 #论文深度研究 #小凯