1.2.1 · 静态稀疏: Longformer, BigBird 与滑动窗口

标准自注意力让长度为 $n$ 的序列产生一个 $n\times n$ 的分数矩阵. 序列长度翻倍时, 分数数量变成四倍; 即使实现没有把完整矩阵写回显存, 点积和 softmax 仍然要处理平方级的候选关系. 长文档里真正有用的关系往往只占其中一部分: 邻近 token 需要稳定交换局部信息, 少数任务相关位置需要跨越全文, 其余远距离配对未必值得逐层逐头计算. 静态稀疏注意力把这项观察写进拓扑: 在看到输入内容以前, 先规定每个查询可以访问哪些键.

Longformer 把局部滑动窗口, dilation 和少量任务驱动的 global attention 组合起来, 面向长文档编码任务. BigBird 把稀疏图拆成局部边, 随机边和全局边, 并分析这种图在表达能力上的条件. 两者都把全连接注意力改成结构化子集, 但不能只用「从平方降到线性」概括. 哪些边留下, 信息经过几层才能到达远处, 全局节点承受多少流量, 稀疏布局能否映射到高效 kernel, 都会决定节省是否成立.

静态稀疏的核心约束是先固定候选边, 再在候选边内部做内容相关的 softmax. 它仍然计算 QK 分数, 仍然归一化并混合 Value; 被取消的是掩码外的配对, 不是注意力机制本身.

静态注意力掩码与跨层全局中继

图 1: 八位置教学示例：全连接、双向半径 1 窗口，以及窗口加全局位置 4 的允许配对分别为 64、22、32 个。上半部横轴是被读取的 key，纵轴是发起读取的 query；下半部箭头按信息流方向绘制。机制依据 Longformer v2 §3.1，参数与路径为教学构造。

图 1 解析:

上半部每个着色单元格只表示允许计算该配对，未指定 softmax 权重。全局位置增加一整行、一整列；与局部带重叠的单元格只计一次。
第一层位置 4 读取输入位置 8，第二层位置 2 才读取更新后的位置 4。同一层并行更新，位置 2 无法在第一层拿到这次全局汇聚的结果。
上方三张掩码用于双向编码器。换成因果生成后，位置 4 无法读取未来位置 8，位置 2 也无法读取未来位置 4；不能直接照搬两跳全局中继。

查看原尺寸图

1. 从全连接矩阵到稀疏图

掩码精确定义了谁能读谁。设一层输入为 $X\in\mathbb{R}^{n\times d}$ , $n$ 是 token 数, $d$ 是隐藏维度. 单个注意力头的投影为 $Q=XW_Q$ , $K=XW_K$ , $V=XW_V$ , 其中 $Q,K\in\mathbb{R}^{n\times d_h}$ , $V\in\mathbb{R}^{n\times d_v}$ . 查询位置 $i$ 对键位置 $j$ 的未归一化分数为:

s_{ij}=\frac{q_i^\top k_j}{\sqrt{d_h}}. \tag{1}

全连接注意力允许 $j\in{1,\ldots,n}$ . 静态稀疏注意力为每个查询位置 $i$ 指定邻居集合 $\mathcal{N}(i)$ . 掩码 $M\in{0,-\infty}^{n\times n}$ 写成:

M_{ij}=\begin{cases} 0,&j\in\mathcal{N}(i),\\ -\infty,&j\notin\mathcal{N}(i). \end{cases} \tag{2}

把式 (2) 加到式 (1), 再沿允许的键归一化:

\alpha_{ij}=\frac{\exp(s_{ij})}{\sum_{t\in\mathcal{N}(i)}\exp(s_{it})},\qquad j\in\mathcal{N}(i), \tag{3}

o_i=\sum_{j\in\mathcal{N}(i)}\alpha_{ij}v_j. \tag{4}

式 (3) 说明被保留的边仍由内容决定权重. 「静态」修饰的是集合 $\mathcal{N}(i)$ , 不是权重 $\alpha_{ij}$ . 同一位置在不同样本中访问的索引可以相同, 但分数和输出会随输入改变. 如果每个查询恰好保留 $m$ 个键, 分数数量从 $n^2$ 变成约 $nm$ . 当 $m$ 不随 $n$ 增长时, 注意力关系数对序列长度呈线性增长.

把位置视为节点, 允许的配对视为有向边, 一层注意力只沿一条边传递信息. 经过两层后, 位置 $i$ 能接收二跳邻居的信息; 经过 $L$ 层后, 可达范围由稀疏图的 $L$ 跳邻域决定. 因而边数只回答计算量, 图直径和路径长度才回答远距离依赖需要多少层.

线性边数不自动等于线性运行时间。全连接单头的 QK 点积约需 $n^2d_h$ 次乘加, AV 混合约需 $n^2d_v$ 次乘加. 若每行保留 $m$ 个位置, 两项分别变成约 $nmd_h$ 与 $nmd_v$ . 注意力分数或 softmax 中间量的逻辑规模也从 $n^2$ 变成 $nm$ . 投影 $XW_Q,XW_K,XW_V$ 的计算仍是 $O(ndd_h)$ 量级, 前馈网络也没有因稀疏掩码而改变.

运行时间还取决于边的排列. 连续窗口能按块读取 K 和 V, 地址规则, 数据复用较好. 任意随机边会产生 gather 和不连续访存; 如果框架先构造稠密 $n\times n$ 分数再用掩码填 $-\infty$ , 算术工作一点也没有减少. 即便调用真正的 sparse kernel, 当 $n$ 较短或 $m$ 较大时, 索引处理, kernel 启动和边界填充也可能盖过少算的点积.

复杂度结论必须同时注明「逻辑边数」与「实际执行布局」. $O(nm)$ 描述需要计算的关系, 不保证硬件以相同比例提速. 连续块, 固定块大小和足够大的序列通常比逐元素不规则稀疏更容易兑现收益.

