Where Did the Quadratic Go? A Field Guide to the 2026 Sparse-Attention Wave

Abstract

Between February 2025 and June 2026, transformer attention went from a known bottleneck to an engineering arms race. Standard attention re-reads every prior token for every new token generated, at quadratic cost in sequence length. At one million tokens, the attention matrix holds a trillion values. Seven architectures now claim solutions: NSA, DSA, MSA, HydraHead, SparDA, RKSC, and Zipage. They arrived within months of each other, each reporting speedups between 1.7× and 20× over full attention.

This piece does three things, in three parts. Part I tells the plain story for a reader who wants to understand what changed and why it costs money, without mathematics. Part II explains the mechanics — what attention is, where the cost lives, what sparse means at the arithmetic level. Part III introduces a two-axis taxonomy that places every architecture on one map: where it applies sparsity (the granularity axis — head, block, token, or reasoning-branch) and how it selects what to keep (the selection axis — learned index, lookahead forecast, similarity gate, or confidence gate). The taxonomy surfaces which cells are crowded and which remain open questions for the field.

A counter-argument from LMSYS runs throughout. The speedup numbers are real. The conditions under which they hold are narrower than most abstracts convey. The piece ends with a decision framework rather than a verdict.

Part I requires no background. Part II requires familiarity with neural networks. Part III assumes comfort with transformer architecture.

---

Part I — The Plain Story

The machine that re-reads everything

Hand an AI assistant a five-hundred-page legal contract and ask it a question about clause 23 on page 340. The assistant answers correctly. What happened on the server is less obvious than the answer on your screen.

Before generating each word of its reply, the model did something most people do not expect: it read the entire five hundred pages again. Not once for the whole reply — once for every single word of the response. A five-sentence answer required five complete re-reads of the contract.

This is not a bug. It is how transformer attention was designed in 2017, when the sequences being processed were short enough that the cost did not matter (Vaswani et al., 2017). The mathematical name for the cost is quadratic: double the document length, and the computation does not double — it quadruples. Triple the length, nine times the work. A standard model handling one million tokens — roughly a thousand pages — runs a computation that would have been considered reckless to attempt five years ago.

For the companies running these systems at scale, quadratic attention is a significant line item. A single inference request at one million tokens can cost tens of cents on current cloud hardware. Run that a million times a day, and the number becomes uncomfortable to discuss in a quarterly review.

What a smarter reading strategy looks like

Consider what a human expert does with a long document. They do not re-read every word before forming each thought. They build a mental map: key clauses here, definitions there, exceptions in the appendix. When they need something specific, they flip to the right section. Most pages are never revisited.

For three years, researchers tried to teach language models a version of this strategy. Make attention sparse: instead of scoring every prior token, score only the tokens most likely to matter — a selected subset, a top-k. The idea is obvious. The execution turned out to be hard.

Early sparse attention methods traded accuracy for speed in ways that broke quietly. A model might appear to answer correctly on standard benchmarks while silently losing track of distant context — the very thing long-context is supposed to fix. The methods were also difficult to train from scratch: gradients do not flow cleanly through hard selection operators. And even when the math worked, the hardware did not cooperate. GPUs are optimized for the dense matrix multiplications of full attention, not the irregular access patterns of sparse selection.

What changed, and when

The problem sat unsolved at production scale until February 2025, when a team at DeepSeek and Peking University published Native Sparse Attention (NSA) — a paper that would receive a Best Paper award at the Association for Computational Linguistics conference that July (Yuan et al., 2025). NSA was the first design to be natively trainable, hardware-aligned, and competitive with full attention on quality benchmarks simultaneously. It demonstrated substantial speedups on 64,000-token sequences while the model maintained performance on general tasks, long-context retrieval, and instruction-following.

The DeepSeek team deployed a refined version in DeepSeek-V3.2, released in late 2025. DeepSeek Sparse Attention (DSA) introduced a "lightning indexer" that reduced attention computation from O(L²) to O(Lk), where k is a fixed small number. At 128,000 tokens, DSA runs at approximately 1.6% of the operations that full attention requires, with output quality that is indistinguishable from the full-attention baseline (DeepSeek-AI, 2025).

