Sparse Attention Still Has a Dense Problem

Using the indexer’s own history to cut the cost of deciding where to attend.

Read the paper

Authors: Yao Fu, Jiahan Chang, Yueying Li, Ritchie Zhao, Bita Darvish Rouhani

Attending to a few still means scoring them all

DeepSeek Sparse Attention (DSA) made long-context attention cheap. Core attention reads only a top-K subset of the cached context KVs. But to find that subset, a lightweight indexer scores every context token, at every decoding step, in every DSA layer. Per step, core attention’s work stays fixed while the indexer’s grows linearly with context length. Even with the 4× sequence-length compression in DeepSeek-V4’s compressed sparse attention (CSA) layers, the indexer remains a major contributor to decode latency at 512K–1M tokens.

Must the indexer score the entire context to find its top-K?

It does not have to. SPIN, the Shadow Predictive Indexer, uses the indexer’s own score history to decide which context KV blocks are worth scoring at each decoding step. Within those blocks, the indexer still computes fresh scores and makes the final top-K choice. SPIN keeps the score history fresh with random exploration, gives more blocks to the layers that are harder to predict, and works with speculative decoding.

At 40% target block sparsity, SPIN keeps task quality comparable to the dense indexer across long-context and agentic benchmarks, including multi-needle retrieval at 512K, and raises output throughput by 8.4% when serving DeepSeek-V4 Flash in vLLM.

Indexer selections follow patterns

Indexer selections show clear patterns across decoding steps. Some keys are selected again and again, forming the vertical lines below. In DeepSeek-V3.2, some selections also move with the query at a fixed offset, forming diagonal bands.

Figure 1. Indexer top-K selection masks from one DSA layer per model on a 9.7K-token summscreenfd prompt, showing 1,400 cached key positions. Each row is a decoding step, progressing downward; yellow marks selected positions. In DeepSeek-V4, the horizontal positions are compressed KV slots.

These patterns make each step’s top-K selection partially predictable from earlier steps. Scores from the same layer at earlier steps predict the current top-K far better than scores from the previous layer at the current step.

Score only where history points

SPIN turns these patterns into a lightweight filter in front of the indexer. It needs no retraining and adds no learned parameters. At each decoding step, SPIN does three things.

1. Accumulate history. Keep exponential moving averages (EMAs) of past indexer scores along two axes, namely fixed positions (the vertical lines) and offsets from the query (the diagonal bands).
2. Select blocks. Predict each KV block’s importance from those statistics, then fill the layer’s block budget (the blocks it scores at each step) with the top-ranked blocks and a few randomly chosen ones for exploration. Operating on KV blocks (64 compressed KV slots each, matching a 256-token KV-cache page) instead of individual KVs keeps SPIN efficient to implement in serving frameworks.
3. Score the current query. Run the indexer only on the selected KV blocks, then apply the existing top-K operator for core attention.

SPIN can run block prediction and EMA updates asynchronously, overlapped with the forward pass of other layers.

Figure 2. SPIN reduces the number of KV blocks scored by the indexer. Blocks not selected by SPIN remain cached. Block counts are illustrative.

SPIN is configured with a target block sparsity, the percentage of KV blocks to skip. At 30–40% target block sparsity, SPIN keeps task quality comparable to an all-keep baseline that scores every block, across standard long-context and agentic benchmarks (Table 1), even without exploration.

Table 1. Task scores on a 0–100 scale; higher is better. DeepSeek-V4 Flash unless labeled Pro. These evaluations use SPIN without exploration; the paper gives each benchmark’s evaluation protocol.

Exploration keeps the history fresh

A skipped KV block receives no new indexer scores, so its history stops updating. After many skipped steps, its predicted score goes stale, and the block can stay skipped even after it becomes important. SPIN refreshes skipped blocks within the same block budget by reserving a small share of it for exploration, which sends the indexer a few blocks outside the top-ranked set. We call it the exploration share and use 5% by default.

MRCRv2, which asks the model to retrieve several needles from a long multi-turn conversation, is where exploration matters. Figure 3 compares random exploration with two alternatives on this benchmark. Staleness-score exploration ranks blocks by staleness and predicted importance, and block-age exploration picks the least recently observed blocks. All three score well above no exploration at 30–50% target block sparsity. Whether SPIN explores matters far more than how it picks the blocks. SPIN uses random exploration, which needs no per-block age tracking, even though block-age exploration scores higher at 512K and 1M. At both 512K and 1M context, exploration keeps MRCRv2 task quality close to all-keep up to 30% target block sparsity, and recovers most but not all of the gap beyond that.

Figure 3. DeepSeek-V4 Flash on 8-needle MRCRv2. Each score averages 40 seeded repeats over 100 fixed prompts. All exploration methods use a 5% exploration share. Error bars and the grey all-keep band show 95% confidence intervals of the mean. Staleness score ranks blocks by staleness and predicted importance; Block age picks the least recently observed blocks.

