Skip to content

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

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/huyhuunguyen/CRISP
Area: Model Compression
Keywords: sparse attention / LLM inference / attention sinks / dynamic routing / long-context prefilling

TL;DR

Addressing the quadratic bottleneck of self-attention prefilling in long-context LLMs, CRISP identifies the overhead in JSD-based dynamic routing and mathematically formalizes the post-softmax mass cliff where cumulative coverage thresholds suffer from \(O(n)\) noise accumulation and sink-only collapse, introducing the \(O(1)\) structural routing proxy \(C_{\text{struct}}\) alongside a sink-aware noise-floor threshold to achieve parity with dense attention on retrieval tasks and up to a 5.30x attention speedup at 512k tokens.

Background & Motivation

The self-attention prefilling phase in long-context large language models scales quadratically with sequence length \(n\), constituting a dominant latency and throughput bottleneck in long-context deployment. To alleviate this, state-of-the-art dynamic sparse attention methods such as FlexPrefill introduce runtime routing: evaluating a representative query subset to classify individual attention heads dynamically into concentrated Vertical-Slash (VS) heads or diffuse Pooled-Estimation (PE) heads, and then selecting key-value blocks on VS heads by accumulating directional attention mass up to a cumulative coverage target \(\gamma\) (e.g., 0.95).

However, analyzing the theoretical underpinnings of dynamic prefilling reveals two fundamental structural flaws. First, routing via Jensen-Shannon Divergence (JSD) acts as an indirect proxy that measures the divergence between a dual-pooled query-key attention estimate and the per-query mean. This requires an extra \(O(nd/b)\) downsampled matrix multiplication, a second softmax, and successive logarithmic and reduction passes on every single head, imposing substantial online overhead. Second, autoregressive Transformers exhibit a sharp post-softmax token mass hierarchy: architectural attention sinks absorb a massive fraction (often \(>90\%\)) of attention mass, task-relevant signal blocks carry moderate probability, and background noise tokens receive near-zero mass that decays as \(O(1/n)\). Under this steep mass cliff, cumulative \(\gamma\)-thresholding inevitably triggers two opposite failure modes: if sink mass exceeds \(\gamma\), selection terminates prematurely inside the sink before evaluating any semantic signal (sink-only collapse); conversely, if sink mass falls short of \(\gamma\), the algorithm crosses the cliff into background noise, collecting \(O(\gamma_{\text{residual}} / \epsilon) \approx O(n)\) noise tokens to fulfill the residual quota.

The key insight of this paper is twofold: concentrated attention heads inherently place their mass on predictable geometric anchors (initial attention sinks and the local recency window), meaning concentration can be read directly from an indexed slice of the proxy attention map without indirect divergences; moreover, navigating the mass cliff requires anchoring selection to an adaptive noise-floor threshold rather than an arbitrary cumulative mass quota. Core idea: eliminate indirect JSD overhead with the constant-time structural proxy \(C_{\text{struct}}\) measured directly at attention sink and recency anchors, and replace cumulative thresholding on VS heads with a sink-aware noise-floor threshold that subtracts anchor mass, preventing both \(O(n)\) background noise accumulation and sink-only collapse across ultra-long contexts.

Method

Overall Architecture

CRISP executes a two-phase dynamic prefilling pipeline: online Pattern Search via structural mass proxy and Dual-Path Sparse Index Selection. For each attention head, the system samples a trailing query block \(\hat{Q} = Q[-b:]\) of size \(b=128\) and computes the proxy attention matrix \(\hat{A} = \text{Softmax}(\hat{Q} K^\top / \sqrt{d})\). It directly extracts \(C_{\text{struct}}\) as the average attention mass concentrated at the initial sink tokens and the local recency window. If \(C_{\text{struct}} \ge \tau_{\text{proxy}}\), the head is dispatched to the VS path to execute sink-aware noise-floor selection; otherwise, it is routed to the PE path using relaxed global pooling with cumulative coverage. Finally, the selected block index set \(S\) drives block-sparse FlashAttention kernels to compute exact attention output \(A(Q, K, V, S)\).

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Q, K, V & Query Block Q_hat"] --> B["Proxy Attention Matrix A_hat<br/>Softmax(Q_hat * K^T / sqrt(d))"]
    B --> C["Direct Structural Routing via Cstruct<br/>Mean slice at sink and recency anchors"]
    C -->|Cstruct >= tau_proxy| D["Sink-Aware Noise-Floor Thresholding<br/>Exclude sinks and recency to compute mu"]
    C -->|Cstruct < tau_proxy| E["Diffuse-Path Global Adaptive Pooling<br/>Retain gamma cumulative coverage"]
    D --> F["Sparse Block Index Set S<br/>Sv union Ss union Anchors"]
    E --> F
    F --> G["Block-Sparse Attention Computation<br/>A(Q, K, V, S)"]