训练时还要保存反向传播需要的中间状态. 激活内存可随边数下降, 但 Q, K, V, 残差流和前馈层激活仍按 $n$ 增长. 推理时则要区分编码器一次性前向, causal Prefill 与逐 token Decode. Longformer 原始目标主要是编码长文档; 把同一个图直接搬到自回归 Decode, 缓存读取规律和可见方向都会变化, 不能从编码器实验直接推出生成吞吐.

1.1. 滑动窗口把局部性写进拓扑

窗口宽度如何决定边数和感受野。对双向编码器, 设单侧半径为 $r$ , 查询位置 $i$ 的局部邻居集合为:

\mathcal{N}_{\mathrm{local}}(i)=\{j:1\le j\le n,\ |i-j|\le r\}. \tag{5}

忽略序列两端后, 每个查询访问 $w=2r+1$ 个位置. 总边数接近 $nw$ . 边界位置的邻居更少, 精确边数可按距离求和. 当 $n\ge 2r+1$ 时:

|E_{\mathrm{local}}|=n(2r+1)-r(r+1). \tag{6}

式 (6) 中, $n(2r+1)$ 假设每行都有完整窗口; $r(r+1)$ 正好扣除左右两端越界的边. 若 $n=8$ , $r=1$ , 理想数量为 $8\times3=24$ , 两端各缺一条边, 所以实际有 $22$ 条. 全连接则有 $64$ 条. 这一例子很小, 但已经能区分「窗口宽度」和「单侧半径」两种容易混用的口径.

一层半径为 $r$ 的局部注意力只能读取相距不超过 $r$ 的位置. 若每层都使用同一窗口, 经过 $L$ 层后, 最远可经逐层中继到距离 $Lr$ 的位置. 对长度 $n\ge2$ 的序列, 当整数半径 $r\ge1$ 时, 两端之间存在信息传播路径所需的最少层数为:

L_{\min}=\left\lceil\frac{n-1}{r}\right\rceil \tag{7}

式 (7) 是拓扑上的精确最短路径长度: 每跳最多跨越 $r$ 个位置, 而连续窗口确实包含实现这条路径的边. 当 $r=0$ 时, 每个位置只能读取自己, 任意多层也无法在不同位置间传递信息. 路径存在以后, 信息能否保真传递还取决于每跳的 softmax 混合、投影、残差和非线性;长路径上的信号可能衰减或被其他内容干扰. 局部窗口保留了相邻结构, 代价是远距离关系从一层直达变成多层传播.

窗口把每层成本限制为 $O(nw)$ , 同时把远距离通信延迟提高到与图路径长度相关. 只比较边数会漏掉这种层数代价.

一个八位置手算。取 $n=8$ , $r=1$ , 只计算位置 $i=4$ 的一个注意力头. 省略位置编码, 并令 $\sqrt{d_h}$ 的缩放已经包含在分数中. 位置 4 只允许访问 $j\in{3,4,5}$ . 假设三个分数分别为 $s_{43}=0$ , $s_{44}=\ln 2$ , $s_{45}=0$ . softmax 分母为:

Z_4=e^0+e^{\ln 2}+e^0=1+2+1=4. \tag{8}

所以三个权重为:

(\alpha_{43},\alpha_{44},\alpha_{45})=\left(\frac14,\frac12,\frac14\right). \tag{9}

令 $v_3=(2,0)$ , $v_4=(0,2)$ , $v_5=(2,2)$ . 逐维代入式 (4):

o_4=\frac14(2,0)+\frac12(0,2)+\frac14(2,2)=(1,1.5). \tag{10}

位置 1, 2, 6, 7, 8 没有参与分母, 也没有参与加权和. 即便位置 8 与位置 4 的内容高度相关, 当前层也没有计算 $q_4^\top k_8$ . 因此静态窗口不会在被屏蔽的远处候选中「发现」相关项; 后续层只能通过已有路径把信息逐步传来.

再看两层传播. 第一层的位置 4 能包含位置 3 至 5 的信息. 第二层的位置 4 分别读取第一层的位置 3, 4, 5; 第一层的位置 3 已经读取位置 2, 第一层的位置 5 已经读取位置 6. 因而第二层的位置 4 最多依赖原始位置 2 至 6. 对称窗口下, 每增加一层, 理论感受野向两侧各扩展 $r$ 个位置. 残差连接使原位置表示继续存在, 但不会生成窗口外的新边.

分块实现与边界效应。逐位置窗口的逻辑布局与 GPU 常见的块运算并不完全相同. 实现通常把序列分成固定大小的 block, 让一个查询 block 访问自己和相邻若干键 block. 这种 block-sparse 布局可能多算一些窗口边缘的配对, 但换来规则矩阵乘法和连续访存. 若每个 block 含 $b$ 个 token, 一个查询 block 访问 $c$ 个键 block, 每行的物理候选上限约为 $cb$ , 不一定等于论文定义的精确 $w$ .

padding 也会改变有效利用率. 长度不能整除 block 大小时, 末块补齐的 token 仍可能占据物理计算槽位, 随后再由 padding mask 清除. 批处理中各样本长度差异越大, 补齐损失越明显. 因此观察显存或吞吐时, 应同时记录真实 token 数, padded token 数, block 大小和窗口配置.

窗口边界还涉及方向. 双向编码任务可用 $|i-j|\le r$ ; causal 生成必须增加 $j\le i$ , 此时邻居集合变成最近的 $r+1$ 个历史位置. 双向窗口每行约 $2r+1$ 个候选, causal 窗口每行最多 $r+1$ 个候选, 两者的边数, 可达路径和任务语义均不同. 把同一个参数名 window_size 放进两个实现, 数值相同也未必代表相同拓扑.

1.2. Longformer: 局部边, dilation 与任务全局边

dilation 扩大跨度但留下采样空隙。 Longformer 的局部窗口可引入 dilation. 设步长为 $\delta$ , 单侧保留 $r$ 个采样位置, 邻居集合可写成:

\mathcal{N}_{\mathrm{dilated}}(i)=\{i+k\delta:k\in\{-r,\ldots,r\}\}\cap\{1,\ldots,n\}. \tag{11}

