Summary (Overview)

  • ADIndex is a novel indexing method for DeepSeek Sparse Attention (DSA) that reduces redundant full-prefix scans through layer-adaptive token bank sharing across neighboring queries.
  • The method is motivated by two key observations: (1) pronounced inter-layer heterogeneity in cross-query retrieval overlap, and (2) distillation-driven coverage gains where lightweight distillation improves Top-K token coverage.
  • ADIndex integrates three components: layer-wise calibration of group sizes and bank budgets, group-level distillation to train lightweight group indexers, and a low-latency inference strategy with shared token banks.
  • Experiments on DeepSeek-V3.2 and GLM-5.1 demonstrate near-lossless task performance on LongBench, LongBench v2, and RULER, with prefill and decoding kernel speedups up to 6.22× and 3.40× at 256K context, and an end-to-end serving speedup of 1.54× at 128K.
  • The distilled group indexer uses only one-eighth as many indexing heads as the original DSA indexer while improving Top-K coverage.

Introduction and Theoretical Foundation

Background and Motivation

Long-context capability is essential for modern LLMs, but full self-attention scales quadratically with sequence length. DeepSeek Sparse Attention (DSA) addresses this by using a lightweight token-wise indexer to score all tokens in each query's causal prefix and select Top-K tokens, which are then processed by a Sparse MLA operator.

The Indexing Bottleneck

Despite reducing attention computation, DSA's indexer introduces substantial overhead:

  • Prefill complexity: O(L2)\mathcal{O}(L^2) for indexing
  • Decoding complexity: O(L)\mathcal{O}(L) per query
  • At 128K context, the indexer alone accounts for 54.2% of total prefill GPU time

Key Theoretical Observations

1. Layer-wise overlap heterogeneity: Even with fixed group size GG and KK, the overlap among neighboring queries' Top-K selections varies substantially across layers. For G=16G=16, K=2048K=2048, per-layer maximum union sizes range from 4,486 to 22,688 on 128K inputs, all below the no-overlap upper bound of GK=32,768GK = 32,768.

2. Distillation-driven coverage gains: Lightweight distillation enables the shared bank to cover a larger fraction of each query's Top-K tokens selected by the original DSA indexer, with gains remaining robust across different indexing-head counts.

Methodology

1. Layer-wise Reuse Calibration

Token Bank Capacity Estimation: For each candidate group size GG, the maximum union size across consecutive query groups is computed:

Uℓ,Gmax⁡=max⁡t∈AG∣⋃r=0G−1Tℓ,t+r∣U_{\ell,G}^{\max} = \max_{t \in \mathcal{A}_G} \left| \bigcup_{r=0}^{G-1} \mathcal{T}_{\ell,t+r} \right|

Configuration Selection: For each layer ℓ\ell, the configuration maximizing indexing speedup is selected subject to capacity constraints:

(Gℓ∗,Pℓ∗)=arg max⁡G∈{4,8,16}P∈{4K,8K,16K}Uℓ,Gmax⁡≤PS(G,P;128K)(G_{\ell}^{*},P_{\ell}^{*}) = \operatorname*{arg\,max}_{\substack{G\in\{4,8,16\} \\ P\in\{4\mathrm{K},8\mathrm{K},16\mathrm{K}\} \\ U_{\ell,G}^{\max}\leq P}} S(G,P;128\mathrm{K})

2. Group-level Distillation

Group Indexer Distribution: Query latents are aggregated using max–min–mean pooling, and hidden representations are averaged:

cˉtQ=Wpool[ctQ,max;ctQ,min;ctQ,mean],hˉt=1Gℓ∑i∈Gthi\bar{\mathbf{c}}_{t}^{\mathrm{Q}} = \mathbf{W}_{\mathrm{pool}}[\mathbf{c}_{t}^{\mathrm{Q,max}}; \mathbf{c}_{t}^{\mathrm{Q,min}}; \mathbf{c}_{t}^{\mathrm{Q,mean}}], \quad \bar{\mathbf{h}}_{t} = \frac{1}{G_{\ell}}\sum_{i\in\mathcal{G}_t}\mathbf{h}_i

The group indexer computes scores using fewer heads (HSIH_S^I):

Iˉt,s=∑j=1HSIwˉt,jIReLU(qˉt,jI⋅ksI),s≤t\bar{I}_{t,s} = \sum_{j=1}^{H_S^I} \bar{w}_{t,j}^{I} \mathrm{ReLU}\left(\bar{\mathbf{q}}_{t,j}^{I} \cdot \mathbf{k}_{s}^{I}\right), \quad s \leq t

