Attention Alternatives: Sparse, Linear, and Recurrent

The Transformer’s Three Attention Patterns ends with a warning: attention’s cost is quadratic in the sequence length. The KV Cache shows the other half of the bill, a cache that grows with every generated token and is read again on every step. Both posts take those costs as given and manage them. This post changes the mechanism instead.

There are three families of alternatives, and they are not versions of one idea. Sparse attention computes only some query-key pairs; its learned forms keep every token in the cache. Linear attention drops the softmax, which lets the past be folded into a fixed-size state. State space models reach the same kind of state from control theory. Each is derived below from the algebra that makes it work and checked in a short script. Then the configuration files of thirteen released models show which of them shipped.

Table of contents

First, be precise about what is expensive

“Attention is quadratic” is true and too vague to design against. There are two separate costs, they dominate at different times, and an alternative can remove one while leaving the other.

Cost 1: prefill compute. Processing a prompt of $n$ tokens computes the score matrix $QK^\top$, which is $n \times n$ per head. Multiplying an $a \times b$ matrix by a $b \times c$ one costs $2abc$ floating-point operations (a multiply and an add per term), so per head:

Cost 2: the cache at decode time. Once generation starts, the model processes one token per step and the quadratic term stops mattering. What matters is the KV cache: every token seen so far left a key and a value in every layer, and all of them are read again on every step. The cache size is a product of the model’s shape:

D = 128                                    # head dimension
LAYERS, KV_HEADS, BYTES = 32, 8, 2         # Llama-3-8B shape, BF16
LENGTHS = (4_096, 32_768, 131_072, 1_048_576)


def prefill_flops(n, d=D):
    """QK^T and (scores)V, each 2*n*n*d FLOPs (a multiply and an add per term)."""
    return 2 * n * n * d + 2 * n * n * d


def kv_cache_bytes(n):
    """A key and a value per token, per layer, per KV head."""
    return 2 * LAYERS * KV_HEADS * D * BYTES * n


def state_bytes():
    """Linear attention: one d x d state per KV head per layer, whatever n is."""
    return LAYERS * KV_HEADS * D * D * BYTES

Full script: bills.py

prefill FLOPs per head, d = 128
  n =     4,096         8.6 GFLOPs
  n =    32,768       549.8 GFLOPs
  n =   131,072     8,796.1 GFLOPs
  32x the tokens costs 1,024x the work

KV cache per token: 128 KiB
    context   KV cache  linear-attention state
      4,096    0.54 GB                  8.4 MB
     32,768    4.29 GB                  8.4 MB
    131,072   17.18 GB                  8.4 MB
  1,048,576  137.44 GB                  8.4 MB
20 sequences of 131,072 tokens: 344 GB = 4.3 H100s of 80 GB

Prefill grows with the square of the prompt: 32 times the tokens costs 1,024 times the work. The cache grows linearly, but per sequence, and twenty conversations of 128K tokens need 344 GB, more than four 80 GB H100s, before any weights are loaded. Because decoding is limited by memory reads rather than arithmetic (The KV Cache shows why), every one of those bytes is read again for each generated token. The last column is the linear-attention state derived below: 8.4 MB, whatever the length.

The two need different fixes. A method that makes prefill cheaper may leave the cache as it was, and a method that shrinks the cache to a constant may make training slower. The useful question about any alternative is which bill it pays, and with what.

The baseline that is not an alternative: FlashAttention

Standard attention writes the full $n \times n$ score matrix to GPU memory, 2.1 GB per head at 32K tokens in BF16 (bills.py prints it), and reads it back twice. The arithmetic was never the bottleneck; the memory traffic was. FlashAttention (Dao et al., 2022) is “an IO-aware exact attention algorithm that uses tiling to reduce the number of memory reads/writes between GPU high bandwidth memory (HBM) and GPU on-chip SRAM.” It computes the softmax block by block, so the score matrix never exists in full, and its output equals standard attention’s up to rounding. FlashAttention derives it; FlashAttention-2 (Dao, 2023) reaches 50–73% of an A100’s peak.

FlashAttention changes the memory and the constant, not the exponent: FLOPs are still $4n^2d$ per head. So the quadratic wall remains, further out, and any alternative that claims a speedup has to beat this kernel. A method with better asymptotics can still be slower at the lengths people run, because it gives up the dense matrix multiplications GPUs are built for.

Way one: attend to less

The first family keeps softmax attention exactly as it is and computes only some of the pairs. The motivation is that a trained model’s attention is concentrated: a query puts most of its weight on a small share of the keys, so most of the $n^2$ products contribute little. The design question is which pairs to keep.

Fixed patterns

The 2020 generation chose the pattern in advance.

Longformer (Beltagy et al., 2020) combines a sliding window, in which each token attends to $w/2$ neighbours on each side at a cost of $O(n \cdot w)$, with global attention on a few task-chosen tokens (the question in question answering, the classification token otherwise) that attend to everything and are attended to by everything. Because the global set does not grow with $n$, the total stays linear. A dilated window, with gaps that widen the reach at no extra cost, helped its character-level model; for the pretrained model the paper reports that dilation on a few heads “hurt performance”.

