PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Huu Huy Nguyen, Chien Van Nguyen, Franck Dernoncourt, Ryan A. Rossi, Linh Ngo Van, Jieyang Chen, Thien Huu Nguyen

arXiv:2609.01925v1cs.LGcs.CL

TL;DR

Long-context prefilling is bottlenecked by quadratic self-attention, while dynamic sparse methods incur routing overhead and use thresholds that overlook post-softmax mass structure. CRISP replaces JSD routing with structural-mass routing and cumulative coverage with sink-aware noise-floor selection, recovering retrieval performance and reaching up to 5.30× attention speedup at 512k tokens.

  • Problem

    Long-context prefilling remains computationally expensive because self-attention scales quadratically, while dynamic sparse methods use indirect routing proxies and coverage thresholds that overlook post-softmax mass hierarchy.

  • Method

    CRISP uses Cstruct to route heads from structural mass at Vertical-Slash-compatible positions and applies sink-aware thresholds grounded in the noise floor for VS selection.

  • Results

    CRISP is the strongest sparse method overall, matches or exceeds exact dense attention on retrieval-heavy benchmarks, recovers up to +28.0 pp on retrieval tasks, and achieves up to a 5.30× attention speedup at 512k tokens.

  • Takeaways & Limitations

    CRISP provides a structurally grounded sparse-prefilling approach that eliminates O(n) background-noise accumulation during selection while preserving the structural decomposition of attention.

  • Takeaways & Limitations

    CRISP’s assumptions may not hold for sink-suppressing architectures, and its evidence covers two model families at 7–8B scale; PE-path improvements remain future work.

Abstract

from arXiv · show

The attention prefilling phase of long-context LLM inference scales quadratically, making self-attention a severe computational bottleneck. Traditional sparse attention methods mitigate this through fixed patterns or offline profiling, but lack the flexibility to adapt to input-dependent attention structure. Recent dynamic methods address this by routing heads to sparse patterns in real-time, but rely on indirect routing proxies with overhead and budget allocation mechanisms that overlook the post-softmax mass hierarchy. We present CRISP (Cliff-awaRe Input-adaptive Sparse Prefilling), which identifies and addresses two structural challenges in this dynamic routing paradigm. First, we show that the routing decision can be read directly off the structure of the proxy attention map. We replace the Jensen-Shannon Divergence (JSD) routing with C_struct, a structural proxy that measures mass at Vertical-Slash compatible positions and reproduces JSD's routing decisions while eliminating both the pooled matmul and subsequent KL divergence overhead. Second, we formalize the post-softmax mass cliff and demonstrate theoretically that strictly cumulative coverage thresholds accumulate O(n) background noise at long contexts. CRISP navigates this via a sink-aware threshold grounded in the noise floor. Empirically, across InfiniteBench, RULER and LongBench on two model families, CRISP is the strongest sparse method overall and matches or exceeds exact dense attention on retrieval-heavy benchmarks, recovering up to +28.0 pp on retrieval tasks over baselines and achieving up to a 5.30x attention speedup at 512k tokens, driven primarily by our O(n) noise elimination during selection while preserving structural integrity.

1 Introduction

CRISP targets quadratic long-context prefilling by replacing indirect dynamic routing and cumulative coverage selection with structural routing and sink-aware thresholding. It addresses routing overhead and the accumulation of background noise across the post-softmax mass cliff.

  • Long-context self-attention makes prefilling a severe quadratic computational bottleneck, while fixed-pattern and offline-profiled sparse methods cannot adapt to input-dependent attention.
  • Dynamic routing methods such as FlexPrefill use JSD to route heads between Vertical-Slash and Pooled-Estimation paths, then select indices with a cumulative coverage threshold γ.
  • Cstruct reads concentration from mass at structurally predictable sink and recency positions, avoiding the pooled estimate and divergence computation used by JSD.
  • VS-head softmax mass forms a hierarchy of sinks, task-relevant signal, and near-zero noise separated by a mass cliff; cumulative thresholding can either stop inside sinks or collect O(n) noise.
  • CRISP replaces γ-based selection on VS heads with a sink-aware noise-floor threshold while retaining separate vertical and slash score computation and unioning their selected indices.
  • CRISP achieves parity with dense attention and provides up to 5.30× speedups by resolving O(n) noise accumulation during sparse selection.