In the three weeks before this writing, four more architectures appeared. MiniMax deployed Sparse Attention (MSA) in its M3 model, a 428-billion-parameter open-weight system, claiming one-twentieth of the per-token compute at one million tokens (Lai et al., 2026). Alibaba published HydraHead, which applies sparsity not at the layer level but inside each layer — along the individual attention head axis (Tan et al., 2026). A team from NVIDIA, MIT, and ByteDance published SparDA, which adds a single new projection to predict which memory blocks the next layer will need, prefetching them before they are required (Fu et al., 2026). And a researcher named Anirudh Sekar demonstrated that inference on reasoning-heavy workloads could run three times faster with no training changes at all, by sharing memory caches across semantically similar reasoning paths and exiting early when the model's output is sufficiently certain (Sekar, 2026).

What this means for anyone using long-context AI

Two things become cheaper when these architectures become standard. The first is the length you can afford to send: at one-twentieth the compute, a document that cost a dollar to process costs five cents. The second is throughput: the same hardware can serve twenty times as many requests at the same cost. Both matter to anyone building on top of these systems, and both change the economics of what is worth building.

The flip side — which Part III examines carefully — is that these gains are not universal. Each architecture has conditions under which it fails quietly, and none of them have been measured against a common standard. The speedup numbers in the papers are real. The headlines are not lying. The conditions are narrower than the abstracts suggest.

That is where the plain story ends. The single takeaway: language models have been learning to stop re-reading the whole book, and 2026 is the year that transition became production-grade. Part II explains the mechanism. Part III maps the field.

---

Part II — How It Actually Works

What attention is

A transformer language model generates text one token at a time. To decide what token comes next, it needs to consider what came before. Attention is the mechanism that does this.

For each new position in the sequence, the model computes three things from its current representation: a query (what this position is looking for), a set of keys (what each prior position contains), and a set of values (what each prior position would contribute if selected). The model then scores the query against every key — a dot product — which produces a weighted distribution over the values. The output is a weighted average of all values, where positions with high query-key similarity contribute more.

This is the mechanism that makes transformers good at understanding context. It is also the mechanism that causes the quadratic cost. Computing a score between every query and every key in a sequence of length L requires L × L = L² operations. A sequence of 1,000 tokens: one million operations. A sequence of 100,000 tokens: ten billion. A sequence of one million tokens: one trillion.

Two bottlenecks, not one

The cost lives in two places, and separating them is important for understanding why different architectures make different choices.

Sparse attention helps with both, through different mechanisms. Reducing the score computation from O(L²) to O(Lk) cuts prefill FLOPs directly. Evicting or compressing the KV-cache reduces the volume of memory reads during decode. A complete efficient-attention design needs to address both; several of the architectures in Part III focus on one more than the other.

What sparse means at the arithmetic level

The key insight: in practice, most of the attention weight in a full-attention computation concentrates on a small fraction of tokens. The rest contribute negligible weight to the output. Computing those near-zero weights is expensive work that could have been skipped.

Sparse attention converts "find the top-k contributing tokens" from an approximation into an architectural choice. Fix a value k much smaller than L. Identify (by some mechanism) the k tokens most likely to matter for the current query. Compute exact attention over only those k tokens. The compute cost falls from O(L²) to O(Lk). Since k is fixed while L grows, the savings increase with sequence length — precisely the regime where savings matter most.

At 128,000 tokens with k = 2,048, DeepSeek Sparse Attention runs at approximately 1.6% of full-attention operations, with output quality indistinguishable from the dense baseline (DeepSeek-AI, 2025). This figure is what made the research community take sparse attention seriously at production scale.

The savings grow without bound as context grows. This is the property that makes sparse attention attractive for the million-token regime specifically.

Why naive sparsity failed, and what NSA changed

Three problems appeared consistently in earlier sparse attention work.

Quality degradation. A sparse method that cannot reliably identify the important tokens makes mistakes in unpredictable ways. A model might score well on benchmarks designed for 4,096-token contexts while quietly losing retrieval ability at 64,000 tokens.

Training instability. Hard top-k selection is not differentiable — gradients cannot flow back through a discrete argmax. Earlier methods either trained with full attention and switched to sparse at inference (degraded quality), or relied on complex approximations.

Hardware inefficiency. Standard GPU kernels for attention assume dense, regular access patterns. Sparse selection introduces irregular memory reads that leave tensor cores underutilized. The theoretical FLOPs savings were often not realized in wall-clock time.

