The Leap of Sparse Attention in Transformers

Part I ended on a practical objection. Exact, data-dependent zeros are theoretically the right thing — but two facts stood in the way of using them at scale. First, GPUs are throughput machines that want big dense matrix multiplies, not scattered token-level zeros. Second, computing the α-entmax threshold \(\tau\) requires iterative root-finding, where softmax gets its normalizer in one closed-form pass. For years this made sparse attention look like a loser on wall-clock time even when it won on FLOPs.

Dismantling that objection took a decade of systems work, most of it developed independently of the principled lineage. The pivotal realization — the one that reorganized the whole field — is that reducing FLOPs does not reduce runtime unless you also reduce memory traffic.

A GPU has a steep memory hierarchy: a large but slow high-bandwidth memory (HBM) and a tiny but fast on-chip SRAM. Naïve attention materializes the full \(n\times n\) score matrix \(S=QK^\top\) in HBM, reads it back to softmax it, and reads it again to multiply by \(V\) — the bottleneck is that traffic, not the arithmetic. FlashAttention (Dao et al., 2022) makes attention IO-aware: it tiles \(Q,K,V\), streams the tiles through SRAM, and computes the exact output in a single fused pass, never writing \(S\) to HBM. Memory drops from \(\mathcal O(n^2)\) to \(\mathcal O(n)\), with provably

far below the naïve algorithm’s \(\Theta(nd + n^2)\), for any SRAM size \(d \le M \le nd\). The trick that makes a single pass possible is online softmax — a running-max, running-denominator reformulation that predates FlashAttention (Milakov & Gimelshein, 2018), whose memory-saving consequence Rabe & Staats had also worked out (2021): as each new key-block arrives, keep a running maximum \(m\) and running denominator \(\ell\), and rescale the partial output \(O\) by the correction factor when the max changes:

The successors form a ladder tracking GPU generations: FlashAttention-2 parallelizes over the sequence and cuts non-matmul work (Dao, 2023); FA-3 exploits Hopper asynchrony and FP8 (Shah et al., 2024); FA-4 co-designs the pipeline for Blackwell — asynchronous MMA, a software-emulated exponential, conditional rescaling — reaching ~1.6 PFLOPs/s in BF16 (Zadouri et al., 2026). Crucially, FlashAttention already shipped a block-sparse variant “faster than any existing approximate attention method” — the door through which principled sparsity would eventually walk. Step through the online-softmax accumulation below.

Before touring the methods, it helps to draw the line that actually organizes them — a line the papers themselves often blur. Every efficient-attention method falls into one of two families, and which family it is in determines what it can and cannot achieve.

Training-free methods take a model that was pretrained with dense softmax attention and, at inference time, skip or evict part of the computation. They need no retraining, which is their great practical appeal. But it comes with a hard constraint: the model they run on assigns strictly positive weight to every token, so any sparse shortcut is an approximation of a dense distribution — and truncating a distribution that is nonzero everywhere always discards some probability mass \(\delta>0\). The output error that mass induces is at most \(2B\delta\) for values bounded by \(B\) — a tight bound — and generically nonzero whenever \(\delta\) is. Bigger budgets shrink it; no budget short of the full cache makes it provably zero.

Trainable methods instead make sparsity part of the model — present during training, so that training and inference compute the same thing. Block-native methods like NSA and MoBA learn which blocks to attend to; the entmax-native line learns attention that is sparse at the level of individual tokens, with exact zeros. Because the model is genuinely sparse, inference is not an approximation problem at all — it is support recovery, and it can be exact.

One honest wrinkle before the tour: a thin middle band retrofits trained components onto a frozen or lightly-tuned backbone. SeerAttention distills block gates from the model’s own attention maps (Gao et al., 2025); Dynamic Memory Compression retrofit-trains per-head eviction decisions (Nawrot et al., 2024); DuoAttention learns which heads deserve a full cache (Xiao et al., 2025). They buy accuracy with a little training — but the target they are trained to imitate is still the dense softmax model, so for the question that organizes this essay they sit with the training-free family, under the same ceiling.

