跳转至

CRISP: Cliff-awaRe Input-adaptive Sparse Prefilling with Structural-Mass-Motivated Routing

会议: EMNLP 2026
论文: ACL Anthology
代码: https://github.com/huyhuunguyen/CRISP
领域: 模型压缩
关键词: 稀疏注意力 / 大模型推理 / 注意力汇聚 / 动态路由 / 长上下文预填充

一句话总结

针对长上下文大语言模型自注意力预填充阶段计算开销巨大的瓶颈,CRISP 指出传统动态路由在 JSD 计算上的多余矩阵开销,并形式化证明了固定累积覆盖阈值在后 Softmax 质量悬崖下面临的 \(O(n)\) 噪声累积与汇聚折叠失效,提出基于物理锚点的常数级路由指标 \(C_{\text{struct}}\) 与动态剥离汇聚质量的本底噪声阈值,在 512k 极长序列下取得高达 5.30 倍注意力加速且全面超越此前稀疏预填充基线。

研究背景与动机

大语言模型在长上下文问答、长文档分析以及多轮交互中的推理需求日益迫切,但预填充(Prefilling)阶段自注意力矩阵计算的时间与显存复杂度随输入序列长度 \(n\) 呈二次方增长,成为制约模型吞吐与响应延迟的主要瓶颈。以 FlexPrefill 为代表的先进动态稀疏注意力方法通过在线评估代表性查询块,将注意力头动态划分为两类:结构高度集中的竖直-斜线头(Vertical-Slash, VS)以及注意力相对弥散的池化估计头(Pooled-Estimation, PE),随后为 VS 头在列方向与对角线方向上按累积概率质量达到预设阈值 \(\gamma\)(如 0.95)进行动态分块截断。

然而,现有的动态路由与分块截断机制在理论基础和系统实现上存在着严重的结构性缺陷。在路由层面,FlexPrefill 采用查询与键的双重池化后 Softmax 估计与单查询 Softmax 均值之间的 Jensen-Shannon 散度(JSD)作为判定集中程度的间接代理,这一过程迫使每个注意力头额外计算一次 \(O(nd/b)\) 的池化矩阵乘法以及随后的两次对数与规约运算,引入了不可忽略的在线延迟。在截断层面,自回归 Transformer 的 Softmax 归一化在注意力头内部催生了极端的质量分层:最初始的若干 Token(注意力汇聚 Attention Sinks)往往吸纳超过 90% 的绝大部分注意力权重,中间是承载语义的任务关键块,尾部则是随序列长度变长而单 Token 权重衰减至 \(O(1/n)\) 的极小本底噪声。这种陡峭的断崖分布使得累积覆盖阈值 \(\gamma\) 陷入根本性的两难失效:当注意力汇聚吸收质量超过 \(\gamma\) 时,选择在触达任何关键任务语义前便早熟终止(汇聚折叠,Sink-Only Collapse);当汇聚质量不足 \(\gamma\) 时,为了凑齐剩余的残差质量,算法不得不横跨质量悬崖,向后收拢大量本底噪声块,在长上下文中必然累积 \(O(n)\) 的垃圾 Token(噪声累积,Residual Noise Accumulation)。

本文的切入角度在于:首先,集中头必然将注意力质量倾注在具有明确几何位置的先验结构上(注意力汇聚与局部因果窗口),其集中度可以直接在现成的代理注意力图对应位置切片读取,无需任何间接散度度量;其次,对抗质量悬崖的关键不在于追求固定的累积百分比,而在于精确锚定有效语义与本底噪声的临界地平面。核心 idea:抛弃间接 JSD 散度,直接利用注意力汇聚与局部窗口切片质量 \(C_{\text{struct}}\) 实现 \(O(1)\) 常数开销的确定性路由,并在 VS 路径上建立剔除首尾锚点质量后的自适应本底噪声地平面阈值,从根本上杜绝超长上下文下 \(O(n)\) 噪声块的累积与汇聚折叠。

方法详解

整体框架