BigBird (Zaheer et al., 2020) uses a window, global tokens and random keys, and proves that it “is a universal approximator of sequence functions and is Turing complete, thereby preserving these properties of the quadratic, full attention model.” The proof needs the pattern to contain a star graph, which is what the global tokens provide. The same paper also proves the limit of the family, under a standard complexity assumption: there is a task that one layer of full attention solves but that needs $\tilde{\Omega}(n)$ layers for any sparse attention with $\tilde{O}(n)$ edges. The authors call it “no free lunch”. Sparse attention pays for its savings in depth.

Mistral 7B (Jiang et al., 2023) shipped the sliding window with $W = 4096$ in all 32 layers, as its config states. A token beyond the window is not lost entirely, since “after $k$ attention layers, information can move forward by up to $k \times W$ tokens”, but the span this gives, about 131K tokens, is an upper bound on propagation, not a measured ability to retrieve. The cache is where the window pays: no key is read again after $W$ steps, so the cache becomes a ring buffer of $W$ entries.

sliding window W = 4,096: cache capped at W tokens
  at n = 32,768: cache 8x smaller, 23% of the causal pairs computed; 32 layers reach 131,072 tokens

At 32K tokens the window computes 23% of the causal pairs and keeps an 8× smaller cache, the figure the paper reports “without impacting the model quality”. That quality claim comes with no measurement: the model in the paper’s Table 1 has a context length of 8,192, and the paper evaluates nothing at 32K.

Attention sinks, and a lesson about softmax

Running a window by evicting the oldest tokens has a failure worth its own subsection. Quality collapses as soon as the very first tokens leave the cache, even though they rarely matter for the meaning. Xiao et al. (2024) found the cause in the softmax. Its weights must sum to one (The Residual Stream derives it), so a head that finds nothing relevant still has to put its attention somewhere. Models learn to put it on the first positions, which every query can see. The authors call these positions attention sinks. Long Context, and Where It Breaks measured one in Qwen2.5-1.5B: averaged over its 28 layers, 30.5% of all attention lands on the first token, where an even split would give it 0.29%.

The fix keeps the first few tokens’ keys and values pinned beside the rolling window. With it, the paper reports Llama-2, MPT, Falcon and Pythia modeling “up to 4 million tokens and more” without fine-tuning, with “up to 22.2x speedup” over recomputing a sliding window.

The idea then became part of the architecture. OpenAI’s gpt-oss alternates windowed and full layers, and its config shows how small the window is:

sliding windows
Mistral-7B-v0.1        sliding_window 4096 in all 32 layers
gpt-oss-20b            12 sliding (128 tokens) and 12 full layers, alternating: ['sliding_attention', 'full_attention', 'sliding_attention', 'full_attention']

Each head also has a learned sink: in the model card’s words, “a learned bias in the denominator of the softmax … which enables the attention mechanism to pay no attention to any tokens.” The sink is a weight in each layer (self_attn.sinks), not a token in the cache.

Learned sparsity

The 2025 generation learned the pattern instead of designing it.

Native Sparse Attention (Yuan et al., DeepSeek, 2025) runs three branches per query and mixes them with learned gates: compression summarizes blocks of 32 tokens through a small network, selection reads 16 blocks of 64 tokens in full (13 chosen by score, plus the first block and the 2 most recent), and a sliding window covers the last 512 tokens. “Native” means the sparsity is present during pretraining, so the model learns around its own access pattern. At 64K tokens the paper measures kernels “up to 9.0x forward and 6.0x backward” faster than FlashAttention-2 on A100s. Its 11.6× for decoding is an expected speedup computed from the memory each step reads, not a measured time.

MoBA (Lu et al., Moonshot, 2025) routes each query to a few blocks of the context, the way a mixture of experts routes a token to a few experts. Its stated principle is “less structure”: “allowing the model to determine where to attend autonomously, rather than introducing predefined biases”. It can also switch back to full attention, so one set of weights serves both.

DeepSeek-V3.2-Exp (2025) shipped learned sparsity at frontier scale. A small lightning indexer scores every earlier token for each query, and attention reads only the top 2,048:

learned sparse attention
DeepSeek-V3.2-Exp      indexer picks top 2,048 earlier tokens per query, in all 61 layers

That takes the main attention from $O(L^2)$ to $O(Lk)$ with $k = 2048$. The indexer still scores every pair, so it is still $O(L^2)$, but in DeepSeek’s words it “requires much less computation” than the attention it replaces. DeepSeek cut its API prices by “50%+” at the launch, and vLLM and SGLang announced support the same day.

One property separates learned sparsity from the next two families: every token stays in the cache. NSA, MoBA and DeepSeek’s indexer choose what to read; nothing is discarded when a token is written, so any token can still be retrieved exactly if the selector picks it. Fixed windows are different: Mistral’s ring buffer and StreamingLLM’s eviction do drop tokens, and what they drop is gone.

Way two: drop the softmax

The second family attacks the exponent, and the argument starts by showing that the softmax is the only obstacle.

Attention as a similarity kernel

Katharopoulos et al.’s Transformers are RNNs (2020) writes attention with an arbitrary similarity function:

Softmax attention is the case $\operatorname{sim}(q, k) = \exp\!\left(q^\top k / \sqrt{d}\right)$. The only property the formula needs is that $\operatorname{sim}$ be non-negative, so that the weights form a distribution. Choose a similarity that factors through a feature map $\phi$, $\operatorname{sim}(q, k) = \phi(q)^\top \phi(k)$, and the formula becomes

