Why Sparse Attention Bottlenecks at the Indexer at 10M Tokens

    As context windows grow from 1M to 10M tokens, the hard part of sparse attention is no longer whether you can compute attention over a few tokens, but how you find them. This article breaks down the cost structure of sparse attention and shows why the indexer becomes the dominant bottleneck during prefill. It introduces Latent Sparse Attention (LSA), which compresses keys into a bounded number of latent vectors so that indexing can drop from quadratic to sub-quadratic or near-linear. Along the way it provides recomputable cost formulas, illustrative pseudocode, guidance on preserving accuracy, an interpretation of the reported 22.7x and 72.4x single-layer speedups, and an engineering checklist covering baseline profiling, TTFT monitoring, recall metrics, end-to-end load testing, and rollback strategies.

    Why Sparse Attention Bottlenecks at the Indexer at 10M Tokens

    Introduction: From 1M to 10M, the bottleneck shifts from “computing attention” to “finding tokens”

    As ultra-long context goes from a demo capability to a default one, 1M tokens is no longer remarkable, and 10M tokens has started to enter engineering discussions. Models now have to handle long documents, codebases, multi-turn conversations, and cross-file tasks, and can no longer assume that every query can read through the entire history. Sparse attention has become a common solution: each query selects only a handful of the most relevant tokens to compute attention over.

    But the longer the context, the more the real question stops being “can we compute over only a few tokens?” and becomes “how do we find those few?”

    According to a paper, at the 10M-token scale, in the prefill of a certain global attention layer, the indexer-related steps can account for about 98% of the time. Note: this figure comes from the paper’s report; the specific model, hardware, batch, sequence length, and measurement method should be verified against the paper’s appendix. This article does not treat it as a universal ratio across all implementations.

    Dimension ~1M tokens ~10M tokens
    Dominant cost Attention computation and KV-cache reads/writes Indexer candidate scoring and selection
    Optimization focus Reducing attention computation Reducing the cost of candidate scoring
    What determines accuracy Whether attention is sparse Whether the candidate set includes the truly important tokens

    Recent research proposes Latent Sparse Attention (LSA). Its core idea is: instead of doing quadratic indexing directly on the original key sequence, first compress the keys into a small number of latent vectors, let the query do a coarse filtering pass in the latent space, and then go back to the original tokens for exact attention. The paper reports that at the 10M-token scale, this approach can speed up the prefill of a certain global attention layer by 22.7x and 72.4x respectively; note that these are paper-reported single-layer prefill results and cannot be directly equated with end-to-end speedup.

    Quick answers: a few key questions

    • What is Latent Sparse Attention? It is a sparse-attention optimization method. Through learnable projections or pooling, it compresses a large number of keys into a controlled number of latent vectors; the query first compares against the latent vectors, and then computes exact attention only over the candidate tokens.
    • Why does sparse attention make the indexer a bottleneck? Because although sparse attention reduces the computation range of the formal attention, the indexer still has to evaluate all keys before selecting a few candidates. As context length grows, this step can exhibit quadratic or near-quadratic overhead.
    • How to choose between LSA and block sparse? Block sparse uses block summaries for coarse scoring, and its advantage is simplicity; LSA uses the latent space for a more controlled coarse filter, aiming to shrink the index comparison range. If a team wants to retain higher scoring precision and reduce missed candidates, it can evaluate LSA first; if engineering change cost is more sensitive, it can start with block sparse.
    • What are the common risks? The risks mainly include recall degradation at long contexts, shifts in key-information position, insufficient gains at very short contexts, memory access offsetting the speedup at small batches, and the inherent need of retrieval-type tasks for global aggregation.

    1. Cost breakdown: the “hidden bill” of sparse attention

    1.1 Full attention: quadratic cost is an explicit expense

    In standard full attention, every query computes relevance against all the keys before it. Let the context length be T; then the prefill computation is O(T²), and during decoding each generated token costs O(T).

    When the context grows from 1M to 10M tokens, the length becomes 10x, so the prefill attention computation becomes about 100x. Meanwhile, the memory footprint of the KV cache also inflates linearly to 10x. For large models, the long-context KV cache can become a major pressure point for both memory and bandwidth.

    So “reducing the computational complexity of attention” has long been the main thread of long-context research. Common approaches include:

    • Sparsification: limit the number of keys each query can see;
    • Linearization: replace softmax attention with feature maps or recurrent states to bring complexity down to linear;
    • Compression: quantize the KV cache, apply low-rank compression, or evict entries.

    Sparse attention is one of the faster approaches to land in production. It does not change the mathematical form of attention; it limits the computation range of each query.

    1.2 Sparse attention: attention gets cheap, the indexer is pushed to the front

    The basic division of labor in sparse attention is:

    1. First, a lightweight indexer selects the k most relevant keys for each query;
    2. Then, the actual attention is computed only over those k keys.

    The cost of attention itself is thus compressed to O(Tk). When k is fixed, this cost grows roughly linearly with T.

    This idea has one key premise: the model really does need only a few keys. Appendix-style validation from the paper shows that at a 128k-token length, if each query attends only to its 512 most relevant keys, the model can still retain accuracy close to full attention on standard long-context benchmarks.

    Here we need to correct a common estimate. 128k tokens equals 131072 tokens. If each query keeps only 512 keys, the ratio is:

    512 / 131072 ≈ 0.0039, i.e., about 0.4%

    not 0.8%. This shows that sparse attention itself is usually safe, and accuracy loss is more likely to come from “selecting the wrong keys” than from “selecting too few.”

    But to decide which 512 keys are most relevant, the indexer first has to score every key. So the indexer ends up back at a scale similar to full attention.

    1.3 Recalculating indexer overhead: formulas instead of guesswork

    To understand this “hidden bill” more precisely, here are recomputable formulas rather than one or two numbers in isolation.

    Let:

    • B be the batch size; for simplicity, take B = 1;
    • H be the number of attention heads, e.g., 32;
    • D be the dimension of each head, e.g., 128;
    • T be the sequence length, e.g., 10M;
    • k be the number of keys each query finally keeps, with k much smaller than T.

    For the main attention:

    • If it is non-causal full attention, each query interacts with all T keys. Considering the two steps Q·Kᵀ and score·V, the main attention multiply-add count is about:
      2 × H × D × T²
    • If it is causal attention, each query sees on average about T/2 historical keys, so the main attention multiply-add count is about:
      H × D × T²
    • If the batch size is B, multiply by B again.

    For the indexer:

    • If the indexer scores similarity between the query and each key in a d_dim-dimensional space, the indexer multiply-add count is about:
      d_dim × T²
    • If d_dim is close to D, or the indexer needs per-head scoring, multiple rounds of candidate filtering, within-block aggregation, and cross-block merging, then the indexer’s computation may be of the same order as the main attention, or even higher.
    • If it also involves top-k selection, sorting, candidate index gathering, sparse gather, memory-access synchronization, and other operations, the actual latency may be significantly higher than the pure multiply-add theoretical value.

    So “98% of the time is spent on the indexer” is more reasonably interpreted as: in a particular implementation, the indexer includes not only candidate scoring but also selection, memory access, and scheduling, causing it to dominate prefill wall-clock time. It should not be simply understood as a fixed rule across all models and all hardware.

    1.4 Why existing optimizations have limited effect

    To compress indexer overhead, the industry has proposed various methods:

    • Dynamic sparse schemes: learn a low-dimensional index vector for each query and retrieve in that low-dimensional space;
    • Multimodal or cross-modal auxiliary-signal schemes: estimate relevance with lightweight auxiliary information;
    • Mainstream block sparse: first aggregate keys by block, then score block by block.

    What these schemes have in common is “compressing the index information of each single key,” for example lowering scoring precision, shortening the index vector dimension, or merging several consecutive keys into one summary. They are all effective, and essentially they push down the constant term c in the formula:

    Indexer cost ≈ c · T²

    But in ultra-long contexts, what often decides success or failure is the T term, not c.

    • When T = 1M, T² = 10¹²;
    • When T = 10M, T² = 10¹⁴.

    Even if you reduce the constant term by an order of magnitude, further growth in length will quickly eat up the gains. This is also why optimizations like low precision, dimensionality reduction, and block summaries are useful but cannot fundamentally change the growth order.

    2. Latent Sparse Attention: making indexing no longer grow with T²

    2.1 Core idea: reduce the objects being compared, not just shrink each key

    The paper’s basic judgment is: the problem with the indexer is not that it “computes inefficiently,” but that it “computes too much.” So the optimization direction must shift from “compressing the index information of each key” to “reducing the number of objects the indexer needs to compare.”

    The key step of LSA is to let index scoring happen in a latent space far smaller than the original key sequence:

    • First, compress all keys into a bounded number of latent vectors;
    • The query only needs to compare against these latent vectors one by one to locate the few tokens that actually need attention.

    Let the number of latent vectors be M. The retrieval stage needs about T × M comparisons. Here we must strictly distinguish complexity:

    • If M is fixed or constant, the indexing retrieval cost is approximately O(T);
    • If M = √T, the indexing retrieval cost is about O(T^1.5);
    • If M grows linearly with T, the indexing retrieval cost may still approach quadratic.

    So a more accurate statement is: LSA, when the number of latent vectors is bounded, can reduce indexing from quadratic to sub-quadratic or near-linear. The key here is not “guaranteed linear,” but “letting M not grow unboundedly with T.”

    It should be emphasized that this does not conflict with linear attention. In the setting of 10M tokens with thousands of latent vectors, the indexer computation can be of a similar order to the main attention; adding the two together can still maintain a relatively low overall growth. LSA retains exact computation of softmax attention; it only hands the job of deciding “what to compute” to the cheaper latent-space retrieval.

    2.2 Three-stage process

    The LSA workflow can be divided into three stages.

    Stage 1: Compression. For the key sequence of each layer or every few layers, use a learnable projection or pooling to map them onto a group of bounded latent vectors. Each latent vector is a “summary” of a segment of keys. This step only needs to project each key once, the cost is linear, and it only needs to run once as the keys are produced.

    Stage 2: Retrieval. Each query computes similarity against all latent vectors, finds which latent vectors are most relevant, and then locates candidate tokens accordingly.

    • This step only performs T × M comparisons, where M is the number of latent vectors;
    • Since M is much smaller than T, this cost can be reduced from quadratic to bounded sub-quadratic;
    • In practice it usually needs to be computed in a streaming, chunked fashion to avoid materializing the full [T, M] score matrix.

    Stage 3: Exact computation. On the selected candidate keys, complete the computation with standard softmax attention. The number of keys here is usually only a few hundred to a few thousand, and the computation cost still grows linearly with context length, the same as sparse attention.

    Compared with common block sparse schemes, the most fundamental difference of LSA is:

    • Block sparse is “coarse-grained scoring, fine-grained computation”;
    • LSA is “small-space scoring, original-precision computation.”

    The former makes a trade-off on scoring granularity; the latter does not sacrifice scoring precision, but narrows the scope of scoring.

    2.3 Illustrative code

    The pseudocode below only expresses the computation flow, omitting engineering details such as kernel implementation, chunk scheduling, and length alignment:

    1. def lsa_prefill_layer(Q, K, V, W_proj, n_latent, block, k):
    2. """
    3. Latent Sparse Attention, single-layer prefill (illustrative flow, not a directly runnable implementation)
    4. Q, K, V : [B, H, T, D] query / key / value for this layer
    5. W_proj : [D, D] key compression projection matrix
    6. n_latent: number of latent vectors, should be fixed or bounded, not grow unboundedly with T
    7. block : length of the key interval each latent vector corresponds to (i.e., block size)
    8. k : number of keys each query finally keeps
    9. """
    10. # 1) Compress: map T keys to n_latent latent vectors
    11. K_lat = pool(proj(K, W_proj), pool_size=block) # [B, H, n_latent, D]
    12. # 2) Retrieve: query compares only against latent vectors, cost ~ O(T * n_latent * D)
    13. # In practice, compute in a chunked streaming fashion to avoid materializing the [B, H, T, n_latent] score matrix
    14. score = matmul(Q, transpose(K_lat)) / sqrt(D) # [B, H, T, n_latent]
    15. # 3) Select: take top-block to get candidate blocks, then concatenate into ~ k candidate keys
    16. top_blocks = topk(score, n_select) # [B, H, T, n_select]
    17. cand_idx = gather_range(top_blocks, block) # [B, H, T, k]
    18. # 4) Exact computation: compute softmax attention only on candidate keys, cost O(T * k * D)
    19. K_c, V_c = gather(K, cand_idx), gather(V, cand_idx)
    20. return sparse_softmax_attention(Q, K_c, V_c)

    2.4 Why accuracy can hold

    Latent-space retrieval brings a new problem: the tokens that get missed may be exactly the key tokens. For example, when many keys are highly similar, their shared summary “dilutes” each other’s scores. LSA usually controls this risk from several angles:

    • Learnable compression: the projection and pooling are trained together with the main model, not a heuristic rule bolted on afterward;
    • Headroom in the candidate set: the coarse-filter candidate size is usually slightly larger than the number of keys finally kept, leaving room for the fine filter to correct;
    • Per-layer independent selection: each query selects keys separately at each layer. The same piece of text plays different roles at different layers, and a single-layer miss can be compensated by other layers;
    • Keeping “anchors”: in practice, the current token, several recent tokens, and fixed starting tokens are often forced into the candidate set, ensuring local coherence and preserving empirical rules like “front information takes priority.”

    But it must be emphasized that the conclusion of “retaining accuracy close to the original model” cannot be simply extrapolated from 128k to 10M. The longer the context, the more semantics need to be covered, and the greater the recall pressure on latent-space retrieval. So accuracy evaluation should not look at the total score alone, but should add the following dimensions:

    • Length-stratified evaluation: separately observe recall at 128k, 1M, 4M, and 10M;
    • Key-information position: whether information sits at the beginning, middle, or end, and its impact on candidate selection;
    • Repeated-entity recall: when the same entity appears multiple times, whether it can be continuously recalled;
    • Multi-hop QA and codebase understanding: these tasks rely more on fine-grained localization;
    • Aggregation-type tasks: e.g., counting, summing, and global ranking, where insufficient local candidate sets should be watched for.

    In engineering practice, long-context recall rate should be monitored as an independent metric over the long term.

    2.5 Interpreting the results: how to understand 22.7x and 72.4x

    The reported speedup numbers have two details worth noting.

    First, the speedup multiple depends on how much time the indexer originally took. In the original implementation, if the indexer already accounts for 98% of prefill time, then by Amdahl’s law, even if the indexer completed instantly, the overall ceiling is only about 50x. To achieve an overall speedup of 22.7x, the indexing step needs to be tens of times faster again. The 72.4x appears on another baseline model, indicating that in that baseline the indexer’s share is higher, leaving more room for optimization.

    Here the scope needs to be made clear:

    • Both numbers come from the paper’s report;
    • The object is global attention layers in the models;
    • The scenario is single-layer results of 10M-token prefill;
    • 22.7x corresponds to a baseline with an indexer share of about 98%, and 72.4x corresponds to a baseline with a higher indexer share;
    • The original material does not provide verifiable model names, hardware models, batch, or test environment, so this article does not fabricate specific models, nor does it recommend that readers directly extrapolate to end-to-end or to other platforms.

    Second, pay attention to the “single attention layer” scope. A real model’s end-to-end prefill also includes:

    • FFN and feedforward networks;
    • local or linear attention layers in hybrid architectures;
    • communication and scheduling overhead;
    • memory bandwidth and kernel-launch overhead.

    These cannot be fully sped up by this optimization. So the end-to-end gain is usually lower than the single-layer numbers, but in long-context scenarios it can still be substantial. When selecting, it is recommended to first measure the per-layer time share on the target model, then estimate the overall gain accordingly.

    3. Engineering implementation: turning the sub-quadratic advantage into real performance

    3.1 Understanding the limits of theoretical speedup

    LSA removes the quadratic term in the indexing step. But even so, prefill still has some costs that may grow with T², just with smaller coefficients:

    • Positional encoding or relative bias: NoPE itself does not necessarily need a pairwise distance function, but some implementations with bias or relative-position effects may still compute distance-related terms for each query–key pair;
    • Structural repeated attention: if the model repeatedly attends to certain earlier segments, their importance may be amplified as the number of queries grows, and the candidate set needs to be enlarged accordingly;
    • Attention scores with bias: some implementations still need to compute scores pairwise, making it hard to rely entirely on standard matmul utilities.

    These costs may not be obvious at 1M length, but above 10M they may reappear. When evaluating LSA, they should be included in the overall budget rather than assuming “the quadratic has already disappeared.”

    3.2 Working with hybrid architectures

    LSA does not need to carry the whole model alone. Current mainstream ultra-long-context designs are often “hybrid”:

    • linear attention layers or local attention layers handle cheap global information aggregation;
    • a few global attention layers are responsible for exact retrieval, and LSA is exactly what makes these layers affordable.

    In a hybrid architecture, linear attention layers can handle coarse global filtering, and LSA does fine retrieval at the global layers. The two complement each other: the linear layers give rough relevance hints, the latent-space index gives precise top-k, and global information is not fragmented by local sliding windows.

    3.3 Training and adaptation

    • Staged context extension: like most long-context schemes, LSA is suited to first training the projection and pooling at medium-short lengths, then continuing pretraining with a small amount of long text, gradually pushing the window to the million- and ten-million-token scale;
    • Task calibration: synthetic “needle-in-a-haystack” data has limited value for the indexer; real tasks like multi-hop QA, long-document summarization, and codebase-level understanding should be used more to calibrate;
    • Low-level implementation: the indexing operators are often memory-access-intensive with low arithmetic intensity, and require fusing computation with selection and pipelining as much as possible, to turn “computing less” into “running faster.”

    3.4 Launch checklist: do not decide based on single-layer speedup alone

    Before going live, it is recommended to verify item by item against this checklist:

    1. Measure the baseline first
      Do prefill profiling on the target model to confirm where time actually goes — attention, FFN, the indexer, or communication. If the indexer’s share is not high, LSA’s gains may be limited.

    2. Quantify the indexer’s share
      Separately record indexer latency across different lengths, batches, and concurrency levels. Cover at least three gradients: 1M, 4M, and 10M.

    3. Monitor TTFT
      Time-to-first-token latency is critical in long-context scenarios. LSA’s gains usually show up directly in TTFT, but also observe whether it stays stable under high concurrency.

    4. Build recall metrics
      Do not look only at benchmark scores. Break down dimensions like length, position, entity repetition, and multi-hop QA, and observe whether the candidate set can cover key information.

    5. Do end-to-end load testing
      Load-test with real long-text traffic, not just a single kernel. Observe peak throughput, tail latency, GPU utilization, and memory usage.

    6. Prepare a rollback strategy
      Provide a switch: when LSA behaves abnormally or recall is insufficient, fall back to block sparse, full attention, or a hybrid architecture. Rehearse the rollback process before going live.

    3.5 Risks and boundaries

    LSA is not a master key:

    • The ceiling of retrieval-type tasks: if a task requires checking every detail one by one, or needs global aggregation — e.g., counting the occurrences of each word across the whole text — any method that “only looks at part of it” carries risk. Such scenarios are better served with a global aggregation signal, or by keeping a few full-attention layers;
    • No gain at very short contexts: when T is small, the indexer’s share is very low, and the extra compression and retrieval overhead may even slow things down end-to-end, so strategies should be set by length range;
    • Limited in small-batch scenarios: prefill speedup comes from fewer arithmetic operations; when the batch is small and the GPU’s compute is underutilized, memory-access and launch overhead may offset part of the gains;
    • Coordination with the decoding stage: long-context decoding is likewise troubled by the indexer. If the LSA scheme also covers decoding, the impact of the KV-cache layout on memory usage and bandwidth needs to be evaluated.

    4. Summary

    As context moves from millions to tens of millions of tokens, the bottleneck of attention has shifted from “computing too much” to “finding too expensively.” Sparse attention has proven that models usually need only a few tokens, but the indexer may still need to score or compare all tokens, so the quadratic cost is retained. Existing means like low precision, dimensionality reduction, and block summaries can push down the constant term, but cannot by themselves change the growth order.

    The breakthrough of Latent Sparse Attention is that it indexes in a different dimension: it compresses all keys into a bounded number of latent vectors, lets the query do coarse filtering in the latent space, and then computes exactly on the original keys. When the number of latent vectors is bounded, the indexing cost can drop from quadratic to sub-quadratic or near-linear. The paper reports that at 10M tokens it can speed up the prefill of two baselines’ global attention layers by 22.7x and 72.4x respectively; but this is paper-reported single-layer prefill data and cannot be directly equated with end-to-end gains.

    For engineering teams, this means “supporting longer contexts” is no longer just “stacking more GPUs.” When context becomes part of the product capability, it is worth re-examining the model from the cost structure: first measure clearly where the time goes, then decide what to optimize. The indexer is exactly that hidden bill most worth prioritizing for examination in the era of ultra-long contexts.