CRISP 整体由在线模式搜索(Pattern Search)和双路径稀疏索引构建(VS/PE Index Selection)两大部分组成。在每个注意力头开始完整的全序列计算前,算法首先截取序列末端大小为 \(b=128\) 的代表性查询块 \(\hat{Q}\),计算其与全体键矩阵 \(K\) 的代理注意力图 \(\hat{A} = \text{Softmax}(\hat{Q} K^\top / \sqrt{d})\)。随后,模型直接提取 \(\hat{A}\) 中首部注意力汇聚区域与尾部局部因果窗口区域的注意力质量均值 \(C_{\text{struct}}\);当 \(C_{\text{struct}} \ge \tau_{\text{proxy}}\) 时将该头路由至 VS 路径,执行基于本底噪声地平面的汇聚感知阈值筛选;当 \(C_{\text{struct}} < \tau_{\text{proxy}}\) 时则进入 PE 路径,保留无陡峭悬崖头所需的全局池化与累积截断。最终两路生成的离散块索引集合用于执行硬件友好的分块稀疏注意力计算。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入 Q, K, V & 采样查询块 Q_hat"] --> B["代理注意力矩阵 A_hat 计算<br/>Softmax(Q_hat * K^T / sqrt(d))"]
    B --> C["基于锚点质量的直接结构路由<br/>计算 Cstruct 均值切片"]
    C -->|Cstruct >= tau_proxy| D["基于本底噪声地平面的汇聚感知阈值<br/>剔除汇聚与局部后算 mu 并以 alpha*mu 截断"]
    C -->|Cstruct < tau_proxy| E["高熵弥散头的保底累积松弛<br/>全局池化并保留 gamma 累积覆盖"]
    D --> F["生成分块稀疏索引集合 S<br/>Sv 并集 Ss 并集 锚点块"]
    E --> F
    F --> G["分块稀疏注意力算子输出<br/>A(Q, K, V, S)"]

关键设计

1. 基于锚点质量的直接结构路由(Cstruct):消除二次池化与散度计算的常数级路由

先前的 JSD 路由机制为了判断注意力分布是偏向低熵结构化还是高熵均匀化,人为构造了一个池化粗粒度注意力分布 \(\bar{a}\) 并与细粒度均值 \(\hat{a}\) 进行相对熵比对。这一计算过程不仅必须对全量键矩阵 \(K\) 重新进行一次降采样池化矩阵乘法,还带来了对数和归约的前向开销。

CRISP 从现代因果大模型的结构归纳偏置出发,揭示了低熵头之所以结构化,其本质就在于注意力的集中必定落脚于模型固有的结构化锚点——即初始若干 Token 的注意力汇聚(Attention Sinks, \(w_{\text{sink}}=128\))以及序列末端临近的局部因果窗口(Local Recency, \(w_{\text{local}}=128\))。因此,与其借由 JSD 迂回探测质量分散度,不如直接测量这些物理锚点上聚集的总质量: $\(C_{\text{struct}} = \frac{1}{|\hat{Q}|} \sum_{i \in \hat{Q}} \sum_{j \in S_{\text{anchor}}} \hat{A}[i, j]\)$ 其中 \(S_{\text{anchor}}\) 严格等于第 \(0\) 块和第 \(N_b - 1\) 块对应的 Token 索引。因为 \(\hat{A}\) 本就是后续分块索引筛选所必需的先验输入,计算 \(C_{\text{struct}}\) 仅需对已生成的矩阵进行常数大小切片求和,计算复杂度为 \(O(w_{\text{sink}} + w_{\text{local}})\),与总序列长度 \(n\) 完全解耦。实测表明,在 Llama-3.1-8B 和 Qwen2.5-7B 上,注意力头 Top-1 质量块落在锚点区域的概率分别高达 91.3% 和 98.3%,且 \(C_{\text{struct}}\) 的硬判决与 JSD 的路由重合度达到 94.0% 和 88.1%,以近乎零的额外算力开销完美平替了 JSD。

2. 基于本底噪声地平面的汇聚感知阈值(Sink-Aware Thresholding):破解后Softmax质量悬崖与O(n)噪声累积

在 VS 头中,Softmax 归一化导致注意力值呈现断崖式阶跃分布。对于具有 \(k\) 个信号 Token(包含汇聚与关键检索信息,logit 值为 \(z\))以及 \(n-k\) 个非关键背景 Token(logit 值为 \(z-\Delta\))的序列,当 \(n \gg k \cdot e^{\Delta}\) 时,每个背景 Token 分配到的注意力质量近似为 \(\epsilon \approx 1/n\)。若强行采用累积阈值 \(\sum a_j \ge \gamma\),一旦出现 \(a_{\text{sink}} \ge \gamma\)(例如汇聚块单块占据 0.93 的权重),挑选集合直接满足条件而提前中止,导致排在后面的 8 个关键任务语义块完全遗漏(汇聚折叠);反之,一旦 \(a_{\text{sink}} + a_{\text{important}} < \gamma\),算法为了弥补极小的残差质量 \(\gamma_{\text{residual}}\),必须持续向下收集权重为 \(\epsilon\) 的背景 Token,收集的垃圾块数量为 \(N_{\text{garbage}} = \gamma_{\text{residual}} / \epsilon \approx \gamma_{\text{residual}} \cdot n\),带来致命的 \(O(n)\) 线性噪声扩张。