Key Designs

1. Direct Structural Routing via Cstruct: Constant-Time Elimination of Secondary Pooling and JSD Computation

FlexPrefill routes heads based on JSD between a pooled attention estimate \(\bar{a}\) and the per-query mean \(\hat{a}\). This requires downsampling \(K\) via pooling, launching an auxiliary \(O(nd/b)\) matrix multiplication, running a secondary softmax, and computing two Kullback-Leibler divergences per head.

CRISP observes that in modern autoregressive Transformers, low-entropy concentrated heads place their probability mass at structurally predictable coordinates—namely the first \(w_{\text{sink}}=128\) tokens (architectural sinks) and the last \(w_{\text{local}}=128\) tokens (local recency window). Rather than indirectly approximating entropy via divergence against a pooled surrogate, CRISP reads concentration directly off these anchor coordinates: $\(C_{\text{struct}} = \frac{1}{|\hat{Q}|} \sum_{i \in \hat{Q}} \sum_{j \in S_{\text{anchor}}} \hat{A}[i, j]\)$ where \(S_{\text{anchor}}\) encompasses the first block \(0\) and the final block \(N_b - 1\). Because \(\hat{A}\) is already required by subsequent index selection, computing \(C_{\text{struct}}\) requires only a constant-time slice reduction of complexity \(O(w_{\text{sink}} + w_{\text{local}})\), completely independent of context length \(n\). Empirically, top-1 mass blocks reside at anchor positions in 91.3% (Llama-3.1-8B) and 98.3% (Qwen2.5-7B) of heads, and \(C_{\text{struct}}\) matches JSD routing decisions on 94.0% and 88.1% of heads respectively, completely stripping out the JSD computational footprint.

2. Sink-Aware Noise-Floor Thresholding: Defeating the Mass Cliff and O(n) Noise Ingestion

On concentrated VS heads, softmax normalizes attention logits such that \(k\) signal tokens with logit \(z\) and \(n-k\) background tokens with logit \(z-\Delta\) yield per-token background probability \(\epsilon = e^{-\Delta} / (k + (n-k)e^{-\Delta}) \approx 1/n\) when \(n \gg k \cdot e^{\Delta}\). When cumulative thresholding \(\sum_{j \in S} a_j \ge \gamma\) is enforced, high sink concentration (\(a_{\text{sink}} \ge \gamma\)) causes premature termination before reaching semantic task blocks (sink-only collapse). Conversely, when \(a_{\text{sink}} + a_{\text{important}} < \gamma\), accumulating the residual quota \(\gamma_{\text{residual}}\) across the background noise floor collects \(N_{\text{garbage}} = \gamma_{\text{residual}} / \epsilon \approx \gamma_{\text{residual}} \cdot n\) tokens, scaling linearly as \(O(n)\) in ultra-long contexts.

CRISP resolves this dilemma by replacing cumulative mass targets with an adaptive noise floor. Excluding the always-retained block \(0\) (sinks) and block \(N_b - 1\) (recency), the expected background mass across the remaining \(N_b - 2\) blocks is formulated as: $\(\mu_d = \frac{\max(1 - p_d[0] - p_d[N_b-1], 0)}{N_b - 2}, \quad d \in \{v, s\}\)$ where \(p_v\) and \(p_s\) denote normalized block-pooled column means and diagonal slash means of \(\hat{A}\), respectively. A block is retained if and only if its mass surpasses the noise floor: $\(\text{block } j \text{ is important} \iff p_d[j] > \alpha \cdot \mu_d\)$ Setting \(\alpha=1.0\) establishes an intuitive, calibration-free default: any block carrying above-average residual mass represents genuine semantic signal. As sink mass increases, the numerator naturally shrinks, appropriately lowering \(\mu_d\) to maintain sensitivity to weak semantic signals; meanwhile, as sequence length \(n\) grows, \(\mu_d\) scales down as \(O(1/n)\), preventing near-zero background blocks from ever being admitted.

