如何降低 Transformer 的计算复杂度？常见的稀疏注意力变体有哪些

1️⃣ 考察意图

面试官想看你是否真正理解Transformer的O(n²)计算瓶颈，而非仅背公式。考察类型是工程取舍+系统设计，刁钻点在于：你是否能区分理论复杂度与硬件实际开销（如显存带宽瓶颈），以及能否根据任务场景（长文本分类 vs 生成）选择合适变体。答好了能展示你对LLM底层原理的扎实理解、工程选型能力，以及对稀疏注意力trade-off的深度认知（召回率 vs 速度 vs 实现复杂度）。

2️⃣ 标准答

核心问题：标准自注意力中，每个token需与所有N个token计算点积，复杂度O(N²d)，当N>4096时显存和计算都爆炸。

降低复杂度的三大思路：

稀疏注意力：限制每个token只与部分token交互，复杂度降至O(N * k)，k是固定窗口大小或采样数。
线性注意力：用核函数近似softmax，复杂度O(Nd²)，但精度损失大，实践中不常用。
分块/层次化：如Longformer的滑动窗口+全局token，或BigBird的随机+窗口+全局。

常见稀疏注意力变体：

Longformer：滑动窗口（窗口大小w=512）+ 少量全局token（如[CLS]）。复杂度O(Nw)，适合长文本分类、QA。坑：窗口大小w需调参，w太小丢失长距离依赖，w太大退化为O(N²)。实际落地时，全局token数量需根据任务调整（分类任务1-2个，QA任务每段1个）。
BigBird：随机注意力（r个随机token）+ 窗口注意力（w）+ 全局注意力（g个全局token）。复杂度O(N(r+w+g))，理论覆盖全图。工程取舍：随机采样保证信息流通，但随机性导致训练不稳定，需增大batch size或梯度累积。
Reformer：LSH（局部敏感哈希）将token分桶，每个token只与同桶内token计算注意力。复杂度O(N log N)。坑：哈希碰撞导致信息丢失，且分桶数需2的幂，序列长度非2的幂时需padding，浪费计算。
Sparse Transformer：固定稀疏模式（如strided模式：每k步取一个token）。复杂度O(N√N)，但模式固定，无法适应动态依赖。
FlashAttention：非稀疏注意力，但通过分块计算+重计算（tiling + recomputation）将显存从O(N²)降至O(N)，速度提升2-4倍。实际落地的坑：需GPU支持Tensor Core（A100/H100），且对长序列（>16K）仍需稀疏化配合。

工程选型依据：

长文本分类：Longformer（窗口+全局）最稳，实现简单，HuggingFace有现成代码。
长文本生成：BigBird（随机+窗口+全局）更优，因生成需全局信息，随机采样保证多样性。
超长序列（>32K）：Reformer或Sparse Transformer，但需接受精度损失。
硬件限制：显存<16GB时，优先FlashAttention+Longformer；显存>40GB时，可直接用BigBird。

trade-off总结：稀疏注意力本质是用召回率换速度。窗口注意力丢失长距离依赖，随机注意力引入噪声，全局注意力增加计算。选型时需在任务指标（如F1、BLEU）和推理延迟间平衡。

3️⃣ 答题模板（30 秒电梯版）

“这个问题我从三个层面回答：第一，Transformer复杂度O(N²)的根源是自注意力中每个token需与所有N个token计算点积；第二，主流稀疏注意力变体包括Longformer的滑动窗口+全局、BigBird的随机+窗口+全局、Reformer的LSH哈希分桶，以及FlashAttention的分块计算；第三，工程选型需根据任务类型（分类用Longformer，生成用BigBird）和硬件限制（显存<16GB用FlashAttention+Longformer）做trade-off。总结一句：稀疏注意力本质是用召回率换速度，选型时需在任务指标和延迟间平衡。”

4️⃣ 高频追问 & 应对

追问 1：Longformer的窗口大小w如何选择？如果w=512但序列长度是8192，长距离依赖怎么捕获？

窗口大小w通常设为512（经验值，来自Longformer论文），但需根据任务调整：分类任务w=256即可，QA任务w=512，生成任务w=1024。长距离依赖通过全局token捕获：在分类任务中，[CLS] token作为全局token，与所有token交互；在QA任务中，每个段落的首token设为全局。如果全局token不够，可增加全局token数量（如每512个token设1个），但复杂度会线性增加。实际落地时，建议用验证集调w和全局token数，观察F1/准确率变化。

追问 2：BigBird的随机注意力中，随机采样数r怎么定？会不会导致训练不稳定？

r通常设为窗口大小w的1/10（如w=512时r=50），来自BigBird论文的理论分析：随机采样保证图连通性，r需≥log(N)才能以高概率覆盖所有节点。训练不稳定是常见坑：随机采样导致每次前向计算图不同，梯度方差大。解法：① 增大batch size（如从32增至64）降低梯度方差；② 使用梯度累积（accumulation steps=4）；③ 固定随机种子，保证每个epoch内采样模式一致。如果仍不稳定，可改用确定性采样（如按位置分块）。

追问 3：FlashAttention和稀疏注意力比，哪个更实用？为什么？

两者互补而非替代。FlashAttention通过分块计算+重计算降低显存，但复杂度仍是O(N²)，适合序列长度≤16K的场景。稀疏注意力降低复杂度至O(N)，适合超长序列（>16K）。实际工程中，优先用FlashAttention+Longformer组合：FlashAttention处理窗口内计算，Longformer处理稀疏化。如果序列长度>32K，则必须用稀疏注意力（如BigBird或Reformer）。选型依据：显存充足时用FlashAttention（速度更快），显存受限时用稀疏注意力。

5️⃣ 避坑 · 常见错误答法

❌ 只背公式：说“复杂度是O(N²)，用稀疏注意力降到O(N)”，但不解释具体变体和工程取舍。✅ 必须给出具体变体（Longformer、BigBird）和选型依据（分类用Longformer，生成用BigBird），并说明trade-off（召回率 vs 速度）。
❌ 忽略硬件限制：说“用BigBird解决所有长文本问题”，不考虑显存和计算开销。✅ 必须提及硬件限制（显存<16GB时优先FlashAttention+Longformer），并给出实际数字（如窗口大小w=512，全局token数=1-2）。
❌ 混淆稀疏注意力和线性注意力：说“稀疏注意力就是线性注意力”。✅ 明确区分：稀疏注意力是限制交互范围（O(Nk)），线性注意力是核函数近似（O(Nd²)），两者原理不同，线性注意力精度损失大，实践中不常用。

6️⃣ 简历呼应

如果你有RAG项目：从长文档检索切入，说明如何用Longformer的滑动窗口+全局token处理长文档（如论文全文），对比标准Transformer的显存节省（如从24GB降至8GB），并提及窗口大小w=512的调参经验。
如果你只做过传统NLP：用CNN的局部感受野类比稀疏注意力的窗口机制，说明Longformer的滑动窗口类似CNN的卷积核，全局token类似池化层，帮助面试官理解你的迁移能力。
如果你是校招无项目：聚焦FlashAttention论文复现，说明你理解分块计算和重计算的原理，并用PyTorch实现一个简化版（如只实现tiling部分），在GPU上测试显存节省（如从O(N²)降至O(N)）。
Longformer: The Long-Document Transformer (Beltagy et al., 2020)
Big Bird: Transformers for Longer Sequences (Zaheer et al., 2020)
Reformer: The Efficient Transformer (Kitaev et al., 2020)
FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (Dao et al., 2022)
Sparse Transformer: Generating Long Sequences with Sparse Transformers (Child et al., 2019)

—— 本场面试完 ——