当 $\delta=1$ 时, 式 (11) 退回连续滑动窗口. 当 $\delta>1$ 时, 每行边数仍至多为 $2r+1$ , 一层覆盖的坐标跨度则从 $r$ 增加到 $r\delta$ . 代价是中间位置可能没有直接边. 例如 $r=2$ , $\delta=3$ , 位置 10 访问 ${4,7,10,13,16}$ , 却不访问位置 9 或 11.

dilation 不能孤立配置. 如果所有层和所有头都使用相同 $\delta=3$ , 按位置编号模 3 分组后, 边只连接同余位置, 图会分裂成三个互不连通的部分, 除非另有连续窗口或全局边连接它们. 混合不同 dilation, 保留部分非 dilation 头, 或周期性插入连续窗口层, 都能恢复局部密集性和跨同余类传播. dilation 增加单层几何跨度, 但连通性取决于各层步长的组合, 不能只看最大覆盖距离.

多层 dilation 的可达位置由步长组合决定. 两层步长分别为 $\delta_1$ 和 $\delta_2$ , 每层单侧索引范围为 $[-r,r]$ , 从位置 $i$ 可到达 $i+k_1\delta_1+k_2\delta_2$ . 若 $\gcd(\delta_1,\delta_2)>1$ 且没有其他边, 仍可能保留周期性断连. 若其中一层 $\delta=1$ , 局部位置至少能进入同一个连通分量, 但有限层数内是否覆盖全文仍取决于 $r$ 与层数.

global attention 改变最短路径。 Longformer 允许选定位置集合 $G$ 作为 global token. 普通局部查询除窗口外可以读取全局位置, 全局位置也可读取整个序列. 对称写法下, 邻居集合为:

\mathcal{N}(i)=\begin{cases} \{1,\ldots,n\},&i\in G,\\ \mathcal{N}_{\mathrm{local}}(i)\cup G,&i\notin G. \end{cases} \tag{12}

设全局位置数为 $g=|G|$ . 局部边约有 $nw$ , 普通位置到全局位置约有 $(n-g)g$ 条边, 全局查询到所有键有 $gn$ 条边. 去掉重复计数后, 总量仍可写成 $O(nw+ng)$ . 当 $g$ 是与 $n$ 无关的小常数时, 总关系数保持线性; 若把大量位置标成全局, $ng$ 会逐渐回到平方级.

全局位置把图直径显著缩短. 普通位置 $a$ 在第一层把信息写入全局位置的表示, 普通位置 $b$ 在下一层读取更新后的全局表示, 因而任意两处通常可通过两层发生间接通信. 同一层的注意力并非顺序更新: $b$ 读取的是该层输入中的全局表示, 不能在同一层先让全局位置吸收 $a$ , 再把新结果传给 $b$ . 这就是为什么跨普通位置的全局中继通常至少需要两层.

global token 不是无条件的信息压缩器. 一个或少数向量要从全文混合信息, softmax 会在大量候选间竞争; 后续位置再从这些向量读取, 可能丢失精细的来源区分. 多头机制可以学习不同投影, 但全局带宽依然由 $g$ , 头数和隐藏维度限制. 增大 $g$ 能提高带宽, 同时按 $ng$ 增加计算和显存.

全局位置由任务语义指定。 Longformer 在分类任务中可让起始分类位置使用 global attention, 使分类表示直接汇总全文. 在问答中, 问题 token 可以设为全局位置, 让文档各处与问题发生直接交互. 这种设计把任务先验写进掩码: 模型不必先通过多层局部传播才把问题带到远端段落.

任务指定也构成边界. 如果真正需要全局通信的位置没有被选中, 静态模式不会自行补边. 若训练时固定某类特殊 token 为全局, 推理输入必须保持相同语义和标记流程. 全局集合还会随样本变化, 但选择规则通常来自 token 类型或任务结构, 并非根据当前层的 QK 分数动态搜索.

从缓存看，编码器前向没有跨请求保存 KV 的必要。一层内部需要局部 K/V 和供全局查询读取的全部 K/V。普通查询只消费窗口块与全局块，全局查询则消费整个序列。Longformer 为局部和全局 attention 使用不同投影参数。按稠密投影核算，单个 $d\to d_h$ 投影作用于全部 $n$ 个位置的乘加量为 $O(ndd_h)$ ；作用于 $g$ 个全局位置则为 $O(gdd_h)$ 。全局查询对全文打分另需 $O(gnd_h)$ 。投影、候选打分和缓存读取是不同成本，应分别计入。

Longformer 的全局性来自被指定的位置和双向全局边, 不是局部窗口自然变成了全连接. 任务收益依赖全局位置是否与信息汇聚需求一致.

2. BigBird: 局部, 随机与全局三类边

块级稀疏图的组成。 BigBird 把序列划分为 block, 再为每个查询 block 分配三类键 block. 局部边连接相邻 block, 保留邻域连续性; 随机边连接若干远处 block, 缩短典型路径并增加跨区域覆盖; 全局边让少数 block 与全部 block 互连. 若每个 block 含 $b$ 个 token, block 数为 $N=\lceil n/b\rceil$ , 每个查询 block 访问 $c$ 个局部 block, $s$ 个随机 block 和 $g_b$ 个全局 block, token 级分数上限约为:

|E|\lesssim N(c+s+g_b)b^2+g_bN b^2. \tag{13}

用 $n\approx Nb$ 代换, 式 (13) 为 $O\bigl(n b(c+s+g_b)\bigr)$ , 只要 $b,c,s,g_b$ 固定就随 $n$ 线性增长. 第二项表示全局查询 block 读取全部键 block; 第一项包含普通查询读取局部, 随机和全局键. 实现中的去重和边界 block 会让精确数略小.

三类边承担不同作用. 局部边稳定保留相邻 token 的结构. 全局边给出确定的短路径和集中汇聚位置. 随机边在不增加很多固定枢纽的情况下分散远距离连接, 降低只依赖少数全局节点的风险. BigBird 用三类边共同提供局部覆盖、短路径与全局通信, 随机性只承担其中的远距捷径. 删除任一类边后, 图的性质和任务偏置都会改变.