3. Diffuse-Path Global Adaptive Pooling: Preserving Smooth Coverage for High-Entropy Heads

Not all attention heads exhibit sharp structural sparsity. For diffuse, high-entropy heads routed to the PE path (\(C_{\text{struct}} < \tau_{\text{proxy}}\)), attention mass decays smoothly and monotonically across the sequence without an abrupt mass cliff. Top-1 block mass in such heads rarely exceeds \(10\%\), and the top-50 blocks aggregate only \(15\%\) to \(80\%\) of total mass, meaning a fixed cumulative target \(\gamma=0.95\) is never reached within the leading blocks. Under such smooth decay, a mean-based noise floor has no cliff to separate; conversely, cumulative coverage \(\sum \bar{A}[i] \ge \gamma\) operates stably as an adaptive coverage sampler without risk of collecting \(O(n)\) near-zero background tokens. CRISP intentionally retains the global-pooling cumulative mechanism for PE heads (Algorithm 4), decoupling the treatment of structured and diffuse attention patterns.

Key Experimental Results

Main Results

Evaluation was conducted on Meta-Llama-3.1-8B-Instruct and Qwen2.5-7B-Instruct across InfiniteBench (131K truncated), RULER (4K–131K context range), and LongBench (4K–16K realistic multi-task). Baselines include exact full dense attention FlashAttention (FA), offline pattern baseline MInference, and FlexPrefill (FP \(\gamma=0.95\) alongside exploratory \(\gamma=0.97\)).

Benchmark Model FlashAttn (FA) MInference FlexPrefill (γ=0.95) FlexPrefill (γ=0.97) CRISP (α=1.0, Rec.) CRISP (α=1.25, Speed)
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

On challenging retrieval tasks vulnerable to sink-only collapse, CRISP achieves remarkable double-digit accuracy recoveries over FlexPrefill:

Retrieval Subtask Source Benchmark Llama-3.1-8B Gain vs FP 0.95 Qwen2.5-7B Gain vs FP 0.95
KV Retrieval InfiniteBench +17.8 pp (61.6 vs 43.8) —* (baseline near-zero)
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)

Ablation Study

Component ablations isolate the impact of \(C_{\text{struct}}\) routing and sink-aware thresholding individually on an NVIDIA H100 GPU:

Configuration Routing Method VS Selection Rule Llama IB Llama LB Llama RULER Qwen IB Qwen LB Qwen RULER
FlexPrefill (Base) JSD Divergence \(\gamma\)-cumsum (0.95) 47.4 46.92 89.22 25.5 45.57 75.52
Abl. 1 (Cstruct only) \(C_{\text{struct}}\) Anchor \(\gamma\)-cumsum (0.95) 45.2 (-2.2) 47.14 87.82 (-1.4) 29.7 45.93 74.92
Abl. 2 (Sink-aware only) JSD Divergence Noise-floor (\(\alpha=1.0\)) 48.7 47.70 89.10 25.7 47.10 77.08
CRISP (Full system) \(C_{\text{struct}}\) Anchor Noise-floor (\(\alpha=1.0\)) 48.7 47.77 88.82 28.7 47.23 76.20

In terms of attention-only latency scaling, eliminating \(O(n)\) noise accumulation yields an efficiency advantage that widens consistently with sequence length:

Context Length (Tokens) FlashAttention FlexPrefill (γ=0.95) FlexPrefill (γ=0.97) CRISP (α=1.0) CRISP (α=1.25) CRISP (α=1.50)
64k Baseline (1.0x) 1,547 ms 1,690 ms 1,776 ms (+5%) 1,589 ms (+3%) 1,441 ms (-7%)
131k Baseline (1.0x) 4,118 ms 5,001 ms 4,801 ms (-4%) 4,314 ms (+5%) 3,940 ms (-4%)
262k Baseline (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)

