# ADIndex: Layer-Adaptive Sparse Attention Indexing via Group-Level Distillation

> ADIndex accelerates DeepSeek Sparse Attention up to 6.22x by sharing token banks across neighboring queries via layer-adaptive calibration and distilled group indexers, with near-lossless accuracy.

- **Source:** [arXiv](https://arxiv.org/abs/2611.12956)
- **Published:** 2026-11-21
- **Permalink:** https://picx.dev/p/yVfIT4
- **Whiteboard:** https://picx.dev/p/yVfIT4/image

## Summary

## 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**: $\mathcal{O}(L^2)$ for indexing
- **Decoding complexity**: $\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 $G$ and $K$, the overlap among neighboring queries' Top-K selections varies substantially across layers. For $G=16$, $K=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,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 $G$, the maximum union size across consecutive query groups is computed:

$$
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_{\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:

$$
\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 ($H_S^I$):

$$
\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:

$$
\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:

$$
\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_\ell$ highest-scoring tokens
- **Query-Specific Refinement**: The original DSA indexer performs Top-K selection over the augmented candidate set $\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:**

| Method | LongBench Avg (DS-V3.2) | LongBench v2 Avg (DS-V3.2) | RULER Avg (DS-V3.2) |
|--------|------------------------|---------------------------|---------------------|
| DSA | 56.07 | 51.89 | 95.37 |
| HISA | 56.47 | 49.50 | 74.18 |
| MISA | 54.69 | 45.33 | 92.56 |
| IndexCache | 55.21 | 49.70 | 93.92 |
| PIVOT | 56.21 | 51.69 | 94.71 |
| **ADIndex** | **56.23** | **52.68** | **95.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.

---

_Markdown view of https://picx.dev/p/yVfIT4, served by PicX — AI-generated visual whiteboard summaries of research papers._
