Latent-Space Sparse Attention for Ten-Million-Token Contexts

    As context windows grow from millions to tens of millions of tokens, the main challenge shifts from computing attention scores to locating the small portions of history that each query actually needs. Latent-space sparse attention separates retrieval from full attention: compressed representations perform inexpensive candidate retrieval, while the original key-value representations are used only for final refinement and attention. This article explains the cost structure, indexing design, training strategy, memory constraints, and evaluation practices required to make this approach practical at extreme context lengths.

    When context windows grow from millions to tens of millions of tokens, the main bottleneck in attention changes. The problem is no longer only whether query-key dot products are affordable. It is whether the system can find the small portion of history that matters without scanning the entire context.

    Sparse attention has repeatedly shown that a query often depends on only a small subset of keys, while maintaining reasonable accuracy. However, if the indexer still scores every historical token one by one, retrieval itself becomes increasingly expensive. At extreme context lengths, prefill time can be dominated by selecting tokens rather than by performing the final attention computation.

    Why Full Attention Becomes Expensive First

    For a sequence of length (T), standard self-attention forms pairwise relationships between queries and keys during prefill, causing computation to grow quadratically with (T). During decoding, each new token must scan the existing key-value cache, so the cost grows linearly with the history length.

    Increasing the context length by a factor of ten can increase prefill attention computation by roughly a factor of one hundred. Activation memory and key-value cache usage also grow sharply. As a result, allowing every query to inspect the entire history is already expensive at million-token lengths and is usually impractical at tens of millions of tokens.

    Sparse attention divides the work into two stages:

    1. A relatively lightweight indexer selects the (k) keys most relevant to each query.
    2. Full attention is computed only at those (k) positions.

    The attention computation itself therefore becomes roughly proportional to (T \times k), provided that each query truly needs only a small number of keys. Ablation studies on contexts ranging from hundreds of thousands to millions of tokens commonly show that long-range retrieval and multi-hop tracking can retain much of their accuracy when (k) represents only a small fraction of the history.

    This demonstrates that “looking at less” can work statistically. It does not, however, mean that finding those few relevant positions is inexpensive.

    Why the Indexer Becomes the New Dominant Cost

    To identify the most relevant (k) keys, the indexer must, in principle, assign a score to every historical key. Common optimization techniques include:

    • Using lower numerical precision for index scoring
    • Projecting keys into a lower-dimensional space
    • Pooling adjacent keys into block representatives and performing block-level sparse retrieval

    These techniques reduce constant factors, but the number of scored items still grows with the history length. The overall process therefore retains a substantial quadratic or “lightweight quadratic” component.

    At tens of millions of tokens, the length of the context can overwhelm those constant-factor improvements. In a global attention layer, memory reads and writes, candidate ranking, and scattered accesses may cost more than the final dense attention over the small selected set.

    The nature of the problem therefore changes. Accuracy experiments have already shown that attention can be sparse. The systems bottleneck is that the selection process has not yet become genuinely subquadratic.

    Latent-Space Sparsity: Separating Retrieval from Computation

    Latent-space sparse attention performs selection on compressed representations rather than calculating full-dimensional scores for every historical key. It can be viewed as a two-stage retrieval system.

    1. Coarse Retrieval

    Keys are mapped to low-dimensional latent vectors, or neighboring keys are grouped into a small number of prototypes. Queries are projected into the same latent space and compared with far fewer latent units than the total number of tokens. This produces a small set of candidate blocks or candidate tokens.

    The number of comparisons is no longer tied to full-dimensional scoring across the entire context.

    2. Refinement and Attention

    Higher-precision keys are restored only for the retrieved candidates. The system then performs top-(k) selection or within-block filtering before applying standard attention.

    The work in this stage depends on the candidate set and (k), rather than on the entire history.

    A conceptual pipeline looks like this:

    1. latent_keys = compress(keys) # Block pooling, low-dimensional projection, or learned prototypes
    2. candidates = top_m(query_latent, latent_keys)
    3. selected = refine_topk(query, keys[candidates], k)
    4. output = attention(query, keys[selected], values[selected])

    The compression stage must preserve the relationship between relevant queries and keys. It does not need to retain every detail required for generation. Generation quality comes from the original key and value representations used in the second stage; the first stage only needs to avoid discarding genuinely relevant positions.

    Evaluation should therefore measure both recall—whether the required positions enter the candidate set—and downstream task performance. The indexer’s own scoring loss is not sufficient.

    Making Retrieval Scale More Slowly with Context Length

    Simply halving the representation dimension usually saves only a constant factor. To make retrieval grow more slowly relative to the context length, the system needs structural reductions in the search space.

    Hierarchical Indexing

    A lower layer can represent local blocks, while an upper layer stores summaries of those blocks. A query first searches the summary layer to locate a small number of promising blocks, then searches within those blocks.

    With a fixed number of levels, the number of comparisons can become closer to a function of block count, logarithmic traversal, or bounded branching width rather than a full-length, full-dimensional dot product.

    A Fixed Budget of Latent Units

    The online index can score a bounded set of prototypes regardless of the total history length. New tokens update the prototypes to which they belong.

    This budget becomes an engineering control that directly limits retrieval latency.

    Separating Local and Global Access

    Nearby tokens can remain accessible through a sliding window to preserve syntax and local references, while distant information is retrieved through the latent-space index.

    Many long-document tasks require both paths: a few sentences written recently and a fact introduced much earlier. Removing either path can reduce reliability.

    All of these designs share an important systems constraint: retrieval reads and writes should be contiguous and batched. Random scattered accesses across tens of millions of tokens can allow memory bandwidth to erase the benefits of lower floating-point computation.

    Training the Indexer to Learn Where Full Attention Looks

    If the indexer and the main model optimize different objectives, a faster index can still retrieve the wrong evidence. Several training practices help align them.

    • Use full attention or a higher-precision teacher to record which key positions provide high-quality evidence for each query. Train the indexer to cover those positions using recall or ranking losses rather than forcing it to reproduce every attention weight.
    • Continue language-model or instruction fine-tuning under the sparse attention mask so that the model adapts to seeing only (k) keys. Changing only inference while leaving the decoding path unchanged can create distribution shift that appears directly on long-context tasks.
    • Give additional weight to examples that are sensitive to retrieval failures. Multi-hop reasoning, table lookup, and cross-section comparison expose missed retrieval more clearly than purely local continuation.

    The candidate multiplier (m) and the final attention budget (k) should be tuned separately. If (m) is too small, accurate reranking cannot recover evidence that never entered the candidate pool. If (m) is too large, reranking approaches full-context scoring again.

    A practical strategy is to first raise recall to an acceptable downstream level and then reduce (m).

    Accuracy, Memory, and Applicability Limits

    Sparse attention is not lossless. Tasks that require global aggregation—such as computing statistics over an entire document, voting across all sections, or summarizing information in which every segment contributes a small amount—can be systematically biased by selecting only a few top-(k) positions.

    One mitigation is to keep a small number of globally visible summary tokens. Another is to perform an inexpensive aggregation over block summaries and allow each query to access both detailed candidates and global summaries.

    Latent-space compression also does not automatically eliminate key-value cache memory. The cache still grows approximately with the number of layers, attention heads, and context length. Latent representations reduce selection computation, but they do not by themselves remove the original cached keys and values.

    If the complete cache cannot fit on the device, the system may additionally require block-wise paging, cache quantization, or materialization of only candidate blocks. Computation speed and memory capacity must be treated as separate constraints. At tens of millions of tokens, the system may run out of memory before computation becomes the limiting factor.

    The hot path also differs between prefill and decoding:

    • Prefill performs indexing over a large existing history.
    • Decoding performs an incremental query against the existing index for each new token.

    Incremental updates must avoid rebuilding all latent representations at every step. Otherwise, interactive latency will still degrade linearly with context length.

    A Practical Evaluation Checklist

    When implementing latent-space sparse attention, consider the following checks:

    • Compare full attention, window-only attention, block-sparse attention, and latent-space sparse attention on the same long-context tasks.
    • Report retrieval-oriented and aggregation-oriented scores separately instead of relying only on continuation perplexity.
    • Measure indexer time, attention time, memory traffic, and candidate-set size to verify that the speedup comes from fewer comparisons rather than from an overly short test context.
    • Test document boundaries, repeated sections, and adversarial near-duplicates, which are especially likely to confuse low-dimensional prototypes.
    • Treat (k), block size, and latent dimension as capacity controls. Perform a small sweep at the target context length before fixing them; do not directly extrapolate the optimal (k) from short contexts to tens of millions of tokens.

    A usable extreme-context system does not require every query to reread the entire history. It requires the cost of finding relevant history to remain controllable with length, while preserving the original keys needed for accurate attention.

    Latent-space sparse attention provides this division of labor: the compressed space performs retrieval, and the original space performs computation. With cost decomposition, recall-aware evaluation, and explicit cache planning, this architecture can better balance latency and task accuracy at tens-of-millions-token context lengths.