Native Sparse Attention, published by Yuan et al. at ACL 2025 and awarded Best Paper, addressed all three. The key innovations: a hierarchical strategy combining coarse-grained token compression with fine-grained token selection (preserving global context awareness while allowing local precision); an arithmetic intensity-balanced algorithm that maintains high GPU utilization under sparse access; and end-to-end training without approximation. Matching or exceeding full-attention performance on general benchmarks while delivering substantial speedups at 64K-token sequences established that production-quality sparse attention was architecturally possible. The June 2026 wave extends or elaborates on that conclusion.

The building blocks every viable scheme now shares

Before the taxonomy in Part III, a summary of what every current architecture has in common.

The differences between architectures lie in which selection mechanism they use and at what granularity they apply sparsity. That is what the taxonomy in Part III is designed to make legible.

---

Part III — The Expert Field Guide

Mapping the design space

Seven architectures. Two axes. This is the frame that makes the field legible.

The first axis is granularity — the unit at which sparsity is applied.

The second axis is selection mechanism — how the system identifies which tokens or blocks to keep.

Placing every architecture on the combined grid:

The crowded cells and the open ones

The block-level granularity × learned-index selection cell is now the dominant production pattern: NSA, MSA, and DSA all occupy it, with variation in indexer architecture. This is where production deployment has concentrated, and it is the regime where the FLOPs math most clearly favors sparsity — gains increase with context length, as shown in the Part II table.

The head-level granularity cell has a single occupant: HydraHead. The observation motivating it — that individual attention heads within the same layer serve distinct functional roles, and that this heterogeneity is measurable and exploitable — is independently supported by a growing mechanistic interpretability literature. Whether head-level selection generalizes to larger models and other architectures is not yet established.

Branch-level sparsity is represented by RKSC's cross-branch KV sharing component. The insight that semantically similar reasoning branches can share a common KV cache prefix is clean, and the training-free implementation is notable. The evaluation covers models in the 7B–10B range; whether the gains hold at frontier scale is an open question.

Several (granularity × selection) combinations remain entirely absent from the current literature. The reasons are not obvious. These are not cells that are theoretically unattractive or that require capabilities current tooling cannot support. They are simply unexplored — which is normal for a field that converged on a new production approach within eighteen months.

A note on benchmarks: the figures are not comparable

The speedup figures in the table above cannot be placed on a common scale. This is not an editorial choice. It is the current state of the field.

A valid comparison would require the same model size, the same GPU, the same context-length distribution, and the same workload mix. That comparison does not yet exist in the published literature.

Claiming that DSA's "1.6% operations at 128K" is comparable to MSA's "1/20 compute at 1M" is incorrect: the context lengths differ by 8×, and as shown in the Part II table, savings grow with length. At 1M tokens, DSA would show a larger saving than 1.6%; at 128K, MSA would show a smaller saving than 1/20. Neither paper is being misleading. Each is transparent about its setup. The absence of a unified harness is simply an open gap in the field's infrastructure.

The "No Free Lunch" counter-case

In November 2025, LMSYS published an analysis of MiniMax M2's efficient attention design under the title "No Free Lunch" (LMSYS Org, 2025). The conclusion is worth carrying into every evaluation of the June 2026 wave: "As GPU compute growth slows and context lengths continue to increase, the benefits of linear and sparse attention will eventually emerge. However, to cross the chasm from theory to production, the community must continue to invest in building more informative evaluation systems, more mature training frameworks, and more robust evaluation methodologies."

The underlying argument has three parts.

Evaluation systems lag. The benchmarks most commonly used to validate sparse attention quality — needle-in-haystack, RULER, LongBench — are well-characterized and increasingly saturated. A model can pass them while silently degrading on retrieval patterns that production workloads actually require. The quality-preservation claims across this wave are made against these benchmarks, not against production query distributions.

The hardware picture changes at scale. Single-GPU inference benchmarks look different from production deployments with disaggregated prefill/decode serving, continuous batching, and multi-node parallelism. A technique that recovers 20× FLOPs in isolation may deliver 2× throughput in a batched serving system where the bottleneck has moved to inter-node communication or KV transfer latency.