The sums no longer depend on $i$. The same $\sum_j \phi(K_j) V_j^\top$ serves every query, so it is computed once.

The one algebraic move

In matrix form this is a change of parentheses:

Matrix multiplication is associative, so the two sides are equal, but their intermediates differ. On the left, $\phi(Q)\phi(K)^\top$ is $n \times n$, the score matrix. On the right, $\phi(K)^\top V$ is $d \times d$, a matrix whose size does not depend on the sequence. The paper’s feature map is $\phi(x) = \operatorname{elu}(x) + 1$, positive everywhere; it prefers elu to relu “to avoid setting the gradients to 0 when x is negative.” Both orders, in code:

def phi(x):
    """elu(x) + 1, the feature map of Katharopoulos et al.: positive everywhere."""
    return np.where(x > 0, x + 1, np.exp(np.minimum(x, 0)))


def quadratic(Q, K, V, causal):
    A = phi(Q) @ phi(K).T                          # n x n similarities
    if causal:
        A = np.tril(A)
    return (A @ V) / A.sum(1, keepdims=True)


def linear(Q, K, V):
    S = phi(K).T @ V                               # d x d, shared by every query
    z = phi(K).sum(0)                              # d
    return (phi(Q) @ S) / (phi(Q) @ z)[:, None]

Full script: linear_attention.py

n = 512, d = 64
non-causal, quadratic vs linear:   max difference 2.8e-16
causal, quadratic vs recurrent:    max difference 8.9e-16
rank of exp(QK^T / sqrt d): 512 of 512
rank of phi(Q) phi(K)^T:    64 of 512

The outputs agree to rounding (the second line checks the causal version, which comes next). The last two lines show why softmax forbids the move. $\exp(q^\top k)$ factors through no finite feature map: its $512 \times 512$ similarity matrix has full rank, while any $\phi(Q)\phi(K)^\top$ has rank at most $d = 64$. Remove the softmax and the reordering is legal; that is all “linear attention” means.

Both orders cost two matrix multiplications, $4n^2d$ FLOPs on the left and $4nd^2$ on the right, so the saving is

At $d = 128$ the two break even at 128 tokens, and below that the linear order is slower. FLOPs are a prediction, so order_timing.py times both orders on the GPU of an Apple M4 laptop, with nothing else running:

for n in (32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384):
    Q, K, V = (torch.randn(n, d, device=device) for _ in range(3))
    quad = best_of(lambda: (Q @ K.T) @ V)
    lin = best_of(lambda: Q @ (K.T @ V))
    print(f"{n:>7,} {quad * 1e3:>8.3f}ms {lin * 1e3:>8.3f}ms {quad / lin:>8.1f}x {n / d:>7.2f}x")

Full script: order_timing.py

device mps, float32, d = 128, best of 20 runs
      n    (QK^T)V   Q(K^T V)  measured  counted
     32    0.181ms    0.223ms      0.8x    0.25x
     64    0.180ms    0.186ms      1.0x    0.50x
    128    0.199ms    0.188ms      1.1x    1.00x
    256    0.227ms    0.200ms      1.1x    2.00x
    512    0.258ms    0.223ms      1.2x    4.00x
  1,024    0.441ms    0.233ms      1.9x    8.00x
  2,048    0.993ms    0.279ms      3.6x   16.00x
  4,096    3.006ms    0.373ms      8.1x   32.00x
  8,192   11.809ms    0.467ms     25.3x   64.00x
 16,384   51.872ms    0.688ms     75.4x  128.00x

The measurement cannot locate the break-even. Below 512 tokens both orders take about 0.2 ms, the fixed cost of launching work on the GPU, so the ratio sits between 0.8 and 1.2: consistent with the count, but not a test of it, and the counted 4× at 512 tokens does not appear. Above that the gap grows with $n$ as predicted, reaching 75× at 16K tokens against 128× counted. The baseline is a plain, unfused $(QK^\top)V$ with no softmax or mask, not FlashAttention, and this is the non-causal case. A causal model needs a separate prefix sum for every query, which is where the next view comes in.

The same model is also an RNN

Make it causal: token $i$ attends only to tokens $1 \dots i$, so the sums become prefix sums, and a prefix sum can be kept as a running total:

That is a recurrent network (Sequences Before Attention builds one by hand). It reads one token, updates a state of fixed size, emits one output, and keeps nothing else:

def recurrent(Q, K, V):
    s, z = np.zeros((d, d)), np.zeros(d)           # the whole memory
    out = np.empty_like(V)
    for i in range(len(Q)):
        k = phi(K[i])
        s += np.outer(k, V[i])                     # write token i into the state
        z += k
        q = phi(Q[i])
        out[i] = (q @ s) / (q @ z)                 # read with query i
    return out

Its outputs match the quadratic form with a causal mask, to $9 \times 10^{-16}$ (the second line of the output above).

Hence the paper’s title: a causal Transformer with linear attention is an RNN. The paper reports generation “up to 4000x faster” on very long sequences (image generation, where a sequence is every pixel). The state $s_i$ is $d \times d$ per head and never grows. It is built from keys and values alone, so heads that share keys and values share one state, and for the Llama-3-8B shape above it is $32 \times 8 \times 128 \times 128$ numbers, the 8.4 MB in the last column of bills.py’s table. Constant memory per sequence, constant work per token, and no cache to page or evict. The problems Paged Attention and SGLang and RadixAttention solve shrink to whatever attention layers remain, and sharing a prefix changes form: a recurrent state has to be saved at the end of the prefix, since it cannot be cut at an arbitrary token.

