Can Sparse Attention Go Even Faster at 10M-Token Contexts?
As context windows move from the million-token range toward 10 million tokens, sparse attention faces a new bottleneck: finding the relevant tokens can cost more than computing attention over them. This article explains why token-space sparse attention still incurs quadratic indexing overhead, how Latent Sparse Attention (LSA) moves retrieval into a low-dimensional latent space, what reported speedups actually mean, and how to evaluate, deploy, and capacity-plan long-context inference systems.
1. Long Context Enters the 10M-Token Era
Over the past two years, context windows have expanded much faster than hardware compute capacity. A 128K context window is now common among open-source models, and major providers increasingly treat million-token context as a baseline capability for long-document services. At the same time, mechanisms such as sparse attention and linear attention are being incorporated into model architectures, resulting in hybrid attention designs.
However, the maximum context a model can accept is not the same as the time required to process it. As context grows toward 10 million tokens, previously secondary costs begin to dominate.
One study estimated that, during 10M-token prefill for a model using global attention, approximately 98% of the computation time in a single layer was spent in the indexer—the component that decides which tokens to attend to. The actual attention computation accounted for only a small fraction.
This changes the central challenge for sparse attention. It has already shown that a model can preserve accuracy while looking at only a small subset of tokens. The real limitation is that finding those tokens may still scale quadratically with context length.
A research team addressed this problem by moving retrieval into a low-dimensional latent space and proposed Latent Sparse Attention (LSA). According to the paper, at a 10M-token context, single-layer prefill speedups were approximately:
- 22.7× for a lightweight model from a major provider that relies primarily on global attention with sparse indexing;
- 72.4× for a billion-scale open-source model family using block-sparse attention.
In the analysis below, both baselines are referred to as token-space sparse attention. We first examine the hidden cost of sparse retrieval, then explain LSA’s design, and finally discuss engineering and deployment considerations.
2. Cost Structure: Sparse Attention Reduces Computation but Leaves Retrieval Behind
2.1 Full Attention: Where Quadratic Growth Begins
In standard multi-head attention, every query computes relevance against all historical keys and then produces a weighted sum of the corresponding values. Let the context length be (T), and let the per-head dimension be (d):
- During prefill, the attention workload is approximately (4T^2d), or (O(T^2));
- During decoding, each generated token interacts with (T) historical keys, so the cost per step is (O(T)).
When context grows from 1M to 10M tokens:
- Prefill attention computation increases by 100×. Even at an effective rate of (10^{15}) floating-point operations per second, the attention component alone can require thousands of seconds, excluding MLP and other model components;
- Per-token decoding cost increases by 10×.
2.2 Sparse Attention: Division of Labor, Not Elimination
Sparse attention divides the work:
- A lightweight indexer scores keys for each query and selects the (k) most relevant ones;
- Full attention is computed only over the selected keys.
The attention component then requires approximately:
[
2Tkd
]
or (O(Tk)). When (k) is fixed, this grows linearly with (T).
The approach is viable because a query often needs only a small number of historical tokens. In one 128K-context evaluation, each query attended to its 512 most relevant keys—about 0.8% of all keys—while retaining approximately 98% of full-attention accuracy on long-context benchmarks.
Most historical tokens are background information for a given query. This provides a strong basis for sparse selection.
2.3 The Paradox: To Look at Less, the Model Must First Look Everywhere
To identify the 512 relevant keys, however, the indexer must score all keys. Relevance is a global property and generally cannot be determined from local information alone.
Existing sparse-attention methods—including dynamic sparse indexing, block-level sparse selection, and multi-token compression—attempt to reduce the per-element cost of indexing through techniques such as:
- Lower-precision relevance scoring;
- Lower-dimensional index vectors;
- Compressing adjacent keys into block representatives, followed by block selection and within-block refinement;
- Sharing selection results across attention heads or layers to avoid repeated retrieval.
These techniques reduce constant factors, but they do not change the fact that the indexer must scan the entire history. At million-token context lengths, this may be sufficient to make indexing a secondary cost. At 10M tokens, the quadratic term grows enough to make the indexer dominant again.
That is the hidden bill of sparse attention.
2.4 The Hidden Cost Goes Beyond FLOPs
Non-materializable score matrices. If a block-sparse system writes query-to-block relevance scores to GPU memory, the matrix contains:
[
T \times (T/b)
]
entries, where (b) is the block size. With (T=10M) and (b=128), this corresponds to approximately (7.8\times10^{11}) entries. Even at half precision, the matrix would exceed 1 TB and cannot be materialized.
Implementations must therefore fuse scoring, block-level reduction, top-k selection, and candidate gathering into a small number of operators, keeping intermediate results in caches and registers.
Sensitivity to numerical precision. Indexers often use low precision or quantization. Relevance scores may span a wide numerical range across long sequences before softmax, making them vulnerable to overflow or the loss of weak but important signals.
Scalar-operation bottlenecks. Top-k selection, sorting, and gather operations rely heavily on scalar processing. They are difficult to map efficiently to tensor cores, and their instruction granularity can be relatively coarse. As a result, actual indexing performance may be worse than a FLOPs-only estimate suggests.
Amplification across layers. Every attention layer repeats the score-and-select process. Even if the indexer takes only a few milliseconds per layer, the cost becomes substantial across dozens of layers. In long-context evaluations such as RULER, retrieval-oriented tasks are particularly sensitive to context length and are often among the first to degrade when indexing quality declines.
3. LSA: Moving Retrieval into a Low-Dimensional Latent Space
3.1 Overall Design
LSA’s basic idea is to avoid scoring every key in the original token space. Instead, it compresses the KV history into compact, low-dimensional memory codes, performs coarse retrieval in a latent space, and then returns to the original token space for fine ranking and sparse attention.
Based on the public paper abstract, the process can be summarized in four stages:
- Low-dimensional memory codes: Each key, or each block containing keys, is represented by a vector much smaller than the original representation. It acts as a semantic fingerprint for a segment of history.
- Latent-space coarse retrieval: The query is projected into the corresponding latent space and compared with memory codes to identify candidate blocks.
- Candidate-level reranking: Fine-grained scoring is performed only on the original tokens within the candidate blocks, producing the final set of (k) keys.
- Sparse attention: Standard attention is computed only over the selected keys and values.
The final two stages are similar to existing token-space sparse methods. LSA changes how candidate regions are located.
3.2 Three Key Changes
First, retrieval moves from tokens to latent representations.
Let the original dimension be (d), and let the memory-code dimension be (d’), where (d’\ll d). The number of scoring units is reduced from (T) tokens to (T/b) blocks.
- The coarse-retrieval workload is roughly (T^2d’/b), compared with (T^2d) for token-space scoring;
- The reduction factor is approximately (db/d’);
- With (d=128), (d’=16), and (b=128), the theoretical reduction is approximately 1,024×.
Fine ranking processes only (m) candidate blocks and is therefore independent of the total sequence length.
Second, the indexer becomes less memory-bound.
There are only (T/b) memory codes. For a 10M-token sequence divided into blocks of 128, this is approximately 78,000 memory codes. The compact representation can remain in high-speed cache or, depending on the implementation, fit into on-chip storage.
This changes the execution profile:
- Each scoring operation is more likely to remain in a compute-dense matrix-multiplication regime;
- Random memory access becomes less dominant;
- Low-precision computation can be used more efficiently.
Third, fine-grained selection is deferred.
Coarse retrieval is responsible for minimizing missed regions, while fine ranking determines the most relevant individual tokens. Semantically related passages may be distributed across different parts of a document, and block boundaries can separate them. Latent-space matching helps preserve coverage before token-level ranking makes the final selection.
The following pseudocode illustrates the data flow. It omits distributed partitioning, causal masking, and variable-length sequence handling:
def lsa_attention(Q, K, V, mem_codes, proj_q):"""Latent Sparse Attention (illustrative)Shapes:Q/K/V : [B, H, T, d] Multi-head query/key/valuemem_codes: [B, H, M, d'] Memory codes,M = ceil(T / block_size)proj_q : [d, d'] Projection into latent spaceFlow:1. Coarse retrieval: select m candidate blocks in latent space2. Fine ranking: select k keys from candidate blocks3. Sparse attention: attend only to selected keys and valuesA production implementation should fuse stages 1 and 2and execute them in hardware-aligned tiles."""q_lat = Q @ proj_q # [B, H, T, d']# Returns candidate blocks [B, H, T, m]# and final keys [B, H, T, k]idx_blk, idx_k = fused_coarse_to_fine(q_lat, Q, K, mem_codes)K_sel = gather(K, idx_k) # [B, H, T, k, d]V_sel = gather(V, idx_k) # [B, H, T, k, d]scores = (Q @ K_sel.transpose(-1, -2)) / sqrt(Q.shape[-1])return softmax(scores) @ V_sel
4. How to Interpret the Reported Results
4.1 The Speedups Reduce Constants, Not Asymptotic Complexity
A 22.7× or 72.4× speedup suggests that LSA reduces the indexer’s constant factors by one or two orders of magnitude. It does not eliminate the quadratic growth of the coarse scoring step.
Using the cost model from Section 2.4, the token-space indexer can be approximated as:
[
t_{\text{idx}}\approx cT^2d
]
For a lightweight model with (c\approx2.5\times10^{-13}):
- At (T=1M), indexing takes approximately 32 seconds;
- At (T=10M), it takes approximately 3,200 seconds.
If LSA reduces the indexing constant by roughly 100×, the corresponding estimates become:
- Approximately 0.32 seconds at 1M tokens;
- Approximately 32 seconds at 10M tokens.
The indexer still grows by 100× whenever context grows by 10×. LSA shifts the quadratic curve downward; it does not turn the algorithm into a strictly subquadratic method. Capacity planning must account for this distinction.
4.2 The Difference Between 22.7× and 72.4× Is Mainly a Baseline Effect
The lightweight model’s sparse indexer still scores at token granularity. It therefore carries substantial memory-access and kernel-launch overhead, leaving more room for LSA to improve performance.
The open-source model uses a block-sparse baseline that already has more parallelism and compression. Its theoretical optimization space is different.
Prefill length, batch organization, and baseline kernel quality also affect the result. The two speedups should not be compared directly or extrapolated to end-to-end latency.
4.3 Single-Layer Acceleration Is Not End-to-End Acceleration
Suppose attention accounts for 60% of a layer’s runtime and is accelerated by 22.7×. Amdahl’s law gives a theoretical layer-level limit of:
[
\frac{1}{0.4+0.6/22.7}\approx2.1\times
]
If attention represents only 30% of total model runtime, the overall theoretical limit is approximately 1.43×.
After attention is accelerated, new bottlenecks may appear in:
- MLP computation;
- Vocabulary projection;
- KV-cache writes;
- Scheduling and orchestration overhead.
Therefore:
- Evaluation should focus on end-to-end time to first token (TTFT), time per output token (TPOT), and throughput;
- Single-layer microbenchmarks are useful for locating bottlenecks but are not sufficient to estimate service-level gains;
- Lightweight models with a higher sparse ratio may obtain more visible end-to-end benefits than models dominated by full attention.
4.4 Similar Accuracy Does Not Mean Lossless Retrieval
“Similar accuracy” describes results on the evaluated tasks. Indexing errors can accumulate across attention layers. Tasks that require connecting distant pieces of evidence are often particularly sensitive to missed tokens.
Only evaluation on a representative production dataset can determine whether the quality loss is acceptable.
5. Deployment Guidance: From Bottleneck Diagnosis to Capacity Planning
5.1 First Identify the Bottleneck
For 10M-token prefill workloads:
- Use a flame graph or operator-level profiling to find the most time-consuming kernels;
- If scoring, selection, or gather operations dominate rather than attention computation, the indexer is the bottleneck;
- Measure performance at multiple context lengths, such as 1M, 2M, 4M, and 8M tokens. If runtime grows substantially faster than linearly, the quadratic term is becoming dominant.
Sparse-indexing optimization is valuable only after the indexer has been confirmed as the limiting factor.
5.2 Choose Based on Workload, Not on a Universal Winner
The following comparison assumes one attention head, one layer, original dimension (d=128), and (k=2048). The figures are order-of-magnitude examples. The coefficient (c) is empirical and depends heavily on the implementation and hardware.
| Attention method | Single-layer, single-head indexer time (1M / 10M) | Asymptotic complexity | Applicability |
|---|---|---|---|
| Full attention, no indexer | Approximately 2,048 / 20,480 seconds | (O(T^2)) | Practical only for shorter contexts |
| Block-sparse attention, block size 128 | Approximately 1 / 100 seconds | (O(T^2)), with constants determined by (b) and (d’) | Usable for medium and long contexts; constrained at 10M |
| Latent sparse attention, (d’=16), quadratic coarse retrieval | Approximately 0.008 / 0.8 seconds | (O(T^2)), with constants determined by (d’) and (b) | Significantly reduces 10M-token indexing cost |
| Latent sparse attention with bucket pruning, such as summarizing every 64 memory codes | Approximately 0.004 / 0.2 seconds | Approximately (O(T^{1.5})), or close to linear when the reduced bucket count is small or fixed | Suitable for 10M-scale workloads, with additional information loss |
These values illustrate relative scale only and do not represent any specific product. Bucket pruning is included to show how the asymptotic growth rate might be reduced; it is not necessarily part of LSA.
Three selection principles are particularly important:
- Choose according to the P95 context length. If the P95 context is within several hundred thousand tokens, a mature block-sparse implementation may already be sufficient. The training and evaluation cost of introducing a new indexer may not be justified.
- Separate mixed workloads by context length. Short and extremely long requests often have different optimal strategies. A short-context pool and a long-context pool can be deployed separately, with a gateway or routing layer directing requests based on length.
- Do not optimize only for throughput on quality-sensitive tasks. Contract review and long-report analysis should also track key-clause recall and agreement with human inspection. A general benchmark score alone is not enough.
5.3 Include Quadratic Growth in Capacity Planning
Assume the average business context grows by 3× every six months. If indexing still scales as (T^2), the compute required for the same workload will grow by approximately 9× over that period.
Techniques such as bucket pruning are valuable because they can reduce the growth slope toward linear. However, semantically related content may fall into different buckets, causing more information loss than block-level summarization.
The number of buckets and the within-bucket retrieval width should therefore be treated as joint quality-and-cost variables. Before deployment, run a two-dimensional sweep over accuracy and cost to find the largest bucket granularity that remains above the required quality threshold.
5.4 Protect Quality Through Training, Evaluation, and Engineering
Training. The sparse-indexing module may require separate training or joint fine-tuning. A common process is to distill indexing behavior from a full-attention model and then gradually increase sparsity. Keep a full-attention fallback during the transition, compare results on a controlled traffic slice, and increase traffic gradually.
Evaluation. Establish a three-level evaluation system:
- General long-context benchmarks;
- Business-specific evaluation sets;
- Layered task suites.
The layered suites should emphasize retrieval, aggregation across multiple passages, and long-chain reasoning, as these tasks often degrade fastest when indexing errors increase.
Diagnostics. In addition to standard quality metrics, track selection overlap—for example, the overlap between sparse selections and the high-attention-weight token set from full attention. When quality declines, this metric can help distinguish missed retrieval from problems in the model itself.
6. Engineering and Operations
Operators and Data Layout
LSA’s benefits depend on the combination of fused operators, low-precision computation, and compact data layout. Practical implementations should:
- Fuse coarse retrieval, fine ranking, gather, and attention computation where possible to reduce GPU-memory traffic;
- Store memory codes in low precision;
- Align block partitioning with hardware cache lines and computation granularity;
- Use profiling tools to validate efficiency at the operator level.
Memory and Cache Management
The KV cache and memory codes for 10M-token contexts must be included in a unified GPU-memory budget. Paged management and per-session reuse are useful for controlling memory pressure.
If prefix caching is available, repeated documents should cache both KV data and memory codes. Cache invalidation must remain consistent with the sparse-selection strategy. Otherwise, a cache hit may still produce incorrect or degraded retrieval.
Elastic Scaling
Prefill is compute-intensive, and the compute demand of a single request can grow quadratically with context length. Two deployment patterns are possible:
- Elastic container instances that scale according to request length;
- A dedicated long-context resource pool with separate scheduling for extremely long prefills.
Observability
Monitor and alert on:
- TTFT;
- TPOT;
- The indexer’s share of total runtime;
- The fitted quadratic coefficient of indexer latency;
- Cache hit rate;
- GPU-memory utilization.
The quadratic coefficient can be estimated by fitting runtime against (T^2) across multiple context lengths. A significant increase after a software release usually indicates an indexing regression.
Cloud Deployment
For long-context inference services, a cloud deployment can combine general-purpose capabilities such as:
- Elastic container instances for inference workloads;
- Object storage for long-document corpora and model artifacts;
- Log management, monitoring, and alerting for the metrics described above.
On Baidu AI Cloud, these capabilities can be combined for long-context inference services. The exact available regions and service options should be verified in the official documentation before deployment.
7. Conclusion: The Next Phase of Context Scaling
The focus of attention optimization has shifted over time:
- Full attention asked how to compute attention faster;
- Token-space sparse attention asked how to compute it over fewer tokens;
- Latent sparse attention asks how to find the tokens worth computing over—faster and more reliably.
LSA reduces the indexer’s constant factors by one or two orders of magnitude, helping move 10M-token contexts from impractical toward usable. Its value, however, does not come from copying a published speedup figure. The important task is to understand how indexing cost scales with (T^2), identify the bottleneck in the target workload, quantify end-to-end gains, and protect quality with production-specific evaluation.
At the 10M-token scale, the question is no longer simply how much text a model can process. It is how quickly and accurately the model can find the parts of that text worth processing.
