A New Path to Sparse Attention Acceleration at Ten-Million-Token Context: Latent-Space Indexing

    This article examines why sparse attention does not automatically make attention linear as context length grows toward the ten-million-token scale, and how latent-space indexing offers a new path forward. It breaks down the cost of attention in both the prefill and decode stages, explains why the indexer's candidate-search cost becomes the dominant bottleneck at extreme context lengths, and details the four sources of that hidden overhead. It then introduces latent-space sparse attention, which projects queries and keys into a low-dimensional space for coarse filtering and candidate recall, and shows how layered filtering can bring indexing cost from near-quadratic down to near-linear. The article also covers projection design, engineering optimizations for prefill and decode, precision-preservation strategies, applicable scenarios, and deployment guidance for ultra-long-context systems.

    1. Problem Background: Ultra-Long Context Is Pushing Attention Cost to a New Order of Magnitude

    As large-model applications move from ordinary question answering toward long-document understanding, codebase analysis, conversation-history compression, log diagnostics, and multi-turn agent collaboration, context length is becoming a key metric in model capability competition. Million-token context has gradually shifted from a “capability showcase” to a “usable capability,” while ten-million-token context is beginning to appear in ultra-long documents, cross-file retrieval, long-term memory, and complex system analysis.

    But increasing context length is not simply a matter of making the input longer. The core problem of the attention mechanism is: for each newly generated query, which positions in the historical sequence should it attend to? Under full attention, every query must compute relevance against all historical keys and values, so the computation in the prefill stage grows quadratically with context length. When context grows from 1 million to 10 million tokens, the theoretical attention computation increases by roughly 100x. Even as hardware compute keeps improving, this growth still places enormous pressure on training, inference, and engineering deployment.

    Sparse attention arose precisely to address this pressure. Its basic premise is that not all historical tokens are equally important, and when generating each new token, the model often only needs to reference a few of the most critical context segments. If some mechanism can quickly locate this key information, attention computation can be compressed from “traversing the entire history” to “focusing on a small window.”

    However, once context reaches the ten-million-token scale, the problem changes. In the past, the main concern was that “attention computation is too expensive”; now the more prominent problem has become that “the act of finding the few tokens that need attention is itself too expensive.” Sparse attention can significantly reduce the number of keys and values that actually participate in computation, but if the indexer still has to evaluate a large number of candidate positions for each query, the indexing stage can still become the main bottleneck.

    2. Cost Structure Breakdown: Sparse Attention Is Not Naturally Linear

    To understand this contradiction, we first need to break down the cost composition of attention.

    In the standard attention mechanism, let the context length be T and the hidden dimension be d. The query-key matching in the prefill stage roughly requires O(T²d) computation. Although the decode stage generates only one new token at a time, it still needs to match against the keys and values in the historical cache, with a per-step cost of about O(Td). When T grows from the million to the ten-million scale, this cost is amplified rapidly.

    Sparse attention typically works in two stages:

    1. Indexing stage: select the k most relevant positions for the current query.
    2. Computation stage: perform exact attention computation only on these k positions.

    If the indexing stage can be done efficiently, the attention computation itself can drop from O(Td) to O(kd). When k is far smaller than T, this can theoretically save a great deal of computation and memory access.

    The problem is that indexing itself is not free. The most naive sparse attention implementation must compute a similarity score between the query and every candidate key/value, then select the top k. This scoring process itself may still be on the order of O(T²d) or close to O(T²). In other words, if the indexer merely shifts the overhead originally used for “computing attention” to “computing the candidate set,” the overall cost structure has not truly changed.

    This is the hidden bill of sparse attention in ultra-long-context scenarios: it saves the high-cost exact attention, but may retain candidate-search costs that are equally expensive or even more so. When the context length is only a few hundred thousand tokens, this bill may still be acceptable; but at the ten-million scale, the indexer’s time cost may far exceed that of attention itself.

    3. Where the Hidden Bill Comes From: Four Types of Indexer Overhead

    3.1 Full Scoring Overhead

    The most direct problem is that if the indexer must compute relevance one by one for every query and every key/value, its complexity still grows close to quadratically. Even using lower precision, dimensionality-reduced vectors, or block compression only lowers the constant factor, not necessarily the order of magnitude.

    3.2 Candidate Bloat from Block Sparsity

    Many approaches first split the context into blocks and then score the blocks. This does reduce the number of exact comparisons, but if too many blocks are retained for recall, or if each block still needs further fine-grained ranking, the indexing overhead accumulates again. Larger blocks make coarse filtering cheaper, but require finer ranking over more tokens within the candidates; smaller blocks make fine ranking more precise, but increase the number of blocks and the scheduling cost.

    3.3 Memory Access and Scheduling Overhead

    In ultra-long-context scenarios, the key/value cache is often very large. Even if computation can be compressed, candidate filtering still requires reading large amounts of vector data. When GPU memory, memory bandwidth, or cache hit rate become bottlenecks, the indexing stage may be slowed not by arithmetic but by data movement. In addition, dynamic candidate sets introduce irregular memory-access patterns that further reduce hardware utilization.

    3.4 Precision Loss and Error Propagation

    The indexer is not a perfect oracle. If the candidate set is chosen incorrectly, no amount of accuracy in the subsequent exact attention can recover it. More complexly, in long-context tasks key information is often scattered across multiple positions, or depends on low-frequency but important cues. Once the indexer systematically favors high-salience tokens, the model may lose long-tail information. So sparse attention must pursue not only being “fast” but also selecting “accurately.”

    4. The Core Idea of Latent-Space Sparse Attention

    A class of new directions recently proposed in the industry moves the indexing process from the original high-dimensional representation into a low-dimensional latent space. These methods are usually called latent-space sparse attention, and their goal is not to simply replace the attention computation but to restructure the cost of candidate selection.

    The core idea can be summarized as:

    Rather than computing full relevance directly in the high-dimensional key/value space, first use learnable projections to map queries and keys/values into a low-dimensional latent space, perform low-cost coarse filtering there to generate a small set of candidates, and then run exact attention only on the candidate set.

    Expressed with a simplified formula:

    Let the query vector be q, the key vector be k, and the original dimension be d. The standard score can be written as:

    s = qᵀk / √d

    Latent-space sparse attention introduces a projection step:

    q̃ = Wq q
    k̃ = Wk k

    and computes an approximate score in the low-dimensional space:

    s̃ = q̃ᵀk̃ / √d_l

    where d_l is usually far smaller than the original dimension d. If the projection can preserve enough similarity-ranking information, candidate generation can be completed at lower cost.

    However, dimensionality reduction alone is not enough. If we still score every candidate one by one, the complexity may still approach quadratic growth. What really matters is that the latent space must not only be “cheaper” but also able to support “layered filtering” and “candidate convergence.”

    So a more complete latent-space sparse attention typically has three levels:

    1. Coarse filtering: low-cost estimation at the block, bucket, or summary level.
    2. Candidate recall: selecting a small number of high-potential regions from a large number of historical segments.
    3. Fine ranking and computation: performing more precise relevance evaluation on the tokens within candidate regions, then executing sparse attention.

    The significance of this structure is that it turns the indexer from “item-by-item full comparison” into “first locate the region, then look closely at the positions,” giving it a chance to compress the indexing cost from near-quadratic growth to near-linear or sublinear growth.

    5. Why It Can Achieve Sub-Quadratic Cost

    For sparse attention to truly solve the ten-million-token context problem, it cannot merely reduce attention computation from O(T²) to O(Tk); it also needs to reduce candidate indexing from O(T²) to a lower order.

    The advantage of latent-space sparse attention is that it can split the indexing process into multiple stages:

    • Use low-dimensional projection to reduce the cost of each scoring operation;
    • Use block means, summary vectors, bucketing, or approximate nearest neighbor structures for coarse filtering;
    • Run fine ranking only on a small number of candidates;
    • Finally, perform exact attention only on a fixed-size top-k set.

    If the candidate-set size does not grow proportionally with context length, or grows only slowly, then the overall complexity can approach:

    O(T · C + T · k)

    where C is the coarse-filtering candidate size and k is the final number of retained tokens. When both C and k are determined by business constraints and are far smaller than T, the indexing cost drops from quadratic to near-linear.

    It must be emphasized that this does not mean all latent-space sparse attention implementations are naturally sub-quadratic. If the number of candidate blocks swells in step with T, or if the cost of building the approximate nearest neighbor index is too high, the overall complexity can still degrade. So the real key is whether the candidate set is controlled, whether the index structure is scalable, and whether the projection is stable.

    6. Key Design Points for Latent-Space Projection

    The success or failure of latent-space sparse attention depends largely on whether the projection is designed reasonably.

    6.1 Preserve Ranking, Not the Original Vectors

    The indexer’s goal is not to perfectly reconstruct the original key/value vectors but to preserve the relative ranking between queries and candidates as much as possible. So projection design should focus on top-k recall rather than pure vector reconstruction error. A low-dimensional representation is still valuable as long as it can keep the most relevant segments at the top, even if it cannot recover the original vectors.

    6.2 Distinguish the Roles of Different Layers

    Different attention layers have different needs for context. Shallow layers tend to focus more on local syntax and neighboring semantics, while deep layers may take on global information integration. Using the same indexing strategy for all layers may not be optimal. In engineering, some layers can keep local-window attention while others use sparse global indexing, balancing precision and efficiency.

    6.3 Coarse Filtering Must Allow Some Over-Recall

    To reduce precision loss, the coarse-filtering stage usually should not keep only the final k candidates but retain more potential candidates, such as several times k candidate blocks or candidate tokens. Over-recall means the indexing stage does a bit more work, but it significantly lowers the risk of missing key information. Truly efficient methods do not compress the candidates to the minimum but keep them at a stable, predictable, batch-processable size.

    6.4 Fine Ranking Must Compensate for Expressive Capacity

    The low-dimensional latent space can only provide approximate ranking; in the end, we still need to return to the original representation for exact scoring. The fine-ranking stage can effectively correct the ranking bias introduced by the projection. Ideally, coarse filtering is responsible for finding the broad region, fine ranking for pinning down the small position, and the final sparse attention for computing the key values.

    7. Key Optimization Points in Engineering Implementation

    7.1 Optimize Prefill and Decode Separately

    The prefill stage faces long sequences, focusing on candidate filtering and batched attention computation; the decode stage generates only one new token at a time, focusing on key/value cache reads and candidate-index reuse. The two have different bottlenecks and cannot use the same optimization strategy.

    Prefill can reduce total time through chunked computation, batching, asynchronous indexing, and caching candidate sets; decode is better suited to incremental indexing, local caching, and fixed candidate sets to avoid re-scanning the global context for every generated token.

    7.2 Cache Candidate Results, Not Full Relevance

    During continuous decoding, the regions of interest across many queries are similar. In engineering, we can cache recently high-frequency candidate blocks or candidate tokens to reduce repeated indexing. Note that the caching strategy should have an invalidation mechanism to avoid stale candidates due to context changing too quickly.

    7.3 Parallelize Indexing and Attention Computation as Much as Possible

    If indexing and exact attention must run serially, overall latency is limited. A common optimization idea is to break candidate generation, candidate fine ranking, and attention computation into stages that can be pipelined. Before the coarse-filtering results are fully complete, some candidates can already enter fine ranking; once fine-ranking results stabilize, attention computation can start asynchronously.

    7.4 Control the Predictability of Candidate Size

    Dynamic candidate sets easily cause irregular memory access and scheduling jitter. In engineering, we should keep the candidate-set size relatively stable, such as a fixed number of candidate blocks or a fixed upper limit on candidate tokens. Predictable overhead is easier to batch, easier to manage in GPU memory, and easier to guarantee latency for.

    8. Illustrative Flow: How Latent-Space Sparse Attention Works

    The following pseudocode shows a generic flow; actual implementations involve more complex index structures, caching strategies, and training-alignment mechanisms.

    1. Input:
    2. q: current query set
    3. k: historical key set
    4. v: historical value set
    5. d_l: latent-space dimension
    6. n_blocks: number of blocks kept by coarse filtering
    7. k_keep: final number of retained tokens
    8. Steps:
    9. 1. Project q and k into the low-dimensional latent space
    10. q_lat = project_q(q)
    11. k_lat = project_k(k)
    12. 2. Aggregate historical keys by block to get block-level summaries
    13. block_summary = block_reduce(k_lat)
    14. 3. Compute the similarity between the query and the block summaries
    15. block_score = q_lat * transpose(block_summary)
    16. 4. Select the blocks with the highest scores
    17. selected_blocks = topk(block_score, n_blocks)
    18. 5. Expand the keys/values within the selected blocks into a candidate set
    19. candidate_ids = collect(selected_blocks)
    20. 6. Fine-rank on the candidate set
    21. exact_score = q * transpose(k[candidate_ids]) / sqrt(d)
    22. final_ids = topk(exact_score, k_keep)
    23. 7. Execute attention only on the final candidates
    24. output = attention(q, k[final_ids], v[final_ids])
    25. Return:
    26. output

    The key to this flow is not how complex any single step is, but that the overall structure turns “global search” into “local fine ranking,” giving it a chance to control the indexing cost.

    9. Precision Guarantees: Sparse Attention Can’t Look Only at Speed

    In ultra-long-context scenarios, precision problems are usually more subtle than in ordinary short contexts. When the model generates a given answer, it may depend on only a very few key segments, and those segments do not always appear frequently. If the indexer over-favors local, recent, or high-salience content, the model may lose key information across chapters, across files, or across turns.

    To reduce the risk, the following strategies can be adopted:

    9.1 Multi-Granularity Candidate Retention

    In addition to fine-grained token candidates, block-level, paragraph-level, or summary-level candidates can also be retained. This way, when the model encounters long-distance dependencies, it at least does not completely lose global cues.

    9.2 Hybrid of Local Window and Global Sparsity

    Pure global sparsity may not stably capture short-range semantics, while a pure local window cannot cover long-distance dependencies. Actual systems can adopt a hybrid structure: dense or window attention for short ranges, sparse indexing for long ranges. This both controls cost and preserves local language-modeling quality.

    9.3 Simulate Indexing Error During Training

    If the indexer is introduced only at inference time, it may be inconsistent with the full-attention distribution used during training. A more robust approach is to simulate the sparse-selection process during continued training or alignment, letting the model adapt in advance to “should-have-been-selected but wasn’t,” candidate noise, and indexing bias.

    9.4 Continuously Monitor Candidate Quality

    In production, we should continuously observe candidate recall, top-k hit rate, long-tail request precision, and degradation across different task types. For scenarios sensitive to key details such as finance, healthcare, and law, more rigorous regression testing and manual spot-checking mechanisms are needed.

    10. Applicable Scenarios and Deployment Recommendations

    Latent-space sparse attention does not need to be enabled in every scenario. For short contexts, strong local semantics, or extremely latency-sensitive tasks, full attention or lightweight sparse attention may already be enough. It is more suitable for the following scenarios:

    • Ultra-long document summarization and question answering;
    • Large code-repository retrieval and cross-file understanding;
    • Long-term conversation memory compression;
    • Root-cause analysis of logs, monitoring data, and system events;
    • Long-range dependency reasoning in multi-turn agent tasks;
    • Prefill tasks that need to load a large amount of historical tokens at once.

    When deploying, we recommend the following path:

    1. First establish a full-attention or standard sparse-attention baseline, clarifying latency, memory, and precision metrics.
    2. Collect context-length distribution statistics for typical requests, identifying the proportion of long-context requests.
    3. Analyze which layers are best suited for global indexing and which can retain local attention.
    4. Validate candidate recall and task precision on a small amount of traffic, then gradually expand the candidate-control range.
    5. Combined with caching, batching, and a monitoring/alerting system, observe whether long-tail requests show stability degradation.

    At the platform level, ultra-long-context capability often involves model inference, feature caching, task scheduling, and observability at the same time. We can use object storage to store long-context caches or index summaries, use a container platform for elastic scaling, and combine logging services, monitoring alerts, and message queues to build a complete long-context inference pipeline. These general cloud capabilities do not solve the algorithmic problem themselves, but they can significantly improve the stability and operational efficiency of ultra-long-context systems in real business.

    11. Conclusion: From “Computing Fast” to “Selecting Accurately, Indexing Cheaply”

    The value of sparse attention has been repeatedly validated: in long-context scenarios, the model does not need to attend to the entire history at all times but only focus on a few of the most relevant positions, giving it a chance to balance precision and efficiency.

    But ten-million-token context has exposed a new bottleneck: the real cost is no longer just attention computation but the indexing process that decides “where to look.” If the indexer still approaches full scoring, sparse attention falls into the dilemma of “computation saved, search not saved.”

    Latent-space sparse attention offers a representative technical path: by performing coarse filtering and candidate recall in a low-dimensional latent space, it turns the indexing process from full comparison into layered filtering, and then, together with fine ranking and exact attention, lowers the overall cost under ultra-long context. It is not simply a matter of compressing dimensions but of reorganizing the candidate-generation flow, freeing the indexer from quadratic pressure.

    From an engineering perspective, the value of this path shows not only in prefill speedup but also in the scalability, schedulability, and operability of long-context inference. As context length keeps growing, relying on hardware stacking alone cannot solve all problems; coordinated optimization at the algorithm and system levels will become key. What latent-space sparse attention represents is precisely this new direction of moving from “reducing computation” to “reducing ineffective search.”