静态随机边通常在训练前或执行前按规则生成并复用, 所以仍属于静态稀疏. 边的索引可以随层或头改变, 但选择不依赖当前输入内容. 固定随机种子有利于复现和 kernel 规划; 每步重采样会引入额外随机性, 还可能破坏预先编译或缓存的布局.

十二个 block 的手算。设 $N=12$ , 每个 block 含 $b=4$ 个 token. 暂不处理边界, 每个普通查询 block 访问自己和左右各一个局部 block, 即 $c=3$ ; 再访问 $s=2$ 个随机 block; 另有 $g_b=1$ 个全局 block. 若各类目标均不重复, 一个普通查询 block 读取 $3+2+1=6$ 个键 block, 产生 $6\times4\times4=96$ 个 token 配对.

全连接情况下, 一个查询 block 对全部 12 个键 block产生 $12\times4\times4=192$ 个配对. 普通 block 的候选关系因此减半. 11 个普通查询 block 产生 $11\times96=1056$ 个配对; 一个全局查询 block 读取全部位置, 产生 $192$ 个配对; 合计上限为 $1248$ . 全连接 $48$ 个 token 则有 $48^2=2304$ 个配对. 若局部, 随机和全局集合存在重叠, 去重后的实际配对少于 $1248$ .

取查询 block 5. 局部集合为 ${4,5,6}$ , 随机选择为 ${1,10}$ , 全局 block 为 ${0}$ , 这里 block 编号从 0 到 11. 查询 block 5 能在一层读取 block 10, 但另一个查询 block 的随机边可能完全不同. 两层后, block 5 可继续访问这些目标各自的邻居. 随机边使可达集合更快扩张, 却不保证某个指定远端 block 一层可达; 确定的一层全局访问仍由全局边提供.

这一手算也暴露 block 化的粒度代价. 查询 block 5 一旦选择键 block 10, 通常会计算两个 block 间全部 $4\times4=16$ 个 token 配对. 其中可能只有一个配对有用. 逐 token 稀疏能保留更精确的边, 但硬件执行更不规则. BigBird 选择 block 级布局, 是用一部分块内多算换规则计算.

理论结论的适用条件。 BigBird 论文给出的两个理论结论具有不同前提. 通用逼近定理讨论紧集 $[0,1]^{n\times d}$ 上的连续序列到序列函数, 距离采用 $L_p$ 形式且 $1<p<\infty$ ; 稀疏有向图必须包含以额外节点 0 为中心的 star graph, 即普通节点能连到自身和节点 0, 节点 0 能连到所有普通节点. 定理说对任意误差 $\epsilon>0$ 存在满足误差界的 sparse Transformer, 并未限定现实训练会找到该参数.

图灵完备结论使用 sparse encoder-decoder 构造, 并继承所引用完整 Transformer 证明的任意精度假设. 论文自己指出这项假设不现实: 固定精度模型是有界有限状态机. 因而「BigBird 是图灵完备的」不能缩写成固定深度、有限精度 BigBird checkpoint 能执行任意算法.

论文还给出反向边界: 在标准复杂度假设下, 有一类完整注意力可用 $O(1)$ 层完成的最远向量任务, 任何只有 $\tilde O(n)$ 条边的稀疏注意力都需要 $\tilde\Omega(n)$ 层. 线性边数可以保留渐近表达性, 不表示保留完整注意力的层效率.

随机图性质同样是概率陈述. 当 block 数较少, 每个 block 的随机连接数太低, 或随机边发生较多重复时, 单个样本图可能覆盖不均. 增加随机边能改善连通性, 也线性增加计算. 固定某一次随机布局后, 模型可能学习适应该布局; 改变序列长度, block 划分或随机生成规则可能造成分布变化.

全局 block 的选择也要落到输入格式. 特殊起始 block 可以集中承担全局角色, 但全局 block 内多个 token 的位置和 padding 处理必须固定. 若把所有任务关键 token 分散在普通 block, 它们到全局 block 仍有直接边, 但信息在全局 block 内如何编码受投影和维度限制. 理论上的短路径不会消除有限向量容量.

2.1. 方法选择与系统边界

三种拓扑放在同一组量上比较。

拓扑	每行主要候选	远距离路径	布局规律性	主要代价
连续滑动窗口	$w$	约 $O(n/w)$ 层级传播	高	远距离依赖需要多跳
dilation 窗口	$w$	跨度增大, 取决于步长组合	较高	可能跳过邻近位置或产生断连
Longformer 局部加全局	$w+g$	通常两层经全局位置中继	中等	全局位置带宽与 $ng$ 成本
BigBird 局部加随机加全局	块级 $c+s+g_b$	随机短路径加确定全局路径	中等	随机 gather, 块内多算与复现约束

表中的路径是拓扑上界或典型行为, 不是语义信息无损传递的层数保证. 连续窗口适合强局部结构和规则 kernel. dilation 适合在固定边数下扩大跨度, 前提是其他层或头补足连续性. Longformer 适合能明确指出全局任务位置的长文档编码. BigBird 用随机边分散远距离连接, 在局部性之外增加更广的覆盖.

窗口大小不能只根据最大文档长度决定. 更直接的量是任务所需的最短直接依赖跨度, 网络深度以及可接受的中继层数. 如果证据与决策位置相距 $D$ 个 token, 连续窗口半径为 $r$ , 只靠局部传播至少需要 $\lceil D/r\rceil$ 层. 若模型总层数小于这个值, 对应依赖在拓扑上就无法到达. 加全局边可以缩短路径, 但要求全局位置能承载这条信息.

稀疏拓扑的选择是「边预算如何分配」: 给局部连续性, 给确定的全局带宽, 还是给分散的远距离覆盖. 同样数量的边放在不同位置, 模型能力与执行效率会明显不同.