3 Structural-Mass Routing

The paper explains VS/PE routing through attention structure: concentrated heads place mass in predictable patterns, whereas diffuse heads are better suited to pooled estimation. It argues that JSD detects this distinction indirectly and motivates a cheaper structural proxy.

  • Low-entropy heads need few tokens for high coverage and tend to place mass at sinks, vertical columns, and slash diagonals, making them suitable for the VS path.
  • High-entropy heads spread mass broadly without a dominant exploitable pattern, making pooled estimation the more effective PE strategy.
  • FlexPrefill’s JSD compares pooled-before-softmax and per-query-averaged distributions; their disagreement is small for vertical agreement but large when queries peak on different slash keys.
  • The paper presents the JSD explanation as an observation consistent with measurements rather than a derivation, and notes that the sink-and-recency structural account is architecture-dependent.
  • Cstruct reproduces JSD routing decisions by measuring structural mass at fixed anchor positions already inspected during index selection.
  • Computing JSD requires an additional pooled matmul, second softmax, logarithm passes, and reductions for every head.

6: # Cstruct: mass at VS-compatible positions

Cstruct replaces indirect JSD routing with direct structural-mass measurement at Vertical-Slash-compatible positions, reducing routing overhead while preserving routing decisions.

  • Cstruct: mass at VS-compatible positions: Cstruct directly measures proxy attention mass at structurally stable sink and recency positions for VS-compatible routing.The anchor set contains the first 128 sink tokens and the last 128 local-recency tokens.
  • Cstruct: mass at VS-compatible positions: The Cstruct block mask measures proxy mass only at architectural sinks and the local recency band, skipping uncomputed queries.This restricts measurement to positions described as structurally stable.
  • Cstruct: mass at VS-compatible positions: Routing agrees with FlexPrefill’s JSD decision for 94.0% of Llama heads and 88.1% of Qwen heads.Top-1 mass lies in a sink or recency block for 91.3% of Llama heads and 98.3% of Qwen heads.
  • Cstruct: mass at VS-compatible positions: Cstruct eliminates the pooled matmul and KL-divergence overhead required by JSD-based routing.It is a constant-time indexed slice reduction over the proxy attention map already computed for index selection.

4 Navigating the Mass Cliff

Strict cumulative coverage thresholds overlook the post-softmax mass hierarchy, causing sink-only collapse or O(n) noise accumulation; CRISP instead selects blocks above a noise-floor threshold.

  • Mass hierarchy: VS-head attention forms a three-class hierarchy of architectural sinks, task-relevant signal, and near-zero background noise.Background per-token mass scales as O(1/n) for a fixed pre-softmax gap.
  • Failure modes of γ: Cumulative coverage thresholds can terminate on sink mass before evaluating task-relevant tokens, producing sink-only collapse.When a_sink ≥ γ, the selected set contains zero semantic information despite satisfying the formal coverage bound.
  • Failure modes of γ: Cumulative coverage can collect O(n) background-noise tokens after crossing the mass cliff.This occurs when sink and important-signal mass remain below γ, requiring residual coverage from near-zero tokens.
  • Scaling outcome: At 512k tokens, CRISP reaches 5.17×, 5.30×, and 5.40× speedup over FlashAttention for α=1.0, 1.25, and 1.5.All configurations overtake their FlexPrefill counterparts beyond 131k tokens.
  • Failure modes of γ: Increasing γ cannot escape the cliff because selection moves deeper into noise, with effects varying by sink-mass position across models and tasks.The text reports that γ=0.97 degrades some benchmarks while marginally improving others.
  • Noise-floor thresholding: CRISP selects non-anchor blocks when their mass exceeds expected background mass, with α=1.0 providing a calibration-free default.The selected budget emerges from task complexity, while the threshold adjusts as sink mass grows.
  • Noise-floor thresholding: CRISP retains γ-cumulative selection for PE heads because their diffuse mass lacks the severe structural hierarchy found on VS heads.The method applies noise-floor selection to VS directions while preserving the PE path’s γ-cumsum approximation.

