Indexer Bottlenecks in 10M-Token Sparse Attention and Latent-Space Optimization

    Sparse attention works at million-token scale, but at tens of millions of tokens the indexer—not the attention kernel—often dominates prefills. This article explains the cost model, why classic indexer tricks stay quadratic, and how latent-space routing plus rerank can make candidate search sub-quadratic while protecting recall.

    1. Background: as context grows, the bottleneck moves

    Long-context capability is moving from “million-token usable” toward “10-million-token usable.” At million-token scale, sparse attention is well validated: each query does not need every past key, only a small set of relevant ones, and retrieval, summarization, and multi-hop QA can stay close to full attention. A common split of labor emerged: a lightweight indexer picks candidate keys per query, then true attention aggregates over that set.

    That split works at million-token length because quadratic attention is still the main cost. At 10 million tokens the cost structure changes. Let context length be (T). Full-attention prefill is (O(T^2)); decoding one token is (O(T)). From 1M to 10M, prefill attention theoretically grows about 100×. Sparse attention compresses attention to (O(Tk)), where (k) is the number of keys kept per query—so attention itself looks solved.

    The real issue is the indexer. To know which keys matter, it usually scores a large set of keys first. Even with lower precision, fewer dimensions, block pooling, or compression, each query may still scan all keys or all blocks. Indexing remains (O(T^2))-class, only with a smaller constant. At 10M tokens, the index stage of a single-layer prefill can dominate runtime; attention becomes secondary. Optimization must shift from “compute attention faster” to “find which tokens to look at faster.”

    2. Cost model: sparse attention’s hidden bill

    Single-layer sparse attention cost splits as:

    [
    C{\text{total}} = C{\text{index}} + C_{\text{attn}}
    ]

    (C{\text{attn}}) is about (O(Tkd)). With (k \ll T), attention looks linear. (C{\text{index}}) depends on the indexer. If every query scores all keys:

    [
    C_{\text{index}} = O(T^2 d_i)
    ]

    where (d_i) is indexer dimension. Shrinking (d_i) only cuts the constant, not the quadratic trend. Block-sparse designs score blocks instead of keys, yielding (O(T^2 / B \cdot d_i)) for block size (B). That shifts the curve down without changing its shape.

    A common misconception: sparse attention is not automatically sub-quadratic. End-to-end prefill is linear or (O(T \log T)) only if finding candidates is itself sub-quadratic. Otherwise the indexer is the new bottleneck—and it is harder to optimize because it is limited by memory bandwidth, recall, batch parallelism, and cache reuse.

    Indexer overhead typically includes:

    1. Key representation: project, quantize, or pool all keys; lots of intermediate I/O.
    2. Relevance scoring: query–candidate similarity; full-key candidates stay quadratic.
    3. Filter and rank: top-k, thresholds, dedup, and rerank add memory traffic.
    4. Index maintenance: incremental decode needs dynamic updates; cache coherence affects latency.
    5. Accuracy compensation: a lighter indexer misses more, so larger candidate sets or hybrid fallbacks raise cost again.

    At 10M tokens the core challenge is not “attention cannot run,” but “the indexer cannot scan.”

    3. Ceiling of traditional optimizations

    Existing sparse-attention systems usually cut index cost via:

    • Low-dimensional projection: approximate scoring in a smaller space.
    • Quantization / low precision: higher throughput, lower bandwidth.
    • Block aggregation: compress consecutive keys, pick blocks then keys.
    • Local windows plus global tokens: keep a recent window and a few globals.
    • Multi-stage filters: coarse prune, then precise score in a small region.

    These help in production, but share a ceiling: the coarse stage must still cover a large range or recall (and accuracy) collapses. To keep quality, systems enlarge candidates, add rerank stages, or keep more global tokens—and give back some of the gains.

    Indexer and attention objectives also diverge. The indexer is trained for approximate relevance; attention needs keys that actually help the downstream task. Without joint calibration, you get wasted candidates the indexer likes but attention cannot use. Longer context amplifies that error.

    4. Core idea: latent-space sparse attention

    A newer approach: stop scoring every key in the original high-dimensional space. Map keys and queries into a low-dimensional, navigable latent space, build a reusable index there, retrieve candidates via hierarchical routing or ANN, then return to original space for precise rerank and sparse attention.

    Call this latent-space sparse attention. The point is not mere dimensionality reduction, but three independently tunable stages:

    1. Latent representations: learn key and query projections so latent distances approximate original attention relevance. Projections can be light networks, calibrated by distillation or contrastive learning.
    2. Navigable index: chunk, cluster, invert, or hierarchically organize keys so a query visits a few buckets or leaves, not all keys. Build in batch at prefill; update incrementally at decode.
    3. Rerank and exact sparse attention: latent retrieval returns a set slightly larger than (k); original Q/K scores pick the final (k) keys for sparse attention.

    This turns “every query scores all keys” into “route to a small candidate set, then compare precisely.” Index cost drops from (O(T^2)) toward about (O(T \log T + Tk’)), with candidate size (k’). If (k’ \ll T), prefill can enter a sub-quadratic regime.

    Latent retrieval need not match exact full top-k. It needs high recall: important keys should enter the candidate set; rerank can drop noise. Treat recall as a first-class metric, not only index latency.

    5. Complexity and engineering structure

    Per layer: (T) queries and (T) keys, latent dim (d_l), keep (k) keys, candidates (k’), with (k < k’ \ll T). A typical breakdown:

    • Index build: (O(T \cdot c{\text{build}})); (c{\text{build}}) depends on chunk size and cluster depth; chunked builds can be (O(T \log T)) or (O(T)).
    • Query routing: (O(\log T)) nodes per query, total (O(T \log T)).
    • Candidate rerank: exact scores on (k’) keys, (O(T k’ d)).
    • Sparse attention: aggregate over (k) keys, (O(T k d)).

    Versus full indexing (O(T^2 d_i)), the index stage no longer grows quadratically in (T). The index should be:

    1. Reusable: share one key index across queries.
    2. Chunkable: build and cache by blocks for peak memory and pipelining.
    3. Incremental: on new decode keys, update only affected chunks or leaves.
    4. Observable: log recall, bucket visits, rerank hits, and fallback rate.

    Library-agnostic sketch:

    1. function latent_space_sparse_prefill(Q, K, V, projector, index, k, k_prime):
    2. # Q: [T, d], K: [T, d], V: [T, d]
    3. # 1. Build or reuse a latent index over keys
    4. latent_keys = projector.project_keys(K)
    5. index.build_or_update(latent_keys)
    6. # 2. Batch-route queries to candidates
    7. latent_queries = projector.project_queries(Q)
    8. candidates = index.search(latent_queries, k_prime) # shape [T, k_prime]
    9. # 3. Exact rerank in original space
    10. scores = Q × K[candidates]^T
    11. selected = top_k(scores, k)
    12. # 4. Sparse attention only on selected keys
    13. weights = softmax(scores[selected])
    14. output = weights × V[candidates[selected]]
    15. return output

    Boundaries: the index only narrows the set; rerank uses original-space scores to limit approximation error; attention stays on (k) keys. Tune (k’/k), chunk size, and index depth jointly for accuracy and memory.

    6. Accuracy: recall beats single-point latency

    Latent indexes introduce error, so guard quality:

    • Recall monitoring: vs exact full top-k, measure how often true important keys land in the candidate set. If recall is low, enlarge candidates or rerank first—not blindly “more precise” indexing.
    • Indexer calibration: distill from attention scores or task loss so latent distances track true relevance. Train and serve the same projection and routing.
    • Candidate slack: keep (k’ > k) as a buffer; crop with original-space scores.
    • Hybrid fallback: for multi-hop aggregation, global stats, or cross-span citations, raise (k’), use local full attention, or exact block scans.
    • Layered eval: not one long-context task. Cover exact retrieval, paragraph aggregation, multi-hop reasoning, repo-scale code, long-dialog state—and watch scaling curves.

    Do not rely only on average accuracy. Ultra-long errors concentrate on a few critical keys; averages hide tail failures. Track recall, task accuracy, time-to-first-token, end-to-end throughput, and peak memory, with fallback thresholds by length band.

    7. Deployment checklist

    On a public cloud or private cluster:

    1. End-to-end latency breakdown: key construction, routing, rerank, sparse attention, output aggregation—confirm the indexer is the bottleneck.
    2. Length scaling curves: measure at ~1M, several million, and 10M; see if index cost is still quadratic.
    3. Tune on recall: latent dim, chunk size, index depth, (k’); plot recall–latency–memory.
    4. Cache the index: batch-build at prefill, incremental update at decode; reuse for stable documents; invalidate fast-changing content.
    5. Keep an exact fallback: if recall is below threshold or the task is a poor fit, fall back to exact block scan or local full attention.
    6. Train–serve consistency: same projector, routing, and rerank online and offline.
    7. Observability: candidate hit rate, hot buckets, fallback share, long-tail request mix.

    8. Scope and conclusion

    Latent-space sparse attention is not a universal fix for every long-context job. When a task truly needs few relevant keys, it can bring 10M-token prefill into a practical range. When it needs global aggregation, cross-span multi-hop, or is highly sensitive to tail keys, keep hybrid fallbacks and conservative candidates. Index build, update, and cache add engineering cost; do not judge only single-layer speedup.

    The direction is clear: the next competition in sparse attention is not only how fast the attention kernel is, but whether the indexer can find the right tokens sub-quadratically. Moving indexing into a navigable latent space, with hierarchical routing and candidate rerank instead of full scoring, is one of the paths that can make 10M-token context usable. Constrain on recall, optimize end-to-end latency, use mixed fallback as a safety bound, and build a verifiable, observable, scalable ultra-long-context attention stack.