1 · 基础: 成本、静态图与混合流式拓扑

稠密注意力把长度为 $n$ 的序列展开成 $n\times n$ 的交互图。这个表示法干净，也让任意两处信息在一层内直接相遇；代价是序列每扩大一倍，分数配对扩大四倍。Sparse Attention 的第一批方案没有训练路由器，也不按输入内容临时检索，而是预先规定哪些边存在。静态拓扑因此成为分析整条技术路线的参照系：边数可以数，最短路径可以算，kernel 能否规则化也可以直接检查。邻接矩阵 $M$ 用来表示 mask。对因果模型， $M_{ij}=1$ 必须满足 $j\le i$ ；对双向编码器则没有这条时间约束。第 $i$ 行非零位置构成集合 $N(i)$ 。注意力仍然执行缩放点积与 softmax，只把归一化范围限制到 $N(i)$ 。稀疏改变的是可交互集合，softmax 定义保持不变。

1. 先把四类成本拆开

1.1. 配对、激活与 cache

单个 head 的稠密 $QK^\top$ 约需 $2n^2d_h$ 次浮点运算，随后用权重乘 $V$ 还需近似相同数量。若每行只有 $k$ 个有效 key，理想工作量降为 $O(nkd_h)$ 。训练还要为反向传播保存或重算选择、概率与归一化统计量；FlashAttention 通过分块重算降低峰值显存，却仍执行所有合法配对。 Decode 的成本构成不同。第 $t$ 步只有一个新 query，稠密注意力计算约为 $O(td_h)$ ，同时读取 $t$ 个历史 key 与 value。此时主要压力常来自 KV cache 容量和带宽。静态窗口若只保留最近 $w$ 个 KV，可把每步容量与读取限制在 $O(wd_h)$ ；若实现仍保留并扫描全部 cache，再在末尾应用窗口 mask，理论边数没有转化为系统收益。

1.2. 路径长度是另一项成本

边少会增加信息传播距离。半径为 $r$ 的双向窗口每层最多把信息向左右各推进 $r$ 个位置，两个相距 $D$ 的 token 至少要经过 $\lceil D/r\rceil$ 层才能建立路径。因果窗口只向历史读取，较早信息向后传播的最短层数同样随距离增长。增加全局 token 可以缩短图直径，但所有远距离交换都可能集中到少数通道。 复杂度下降与有效感受野扩大是两条不同曲线。 边数只说明算多少，图路径只说明理论上能否到达；优化是否学到跨层转发，还要由训练任务和实验证据回答。

2. 三种静态构件

2.1. 滑动窗口

窗口注意力让位置 $i$ 只访问邻近位置。对因果模型可写成 $N(i)={j:\max(1,i-w+1)\le j\le i}$ ，其中 $w$ 包含当前位置。长度 $n=8,w=3$ 时，各行有效 key 数依次为 $1,2,3,3,3,3,3,3$ ，总边数是 $1+2+6\times3=21$ ；完整因果注意力有 $8\times9/2=36$ 条边。窗口省去 15 条边，但位置 8 在一层内看不到位置 1。窗口规则适合块化并能配合环形 KV cache。它的边界也明确：依赖距离超过多层感受野时，信息必须被中间 token 连续携带；一旦中间表征没有保留所需细节，后层无法重新访问原始 KV。

2.2. 全局与随机连接

Longformer 给少量位置配置全局注意力。全局位置既读取全部 token，也可被全部 token 读取；任务分类 token 或问题 token 因而可以聚合整段信息。若有 $g$ 个全局位置，额外边数约为 $O(ng)$ 。当 $g\ll n$ 时仍保持线性增长，但 $g$ 不是免费的：全局位置增加稠密条带，并要求任务预先知道哪些位置承担中转。 BigBird 将局部窗口、全局 token 与随机连接组合。随机边让图更快混合，并降低只靠局部链路造成的长路径。理论结论依赖特定随机图和全局连接假设，不能直接推出任意手写 mask 都保持完整注意力的表达性质；实践中还要固定随机模式、块大小和实际可执行 kernel。

3. 三篇正文怎样衔接

3.1. 成本模型先于方法名

