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

> CRISP replaces indirect JSD routing and cumulative coverage thresholds with a structural-mass proxy and sink-aware noise-floor threshold, achieving parity with dense attention and up to 5.30x speedup at 512k tokens.

- **Source:** [arXiv](https://arxiv.org/abs/2609.01925)
- **Published:** 2026-09-05
- **Permalink:** https://picx.dev/p/5JcsAV
- **Whiteboard:** https://picx.dev/p/5JcsAV/image

## Summary

## 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).

| Measurement | Llama-3.1-8B | Qwen2.5-7B |
|---|---|---|
| Routing agreement with JSD | 94.0% | 88.1% |
| Top-1 mass at sink/recency | 91.3% | 98.3% |

*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:

| Benchmark | Method | Llama-3.1-8B | Qwen2.5-7B |
|---|---|---|---|
| InfiniteBench (131K) | FlashAttn (FA) | 48.6 | 24.0 |
| | MInference | | 36.5 | 25.1 |
| | FP γ=0.95 | | 47.4 | | 25.5 |
| | FP γ=0.97 | | 47.3↓ | 26.7 |
| | CRISP α=1.25 | | 48.0 | | 28.4 |
| | CRISP α=1.0 | | 48.7↑FA | 28.7↑FA |
| RULER (4K–131K) | FlashAttn (FA) | | 89.02 | | 75.84 |
| | MInference | | 86.14 | | 72.44 |
| | FP γ=0.95 | | 89.22 | | 75.52 |
| | FP γ=0.97 | | 89.14↓ | 75.80 |
| | CRISP α=1.25 | | 88.62 | | 75.80 |
| | CRISP α=1.0 | | 88.82 | | 76.20↑FA |
| LongBench (4K–16K) | FlashAttn (FA) | | 48.82 | | 48.80 |
| | MInference | | 41.40 | | 38.95 |
| | FP γ=0.95 | | 46.92 | | 45.57 |
| | FP γ=0.97 | | 47.12 | | 46.45 |
| | CRISP α=1.25 | | 46.92 | | 46.76 |
| | CRISP α=1.0 | | 47.77 | | 47.23 |

*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:

| Task | Benchmark | Llama Δ | Qwen Δ |
|---|---|---|---|
| KV Retrieval | InfiniteBench | | +17.8pp | - * |
| Passkey | InfiniteBench | | 0.0pp | +28.0pp |
| Passage Retrieval (En) | LongBench | | +12.50pp | +13.50pp |
| Passage Retrieval (Zh) | LongBench | | +3.16pp | +4.50pp |
| RULER 65K | RULER | | +2.65pp | +1.45pp |

*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:

| Method | 64k | 131k | | 262k | | 512k |
|---|---|---|---|---|---|---|
| FP γ=0.95 | 1,547ms | 4,118ms | 13,428ms | | 40,949ms |
| FP γ=0.97 | 1,690ms | | 5,001ms | | 13,413ms | | 46,369ms |
| CRISP α=1.5 | | 1,441ms (-7%) | | 3,940ms (-4%) | | 10,982ms (-18%) | | 33,454ms (-18%) |
| CRISP α=1.25 | | 1,589ms (+3%) | | 4,314ms (+5%) | | 11,714ms (-13%) | | 34,111ms (-17%) |
| CRISP α=1.0 | | 1,776ms (+5%) | | 4,801ms (-4%) | | 12,740ms (-5%) | | 34,983ms (-25%) |

*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.

---

_Markdown view of https://picx.dev/p/5JcsAV, served by PicX — AI-generated visual whiteboard summaries of research papers._