Prefill, Decode 与 KV cache 要分开看。双向编码器一次处理完整输入, 所有查询同时存在. 滑动窗口能直接减少整层 QK 和 AV 的候选边. causal Prefill 也能使用只看左侧的窗口, 第 $i$ 个查询读取最近 $w$ 个历史键, 总边数约为 $nw$ 而不是 $n(n+1)/2$ . 但每个历史 token 的 K 和 V 是否需要长期保存, 取决于后续 Decode 的窗口规则.

对纯 causal 滑动窗口 Decode, 新 token 只读取最近 $w$ 个 K/V. 超出窗口的历史 K/V 若以后永远不可见, 可以从 cache 中逐出, 单层 KV cache 从随生成长度增长变成上限约 $w$ 个位置. 如果还保留全局 token, 全局位置的 K/V 必须持续驻留; 若规则允许周期性全局位置, 驻留数量会随长度增长. 随机远程边在 Decode 中更麻烦: 未来查询可能访问哪些旧 block 若能预先确定, cache 可按这组需求保留; 若随机布局随未来位置生成, 提前丢弃旧 K/V 可能破坏可达边.

Longformer 与 BigBird 的原始双向结构还允许 token 访问右侧位置. 自回归生成不能使用未来 K/V, 所以必须改成有向 causal 图. 改图以后, 论文中的双向路径长度, 理论构造和原始任务结果不再原样成立. 编码器上的长文档准确率也不能直接当作 Decode 质量证据.

从访存看, Decode 每步查询数通常为 1, 算术密度低. 读取规则 K/V 块比执行不规则随机 gather 更容易利用带宽. 因而某个拓扑在 Prefill 节省大量 FLOPs, 不代表 Decode 同比例加速. 应分别测量 Prefill 延迟, Decode 每 token 延迟, cache 容量与实际显存带宽.

常见失效模式与可检查量。最常见的失效是逻辑稀疏成立, 任务依赖或执行路径却不匹配. 窗口太小, 证据在有限层数内到不了决策位置; 窗口太大, 候选边接近全连接, sparse kernel 的额外开销失去意义. 全局位置太少, 多种远距离信息争用有限表示; 全局位置太多, $ng$ 项侵蚀线性优势. 随机边太少会覆盖不稳, 太多则增加 gather 和块内多算.

训练阶段应记录每层真实边数, padding 后边数, 各类边的重复率, 全局位置数和梯度稳定性. 仅记录名义窗口大小不足以解释显存. 对 block-sparse 实现, 还应记录 block 占用率: 被计算的 block 内有多少 token 配对后来被更细的 mask 清除. 占用率过低表示物理计算远高于逻辑边数.

评测阶段可以按依赖距离分桶, 比较答案所需证据与输出位置的间距. 若准确率在某个距离后明显下降, 再对照式 (7) 的层数可达范围, 能区分拓扑不可达与模型虽可达但未学会. 对 global attention, 可改变全局位置集合做消融; 对随机边, 应报告多个随机种子或固定布局, 避免把一次图采样当作稳定结论.

部署阶段要检查 kernel 是否真正跳过掩码外配对, 是否因序列长度回退到稠密实现, block 大小是否与硬件和批大小匹配. 峰值显存, 吞吐和端到端延迟都要测, 因为稀疏注意力只改变模型的一部分. 前馈网络, 归一化, 投影和通信可能在注意力加速后成为主要耗时.

静态拓扑明确丢掉了什么。静态拓扑丢掉的是输入驱动的候选发现. 对于掩码外的 $(i,j)$ , 系统既不计算分数, 也无法知道该配对本来会得到多高权重. 内容相关权重只能在预设邻域内部竞争. 动态稀疏或检索式方法会尝试根据内容选择远端键, 代价是选择器, 索引构建, 路由稳定性以及不规则执行.

静态模式的优势也来自这项限制. 邻居索引可预先生成, 训练和推理使用相同布局, 计算量上界清楚, block 规划较稳定. 连续窗口甚至不需要显式保存每条边的索引, 只需窗口参数和位置偏移. BigBird 随机边需要保存或可复现地生成索引, 但仍不依赖当前隐藏状态.

静态稀疏提供的是可预测的计算预算, 不是对所有长距离关系的免费保留. Longformer 用少量任务全局位置补局部窗口的路径长度, BigBird 再加入随机边扩展远距离覆盖. 两种设计都要求把数据中的依赖结构与图中的可达结构对齐.

从依赖距离反推窗口和全局预算。配置窗口时可以先从模型深度与依赖距离反推, 而不是先挑一个整齐的窗口数. 设模型有 $L$ 层, 任务中大部分需要直接组合的信息相距不超过 $D$ 个位置. 如果完全依靠连续局部边, 单侧半径至少要满足 $Lr\ge D$ , 即:

r\ge\left\lceil\frac{D}{L}\right\rceil. \tag{14}

例如模型有 $L=12$ 层, 需要让相距 $D=900$ 的位置在拓扑上可达, 则 $r$ 至少为 $75$ , 双向内部窗口宽度约为 $151$ . 对长度 $n=8192$ 的序列, 忽略边界时每层约计算 $8192\times151=1{,}236{,}992$ 条局部边; 全连接为 $8192^2=67{,}108{,}864$ 条边. 名义边数约降为全连接的 $1.84%$ . 这个比例只说明候选配对数量, 实际速度仍受 block 填充和其他子层限制.

式 (14) 只是可达条件. 如果依赖要经过 12 次混合才到达, 优化可能比一条短路径困难. 加入 $g=4$ 个全局位置后, 普通位置增加至多约 $4n$ 条读取全局的边, 全局查询增加约 $4n$ 条读取全文的边, 总增量数量级约为 $8n=65{,}536$ . 相比上面的局部边数, 这个增量不大, 任意两个普通位置却能在两层内经全局位置建立路径. 收益是否出现, 取决于全局向量能否保留任务所需细节, 因而还要测量不同 $g$ 下的任务曲线, 不能仅依据图直径决定.

