Sub-Quadratic Sparse Attention for Ten-Million-Token Contexts

    As context windows grow from hundreds of thousands to millions and then to tens of millions of tokens, the real challenge shifts from whether a model can understand more to whether attention can stay affordable. Standard full attention scales quadratically, and while sparse attention reduces the cost of "looking," the indexing step that decides what to look at can reintroduce a near-quadratic bottleneck. This article explains how latent-space sparse attention addresses this by moving candidate selection into a compact, lower-dimensional representation—coarse-filtering candidate blocks first, then fine-scoring in the original key space. It covers why this approach approaches sub-quadratic complexity, how to preserve accuracy without "seeing less," how to optimize prefill and decode separately in production, and why evaluation should measure effective context usage rather than maximum length.

    Ten-Million-Token Context Is Not Just Scaling Up — It Rewrites the Cost Structure

    When context length climbs from hundreds of thousands of tokens to millions, and then to tens of millions, the first problem a model faces is not “can it understand more content” but “can computation and scheduling still hold cost to an acceptable level.” In standard full attention, every query position must compute a relevance score against every key in the entire history, so as context length grows, the compute cost grows quadratically. Going from millions to tens of millions of tokens, the theoretical cost of the attention part alone can rise by two orders of magnitude.

    Sparse attention changes “compute everything” into “compute selectively.” It assumes the model does not need to attend to every piece of history word by word, but only needs to select a few of the most relevant key-value segments. This assumption has been widely validated in long-context tasks: as long as the candidate set is accurate enough, the model can achieve results close to full attention under a much shorter effective view.

    But as context keeps growing, a new problem surfaces: attention computation can be sparsified, yet the act of “finding the few pieces worth attending to” can itself be expensive. In other words, sparse attention lowers the cost of “looking,” but not necessarily the cost of “finding.” If the indexer has to score every historical key in full, then even if the subsequent attention only computes a small portion, overall latency is still held back by the indexing stage.

    The Hidden Bill of Sparse Attention: From a Compute Bottleneck to an Index Bottleneck

    In full attention, cost is concentrated in the pairwise interaction between queries and keys. For a context of length T, attention compute is roughly proportional to T squared. Sparse attention introduces an indexer that compresses the attention computation into a fixed or near-fixed local window, bringing the main cost down from T² to a near-linear form.

    But there is an easily overlooked premise here: the indexer must know which keys are relevant. If the indexer still evaluates every historical key one by one, it introduces its own quadratic or near-quadratic search cost. So the bottleneck of long-context inference shifts: time originally spent on the attention matrix now goes heavily into candidate generation, score computation, ranking and filtering, and block-level routing.

    In ten-million-token scenarios, this shift is especially pronounced. The longer the context, the larger the candidate space, and any naive full scoring becomes unacceptable. Even reducing index dimensions, compressing key representations, or merging adjacent segments only eases the burden — it does not fundamentally remove the quadratic growth. What really needs solving is giving the indexing process itself sub-quadratic, or even more efficient, retrieval capability.

    The Core Idea of Latent-Space Sparse Attention: Don’t Search Hard in the Raw Token Space

    Latent-space sparse attention is not simply truncating the raw key-value sequence. Instead, it moves the process of “finding the most relevant segment” into a more compact, more abstract representation space. Its core idea can be summarized as: coarse-filter first, then fine-select.

    Concretely, raw key-value segments usually carry high-dimensional information, and computing similarity across all segments directly is costly. The latent-space approach first maps keys into a low-dimensional latent representation, forming a kind of “summary index” or “compressed index.” The query is also projected into the same latent space and does an initial match against the compressed key summaries. Because the latent representation is lower-dimensional and more concentrated in information density, this stage can quickly produce a candidate set — say, a handful of candidate blocks or buckets.

    Then the system goes back to the raw key-value representation only within the coarse-filtered candidate range for fine-grained scoring, and finally selects the true top-k segments that actually participate in attention. This compresses the expensive full comparison into a “small-scale candidate re-check,” significantly lowering the overall complexity.

    A simplified pseudocode flow:

    1. for each query q_i:
    2. q_latent = project_query(q_i)
    3. block_scores = q_latent · latent_keys^T
    4. candidate_blocks = top_k(block_scores, B)
    5. candidate_scores = []
    6. for block in candidate_blocks:
    7. raw_scores = q_i · raw_keys[block]^T
    8. candidate_scores.extend(raw_scores)
    9. selected = top_k(candidate_scores, k)
    10. output_i = softmax(selected) · raw_values[selected]

    Two parameters are key here: B is the number of candidate blocks selected by coarse filtering, and k is the number of keys that finally participate in attention. The larger B is, the more complete the recall, but the index and re-check costs rise; the smaller B is, the faster it runs, but there is a risk of missing key segments. k directly determines the precision and local compute of the sparse attention. In engineering, these need to be jointly tuned based on task length, model architecture, memory budget, and latency targets.

    Why Latent-Space Methods Approach Sub-Quadratic Complexity

    From a complexity standpoint, the advantage of latent-space sparse attention comes from three levels.

    First, representation compression reduces the index dimension. Raw key vectors are often high-dimensional, and searching directly in the full space puts heavy pressure on both compute and storage. After projecting keys into a low-dimensional latent space, similarity computation can be done over smaller dimensions. Projection itself needs extra computation, but it can usually be parallelized and optimized during training so the index representation better fits the attention distribution.

    Second, block-level routing shrinks the candidate scale. Splitting the context into blocks and using each block’s summary vector to represent its content lets the indexer first judge which blocks are worth attending to, instead of evaluating token by token. This turns the search space from “all tokens” into “a few candidate blocks,” significantly reducing complexity. Block-level routing also pairs well with caching, paging, and scheduling systems.

    Third, two-stage filtering avoids excessive precision loss. Relying only on the low-dimensional latent space for the final selection could miss truly important segments due to compression error. So after coarse filtering, going back into the raw key space for fine scoring strikes a balance between speed and quality. Coarse filtering expands the recall boundary; fine filtering guarantees selection quality.

    Overall, the goal of this class of methods is not to push the total complexity down to strictly linear, but to turn the quadratic term that grows rapidly with context length into a controllable, approximate retrieval cost — making ten-million-token prefill engineering-feasible.

    The Key to Preserving Accuracy: Not “Seeing Less,” but “Misseeing Less”

    Whether sparse attention can be deployed ultimately comes down to a plain question: can the model tolerate occasionally not seeing everything? In practice, many tasks do not depend on all historical information but on a few key segments. Yet if the candidate selection is wrong, output quality drops noticeably no matter how fast the subsequent attention is. So the engineering value of latent-space sparse attention depends not only on index speed but also on index quality.

    Accuracy stability can be improved along several dimensions.

    First, the index representation needs to align with attention semantics. If the latent space is only a naive compression without task-aware training, it may diverge from what the model actually attends to. A more ideal approach is to use joint training, distillation, or contrastive objectives so the indexer learns to recognize the context segments the model truly attends to.

    Second, multi-granularity information needs to be preserved. Only global summaries can lose local detail; only local windows can miss long-range dependencies. A common practice is to combine global state, block-level summaries, local windows, and the final sparse segments. Local segments handle precise retrieval, while global state carries long-distance context memory — the two complement each other.

    Third, linear or state-based attention can be part of a hybrid structure. Sparse attention is good at jumping between local and key segments, while linear attention or state-compression mechanisms are better at maintaining a low-cost global context representation. Combined, the model neither does full pairwise computation over all tokens nor loses overall context through over-sparsification.

    In addition, positional encoding and context extrapolation also affect long-context stability. When training length and inference length differ, the distribution of positional information drifts. Even if the indexer finds the right content, the model’s perception of position can be off. So a long-context system usually needs to consider position scaling, training coverage, data distribution, and task evaluation together, rather than focusing only on index speed.

    Engineering in Production: Prefill and Decode Need Separate Optimization

    In a real inference service, sparse attention is not an isolated algorithm — it must be designed together with caching, scheduling, parallelism, and monitoring.

    The prefill stage usually takes a large chunk of context into the model at once, and the bottleneck concentrates on the indexer and the initial attention computation. This is where latent-space sparse attention delivers the most obvious value. In engineering, you can fuse index projection, block summaries, candidate filtering, and fine scoring into the same execution flow to reduce writing intermediate results to disk or waiting on synchronization. For long-text inputs, you can also use chunked prefill, processing different blocks in parallel and generating candidate indices as soon as each block completes.

    The decode stage cares more about per-token generation latency and cache hits. Here, historical key-values are usually already cached in GPU memory or fast storage, so the indexer does not need to reprocess all history — it does incremental updates using already-generated block summaries or latent indices. This makes generation cost depend mainly on candidate lookup and local attention computation, not full recomputation.

    At the system level, several points are worth noting.

    First, index results need to be cacheable and reusable. For multi-turn dialogues or repeated long contexts, block summaries and candidate indices can be reused across requests to cut redundant computation.

    Second, synchronization between the indexer and attention computation should be minimized. Candidate filtering, sorting, and local attention can be pipelined to avoid serial waiting on the critical path.

    Third, memory management needs to be redesigned for long context. In ten-million-token scenarios, the key-value cache itself is a huge burden. Paging, block-level release, hot/cold tiering, and on-demand loading are common techniques.

    Fourth, monitoring and observability need fine granularity. Beyond first-token latency and throughput, you should watch index recall, candidate block hit rate, sparsity ratio, peak memory, and request queue time. Anomalies in long-context inference are often not caused by a single module but by the joint effect of indexing, caching, and scheduling.

    In cloud service scenarios, this capability usually needs to combine with general infrastructure such as elastic scheduling, logging services, monitoring and alerting, object storage, and message queues. For example, input segments of long-context requests can be cached in object storage, a task queue handles peak shaving, monitoring systems track per-stage latency, and the container platform adjusts resources dynamically based on load. Algorithm optimization only becomes stable production value when combined with system capability.

    Evaluation Can’t Look Only at Maximum Length — It Must Look at Effective Context

    Long-context model evaluation often has a misconception: focusing only on whether the system can accept longer input while ignoring whether the model actually uses the context. Ten-million-token capability, without task-level validation, easily becomes “input-able but not usable.”

    A more reasonable evaluation should cover multiple layers.

    The first is recall evaluation. Given a question or the location of key information, can the system select the relevant segments into the candidate set? Here you look not only at whether the final output is correct, but also at whether the indexer missed key information.

    The second is task-effect evaluation. This includes long-document QA, multi-hop reasoning, long-text summarization, codebase understanding, log root-cause analysis, and meeting-note extraction. Different tasks have different sensitivity to the sparse strategy — some rely on global summaries, others on precise segment localization.

    The third is system-performance evaluation. This includes prefill latency, decode throughput, first-token time, peak memory, cache hit rate, and the share of indexing overhead. Sparse attention only has production value when performance gains do not come at a significant precision cost.

    The fourth is stability evaluation. Long-context systems often face uneven request-length distributions, repeated inputs, and concentrated hotspot segments. You need to observe behavior under different traffic patterns in a canary environment to avoid a local optimum masking global problems.

    From “How Long It Supports” to “At What Cost It Supports That Long”

    Early long-context competition focused mostly on window length, but the core question in the next stage is shifting toward per-token cost, effective context utilization, and inference-service stability. Sparse attention matters precisely because it no longer treats context length as an incompressible input, but turns it into a structured object that can be retrieved, compressed, and cached.

    The significance of latent-space sparse attention is not just pushing attention compute lower — more importantly, it frees the indexing process from the burden of quadratic growth. It shows that long-context optimization cannot stop at the attention-matrix level; it must also optimize the index representation, candidate generation, hybrid memory structure, and the runtime system together.

    For developers, a truly deployable long-context solution usually needs to satisfy four conditions at once: fast enough indexing, accurate enough candidates, economical enough compute, and stable enough systems. Only when the algorithm and engineering evolve together can ten-million-token context go from a capability metric to a scalable service experience.