CRISP 彻底抛弃了累积比例准则,转向自适应的本底噪声地平面(Noise Floor)截断。将序列按 \(B=128\) 分为 \(N_b = \lceil n/B \rceil\) 个块,由于第 \(0\) 块(汇聚)与第 \(N_b-1\) 块(局部)作为全局语义锚点是无条件保留的,算法首先将其质量贡献剔除,计算其余 \(N_b - 2\) 个非锚点块的平均残差质量,将其定义为物理本底噪声地平面 \(\mu_d\): $\(\mu_d = \frac{\max(1 - p_d[0] - p_d[N_b-1], 0)}{N_b - 2}, \quad d \in \{v, s\}\)$ 其中 \(p_d\) 分别代表代理注意力图在列求和(Vertical)与对角线求和(Slash)方向上的归一化分块质量。随后,CRISP 制定了严格基于信噪比的分块筛选准则: $\(\text{block } j \text{ is important} \iff p_d[j] > \alpha \cdot \mu_d\)$ 当 \(\alpha=1.0\) 时,该阈值在数学上严格对应于“非锚点块的平均残留质量”——任何高于该均值的块必然携带超出纯背景噪声的有效语义信号,无需任何超参数人工微调即可实现零样本免校准。当汇聚质量异常庞大时,分子上的残差自然收敛,\(\mu_d\) 相应下调,保护细微的关键语义块不被漏选;而在长上下文中,\(\mu_d\) 随着 \(N_b\) 的增加以 \(O(1/n)\) 自然衰减,严格拦截了所有低于本底均值的垃圾块,一举根除了 \(O(n)\) 噪声累积。

3. 高熵弥散头的保底累积松弛(Diffuse-Path Relaxation):保持高熵分布的紧凑覆盖

注意力头并非全都是低熵集中型。对于被 \(C_{\text{struct}} < \tau_{\text{proxy}}\) 划入 PE 路径的高熵注意力头而言,注意力的概率质量在全序列上单调、平滑且弥散地铺展,其 Top-1 块通常仅占百分之几的微小比重,且前 50 个块累积质量甚至不足 80%,完全不存在断崖式阶跃。在此类平滑分布下,平均值地平面无法提供明确的信噪分界线,而传统累积覆盖准则在平滑曲线上反而能够平稳地选出最具代表性的紧凑子集,且不会踏入近零的深层本底噪声区域。CRISP 在架构上明确保持了这一路径的解耦性:仅对 VS 头应用本底噪声阈值,而在 PE 头中保留全局池化与基于 \(\gamma\) 的累积覆盖筛选(算法 4),使得系统既能对集中头进行激进的高信噪比去噪,又不会牺牲高熵弥散头必要的语义上下文广度。

实验关键数据

主实验

评估基于 Meta-Llama-3.1-8B-Instruct 与 Qwen2.5-7B-Instruct,在长上下文基准 InfiniteBench(131K 截断)、RULER(4K–131K 上下文检索与聚合)以及 LongBench(4K–16K 真实多任务)上进行系统评测。基线包括完整精确稠密注意力 FlashAttention(FA)、离线固定模式稀疏方法 MInference,以及当前最强的动态稀疏预填充基线 FlexPrefill(FP \(\gamma=0.95\) 及更高覆盖率探究配置 \(\gamma=0.97\))。

基准评测集 评估模型 FlashAttn (FA) MInference FlexPrefill (γ=0.95) FlexPrefill (γ=0.97) CRISP (α=1.0, 推荐) CRISP (α=1.25, 速度)
InfiniteBench (131K) Llama-3.1-8B 48.6 36.5 47.4 47.3 48.7 (↑FA) 48.0
Qwen2.5-7B 24.0 25.1 25.5 26.7 28.7 (↑FA) 28.4
RULER (4K–131K) Llama-3.1-8B 89.02 86.14 89.22 89.14 88.82 88.62
Qwen2.5-7B 75.84 72.44 75.52 75.80 76.20 (↑FA) 75.80
LongBench (4K–16K) Llama-3.1-8B 48.82 41.40 46.92 47.12 47.77 46.92
Qwen2.5-7B 48.80 38.95 45.57 46.45 47.23 46.76