Training stability at frontier scale is not fully characterized. NSA demonstrates end-to-end training. DSA was obtained by continued pretraining from V3.1-Terminus rather than full pretraining from scratch. Whether all architectures in the wave are as stable to train at 400B+ parameters as their papers suggest is an empirical question that requires data not yet publicly available.

None of this invalidates the efficiency gains. MiniMax M3 is deployed. DeepSeek-V3.2 is deployed. Boyina's analysis of MSA's kernel confirms the 28× attention compute reduction at 1M tokens is real (Boyina, 2026). The point is that the conditions for realizing the full published gains are more specific than headlines convey.

A decision framework

Three principal findings

First: the NSA-to-DSA-to-MSA lineage demonstrates that production-scale sparse attention at million-token contexts is no longer theoretical. It is deployed in MiniMax M3 (428B MoE parameters, open-weight, 1M context window) and DeepSeek-V3.2 (685B MoE parameters) as of mid-2026. The transition from academic curiosity to frontier model infrastructure took less than eighteen months.

Second: the field has converged on block-level granularity with learned-index selection as the dominant production pattern. Head-level, branch-level, and several other (granularity × selection) combinations are either underrepresented or entirely absent from current deployments, relative to what the full architecture space would suggest.

Third: speedup figures across papers are not comparable. Context length, GPU model, batch size, baseline, and the prefill/decode phase being measured vary arbitrarily between publications. A unified empirical comparison across a single evaluation harness does not yet exist. Building one is the field's most pressing near-term infrastructure need.

---

References

1. Yuan, J., Gao, H., Dai, D., Luo, J., Zhao, L., Zhang, Z., Xie, Z., Wei, Y. X., Wang, L., Xiao, Z., Wang, Y., Ruan, C., Zhang, M., Liang, W., & Zeng, W. (2025). Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (ACL 2025), Volume 1: Long Papers, pp. 23078–23097. arXiv:2502.11089.

1. DeepSeek-AI. (2025). DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models. arXiv:2512.02556.

1. Lai, X., Xu, W., Yang, Y., Chen, Q., Xu, Y., Zeng, L., Li, X., Sun, H., Zhu, H., Zhang, V., Hu, J., Li, J., Gao, R., Li, Z., Zhu, S., Zhou, J., & Zhao, P. (2026). MiniMax Sparse Attention. arXiv:2606.13392.

1. Tan, Z., Chen, W., Shen, J., Liu, Y., Shen, X., Wu, Y., & Ye, J. (2026). HydraHead: From Head-Level Functional Heterogeneity to Specialized Attention Hybridization. Alibaba Group. arXiv:2606.20097.

1. Fu, Y., Xiao, G., Dong, X., Han, S., & Villa, O. (2026). SparDA: Sparse Decoupled Attention for Efficient Long-Context LLM Inference. NVIDIA / MIT / ByteDance. arXiv:2606.04511.

1. Sekar, A. (2026). RKSC: Reasoning-Aware KV Cache Sharing and Confident Early Exit for Multi-Step LLM Inference. arXiv:2606.09937.

1. Liao, M., Wang, L., Zhang, C., Qiao, B., Qin, S., Lin, Q., Rajmohan, S., Zhang, D., & Wan, H. (2026). Zipage: Maintain High Request Concurrency for LLM Reasoning through Compressed PagedAttention. Microsoft / Beijing Jiaotong University. arXiv:2603.08743.

1. Srivastava, A. (2026, June 12). Deploy Long-Context Reasoning and Agentic Workflows with MiniMax M3 on NVIDIA Accelerated Infrastructure. NVIDIA Technical Blog.

1. LMSYS Org. (2025, November 4). "No Free Lunch": Deconstruct Efficient Attention with MiniMax M2. LMSYS Blog.

1. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., & Polosukhin, I. (2017). Attention Is All You Need. Advances in Neural Information Processing Systems (NeurIPS 2017), 30.

1. Boyina, G. (2026, June 19). MiniMax Cut Attention Compute by 28x at 1M Tokens. Towards AI.

---

Sources: arXiv:2502.11089, arXiv:2512.02556, arXiv:2606.13392, arXiv:2606.20097, arXiv:2606.04511, arXiv:2606.09937, arXiv:2603.08743, developer.nvidia.com, lmsys.org, pub.towardsai.net

Last updated: June 22, 2026