Atlas
kb://library/native-sparse-attention2026-06-16

Native Sparse Attention (NSA, MoBA)

sparse-attentionnative-sparse-attentionnsamobalong-contextdeepseekmoonshotkimitrainable-sparsityhardware-awareattentionefficiency

Native Sparse Attention (NSA, MoBA)

One-line summary. Full attention makes every token look at every other token — cost grows with the square of sequence length, which is what makes million-token context so expensive. Native sparse attention lets each query token attend to only a small, learned subset of the past, and — the key word is native — it does this during pretraining, so the model learns with the sparsity instead of having it bolted on afterward. The two landmark 2025 designs, DeepSeek's NSA and Moonshot's MoBA, both make sparsity (a) trainable end-to-end and (b) hardware-aligned to GPU memory access, and both report matching or beating full attention on long-context benchmarks while running several times faster. NSA-style sparsity has since shipped in production (DeepSeek-V3.2's DSA, MoBA in Kimi).

What it is (intuition first)

Picture reading a 500-page novel and being asked a question about chapter 12. You do not re-read all 500 pages weighting every sentence equally. You skim to the relevant chapters, read those closely, and keep the last page you read fresh in mind. That triage — most of the text is irrelevant to this particular question, so don't pay full attention to it — is exactly the bet sparse attention makes.

Standard ("full") self-attention ([[attention-and-transformers]]) does the opposite: for a sequence of length L, every one of the L query tokens computes a similarity score against all L keys, an `L × L` matrix. That O(L²) cost is fine at 2k tokens and ruinous at 1M tokens — both in compute and in the KV-cache memory you must keep around at inference ([[llm-inference-internals]], [[long-context]]). Sparse attention restores tractability by having each query attend to only k ≪ L tokens, turning the cost toward O(L·k).

The hard part is which k. There's a long history of fixed sparse patterns — sliding windows, dilated/strided patterns, attention "sinks," global tokens (Longformer, BigBird era). They work, but they bake in a human guess about what matters, and they're usually applied post-hoc: train a dense model, then sparsify it for inference. That mismatch ("trained dense, served sparse") leaves accuracy on the table and the sparsity pattern can't learn what to keep.

Native sparse attention fixes both problems at once:

  • Trainable / learned, not fixed. The model decides per query which blocks of the past to attend to, and gradients flow through that decision, so the selection improves during pretraining.
  • Native to training, not retrofitted. Sparsity is present from token 1 of pretraining, so the model's weights adapt to it — no train/inference gap.
  • Hardware-aligned. The selection is organized in contiguous blocks (not scattered individual tokens) so a GPU can load them in coalesced chunks and keep its tensor cores busy. A sparse pattern that's mathematically efficient but causes random memory access can be slower than dense attention in practice; "hardware-aligned" is the discipline of making the FLOP savings translate into wall-clock savings.

The two flagship 2025 papers:

  1. NSA — "Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention" (Yuan et al., DeepSeek-AI + Peking University + UW, Feb 2025; ACL 2025). A three-branch design: coarse compression + fine-grained selection + a sliding window, fused by a learned gate.
  2. MoBA — "Mixture of Block Attention for Long-Context LLMs" (Lu et al., Moonshot AI + Tsinghua, Feb 2025). Applies Mixture-of-Experts routing ([[mixture-of-experts]]) to attention: chop the past into blocks, and a router picks the top-k blocks each query may attend to. Deployed in Kimi.

Why it matters

  • Long context is a headline feature, and `O(L²)` is the tax on it. Agentic workflows, whole-repo coding, and long documents all push context lengths into the hundreds of thousands of tokens. Native sparse attention is one of the few approaches that attacks that cost without abandoning the transformer or degrading quality — distinguishing it from linear-attention approximations ([[linear-attention-and-deltanet]]) and SSM hybrids ([[hybrid-attention-ssm-architectures]], [[state-space-models]]).
  • It closed the "sparse loses accuracy" gap — on the reported benchmarks. The headline claim of both papers is that native sparsity matches or exceeds full attention. NSA reports a higher average on its general benchmark suite and on LongBench than the full-attention baseline at the same scale; MoBA reports near-identical RULER@128K to full attention. (Read these as the authors' own reported results, not independent replications — see caveats.)
  • It's a *training* speedup, not just an inference trick. Because sparsity is native and the backward pass is sparse too, NSA reduces pretraining compute — earlier sparse methods only saved at inference. That changes the economics of pretraining long-context models.
  • It already shipped to production. This is not a paper-only idea: MoBA runs in Kimi; DeepSeek-V3.2 (Dec 2025) ships DSA (DeepSeek Sparse Attention, a lighter "lightning-indexer" descendant of NSA) and it's supported day-0 in vLLM ([[deepseek-architecture]]).

How it works (the real mechanics)

NSA — three branches + a gate

For each query token q_t, NSA computes three separate attention outputs over three different views of the past, then blends them with learned gates. The three "compression categories" 𝒞 = {cmp, slc, win}:

1. Compression (cmp) — coarse global view. Chop the past keys/values into blocks of length l (stride d). A small learnable MLP φ (with intra-block position encoding) compresses each block into one representative key/value. So instead of attending to thousands of raw tokens, the query attends to a handful of block summaries — cheap, captures the gist, but lossy.

2. Selection (slc) — fine-grained zoom-in. This is the clever bit. NSA reuses the compression branch's attention scores to decide which blocks deserve a closer look: p_cmp = Softmax(q_tᵀ · K̃_cmp). The blocks with the highest compression-attention scores are the important ones — so NSA keeps the top-n blocks and runs full, uncompressed attention over just those tokens. The coarse pass acts as a cheap index that tells the fine pass where to look (no separate, expensively-trained scorer needed).

3. Sliding window (win) — recent local context. Plain dense attention over the last w tokens. Local context (recent tokens, syntactic neighbors) is almost always relevant, and giving it a dedicated branch stops the selection branch from wasting its budget on the obvious recent stuff — it can specialize in long-range retrieval.

Gated fusion. The final output is a learned weighted sum:

o_t = Σ_{c ∈ {cmp, slc, win}}  g_t^c · Attn(q_t, K̃_c, Ṽ_c)

where the gates g_t^c ∈ [0,1] come from an MLP on the input + sigmoid — so the model learns, per token, how much to trust the coarse summary vs. the zoomed-in blocks vs. the local window.

Hardware alignment (the part that makes it fast for real). Two ideas:

  • Blockwise, not token-wise, selection. Selecting contiguous blocks means the GPU loads coalesced memory chunks — friendly to tensor cores. Token-by-token gather would thrash memory.
  • GQA-aware kernel. Modern models use Grouped-Query Attention ([[positional-encoding]], [[long-context]]) where several query heads share one KV head. NSA forces all heads in a GQA group to select the same blocks (it sums their importance scores: p_slc′ = Σ_h p_slc^(h)), so the custom Triton kernel loads each shared KV block once for the whole group ("group-centric data loading") instead of redundantly per head. This is what keeps arithmetic intensity (FLOPs per byte loaded) high enough to actually beat dense attention.

Reported results (NSA, authors' numbers). A 27B-total / 3B-active MoE model (30 layers, 64 heads, GQA groups of 4), pretrained on 270B tokens of 8k-length text:

  • General benchmark average: NSA 0.456 vs Full Attention 0.443.
  • LongBench average: NSA 0.469 vs Full Attention 0.437.
  • Needle-in-a-haystack @ 64k: perfect retrieval at all positions.
  • Speedups @ 64k sequence: ≈ 9.0× forward, 6.0× backward, 11.6× decoding vs full attention.

MoBA — Mixture-of-Experts, but the "experts" are blocks of the past

MoBA's framing: treat attention like MoE routing ([[mixture-of-experts]]). Split a context of length N into n blocks of size B = N/n. Each block is a candidate "expert"; a router picks the top-k blocks each query may attend to.

  • Block scoring. For query q, the score for block i is the inner product of `q` with the mean-pooled keys of that block: s_i = ⟨q, mean-pool(K[I_i])⟩. (One cheap dot product per block — far cheaper than scoring every token.)
  • Top-k gate. g_i = 1 if s_i is among the top-k block scores, else 0. The query then attends densely over the union of selected blocks: I = ⋃_{g_i>0} I_i.
  • Causality, handled carefully. Two rules keep it autoregressive: (1) future blocks are masked out of routing (s_i = −∞ for blocks ahead of the query); (2) the query's own current block is always selected, with a standard causal mask applied within that block (you can't mean-pool a partially-future block honestly, so the current block is treated specially).
  • Seamless full ⇄ sparse switching. Because MoBA never changes the attention math (it only restricts which keys/values participate), you can flip any layer to full attention by selecting all blocks — and you can do it mid-training. Moonshot uses this for a hybrid stack: e.g. 29 MoBA layers + the top 3 layers kept as full attention (the layers nearest the output benefit most from a global view).

Reported results (MoBA, authors' numbers). An 8B-class model with block size 4096, top-k = 12 (so at 1M context, sparsity 1 − (4096×12)/1M ≈ 95.3%), tested to 1M tokens:

  • RULER @ 128K: MoBA 0.7818 vs full attention 0.7849 — essentially on par.
  • Speedups: ≈ 6.5× faster at 1M tokens and ≈ 16× faster at 10M tokens vs FlashAttention ([[flash-attention]]).

The production descendant: DeepSeek-V3.2's DSA

The lineage matters. NSA's three-branch design is powerful but heavy. DeepSeek-V3.2 (Dec 2025) ships a streamlined DeepSeek Sparse Attention (DSA): a lightweight "lightning indexer" scores all preceding tokens against the query with a multi-head ReLU-gated dot product, then selects the top-k (k=2048) positions for full attention — reducing per-layer core attention from O(L²) to O(L·k). The indexer is warmed up via a dense stage during continued pretraining (so the selector learns to imitate the dense attention it replaces). DeepSeek reports roughly 2–3× faster inference and 30–40% lower memory for long contexts (vendor figures). This is the "native sparse attention, productionized and simplified" endpoint of the 2025 line of work.

Key ideas & tradeoffs

  • The unifying insight: a *cheap index* + a *precise read*. NSA's compression branch, MoBA's mean-pooled block scores, and DSA's lightning indexer are all the same move — a low-cost approximate scorer that decides where the expensive, exact attention should be spent. Get the cheap scorer right and you keep ~95% of the work while keeping ~all of the quality (on the reported tasks).
  • Block-level, not token-level, is doing the heavy lifting. Both methods select contiguous blocks. This is partly a quality choice (relevant tokens cluster) and largely a hardware choice (coalesced memory access). The hardware alignment is not a footnote — it's the difference between "fewer FLOPs" and "actually faster."
  • Native vs. post-hoc is the whole point. Retrofitting sparsity onto a dense-trained model (the older paradigm) creates a train/inference distribution gap and can't learn the pattern. Training with sparsity lets the gates/router co-adapt with the weights. This is also why these are training speedups, not just inference ones.
  • vs. linear attention & SSMs. Linear attention ([[linear-attention-and-deltanet]]) and state-space models ([[state-space-models]], [[hybrid-attention-ssm-architectures]]) get O(L) by changing the math (kernels, recurrences) — often with a quality cost on hard retrieval. Native sparse attention keeps exact softmax attention over a learned subset, betting that "exact attention over the right tokens" beats "approximate attention over all tokens." Which wins is task-dependent and still contested.
  • vs. FlashAttention. FlashAttention ([[flash-attention]]) makes dense attention memory-efficient (it's still O(L²) FLOPs, just IO-aware). Native sparse attention reduces the FLOPs themselves. They compose: NSA/MoBA kernels borrow FlashAttention's tiling discipline.
  • It's MoE-shaped (MoBA literally so). The "route each query to a few experts/blocks" framing connects this directly to [[mixture-of-experts]] — same load-balancing and routing-collapse concerns can apply.

Honest caveats & open questions

  • The "matches/beats full attention" claims are author-reported. NSA's +0.013 general / +0.032 LongBench edge and MoBA's near-parity RULER come from the papers' own evaluations at their scales and data mixes. They're credible and peer-reviewed (NSA at ACL 2025), but treat "sparse beats dense" as reported under their setup, not a settled universal law. Small benchmark deltas can flip with data, scale, or task.
  • Slight quality gaps exist and may matter. MoBA's RULER@128K is marginally below full attention (0.7818 vs 0.7849). For most tasks negligible; for adversarial long-range retrieval the gap could widen. NSA's hybrid-of-three design and MoBA's keeping top layers dense both hint that pure aggressive sparsity isn't free.
  • Speedups are workload- and length-dependent. The big multipliers (11.6× decode, 16× at 10M) are at very long contexts. At short contexts sparse attention can be neutral or slower (selection/routing overhead, kernel launch). The crossover length matters and is rarely emphasized in headlines.
  • Vendor figures (DSA's "2–3× / 30–40%") are vendor figures. DeepSeek-V3.2's production numbers are self-reported and should be read as such until independently profiled. Encouragingly, third-party stacks (vLLM) have implemented DSA, which is partial corroboration of the mechanism, not the marketing numbers.
  • Implementation is genuinely hard. Both methods rely on custom Triton/CUDA kernels; the algorithm is the easy part. A naive PyTorch gather implementation will likely be slower than dense FlashAttention. This is a real adoption barrier — the win lives in the kernel.
  • Choosing block size / top-k / window is tuning, not theory. l, n, w (NSA) and block-size / top-k / number-of-dense-layers (MoBA) are hyperparameters set empirically. There's no clean theory yet for the optimal sparsity budget at a given length and task.

How it connects to OpenAlice

OpenAlice is a systems-and-orchestration layer over frontier models, not a pretraining lab — so native sparse attention reaches us mostly as the reason long context got cheaper, and as a property of the models Alice routes to:

  • It's why our long-context paths are viable at all. Whole-repo reasoning, long agent transcripts, and the Atlas knowledge corpus all push context length up; the providers Alice uses (DeepSeek-V3.2 with DSA, Kimi/Moonshot with MoBA, and others) bake native sparse attention into their long-context offerings. When [[model-routing]] sends a long-context job somewhere, this machinery is what keeps it affordable — directly relevant to [[long-context]] and [[llm-inference-internals]].
  • It changes the cost shape of "just stuff it in the context." Because sparse attention bends O(L²) toward O(L·k), the old reflex to aggressively summarize/RAG everything ([[graphrag]], [[context-engineering]]) is partly relaxed for sparse-attention models — but only partly, and never for free (see caveats). The right call is empirical per model, which is exactly what our bench rig is for.
  • DeepSeek lineage is one we track closely. NSA → DSA sits inside the broader [[deepseek-architecture]] story (MLA, MoE, sparse attention) that several models in our routing pool descend from; understanding the attention mechanism helps explain their long-context latency/memory profiles.
  • Educationally, this is a long-context-efficiency node. For OpenAlice Academy it sits alongside [[flash-attention]] (IO-aware dense), [[linear-attention-and-deltanet]] and [[state-space-models]] (sub-quadratic by changing the math), and [[hybrid-attention-ssm-architectures]] (mix-and-match) — the four main families competing to make sequence length cheap. Native sparse attention is the "keep exact softmax, attend to a learned subset" family.

See also

  • [[attention-and-transformers]] — the O(L²) full-attention baseline this whole topic is trying to escape.
  • [[flash-attention]] — IO-aware dense attention; composes with sparse kernels, doesn't reduce FLOPs.
  • [[long-context]] · [[llm-inference-internals]] — why KV-cache and L² cost dominate long-context serving.
  • [[linear-attention-and-deltanet]] · [[state-space-models]] · [[hybrid-attention-ssm-architectures]] — sub-quadratic rivals that change the math instead of sparsifying.
  • [[mixture-of-experts]] — MoBA is MoE routing applied to blocks of the past; shared routing concerns.
  • [[deepseek-architecture]] — NSA → DSA in the DeepSeek lineage (alongside MLA + MoE).
  • [[context-engineering]] · [[graphrag]] — the orchestration-layer alternatives to long native context.