题目
实现Transformer的稀疏注意力，Longformer的滑动窗口。
完整讲解
- 标准 self-attention 的复杂度为序列长度 $L$ 的平方（$O(L^2)$），长序列时显存与算力压力大。稀疏注意力只计算部分 query-key 对，使复杂度降为 $O(L \cdot k)$ 等。Longformer 是代表性方案之一，采用滑动窗口等局部+全局稀疏模式。
- 局部滑动窗口：每个 query 只 attend 到左右各 $w$ 个 token（窗口大小 $2w+1$），复杂度 $O(L \cdot w)$。适合局部依赖强的文本；窗口可重叠，信息可间接传递多跳。
- 全局 token：指定少量 token（如 [CLS]、句首）为全局，所有位置 attend 到它们、它们 attend 到全部，用于汇总信息；数量少，不改变主导复杂度。
- 实现：attention 矩阵为带状+少量全行/列；可用 banded mask 或稀疏矩阵格式只算非零块；或分块计算（每 query 块只与对应 key 块及全局做 attention）。
三、与推荐的关系
- 长序列行为、长文本用 Transformer 时，滑动窗口可限制长度、降低延迟；推荐序列可「近期全量+远期采样」或直接滑动窗口，兼顾效果与成本。
四、实现要点
-
| 注意力 mask：仅允许 (i, j) 在 |
i-j |
≤ w 或 j 为全局时为 1；softmax 前对禁止位置置 $-\infty$。高效实现可用块状 kernel 或稀疏库。 |
面试要点
- 能说清 Longformer 滑动窗口：每 query 只 attend 窗口内+全局 token；复杂度 $O(L \cdot w)$。
- 能说明全局 token 的作用、以及 mask 与实现思路（带状、分块、稀疏）。
记忆要点
- Longformer：局部滑动窗口（每 query 左右各 w）+ 少量全局 token；复杂度 O(L·w)。
- 实现：banded mask 或稀疏；推荐长序列可滑动窗口降成本。