The right exploration share grows with sparsity. At higher sparsity, the same exploration share covers fewer blocks while more blocks are skipped, so each skipped block is revisited less often. With a 20–30% share, task quality stays close to all-keep at 50% target block sparsity (Figure 4). Raising the share comes at no cost in throughput, because it only reallocates blocks within the block budget and leaves the block sparsity unchanged.

Figure 4. DeepSeek-V4 Flash on 8-needle MRCRv2 with random exploration and a uniform budget, at 256K context (50%, 60% and 70% target block sparsity) and 512K context (40% and 50%). Each point averages 40 seeded repeats over 100 fixed prompts. Error bars and the grey all-keep bands show 95% confidence intervals of the mean.

Per-layer block budgets

Not all layers are equally predictable. Figure 5 shows the miss rate (the fraction of the dense indexer’s top-K slots that fall into skipped blocks) at each layer, with the same target block sparsity in every layer. Some layers miss many times more than others, and the hardest layers are consistent across inputs.

Figure 5. Per-layer miss rate of SPIN on DeepSeek-V4 Flash at 50% target block sparsity, decoding 16 prompts from each input set. Miss rate is the fraction of the dense indexer’s top-K slots that fall into skipped blocks. Token counts are median prompt lengths. Only the 21 CSA layers, the only layers with an indexer, are shown.

SPIN sizes a per-layer block budget, keeping the total budget across all layers at the same user-specified target block sparsity. The allocation minimizes the worst layer’s miss rate, not the average. Empirically, this objective performs better, scoring about 1.28 points higher on average than minimizing the average layer’s miss rate across 50–70% target block sparsity (the Pareto points in Figure 6).

Every P decoding steps, where P is the probe period, SPIN runs a dense probe step that scores all blocks to measure each layer’s miss curve (its miss rate at each budget). A background thread recomputes the budgets whenever the miss curves drift and publishes them to a device-side table that works with CUDA graphs, so no offline search is needed. The probe period trades quality against throughput. Recomputing the budget is cheap, but each dense probe step scores every block, so probing more often improves quality at the cost of more dense steps.

Per-layer block budgets pay off most at high sparsity. With 5% exploration and a probe period of 8 on MRCRv2 at 512K context, they keep task quality close to all-keep at 57% and 61% effective block sparsity, the target block sparsity with every probe step counted as dense, well above a uniform budget at similar sparsity (Figure 6).

Figure 6. DeepSeek-V4 Flash on 8-needle MRCRv2 at 512K context with a 5% exploration share, 5 seeded repeats over 100 fixed prompts. Effective block sparsity accounts for the dense probe every P steps. Error bars and the grey all-keep band show 95% confidence intervals.

SPIN works with speculative decoding

Speculative decoding is an essential optimization for the decode stage. It uses a smaller drafter to generate multiple draft tokens, which are then verified by the main model in a single decode step. Not all draft tokens are accepted. With speculative decoding, a DSA indexer receives several queries in a single step. SPIN predicts a block mask for each query and uses their union as one shared indexer input. Adjacent queries select largely overlapping blocks, so the union adds few blocks. After verification, SPIN only applies the EMA updates generated by accepted tokens in order, discarding EMA updates from rejected tokens. With DeepSeek-V4’s native multi-token prediction and 3 draft tokens, SPIN keeps 39.51% realized block sparsity, the fraction of blocks skipped after the union, at a 40% target, with no visible change in draft-token acceptance.

Faster decoding in vLLM

We integrated SPIN into vLLM and measured DeepSeek-V4 Flash on 8 NVIDIA B300 GPUs serving a long cached context.

Table 2. MRCRv2 512K task quality and serving performance. TP8 with expert parallelism, 507K cached + 5K new input tokens, 96 concurrent requests, 16K output tokens per request, CUDA graphs with MTP disabled. Percentages are relative to all-keep. The exploration share is 20% at 40% and 50% uniform sparsity, and 5% otherwise.

Throughput gain grows steadily with block sparsity (Table 2), so sparsity that SPIN keeps at high quality turns directly into serving speed.

Per-layer block budgets push the block sparsity that keeps MRCRv2 close to all-keep higher (Figure 6), and at that sparsity they also outpace every uniform setting in Table 2.

Conclusion

Sparse attention made attending cheap. SPIN makes deciding where to attend cheaper by remembering what the indexer has already found, keeping that memory fresh with exploration and giving the harder-to-predict layers more of the block budget. Combining history with current-query or cross-layer signals may reduce worst-case misses under sudden attention shifts and is a natural next step.

For the full algorithm, benchmark sweeps and design ablations, read SPIN: Shadow Predictive Indexer for Sparse Attention.