Indexing Bottleneck of Sparse Attention at 10-Million-Token Context
Sparse attention reduces compute from quadratic to linear in context length T, yet the indexer that selects top-k keys remains O(T²) and dominates prefill time once T reaches tens of millions. This article examines why the indexer becomes the new bottleneck, reviews three common optimizations (lower precision, reduced dimension, block compression) and their limits, and shows that the core challenge is sub-quadratic retrieval of the relevant keys.
Background: Long Context Reallocates Attention Cost
Million-token context windows have become common. Long-document analysis, repository-scale code understanding and multi-turn dialogue all rely on them. Full attention computes every query against every historical key, so prefill cost is O(T²) while each decode step costs O(T).
Sparse attention first selects a small number of relevant keys for each query and then performs full attention only on those keys. Attention cost therefore drops to O(Tk) where k ≪ T.
Public experiments confirm that a tiny fraction of keys is often sufficient to preserve most of the original quality. The remaining question is how to locate those keys quickly.
Hidden Cost: The Indexer’s Quadratic Overhead
Sparse attention consists of two stages:
- Indexing: score every key for every query and keep the top-k.
- Attention: standard attention on the selected k keys.
The second stage is O(Tk) and grows linearly. A naïve indexer, however, still materializes a T×T score matrix and remains O(T²). When context grows from 1 M to 10 M tokens the quadratic term increases 100-fold and indexing quickly dominates wall-clock time.
Layer-level measurements on 10 M-token prefill show that the indexer accounts for the vast majority of runtime; the subsequent attention itself is comparatively cheap. Consequently the research focus has shifted from “is sparsity accurate enough?” to “can the relevant keys be found in sub-quadratic time?”
Many teams observed large speed-ups at million-token scale and assumed the problem was solved. As context continues to grow, indexer cost eventually exceeds attention cost.
Existing Cost-Reduction Paths and Their Limits
Three families of indexer optimizations are widely used.
3.1 Reduced Scoring Precision
Switching from high-precision floating-point to low-bit formats cuts memory bandwidth and arithmetic time. The drawback is that scoring error can invert nearby keys whose true scores are close, causing critical information to be dropped from the top-k.
3.2 Reduced Scoring Dimension
The indexer may use a lower-dimensional projection than the main attention. This improves the constant factor but leaves the complexity O(T²). Doubling context still quadruples work.
3.3 Block-Level Compression
Adjacent keys are aggregated into a single block representation that is then scored. For example four keys may be replaced by one representative vector, reducing the number of candidates. Fine-grained information inside each block is lost; if a salient token sits on a block boundary or is diluted by averaging, retrieval quality suffers.