With that map in hand: §4–§6 survey the training-free family (and where it plateaus); §7 states the approximation ceiling precisely; §8 covers trainable block-native methods; and §9 arrives at the entmax-native systems that are trainable and exact.

The training-free family’s first move is to keep the pretrained softmax model but compute only the parts of the score matrix that matter. Once attention is computed block by block, the natural efficiency move is to skip entire blocks. The dynamic-prefill line estimates, cheaply and online, which query–key blocks carry mass and computes only those. MInference (Jiang et al., 2024) classifies each head offline into one of three patterns — A-shape, Vertical-Slash, Block-Sparse — then builds per-input sparse indices online, reporting up to \(10\times\) faster prefill at 1M tokens. FlexPrefill (Lai et al., 2025) switches patterns by a JS-divergence test; XAttention (Xu et al., 2025) scores blocks by an antidiagonal sum; MMInference (Li et al., 2025) adds modality-aware permutation; SpargeAttention makes the recipe model-agnostic — a two-stage online filter over quantized attention that carries the same trick to language, image, and video models (Zhang et al., 2025).

The programmable substrate underneath is FlexAttention (Dong et al., 2024), which compiles arbitrary score_mod / mask_mod functions plus a BlockMask into a fused kernel — turning “which blocks to skip” into a first-class, compiler-supported knob (with autograd through the fused kernel; the discrete skip decision itself is not differentiated). The move from Part I’s fixed patterns (Longformer, Big Bird) to these content-estimated patterns is the same static→dynamic transition, now at block granularity and hardware-aligned.

Prefill sparsity is about the \(n\times n\) score matrix. Decoding sparsity is about a different object: the KV cache, the stored keys and values of all past tokens, which grows linearly with sequence length and batch size and quickly dominates memory bandwidth (Zhang et al., 2023). The serving substrate is PagedAttention (Kwon et al., 2023), which stores the cache as OS-style non-contiguous pages with copy-on-write sharing. (Sparsity is one axis of three, for the record: you can also store the cache smaller — KIVI and KVQuant quantize it to 2–3 bits — or share it structurally across heads and layers, from MQA/GQA/MLA to YOCO; the surveys of Shi et al. (2024) and Li et al. (2025) map those orthogonal axes. This essay stays on the sparsity axis.) On top of the paged substrate, two philosophies compete.

(a) Eviction — bounded, irreversible state

Permanently drop tokens to cap memory. H2O (Zhang et al., 2023) keeps recent tokens plus “Heavy Hitters” (high accumulated attention), framing eviction as dynamic submodular maximization: assuming the attention scheme is submodular, greedy heavy-hitter retention is near-optimal,

for assumption-dependent constants \(\varepsilon,\beta>0\) (their Theorem 4.4; \(\varepsilon\) is the paper’s \(\alpha\), renamed here to keep entmax’s \(\alpha\) sacred). Note what is and is not proven: the submodularity is itself an assumption, the bound concerns a surrogate utility \(f\), and accumulated attention is a proxy for future attention nobody can see — caveats most citations of H2O quietly drop. StreamingLLM (Xiao et al., 2024) found that a few initial tokens act as attention sinks — they soak up the excess mass softmax is forced to assign somewhere (Part I’s pressure valve) — so keeping the first few tokens plus a recent window preserves quality at unbounded length. TOVA (Oren et al., 2024) views decoders as “multi-state RNNs” and drops the single lowest-attention token per step; FastGen picks the cheapest adequate eviction policy per head (Ge et al., 2024); and keys with a small \(\ell_2\)-norm turn out to attract high attention, so you evict the large-norm ones (Devoto et al., 2024). Notice that these importance proxies — accumulated attention, last-query attention, per-head structure, key norm — are mutually inconsistent. That they all “work” says the benchmarks are forgiving, not that token importance is solved.