What it costs: the recall wall

The price is the same fixed-size state. A KV cache is lossless: each token’s key and value are stored separately, so a query at step 10,000 can retrieve token 3 exactly. A $d \times d$ state stores the sum of every token’s outer product $v k^\top$. With up to $d$ nearly orthogonal keys a query can still pull its own value out of the sum; beyond that the keys interfere.

recall.py measures this directly, with no training. It writes $n$ random key-value pairs into three memories and asks each memory for every value back, using the stored key as the query. The memories are a KV cache read by softmax attention, the linear-attention state, and the delta rule described in the next subsection:

def read_cache(keys, values, queries, scale=16.0):
    w = np.exp(scale * queries @ keys.T)                     # softmax over every stored key
    return (w / w.sum(1, keepdims=True)) @ values


def write_linear(keys, values):
    return values.T @ keys                                   # sum of outer products v k^T


def write_delta(keys, values, beta=1.0):
    S = np.zeros((values.shape[1], keys.shape[1]))
    for k, v in zip(keys, values):
        S += beta * np.outer(v - S @ k, k)                   # replace what k reads, keep the rest
    return S

Full script: recall.py

A read counts as correct if the returned vector is closer (by cosine) to the right value than to any other stored value; cos is the average cosine to the right value.

key and value width d = 64; the state is d x d = 4,096 numbers
 pairs  cache size        cache       linear        delta
         (numbers)  correct cos  correct cos  correct cos
    16       2,048   100%  1.00   100%  0.91   100%  0.95
    32       4,096   100%  1.00   100%  0.81   100%  0.84
    64       8,192   100%  1.00   100%  0.71    88%  0.67
   128      16,384   100%  1.00    96%  0.59    59%  0.46
   256      32,768   100%  1.00    70%  0.44    27%  0.25
   512      65,536   100%  1.00    35%  0.33    12%  0.13
 1,024     131,072   100%  1.00     9%  0.24     7%  0.07
 4,096     524,288   100%  1.00     0%  0.12     2%  0.02

The KV cache reads back every pair at every size, because its size grows with the pairs: 524,288 numbers at 4,096 pairs. The linear state stays at 4,096 numbers. It returns the right value for every pair up to $n = d = 64$ (with the average cosine already falling, 0.71 at 64), 70% at 256, 35% at 512 and none at 4,096. The size of the state is the dial. With 256 pairs and a fresh draw for each width:

state size dial: 256 pairs, linear and delta memories of width d
    d    state       linear        delta
   32    1,024    16%  0.34    11%  0.13
   64    4,096    73%  0.45    25%  0.25
  128   16,384   100%  0.57    62%  0.43
  256   65,536   100%  0.71   100%  0.68
  512  262,144   100%  0.82   100%  0.84

Doubling the width quadruples the state and moves the point where recall breaks. The experiment is a simplification. Its keys are random unit vectors, where a trained model learns keys that suit the data. It uses no feature map, where elu + 1 maps every key into the positive orthant and makes keys overlap more. Its softmax scale is fixed at 16, sharp enough to pick one key out of 4,096. Its delta rule writes at full strength ($\beta = 1$) with no learned strength and no gate. A real model also reads the state through many layers and heads. The shape of the result still matches the literature:

• Zoology (Arora et al., 2023) found gated-convolution models trailing attention “by up to 2.1 perplexity points on the Pile”, with “82% of the gap” explained by associative recall, retrieving something stated earlier in the context. “A 70M parameter attention model outperforms a 1.4 billion parameter gated-convolution model on associative recall.”
• Based (Arora et al., 2024) names “a key tradeoff between a model’s state size and recall ability”, the dial in the table above.
• Repeat After Me (Jelassi et al., 2024) proves that a two-layer Transformer can copy strings of length exponential in its number of heads, while state space models “cannot accurately copy strings with more bits than the size of the latent state”. Measured on pretrained models, Transformers “dramatically outperform state space models at copying and retrieving information from context.”

A fixed-size state buys constant inference cost and pays in in-context recall, at a rate set by the state’s size.

The delta rule: writing over instead of piling on

Plain linear attention only adds, $S_t = S_{t-1} + v_t k_t^\top$. Nothing is ever removed, so writing a key twice leaves both values in the sum. DeltaNet (Schlag et al., 2021; parallelized by Yang et al., 2024) uses the delta rule instead:

The first term erases what the state returned for $k_t$, scaled by a learned write strength $\beta_t \in (0, 1)$; the second writes the new value. write_delta above is this rule with $\beta = 1$. When a key is written twice, the difference is plain:

key 0 written with value a, 31 other pairs, then key 0 again with value b
  linear reads key 0: cos to a  0.73, cos to b  0.71
  delta  reads key 0: cos to a  0.21, cos to b  1.00

The linear state returns a mix of the old and new values; the delta rule returns the new one. The recall table shows the cost. From $n = d$ on, the delta rule did worse than plain accumulation, because each write erases part of what earlier, overlapping keys stored. Sorting the 256 pairs by when they were written shows where the losses fall:

