Multi-layer Indexer: Overlapping Selection and Attention in DeepSeek Sparse Attention

Summary (Overview)

  • Core contribution: The paper introduces the Multi-layer Indexer (MLI), a drop-in scheduling technique that overlaps the indexer scan with attention computation in DeepSeek Sparse Attention (DSA), eliminating the serial dependency between selection and attention at each layer.
  • Key insight: Adjacent DSA layers select nearly identical token sets (Jaccard overlap ~0.42 on DeepSeek-V3.2, ~0.26 on GLM-5), so a layer can attend the selection produced by a previous indexer layer rather than waiting for its own.
  • No training required: MLI needs no retraining and no new weights; it changes only which selection each layer attends, leaving all indexer arithmetic and selections unchanged.
  • Composition with IndexCache: MLI composes with IndexCache (cross-layer indexer reuse), yielding up to 14.5% faster decode on DeepSeek-V3.2 and 9.8% on GLM-5 at retention 1/2, with quality staying within a few percentage points of IndexCache.
  • Free retention halving: At retention 1/r1/r, IndexCache+MLI is faster than IndexCache at 1/2r1/2r while attending twice as many fresh selections, reaching 1.32× the unmodified model's throughput at 128K context and retention 1/4.

Introduction and Theoretical Foundation

Background

DeepSeek Sparse Attention (DSA) is the attention mechanism behind DeepSeek-V3.2 and the GLM-5 family. At each layer, a lightning indexer with HIH_I small heads scores every cached token:

It,n=∑h=1HIwt,hReLU⁡(qt,hI⋅kn,hI)I_{t,n} = \sum_{h=1}^{H_I} w_{t,h} \operatorname{ReLU}\left(\mathbf{q}_{t,h}^I \cdot \mathbf{k}_{n,h}^I\right)

where It,nI_{t,n} is the indexer's score for query tt and cached token nn, the superscript II marks the indexer's own projections, hh indexes its HIH_I heads, and qt,hI,kn,hI\mathbf{q}_{t,h}^I, \mathbf{k}_{n,h}^I are low-rank projections of the layer input with wt,hw_{t,h} a per-head weight.

The Problem

The layer keeps the set StS_t of the k=2048k=2048 highest-scoring tokens and runs sparse attention over those tokens only. This creates a serial dependency: attention cannot begin until the top-k is known. While sparse attention's cost is flat in sequence length LL, the indexer scans all LL keys—at 128K context, the scan constitutes roughly two-thirds of the attention-side layer cost.

Key Observation

The cost of the indexer per decode step factors into two independent components:

  1. How many indexers run (addressed by IndexCache, which keeps indexers on a fraction 1/r1/r of layers)
  2. How long each indexer is waited for (addressed by MLI)

Since adjacent layers select strongly overlapping token sets, a layer's attention need not wait for its own selection—an earlier layer's selection suffices.

Methodology

The MLI Schedule

Let SfS_f denote the top-2048 tokens selected by full layer ff, and F⊆{1,…,N}F \subseteq \{1, \ldots, N\} be the set of full layers. For any layer ℓ\ell, let p(ℓ)p(\ell) be the nearest full layer at or before ℓ\ell, and πk\pi_k step back kk full layers along FF (the lag depth). Every layer attends:

layer ℓ attends Sσ(ℓ),σ(ℓ)=πk(p(ℓ))\text{layer } \ell \text{ attends } \mathcal{S}_{\sigma(\ell)}, \quad \sigma(\ell) = \pi_k(p(\ell))

Key properties:

  • With k=0k=0: standard DSA (r=1r=1) or IndexCache (r>1r>1)
  • With k≥1k \geq 1: MLI when r=1r=1, or the composition when r>1r>1
  • The first kk full layers run the standard schedule (no predecessor exists)

Realization in the Decode Graph

The implementation in SGLang's DSA decode path:

  1. Two-stream execution: At a full layer, the indexer (projections, scan over paged index-key cache, top-k) is enqueued on a second CUDA stream while attention proceeds on the main stream with the assigned selection.
  2. CUDA graph capture: Cross-stream edges are ordinary graph dependencies, so the schedule is captured once and replayed without host involvement.
  3. Memory safety: References to the indexer's inputs/outputs are held until the join point (k full layers later) to prevent premature memory reuse.

Distillation for Quality Recovery

To recover selection quality, only the indexers (≈0.5% of parameters) are trained so that a full layer's selection matches what its consumer layers would have selected. The per-layer loss combines KL divergence and a listwise Plackett–Luce term:

Lf=1∣C(f)∣∑c∈C(f)[λKL(pc∥p^f)+(1−λ)LPL(πc;I^f)]\mathcal{L}_f = \frac{1}{|\mathcal{C}(f)|} \sum_{c \in \mathcal{C}(f)} \left[ \lambda \mathrm{KL}\left(p^c \| \hat{p}^f\right) + (1-\lambda) \mathcal{L}_{\mathrm{PL}}\left(\pi^c; \hat{I}^f\right) \right]

where C(f)\mathcal{C}(f) is the set of consumer layers, pc,p^fp^c, \hat{p}^f are softmax teacher/student scores, πc\pi^c is the teacher's top-k ranking, and λ=0.5\lambda = 0.5.

Fused Kernel

A fused decode kernel runs sparse attention and the indexer's prefix scan in a single launch, so the scan never competes for streaming multiprocessors with a separate launch. This helps DeepSeek-V3.2 (4–6 percentage points faster) but hurts GLM-5 (which has half as many index heads per rank).

Empirical Validation / Results

Throughput Gains (Single Request)

