- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes the Linear Indexer, which removes the ReLU nonlinearity and aggregates the DSA query heads before computation to reduce the computational cost of the DSA indexer. The Linear Indexer serves as a filtering mechanism for the subsequent DSA computation by providing a filtered set of KV indices. The authors also provide interesting observations about the DSA indexer that justify its linearization and suggest that the Linear Indexer can serve as a good proxy for the original DSA indexer.
The proposed Linear Indexer achieves a significant speedup over the DSA indexer while largely preserving downstream task accuracy. Although the proposed method demonstrates substantial efficiency gains while maintaining accuracy, the current manuscript does not provide sufficient direct comparisons against other baseline methods mentioned in the paper.
Critical strengths
-
Simple and performant design: The proposed method exploits the sign stability of the learned DSA indexer and introduces a simple algebraic simplification without requiring additional training. Its direct mode achieves a 10.4× indexer speedup and a 1.39× prefill speedup at a 256K context length. Negligible or no accuracy degradation is observed on the evaluated RULER and LongBench v2 benchmarks.
-
Design supported by empirical observations: The authors provide interesting observations about the behavior of the DSA indexer, particularly the finding that certain DSA indexer outputs exhibit consistent signs across different inputs. Based on these observations, the authors provide empirical justification for the proposed Linear Indexer.
Critical weaknesses
-
Incomplete comparison against baseline methods: Although the paper directly compares the proposed method against MISA and HISA for KV retrieval, it does not provide comparisons of downstream task accuracy, indexer speedup, or end-to-end prefill speedup against these methods.
-
Limited decoding latency improvement: The demonstrated efficiency gains of the Linear Indexer are primarily focused on prefill, and the authors acknowledge this limitation. However, this limits its practical benefits for workloads where decoding accounts for a substantial portion of the total latency.
Questions for authors
-
Is the Linear Indexer used during decoding? Given the design of the Linear Indexer, it is reasonable to expect that decoding latency would not improve significantly. However, if the Linear Indexer is also adopted during decoding, can we expect it to preserve generation accuracy?
-
Applicability to QSA: In the analysis in Section 3, the authors argue that sign dominance is a learned property of the DSA indexer and that the input-dependent weight term further reinforces this sign consistency, making the output scores predominantly either positive or negative. Considering that Qwen Sparse Attention (QSA) shares many design similarities with DSA, would similar observations hold for QSA, and could the Linear Indexer also be applied to QSA?
5 comments
Response to Reviewer PbE1 — W2: Practical benefits beyond prefill latency
We thank the reviewer for highlighting this limitation. Linear Indexer achieves a speedup in end to end latency at 256K context under four concurrent requests, including 512-token generation. This measures the time to complete generation, rather than TTFT alone.
We use the same serving settings as in the paper, with four concurrent requests, each generating 512 tokens. Under continuous batching and chunked prefill, decoding tokens can be processed in the same execution batches as other requests’ prefill chunks, allowing prefill acceleration to benefit complete-request latency.
| Input context | Exact | Direct Linear Indexer () | E2E Speedup |
|---|---|---|---|
| 64K | 27.98 s | 25.60 s | 1.09× |
| 128K | 60.18 s | 50.23 s | 1.20× |
| 256K | 149.81 s | 108.88 s | 1.38× |
The results demonstrate benefits for concurrent long-input workloads, while gains remain workload-dependent and may be smaller when decoding dominates total latency.
Complementarity with decoding acceleration. Head folding reduces scoring computation and is complementary to key compression and candidate restriction, as illustrated by its applicability to DSA, CSA, and CSA2. It can therefore be combined with methods targeting memory traffic during decoding.
Implications for training. Our findings also motivate training indexers directly with the folded linear score. Indexer training processes many query positions over long sequences, making query–key scoring a natural target for acceleration. The same factorization reduces scoring arithmetic in both forward and backward passes, offering a route to lower long-context indexer-training cost. We leave native training and its quality–efficiency tradeoff to future work.
Response to Reviewer PbE1 — Q1: Use of Linear Indexer during decoding and its impact on generation quality
We thank the reviewer for highlighting this distinction. In our V4 evaluations, Linear Indexer is enabled for both prefill and decoding. Under this configuration, it maintains downstream quality comparable to Exact CSA on LongBench-v2 and RULER through 256K context.
In our newly added V3.2 comparisons, Linear Indexer is applied only during prefill, while decoding retains Exact DSA. It likewise achieves comparable downstream quality: 48.42% versus 48.10% on LongBench-v2, and 88.19% versus 88.92% on RULER at 128K. A supplementary V3.2 run enabling replacement during both prefill and decoding also matches Exact DSA’s aggregate LongBench-v2 accuracy at 48.10% (152/316).
These results are encouraging for generation quality in the evaluated settings.
Response to Reviewer PbE1 — W1: Downstream quality, indexer latency, and end-to-end comparisons with MISA and HISA
We thank the reviewer for motivating these additional comparisons. The downstream-quality and TTFT results are now included in Sections 5.4–5.5, with experimental settings in Section 5.1 and Appendix G, and detailed downstream results in Appendix H.4.
Our added DeepSeek-V3.2 experiments show that direct Linear Indexer achieves comparable downstream quality to Exact DSA on LongBench-v2 and RULER, higher aggregate scores than HISA/MISA, and the lowest TTFT at all three tested context lengths. At 128K, it achieves a 1.73× TTFT speedup over Exact DSA. These results complement the indexer latency comparisons already reported in Table 10 of the original submission (Table 18 in the revised manuscript).
We evaluate DeepSeek-V3.2, integrating the released HISA/MISA kernels into a common inference framework. All methods retain the native final K=2048 budget and replace indexing only during prefill; decoding uses Exact DSA. Direct Linear Indexer operates as a training-free, drop-in scorer replacement, without refinement or layer-specific budget tuning.
Downstream quality. Since the DeepSeek-V3.2 checkpoint specifies a maximum context length of 160K tokens, all methods are evaluated on the same 316 LongBench-v2 examples with input lengths up to 128K. RULER is evaluated at 128K on the same 50 examples for each of its 13 tasks, yielding 650 examples per method.
Indexer latency. On the 64K V3.2 capture, direct Linear Indexer takes 2.51 ms per layer, compared with 18.26 ms for Exact DSA, 11.45 ms for HISA (B=8192), and 10.14 ms for MISA (h=8). The corresponding speedups over Exact DSA are 7.26×, 1.60×, and 1.80×, respectively. These measurements include final Top-2048 selection; the full protocol and budget sweep are provided in Appendix H.2.
End-to-end prefill latency. We measure served TTFT on eight NVIDIA H20 GPUs with TP8, a 2,048-token prefill chunk, and piecewise CUDA graphs. Inputs and serving settings are matched across methods. Results are medians of three timing trials after two warmups.