Eviction’s deeper trouble is what it does to the model class. Dropping state turns the transformer into a bounded-memory model, and bounded-memory models provably cannot copy or retrieve beyond their state size — the very theorem that separates transformers from state-space models (Jelassi et al., 2024). And the failure shows up where the theory says it should: eviction rests on a stability assumption — that yesterday’s importance predicts tomorrow’s — which breaks badly on shifted or multi-query workloads (Feng et al., 2025). (To be honest about the state of theory: nobody has proved a clean impossibility theorem for eviction — the case is folklore plus mounting empirics.) The retrofit-trained corner does better: Dynamic Memory Compression teaches the model itself to decide, per head, whether to append or merge each incoming KV entry (Nawrot et al., 2024), and its successor spends the freed memory on longer reasoning at the same compute (Łańcucki et al., 2025) — a preview of the trainable family’s answer.

(b) Selection — full state, chosen per query

Keep everything, but load only what this query needs. Quest (Tang et al., 2024) stores per-page coordinatewise min/max of the keys, \(m^p\) and \(M^p\), and scores a page by an upper bound on the best attention it could contain:

then loads only the top-\(K\) pages. The bound guarantees no page is skipped for scoring too low — an inflated estimate can only waste budget, never hide a page from the estimator. It is not a recall guarantee, though: under a top-\(K\) rule, other pages’ inflated bounds can still crowd out the true best page. (A threshold rule on the same bounds would give the no-miss guarantee — a point EntmaxKV later makes precise; §7.) SnapKV (Li et al., 2024) votes with an end-of-prompt window; PyramidKV (Cai et al., 2024) allocates non-uniform per-layer budgets — more where lower layers scatter, less where upper layers focus; Loki (Singhania et al., 2024) scores every key against the current query in a PCA subspace; ShadowKV (Sun et al., 2025) keeps low-rank pre-RoPE keys on the GPU, offloads the values to CPU, and re-selects chunks each step.

A recurring finding sharpens the picture: token importance is query-dependent. Query-agnostic scores — accumulated attention, key norm, PCA energy — are cheap but fail on retrieval, where “the criticality of a token highly depends on the query” (Tang et al., 2024). The most robust methods therefore score each key against the current query, and increasingly replace a fixed budget \(k\) with an adaptive one.

Instead of “always keep \(k\) tokens,” adaptive-budget methods keep the smallest set whose cumulative estimated mass exceeds a threshold — a top-\(p\) rule on attention:

so easy queries spend little and hard queries spend more. Twilight (Lin et al., 2025), Tactic (Zhu et al., 2025), and Double-P (Ni et al., 2026) all make the budget data-dependent.

Two further axes complete the training-free toolbox. Budgets can live at the level of heads: a small set of “retrieval heads” does the long-range lookups (Wu et al., 2024), so DuoAttention hands those a full cache and starves the rest down to sinks-plus-recency (Xiao et al., 2025). And selection itself can be swapped for sampling: MagicPIG observes that top-\(k\) is a biased estimator of the attention output — it fails precisely on aggregation-style queries whose mass is spread wide — and instead samples keys with LSH to get a near-unbiased estimate (Chen et al., 2025). If the adaptive rule — “keep the smallest set covering mass \(p\)” — sounds familiar, it should: it is a thresholding heuristic reaching for exactly what α-entmax computes exactly. Which is the point of the next section.

Now make the §3 warning quantitative — this is the hinge of the whole part. Every training-free method in §4–§6, however clever its scoring, is approximating a dense softmax distribution with a truncated one. Write \(\delta\) for the attention mass the truncation discards. For softmax, \(\delta>0\) under every strict subset of the cache, and the output error it induces obeys \(\lVert o_{\mathcal C}-o_{\text{full}}\rVert \le 2B\delta\) for values bounded by \(B\) — a tight bound, generically nonzero whenever \(\delta\) is (EntmaxKV’s Proposition 1). A bigger budget shrinks the floor; nothing eliminates it. That is the ceiling over the entire training-free family. EntmaxKV (Duarte et al., 2026) reframes the problem to remove it: with α-entmax, most keys have exactly zero weight, so an entmax decoder does not need to approximate anything (Proposition 2) —

Once the cache \(\mathcal C\) contains the (small) nonzero support, the decoder’s output is exactly equal to full-cache attention. The task changes from lossy approximation to lossless support recovery: find the handful of tokens with nonzero weight, and you are done — no budget to tune, no discarded tail. In paged Triton kernels this runs at up to \(5.4\times\) over full-cache attention at 1M context; and the same paper shows that threshold-based page bounds admit no false negatives (its Proposition 4) — the recall guarantee Quest’s top-\(K\) rule cannot offer. Compare the two regimes below.