对依赖距离分布有长尾的任务, 可以把预算拆成两部分. 连续窗口覆盖高频的中短距离依赖, 全局或随机边处理少量长距离依赖. 设每行总边预算为 $m$ , 分给局部窗口的数量为 $w$ , 分给远程边的数量为 $m-w$ . 增大 $w$ 会提高邻域分辨率, 却减少远程覆盖; 减小 $w$ 则可能破坏短语, 句子或局部结构. 最合理的分配要用真实数据中的依赖距离, block 占用率和任务消融共同确定.

层间也不必使用完全相同的分配. 底层可用较密的连续窗口建立局部表示, 中层加入 dilation 或随机边扩大覆盖, 高层使用任务全局位置集中汇聚. 这种安排仍是静态拓扑, 因为每层边型在读取输入前已经确定. 但分析可达性时必须把各层图按顺序复合: 只看任意一层的窗口或随机度数, 无法推出最终哪些原始位置能够影响输出.

稀疏等价检查要比较数值而非名称。实现稀疏 attention 时, 最直接的正确性检查是在小序列上构造同一张布尔掩码, 分别运行稠密参考实现和 sparse kernel. 两者应使用相同的 Q, K, V, 相同的缩放因子, 相同的 padding 与 causal 方向. 对允许位置, 稠密参考把掩码外 logits 设为 $-\infty$ ; sparse kernel 只生成允许位置的 logits. 比较输出和梯度时要给出浮点容差, 并单独覆盖序列两端, 不整除 block 的末块, 全局位置与随机边重叠等情况.

softmax 的归一化集合必须一致. 常见偏差来自 block kernel 先计算整块, 却没有把块内不允许的元素清除; 或全局边与局部边重复后, 同一个键被放入分母两次. 重复边若没有去重, 式 (3) 的概率空间已经改变. 另一个偏差来自全掩码行: 若某个 padding 查询没有任何允许键, 直接对全 $-\infty$ 做 softmax 会产生非数. 实现需要跳过该行或明确输出零, 同时保证反向传播不污染其他位置.

数值等价通过后再测性能. 测量应固定模型维度, 头数, dtype, batch 和序列长度, 分别报告投影, 注意力核心与整层时间. 只测注意力核心能展示 kernel 上限, 整层时间才能回答实际收益. 还应做长度扫描: 短序列区域可能由调度开销主导, 超过某个长度后稀疏布局才开始占优. 交叉点会随硬件, 编译器, block 大小和窗口变化, 不能从复杂度符号中读出.

内存测量要区分已分配, 已保留和峰值激活. 框架的缓存分配器可能保留先前申请的显存, 使任务管理器读数看不出逻辑中间量下降. 更可靠的做法是在相同进程状态下重置峰值计数, 完成一次前向或训练步后读取峰值, 并同时记录实际边数. 若边数下降而注意力核心时间与峰值都不变, 通常意味着实现仍走稠密路径, block 填充吞掉收益, 或瓶颈已经转移到投影和前馈网络.

随机静态边还需要验证可复现性. 训练时若每步重采样, 它接近一种结构正则化; 推理固定一张图, 训练和部署分布会不同. 如果训练、评测都固定随机图, 模型可能适应特定捷径, 更换种子后质量下降. 因此配置里要保存随机种子、层号与 head号到邻接表的映射, 复现实验则至少比较若干独立种子.

分布式切分不能各 rank随意生成局部随机边. 同一逻辑 head迁移到另一 rank后, 邻接关系应保持一致; 序列并行下还要把全局 token位置映射到持有它的设备. 若随机边跨设备, 理论边数虽未变化, 通信会从规则 all-to-all变成按索引 gather. 性能报告要把这部分字节计入, 否则单卡结论无法解释集群训练.

2.2. 从拓扑定义走到可运行实现

复杂度与生成质量不是同一个问题。 Sparse Transformer 给出 $O(n\sqrt n)$ 的特定分解, Longformer 组合局部边与任务全局边, BigBird 则使用局部、随机和全局三类边。把这些定义展开成逐行邻接集合, 就能重新计算边数和路径距离, 但这些结构量不会直接给出下游任务分数。

Longformer 与 BigBird 的论文实验主要建立长文档编码证据。将这些拓扑用于 causal decode 属于结构推演, 双向编码结果不能直接证明生成质量。BigBird 的理论定理也按 star graph、函数域、 $L_p$ 误差和任意精度等条件陈述，没有外推到任意随机 mask。

代码路径决定真实交叉点。 Longformer 作者仓库区分 TVM、自带 $n^2$ 和 sliding-chunks 三种注意力路径，并说明 sliding-chunks 版本内存更高且不支持 dilation 与 autoregressive attention。BigBird 作者仓库区分 original_full、simulated_sparse 与 block_sparse，当前 block 配置使用三个窗口块、两个全局块和两个随机块，并受静态 tensor shape 约束。换用另一套 kernel 或布局后, 这些限制与性能交叉点都可能变化。

官方代码还建议长度小于 1024 时使用完整注意力，因为稀疏实现没有收益。这是该实现的工程建议，不是「稀疏算法在 1024 以下必然更慢」的普遍定理。硬件、block 与 kernel 改变后，交叉点需要重新测量。

2.3. 多层图的可达关系

第 $\ell$ 层邻接矩阵记为 $A^{(\ell)}$ ，约定 $A^{(\ell)}_{ij}=1$ 表示位置 $i$ 可以读取位置 $j$ 。残差连接让每个位置保留自身状态，可把单位阵加入邻接。经过 $L$ 层的结构可达矩阵为

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

矩阵乘法在这里按布尔半环理解：乘法表示路径连接，加法表示至少存在一条路径。 $R^{(L)}_{ij}=1$ 是位置 $j$ 影响位置 $i$ 的必要结构条件。它没有说明权重有多大，也没有说明有限维中间状态能否保存所需细节。

滑动窗口的精确可达距离。因果窗口宽度为 $w$ 时，第 $i$ 个位置在一层内读取

N(i)=\{j:\max(1,i-w+1)\le j\le i\}.