256 pairs, d = 64: share read back correctly, by when the pair was written
       written  linear   delta
          1-32     84%      0%
         33-64     75%      0%
         65-96     81%      0%
        97-128     75%      0%
       129-160     66%      3%
       161-192     84%     22%
       193-224     84%     81%
       225-256     84%    100%

The two memories fail differently. Linear attention keeps a blurred copy of everything; the delta rule keeps the most recent pairs exactly and has overwritten the oldest. Both read back every pair correctly through 32 pairs and degrade past about $d$, the delta rule sooner and faster (88% against 100% at 64 pairs, 27% against 70% at 256). It fixes a rewritten key without raising capacity, and in this toy it lowered it. This toy should not be read as a ranking. In a trained model $\beta_t$ decides per token how hard to write, so a token can be stored lightly or not at all, and Yang et al. (2024) found DeltaNet more effective at associative recall than plain linear attention. Gated DeltaNet (Yang et al., 2024) adds a decay gate: “gating enables rapid memory erasure while the delta rule facilitates targeted updates.” That combination is what several 2025 models shipped.

Way three: replace attention with a recurrence

The third family reaches a similar place from the other side. It starts from control theory and adds what a language model needs.

The state space model

A state space model (SSM) is a hidden state $h(t)$ driven by an input $x(t)$, with the output read from the state:

To use it on tokens, it is discretized with a step size $\Delta$, which gives a plain recurrence:

With the zero-order hold (the input is held constant for the length of each step), $\bar{A} = \exp(\Delta A)$ and $\bar{B} = (\Delta A)^{-1}(\exp(\Delta A) - I)\,\Delta B$. For a diagonal $A$, as in the models below, everything is elementwise:

def discretize(delta, A, B):
    """Zero-order hold for diagonal A: Abar = exp(delta A), Bbar = (exp(delta A) - 1) / A * B."""
    Abar = np.exp(delta * A)
    return Abar, (Abar - 1) / A * B


def recurrence(Abar, Bbar, C, x):
    """h_t = Abar_t * h_{t-1} + Bbar_t x_t,  y_t = C_t . h_t; parameters may change with t."""
    h, y = np.zeros(N), np.empty(len(x))
    for t in range(len(x)):
        h = Abar[t] * h + Bbar[t] * x[t]
        y[t] = C[t] @ h
    return y

Full script: ssm.py

delta is a gate: Abar = exp(delta A) for this model's slowest and fastest state
  delta = 0.001   keeps 1.000 and 0.996 of the old state
  delta = 0.1     keeps 0.990 and 0.692 of the old state
  delta = 10.0    keeps 0.376 and 0.000 of the old state

$\Delta$ acts as a gate. With $A$ negative, a small $\Delta$ keeps the old state almost untouched and lets the token pass lightly; a large $\Delta$ wipes the state and writes the token in.

When $A$, $B$, $C$ and $\Delta$ are fixed, unrolling the recurrence shows that each output is a weighted sum of past inputs with weights $C\bar{A}^k\bar{B}$, the same for every position. That is a convolution, which can be computed in parallel over the whole sequence during training:

kernel = np.array([C @ (Abar ** k * Bbar) for k in range(T)])
y_conv = np.convolve(x, kernel)[:T]

Full script: ssm.py

fixed parameters, recurrence vs convolution: max difference 2.9e-15

The difficulty is $A$. A careless choice makes the state forget almost immediately or blow up, the vanishing and exploding gradients of RNNs. HiPPO (Gu et al., 2020) derives $A$ from a question: what fixed-size summary of a signal arriving one step at a time best reconstructs its history? Projecting the history onto polynomials gives a specific $A$; the LegS variant “assigns uniform weight to all history”, which avoids building a timescale into the model and gives bounded gradients.

S4 (Gu et al., 2021) made this fast by writing $A$ as normal plus low rank, “allowing it to be diagonalized stably and reducing the SSM to the well-studied computation of a Cauchy kernel”. It set the state of the art on every Long Range Arena task, “including solving the challenging Path-X task of length 16k that all prior work fails on.”

Mamba: making the recurrence input-dependent

S4 is a convolution because its parameters are fixed, and that is also its weakness: the same rule summarizes every token, so the model cannot treat one token as important and the next as filler. Attention does this by construction; that is what the softmax weights are.

Mamba (Gu & Dao, 2023) makes some of the parameters functions of the input, a change it calls selection:

Each token now chooses its own $\Delta$, so it decides how far it moves the state, and its own $B$ and $C$ decide what goes in and what comes out. The cost is that there is no longer one set of weights to convolve with. The paper says it plainly: “this change prevents the use of efficient convolutions.” In ssm.py, a kernel built from the first token’s parameters misses the selective recurrence by up to 4.9:

W_d, W_B, W_C = rng.standard_normal(), rng.standard_normal(N), rng.standard_normal(N)
deltas = np.log1p(np.exp(W_d * x))               # softplus, one step size per token
Bs, Cs = np.outer(x, W_B), np.outer(x, W_C)      # one B and one C per token
Abars, Bbars = zip(*(discretize(dt, A, b) for dt, b in zip(deltas, Bs)))
y_sel = recurrence(Abars, Bbars, Cs, x)

Full script: ssm.py

input-dependent, recurrence vs first token's kernel: max difference 4.9e+00
parallel scan in 8 steps vs 256 sequential steps: max difference 3.6e-15