5 Experiments

Across three long-context benchmarks and two model families, CRISP is the strongest sparse method overall, recovering retrieval accuracy and widening its latency advantage as contexts grow. Its main limitation is a modest Llama RULER regression on aggregation tasks, reflecting a precision–coverage trade-off.

  • Overall results: CRISP α=1.0 achieves parity with or exceeds exact dense attention on retrieval-heavy tasks and is the top-performing sparse method overall.The summary table compares CRISP with FlexPrefill, MInference, and FlashAttention.
  • Retrieval Accuracy Recovery: +28.0pp is the Qwen2.5 passkey gain over FlexPrefill γ=0.95, while γ=0.97 provides no retrieval improvement and costs additional latency.The result is attributed to sink-only collapse under cumulative coverage selection.
  • General Performance: CRISP α=1.0 achieves InfiniteBench parity with exact dense attention: 48.7 vs 48.6 on Llama and 28.7 vs 24.0 on Qwen.These results are reported for CRISP α=1.0 and exact dense attention in Table 10.
  • General Performance: CRISP gains +0.85pp and +1.66pp over FlexPrefill γ=0.95 on LongBench, while γ=0.97 reaches only 47.12 on Llama versus CRISP’s 47.77.The higher-coverage FlexPrefill setting also incurs a substantial latency regression.
  • General Performance: CRISP is modestly lower on Llama RULER by −0.40pp versus γ=0.95, because sink-aware selection can under-select borderline midrange blocks required by aggregation tasks.On Qwen, CRISP wins RULER outright at 76.20 vs 75.52 vs 72.44, showing model-dependent behavior.
  • Latency Scaling: 5.30× is CRISP α=1.25’s attention speedup at 512k, versus 4.41× for FlexPrefill γ=0.95; the advantage widens with sequence length.CRISP α=1.0 is 25% faster than γ=0.97 at 512k, while α=1.5 reaches 5.40× over FlashAttention.
  • Latency Scaling: At 8K, CRISP is 7% faster than FlexPrefill but both remain slower than dense attention; by 64K, CRISP is 1.76× faster than dense.The reported crossover between routing overhead and sparse-attention savings falls between 8K and 64K.
  • Ablation: The full system is more robust than either isolated component: C_struct routing alone causes Llama regressions, while sink-aware selection recovers them.The ablation identifies an interaction between routing and VS selection.

6 Related Work

Related work spans fixed or offline sparse patterns, dynamic input-adaptive attention, and architectural alternatives that replace softmax attention. CRISP extends dynamic sparse attention with a formal account of the VS/PE routing dichotomy and mass-cliff interaction.

  • Fixed and Offline Sparse Attention: Early sparse methods use fixed structural patterns, while MInference profiles per-head patterns offline and generates runtime indices within those profiles.Offline assignment cannot adapt when sink-mass concentration varies across inputs or context lengths.
  • Dynamic Sparse Attention: FlexPrefill dynamically routes heads and allocates budgets at prefill time based on each input’s attention structure.Other dynamic methods track heavy hitters, use query-aware page routing, mix sparse patterns, approximate scores, or use locality-sensitive hashing.
  • Subquadratic Alternatives: Subquadratic alternatives replace softmax attention with linear or recurrent formulations, including state-space models and gated linear attention.These approaches change the architecture and usually require distillation or finetuning, whereas CRISP is training-free and retains exact softmax attention on selected blocks.
  • Theoretical Grounding: Prior theory linked attention concentration or entropy to representation and context-encoding efficiency without formally explaining the VS/PE dichotomy or cumulative thresholding.CRISP supplies that foundation by identifying the mass cliff as a structural consequence of autoregressive softmax attention.

