Yifan Guo Research notes

Sparse attention

Interleaved DeepSeek Sparse Attention

DeepSeek Sparse Attention turns long-context attention into a token-level retrieval problem. The attention itself becomes sparse, but exact top-k selection introduces a global dependency that is difficult to scale across context-parallel GPUs.

Block-sparse attention selects groups of tokens. With block size B, a highly tuned selector examines roughly N/B candidates. DSA is finer-grained: it ranks individual tokens and therefore examines N candidates. As context grows, the ranking path can become a first-order contributor to time-to-first-token.

Where DSA spends its work

DSA separates selection from attention. A lightweight indexer scores the historical sequence and returns token indices. Sparse MLA then gathers only the selected rows from its latent KV cache. This saves attention work, while leaving the indexer responsible for scanning the sequence.

DeepSeek Sparse Attention dataflow The current hidden state creates indexer queries and MLA queries. The indexer scores the sequence, selects top-k token indices, and Sparse MLA gathers only those KV rows. hidden state xt INDEXER score all tokens qI · kI + token gates SELECTION top-k token IDs, not KV MLA PATH compressed KV latent cache for all tokens SPARSE MLA gather selected KV attention over k rows output ot The score path decides where the attention path reads.
Figure 1. The indexer decides which historical token IDs Sparse MLA reads. The scoring path and the attention path use separate representations.

This distinction matters in a distributed system. When context is split across GPUs, each card sees only a local shard. It can identify its own strongest candidates, but it cannot know which of them belong to the global top-k.

The exactness barrier

The conventional solution has two ranking stages. Every GPU computes a local top-k, the candidates are gathered, and a second top-k selects the global winners. The second stage is exact, but it also forms a synchronization barrier: communication must complete before sparse attention can begin.

Global top-k bottleneck Four GPUs each run local top-k. Their candidates are gathered and ranked a second time to produce global top-k for Sparse MLA. CONTEXT SHARDS GPU 0 · C0local top-k GPU 1 · C1local top-k GPU 2 · C2local top-k GPU 3 · C3local top-k ALL-GATHER G × k candidates scores + global token IDs SECOND RANKING global top-k synchronizing decision Sparse MLA exact k indices global dependency barrier communication must finish before exact ranking can finish
Figure 2. Exact distributed selection gathers G × k candidates and ranks them again. The second ranking stage creates the global dependency.

This barrier is especially visible at low batch size and long sequence length. Those are precisely the settings where context parallelism is useful for reducing latency and distributing KV storage.

The observation behind the relaxation

To look for a way around this barrier, I start from one observation in our experiments: k = 2048 is a training setting, but it is not necessarily the best inference setting. Model quality improves as inference-time k increases. The improvement is steep before 2048, then continues more slowly toward full attention.

Qualitative performance curve over top-k Performance rises quickly before k equals 2048 and more slowly after, approaching full attention at sequence length. inference-time k model performance 2048 512 sequence length full attention fast gain slower gain
Figure 3. Qualitative form of the observed trend. This diagram communicates the shape of the observation and does not encode measured values.

My hypothesis comes from the training history of DeepSeek-V3.2. The model was not sparse from scratch; it was continuously pretrained from a full-attention base model. How strongly it adapts to sparsity should therefore depend on the relative training intensity of these two stages:

training intensity of continued pretraining for sparse adaptation training intensity of first-stage pretraining for the full-attention base model

When this ratio is limited, sparse adaptation changes how the model retrieves context without completely removing the full-sequence perception inherited from the base model. This gives a plausible reason why increasing k at inference time can still help.

Can we deliberately include some additional, less important tokens outside exact top-k, while preserving high recall of the important tokens inside top-k?

If the answer is yes, we no longer need an exact global boundary. We can relax the candidate set, remove the second global top-k, and break the distributed dependency barrier.

Local top-m, then one gather

Interleaved DSA asks every GPU for a smaller local top-m set. The sets are gathered and their union is passed directly to Sparse MLA. There is no second global ranking stage. The union can be larger than k, but it avoids placing an exact top-k decision on the critical path.

Exact distributed DSA

GPU 0top-k GPU 1top-k GPU 2top-k GPU 3top-k all-gather G × kcandidate pool second top-k Sparse MLA · k tokens
Local top-k → gather G × k candidates → second top-k → Sparse MLA.

Interleaved DSA

GPU 0top-m GPU 1top-m GPU 2top-m GPU 3top-m all-gather union≤ G × m token indices Sparse MLA directly no global second top-k extra tokens are the relaxation
Local top-m → gather the union → Sparse MLA directly.

The useful operating point is the smallest m that retains the global top-k with a chosen confidence. Smaller m reduces both selection work and communication; larger m gives more recall margin.

Why interleaving matters

Important context is not uniformly distributed. Attention often concentrates on contiguous semantic regions. With contiguous context shards, one GPU can receive most of a relevant region and therefore most of the global winners. A fixed local m then becomes either unsafe for that GPU or wastefully large for every other GPU.

Round-robin interleaving assigns token i to GPU i mod G. Contiguous neighborhoods are spread across cards, making the number of important tokens per GPU more balanced.

Contiguous and interleaved context placement A clustered important region falls mostly on one GPU with contiguous placement, but is distributed across all GPUs with interleaved placement. SEQUENCE · IMPORTANT REGION IS HATCHED CONTIGUOUS GPU 0 · tokens 0–41 important GPU 1 · tokens 5–95 important GPU 2 · tokens 10–140 important GPU 3 · tokens 15–190 important INTERLEAVED · token i → GPU (i mod G) GPU 00 · 4 · 8 · 12 · 161–2 important GPU 11 · 5 · 9 · 13 · 171–2 important GPU 22 · 6 · 10 · 14 · 181–2 important GPU 33 · 7 · 11 · 15 · 191–2 important Interleaving converts spatial clustering into a more balanced per-GPU candidate load.
Figure 4. Interleaving converts a spatially clustered important region into a more balanced per-GPU candidate load.

Choosing the local list size

Let G be the number of GPUs, C the complete context, Cg the tokens assigned to GPU g, K the desired global top-k, and γ the target coverage confidence. We require the union of local top-m sets to cover the global top-k:

P( Top(C,K) ⊆ ⋃g=0G−1 Top(Cg,m) )>γ
Gnumber of GPUs
Ccomplete context
Cgcontext on GPU g
Kglobal top-k
γcoverage confidence

Writing m = K/G + ε, the goal is to minimize the safety margin ε while satisfying the coverage constraint. Under the probability model in our derivation, the local list size can be estimated as:

m=⌈ KG+ Z 1−1−γG · K(G−1) G +0.5⌉

Interleaving supports this estimate by making the load-balancing assumption more plausible when attention is locally clustered. The algorithm replaces a globally exact boundary with a probabilistic coverage guarantee, while Sparse MLA still receives the token indices it needs.

The systems trade-off is simple: admit a controlled number of extra candidates so that sparse attention no longer waits for a global second top-k.

Further reading. The full derivation and experiments are available in the early workshop paper. The latest camera-ready version for NeurIPS 2026 is forthcoming.