Why Sparse Attention Is Still Quadratic at Million-Token Contexts: Indexer Cost, Constant Factors, and What Actually Changes the Complexity Class

    As million-token context windows become a baseline capability of frontier LLMs, attention computation has become the most visible variable in inference cost. Engineering approaches aimed at long context all try to cut that cost: sparse attention masks, lightweight "indexers" that score attention relevance separately, and block-sparse schemes that select and compute at block granularity. Claims like "22x faster than mainstream sparse attention at tens of millions of tokens" sound striking, but under an asymptotic-complexity lens they describe the constant factor, not the order. This article explains why quadratic cost in prefill is hard to escape, why indexer optimizations cannot break the quadratic barrier mathematically, and under which conditions developers should adopt sparse and hierarchical strategies so that complexity gains actually show up in business metrics.

    Introduction: The Real Problem Behind “22x Faster”

    Once million-token context becomes a baseline capability of frontier LLMs, attention computation has become the most visible variable in the cost structure of inference serving. The industry has responded with a family of long-context engineering approaches: applying sparse masks to attention, designing a lightweight “indexer” dedicated to attention scoring, and adopting block-sparse strategies that select and compute at block granularity.

    The claimed gains are often striking — for example, “22x faster than mainstream sparse attention schemes at the ten-million-token scale.” But if you put the question back into a complexity framework, you notice these conclusions describe not the order of complexity but the coefficient.

    A simple observation: as long as the indexer must still compare a query against every key in the context, the total work grows quadratically with context length — no matter how cheap each individual comparison becomes (lower precision, fewer dimensions, multiple keys merged into one computation). Dividing the constant by tens does not turn a quadratic curve into a linear one.

    This article tries to answer three questions:

    1. Why the quadratic complexity of the prefill stage is so stubborn;
    2. Why “indexer cost reduction” optimizations cannot break the quadratic barrier mathematically;
    3. Under what conditions and in what way developers should use sparse and hierarchical strategies so that complexity gains actually land on business metrics.

    1. Where the Bottleneck Actually Sits in Long Context

    1.1 Prefill and decode have completely different complexity profiles

    Autoregressive inference splits into two phases with entirely different bottlenecks:

    Phase Main cost Compute characteristics Business metric
    Prefill One-shot attention and FFN over all input tokens Compute-bound; large matrices, high parallelism Time to first token (TTFT)
    Decode Each step computes attention for the new token against all historical KV Memory-bound; constrained by KV cache read bandwidth Time per output token (TPOT), throughput

    For standard multi-head attention with sequence length L and per-head dimension d, the two matmuls Q·Kᵀ and attn·V together cost roughly 4·L²·d multiply-adds. This term grows with the square of the length and directly determines prefill latency.

    1.2 Why “dense” cannot be the default for long context

    A quick order-of-magnitude calculation under a typical configuration (estimated as 4·L²·d, excluding FFN):

    Sequence length L Compute (FLOPs) Single-layer prefill time at 400 TFLOPS effective per-card throughput
    8K ≈ 2.1 × 10¹² ~5 ms
    32K ≈ 3.4 × 10¹³ ~85 ms
    128K ≈ 5.5 × 10¹⁴ ~1.4 s
    1M ≈ 3.4 × 10¹⁶ ~85 s

    Two caveats: this estimate assumes a single attention layer completed serially on one card, and excludes parallel partitioning, fused kernels, and pipelining optimizations. It illustrates the order of magnitude only; the values involve unit-rounding approximations and should not be cited as actual product performance data.

    The conclusion is clear: double the length and the compute becomes four times. Going from 128K to 1M is only an 8x difference in length, but a 64x difference in compute. That is the entire motivation for sparsification.

    1.3 The basic idea of sparse attention: compute the cheap part first, then the expensive part

    The general paradigm of sparse attention can be summarized as “select first, then compute“:

    1. Use a lightweight scoring function (the indexer) to compute a relevance score for every candidate key;
    2. Keep only the top-k keys (or top-k blocks) by score;
    3. Run the full attention computation only over the selected subset.

    With this, the cost of step 3 drops from O(L²) to O(L·k); when k is independent of L (a fixed budget), that part becomes linear. This is also the fundamental reason sparse attention still holds up on long context.

    The problem lies in step 1.


    2. The Core Conflict: Indexer Cost Cannot Be “Skipped”

    2.1 The indexer is a step that must scan everything

    The correctness of top-k selection depends on comparing against all candidates. Unless an additional index structure is introduced (hierarchical, clustered, hashing, and so on — see section 5), then:

    • every token must compute a score against all L keys;
    • the full pass processes L tokens;
    • total indexer work ≈ c_index · L², where c_index depends on index dimension, precision, and the computation method.

    So the total cost of sparse attention is approximately:

    1. T(L) ≈ α · L² (indexer, quadratic term)
    2. + β · L · k (selected attention, linear when k is fixed)
    3. + γ · L (FFN and the rest, linear)

    As long as α > 0, the asymptotic order of T(L) is Θ(L²).

    2.2 The mathematical nature of the three common “cost reduction” tactics

    Efforts to lighten the indexer roughly fall into three categories:

    1. Lower numerical precision: use FP8/INT8 or even fewer bits for similarity scoring, exploiting hardware low-precision throughput;
    2. Compress the index dimension: instead of scoring with vectors at the same dimension as main attention, project into a low-dimensional space (such as 64 or 128 dimensions), or replace all attention heads with a few index heads;
    3. Merge multiple keys: aggregate consecutive groups of 4 (or 8, or 16) keys into a “block representation” (mean pooling, max pooling, learned projection), using one score to stand in for an entire block.

    All three share the same characteristic: they change the cost of each comparison, not the number of comparisons.

    Tactic Effect on per-comparison indexer cost Effect on asymptotic order
    Lower precision (e.g., 16-bit → 8-bit) ~2x cheaper None; still Θ(L²)
    Lower dimension (d → d/16) ~16x cheaper None
    Merging 4 keys into 1 block representation ~4x cheaper None
    Fixed window + local block sparsity Comparison count grows linearly with L Drops from Θ(L²) to Θ(L)

    Stacking the first three does deliver one to two orders of magnitude of constant-factor gains. But they have no effect at all on the slope of the curve. The fourth is different because it directly reduces the number of comparisons rather than the unit price of each one.

    2.3 “22x” and “the quadratic bottleneck” can both be true

    This is the point most often misread. Let us break it apart:

    • At 1M length, dense attention costs roughly 3.4 × 10¹⁶ FLOPs (single layer, 4·L²·d estimate);
    • with an indexer using d_index = 128, 8-bit precision, and 4:1 block merging, its own cost is on the order of 1/128 of the dense Q·Kᵀ part;
    • combined with kernel fusion, memory-access optimization, and low-precision throughput advantages, tens of times end-to-end speedup is entirely plausible at the order-of-magnitude level.

    But this still only answers “at the same L, how much faster?” It does not answer “when L doubles again, how much slower?” The latter is determined by the asymptotic order, and that has not changed.

    A clearer way to put it: this class of work improves how well the constant factor can be exploited — compressing a quadratic complexity that was previously bound by memory bandwidth and unable to saturate compute into something that fits inside an existing hardware budget. Its value is real, but it is engineering value, not an asymptotic breakthrough.


    3. Illustrative Code: Understanding the Cost Structure of an Indexer

    The Python pseudocode below illustrates the flow of “block-level indexer + block-sparse attention” (no third-party dependencies), with emphasis on where each part of the computation is accounted for.

    1. import math
    2. def index_score(q_low, k_block_repr, dim_index):
    3. """Indexer: dot product of query and block representation in a
    4. low-dimensional, low-precision space."""
    5. return sum(a * b for a, b in zip(q_low, k_block_repr)) / math.sqrt(dim_index)
    6. def build_block_index(k_low, block_size=4):
    7. """Aggregate every block_size consecutive keys into one block representation.
    8. This step is offline/precomputed and is not part of online attention cost.
    9. """
    10. blocks = []
    11. for start in range(0, len(k_low), block_size):
    12. chunk = k_low[start:start + block_size]
    13. # Mean pooling: 4 keys into 1, so indexer work drops by ~4x
    14. rep = [sum(col) / len(chunk) for col in zip(*chunk)]
    15. blocks.append(rep)
    16. return blocks
    17. def sparse_attention_prefill(q_low, k_low, v_low, topk=64, block_size=4, dim_index=128):
    18. """
    19. Step 1: full scan by the indexer (cost ∝ L)
    20. Step 2: select topk blocks, run attention only inside them
    21. (cost ∝ L * topk * block_size)
    22. Note: if q_low runs this flow for all L tokens, the total cost of
    23. step 1 is ∝ L^2
    24. """
    25. blocks = build_block_index(k_low, block_size=block_size)
    26. scores = [(index_score(q_low, b, dim_index), i) for i, b in enumerate(blocks)]
    27. scores.sort(key=lambda x: x[0], reverse=True)
    28. selected = [i for _, i in scores[:topk]]
    29. total, norm = 0.0, 0.0
    30. for b in selected:
    31. start = b * block_size
    32. for j in range(start, min(start + block_size, len(k_low))):
    33. # This is the actual attention computation, bounded by topk
    34. w = math.exp(index_score(q_low, k_low[j], dim_index))
    35. total += w * v_low[j]
    36. norm += w
    37. return [x / norm for x in total]

    Two things in this code are easy to confuse and worth pointing out separately:

    • The pooling cost in build_block_index is preprocessing in nature. It can be reused across layers and completed offline, and should not be counted toward online attention complexity;
    • what actually determines the complexity order is “whether the outer loop performs a full scores scan for every token.” It does — and that is precisely the source of the quadratic term.

    Put differently, compressed representations optimize the representation cost of each block, while hierarchical retrieval is what optimizes the number of scans. The two are not interchangeable.


    4. Order-of-Magnitude View: When the Indexer Becomes the Dominant Term

    Write the total cost in comparable form, with k the number of keys retained per token, b the block size, d the main attention dimension, and d_index the index dimension:

    1. T(L) ≈ α·L² + β·L·k + γ·L

    In the long-context regime, the ratio of the indexer term α·L² to the main attention term β·L·k is roughly (α·L) / (β·k). This means:

    • once L grows past a certain point, the indexer term necessarily overtakes the main attention term and becomes the only dominant term;
    • the larger k (the more you keep), the heavier the main attention term, and the lower the indexer’s relative share;
    • therefore, optimizations that reduce indexer cost pay off most in scenarios with small k and large L.

    This explains why these optimizations show the most significant gains in scenarios like long-document retrieval, repository-level code understanding, and multi-turn long-conversation summarization — scenarios where k stays relatively tight while L balloons. Conversely, if the workload needs to retain nearly the entire context (k approaching L), the benefit of sparsification decays quickly; a more sensible direction then is improving the efficiency and parallelism of the attention kernel rather than continuing to subtract from the indexer.


    5. Directions That Actually Change the Asymptotic Order

    If the goal is to turn Θ(L²) into Θ(L) or Θ(L·logL), you must reduce the number of comparisons, not the cost of each comparison. Common industry paths:

    5.1 Fixed window + local block sparsity

    Restrict each token’s visibility to the most recent w tokens plus a small set of global tokens. Total cost becomes Θ(L·w), strictly linear.

    The cost is a limited receptive field: distant critical information must be perceived through a hierarchy (such as segmented summarization) or through multiple rounds of propagation, which requires additional design for tasks that need reasoning across large spans (long-document QA, cross-file code understanding).

    5.2 Hierarchical / coarse-filter then fine-rank

    A two-level structure:

    1. The first level uses an extremely cheap method (block means, hierarchical clustering, random projection) to compress L candidates into O(L/B) candidate blocks;
    2. The second level performs precise scoring only within the few selected blocks.

    With O(L/B) and O(B) candidates at the two levels, total cost is Θ(L·(L/B + B)), which reaches Θ(L^1.5) when B ≈ √L. This is a subquadratic but not strictly linear compromise that is very easy to deploy in practice, with typically controllable impact on accuracy.

    5.3 Approximate-nearest-neighbor style indexing

    Hand similarity retrieval to a dedicated nearest-neighbor index structure (clustered inverted lists, product quantization, locality-sensitive hashing, and so on). Such methods can approach O(L·logL) or lower in the average case, but they require maintaining an additional index, and in the dynamically growing KV cache scenario (keys and values are continuously appended during decode) they need incremental updates, which raises implementation complexity considerably.

    5.4 Structural approaches: linear attention and state space models

    Linear attention factorizes the kernel and rewrites attention into a recurrent form, achieving strictly O(L) complexity; state space models maintain history in a fixed-size hidden state, which is essentially “trading constant memory for quadratic compute.”

    The advantages of this class are the best asymptotic order. The disadvantages:

    • relatively weak performance on exact retrieval tasks (needle-in-a-haystack style fragment localization);
    • more complex training and inference implementations, and long-context extrapolation requires additional positional encoding design;
    • incompatible with existing model architectures built around softmax attention, which usually means retraining rather than an incremental swap.

    6. Engineering Practice: Turning Complexity Gains into Metrics

    6.1 First measure your length-latency curve

    Before making a selection, collect data using your actual business length distribution: measure time to first token at the four tiers 8K / 32K / 128K / 1M, then fit the slope in log-log coordinates.

    • Slope near 2 → still dense, or “fake sparse” (the indexer is not really taking effect, or top-k is not being pruned cleanly);
    • Slope near 1 → linear regime dominant, the sparse strategy is working;
    • Slope between 1 and 2 → subquadratic, typically the signature of hierarchical retrieval working.

    This curve is far more valuable for decision-making than any single “N times faster” claim, because it tells you directly what happens when the business length doubles.

    6.2 Sparsity budget: k is not “bigger is better”

    Make k a configurable parameter, tiered by workload type:

    • Summarization, rewriting, multi-turn conversation: k can be tight (a few hundred to one or two thousand);
    • Long-document QA, retrieval-augmented generation: moderate k, combined with hierarchical coarse filtering;
    • Repository-level code understanding, cross-file reasoning: k needs to be more generous, and at this point it is worth evaluating a hybrid “local window + global tokens” structure.

    It also helps to add a lower-bound safeguard to top-k selection: when all candidate scores are extremely low, fall back to a local window plus a fixed-proportion random sample, so the model does not over-concentrate on a few blocks for inputs that contain no relevant information.

    6.3 Scheduling and reuse: amortize the preprocessing cost

    • Precompute block representations and reuse them across layers: block mean/pooled representations are independent of the specific attention head, so they can be shared across layers, or even cached across requests (a notable win for static long-document scenarios);
    • Chunked prefill: split an oversized prefill into multiple chunks and interleave scheduling with decode requests, avoiding a long request monopolizing compute for a long time, which improves overall throughput and tail latency;
    • Sequence parallelism: partition the sequence dimension across multiple cards and complete attention with ring communication; note that block sparsity causes load imbalance, so dynamic assignment by block score is needed rather than static even splitting;
    • Paged KV cache management + low-precision storage: paging reduces fragmentation, and low-precision KV storage directly relieves the memory-access bottleneck in the decode phase;
    • Kernel fusion: make sure top-k selection, gather, softmax, and the weighted sum are fused into a single kernel, avoiding repeated reads and writes of intermediate tensors to device memory — especially critical for a memory-bound stage like the indexer.

    6.4 Accuracy and quality validation

    The impact of sparsification on accuracy usually shows up in “long-range critical information.” Cover at least three categories of validation:

    1. Long-document key information localization (fact extraction across large spans);
    2. Multi-hop reasoning (information scattered across fragments that are far apart);
    3. Long-context stability (how output consistency varies with input length).

    Validation should use evaluation sets consistent with your business distribution rather than generic benchmarks, because the failure modes of sparse strategies are highly dependent on the data distribution.


    7. Selection Guidance: One-Line Conclusions

    • If your business lengths are within 32K, kernel efficiency and parallelism should be the priority, and the marginal benefit of sparsification is limited;
    • If lengths exceed 128K and you need strict constant-factor control, the combination of local window + hierarchical coarse filtering + block sparsity is usually the most cost-effective engineering path;
    • If you need million-level context and are sensitive to time to first token, it is worth evaluating linear/state space approaches in parallel, but the retraining cost and the quality loss on retrieval-type tasks must be counted into the total cost;
    • Whichever path you take, evaluating approaches by complexity slope rather than single-point multipliers is the key to avoiding expensive rework later.

    Sparse attention will not be ended by “cheaper indexers” — it will be ended by “fewer comparisons.” Understanding that dividing line has more long-term value than memorizing any set of speedup numbers.