在更具代表性的长文本关键信息检索任务中,CRISP 彻底扭转了 FlexPrefill 因汇聚折叠导致的严重失分,展现了极其惊人的恢复幅度:

关键检索子任务 所属评测集 Llama-3.1-8B 相比 FP 0.95 增益 Qwen2.5-7B 相比 FP 0.95 增益
KV Retrieval InfiniteBench +17.8 pp (61.6 vs 43.8) —* (基线接近零)
Passkey Retrieval InfiniteBench +0.2 pp (98.8 vs 98.6) +28.0 pp (50.3 vs 22.4)
Passage Retrieval (En) LongBench +12.50 pp (94.50 vs 82.00) +13.50 pp (88.50 vs 75.00)
Passage Retrieval (Zh) LongBench +3.16 pp (93.83 vs 90.67) +4.50 pp (89.50 vs 85.00)
RULER 65K RULER +2.65 pp (86.06 vs 83.41) +1.45 pp (67.79 vs 66.34)

消融实验

消融实验深入验证了两个核心组件(\(C_{\text{struct}}\) 路由与汇聚感知阈值筛选)在不同模型结构上的独立及协同贡献(单张 NVIDIA H100 80GB 测试):

消融配置方案 路由策略 VS 截断准则 Llama IB Llama LB Llama RULER Qwen IB Qwen LB Qwen RULER
FlexPrefill (基线) JSD 散度 \(\gamma\)-cumsum 累积 (0.95) 47.4 46.92 89.22 25.5 45.57 75.52
Abl. 1 (仅 Cstruct) \(C_{\text{struct}}\) 锚点 \(\gamma\)-cumsum 累积 (0.95) 45.2 (-2.2) 47.14 87.82 (-1.4) 29.7 45.93 74.92
Abl. 2 (仅 Sink-Aware) JSD 散度 汇聚感知地平面 (\(\alpha=1.0\)) 48.7 47.70 89.10 25.7 47.10 77.08
CRISP (完整系统) \(C_{\text{struct}}\) 锚点 汇聚感知地平面 (\(\alpha=1.0\)) 48.7 47.77 88.82 28.7 47.23 76.20

在极长序列端到端预填充注意力延迟(Attention-Only Latency)方面,由于彻底阻断了 \(O(n)\) 噪声块的累积,CRISP 展现了随序列长度递增而愈发扩大的效率优势:

上下文长度 (Tokens) FlashAttention FlexPrefill (γ=0.95) FlexPrefill (γ=0.97) CRISP (α=1.0) CRISP (α=1.25) CRISP (α=1.50)
64k 基准 (1.0x) 1,547 ms 1,690 ms 1,776 ms (+5%) 1,589 ms (+3%) 1,441 ms (-7%)
131k 基准 (1.0x) 4,118 ms 5,001 ms 4,801 ms (-4%) 4,314 ms (+5%) 3,940 ms (-4%)
262k 基准 (1.0x) 13,428 ms 13,413 ms 12,740 ms (-5%) 11,714 ms (-13%) 10,982 ms (-18%)
512k 180,634 ms (1.0x) 40,949 ms (4.41x) 46,369 ms (3.90x) 34,983 ms (5.17x) 34,111 ms (5.30x) 33,454 ms (5.40x)

关键发现

  • 两模块协同消除系统漂移:单测 Abl. 1(仅引入 \(C_{\text{struct}}\))在 Llama 上出现明显掉点(InfiniteBench 降 2.2 pp),原因在于 \(C_{\text{struct}}\) 将更多边界头判定为 VS 路径,使这些注意力头暴露在 \(\gamma\)-cumsum 致命的质量悬崖下;而一旦与汇聚感知阈值结合(完整 CRISP),两者的强健性立即互补,取得全场最佳。
  • 纯粹调大 \(\gamma\) 无法逃脱悬崖诅咒:将 FlexPrefill 的累积阈值从 0.95 激进提升到 0.97 时,由于收集了更多本底噪声,延迟大幅恶化(512k 下从 40.9s 飙升至 46.4s),但在长文本检索上却毫无改善,甚至在 InfiniteBench 上出现反向掉点(47.4 \(\to\) 47.3),直接印证了质量悬崖理论。
  • 在检索密集型任务上超越稠密注意力:CRISP \(\alpha=1.0\) 在 InfiniteBench 上不仅追平甚至超越了 FlashAttention 全注意力(Llama 48.7 vs 48.6;Qwen 28.7 vs 24.0)。这是由于全注意力被迫将大量注意力权重机械分散给数以万计的无关背景 Token,导致最终特征表征混杂了大量架构汇聚噪声;CRISP 干净的信噪比切割反而净化了检索信号表示。