成本与阶段先统一计算口径, 成本模型再按训练、prefill、decode 分别计算 FLOPs、激活、KV 容量和读取量。相同的 $O(nw)$ 在三个阶段并不对应相同收益：训练可能受算力约束，decode 可能受带宽约束，动态路由还可能先读完整 cache 才得到选择结果。

静态图结构组织窗口、全局与随机连接, Longformer 与 BigBird把静态 mask 展开到逐行邻接集合，并比较局部、全局和随机边。重点是每种边解决哪一种路径问题，以及论文结论在编码器、因果生成和硬件实现之间能否直接迁移。

3.2. 混合层与 attention sink

混合与流式说明层轴与 token 轴的组合方式, Hybrid SWA 与 attention sink讨论两类常被混在一起的保真手段。局部层之间插入全局层，是沿深度轴周期性恢复全局通信；保留序列开头的 sink token，则是为 streaming decode 保留 softmax 中稳定吸收多余概率质量的位置。前者改变层级拓扑，后者改变 cache 边界，两者不能相互替代。静态方案适合作为基线，是因为系统能预先知道访问地址。后续动态稀疏必须证明内容相关选择的质量收益足以覆盖路由、索引和负载不均衡成本。若静态窗口已经满足任务依赖，动态方法增加的复杂度未必值得。

KDA 与混合线性注意力把历史从逐 token KV 改成固定大小矩阵状态，再用少数 MLA 或 softmax 层保留精确回看。它与稀疏选择同样追求长上下文效率，约束却落在状态容量而非候选召回上；先分清这两种误差，后面比较 NSA、DSA 与跨层 KV 复用才不会把「少读地址」和「没有地址」混在一起。

4. 判断结论的适用范围

4.1. 编码器与生成模型

Longformer 和 BigBird 的经典实验大量面向双向编码任务，位置可以同时读取左右邻居。自回归语言模型只能读取过去，随机边也不能越过因果边界。把双向 mask 改为因果 mask 后，图直径、全局 token 的信息流向和任务接口都会变化，因此不能只凭方法名称认定生成阶段具有相同性能。

窗口训练与窗口 decode 也要匹配。训练时若使用稠密注意力，部署时突然截断 KV，模型可能依赖从未受限的远距离边；训练时一直使用窗口，则模型有机会学习跨层搬运或把稳定状态写到保留位置。两者仍不保证窗口外事实被可靠保存，长距离检索必须单独评测。

4.2. mask 与 kernel

规则 mask 只有在实现能跳过无效块时才节省时间。块稀疏 kernel 通常要求块大小对齐，边界位置和全局 token 可能造成补零或额外分支。短序列上，索引与调度开销会使稀疏版本慢于优化充分的稠密 kernel；长度增长后，少读数据与少做矩阵乘法才逐渐占优。因此报告结果时要同时给出模型维度、窗口宽度、全局 token 数、块大小、序列长度、batch、精度、硬件与基线 kernel。静态拓扑提供可预测的边集合，但端到端收益仍由执行这些边的系统决定。

质量结论也要按距离分桶。平均困惑度会把大量局部预测与少量长依赖混在一起。一个窗口模型可以在局部语言建模上保持良好均值，却在窗口外的精确引用上完全失败。评测应把 query 与证据的距离分成窗口内、一到两倍窗口、多层理论可达区和理论不可达区，再分别报告准确率。若加入全局 token，还应改变全局位置的数量与放置规则，检查提升来自更短路径还是更多参数化接口。

静态随机边的评测还要固定随机种子或报告多次采样。不同图可能具有相近边数，却出现不同的局部瓶颈和最短路径。图论性质只给出结构条件，模型是否学会利用随机连接仍需消融。这样的分桶能把「平均表现没有下降」改写成可定位的结论：哪些距离、哪些任务和哪些拓扑真正受益。