Table 1: Per-request decode throughput at single concurrency (percentage change over base; base in tok/s):

DeepSeek-V3.2 retention10K IC+MLI60K IC+MLI120K IC+MLI128K IC+MLI
none (base, tok/s)89.188.085.785.5
all (MLI alone)+21.5+19.8+26.1+25.1
1/2+11.5+25.3+12.3+25.2+13.6+30.1+13.7+29.8
1/4+19.1+27.3+20.5+28.3+22.8+32.5+22.7+32.3
1/8+23.4+28.5+25.2+29.8+27.9+33.7+28.0+33.7
1/16+25.3+26.3+27.1+28.2+30.2+31.6+30.2+31.7
1/32+26.1+26.9+28.2+28.5+31.4+32.2+31.4+32.2
GLM-5 retention10K IC+MLI60K IC+MLI120K IC+MLI195K IC+MLI
none (base, tok/s)68.567.866.565.0
all (MLI alone)+14.6+14.4+15.6+16.8
1/2+8.2+17.6+8.7+17.9+9.8+19.8+10.6+21.4
1/4+13.7+18.8+14.2+19.2+15.9+21.6+17.7+23.7
1/8+16.3+19.4+17.1+20.4+19.3+22.8+21.3+25.0

Key findings:

  • Equal retention: MLI+IndexCache is faster than IndexCache at every retention, with gains largest where indexers are densest (14.5% at 1/2 on DeepSeek-V3.2)
  • Free halving: At retention 1/r1/r, MLI+IndexCache beats IndexCache at 1/2r1/2r—at 128K and 1/4, it achieves 1.32× base vs. IndexCache's 1.28× at 1/8
  • Gains grow with context and persist on IndexCache's searched patterns

Quality Results

Table 2: Quality at reported retentions (percentage change over base; base = absolute score):

DeepSeek-V3.2LongBench IC+MLIRULER IC+MLILB v2 IC+MLI
none (base)0.4490.9750.501
all (MLI alone)-0.0-2.1-0.4
1/2-0.2-0.3-2.7-4.0+0.8+0.4
1/4-0.3+0.5-0.9-0.4-1.6-0.4
1/8-0.1-1.1-0.7+0.3-0.4+0.4
GLM-5LongBench IC+MLIRULER IC+MLILB v2 IC+MLI
none (base)0.4530.9410.477
all (MLI alone)-0.2+2.3-0.8
1/2-1.2-1.1+2.9+2.1+1.2+0.4
1/4-0.2-0.4+0.7+1.6+2.5-0.4
1/8-0.0-1.4+1.6-1.3+0.8-1.7

Quality findings:

  • MLI alone stays within 0.4–0.8 points of base on LongBench and LongBench v2
  • On top of IndexCache, MLI costs at most 1–2 points
  • Distillation is decisive at the "cliff": at 1/16 on GLM-5, it turns IndexCache's collapse (LongBench −11.5, RULER −61, needle 0.00) into recovery (LongBench −0.1, RULER −7.4, needle 1.00)

What Limits the Gain

  • MLI hides about four-fifths of the exposed scan on DeepSeek-V3.2 and two-thirds on GLM-5
  • The first full layer's scan remains serial (no earlier layer to overlap)
  • The remaining limit is memory bandwidth: the scan hides only in HBM bandwidth that attention and feed-forward leave idle
  • At full-KV-cache batch sizes (64 requests), the gain vanishes as requests saturate bandwidth

Theoretical and Practical Implications

Theoretical Significance

  1. Selection-attention decoupling: The paper demonstrates that in DSA, the indexer-attention dependency is on the support of the softmax, not on shared computation—breaking this dependency is both possible and beneficial.

  2. Shared primitive argument: The indexer score and attention logit are both low-rank bilinear interactions of the layer input. The indexer is a "second consumer" of what attention already computes, suggesting DSA models should be co-designed around this shared primitive rather than placing a selector ahead of attention.

  3. Compositionality of optimizations: The two cost factors (number of indexers × wait time per indexer) multiply, and MLI's overlap technique composes orthogonally with IndexCache's layer-skipping.

Practical Implications

  1. Drop-in deployment: MLI requires no retraining, no new weights, and runs inside SGLang's production decode graph with unchanged kernels.

  2. Production serving benefits: At long contexts (where KV memory caps concurrency at 2–6 requests), MLI provides substantial throughput gains exactly where the indexer scan is most exposed.

  3. Architecture guidance: The fused kernel's success on DeepSeek-V3.2 (but not GLM-5) provides evidence for co-designing DSA models around the shared bilinear primitive from the start.

Conclusion

The Multi-layer Indexer (MLI) eliminates the serial dependency between the indexer scan and attention in DSA by having each layer attend the selection of a previous indexer layer. The change is drop-in—no retraining, no new weights—and composes with IndexCache.

Key takeaways:

  • Faster at equal retention: Up to 14.5% faster decode on DeepSeek-V3.2 and 9.8% on GLM-5 at retention 1/2
  • Free halving of indexer budget: At retention 1/r1/r, MLI+IndexCache is faster than IndexCache at 1/2r1/2r while attending twice as many fresh selections
  • Quality preserved: Within a few percentage points of IndexCache across LongBench, RULER, and LongBench v2
  • Future direction: The indexer only recomputes the bilinear interaction attention already forms—co-designing DSA around this shared primitive is the natural next step

Limitations: The gain diminishes with batch size (bandwidth-bound), the fused kernel helps only DeepSeek-V3.2, and GLM-5.2 (which ships IndexShare natively) is out of scope for equal-footing comparison.

Related papers