Sparse Attention Indexers at 10M Tokens: A Cost-Reduction Guide

    As context windows scale from millions to tens of millions of tokens, sparse attention remains a key route for long-context models. But at the 10M-token scale, the real bottleneck is often no longer the attention computation itself—it is the indexer that decides which tokens to look at. This guide breaks down the cost structure, explains why a naive indexer quietly reintroduces quadratic cost, and lays out actionable optimization paths, from lower-precision scoring and low-rank projection to latent-space structured retrieval using buckets, clustering, or hierarchical indexes. It also covers how to measure indexer overhead, validate the sparsity assumption, tune k and r, and evaluate recall so you can pick the smallest configuration that keeps accuracy while cutting cost.

    Introduction: Why does the indexer slow down at 10M tokens?

    As context windows grow from millions to tens of millions of tokens, sparse attention remains an important route for long-context models. When evaluating options, teams tend to circle back to three questions: Why does the sparse attention indexer slow down? How do you choose a low-dimensional latent-space index? What are the common mistakes?

    Historically, attention has been about the attention matrix multiplication itself: the longer the context, the more expensive it becomes to compute the correlation between Q and K. But as the context moves from 1M toward 10M, the problem gradually shifts. Sparse attention does not require every query to scan all historical tokens; instead, a lightweight indexer first selects a small number of relevant keys, and only then does the real attention computation run on them. At the million-token scale, this route has been validated repeatedly: as long as the number of retained keys is reasonable, model accuracy generally does not collapse noticeably.

    However, as the context keeps growing to the ten-million scale, what actually runs out of control is often not the attention itself, but the indexer that decides “which tokens to look at.” After sparse attention pushes the attention computation below quadratic cost, the indexer can quietly pile the quadratic cost right back on. This article focuses on that point: it breaks down the cost structure, offers an actionable optimization path, and adds guidance on selection and stress testing.

    1. Where does the attention cost actually go?

    Let’s first review the cost structure of standard full attention. Let the context length be T and the head dimension be d. Every query then needs to compute correlation with all preceding keys:

    1. def full_attention(Q, K, V):
    2. # Q, K, V all have shape [T, d]
    3. scores = Q @ K.T / sqrt(d) # [T, T], cost O(T^2 * d)
    4. attn = softmax(scores, axis=-1)
    5. return attn @ V # O(T^2 * d)

    In the prefill stage, when the entire input is processed at once, the attention computation is roughly O(T²). In the decode stage, each generated token typically faces roughly O(T) historical dependency. As the context grows from 1M to 10M, looking at the attention term alone, prefill computation can scale up by around 100x; at the same time, the KV Cache also grows linearly with length, and memory and bandwidth pressure rise together.

    The premise of sparse attention is direct: if the model does not need to look at every historical token, there is no reason to pay for a full pairwise comparison.

    2. Sparse attention: from full scan to selective viewing

    The basic form of sparse attention is “select first, then compute.” A lightweight indexer first picks the k most relevant keys for each query, and the real attention runs only on those k keys:

    1. def sparse_attention(Q, K, V, k):
    2. # Step 1: the indexer selects the top-k relevant keys
    3. idx = indexer(Q, K, topk=k)
    4. # Step 2: run attention only on the selected k keys
    5. K_sel = gather(K, idx) # [T, k, d]
    6. V_sel = gather(V, idx) # [T, k, d]
    7. scores = einsum('td,tkd->tk', Q, K_sel) / sqrt(d)
    8. attn = softmax(scores, axis=-1)
    9. return einsum('tk,tkd->td', attn, V_sel)

    The cost of the second step is roughly O(T × k × d). As long as k is much smaller than T, this part is usually acceptable. Related long-context research has repeatedly shown that, in many tasks, letting each query look at only a few of the most relevant keys still preserves accuracy close to full attention on long-context benchmarks. Sparse attention therefore already delivers strong engineering value at the million-token scale.

    But the problem lies precisely here: if the indexer itself is expensive, the attention computation that sparse attention saves can be eaten right back up by the indexing overhead.

    3. The paradox: the indexer becomes the hidden bill

    The naive approach to indexing is to score every query against all candidate keys:

    1. def indexer(Q, K, topk):
    2. score = Q @ K.T # [T, T], inherently quadratic
    3. return topk_indices(score, k=topk)

    This step still has a complexity close to O(T²); only the matrix dimensions at each step may be lower than in full attention. A typical paradox emerges: sparse attention reduces attention computation from O(T²) to O(Tk), yet piles the cost right back onto the indexer’s scoring stage. The longer the context and the more candidate keys there are, the heavier the indexer becomes.

    In public material or internal stress tests, a common conditional observation is this: in a model that supports million-token context, if a certain global attention layer processes 10M tokens during prefill, and the indexer shares fixed hardware, a fixed inference framework, and a fixed k value with the attention, indexer scoring can take up a fairly high proportion of the runtime—sometimes reaching the point where “the vast majority of time is spent selecting tokens.” It is important to note that this proportion depends heavily on model structure, layer count, context length, hardware, parallelism strategy, the value of k, and whether index results are cached. Without a clear measurement basis, it should not be extrapolated into a universal conclusion for all models.

    A more accurate statement is this: sparse attention does not eliminate the quadratic cost; it migrates the quadratic cost from “computing attention” to “selecting tokens.” At the ten-million-token scale, what usually needs optimizing is not the attention kernel itself, but the indexer’s selection mechanism.

    4. The classic cost-reduction route: lower the unit price or the total volume of scoring

    The industry has already evolved several ways to lighten the indexer’s load. Their goal is usually not to rebuild the selection paradigm, but first to reduce the cost of “scoring every key.”

    1. Lower the scoring precision

    The indexer only needs relative ranking, so it is not very sensitive to numerical precision. Computing index scores in lower-precision formats such as int8 or FP8 reduces bandwidth and compute pressure. This approach is relatively easy to implement, but you must verify whether lower precision changes the top-k boundary, especially when candidate scores are very close together.

    2. Compress the scoring dimension

    Projecting the Q and K used for scoring into a lower-dimensional space before comparing them is a common idea. The real attention can still use the high-dimensional representation, while the indexing stage uses only the low-dimensional projection. This lowers the cost of a single dot product, but it is still fundamentally scoring every candidate key.

    3. Key compression and block sparsity

    Pooling and compressing several adjacent keys into one block lets you coarsely filter at block granularity first, then look closely within the matched blocks. For example, compressing every 4, 8, or 16 keys into one block can significantly reduce the number of coarse-filter entries. Block sparsity has good engineering feasibility, but block size directly affects recall: too large a block gives insufficient filtering granularity; too small a block limits the compression gains.

    Here is a rough comparison:

    Route Complexity change Accuracy risk Typical scenario
    Full attention O(T²d), baseline cost No sparsity loss, but highest cost Short context or accuracy-first
    Naive sparse attention Attention drops to O(Tkd), indexer still O(T²) Indexer may become the new bottleneck Initial optimization at million-token context
    Low-precision index Lowers constant factor and bandwidth pressure Boundary tokens may be picked wrong When index ranking is insensitive to precision
    Low-rank projection Scoring becomes O(T²r), only lowers constant Insufficient low-dim info causes missed selections As preprocessing for structured retrieval
    Key compression / block sparsity Fewer coarse-filter entries, lower constant Overly coarse blocks lose recall Engineering scenarios that tolerate approximate recall
    Latent-space structured retrieval Near sub-quadratic when candidate scale is bounded Clustering, bucketing, or approximate retrieval may miss results The key optimization direction at ten-million-token context

    These classic methods still do not escape the framework of “each query compared pairwise against every candidate.” As long as the candidate set grows linearly with T, the total amount of scoring can still approach quadratic—only the constant gets pushed down. To achieve a qualitative change at the ten-million-token level, you need to rebuild “selection” itself into a retrieval problem with a controllable candidate scale.

    5. Low-dimensional latent space: lower the constant first, then move toward sub-quadratic

    Moving the indexing process into a low-dimensional latent space is a promising direction today. Its basic form is as follows:

    1. def latent_indexer(Q, K, topk):
    2. # Project Q and K into a low-dimensional latent space
    3. Q_lat = Q @ Wq # [T, r], r << d
    4. K_lat = K @ Wk # [T, r]
    5. score = Q_lat @ K_lat.T # [T, T]
    6. return topk_indices(score, k=topk)

    It must be emphasized here: low-dimensional projection by itself does not automatically deliver sub-quadratic complexity. The code above still scores every key, and its complexity is still O(T² × r)—only the constant is lower than at the original dimension d. If r is clearly smaller than d, a single scoring pass is cheaper; but as long as the candidate set is still all T keys, the total volume still grows quadratically with T.

    So low-dimensional projection is only the first step. The real key to approaching sub-quadratic complexity is making the latent-space representation “retrievable.” For example, build buckets, cluster centers, or a hierarchical index in the latent space, so that each query first locates a few candidate buckets, then does precise scoring only within those few candidates. This can be written as:

    1. def structured_latent_indexer(Q, K, k, B, C):
    2. # Q, K: [T, d]
    3. Q_lat = Q @ Wq
    4. K_lat = K @ Wk
    5. # Build bucket centers offline or incrementally; B is the number of buckets
    6. centers = build_buckets(K_lat, num_buckets=B)
    7. # Each query selects only a few candidate buckets
    8. selected_buckets = query_centers(Q_lat, centers, B)
    9. # Collect candidate keys from the selected buckets; C caps candidates per bucket
    10. candidates = gather_bucket_candidates(K_lat, selected_buckets, max_per_bucket=C)
    11. # Score only within the candidate set in the low-dimensional space
    12. scores = Q_lat @ candidates.K_lat.T
    13. # Return the global top-k
    14. return map_to_global(topk_indices(scores, k=k), candidates)

    In this structure, each query selects B candidate buckets, with an upper bound of C candidates per bucket and latent dimension r. If the candidate scale M ≈ B × C and M is far smaller than T, then scoring cost can drop from O(T² × r) to close to O(T × M × r), plus the cost of building bucket centers and querying bucket centers. When the bucket structure is well built and candidate recall is sufficient, the overall complexity can approach sub-quadratic, and in some engineering implementations even approach linear candidate scanning.

    The key here is recall. Recall can be defined as: of the keys that should genuinely enter the top-k, how many are covered by the candidate set. Common metrics include Recall@Candidate, Recall@k, and MRR. If latent-space retrieval misses the truly relevant keys, no amount of subsequent attention precision can make up for the error.

    6. Effects and costs: always condition the speedup

    In public research, methods that compress the indexing process into a low-dimensional latent space can deliver significant speedup in single-layer prefill scenarios at the ten-million-token scale relative to native sparse attention; some sources report gains on the order of tens of times. But such numbers must be understood conditionally and cannot be directly extrapolated to arbitrary models.

    At a minimum, you should specify the following measurement basis:

    • Model and layer count: Is it a single global attention layer, or a multi-layer hybrid attention setup?
    • Context length: Is it 1M, 4M, or 10M?
    • Hardware and framework: What are the GPU model, memory bandwidth, inference framework, and parallelism strategy?
    • What is the baseline: Naive sparse attention, or an already-optimized block-sparse approach?
    • Key parameters: What are k, r, block size, number of candidate buckets B, and candidates per bucket C?
    • Is the index pre-built: Are bucket centers built offline, or built in real time for each request?
    • Evaluation task: Is it RULER, LongBench, Needle-in-a-Haystack, or a custom business task?
    • Accuracy metric: Are you looking at accuracy, recall, MRR, or downstream task scores?

    Without these specifics, a claimed “tens-of-times speedup” can only be treated as a reference under particular experimental conditions, not as a general promise.

    At the same time, watch out for three kinds of cost:

    1. The projection matrices Wq and Wk introduce extra parameters and training/adaptation costs.
    2. If latent-space approximate retrieval introduces clustering, hashing, or bucket retrieval, it creates recall problems.
    3. k and r need joint tuning: too small a k may hurt accuracy, while too large a k weakens the sparsity gains; too small an r causes selection distortion, while too large an r limits the cost-reduction effect.

    A simplified parameter risk table is as follows:

    Parameter Role Main risk Empirical direction
    k Number of keys finally retained per query Too small hurts accuracy, too large reduces gains Start stress testing at 512, 1024
    r Latent-space scoring dimension Too small misses selections, too large keeps the constant high Try 16, 32, 64, 128
    Block size Granularity of key compression or coarse filtering Too large hurts recall, too small limits gains Commonly 4, 8, 16
    Number of buckets B Candidate bucket scale and retrieval granularity Too many buckets are expensive to build, too few are too coarse Tune against T and recall
    Candidates per bucket C Controls candidate set size Too small loses recall, too large loses the cost reduction Treat recall as the primary constraint
    Recall threshold Validates approximate retrieval quality Insufficient recall degrades accuracy Start with a target of 0.95 or 0.99

    7. Engineering practice: how to choose and stress test

    If you are making architecture choices for ultra-long-context scenarios, you can proceed along the following path.

    1. First quantify the indexer’s share of the overhead

    Do not assume the bottleneck is attention from the start. First measure the following separately at the target length:

    • Attention computation time;
    • Indexer scoring time;
    • top-k selection time;
    • KV Cache read and transfer time;
    • End-to-end prefill and decode latency;
    • P50, P95, and P99 tail latency.

    Only when the indexer truly accounts for the majority of the time does optimizing it yield a clear payoff.

    2. Verify that the sparsity premise holds

    The premise of sparse attention is that the model genuinely needs only a few keys. This premise does not hold for every workload. Verify it on your own business data and long-context benchmarks:

    • Whether looking at only the top-k causes a noticeable drop;
    • Which tasks are most sensitive to k;
    • Which tasks can tolerate more aggressive block compression;
    • Whether low-precision indexing changes the ranking of key tokens.

    If the sparsity premise does not hold, no matter how fast the indexer is, it cannot rescue accuracy.

    3. Coarse filtering plus close inspection in stages

    A cost-effective combination in engineering is usually:

    • First use low-rank projection or block compression for coarse filtering;
    • Then run precise attention within the candidate blocks;
    • If necessary, layer on bucket retrieval or hierarchical retrieval.

    This staged approach controls recall more easily than compressing all candidates into a low-dimensional space at once, and it also makes problems easier to localize.

    4. Build a recall evaluation, not just watch latency

    The biggest risk of approximate indexing is missed detection. It is advisable to include the following metrics in your evaluation:

    • Recall@Candidate: the proportion of the candidate set that covers the true top-k;
    • Recall@k: the proportion of truly relevant keys among the finally retained keys;
    • Miss rate;
    • Accuracy decay magnitude;
    • Recall on tail requests;
    • Recall curves under different k, r, B, and C values.

    A minimal stress-test procedure could be:

    1. Fix the input length and data distribution;
    2. Run the native sparse attention baseline;
    3. Add low-rank projection and confirm it only lowers the constant;
    4. Add block compression or bucket retrieval and measure the change in candidate scale;
    5. Sweep k, r, block size, number of buckets B, and candidates per bucket C;
    6. Record latency, memory, bandwidth, recall, and task accuracy simultaneously;
    7. Choose the smallest configuration that meets the recall threshold.

    5. Watch memory, bandwidth, and the tail

    This kind of capability is very sensitive to memory and bandwidth. Beyond average latency, also watch:

    • Whether the indexer consumes extra memory;
    • Whether building bucket centers requires large amounts of cache;
    • Whether candidate set gather causes bandwidth jitter;
    • Whether long-context requests trigger tail latency;
    • Whether cloud platform deployment needs object storage, monitoring alerts, and elastic compute to work together.

    8. FAQ: quick answers to common questions

    What is a sparse attention indexer?

    A sparse attention indexer finds the few most relevant keys for each query, so that subsequent attention computes only on that subset. It decides “where to look” for sparse attention.

    Why does the indexer slow down at ten million tokens?

    Because a naive indexer scores every query against all candidate keys, the number of candidates grows with context length, the amount of scoring rises accordingly, and a near-quadratic cost forms.

    Can low-rank projection achieve sub-quadratic directly?

    No. Low-rank projection only reduces the scoring complexity from O(T²d) to O(T²r); it still scores every candidate. To achieve sub-quadratic complexity, you additionally need block partitioning, clustering, bucket retrieval, or hierarchical retrieval as structured candidate selection.

    How do you evaluate recall?

    You can define Recall@Candidate: the proportion of the candidate set that contains the true top-k; or Recall@k: the proportion of truly relevant keys among the finally retained keys. It is advisable to observe recall stability across different lengths and tasks simultaneously.

    How do you choose k and r?

    It is advisable to start stress testing within a small range, for example k starting at 512 or 1024 and r starting at 16, 32, or 64, then observe the accuracy and latency curves. Do not look only at the average gain—also look at recall, memory, and tail latency.

    9. Checklist of common mistakes

    1. Only reducing dimensions without doing structured retrieval, wrongly assuming low-rank projection is sub-quadratic.
    2. Only optimizing the indexer without validating the sparsity premise, causing accuracy to drop first.
    3. Only looking at average latency, not P95 and P99 tail latency.
    4. Only looking at the speedup ratio, without evaluating recall and miss rate.
    5. Setting k too large, so the sparsity gains are entirely eaten up.
    6. Setting block size or number of buckets unreasonably, so the candidate set is too large or too many results are missed.
    7. Directly extrapolating speedup numbers from public research while ignoring differences in model, hardware, length, and baseline.
    8. Ignoring index construction cost and optimizing only the query stage.
    9. Not building a recall evaluation, which makes accuracy problems hard to localize after launch.

    Conclusion

    From full attention to sparse attention, the industry has already solved the problem of “looking at too much.” The new challenge posed by ten-million-token context is “how to cheaply find the small part worth looking at.” When the indexer replaces attention as the main bottleneck, the focus of optimization must shift from reducing attention computation to rebuilding the selection process.

    The low-dimensional latent space is a promising direction, but it is not a magic switch. Low-rank projection can only lower the constant; to truly approach sub-quadratic complexity, it must be combined with block partitioning, clustering, bucket retrieval, or hierarchical retrieval, and recall must be treated as a first-class metric. For engineering teams, understanding exactly which step the cost falls on matters more than chasing a particular speedup number. That is the first-principles approach to coping with ultra-long context.