训练拓扑必须写进模型定义。 mask 不只是部署参数。训练期间每个 token 看见哪些上下文，会改变梯度路径和模型形成的内部策略。推理时缩小窗口属于近似执行，推理时扩大窗口也不保证模型会使用新出现的远距离边。若一个模型在不同层采用不同窗口或周期性全局层，这张层表应与权重配置一同保存。可复现配置至少给出每层模式、左右或因果窗口、全局位置规则、块大小与特殊 token。这样才能由配置重建邻接矩阵，进一步复算边数、cache 和路径。只留下「使用 sliding window」的文字标签，会丢失决定行为的主要参数。

5. 从结构定义走到实际表现

5.1. 理论、代码与测量各管一段

Sparse Transformer 的特定稀疏分解回答边数怎样下降, BigBird 在含常数个全局 token 等条件下讨论表达能力, StreamingLLM 则观测初始 token 在流式推理中的特殊作用。到了实现层, Longformer 的 TVM 与 sliding-chunks 路径、BigBird 的 block 参数和静态 shape 限制、FlashAttention 的精确 attention kernel 又会改变真实运行成本。只要邻接集合和层表已经确定, 边数、分阶段 cache 容量和混合层加权都可以独立复算。实际加速还要看目标硬件上的 benchmark, 因为相同边数可能对应完全不同的访存连续性与调度开销。

三个数字不能互相替代。复杂度、表达能力和工程吞吐回答的是三个问题。BigBird 的线性边数与通用逼近各有自己的构造和假设；FlashAttention 的 IO 优化也没有删除边。看到「线性复杂度」时仍要追问模型能否利用远距路径, 看到 kernel 加速时还要追问端到端时间里 attention 占多少。数值手算只对给定 $n,w,g$ 和层表成立。真实系统还包含 block 对齐、kernel 调度与通信，因此手算给出上界或下界后，仍要用作者实现和目标硬件上的测量加以核对。

5.2. 把注意力写成带权有向图

对第 $\ell$ 层，令 $G^{(\ell)}=(V,E^{(\ell)})$ 。节点 $i\in V$ 表示第 $i$ 个 token；若位置 $i$ 在这一层允许读取位置 $j$ ，则有有向边 $(j,i)\in E^{(\ell)}$ 。注意力权重是边权。以单头为例，输入状态为 $h_j^{(\ell)}$ ，值向量沿边聚合得到输出投影之前的 $a_i^{(\ell)}$ ：

a_i^{(\ell)}= \sum_{j:(j,i)\in E^{(\ell)}} \alpha_{ij}^{(\ell)}W_V^{(\ell)}h_j^{(\ell)}.

残差连接还给每个节点保留了一条跨层自环。这样写有两个好处。其一，计算量由边数 $|E^{(\ell)}|$ 控制；其二，信息能否到达由多层图的复合关系控制。若从证据位置 $j$ 到查询位置 $i$ 存在一条依次经过 $E^{(1)},E^{(2)},\ldots,E^{(L)}$ 的路径，证据才有机会影响最终表示。单层没有直连并不等于永远不可达，不过路径每增加一跳，都要经过一次有限维压缩、非线性变换和残差混合。

以因果窗口 $w$ 为例，一层最多向前跨 $w-1$ 个位置， $L$ 层的结构可达距离不超过 $L(w-1)$ 。这只是必要条件。中间 token 必须把远处信息编码进自己的有限维状态，后续层还要继续选择这条链，所以「图上可达」弱于「可可靠回忆」。若每隔若干层加入全局边，最短路径会骤然缩短；若只加入随机边，平均路径可能缩短，但具体证据是否落在可用路径上具有方差。

Yun 等人给出了稀疏 Transformer 通用逼近的充分条件，并证明每层只含 $O(n)$ 条连接也可能保持通用逼近能力。这个结论说明二次边数并非表达能力的必要条件，却没有承诺固定深度、固定宽度和有限数据下与稠密模型等价。构造性存在结论与训练后模型能否找到有效路由之间，还隔着优化、容量和样本复杂度。

