Sub-Quadratic Sparse Attention at the Ten-Million-Token Context Scale: Conditions and Approaches
At the ten-million-token context scale, sparse attention does not deliver sub-quadratic acceleration automatically—the cost of finding relevant tokens can outweigh the savings in attention itself. This article explains how latent-space sparse attention shifts the "find relevant tokens" step into a shared low-dimensional space, using coarse retrieval followed by fine reranking to keep latency and memory under control. It walks through the full pipeline (latent projection, block-level coarse ranking, candidate reranking, and sparse computation), a complexity analysis showing the exact conditions under which O(T·r·log(T/b)) holds, illustrative causal pseudocode, accuracy-preservation tactics, engineering practices from prefill to decode, cache-governance limits, and the evaluation metrics and rollback strategy needed to ship it reliably.
1. The Shifting Problem: From Compute to Selection, and the Conditions for Sub-Quadratic Scaling
At the ten-million-token context scale, the core questions in the prefill path have become how to reduce indexing overhead, how to measure recall, and how to tune candidate size. Dense attention scales with the square of the sequence length T, so prefill cost grows quadratically as T increases. When the context grows from millions to tens of millions of tokens, simply adding more compute often fails to relieve latency linearly, because what actually slows the system down is not just matrix multiplication—it is also memory access, data movement across GPU memory, candidate ranking, and index maintenance.
The goal of sparse attention is to reduce the number of tokens that ultimately participate in computation. But this comes with a prerequisite: the system must first find a few key tokens at low cost. If the indexer still scans every historical token, sparse attention merely turns “compute directly” into “compute relevance first, then select,” and the total cost may not drop at all.
So the “sub-quadratic” behavior discussed in this article is not an unconditional promise. It is a goal that can only appear under conditions such as approximate retrieval, hierarchical indexing, bucketing, clustering, and low-dimensional projection. Sparse attention becomes viable only after the cost of candidate generation is genuinely driven down.
The differences between approaches can be understood with a simplified cost comparison:
| Approach | Indexing overhead | Memory & bandwidth | Recall risk | Applicable conditions |
|---|---|---|---|---|
| Dense full attention | High, roughly scales with T² | High | No missed recall, but highest cost | Short contexts or critical business layers |
| Block-sparse attention | Medium, depends on block scoring | Medium | Poor block partitioning causes missed recall | Stable block structure, tolerance for block-level approximation |
| Latent coarse ranking + candidate reranking | Lower, but depends on index structure | Low–medium, cache must be controlled | Missed recall when low-dimensional representation is insufficient | Approximate retrieval, hierarchical indexing, tunable candidate size |
2. The Hidden Bill: The Indexer Can Cost More Than Attention Itself
A common approach to sparse attention is to first use a lightweight indexer to score historical tokens, then select the k tokens with the highest scores to participate in attention computation. This seems reasonable, but the indexer itself must cover a large number of candidates. If the indexer still interacts with every historical token in the original high-dimensional space, then the longer the context, the closer the indexing cost gets to a dense comparison.
This produces a counterintuitive phenomenon: the attention matrix has already shrunk significantly, yet prefill latency shows no clear improvement. The reason is that the time is being consumed by the indexer, the ranker, the candidate selector, and cache maintenance. What the user sees—that only a few tokens were computed—hides the fact that the system is maintaining, behind the scenes, a relevance catalog spanning the entire context.
Therefore, sparse attention must solve three classes of problems at once:
- Accuracy: after keeping only a few tokens, model capability must not degrade noticeably.
- Efficiency: the discovery process for candidate tokens must be lightweight enough.
- Consistency: training, prefill, decoding, caching, and incremental updates must stay consistent with one another.
Under extremely long contexts, the efficiency problem is especially acute. If the indexing stage still performs dense comparisons, sparse attention merely swaps “computing the selection” for “selecting what to compute” and does not change the fundamental complexity.
3. Latent-Space Sparse Attention: Moving “Finding Relevant Tokens” to a Low-Dimensional Space
The core idea of latent-space sparse attention is this: do not complete full-candidate screening directly in the original high-dimensional space. Instead, first project queries and keys into a shared low-dimensional latent space, do coarse-grained recall there, and then return to the original space for fine-grained selection.
This splits the discovery of relevant tokens into two stages:
- Coarse ranking: quickly narrow the candidate range in the latent space.
- Fine ranking: score precisely within the candidate range using a representation closer to the original space.
The value here is that the low-dimensional index space can be combined with structures such as chunking, bucketing, clustering, summary pooling, and approximate nearest neighbor to organize tens of millions of tokens into a searchable hierarchy. The original attention is like surveying streets one by one—costly but precise; a latent-space index is more like a city road map: first locate the region, then enter the specific intersection.
Latent-space sparse attention is not simple dimensionality reduction. It requires building a maintainable “relevance navigation layer.” Within this layer, the system no longer compares original representations token by token; instead, through projection, block summaries, bucketing, or clustering, it turns large-scale context into a structure that is easier to search.
4. The Typical Pipeline: From Latent Projection to Sparse Attention Computation
4.1 Latent Projection and the Order of Candidate Tuning
First, project queries and keys into the shared latent space with low-dimensional projections. The latent space does not need to retain every semantic detail of the original model, but it must be able to express “which regions are more likely to be relevant.”
In engineering terms, the projection can use a linear matrix, grouped projection, low-rank decomposition, hash encoding, and similar techniques. The target of the latent dimension r is to improve recall efficiency, not to replace the full semantic representation. If r is too low, key structure is lost; if r is too high, the acceleration effect is weakened.
Tune parameters in the following order:
- First, fix the accuracy target and the candidate ceiling. The candidate ceiling c must not approach T, or sparsification loses its meaning. In long-context scenarios, controlling the coarse-ranked candidate tokens to about 1%–5% of the total length is a reasonable engineering starting point, then adjust based on task validation.
- Next, set the latent dimension r. Start stress-testing from tiers such as 32, 64, and 128. If recall is insufficient, prefer increasing r rather than blindly expanding the candidate count.
- Then set the block size b. A larger block reduces the number of blocks but lowers recall granularity; a smaller block increases the number of blocks and raises indexing pressure. In long contexts, start from 64 or 128.
- Next, set num_blocks, the number of coarse-ranked candidate blocks. It determines the candidate scale entering fine ranking. You can begin by making the coarse-ranked candidate tokens 1.5×–3× the number of tokens ultimately retained, to keep some redundancy.
- Finally, set final_topk. It should be determined jointly by memory, compute, and task accuracy, and should not be over-compressed from the start.
Pay particular attention: if r is too low, block_size is too large, or the number of candidate blocks is insufficient, the coarse-ranking stage may miss key regions. No matter how strong the subsequent fine ranking is, it cannot compensate for missing candidates.
4.2 Block-Level or Bucket-Level Coarse Ranking
In the latent space, consecutive tokens can be grouped into blocks, block-level representations can be computed, and those representations can then be used to estimate the relevance between a query and a historical range. This way the system does not judge token by token; it first decides “which regions are worth entering.”
The key metric for the coarse-ranking stage is recall. Coarse ranking can be moderately loose—it is better to recall a few extra candidate blocks than to miss the truly important regions. If coarse ranking misses a key block, no amount of precision in the fine-ranking stage can recover it.
For causal language models, causal constraints must also be respected: the current query can only attend to the current and past history. Although block-level coarse ranking reduces candidate-generation cost, you must not let future tokens leak into the current query’s candidate set just to save effort.
4.3 Fine Ranking Within the Candidate Range
Inside the blocks, buckets, or regions selected by coarse ranking, the system returns to the original space or a representation closer to it and performs more precise relevance scoring on the candidate tokens.
The fine-ranking stage typically processes only a small subset of candidates, so even with a more complete scoring method the total cost stays controllable. Common strategies include:
- Exact dot-product scoring on candidate tokens;
- Local top-k within candidate blocks;
- Combining position weights, distance decay, and local windows;
- Introducing a small number of global summary tokens as a fallback;
- Applying strict masking at the causal boundary to prevent future tokens from being selected.
The goal of fine ranking is not to pursue theoretical optimality, but to retain high-scoring tokens as well as possible within an acceptable candidate size.
4.4 Sparse Attention Computation and Common Mistakes
Finally, the model performs attention only on the small set of selected tokens. Because the number of selected tokens is far smaller than the total length, the attention matrix shrinks significantly.
Common mistakes in engineering practice include:
- Only doing the low-dimensional projection without candidate fine ranking, causing unstable recall;
- Focusing only on global sparsity while ignoring the local window, causing loss of local detail;
- Missing causal masking, causing inconsistency between training and inference behavior;
- Too few candidates, so key tokens cannot enter the attention computation;
- Block-level summary granularity too coarse, causing important fragments to be averaged away;
- Optimizing only prefill speed without monitoring incremental index consistency in the generation stage.
5. Complexity Analysis: Why Sub-Quadratic Scaling Requires Conditions
Let the context length be T, the original hidden dimension be d, the latent dimension be r, the block size be b, the number of blocks be B ≈ T / b, the number of coarse-ranked candidate tokens be c, and the number of tokens ultimately retained be k.
The prefill complexity of standard full attention can be roughly expressed as O(T²d). The goal of sparse attention is to reduce the tokens actually participating in attention to k, bringing the attention computation down to O(Tkd).
But the problem is: if, in order to find these k tokens, the system still scores every token in the original space, the indexing stage may still approach O(T²d).
The optimization of latent-space sparse attention is to move the indexing stage from the original space into a low-dimensional latent space and to introduce block-level, bucket-level, or approximate structures. The main costs are:
- Projecting queries and keys into the latent space: about O(Tdr).
- Coarse ranking and candidate generation in the latent space: with bucketing, clustering, approximate nearest neighbor, or hierarchical indexing, this can approach O(T·r·log(T/b)); if the query is scored pairwise against all blocks, the complexity may still reach O(T²r/b).
- Reranking within the candidate range: about O(Tcd), where c should be far smaller than T.
- Final sparse attention computation: about O(Tkd), where k should also be far smaller than T.
Therefore, O(T·r·log(T/b)) is not an automatic conclusion—it depends on the following conditions:
- A bucketing, clustering, approximate-nearest-neighbor, hierarchical-index, or similar approximate-retrieval structure must be used;
- Coarse ranking must not degenerate into dense pairwise scoring of the query against all blocks;
- The number of blocks, candidate blocks, and candidate tokens must be significantly smaller than the total length;
- The index structure must support incremental updates, otherwise the decode stage may repeatedly rebuild the index;
- The projection dimension r must be large enough to express relevance, yet small enough to keep indexing cost low.
Only when r, c, and k are all significantly smaller than d or T can the overall complexity shift from near-quadratic growth toward sub-quadratic or near-linear growth. The value of latent-space sparse attention is not merely reducing the attention computation—it is changing the complexity structure of “relevance discovery.”
6. Illustrative Code: An Abstract Implementation of Causal Latent-Space Sparse Attention
The pseudocode below is used only to express the core flow and does not depend on any specific framework. It highlights the idea of “latent coarse ranking + candidate fine ranking + sparse computation” and adds causal constraints.
# Pseudocode: prefill flow of causal latent-space sparse attention# Causal constraint: the i-th query token can only attend to historical tokens at positions <= i.# Historical block index: block j can only be accessed by query blocks >= j.# Coarse ranking uses only the current and past blocks, avoiding dense pairwise scoring# between q_latent and all blocks.# Fine ranking still needs a token-level causal mask to prevent future tokens within a# block from leaking.def causal_latent_sparse_attention(q, k, v, Pq, Pk, block_size, num_blocks, final_topk):"""q: query representations, roughly shaped [T, d]k: key representations, roughly shaped [T, d]v: value representations, roughly shaped [T, d]Pq, Pk: projection matrices from queries and keys to the low-dimensional latent spaceblock_size: coarse-ranking block sizenum_blocks: number of candidate blocks retained per query blockfinal_topk: number of tokens ultimately retained after fine ranking"""# 1. Project into the shared latent space to reduce indexing costq_latent = q @ Pqk_latent = k @ Pk# 2. Aggregate the key sequence at block level to form a coarse-grained indexk_blocks = chunk_mean(k_latent, block_size) # [B, r]B = k_blocks.shape[0]outputs = []# 3. Process per query block, using only the current and past blocks for coarse rankingfor block_id in range(B):# Historical block index: current and past blocks, excluding future blocksvisible_blocks = k_blocks[:block_id + 1]# Current query block rangeq_start = block_id * block_sizeq_end = min(q.shape[0], q_start + block_size)q_chunk = q_latent[q_start:q_end]# 4. Compute coarse-grained relevance between the current query block and visible blocks# Only visible blocks are processed here, avoiding full pairwise scoringblock_scores = q_chunk @ visible_blocks.transpose(-1, -2)# 5. Select the candidate blocks with higher relevanceselected_local_blocks = top_k(block_scores, num_blocks, axis=-1)# 6. Map local block ids to global block ids and expand them into candidate tokenscandidate_tokens = expand_blocks(selected_local_blocks, block_size, offset=0)# 7. Within the candidate range, return to the original space for finer scoringcandidate_k = k[candidate_tokens]candidate_v = v[candidate_tokens]exact_scores = q_chunk @ candidate_k.transpose(-1, -2)# 8. Causal mask: keep only candidate tokens at positions not exceeding the current query positionexact_scores = causal_mask(exact_scores, q_start, candidate_tokens)# 9. Within the candidate range, keep the tokens that finally participate in computationkeep = top_k(exact_scores, final_topk)selected_k = candidate_k[keep]selected_v = candidate_v[keep]# 10. Perform attention only on the selected tokensattention_scores = (q_chunk @ selected_k.transpose(-1, -2)) / sqrt(q_chunk.shape[-1])attention_weights = softmax(attention_scores)output = attention_weights @ selected_voutputs.append(output)return concatenate(outputs)
This pseudocode expresses a general design paradigm: first narrow the search range through a low-dimensional latent space, then perform precise selection within the candidate range. A production implementation still needs to handle details such as batched inference, parallel partitioning, cache management, positional encoding, masking strategies, dynamic candidate ceilings, and memory optimization.
7. Preserving Accuracy: Speed Isn’t Enough—You Must Not Miss Key Tokens
Latent-space sparse attention can reduce indexing cost, but the risk is equally clear: if the latent representation is insufficient, the coarse-ranking stage may miss the tokens that truly matter. Once a key token is not recalled, no matter how strong the subsequent fine ranking is, it cannot be recovered.
Therefore, engineering must treat accuracy as a core constraint, not an afterthought patch.
7.1 Controlling Information Loss in the Latent Space
The latent dimension, the projection method, and the normalization strategy all affect recall. The following strategies can improve stability:
- Normalize the projected representations to avoid scale imbalance;
- Use multi-head or grouped indexing to reduce the information loss of a single projection;
- Model positional information separately to prevent long-range dependencies from being over-compressed in the latent space;
- Retain an original-space fallback for key semantic tokens;
- Keep a local window or a dense layer as insurance for high-risk tasks.
7.2 Providing Candidate Redundancy
The coarse-ranking stage should not pursue extreme sparsity; it should retain some redundancy. A few more candidate blocks and a few more candidate tokens can usually improve recall significantly. Once recall improves, the fine-ranking stage can recover accuracy through top-k selection.
A latent-space index should prioritize “not missing anything” rather than over-compressing. Too-small a candidate size is one of the most common sources of accuracy loss in long-context inference.
7.3 Combining Local Windows with Global Summaries
Long-context tasks require both long-range semantic association and local continuity. Pure sparse selection may weaken local detail. So you can introduce local-window attention as a baseline safeguard and then layer global sparse selection on top of it.
At the same time, you can insert a small number of global summary tokens or block summaries into the sequence to carry cross-segment information. This way, even if some original tokens are not selected, the model can still obtain part of the context signal through the summaries.
7.4 Aligning with the Training Stage
If the latent-space index is part of the model architecture, it is best to let the indexing process participate in training or fine-tuning. Otherwise, suddenly changing the candidate-selection method at inference time can cause the model’s behavior to drift.
Common practices include:
- Introducing sparse-attention constraints during pre-training;
- Jointly optimizing the indexer and the backbone model during long-context fine-tuning;
- Using distillation to make the sparse model approximate the behavior of the dense model;
- Adding auxiliary-loss supervision on the index recall results;
- Keeping dense or semi-dense computation for critical layers to reduce training instability.
8. Engineering Essentials: End-to-End Optimization from Prefill to Decode
The value of latent-space sparse attention shows up not only at the algorithm level but also in engineering practice. In extremely long-context scenarios, the system bottleneck is often not a single computation but the combined result of memory access, scheduling, caching, and parallelism strategies.
8.1 Prefill Stage: Lowering the First-Build Cost
The prefill stage must process the entire context at once. This is where the latent-space index shows its greatest advantage, because it reduces the cost of “building the relevance catalog.” Engineering should note:
- Keep the low-dimensional index in memory or GPU memory as much as possible to reduce repeated data movement;
- Compute block-level summaries in batches to improve matrix-operation efficiency;
- Split candidate recall and candidate selection into parallelizable stages;
- Batch requests of different lengths to improve throughput;
- Set a candidate ceiling for extremely long requests so a single request does not drag down the whole service.
8.2 Decode Stage: Keeping the Incremental Index Consistent
In the decode stage, every newly generated token needs a decision on whether it should attend to historical tokens. If the latent-space index were rebuilt from scratch each time, the cost would be unacceptable. So it is recommended to maintain the latent-space index as persistent state, updated incrementally as generation proceeds.
Incremental maintenance includes:
- Adding new tokens to the low-dimensional index;
- Dynamically updating block summaries;
- Locally refreshing the candidate set as positions change;
- Evicting stale candidates to avoid unbounded cache growth;
- Ensuring the incremental index is representationally consistent with the prefill index.
8.3 Memory and Cache Design: Preventing the Index Cache from Cancelling the Sparsity Gains
At the ten-million-token scale, cache management is critical. Although sparse attention reduces the tokens participating in computation, the index structure itself still consumes resources. If the cache grows without bound, the index cache may cancel out the gains from sparse computation.
Set boundaries from the following angles:
- Index cache capacity ceiling: set a hard limit per request or per sequence. As a starting point, cap a single request’s index cache at 10%–20% of the available GPU memory per card, or at no more than half of the same request’s activation peak. Once exceeded, trigger eviction, dimensionality reduction, keeping only candidate-block indices, or on-demand recomputation.
- Layered cache content: prioritize caching low-dimensional block summaries, bucket centers, and candidate-token indices, and avoid caching too many raw intermediate representations.
- Eviction thresholds: trigger cache eviction or a degraded strategy when the GPU memory watermark exceeds 80%, cache hit rate falls below 70%, or prefill latency rises persistently.
- Eviction policy: use LRU, LFU, position-based decay eviction, or compression of candidates that have not been hit for a long time.
- Hit-rate monitoring: at minimum, monitor the index-cache hit rate, block-cache hit rate, eviction rate, recomputation rate, and candidate recall rate.
For ten-million-token contexts, index-cache governance is not a side item—it is a core part of whether the system stays stable.
8.4 Observability and Tuning Metrics
Latent-space sparse attention is not a fully deterministic black box. Different requests, context distributions, and block sizes all affect recall. So online systems need clearly defined monitoring metrics:
- Recall baseline: use dense attention, or high-weight tokens from smaller-scale contexts, as a reference to measure coarse-ranking coverage.
- Key-token retention rate: measure whether the fragments that truly affect the task enter the candidate set.
- Coarse-ranking hit distribution: observe whether candidate blocks concentrate in a few regions and whether there is systematic omission.
- P99 prefill latency: do not look only at average latency; long-tail requests must be watched.
- Generation-quality delta: compare task metrics between the sparse path and the dense baseline.
- Memory and bandwidth usage: monitor the resource footprint of the index cache, block summaries, and candidate sets.
Only by folding these metrics into routine monitoring can quality stay stable while pursuing speed.
9. Evaluation: How to Tell Whether the Approach Actually Works
In practice, you cannot judge solely by whether prefill speed drops; you must evaluate across multiple dimensions.
9.1 Recall
Recall measures whether the coarse-ranking stage misses important tokens. Construct a baseline: use attention weights from dense attention or from smaller-scale contexts as the reference, and observe whether the latent-space index can cover the high-scoring tokens.
One actionable criterion is to measure, on a validation set, the fraction of top-k attention tokens covered by the candidate set. If recall is below a preset target, first expand the candidate size or increase the latent dimension.
9.2 Downstream Task Accuracy
Long-context capability cannot be judged only by whether attention is sparse; you must also check whether task performance stays stable. Evaluation should cover:
- Long-document comprehension;
- Multi-hop question answering;
- Code repository analysis;
- Long-log summarization;
- Multi-turn conversation memory;
- Retrieval-augmented generation.
If task accuracy drops noticeably, it usually means the recall strategy is too aggressive or the latent representation is insufficient.
9.3 Latency and Throughput
Evaluate prefill latency, decode latency, batch throughput, and long-tail request behavior separately. In extremely long-context scenarios, long-tail requests can consume a large amount of resources, so you must look not only at average latency but also at P99 and P999 latency.
9.4 Resource Usage
Although the latent-space index reduces computation, it introduces extra cache and projection overhead. Watch GPU memory, host memory, bandwidth, and scheduling cost. If the index cache grows too large, it may cancel out part of the compute gains.
9.5 Stability
Context length, content distribution, language type, and code structure vary greatly across requests. The system must stay stable across many distributions, not just perform well on specific samples.
10. Applicable Scenarios, Rollout Advice, and Rollback Strategy
Latent-space sparse attention is especially suited to scenarios where the context length far exceeds a normal inference window and where the task depends heavily on local key information. Examples include:
- Ultra-long document analysis and summarization;
- Large code repository comprehension;
- Complex multi-turn conversation memory;
- Long-log and monitoring-data analysis;
- Knowledge-base retrieval augmentation;
- Long-horizon business auditing and compliance checks.
For rollout, a progressive strategy is recommended:
- First validate accuracy loss on smaller-scale contexts;
- Then gradually scale up to million- and ten-million-token contexts;
- Keep dense or semi-dense attention for critical business layers;
- Prioritize enabling the sparse index on non-critical layers;
- Bring recall, task accuracy, and P99 latency into unified monitoring;
- Dynamically adjust candidate size and block size according to traffic characteristics.
It is also advisable to prepare a rollback strategy. For example:
- When downstream task accuracy drops by more than 1%–2%, or the key-token retention rate falls below target, first enlarge the candidate size by 1.5×–2×;
- If enlargement still does not meet the target, reduce block_size, increase r, or restore the local window;
- For high-risk business paths, temporarily switch back to dense or semi-dense layers;
- For extremely long requests, apply a degradation strategy such as keeping only block summaries, reducing the candidate count, or processing in shards.
For enterprise-grade systems, relying on algorithmic optimization alone is not enough. It also takes combining inference serving, cache management, log tracing, monitoring and alerting, and elastic scaling to build a stable ultra-long-context capability.
11. Summary
Sparse attention solves the question of “whether every token must be computed,” while latent-space sparse attention further addresses the deeper question of “how to find the tokens that need computing at low cost.” At the million-token scale, this difference may be just a performance optimization; at the ten-million-token scale, it may decide whether the system is viable at all.
Its core idea can be summarized as: move relevance discovery from the original high-dimensional space into a low-dimensional latent space, reduce candidate cost through coarse-ranking recall, and then preserve effectiveness through fine ranking and sparse computation. Sub-quadratic behavior is not an unconditional conclusion; it is achievable only when approximate retrieval, hierarchical indexing, bucketing and clustering, causal constraints, and cache governance all hold together.
For technical teams that want to build ultra-long-context capability, the key is not simply applying a particular sparse strategy, but understanding the change in the cost structure and designing the latent-space index, recall quality, accuracy preservation, and engineering governance as a whole. Only with joint optimization of algorithms and systems can stable, efficient, and scalable attention inference be truly achieved at the ten-million-token scale.
