Summary (Overview)

• Problem: The attention prefilling phase of long-context LLM inference scales quadratically, making self-attention a severe computational bottleneck. Traditional sparse attention methods use fixed patterns or offline profiling, lacking flexibility to adapt to input-dependent attention structures.
• Key Contributions: CRISP (Cliff-awaRe Input-adaptive Sparse Prefilling) identifies and addresses two structural challenges in dynamic routing: (1) replaces indirect Jensen-Shannon Divergence (JSD) routing with a structural-mass proxy $C _ { \mathrm { s t r u c t } }$ that measures mass at Vertical-Slash compatible positions, eliminating pooled matmul and KL divergence overhead; (2) formalizes the post-softmax "mass cliff"and introduces a sink-aware threshold grounded in the noise floor to replace cumulative coverage thresholds that accumulate $O(n)$ background noise at long contexts.
• Results: CRISP achieves parity with or exceeds exact dense attention on retrieval-heavy benchmarks, recovering up to +28.0 pp on retrieval tasks over baselines, and delivering up to a 5.30× attention speedup at 512k tokens; it is the strongest sparse method overall across InfiniteBench, RULER, and LongBench on two model families (Llama-3.1-8B, Qwen2.5-7B).

Introduction and Theoretical Foundation

• Background: The prefilling phase of long-context LLM inference scales quadratically, making self-attentiona severe bottleneck. Traditional sparse attention uses fixed patterns (Child et al., 2019; Zaheer et al.,, 2020) or offline profiling(Jiang et al,,, .,2024), lacking flexibility to adapt to input-dependent attention structures.
• Motivation: State-of-the-art methods like FlexPrefill(Lai et al.,, 2025) introduce dynamic routing, categorizing heads in realtime to allocate compute budgets, using JSD for pattern routing anda cumulative coverage threshold $\gamma$ for index selection. However, analyzing their theoretical foundations reveals principled limitations in both mechanisms:
  • JSD is an indirect routing signal: JSD builds a second, pooled estimate of the head's attention and measures how far it diverges from the per-query one, routing to VS above a threshold $\tau$. This estimate costs a matmul anda softmax that nothing else in the method needs.
  • Cumulative thresholds cannot navigate the mass cliff: On VS heads, softmax amplification produces a rigid mass hierarchy: architectural sinks(might absorb up to >90% mass), task-relevant signal blocks,and near-zero background noise. Cumulative $\gamma$-thresholding accumulates mass indiscriminately across this boundary, producing two structural failure modes: sink-only collapse(in which selection terminates before reaching signal) and residual noise accumulation(in which $O(n)$ near-zero background tokens are collected to satisfy the residual threshold.
• Theoretical Basis: The information-theoretic link between entropy and support size(Campbell,1966) tells us that low-entropy heads need few tokens for high coverage; in autoregressive transformers, these tokens occupy structurally predictable positions—architectural sinks(Xiao et al.,,,2024), vertical columns,and slash diagonals(Jiang et al,,, 2024; Lai et al,,, 2025)—giving rise to the Vertical-Slash(VS) pattern. High-entropy heads lack such structure, making pooled estimation(PE) the more effective strategy.

Methodology

• $C _ { \mathrm { s t r u c t } }$Structural Proxy:

  • Replaces JSD with a direct measurement of VS-compatible mass:
  C _ {\text { struct }} = \frac {1}{| \hat {Q} |} \sum_ {i \in \hat {Q}} \sum_ {j \in \mathcal {S} _ {\text { anchor }}}} \hat {A} [ i,j ]\tag{2}

  where $S _ { \mathrm { a n c h o r } }$ contains the architectural sinks(first $w _ { \mathrm { s i n k } } { = } 1 2 8$ tokens) andthe local recency window($w _ { \mathrm { l o c a l } } { = } 1 2 8$).

  • CRISP routes a head to VS if $C _ { \mathrm { s t r u c t } } \geq \tau _ { \mathrm { p r o x y } } ,$and to PE otherwise. The operation executes in $O ( w _ { \mathrm { s i n k } } + w _ { \mathrm { l o c a l } } )$ time, scaling independently of total sequence length n, eliminating JSD overhead.

• Sink-Aware Thresholding:

  • The proxy attention map is partitioned into $N _ { b } = \lceil n / B \rceil$ blocks of $B { = } 1 2 8$ tokens;the first block(sinks)and last block(local recency) are always retained. A baseline expected mass over the remaining $N _ { b } - 2$ blocks is:
  $$\mu = \frac {\max (1 - a _ {\mathrm{first}} - a _ {\mathrm{last}} , 0)}{N _ {b} - 2}\tag{3}$$

  A block is selected if and only if it exceeds the expected background mass:

  $$\text { block } j \text { is important } \iff p _ {j} > \alpha \cdot \mu\tag{4}$$

  At $\alpha=1.0$, the threshold equals the expected background mass—any block above the mean carries above-average signal, making $\alpha=1.0$ a calibration-free default. The budget $k$ emerges from task complexity: focused tasks select fewer blocks, dense tasks select more.