The way back to parallel training is a scan. The step $h_t = a_t h_{t-1} + b_t$ composes associatively: applying $(a_1, b_1)$ then $(a_2, b_2)$ is the single step $(a_1 a_2,\ a_2 b_1 + b_2)$. So neighbours can be combined in pairs, then pairs of pairs, and 256 steps take 8 rounds, each fully parallel:

def scan(a, b):
    a, b, steps, k = a.copy(), b.copy(), 0, 1
    while k < len(a):
        b[k:] = a[k:] * b[:-k] + b[k:]           # every position combines with the one k back
        a[k:] = a[k:] * a[:-k]
        k, steps = 2 * k, steps + 1
    return b, steps

Full script: ssm.py

Mamba’s selective scan runs this inside the GPU’s on-chip memory, FlashAttention’s approach: parameters are loaded once, the state never goes out to main memory, and intermediate states are recomputed in the backward pass instead of stored. The paper reports the scan “up to 20-40x faster than a standard scan implementation”, “up to 3x faster” than earlier convolution-based SSMs on A100s, “5x higher throughput than Transformers” at generation, and a 3B Mamba matching Transformers twice its size. Its state is small: $N = 16$ numbers per channel.

Mamba-2: the two families turn out to be one

The two ways out of this post meet. Mamba-2 (Dao & Gu, 2024) proves a state space duality: “masked attention with 1-semiseparable structured matrices” is “a special case of a diagonal SSM where the diagonal matrix is a scalar multiple of the identity.”

The key step is short enough to check numerically. Restrict $A$ to one number per step, $a_t$. Then the contribution of input $s$ to output $t$ is $C_t^\top B_s \cdot a_{s+1} \cdots a_t$, and the whole layer is one masked matrix, $y = (L \circ CB^\top)\,x$, where $L$ holds the products of decays below the diagonal. That is attention’s quadratic form with $Q = C$, $K = B$, $V = x$:

a_t = np.exp(-deltas)                            # one scalar decay per token
Bk, Cq = rng.standard_normal((T, N)), rng.standard_normal((T, N))
h, y_lin = np.zeros(N), np.empty(T)
for t in range(T):
    h = a_t[t] * h + Bk[t] * x[t]
    y_lin[t] = Cq[t] @ h
logs = np.cumsum(np.log(a_t))
L = np.tril(np.exp(logs[:, None] - logs[None, :]))
y_quad = (L * (Cq @ Bk.T)) @ x

Full script: ssm.py

scalar decay, linear recurrence vs quadratic masked form: max difference 1.4e-13
with every a_t = 1, L is the causal mask and (L * (C B^T)) x is causal linear attention, Q = C, K = B, V = x

The paper describes the two forms as “naive (quadratic-time) multiplication by the matrix M” and “a particular efficient (linear-time) algorithm”, the same choice as $(QK^\top)V$ against $Q(K^\top V)$ above, reached from the other side. Mamba-2 then uses it for speed. With a scalar $A$, the computation splits into blocks of matrix multiplications, which run on tensor cores, the units Mamba’s scan could not use. The paper reports its layer “2 - 8x faster than the optimized selective scan implementation of Mamba, while simultaneously allowing for much larger recurrent state sizes (8x the size of Mamba or even higher, with minimal slowdown)”. That is the recall dial from recall.py, turned up because it became cheap.

What actually shipped: nobody picked one

None of the three families won. The models that ship something other than plain attention mostly mix: a few attention layers for exact recall, many cheap layers for the rest. configs.py reads each model’s layout from its config.json at a pinned revision, and computes the KV cache the attention layers need at 256K tokens:

full attention, for comparison
Llama-2-7b-hf           32 of  32 layers attention (100%), KV cache at 256K  128.0 GiB (all-attention  128.0 GiB)
Mixtral-8x7B-v0.1       32 of  32 layers attention (100%), KV cache at 256K   32.0 GiB (all-attention   32.0 GiB)

hybrids: attention beside linear-attention or state-space layers
Jamba-v0.1               4 of  32 layers attention ( 12%), KV cache at 256K    4.0 GiB (all-attention   32.0 GiB); Mamba state size 16
Nemotron-H-8B            4 of  28 mixers attention ( 14%), KV cache at 256K    4.0 GiB (all-attention   28.0 GiB); plus 24 MLP layers
Qwen3-Next-80B-A3B      12 of  48 layers attention ( 25%), KV cache at 256K    6.0 GiB (all-attention   24.0 GiB); one attention layer every 4, the rest Gated DeltaNet
Kimi-Linear-48B-A3B      7 of  27 layers attention ( 26%); attention (MLA) at layers [4, 8, 12, 16, 20, 24, 27], Kimi Delta Attention elsewhere
MiniMax-Text-01         10 of  80 layers attention ( 12%), KV cache at 256K   10.0 GiB (all-attention   80.0 GiB); the rest lightning (linear) attention

Full script: configs.py

Three things in that output are worth a closer look.

The savings match what the papers report. Jamba’s paper gives 4 GB at 256K tokens against 32 GB for Mixtral and 128 GB for Llama-2-7B (the row in its Table 1 is the 6.7B model); the configs give 4.0, 32.0 and 128.0 GiB. Kimi Linear reports “up to 75%” less KV cache and a 6.3× faster time per output token than full attention at 1M tokens. Nemotron-H reports “up to 3x” faster inference for its 8B model against Llama-3.1-8B, with attention in 4 of its 52 layers (4 of the 28 that mix tokens; the rest are MLPs).