从边预算推到传播预算。设每个普通位置每层保留 $k$ 条入边，共有 $L$ 层。忽略边集合重合时，一个节点在 $L$ 层后最多受到 $k^L$ 个源节点影响；实际可达节点数还受序列长度、因果方向和拓扑重叠限制。局部窗口的大量路径会反复经过相邻位置，因此覆盖增长远慢于 $k^L$ 。随机边更容易扩大覆盖，却会牺牲局部连续性。局部边、少量全局边与内容路由之所以经常混合使用，正是因为三者分别提供稳定近邻、较短直径和针对当前 query 的远距连接。还可以把层间传播写成布尔矩阵。令 $A^{(\ell)}_{ij}=1$ 表示第 $\ell$ 层中 $i$ 可读取 $j$ ，加入单位阵以表示残差通路，则

R^{(L)}=\mathbf 1\!\left[ (A^{(L)}+I)(A^{(L-1)}+I)\cdots(A^{(1)}+I)>0 \right].

$R^{(L)}$ 只说明存在路径。若把布尔乘法换成真实注意力矩阵乘积，某条长度为 $L$ 的路径贡献近似含有 $\prod$ {\ell=1}^{L}\alpha_{e_\ell}^{(\ell)} $\prod_{ℓ = 1}^{L} α_{e_{ℓ}}^{(ℓ)}$ 。每跳权重都小于一时，长路径的直接贡献可能快速衰减；残差与 MLP 可以改变这一结果，却不能让「存在路径」自动变成稳定信号。评测长距离检索时，除了距离，还应控制所需跳数和中间位置是否具有可压缩摘要。

稀疏近似的两个误差来源。内容选择常以稠密注意力为参照。设稠密概率为 $p_j$ ，保留集合为 $S$ ，被删除的概率质量为

\tau=\sum_{j\notin S}p_j.

在保留集合内重新归一化后， $\hat p_j=p_j/(1-\tau)$ 。若 $\mu_S$ 和 $\mu_{\bar S}$ 分别是保留项与删除项按各自概率归一化后的 value 均值，则

o=(1-\tau)\mu_S+\tau\mu_{\bar S}, \qquad \hat o=\mu_S,

因而

o-\hat o=\tau(\mu_{\bar S}-\mu_S).

误差同时取决于尾部质量 $\tau$ 和首尾 value 的差异。只报告 top- $k$ 命中率会漏掉第二项：选择器错过许多与已选 value 相近的 token，输出仍可能变化很小；漏掉一个概率不大但 value 方向独特的 token，也可能产生明显误差。最新的 top- $k$ 理论工作把总变差距离与被删除 softmax 质量直接联系起来，这给选择器评测提供了比索引重合率更贴近 attention 输出的量。

另一类误差发生在候选生成之前。哈希、聚类、页级上界或低维索引先构造候选集 $C_i$ ，精确分数只在 $C_i$ 内计算。最终误差可以拆成「相关 key 没进入候选集」和「候选集内排序或截断有误」两部分。前者无法靠更精确的局部 softmax 修复，后者可以通过扩大 $k$ 、提高索引维度或改进打分器降低。把候选召回率、尾部概率质量和输出误差同时报告，才能判断瓶颈到底在索引还是截断。

基础路线之间的共同坐标。静态窗口把 $E^{(\ell)}$ 写进架构，查询内容不会改变边；哈希与聚类依据低维相似性构造候选；学习型索引器预测边；跨层共享把一次选择复用于多个 attention 层；KV 驱逐则永久或阶段性删除一部分可选节点。这几类方法都在减少边，但它们回答的并非同一个问题。

静态拓扑控制「哪些边原则上存在」，边集合可提前生成。
动态索引控制「当前 query 值得精算哪些边」，主要风险是召回不足。
跨层共享控制「多久重新决定一次边」，主要风险是表示漂移后旧索引失效。
cache 驱逐控制「哪些历史状态仍然存在」，被删状态通常无法在后续步骤恢复。
训练原生稀疏把边选择放进训练分布，使模型有机会适应缺边并学习替代路径。

因此，同样写成每行 $k$ 条边，窗口、NSA 一类训练原生选择、DSA 一类索引选择以及 H2O 一类驱逐策略的可恢复性完全不同。窗口外信息仍可能经中间状态传播；动态选择下一层可以重新选回遗漏 token；被驱逐的 KV 除非另有压缩记忆，后续 query 已经没有读取原表示的机会。比较方法时先辨认删除发生在哪一层，再讨论复杂度和质量。