7 Conclusion

CRISP addresses two structural limitations in dynamic sparse attention: indirect JSD routing and cumulative-threshold failure at the post-softmax mass cliff. Its sink-aware design improves retrieval performance and latency, while its assumptions remain bounded by architecture, head structure, scale, and prefilling scope.

  • Contributions: Cstruct reproduces JSD routing decisions while removing pooling matmul and KL-divergence overhead.It is a structural-mass proxy for routing heads between Vertical-Slash and Pooled-Estimation paths.
  • Contributions: Cumulative γ-thresholding inherently accumulates O(n) background noise at long contexts.CRISP replaces it with a sink-aware threshold grounded in the noise floor to separate task signal from architectural noise.
  • Results: CRISP recovers up to +28.0 pp on retrieval tasks, matches exact dense attention on InfiniteBench, and reaches up to a 5.30× latency speedup at 512k tokens.These outcomes establish the reported performance hierarchy for the evaluated sparse-attention setting.
  • Architectural Scope: Cstruct is not guaranteed to work when architectures suppress attention sinks, because its routing correspondence is empirical for current sink-having architectures.Sink-free architectures may require a different structural proxy.
  • Hybrid Heads: CRISP inherits binary VS/PE routing, so mixed-structure heads may be misrouted and softer confidence-weighted schemes remain future work.The sink-aware threshold can discard tokens that do not fit the VS pattern.
  • Scaling and Decoding: Evaluation beyond 8B models, beyond established benchmark contexts, and for token-level decoding remains future work.The current method addresses prefilling, while autoregressive decoding requires dynamic mass-cliff characterization.
  • Path Selection: CRISP’s improvements focus heavily on the VS path, leaving full PE-path improvements and dynamic α scheduling for future treatment.The stated open issue includes precision-coverage tradeoffs in aggregation tasks such as Llama RULER.

A FlexPrefill Baseline Algorithms

FlexPrefill uses JSD-based pattern routing and dual-direction cumulative thresholding for VS-head index selection. CRISP replaces these mechanisms with direct structural routing and sink-aware block-level thresholding to remove their stated overheads.

  • Baseline Algorithms: FlexPrefill’s baseline algorithms comprise JSD-based pattern search and dual-direction cumulative thresholding for VS heads.Algorithm 5 handles routing, while Algorithm 6 handles VS-head index selection.
  • Pattern Search: JSD routing compares attention estimates to choose between Vertical-Slash and Pooled-Estimation paths.The supplied algorithm excerpts include normalized vertical and diagonal scores and union selected indices with sinks and local positions.
  • Comparison with CRISP: CRISP uses a constant-time indexed slice reduction over the proxy attention map instead of JSD-based routing.This removes the O(nd/b) pooled matmul and O(n/b) KL-divergence overhead in the baseline routing lines.
  • Comparison with CRISP: CRISP replaces dual-direction cumulative thresholding with block-level sink-aware thresholding for VS-head selection.The replacement eliminates the baseline’s dual-direction decomposition.

B Entropy-Coverage Relationship

Entropy determines the effective support needed to reach a coverage threshold: concentrated heads need compact index sets, while diffuse heads need broad coverage. This relationship motivates routing low-entropy heads to VS and high-entropy heads to PE, while the mass-cliff analysis explains long-context noise growth.

  • Effective support size: Exponentiated entropy e^H(a) measures a distribution’s effective support size, ranging from approximately 1 for concentrated attention to n for uniform attention.The extremes correspond to one element holding most mass versus mass spread evenly across n elements.
  • Monotone scaling: Lower entropy reduces the number of tokens needed to achieve coverage γ, whereas higher entropy requires broader coverage.This monotone scaling links attention concentration to sparse index-set size.
  • Connection to routing: Low-entropy heads fit the VS path because they concentrate mass at sinks, vertical columns, and slash diagonals, while high-entropy heads fit PE because no compact pattern dominates.The routing dichotomy follows the different support requirements of concentrated and diffuse distributions.
  • Mass-cliff analysis: For long contexts where n ≫ k·e^Δ, each background token has mass approximately 1/n.The denominator is dominated by the many background tokens at logit z−Δ.
  • Mass-cliff analysis: N_garbage = γ_residual/ϵ ≈ γ_residual·n, demonstrating O(n) background-token accumulation at long contexts.The residual threshold is γ_residual = γ − a_sink − a_important.

