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

CRISP. Cliff-awaRe Input-adaptive Sparse Prefilling with Structural-Mass-Motivated Routing. By Huu Huy Nguyen and six others, from the University of Oregon, Adobe Research, and one other institution. Published on the first of September. No code repository is linked to it.

In long-context LLM inference, the attention prefilling phase scales quadratically, which makes self-attention a severe computational bottleneck. Traditional sparse attention methods ease this with fixed patterns or with offline profiling, but neither can adapt to attention structure that depends on the input. More recent dynamic methods route heads to sparse patterns in real time. They carry two weaknesses of their own. They rely on indirect routing proxies that add overhead, and their budget allocation overlooks the hierarchy of mass that exists after the softmax. The first weakness costs time on every routing decision. The second affects which positions get kept once a head has been routed, and so how much of the budget is spent on positions that carry signal.

CRISP, short for Cliff-awaRe Input-adaptive Sparse Prefilling, keeps the dynamic routing paradigm and addresses two structural challenges inside it. The first is that the routing decision can be read directly off the structure of the proxy attention map, with no separate measure needed. The second is what the authors call the post-softmax mass cliff, which decides how a sparsity budget should be spent.

For routing, CRISP replaces Jensen-Shannon Divergence routing, JSD for short, with a structural proxy called C struct. It measures mass at positions compatible with Vertical-Slash patterns. It reproduces the routing decisions JSD would have made, while eliminating both the pooled matrix multiply and the KL divergence computation that follows it.

For budgets, the authors formalise the mass cliff and show theoretically that thresholds based strictly on cumulative coverage accumulate background noise of order n at long contexts. Keep adding coverage until a target is met, and the noise comes along with it. CRISP navigates this with a sink-aware threshold grounded in the noise floor. Rather than a fixed share of total coverage, the cutoff is tied to the level of the background itself, so the longer the context, the more the difference matters.

Testing spans InfiniteBench, RULER and LongBench, on two model families. CRISP is the strongest sparse method overall, and on retrieval-heavy benchmarks it matches or exceeds exact dense attention. Over baselines, it recovers up to twenty-eight percentage points on retrieval tasks. It also reaches up to a five point three times attention speedup at five hundred and twelve thousand tokens. The authors attribute that speedup primarily to eliminating the order n noise during selection, while the structure of the attention is preserved.

Both fixes come from reading one object more closely: the attention map's own structure. One reading makes a costly divergence calculation unnecessary for routing. The other explains why summing coverage up to a threshold lets noise in as contexts grow, and swaps it for a threshold that knows where the noise floor sits. Less work in routing, less noise in selection, and the speedup follows from the second.