Natively Trainable Sparse Attention

There is a familiar shape to sparse attention results: a paper trains a model with full attention, applies a sparsity pattern at inference, reports that perplexity barely moved, and claims a large theoretical speedup. Two things usually go wrong afterwards. The accuracy loss that "barely moved" on perplexity shows up sharply on tasks that need the dropped tokens, and the theoretical speedup fails to materialise because the pattern's memory accesses are scattered in a way GPUs punish.

DeepSeek's Native Sparse Attention is a direct response to both, and its argument is that sparsity has to be present during pretraining and has to be designed against the hardware, not merely against FLOP counts (DeepSeek-AI, 2025, Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention, arXiv:2502.11089).

Three branches, one gate

NSA replaces full attention with three parallel paths, each answering a different need, combined by a learned gate:

• Compression. Blocks of past tokens are pooled into coarse block-level representations, so every query can attend to a summary of the entire history at low cost. This is the branch that preserves global awareness.
• Selection. A small number of blocks are selected per query for full-resolution attention, using scores derived from the compression branch. This is the branch that recovers precision, and its block granularity is what makes it fast.
• Sliding window. A fixed local window is always attended, so recent context is never dropped (see sliding window attention).

The gate is a learned per-query mixture over the three outputs, which is what makes the whole thing trainable end to end: the selection scores flow gradients through the compression branch, so the model learns what to select rather than having a heuristic imposed on it.

Why "hardware-aligned" is doing real work

Token-level sparsity — pick the top-k individual keys per query — is the natural formulation and the wrong one for a GPU. Gathering scattered keys produces uncoalesced memory reads and leaves tensor cores idle, so a pattern that removes 90% of FLOPs may remove almost none of the wall-clock time.

NSA selects at block granularity instead, so each selected unit is a contiguous run of keys and values that loads as one tile into shared memory (see memory coalescing and shared memory and tiling). The design target is arithmetic intensity: enough compute per byte moved to keep the units busy. The paper reports substantial speedups over full attention on 64k-length sequences across decoding, forward propagation and backward propagation — the backward pass mattering precisely because this is a training-time method, and most inference-only sparse schemes have no efficient backward at all.

Native versus post-hoc sparsity

The distinction is the point of the paper. Post-hoc sparsity applies a pattern to a model that learned to rely on full attention; the model's representations were shaped by information it can no longer see, and the mismatch is a permanent tax. Native sparsity trains the model under the pattern it will be served with, so it learns to route the information it needs through the paths that remain. DeepSeek report that a model pretrained with NSA maintains or exceeds full-attention models across general benchmarks, long-context tasks, and instruction-based reasoning. That direction — sparse matching or beating dense rather than approaching it from below — is only available to native methods.

When it breaks

• It is a pretraining commitment. You cannot adopt NSA for an existing checkpoint without retraining or extensive continued pretraining, so the decision is made once, early, by whoever owns the pretraining run.
• Comparisons are hard to trust. Every sparse-attention result compares against a full-attention baseline the authors trained; matched-compute, matched-data comparisons across labs barely exist. Independent replication of "sparse beats dense" claims is thin.
• Three branches mean three sets of hyperparameters. Block size, compression ratio, number of selected blocks, and window size all interact, and the published values are tuned for one model scale and one sequence-length regime.
• Gains concentrate at long context. At a few thousand tokens the three branches are overhead, not savings; the method exists for the 32k-and-beyond regime.
• It does not remove the KV cache. Sparse attention reduces the compute spent reading the cache, not the memory holding it — the compression branch adds a small amount of its own state. Cache size remains a separate problem needing separate tools (see KV cache eviction and compression).