Cross into the second family. Instead of approximating a frozen dense model, train the sparsity in — so training and inference compute the same sparse operation and the kernel is co-designed with the pattern. These methods escape the §7 ceiling in principle, because the model they run is genuinely sparse. Most of them, though, are sparse at block granularity (which suits GPUs) rather than at the level of individual tokens. The idea has an ancestor the new wave rarely cites — Landmark Attention trained block retrieval into the model back in 2023, via landmark tokens and a grouped softmax (Mohtashami & Jaggi, 2023) — but the moment the mainstream noticed was Native Sparse Attention (NSA) (Yuan et al., 2025), DeepSeek’s ACL 2025 Best-Paper: three branches per query — a coarse compressed stream, a selected set of blocks, and a local sliding window — combined by learned gates, with a block layout aligned to GPU tensor cores, pretrained from scratch at 27B and matching or beating full attention on their benchmarks.

MoBA (Lu et al., 2025) makes the “attention sparsity is routing” analogy literal: it treats KV blocks as experts and applies Mixture-of-Experts top-\(k\) gating, scoring each block by the affinity of the query to the block’s mean key

explicitly adopting a “less structure” principle: let the model decide where to attend rather than imposing a fixed pattern. InfLLM-V2 (Zhao et al., 2025) switches smoothly between dense and sparse while reusing the dense-attention parameters — no extra modules, unlike NSA — preserving the pretrain-short/finetune-long workflow; NOSA (Huang et al., 2025) splits the selection into query-aware and query-agnostic parts with a proven locality lower bound, so the CPU↔GPU traffic of an offloaded cache stays bounded. The wave keeps widening: SeerAttention-R adapts self-distilled gates to long reasoning decodes (Gao et al., 2025); HSA learns chunk-level retrieval inside a recurrent hybrid and reads 64M-token passkeys after training at 4K (Hu et al., 2025); FSA re-engineers NSA’s kernel for the small GQA groups where the original layout underperforms (Yan et al., 2025); MTraining takes dynamic sparse attention distributed, training at 512K context (Li et al., 2025). Sparsity has become an architectural primitive, not a post-hoc filter — the same destination Part I reached from the theory side.

And it shipped. DeepSeek-V3.2 put trained fine-grained sparse attention into a frontier production model — a lightning indexer scores tokens in FP8, a top-\(k\) selector feeds the attention — and the cost drop headlined the release (DeepSeek-AI, 2025); GLM-5 then adopted DSA wholesale (GLM-5 Team, 2026), and MoBA serves Kimi’s long-context traffic. The most telling arc is MiniMax’s: hybrid-linear at 456B (MiniMax, 2025), then back to full attention in M2 when the hybrid degraded multi-hop reasoning at scale, then trained block-sparse attention shipped in M3 (Lai et al., 2026) — linear → full → sparse. Meanwhile Kimi’s 1T-parameter K2 stayed dense-full (Kimi Team, 2025) even as its research line probes linear hybrids (Kimi Linear, 2025), and the quiet incumbents — sliding windows in Mistral (Jiang et al., 2023) and Gemma (Gemma Team, 2025), gpt-oss’s banded-window-plus-learned-sink layers (OpenAI, 2025) — have shipped static sparsity all along. Nobody agrees on the attention layer anymore; what is no longer in dispute is that sparsity can be trained in at production scale.

One thing these block-native methods do not quite give you is exactness. They learn which blocks to keep, but inside a kept block the attention is still a dense softmax, and a dropped block is still an approximation with \(\delta>0\). Closing that last gap — trainable sparsity that is exact at the token level — is where our own line comes in.