一层最多向过去跨越 $w-1$ 。经过 $L$ 层，最远可达位置为 $i-L(w-1)$ ，有效感受野宽度

W_L=1+L(w-1),

直到被序列开头截断。这个结果可以用归纳证明：第 $L$ 层最早读取的中间位置为 $i-w+1$ ，该位置在前 $L-1$ 层最早覆盖 $i-w+1-(L-1)(w-1)=i-L(w-1)$ 。

若 $w=4096,L=32$ ，结构感受野为 $1+32\times4095=131041$ ，比 $128\times1024=131072$ 少 31 个位置。靠近序列末位的早期证据在这个范围内图上可达，却需要经过最多 32 次状态搬运。每一步都要决定保留什么，且中间表示维度固定，任务能力还要单独测量。

Block attention 与 sliding window 不等价。互不重叠的 block attention 让每个 query 只读取所在块的历史。无论叠多少层，若所有层边界相同，信息都无法跨块，邻接矩阵是块对角结构。Sliding window 在块边界处仍保留跨界边，多层感受野持续扩张。

令组长为 $w$ 。位置 $w+1$ 在 block attention 中无法读取位置 $w$ ，尽管两者相邻；在 sliding window 中必然相连。平均边数可以接近，图连通性完全不同。将窗口 kernel 简化为独立分块若没有 shifted layer 或全局边，改变了模型定义。

若相邻层把块边界平移 $w/2$ ，组间可以交换信息。S²-Attn 就利用这类平移在微调时构造跨组路径。路径扩张速度与平移规则、head 分配和层数有关，不能继续用固定块对角矩阵分析。

变化窗口的精确上界与构造。设第 $\ell$ 层的因果窗口允许当前位置读取自己以及前方 $w_\ell-1$ 个位置。对任意从位置 $i$ 出发的反向路径，第 $\ell$ 步最多向前移动 $w_\ell-1$ ，所以经过 $L$ 层后，最远只能到达

i-\sum_{\ell=1}^{L}(w_\ell-1).

这先给出一个上界。它也确实能够达到：第一层取允许集合中最远的 key，第二层再从该位置取最远 key，如此逐层走满窗口。于是忽略序列左端截断时，位置 $i$ 在 $L$ 层后的精确感受野长度为

R_L=1+\sum_{\ell=1}^{L}(w_\ell-1).

这个结论比笼统的「感受野随深度线性增长」多了一层用途。只要给出依赖距离 $d$ ，就能检查 $d\le R_L-1$ 是否成立；还能反推至少需要多少层。固定窗口 $w$ 时，最小层数是 $\lceil d/(w-1)\rceil$ 。如果证据距离为 32K、窗口为 2K，至少要经过 17 层注意力传播，才可能把最远证据送到 query。这里说的是结构下界，不保证模型真的学会连续中继。

窗口按层变化时，总窗口和决定最大跨度，窗口出现的先后却决定中间表示。以三层窗口 $(2,2,5)$ 与 $(5,2,2)$ 为例，最终都覆盖前方六个位置。前者的末层 query 才能直接读取较远位置的第二层表示；后者的第一层 query 就读取较远位置的原始表示，随后两层在这些已聚合表示上继续局部加工。最远证据在两种安排中都可沿三层路径进入最终输出，但经过的中间位置、非线性变换与聚合顺序不同。

双向窗口也可同样推导。若第 $\ell$ 层向左、向右分别允许 $a_\ell,b_\ell$ 个位置，则忽略边界后，可达区间为

\left[i-\sum_{\ell=1}^{L}a_\ell,\ i+\sum_{\ell=1}^{L}b_\ell\right].

边界处的区间被截断，但不会凭空向另一侧补齐。因此，固定总入度的实现若在开头把缺少的左邻居补成更多右邻居，它已经改变了拓扑，而不只是做边界优化。对于 causal 模型更不能补未来边，真实边数必须保留三角形修正项。

偏移集合给出比最大跨度更强的判据。窗口拓扑的允许偏移是连续集合，因此区间内每个距离都可达。Stride 和 dilation 的偏移并不连续，只看最远偏移会高估覆盖。把第 $\ell$ 层的非负因果偏移集合记为 $D_\ell$ ，多层可达距离集合满足递推

S_0=\{0\},\qquad S_\ell=\{s+d:s\in S_{\ell-1},d\in D_\ell\}.

这个递推可以用 bitset 精确计算，不需要枚举所有路径。若每层偏移都是 ${0,4,8}$ ，无论叠多少层都只能到达 4 的倍数；最远距离持续增加，三个其余数类依旧为空。若某一层加入偏移 1，只能让最终集合多出一种组合位置；要填满整个区间，需要偏移集合在层间形成足够丰富的和集。

最大公约数是必要条件，却不是充分条件。偏移 ${0,6,10}$ 的最大公约数为 2，奇数必然不可达；加入 15 后总体最大公约数变为 1，但在有限层数下仍有大量小距离无法组合出来。经典硬币问题只讨论无限次使用偏移，Transformer 每层至多选一次该层允许偏移，约束更强。正确检查方式仍是按真实层表计算 $S_L$ 。

多头结构还要先决定怎样组合偏移。每个 head 的结果在层末混入同一位置表示，因此下一层可以从任一 head 已带回的信息继续传播；可以把一层的有效可达偏移近似写成各 head 偏移集合的并集。这个并集只能用于跨层可达分析，不能用来声称某个 head 在同一次 softmax 中比较了全部候选。若输出投影被分组或某些通道不互通，还需把通道状态加入图节点，普通 token 图会再次高估可达性。

3. 图直径、扩张性与瓶颈

无向图直径是任意节点对最短路径的最大值；因果 attention 是有向图，只允许过去流向未来，应使用有向可达距离。窗口图从位置 1 到位置 $n$ 的距离约为 $\lceil(n-1)/(w-1)\rceil$ 。加入少量跨距边可显著缩短平均距离，但最坏节点是否受益取决于边的覆盖。

