Sparse Attention in Latent Space: How It Breaks the Indexing Bottleneck at Ten-Million-Token Context Lengths
Sparse attention cuts the cost of attention computation in long-context models, but at ten-million-token scale, finding the relevant tokens can still dominate runtime. This article explains why the indexing step becomes the bottleneck, compares three common indexing strategies and their trade-offs, and shows how latent-space sparse attention separates coarse retrieval from exact attention. It also covers recall risks, engineering design choices, and the metrics needed to evaluate efficiency, quality, and stability.
In long-context models, the hard problem is not simply letting the model see more content. The real challenge is finding useful information among massive amounts of historical tokens quickly, while keeping latency, GPU memory, and compute costs acceptable.
At the million-token scale, the quadratic complexity of full attention already creates significant pressure. As context grows to ten million tokens, many systems adopt sparse attention so that each query attends to only a small set of candidate positions. However, sparsity does not simply turn quadratic cost into linear cost. A problem that is easy to overlook is that the model must first decide which tokens are worth attending to, and this selection process can itself become the dominant cost.
1. The Core Tension in Ultra-Long Context: Computation Drops, but Search Does Not Disappear
Standard attention can be written as:
Attention(Q, K, V) = softmax(QKᵀ / √d)V
The query matrix Q must be scored against the full key matrix K. The resulting relevance weights are then used to combine the value matrix V. Suppose the sequence length is T and the hidden dimension is d. In the prefill stage, attention generally has a time complexity of roughly O(T²) and places heavy pressure on memory access.
In the decoding stage, each step adds only one token, so the computation is roughly O(T). As the history grows, however, per-step latency and the amount of KV cache read keep increasing.
The basic idea of sparse attention is to keep only the k most relevant keys for each query, where k is much smaller than T. Ideally, the actual attention computation drops from:
O(T²)
to:
O(Tk)
When k stays relatively stable, this approach is very attractive for ultra-long contexts. The system still has to complete a preprocessing step, though:
Find the k most relevant keys for each query
If this search scans all historical tokens, the indexing stage remains close to O(T²). In that case, the system has only replaced “full attention computation” with “full candidate search,” and the overall gain shrinks substantially.
This is the hidden cost of sparse attention. Only a few tokens actually take part in the final weighting, but to identify them, the system may still have to score the vast majority of historical positions.
2. Why Traditional Sparse Attention Hits an Indexing Bottleneck
Current sparse strategies fall into three rough categories.
1. Lowering the Precision of Index Computation
The indexer uses low-precision data types or smaller projection dimensions instead of full-dimensional queries and keys. This reduces multiply-add operations and memory bandwidth demand.
This approach only reduces constant overhead. It does not change the basic structure, in which every query must scan a large number of keys. When context grows from the million-token scale to ten million tokens, linear scanning remains expensive.
2. Block-Level Filtering
The system first divides consecutive tokens into blocks and generates a summary vector for each block. A query only needs to determine which blocks may be relevant, and then it runs finer attention inside the selected blocks.
Block-level filtering reduces the number of candidates, but it has two problems. First, larger blocks lower indexing cost but reduce localization accuracy. Second, smaller blocks localize more precisely, but they create more summaries, more indexing operations, and higher memory access overhead.
No single block size suits every task. Code retrieval, long-document QA, log analysis, and multi-turn dialogue each place different demands on locality structure.
3. Compressing Multiple Keys Before Retrieval
Another class of methods aggregates several adjacent or related keys into one representation, which reduces the number of elements involved in indexing. This shrinks the search scale, but compression can lose fine-grained information.
If key evidence appears only in a very small local region, and that region is merged with many unrelated tokens, the indexer may fail to judge its importance accurately. Recall then drops.
The key to sparse attention, then, is not only reducing the number of candidates. It is also preserving the ability to tell important information apart after compression.
3. The Basic Idea of Latent-Space Sparse Attention
Latent-space sparse attention treats two steps as separate problems: searching over historical tokens, and performing the final attention.
Traditional approaches usually index directly at the raw token level:
Query → compare with all keys → select candidate tokens
The latent-space approach first compresses historical information in a structured way, mapping many tokens to a smaller number of latent units. The query then retrieves over these units:
History tokens → latent representation → Query retrieves relevant latent units → map back to raw tokens
Here, the latent space works as an intermediate index layer. It does not simply delete tok
