Index Optimization for Sparse Attention at Tens of Millions of Tokens

    This article examines why sparse attention becomes index-bound when context grows to tens of millions of tokens, and reviews Latent Sparse Attention (LSA) as an index optimization approach. It explains low-dimensional projection, two-stage candidate screening, replacement preconditions, a comparison with conventional indexers, how to interpret reported speedup and accuracy figures, and includes a pseudocode sketch.

    1. Background: Sparsification Has Become a Mainstream Path for Long Context

    In recent years, context lengths for large models have expanded from hundreds of thousands of tokens to millions, and some models now treat ultra-long context as a default service specification. A common design is a hybrid architecture: most layers use sparse attention or linear attention, while only a small number of global attention layers are retained. Each query no longer traverses the entire history; instead, an indexer selects a small number of relevant tokens for computation.

    At the million-token scale, this approach has been validated repeatedly. Accuracy loss remains controllable, and memory usage drops noticeably. The problem appears when context continues to grow into the tens of millions of tokens.

    2. The Core Issue: Computation Is Saved, but Retrieval Is Not

    During prefill at the tens-of-millions-token scale, measurements show that most of the time is spent in the indexing stage rather than in attention computation itself. Here, indexing means deciding which tokens each query should attend to.

    This implies two things. First, focusing on only a small number of key tokens can preserve accuracy, and this has already been validated. Second, the process of finding those tokens still requires evaluating similarity between the query and historical tokens. If every query is compared with all historical tokens, the computation still grows quadratically with context length. The time saved on attention computation may be consumed by index retrieval.

    3. The Latent Sparse Attention Approach

    Latent Sparse Attention (LSA) is a recently proposed method. Its core idea is to first project tokens into a low-dimensional latent space, perform candidate screening in that low-dimensional space, and then return to original precision for fine selection.

    3.1 Low-Dimensional Projection Reduces the Cost per Comparison

    A conventional indexer computes similarity between keys in the full dimension. LSA reduces the dimension from d to r, where r is usually very small. This lowers the cost of each dot product from O(d) to O(r), a constant-factor reduction.

    However, this step does not change the number of objects being compared. If every query still scores all n historical tokens, the total cost is O(n²·r), which is still quadratic growth. To obtain near-linear indexing overhead, an additional mechanism is needed, such as approximate nearest neighbor (ANN) retrieval, blocking, or clustering, so that each query is compared only with a subset of candidates. The source material does not state which mechanism is used, so low-dimensional projection alone is not enough to conclude that indexing has become near-linear.

    3.2 Two-Stage Screening Provides an Accuracy Fallback

    Low-dimensional projection loses information, and using it directly to select tokens may miss key content. The two-stage approach works as follows:

    • In the first stage, a candidate set is recalled in latent space. The goal is high recall with low per-query cost.
    • In the second stage, the candidate set is rescored at original precision to decide which tokens finally participate in attention computation.

    A larger candidate set makes recall more stable, but it also increases the cost of the second stage. The candidate count C is the most critical tuning parameter and requires a trade-off between accuracy and speed.

    3.3 Preconditions for Replacement

    LSA is designed as an intra-layer replacement within existing sparse attention architectures and does not change the model’s hybrid layout. Whether it can be replaced directly depends on how the projector is obtained. The projection matrix usually needs training or distillation so that sufficient similarity information is retained in the low-dimensional space. Therefore, “replaceable” applies only to models that satisfy the projector adaptation conditions. Migration also requires evaluating additional parameters, memory used by latent representations, and the cost of training adaptation.

    4. Conventional Indexer vs. LSA

    Dimension Conventional Indexer LSA
    Similarity computation dimension Full dimension d Low dimension r
    Full-scan complexity O(n²·d) O(n²·r); ANN or blocking is needed for further reduction
    Source of accuracy Direct scoring at original precision Latent-space recall plus original-precision fine selection
    Additional parameters Depends on the specific design Projection matrix
    Training cost Depends on the specific design Projector adaptation required
    Main risk High retrieval overhead in long context Recall affected by projection quality and candidate count

    5. How to Interpret the Performance Data

    Public materials mention two figures: a hybrid sparse architecture model achieved more than 20x prefill speedup in its global attention layers, and another medium-scale model achieved more than 70x speedup in a single layer. On accuracy, tasks such as long-text understanding and retrieval question answering were described as basically on par with the original model.

    These numbers need verification before they can be used as references. At minimum, the following information should be confirmed: model scale, sequence length, hardware model, batch size, measurement scope (whether index time is included), and the specific accuracy metrics and tasks. Without this information, they should be treated as references pending verification, not as benefits that can be promised directly.

    The meaning of “basically on par” also needs to be qualified. It may hold only on some tasks and may be sensitive to changes in the candidate count.

    6. Pseudocode Sketch

    1. def lsa_attention(query, keys, values, causal_mask, C):
    2. # query: [H, Q, d], where Q is the number of queries in this computation
    3. # keys, values: [H, n, d], keys and values of historical tokens
    4. # causal_mask: [Q, n], query at position i can only see keys j <= i
    5. # C: number of candidates, much smaller than n
    6. # 1. Project to low-dimensional latent space, where r is a small constant
    7. q_lat = query @ W_q # [H, Q, r]
    8. k_lat = keys @ W_k # [H, n, r]
    9. # 2. Latent-space coarse screening: still scans all n keys;
    10. # ANN or blocking is needed to reduce complexity
    11. coarse = q_lat @ k_lat.transpose(-1, -2) # [H, Q, n]
    12. coarse