CRISP: Cliff-awaRe Input-adaptive Sparse Prefilling with Structural-Mass-Motivated Routing
Abstract Overview
CRISP is a training-free method for long-context sparse prefilling that targets two limitations identified in prior dynamic sparse attention systems. First, the paper argues that routing decisions can be inferred directly from the structure of a proxy attention map, replacing Jensen-Shannon-divergence-based routing with a structural mass measure, C_struct, over sink and recency positions. Second, it formalizes a post-softmax "mass cliff," where cumulative coverage thresholds can either stop inside sink mass or accumulate long-tail background noise as context length grows. The method therefore uses sink-aware thresholding on vertical-slash heads while retaining a pooled-estimation path for diffuse heads. Experiments on Llama-3.1-8B and Qwen2.5-7B across InfiniteBench, RULER, and LongBench evaluate both accuracy and attention-only latency scaling.
Novelty
The paper’s main novelty is the combination of a structural routing proxy, C_struct, with a theory-motivated sink-aware threshold that is designed around the post-softmax mass hierarchy rather than a cumulative coverage target. It also contributes a theoretical argument that strict cumulative thresholds can incur O(n) background-noise accumulation at long context lengths.
Results
Empirically, C_struct reproduces JSD routing decisions with 94.0% agreement on Llama and 88.1% on Qwen, while avoiding the extra pooled matmul and KL-divergence computation used by the baseline router. Across benchmarks, CRISP is reported as the strongest sparse method overall, with retrieval gains of up to +28.0 percentage points over FlexPrefill baselines and parity with or better than dense attention on some retrieval-heavy settings. In attention-only latency tests up to 512k tokens, CRISP reaches up to 5.30x speedup at the recommended settings and 5.40x in the fastest configuration, with larger advantages appearing at longer contexts.
Key Points
- CRISP replaces indirect JSD-based routing with C_struct, a direct measurement of attention mass at sink and recency anchor positions already present in the proxy map.
- The paper identifies a post-softmax mass cliff and argues that cumulative coverage thresholding has two structural failure modes: sink-only collapse and O(n) residual noise accumulation.
- On two model families and multiple long-context benchmarks, CRISP improves retrieval-oriented performance over prior sparse baselines and shows stronger long-context latency scaling than FlexPrefill.