CRISP speeds up long-context Prefilling (LLM inference) by routing each attention head with a cheap structural signal and picking tokens against a noise floor instead of a coverage target, cutting the O(n) noise blocks that cumulative thresholds accumulate at 512k tokens.
You’re serving a long-context model behind a chat or RAG endpoint, and the prefill pass on a 200k-token prompt dominates your p50 latency. The standard fix is sparse attention: skip most of the QK matmul by only computing attention for a chosen subset of key blocks per head. The current strong dynamic approach, FlexPrefill, decides per input which heads get which sparse pattern and how many tokens each keeps. CRISP is a drop-in replacement for FlexPrefill’s two decision rules that is both faster and more accurate, especially past 100k tokens.
CRISP inherits FlexPrefill’s split: each head goes down either a Vertical-Slash path (for heads whose attention concentrates on specific columns and diagonals) or a Pooled-Estimation path (for diffuse heads). It changes two things.
First, the routing signal. FlexPrefill decides which path by building a second pooled attention estimate and measuring Jensen-Shannon Divergence (JSD) against the per-query one. That costs an extra matmul and softmax per head. CRISP observes that in current models, concentrated heads dump their mass onto a small set of structurally predictable positions: the first ~128 tokens (Attention sink) and the last ~128 tokens (local recency window). So it just sums proxy-attention mass at those anchor positions, calls that C_struct, and routes to Vertical-Slash if C_struct is above a threshold. This reproduces JSD’s routing decision on 94% of Llama heads and 88% of Qwen heads at essentially zero extra cost.
Second, the token-selection rule for Vertical-Slash heads. FlexPrefill sorts block scores and keeps adding blocks until they sum to a coverage target γ (say 0.95). The paper’s core observation: after softmax, blocks fall into three tiers, sinks (huge mass), signal (moderate), and background (near-zero, roughly 1/n per token). They call the gap between signal and background the mass cliff. A γ target either terminates inside the sink (missing all signal) or overshoots signal and swallows O(n) noise blocks to hit the residual. CRISP instead computes the average residual mass per non-anchor block, μ, and keeps every block above α·μ, with α=1.0 as the calibration-free default (“keep blocks with above-average residual mass”).
# Per head, at prefill time:
A_hat = softmax(Q_last_block @ K.T / sqrt(d)) # proxy attention
C_struct = A_hat[:, sink_idx + recency_idx].sum() / b
if C_struct >= tau_proxy: # Vertical-Slash path
p = block_pool(colmean(A_hat)), block_pool(diagmean(A_hat))
mu = max(1 - p[0] - p[-1], 0) / (N_blocks - 2)
S = {j : p[j] > alpha * mu} # noise-floor, not coverage
else: # Pooled-Estimation path
S = gamma_cumsum(pool(Q), pool(K), gamma=0.95)
return sparse_attention(Q, K, V, S)
The prevailing recipe for dynamic sparse attention is “pick tokens until you’ve covered γ of the softmax mass.” This paper shows the opposite. Once softmax has amplified a few tokens into a mass cliff, chasing a coverage target guarantees you either stop inside the sink or scrape O(n) background noise to fill the quota; the right rule is to keep blocks that beat the residual noise floor. The clean evidence is not the headline benchmarks but the Mass cliff ablation: pushing FlexPrefill’s γ from 0.95 to 0.97 degrades some tasks while slowing everything down.
The load-bearing result is that raising FlexPrefill’s coverage γ from 0.95 → 0.97 does not fix its retrieval failures and costs meaningful latency, exactly as the mass-cliff analysis predicts. That establishes the failure mode is structural, not a tuning problem.
Given that, CRISP’s numbers:
•
Retrieval recovery vs FlexPrefill γ=0.95: +17.8 pp on InfiniteBench kv_retrieval (Llama), +28.0 pp on passkey (Qwen), +12.5/+13.5 pp on LongBench passage-retrieval-en.
•
Parity with exact dense attention on InfiniteBench at 131k: Llama 48.7 vs FlashAttention 48.6; Qwen 28.7 vs 24.0. Sparse actually edging dense is attributed to CRISP filtering sink noise that dense attention still aggregates.
•
Latency at 512k tokens on one H100: up to 5.30× over FlashAttention at α=1.25, vs 4.41× for FP γ=0.95. The gap widens with context length, which is the O(n) noise elimination showing up as wall-clock.
•
Ablation: C_struct routing alone slightly hurts Llama (it routes more heads to the broken γ-selection); sink-aware selection alone helps; you need both. On RULER Llama, CRISP loses 0.4 pp vs γ=0.95, a precision-coverage tradeoff on aggregation tasks.
•
Below ~64k tokens, routing overhead dominates and sparse prefilling is slower than dense for both methods.
Reach for this if you’re running long-context prefill (≥64k tokens) on a sink-having model like Llama-3.1-8B-Instruct or Qwen2.5-7B-Instruct and today you’re using FlexPrefill or MInference. The swap is two decision rules inside the sparse-attention kernel: replace the JSD router with a slice-sum over sink+recency blocks, replace γ-cumsum with a mean-based threshold. You get retrieval accuracy that matches dense on long prompts and speedups that grow with sequence length. If you serve mostly short prompts, gate sparse prefill on a length threshold; below the crossover it’s slower than FlashAttention.
The paper doesn’t link a code repository in the provided text. The evaluation setup uses two off-the-shelf 7-8B instruction-tuned models against three published long-context benchmarks (InfiniteBench, RULER, LongBench), so replication is at least clearly specified even if artifacts aren’t announced here.
When softmax builds a cliff, thresholding on “above the noise floor” beats thresholding on “covers γ of the mass.” Coverage-based rules were always going to break at long context because the background band scales with n, and the fix isn’t more coverage, it’s a rule that knows what background looks like.
•
The whole story rests on models having strong attention sinks. Architectures that suppress sinks (e.g. gated attention variants) break the C_struct proxy; the paper is explicit that this is empirical, not a property of softmax.
•
Evidence is two 7-8B models plus one 4B check. No results at 70B+ scale, and no results on decoding, only on prefill. Extending to autoregressive decoding needs a different treatment of the cliff.
•
The Vertical-Slash / Pooled-Estimation split is inherited wholesale from FlexPrefill and forced to be binary. Heads with mixed structure get shoved onto the VS path, where sink-aware selection can discard tokens they actually needed, which likely explains the small RULER regression on Llama.