Two labs chose three linear layers per attention layer. Qwen3-Next places one attention layer every four. Kimi Linear, which cites Qwen3-Next, tested several ratios and found that “the 3:1 ratio … yielded the best results”, while 7:1 trained worse. Its released 27-layer model has 7 attention layers, ending the pattern one layer early. Jamba and MiniMax-Text-01 used 7:1 and Nemotron-H 6:1 among its mixing layers, so the right ratio is a trade-off each team prices differently, not a constant.

The cheap layers differ, the principle does not. Jamba and Nemotron-H use Mamba layers; Qwen3-Next uses Gated DeltaNet; Kimi uses Kimi Delta Attention, which “extends Gated DeltaNet with a finer-grained gating mechanism”, and its attention layers use multi-head latent attention (MLA), which caches a compressed latent per token (The KV Cache derives it), so configs.py does not size its cache; MiniMax-Text-01 used lightning attention, a linear attention. Other designs mix within a layer rather than across layers: Falcon-H1 runs attention and Mamba-2 heads side by side in each block, Samba interleaves Mamba with sliding-window attention, and Zamba2 shares one or two attention blocks across a Mamba-2 backbone.

DeepSeek-V4 mixes along a different axis. Its config gives each layer a compression ratio:

DeepSeek-V4-Pro        61 layers: 30 merge 4 tokens per entry (CSA), 31 merge 128 (HCA); top 1,024 entries, window 128

Compressed Sparse Attention merges every 4 tokens’ keys and values into one entry and selects among them; Heavily Compressed Attention merges every 128 and, in the report’s words, “keeps dense attention” over the result. Both also attend to the last 128 tokens directly. The report gives “only 27% of single-token inference FLOPs and 10% of KV cache compared with DeepSeek-V3.2” at 1M tokens. This is compression at write time, like a linear state, but of a different kind: the cache still grows with the context, at 1/4 or 1/128 of the rate, instead of staying fixed. Anatomy of a Frontier Model reads the design in detail.

The honest scorecard

MiniMax shipped a linear hybrid, then went back to full attention. MiniMax-Text-01 used lightning attention in 70 of its 80 layers; MiniMax-M2 uses full attention in all 62, as its config shows. The engineering post explaining why is candid: “the truth is that efficient attention still has some way to go before it can definitively beat full attention.” The hybrid “looked just as good as pure full attention” on MMLU, BBH, MATH and LongBench, but “the price paid became obvious at a larger scale: the model had clear deficits in complex, multi-hop reasoning tasks.” The section reporting this is titled “Benchmarks are a Leaky Abstraction”.

The post’s reasons are broader than one benchmark gap. MiniMax built proxy metrics for the weakness and “iterated until the hybrid model seemed to match MHA”, then could not tell whether the proxies would keep tracking real tasks; it names the limits of evaluation and the immaturity of infrastructure for linear and sparse attention (low-precision state, prefix caching, speculative decoding). It groups linear, sparse and hybrid attention together. Then MiniMax-M3 shipped sparse attention:

back to full attention, then sparse
MiniMax-M2              62 of  62 layers attention (100%), KV cache at 256K   62.0 GiB (all-attention   62.0 GiB)
MiniMax-M3             57 of 60 layers sparse: top 16 blocks of 128 tokens per query, 2,048 keys; the first 3 layers full

Each query in M3 reads 16 blocks of 128 tokens chosen by an index, and every token stays in the cache. MiniMax did not say why it chose sparse over linear, and the M3 report itself lists a “residual long-context retrieval gap” as future work. The pattern fits the distinction this post has been building, which is an interpretation and not MiniMax’s stated reason:

• Sparse attention keeps the full cache and selects what to read. Recall fails only if the selector misses, and the information is still there for the next query.
• Linear attention and SSMs fold the past into a fixed-size state as it arrives. Recall fails because the information is gone, and recall.py shows the point where that starts: about $d$ pairs per state.
• A compressed cache, as in DeepSeek-V4, sits between them: it discards detail at write time, but its capacity still grows with the context.

BigBird’s “no free lunch” bound in 2020 and MiniMax’s multi-hop deficit in 2025 point the same way: spending less per token takes something from some capability, and the evaluation has to look for it.

The broadest study of training-free sparse attention, The Sparse Frontier (Nawrot et al., v3, 2026), cuts both ways. For sparsity: “larger sparse models outperform smaller dense ones at equivalent cost, improving the Pareto frontier.” Against applying it uniformly: “sparsity tolerance varies dramatically across tasks,” and no method wins everywhere, since “fine-grained token selection … excels at retrieval, chunk-based methods … suit reasoning and aggregation.” Decoding also tolerates more sparsity than prefill.

Choosing, in practice

Match the method to the bill being paid:

Two rules come from the evidence rather than the theory. When evaluating a cheaper attention mechanism, test in-context retrieval directly: multi-hop questions, needle-in-a-haystack, copying. Aggregate benchmarks did not show MiniMax the failure. And when the budget allows, prefer methods that keep the cache addressable. That second rule is this post’s reading of the evidence: MiniMax’s reversal went to full attention first, and it gave no reason for choosing sparse attention afterwards.

Where this leads