随机边常被用来构造小世界效应。每个节点保留局部邻居并增加常数条随机远边时，典型路径可能从线性降到对数级。对 causal 图，随机边必须指向过去；早期节点无法从未来获得信息，但后期 query 可以沿反向时间方向快速跳到远处。随机采样的方差意味着某些区间仍可能形成稀疏瓶颈，所以要跨种子测量最短路径与割边。

扩张边界衡量局部团是否被困住。对节点集合 $S$ ，边界 $\partial S$ 是从 $S$ 指向外部或从外部进入 $S$ 的边，具体方向按信息流定义。无向近似中的边扩张率可写为

h(G)=\min_{0<|S|\le |V|/2} \frac{|\partial S|}{|S|}.

$h(G)$ 小表示存在一个大子集只有很少跨界边，信息容易被困在局部团。固定 block attention 的块边界扩张为零；滑动窗口的跨界边集中在边界附近，集合越长，单位节点边界越小；随机边提高大集合跨界连接的概率。

扩张率不会直接给语言模型准确率。它描述图的混合能力，没有考虑边权学习、位置方向和 token 内容。它仍能解释两张边数相同的图为何多层覆盖不同，并为随机种子检查提供比平均路径更严格的结构量。

全局节点把直径缩短到常数。若有一个全局节点 $g$ 同时读取所有 token，且所有 token 下一层能读取 $g$ ，任意位置 $j$ 的信息可经 $j\to g\to i$ 两跳到达 $i$ 。编码器中的双向 global attention 很容易满足这一路径。因果生成模型必须尊重时间：位于序列开头的固定 sink 无法读取后来的 token，可以成为后续 query 持续可读的锚点，却不能充当汇总后来内容的中继。

可以让每段末尾的摘要 token 读取本段，再让后续位置读取这些摘要。这样全局节点随时间生成，保持因果性；摘要槽数量和维度限制了可保存信息。ETC 使用 global-local attention 编码结构化输入，Longformer 的任务全局 token 常由问题或特殊位置指定，BigBird 理论则强调常数个 global token 对表达能力的作用。三者的「global」信息方向和任务接口并不完全相同。

割、边不相交路径与故障余量。最短路径只看最快的一条路，无法区分「只有一条路」和「有一百条同样短的路」。对源位置集合 $A$ 与目标位置集合 $B$ ，如果删除节点集合 $C$ 后，所有从 $A$ 到 $B$ 的有向路径都消失，那么 $C$ 是一个顶点割。所有跨区信息都必须经过 $C$ 中的表示。Menger 定理在普通图上把最小顶点割大小与内部顶点不相交路径的最大条数联系起来，这给稀疏 attention 一个很直观的检查量：远距关系有多少条不共享中间 token 的通道。

局部窗口跨越一个人为文档边界时，通常有多条不同边连接左右两侧，边界附近多个 token 都能承担中继。一个单独 global token 虽然把任意两段路径缩成两跳，却把割缩到一个节点。前者路径较长、冗余较多；后者路径极短、容量和故障集中。把二者混合，往往比只追求最短直径更稳。

不相交路径也不能直接等同于可传输的实数维数。每个节点是 $d$ 维向量，attention 还要经过共享投影、softmax 与残差；多条路径可能学习到相同内容。不过，如果两条所谓独立路径在下一层立即汇聚到同一个摘要槽，它们只在汇聚前独立。分析应在逐层展开的计算图上进行，把同一 token 在不同层视为不同节点，否则会把残差和时序折叠掉。

一个可复算的压力测试是逐个关闭中间节点。先计算从证据到 query 的最小割候选，再在不重新训练的情况下屏蔽其中一个节点或一组边。若单点屏蔽让准确率接近随机，而替代拓扑在同等边数下缓慢下降，差异来自路径冗余。随后重新训练带屏蔽的模型，能判断网络是否可以迁移到备用路径。前者测当前权重依赖，后者测拓扑可塑性。

随机边常提高平均冗余，但保证形式要说清楚。每个 query 抽到若干远边，不代表任意指定证据都有多条短路径；高概率连通是对随机图事件或节点对分布的陈述。关键控制信息若必须确定到达，应由规则边或任务 global 兜底，不能把期望上的小直径当成逐样本保证。

图对称性与位置辨识。规则拓扑往往具有平移或置换对称。无限滑动窗口中，把所有位置整体平移，邻接关系不变；相同大小的独立 block 之间也近似同构。若输入内容相同且没有任何位置编码，处于对称位置的 token 会经历相同计算，模型无法仅靠拓扑区分「第一块」和「第十块」。静态图提供相对邻接，并不自动提供绝对位置。

用图自同构描述更精确。若存在一个节点置换 $\pi$ ，使边集合在置换后不变，并且对应节点的输入表示也相同，那么共享参数的消息传播会保持这种等价关系。位置编码、边界截断、特殊 global token 与不同层 mask 都能打破部分对称。它们打破的是哪一种对称，决定模型能分辨哪些位置。

绝对位置编码可给每个位置唯一身份，但长度外推时可能没有训练过的绝对索引。旋转或相对位置机制更强调距离；若两个候选 key 与 query 的相对距离相同、内容也相同，而拓扑没有额外结构，二者仍难区分。文档段落 ID、层级节点和边类型 embedding 可以补充结构身份，同时也把模型绑定到解析规则。

边界是最常见的隐式锚点。窗口中的开头 token 入度较小，模型可通过多层传播感知离开头的距离；固定 block 的块首也有重复边界信号。这种位置线索并不一定符合任务语义，反而可能让模型记住训练长度或块内槽位。把同一内容整体平移、改变左侧无关前缀长度，再观察答案是否变化，可以检验模型使用的是内容关系还是拓扑坐标。

图对称还解释了为什么固定随机边会带来额外能力。固定随机图为不同位置赋予近似唯一的邻接指纹，间接打破平移对称；换随机种子后，指纹随之变化。若模型依赖这些指纹而不是稳健的远距传播，更换种子就会显著下降。因此随机种子鲁棒性也在测一种位置依赖。