ADIndex Restructures Sparse-Attention Indexing with Group-Level Distillation

Summary:ADIndex targets a major bottleneck in DeepSeek Sparse Attention: its indexer still scores the entire causal prefix for every query, accounting for more than half of prefill GPU time at long context lengths. The method combines layer-wise calibration, group-level distillation, and shared token-bank scanning within query groups while retaining query-specific refinement. On DeepSeek-V3.2 and GLM-5.1, the paper reports up to 6.22x prefill-kernel and 3.40x decoding-kernel speedups at 256K context, pl

---

ADIndex moves the sparse-attention bottleneck from “how many tokens are selected” to “how cheaply those tokens are located.” In DeepSeek Sparse Attention (DSA), the indexer still scores the entire causal prefix for every query, and that stage can consume more than half of prefill GPU time at long context lengths.

Why the Indexer Becomes the Bottleneck

A standard DSA pipeline first uses an indexer to select the positions that should receive exact attention. The main attention cost can be reduced approximately from (O(N^2)) to (O(NS)), where (N) is the context length and (S) is the number of selected or processed tokens. However, this does not remove the indexer's (O(N^2)) candidate-scoring work.

During prefill, every query is available at once, so the indexer repeatedly scans the same prefix. During decoding, fewer new queries are processed, but each one can still trigger another full scan over historical KV state. Sparse attention therefore does not automatically imply linear end-to-end complexity: locating a small number of relevant tokens can still dominate memory bandwidth and compute.

ADIndex attacks precisely this stage. Its goal is to eliminate redundant prefix scans without materially changing the quality of token retrieval.

Three Core Components

1. Layer-Wise Calibration

ADIndex first calibrates retrieval behavior across Transformer layers. The authors observe pronounced inter-layer heterogeneity: layers may attend to different token types, exhibit different overlap patterns, and make different use of historical context. Applying one global reuse policy can therefore waste candidate budget in some layers while missing distant evidence in others.

Layer-specific calibration allows each layer to select a more appropriate indexing strategy. Operationally, this requires maintaining per-layer index configurations rather than relying on one global threshold.

2. Group-Level Distillation

The second component trains adaptive layer-wise group indexers through group-level distillation. Instead of requiring every query to perform independent full-prefix retrieval, related queries share candidate information while salient signals are distilled from individual queries to preserve query-specific relevance.

This differs from conventional knowledge distillation in an important way: the teacher signal includes both shared historical positions used by a group and the layer-dependent differences among group members. After training, the serving system can process candidates in groups and perform lightweight refinement for each query.

3. Low-Latency Token-Bank Sharing

At inference time, queries in the same group share a token bank, avoiding an independent full-prefix scan for every request. Query-specific refinement remains in the pipeline so that important tokens unique to an individual query can still be recovered.

The basic flow is:

1. Generate a group-level candidate set for incoming queries.
2. Share the token bank and partial index results within the group.
3. Execute attention over the selected candidates.
4. Refine the candidate set for each query and add query-specific tokens when needed.

The core trade-off is clear: more sharing means fewer scans but more risk of missing query-specific information; less sharing preserves accuracy but reduces the efficiency benefit. ADIndex uses layer-wise calibration and query-level refinement to balance these costs rather than masking retrieval misses by simply enlarging the candidate set.

Measured Gains and Evaluation Boundaries

The paper evaluates ADIndex on DeepSeek-V3.2 and GLM-5.1. At a 256K context length and across layer-wise reuse configurations, it reports up to a 6.22x prefill-kernel speedup and a 3.40x decoding-kernel speedup. At 128K context, end-to-end serving throughput improves by as much as 1.54x. The method maintains near-DSA task performance on LongBench, LongBench v2, and RULER.

The results suggest that long-context serving can benefit substantially from reducing repeated memory access in the indexing stage rather than from changing the final sparse-attention token-selection objective. For inference engines, this is particularly relevant when the indexer dominates prefill time: eliminating redundant scans can directly improve time-to-first-token latency.

However, the reported “up to” figures depend on context length, layer-reuse settings, and model configuration. They should not be generalized to all serving workloads. A complete evaluation should examine:

• Runtime variance as the similarity of query groups changes;
• Whether high-concurrency or highly diverse requests dilute the benefit of sharing;
• The exact metrics, task distribution, and statistical variation behind the near-lossless quality claim;
• Training data, compute, and online calibration costs for the distilled indexers;
• Whether end-to-end measurements include KV transfers, scheduling, sampling, and networking.

Kernel speedups and end-to-end speedups must also be kept separate. The 6.22x and 3.40x figures are kernel-level results at 256K, while 1.54x is an end-to-end serving result at 128K. Production evaluation should measure TTFT, TPOT, throughput, peak memory, and tail latency across realistic request distributions.

Deployment Guidance

ADIndex is most relevant to teams deploying DeepSeek Sparse Attention or similar token-level sparse-attention models, particularly for long-document processing, repository-scale coding assistants, retrieval-augmented generation, and high-concurrency long-context services.

A practical deployment sequence is:

1. Profile the indexer separately. Measure candidate scoring, exact attention, KV reads, and sampling independently to avoid misattributing the bottleneck.
2. Start with layer-reuse calibration. Measure query overlap and candidate hit rates per layer, then choose conservative reuse levels that avoid recall degradation.
3. Keep a full-scan fallback. Re-run full-prefix indexing for low-confidence requests, unusual distributions, or detected retrieval failures to bound worst-case latency and quality risk.
4. Validate online distribution drift. Long conversations, source-code retrieval, and RAG traffic have different retrieval patterns and cannot be represented solely by static LongBench-style data.
5. Optimize the serving kernel end to end. Grouped index packing, resident token banks, and sparse KV access must form a contiguous execution path; otherwise, theoretical scan reductions may be offset by extra scheduling and memory copies.

Conclusion

ADIndex's key contribution is recognizing that DSA's indexer has become a dominant long-context latency source, then modeling layer heterogeneity, distilling group-level indexers, and sharing scans within query groups. It provides a technically plausible path from algorithmic optimization to serving-kernel acceleration. The headline speedups are promising, but production adoption still requires realistic request-mix testing, tail-latency measurement, and explicit quality-fallback policies.

---

Source: ArXiv Machine Learning (cs.LG) (2026-11-11)

— END —

Tags: #ADIndex Follow #Sparse Attention Follow #Long-Context Inference Follow #Group-Level Distillation Follow #DeepSeek Sparse Attention Follow