• FlashAttention derives the exact kernel every method here is measured against.
• Long Context, and Where It Breaks measures attention sinks and the recall failures that full attention has too.
• Anatomy of a Frontier Model reads DeepSeek-V4’s compressed sparse attention layer by layer.
• How LLM Architecture Evolved, 2017–2026 places hybrids among the other substitutions since 2017.

Takeaways

• “Attention is quadratic” hides two bills: $4n^2d$ FLOPs per head at prefill (8.8 TFLOPs at 128K tokens) and a KV cache read on every decode step (17.2 GB at 128K for a Llama-3-8B shape). Each alternative cuts one or both, and pays in something else: recall, depth or selector misses.
• FlashAttention is exact, not an alternative. It removes the memory traffic and keeps the $O(n^2)$ FLOPs, and it is the bar every approximate method must clear.
• Linear attention is one change of parentheses: without the softmax, $(QK^\top)V = Q(K^\top V)$, and the right-hand order builds a $d \times d$ state instead of an $n \times n$ matrix. The saving is $n/d$ by count; on an M4 GPU, against a plain product, it was 75× at 16K tokens and nothing measurable below 512.
• State space models reach the same recurrence from control theory. Mamba’s input-dependent parameters break the convolution and need a scan; Mamba-2 shows that with a scalar decay the SSM is masked linear attention, computable in either order.
• The fixed-size state is what is being bought. A 64-wide linear-attention state read back all of 64 stored pairs and 35% of 512; the delta rule keeps the newest exactly and loses the oldest. That limit is a likely reason no frontier model is purely linear.
• What shipped is hybrids, with attention in roughly one layer of four to one of eight, and one lab that went from a linear hybrid to full attention to sparse attention.

References

Start with Katharopoulos et al. for the algebra of linear attention, then Mamba-2 for the duality between linear attention and SSMs, then MiniMax’s post for what the trade-off looked like in production.

• Vaswani et al., Attention Is All You Need (2017): the softmax attention this post looks for alternatives to.
• Dao, Fu, Ermon, Rudra & Ré, FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022), and Dao, FlashAttention-2 (2023): exact attention made fast enough to be the bar.
• Beltagy, Peters & Cohan, Longformer (2020): sliding, dilated and global attention.
• Zaheer et al., Big Bird: Transformers for Longer Sequences (2020): window, global and random attention, universal approximation, and the “no free lunch” depth bound.
• Jiang et al., Mistral 7B (2023): sliding-window attention in production, and the rolling buffer cache.
• Xiao et al., Efficient Streaming Language Models with Attention Sinks (ICLR 2024): why evicting the first tokens breaks a model, and the fix.
• OpenAI, gpt-oss-120b & gpt-oss-20b Model Card (2025): alternating 128-token windows and learned sinks.
• Yuan et al., Native Sparse Attention (DeepSeek, 2025): trainable sparsity with compression, selection and window branches.
• Lu et al., MoBA: Mixture of Block Attention for Long-Context LLMs (Moonshot, 2025): mixture-of-experts routing applied to blocks of the context.
• DeepSeek-AI, DeepSeek-V3.2-Exp (2025): the lightning indexer and top-2,048 sparse attention.
• Schlag, Irie & Schmidhuber, Linear Transformers Are Secretly Fast Weight Programmers (ICML 2021): the delta rule as a write rule for linear attention.
• Katharopoulos, Vyas, Pappas & Fleuret, Transformers are RNNs (ICML 2020): the kernel view, the change of parentheses, and the recurrent form.
• Arora et al., Zoology: Measuring and Improving Recall in Efficient Language Models (2023) and Simple linear attention language models balance the recall-throughput tradeoff (Based, 2024): the recall gap, and state size as a dial.
• Jelassi et al., Repeat After Me: Transformers are Better than State Space Models at Copying (2024): the proof that a fixed state limits copying.
• Yang et al., Parallelizing Linear Transformers with the Delta Rule (2024) and Gated Delta Networks (2024): erase-then-write memory, and gating added to it.
• Gu, Dao, Ermon, Rudra & Ré, HiPPO: Recurrent Memory with Optimal Polynomial Projections (2020): where the $A$ matrix comes from.
• Gu, Goel & Ré, Efficiently Modeling Long Sequences with Structured State Spaces (S4, 2021): the normal-plus-low-rank parameterization and Long Range Arena.
• Gu & Dao, Mamba: Linear-Time Sequence Modeling with Selective State Spaces (2023): selection, and the hardware-aware scan.
• Dao & Gu, Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality (Mamba-2, 2024): the duality between linear attention and SSMs.
• Lieber et al., Jamba (AI21, 2024), Ren et al., Samba (Microsoft, 2024), Zamba2 (Zyphra, 2024), Nemotron-H (NVIDIA, 2025), Falcon-H1 (TII, 2025), Kimi Linear (Moonshot, 2025), and the Qwen3-Next model card (2025): the production hybrids.
• DeepSeek-AI, DeepSeek-V4 (2026): compressed sparse and heavily compressed attention.
• MiniMax, MiniMax-01: Scaling Foundation Models with Lightning Attention (2025): the linear hybrid that M2 replaced.
• MiniMax, Why Did M2 End Up as a Full Attention Model? (2025): the reversal, and “Benchmarks are a Leaky Abstraction”. MiniMax, MiniMax Sparse Attention (2026): the sparse attention in M3.
• Nawrot et al., The Sparse Frontier (v3, 2026): when training-free sparsity pays and when it does not.