Aggregated Teacher Distribution: Per-query teacher distributions are aggregated using element-wise maximum:

πi,s=exp⁡(zi,s)∑u≤texp⁡(zi,u),mt,s=max⁡i∈Gtπi,s\pi_{i,s} = \frac{\exp(z_{i,s})}{\sum_{u\leq t}\exp(z_{i,u})}, \quad m_{t,s} = \max_{i\in\mathcal{G}_t}\pi_{i,s}

Distribution Alignment: The group indexer is trained by minimizing forward KL divergence:

Lt=DKL(ptT∥ptS)=∑s∈Stpt,sTlog⁡pt,sTpt,sS\mathcal{L}_t = D_{\mathrm{KL}}(p_t^T \| p_t^S) = \sum_{s\in\mathcal{S}_t} p_{t,s}^T \log\frac{p_{t,s}^T}{p_{t,s}^S}

3. Inference Strategy

  • Shared Token Bank Construction: A single full-prefix scan per query group selects the PℓP_\ell highest-scoring tokens
  • Query-Specific Refinement: The original DSA indexer performs Top-K selection over the augmented candidate set Ci=Pt∪{t+1,…,i}\mathcal{C}_i = \mathcal{P}_t \cup \{t+1, \ldots, i\}
  • Applied to both prefill and MTP target verification phases

Empirical Validation / Results

Task Performance

Key results from Table 1:

MethodLongBench Avg (DS-V3.2)LongBench v2 Avg (DS-V3.2)RULER Avg (DS-V3.2)
DSA56.0751.8995.37
HISA56.4749.5074.18
MISA54.6945.3392.56
IndexCache55.2149.7093.92
PIVOT56.2151.6994.71
ADIndex56.2352.6895.28
  • ADIndex achieves the highest overall accuracy on LongBench v2 among all acceleration methods
  • On RULER at 128K, ADIndex drops only 0.35 and 0.48 percentage points below DSA on the two models, while all competing methods drop more than one percentage point
  • ADIndex is the only method that remains within one percentage point of DSA on both models at each of the four evaluated context lengths

Efficiency Results

  • Prefill indexing speedup: 3.15×–6.22× at 256K context (across four reuse configurations)
  • Decode indexing speedup: 2.46×–3.40× at 256K context
  • End-to-end speedup: 1.54× at 128K KV-cache length
  • Gains become more pronounced at longer context lengths

Ablation Studies

Abl.1: Layer-wise calibration improves end-to-end speedup from 1.11× and 1.30× (uniform configurations) to 1.54× at 128K, with comparable RULER performance.

Abl.2: Distilled group indexer improves average RULER from 94.47 to 95.28 on DeepSeek-V3.2 and from 94.90 to 95.35 on GLM-5.1, with the largest gains at 128K (1.68 and 1.10 percentage points).

Abl.3: Head count robustness — performance remains stable across head counts (4–64), with only 0.62 and 0.13 percentage point differences on the two models. The chosen 8-head (DeepSeek-V3.2) and 4-head (GLM-5.1) configurations use one-eighth of the original heads.

Theoretical and Practical Implications

Theoretical Significance

  • Characterizes inter-layer heterogeneity in cross-query retrieval overlap, revealing that uniform reuse configurations are suboptimal
  • Demonstrates that group-level distillation can effectively compress per-query indexing signals into a lightweight group indexer with fewer heads
  • Establishes a principled calibration framework (Eq. 5) for selecting layer-adaptive reuse configurations

Practical Implications

  • Addresses the indexing bottleneck that dominates prefill GPU time (54.2% at 128K) in production-scale sparse attention systems
  • Provides near-lossless acceleration for long-context inference, making it suitable for deployment in production LLMs like DeepSeek-V3.2 and GLM-5.1
  • Reduces indexing head requirements by 8×, lowering memory and computation overhead
  • The approach is model-agnostic and applicable to any token-level sparse attention mechanism

Conclusion

ADIndex presents an effective solution to the indexing bottleneck in token-level sparse attention. By exploiting layer-wise heterogeneity through adaptive calibration and leveraging distillation to train efficient group indexers, it achieves substantial efficiency gains while preserving near-lossless task performance. Key findings include:

  1. Layer-adaptive reuse outperforms uniform configurations, particularly at longer contexts
  2. Distilled group indexers improve coverage and task performance over frozen baselines while using far fewer heads
  3. Shared token banks with query-specific refinement effectively balance efficiency and selection quality

Future directions could explore extending the approach to other sparse attention architectures, dynamic calibration during inference, and further reducing the group indexer's parameter footprint.

Related papers