• Algorithm Overview:

  • Algorithm 1 (CRISP Sparse Attention): Routes each head via PATSEARCH, selects sparse index set via VSINDEX (sink-aware) or PEINDEX, then computes sparse attention output.

  • Algorithm 2 (PatSearch): Computes representative attention $\hat{A}$ on a query subset, calculates $C_{\text{struct}}$ as mass at VS-compatible positions, and routes to VS if $C_{\text{struct}} \geq \tau_{\text{proxy}}$.

  • Algorithm 3 (VS Index, Sink-Aware): Computes directional scores(column means $a_v$ and diagonal means $a_s$), block-pools them, computes noise floor $\mu_d$ over non-retained blocks, and selects blocks exceeding $\alpha \cdot \mu_d$;always retains first and last blocks.

  • Algorithm 4 (PE Index, GlobalAdaptive): Pools over all queries, computes $\bar{A} = \text{Softmax}(\bar{Q}\bar{K}^\top/\sqrt{d})$, flattens and normalizes, sorts,and applies $\gamma$-cumsum to select top-$K^*$ blocks.

Empirical Validation / Results

• Routing Analysis: $C _ { \mathrm { s t r u c t } }$ reproduces JSD's routing decisions on 94.0%(Llama)and 88.1%(Qwen)of measured heads;top-1 mass at sink/recency is 91.3%(Llama)and 98.3%(Qwen).

Table ​1: Routing analysis over all attention heads of both models, measured on InfiniteBench inputs.

• Summary Results (Table 2): CRISP $\alpha = 1 .$ .0 achieves parity with or exceeds exact dense attention on retrieval-heavy tasks and is the top-performing sparse method overall:

Table ​2: Summary results. FP = FlexPrefill; FA = FlashAttention (full attention). The red arrow (↓) denotes performance degradation when increasing FP coverage from 0.95 to 0.97.

• Retrieval Accuracy Recovery (Table 3): Double-digit gains on retrieval tasks, empirically proving sink-only collapse:

Table ​3: Retrieval accuracy recovery vs FlexPrefill γ=0.95. ∗Qwen2.5 baseline is near-zero on this task; difference is not meaningful.

• Latency Scaling (Table 4, Figure 4): All CRISP configurations overtake FlexPrefill at long contexts, reaching 5.17×–5.40× speedup over FlashAttention at 512k tokens:

Table ​4: Attention-only latency(mean, single H100). Overhead/saving in parentheses relative to FP γ=0.95 for α∈{1.5, 1.25} and FP γ=0.97 for α=1.0.

• Component Ablation (Table 5): Full CRISP demonstrates the most robust performance across both models, recovering from regressions caused by partial systems:

the two components interact—replacing JSD routing alone exposes more heads to γ-cumsum selection that the mass cliff defeats, while sink-aware selection alone is broadly beneficial.

Theoretical and Practical Implications

• Theoretical Implications:

  • Formalization of the mass cliff: The post-softmax token hierarchy is formalized, with architectural sinks absorbing dominant mass, task-relevant signal holding moderate mass,and background noise carrying near-zero mass that scales as $O(1/n)$. Strictly cumulative coverage thresholds inherently accumulate $O(n)$ background noise at scale, making them asymptotically ill-suited to ultra-long contexts.

  • Routing dichotomy grounding: The VS/PE routing dichotomy is given an information-theoretic foundation: low-entropy heads concentrate mass at structurally predictable positions(sinks, vertical columns, slash diagonals), while high-entropy heads lack such structure, making pooled estimation more effective. The $C_{\text{struct}}$ proxy works because low-entropy heads in current sink-having architectures place their mass at exactly those positions.

• Practical Implications:

  • Calibration-free default: $\alpha=1.0$ is theoretically motivated as the noise-floor threshold, requiring no empirical calibration;it achieves parity with or exceeds exact dense attention on InfiniteBench while providing significant speedups.

  • Retrieval task recovery: CRISP recovers up to +28.0 pp on retrieval tasks, demonstrating that sink-only collapse is a real failure mode of cumulative thresholding that parameter tuning cannot resolve—increasing $\gamma$ merely pushes selection deeper into noise with no retrieval improvement.

  • Latency scaling: The efficiency advantage compounds as context grows, with CRISP overtaking FlexPrefill beyond 131k tokens and reaching up to 5.30× speedup at 512k tokens, driven entirely by resolving the $O(n)$ noise accumulation bottleneck during selection while preserving structural integrity.

Conclusion

• Main Takeaways:

  • CRISP identifies and resolves two principled limitations in dynamic sparse attention: indirect JSD-based routing and cumulative $\gamma$-thresholding that accumulates $O(n)$ background noise.

  • By replacing JSD with the structural proxy $C_{\text{struct}}$ and cumulative thresholds with a sink-aware noise-floor threshold, CRISP explicitly separates signal from architectural noise, achieving parity with exact dense attention on InfiniteBench and delivering up to a 5.30× latency speedup at 512k tokens. The method establishes a new performance hierarchy, recovering up to +28.0 pp on retrieval tasks over baselines.

• Future Directions:

  • Architectural scope: $C_{\text{struct}}$ relies on the empirical property that low-entropy heads in current sink-having architectures concentrate mass at sinks and recency;architectures that suppress attention sinks would require a different structural proxy. Evidence spans two model families at 7–8B scale, bounding how far these regularities should be assumed to generalise.

  • Hybrid heads: CRISP inherits FlexPrefill's binary VS/PE routing;softer schemes—probabilistic mixing, or per-head confidence-weighted decisions—are left to future work.

  • Scaling and decoding: Empirical verification on models >8B or contexts beyond established benchmarks remains future work;extension to token-level decoding under causal masking requires characterizing the mass cliff dynamically during autoregressive generation.

  • Path selection: CRISP improvements focus heavily on the VS path;full improvements to the PE path and dynamic scheduling of $\alpha$ to mitigate precision-coverage tradeoffs in aggregation tasks(e.g., Llama RULER) are left to future treatment.