亮点与洞察

  • 切片替代散度的计算减法:利用 Transformer 注意力汇聚与因果滑动窗口的几何稳定性,将原本复杂的在线二次池化与 JSD 散度比对退化为一个常数级直接切片读取(\(C_{\text{struct}}\)),在保持近 90% 路由决策一致性的同时完全消除了相关开销。
  • 以信噪比地平面取代累积覆盖度量:敏锐指出概率累积阈值面对极端长尾分布时的固有数学脆弱性,通过动态剥离首尾锚点质量直接建模“平均背景噪声密度”,将块选择转化为纯粹的信噪比判定,给长文本稀疏化提供了一个全新的无校准理论支点。
  • 超长文本线性噪声阻断的可扩展性:在极长上下文(如 512k)场景下,传统累积法引入的垃圾 Token 数量随 \(n\) 呈正比例 \(O(n)\) 爆炸,CRISP 从物理机制上将背景噪声拦截在门外,使得序列越长,相较于传统方法的吞吐与延迟收益越发显著。

局限与展望

  • 对无汇聚新型架构的泛化假设受限:\(C_{\text{struct}}\) 的高精度路由强烈依赖于现代大语言模型具有显式注意力汇聚(Attention Sinks)的架构特性;如果未来模型通过门控机制(Gated Attention)彻底消除了注意力汇聚,当前的锚点切片代理将失去物理对应,需重新设计无汇聚下的代理指标。
  • 二元路由缺乏软性过渡机制:当前方法延续了 VS 与 PE 的二元硬路由决策,对于处于集中与弥散临界态的“混合型(Hybrid)注意力头”,强制划入 VS 路径可能导致非规则分布的关键语义被噪声地平面错误滤除,未来可探索连续置信度加权的软混合路由。
  • 仅聚焦于预填充阶段:该工作主要解决自注意力计算密集型的长 Prompt Prefill 阶段,尚未涵盖显存带宽受限的逐 Token 自回归解码(Decoding)过程,未来可探索将其与针对解码期的动态 KV Cache 剪枝方法协同集成。

相关工作与启发

  • vs FlexPrefill (Lai et al., 2025): FlexPrefill 首次确立了在线 VS/PE 动态路由范式,但采用 JSD 产生冗余算力,且采用固定累积阈值 \(\gamma\) 在后 Softmax 质量悬崖下陷入汇聚折叠与 \(O(n)\) 噪声累积两难;CRISP 采用切片代理 \(C_{\text{struct}}\) 替代 JSD,并以基于残差均值的噪声地平面替代累积阈值,以更低开销彻底根除噪声。
  • vs MInference (Jiang et al., 2024): MInference 依赖离线预先刻画各层注意力的固定稀疏模式并在推理期填充;CRISP 属于全在线纯动态机制,能够针对不同提示词实时捕捉注意力汇聚质量的剧烈波动,避免了离线模式在跨任务与极长上下文下的性能雪崩(LongBench 领先 5–8 pp)。
  • vs Twilight (Lin et al., 2025): Twilight 针对自回归解码(Decoding)阶段的单行 Query 进行自适应 top-p 剪枝以节省显存带宽;CRISP 则专注于预填充(Prefilling)阶段全量矩阵的二次方计算瓶颈,两者的技术思路在长上下文推理引擎中具有天然的上下游互补性。

评分

  • 新颖性: 4.5/5 (直击后Softmax质量分层的数学本质,提出常数级Cstruct路由与汇聚感知噪声地平面,理论深刻且设计巧妙)
  • 实验充分度: 5.0/5 (跨越两个主流模型家族,覆盖三大主流长上下文基准,包含详尽的512k超长延迟扩展测试与严格的单组件消融)
  • 写作质量: 5.0/5 (数学机理阐述极其清晰,图表绘制精良,逻辑论证层层递进)
  • 价值: 4.5/5 (免训练即插即用,彻底解决超长上下文稀疏注意力累积噪声的核心瓶颈,工程落地价值极高)