This is the corner of the design space that is both trainable and token-exact — and, as far as the two-family map goes, the only one. α-entmax is trained into the model (Part I), so its zeros are real, not approximated; the job that remains is purely a systems one. And it is a genuinely hard one, because α-entmax breaks the two assumptions FlashAttention is built on: its normalizer is not a closed-form reduction, and its zeros are unstructured (per-token, data-dependent), not neatly block-aligned. This section opens up the kernels — AdaSplash and AdaSplash‑2 — and shows exactly how each obstacle is turned into a speedup rather than a tax.

The bottleneck: a normalizer with no closed form

Softmax gets its normalizer for free — \(\tau=\log\sum_j e^{s_j}\) is one streaming reduction, computed alongside the running max in FlashAttention’s online‑softmax. α-entmax’s threshold is the root of

which has no closed form for general \(\alpha\). Every query row needs its own \(\tau\), found by iterative root‑finding over that row’s scores. Historically this is what kept sparse attention off the FlashAttention Pareto frontier: the inner loop is not a reduction but a solve. The whole engineering story is about making that solve — and the sparsity it unlocks — nearly free.

AdaSplash: a safeguarded Halley–bisection solve

AdaSplash’s _get_tau kernel keeps \(f\) monotone and brackets the root in \([\tau_{\text{lo}}, \tau_{\text{hi}}]\), then takes Halley steps that fall back to bisection whenever a step would leave the bracket. Because a single tiled pass over the scores can accumulate \(f,f',f''\) at once (three running moments), each iteration is cheap, and the cubic convergence of Halley cuts the iteration count by roughly \(7\times\) versus plain bisection — about \(3\) iterations where bisection needs \(23\) at the same precision.

The solver runs inside the tiled Q×K loop (\(B_r{=}64,\,B_c{=}16\) for the \(\tau\) phase in the released kernels), so it reuses scores already staged in SRAM rather than re‑reading them from HBM.

AdaSplash‑2: a histogram that brackets τ before you solve

AdaSplash‑2’s insight is to spend a streaming pass — right after the running‑max pass — building a coarse histogram of the scores in SRAM, then read provable bounds on \(\tau\) straight off the bin counts, so the root‑finder starts from a tight bracket and typically converges in one or two steps. The figure shows the forward kernel: as each key tile \(K_j\) streams through, the score tile \(Z_{ij}\) updates the per‑query histogram \(\mathcal H_{ij}\); a descending sweep over bins gives \(\tau_h \le \tau^\star\), which is stored and handed to the solver.

Fig. 5. The AdaSplash‑2 forward pass. Query blocks \(Q_i\) (grid loop) and key blocks \(K_j\) (inner loop) stream through SRAM; each score tile \(Z_{ij}\) updates a compact histogram \(\mathcal H_{ij}\) held on‑chip. To keep it nearly free, the bin counts are bit‑packed into a single machine word — \(B\in\{4,8,16\}\) bins in a uint64, \(64/B\) bits per counter, with the per‑bin capacity \(2^{64/B}-1\) budgeted explicitly against the tile size. A descending sweep over bins accumulates the prefix moments \(S_0,S_1,S_2\) and stops at the first bin whose inclusion pushes \(f(\tau)\) positive — for \(\alpha=1.5\), where \(S_0\tau^2-2S_1\tau+S_2 \ge 1\) — then solves that bin’s quadratic exactly; with left‑edge binning this yields a lower bound \(\tau_h \le \tau^\star\) (so the estimated support always contains the true one) — a tight initialization that needs no dense intermediates.

Skipping the zeros: from boolean masks to bit‑packing

A threshold is only half the win; the other half is not computing the blocks that end up all‑zero. AdaSplash marks each score tile (\(16\times 16\) at output granularity in the released kernels) with a boolean bmask — a block is skippable when every score in it falls below \(\tau\) (a row‑wise OR reduction) — then compute_bidxs_and_cubcounts turns that into a list of surviving block indices, so the output kernel iterates only over good_nblocks per query.

AdaSplash‑2 shrinks the mask itself. Instead of one byte per block it packs one bit per key block, 32 blocks to an int32 (a 32× smaller mask), building it on the fly as bmask <<= 1; bmask += (Σ qk_mask > 0) and flushing every 32 blocks. The output kernel then walks only the set bits using the GPU’s native find‑next‑set instruction (PTX fns), jumping straight from one nonzero block to the next with no per‑block branch. Small mask, branch‑free traversal, less HBM traffic.

The backward pass is sparse too — and that is where it pays

Training spends more time in the backward pass than the forward, so this is where exactness has to earn its keep. It does, because the α-entmax Jacobian is itself sparse: for \(p=\alpha\text{-entmax}(s)\),

So gradients touch only the surviving tokens. AdaSplash splits the backward into separate kernels for \(dQ\) and for \(dK,dV\), plus a small pre‑pass — the entmax analogue of FlashAttention’s \(D=\mathrm{rowsum}(\mathrm dO\odot O)\), which here needs a stored second output moment \(O^{(2)}\). It saves each row’s \(\tau\) and recomputes scores and probabilities from it rather than storing the \(n\times n\) matrix, and reuses the very same block mask to skip null blocks. AdaSplash‑2 goes further and also uses the transposed block mask \(M^\top\) so the \(dK,dV\) kernel — which must loop over query blocks per key block — likewise iterates only over active blocks. At high sparsity this turns the backward pass from the dominant cost into an order‑of‑magnitude speedup; end to end, AdaSplash‑2 matches FlashAttention‑2’s training step time at moderate block sparsity (≳60%) and passes \(2\times\) beyond it.

Two more systems close the loop. DashAttention (Huang et al., 2026) lifts entmax one level up: an α‑entmax router selects a variable number of KV blocks per query — where NSA and InfLLM‑V2 fix a top‑\(k\), assuming every query needs the same amount of context — with the whole hierarchy differentiable end to end and fused kernels up to \(3.3\times\) faster than FlashAttention‑3 at inference. And EntmaxKV (Duarte et al., 2026) is the decode‑time answer to §7’s ceiling — exact support recovery (\(\delta=0\), not \(\delta>0\)) in paged Triton kernels, up to \(5.4\times\) over full‑cache entmax attention at 1M tokens. Together with AdaSplash‑2 — an ICML 2026 paper — they show that exact, adaptive, trainable sparsity is now competitive with the most optimized dense kernels: you do not have to choose between exactness and speed.

Efficiency claims are easy to overstate, so it is worth ending on discipline. The Sparse Frontier (Nawrot et al., 2025) evaluates training-free sparse attention across a four-axis taxonomy (unit of sparsification, importance estimation, budget allocation, cache management) and finds it genuinely shifts the accuracy–efficiency Pareto frontier — larger-but-sparse beats smaller-but-dense at equal cost — while warning that “fixed-budget methods in production are suboptimal” and that safe sparsity levels are task-dependent: budgets that are harmless for retrieval break aggregation and multi-hop reasoning.

Three more doses of discipline. SCBench stress-tests the KV lifecycle — multi-turn, shared-context serving — and finds that methods holding sub-\(\mathcal O(n)\) memory collapse there, while \(\mathcal O(n)\)-memory dynamic sparsity holds up (Li et al., 2025). Passkey-style benchmarks sit in the easiest quadrant of the difficulty map — low dispersion, low scope — so headline needle numbers systematically flatter every method on this page (Goldman et al., 2024). And our own family has an open front to declare: as of mid-2026, nobody has pretrained a \(>\)1B-parameter entmax LLM — the entmax-native results above are academic-budget scale, a gap to state rather than paper over. The field is not waiting: at ICML 2026 alone, learned and adaptive sparsity is everywhere — online sparsity prediction, feature-space alignment of sparse to full attention, test-time adaptive sparsity ratios, cross-head unified selection for reasoning (Yang et al., 2026), sparse attention inside diffusion LMs. The two-family map holds; the territory inside it is redrawn every conference cycle. The live disagreements that will shape the next few years:

Read down the right column and a single position emerges: sparsity should be a property of the model, trained in, exact, and co-designed with the kernel. That is precisely the object Part I built from sparsemax and α-entmax. The efficiency era did not replace the principled lineage — it caught up to it.

One table for the whole zoo, grouped by family. Read across for what each method does; the column that matters most is the last technical one — approximates softmax (a permanent error floor) versus exact (δ = 0). Scroll the table sideways to see every column.