Key Findings

  • Compounding Interaction of Both Fixes: Evaluating Abl. 1 in isolation degrades performance on Llama (-2.2 pp on InfiniteBench) because \(C_{\text{struct}}\) routes slightly more heads to the VS path, exposing them directly to the hazardous cumulative threshold \(\gamma\)-cumsum. Full CRISP pairs \(C_{\text{struct}}\) with sink-aware thresholding to eliminate regressions completely across both model architectures.
  • Tuning Cumulative Coverage Cannot Escape the Cliff: Increasing FlexPrefill coverage from \(\gamma=0.95\) to \(\gamma=0.97\) provides negligible retrieval improvement while severely worsening latency at 512k tokens (from 40.9s to 46.4s), as selection pushes deeper into near-zero background noise.
  • Surpassing Dense Attention via Representation Denoising: On InfiniteBench, CRISP \(\alpha=1.0\) matches or outperforms exact FlashAttention (48.7 vs 48.6 on Llama; 28.7 vs 24.0 on Qwen). Full attention aggregates attention across thousands of uninformative tokens and architecture noise, whereas CRISP isolates genuine signal blocks, yielding a cleaner post-attention representation.

Highlights & Insights

  • Direct Coordinate Slicing Over Divergences: By leveraging the architectural inductive bias of attention sinks and local causal windows, CRISP replaces expensive downsampled matrix multiplications and JSD divergences with a simple \(O(1)\) coordinate slice reduction (\(C_{\text{struct}}\)).
  • Grounding Sparsity in a Physical Noise Floor: Replacing an arbitrary cumulative coverage percentage with an adaptive noise-floor threshold (\(\alpha \cdot \mu_d\)) derived from non-retained residual mass provides a calibration-free, mathematically grounded boundary between semantic signal and background noise.
  • Linear Noise Elimination at Scale: Because per-token background noise decays as \(O(1/n)\), cumulative selection inherently admits \(O(n)\) noise tokens; CRISP eliminates this \(O(n)\) noise entirely, widening its latency speedup up to 5.40x at 512k tokens.

Limitations & Future Work

  • Dependency on Sink-Having Architectures: \(C_{\text{struct}}\) relies on the presence of architectural attention sinks. In emerging sink-free or gated architectures (e.g., Gated Attention), the physical correspondence between low entropy and fixed anchor coordinates may break down.
  • Rigid Binary Routing: The binary assignment into pure VS or pure PE paths does not perfectly suit hybrid heads that exhibit mixed structural behaviors. Softer probabilistic mixing or dynamic per-head schedules remain an open direction.
  • Prefilling Scope: The current formulation focuses on compute-bound prefilling and does not directly extend to token-by-token autoregressive decoding, where KV-cache bandwidth becomes the primary constraint.
  • vs FlexPrefill (Lai et al., 2025): FlexPrefill pioneered online dynamic routing but relies on compute-heavy JSD and cumulative coverage that triggers sink-only collapse and \(O(n)\) noise ingestion. CRISP substitutes JSD with constant-time \(C_{\text{struct}}\) and cumulative coverage with a sink-aware noise floor.
  • vs MInference (Jiang et al., 2024): MInference profiles per-head sparse patterns offline, failing to adapt when sink mass varies across inputs and sequence lengths (trailing FlexPrefill by 5–8 pp on LongBench). CRISP adapts completely online with zero offline profiling.
  • vs Twilight (Lin et al., 2025): Twilight targets memory bandwidth during decoding via adaptive top-\(p\) pruning across single query rows, whereas CRISP targets compute bottlenecks during prefilling over full sequence attention matrices; both represent complementary techniques for end-to-end long-context inference.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ (Elegant formulation of the post-softmax mass cliff, with constant-time Cstruct proxy and sink-aware noise-floor thresholding)
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ (Rigorous validation across two distinct model families, multiple context lengths up to 512k tokens, and extensive ablations)
  • Writing Quality: ⭐⭐⭐⭐⭐ (Exceptionally clear narrative, precise mathematical derivations, and illuminating empirical visualizations)
  • Value: ⭐⭐⭐⭐⭐ (Training-free, drop-in sparse prefilling mechanism with substantial speedups and zero accuracy degradation on long-context tasks)