D Additional Mass Cliff Examples

Additional visual and sensitivity analyses support CRISP’s treatment of the mass cliff and its robustness to threshold choices. The evidence also distinguishes diffuse PE-head behavior and records limitations of the visualization and evaluation scope.

  • Additional Mass-Cliff Examples: Across four additional layers and heads, the CRISP noise-floor criterion with α=1.0 isolates task-relevant signal without accumulating O(n) background noise.The examples exhibit the two structural failure modes of cumulative γ-thresholding at different cliff locations.
  • Additional Mass-Cliff Examples: Figure 5 attributes sink-only collapse and noise accumulation to a fixed threshold applied across heads with different cliff positions.This supports a structural limitation of cumulative thresholding rather than a calibration artefact.
  • τ_proxy Sensitivity: Varying τ_proxy from 0.15 to 0.25 changes InfiniteBench performance by less than 0.7pp and LongBench performance by less than 1.2pp.The reported insensitivity indicates stable Cstruct routing without careful per-model calibration.
  • α Sensitivity: Even at α=1.5, CRISP Pareto-dominates FlexPrefill γ=0.95 on aggregate accuracy while running faster.At 131k tokens, aggregate accuracy is 55.3 versus 55.0 and runtime is 21% faster.
  • PE Heads: PE-head profiles decay gently without a mass boundary, with top-50 blocks holding 15% to 80% of mass versus 99% for the contrasting VS head.This is the regime where a mean-based threshold has no sharp separation to exploit.
  • Caveats: The PE-head visualization characterizes concentration from top-50 sorted block masses but cannot recompute routing and covers only one model and input.It establishes distribution shape rather than variability.

G Per-Benchmark Pareto Plots

CRISP’s benchmark-level results are generally strong across models and tasks, while the per-benchmark view exposes a specific RULER tradeoff on Llama and robustness checks for architecture and noise-floor choices.

  • Per-benchmark comparison: CRISP α=1.0 leads on InfiniteBench and LongBench, but sits marginally below both FlexPrefill settings on RULER for Llama.The per-benchmark plot reveals this task-specific precision-coverage tradeoff, which aggregate results conceal.
  • Architecture transfer: On Qwen3-4B-Instruct-2507, CRISP exceeds dense attention on InfiniteBench by +2.6 pp and comes within 0.30 pp of dense on LongBench.It also remains within ±1.7 pp on RULER across all six context lengths under the same configuration.
  • Noise-floor variant: Mean and median noise floors remain within ±0.7 pp of each other on every benchmark, with neither dominating.The authors retain the mean because it preserves the interpretation of α=1.0 as selecting above-average residual mass, despite a possible clumpy-noise failure mode.
  • InfiniteBench: CRISP achieves parity with exact dense attention on InfiniteBench across both evaluated models.The full InfiniteBench results compare CRISP α=1.0 against FlashAttention, MInference, and FlexPrefill.
  • LongBench: CRISP retains the highest mean LongBench score, while FP 0.97 yields only marginal gains over FP 0.95 at higher latency.This indicates that the higher FlexPrefill coverage setting does not improve the overall efficiency-accuracy tradeoff enough to offset its latency cost.
  • RULER: CRISP wins RULER outright on Qwen and remains competitive on Llama.The full results are reported separately by context length rather than only through an aggregate benchmark view.
Loading 2609.01925v1…