CRISP Makes Long-Context Sparse Prefilling Structure-Aware

Introduction

Long-context inference is often constrained before token generation even begins. During attention prefilling, the model must process the entire input and establish interactions among tokens. Because dense self-attention scales quadratically with sequence length, this stage becomes increasingly expensive as context windows grow. Sparse attention reduces the workload, but fixed patterns do not adapt to the input, while offline profiling can miss the structure of a new prompt. CRISP, or Cliff-awaRe Input-adaptive Sparse Prefilling, focuses on making dynamic sparsity cheaper and more faithful to the attention distribution.

Two structural changes

• A direct routing signal. Existing dynamic approaches can use a pooled matrix multiplication followed by Jensen-Shannon Divergence, or JSD, to estimate which sparse pattern best fits an attention head. CRISP argues that the decision is already visible in the structure of the proxy attention map. Its C_struct metric measures mass at positions compatible with a Vertical-Slash pattern. According to the paper, this structural score reproduces the routing choices of JSD while removing both the pooled matmul and the subsequent divergence calculation.

• A threshold that accounts for sinks and noise. The paper formalizes a post-softmax mass cliff: a small number of positions may carry clearly larger mass, followed by a long tail of low-level background values. A strictly cumulative coverage rule keeps adding positions until a target percentage is reached. At long context lengths, that tail can accumulate O(n) background noise, expanding the selected set without adding comparable information. CRISP instead derives a sink-aware threshold from the noise floor, aiming to retain meaningful structure without treating the whole background as useful attention.

Results and implications

Across InfiniteBench, RULER, and LongBench, evaluated on two model families, CRISP is reported as the strongest sparse method overall in the supplied material. On retrieval-heavy tasks, it matches or exceeds exact dense attention and recovers up to 28.0 percentage points over baselines. At a context length of 512k tokens, the paper reports up to a 5.30x speedup for the attention component. The stated driver is primarily the elimination of O(n) noise during selection while preserving the structural organization of attention.

The broader lesson is that dynamic sparse inference has two separate costs: deciding where to route and deciding how many positions to retain. CRISP addresses both. Its first contribution reduces routing overhead by using a structural proxy; its second revisits the assumption that cumulative mass is a reliable budget signal at extreme context lengths. That distinction could matter for serving systems where routing must happen online and every extra selected position affects latency and memory traffic. The available material does not establish how the method behaves across all architectures, hardware platforms, or alternative sparse patterns, so those remain open evaluation questions.

Source: Hugging Face Daily Papers