LiteTopK: Exploiting the Curse of Dimensionality for a Fused Indexer-TopK Kernel in Long-Context Sparse Attention
Ziqi Yin, Jianyang Gao, Peiqi Yin, Jiangneng Li, Gao Cong
原文摘要
Indexer-TopK, which computes scores and selects the top-$k$ candidates, is a key primitive in long-context sparse attention for large language models, vector retrieval for recommendation systems, and vector databases. However, existing GPU-based Indexer-TopK kernels like DeepSeek Sparse Attention (DSA) typically separate scoring from selection and materialize the full score matrix in high-bandwidth memory. This strategy is inefficient for large score matrices, such as those encountered in long-context sparse attention, due to excessive global-memory traffic, costly synchronization, and prohibitive memory overhead. In this study, motivated by the curse of dimensionality, we observe that sparse attention scores exhibit a score concentration phenomenon, with scores falling within a narrow range. Based on this observation, we propose LiteTopK, a sample-filter-select framework that estimates query-data score ranges from a small subset of the data. It uses these estimates to filter scores as they are computed, materializes only the candidates that pass the filter, and selects from the surviving candidates. In particular, we develop two implementations of LiteTopK. The first uses a conservative threshold estimate, while the second pairs a predicted threshold with a fallback strategy. Building on LiteTopK, we further propose LiteDSA, which reuses overlapping key/value entries across neighboring queries to accelerate attention computation. We integrate LiteTopK into vLLM, SGLang, and Megatron-LM. Our evaluation on eight B200 GPUs demonstrates prefill speedups of up to 1.49$\times$ across GLM-5.2, DeepSeek-V4-Flash, and Hy-4-Preview at a context length of 1M tokens, without compromising model capabilities.
cs.LG