The Race to O(n)

Every softmax attention layer compares each token against every other token with O(T²) complexity in sequence length, and O(T²) memory costs ^[1,2]. With ever-growing context windows (at least since context windows crossed the hundred-thousand-token mark) the contested race to get attention's cost down to O(n) started. So much so, that Miami startup SubQ raised $29M while the AI community shouted "Theranos allegations" in response to the breakthroughs ^[30]. The literature surfaces the pattern that every family of solution relaxes one constraint while quietly keeping another, and the places where people claim to have relaxed all of them at once are exactly where you should look the hardest.

Family 1: keep the comparisons, prune them

The first response doesn't touch the O(T²) structure at all and refuses to compute most of the matrix, using a pattern fixed in advance. Longformer restricts each token to a local sliding window plus a few global tokens; BigBird adds random tokens on top of a local window and proves the combination is still Turing-complete and a universal function approximator, so fixed sparsity doesn't provably cost expressivity in principle ^[3,4,5]. In practice, fixed-pattern sparse attention has consistently failed on long-context retrieval benchmarks like RULER, because a token can only attend where the pattern allows, regardless of whether the relevant information is actually there, the sparsity is positional, not content-dependent ^[6].

FlashAttention takes an orthogonal angle on the exact same computation: it never materializes the full N×N score matrix in GPU memory, tiling the softmax into blocks that fit in on-chip SRAM via an online-softmax recurrence, so peak memory drops from O(N²) to O(N) and throughput rises substantially with output numerically identical to naive attention ^[7,8]. It does not (nor does it aspire to) change the FLOP count, as doubling the sequence length still quadruples the compute. At 128K tokens attention costs roughly 8.6 billion operations per layer; at 1M, 549 billion; at 2M, 2.2 trillion ^[6]. FlashAttention solved the memory problem that made long-context experimentation impractical for the first time ^[6].

Family 2: learn what to prune, and pay for the learning

DeepSeek's 2025 Native Sparse Attention (NSA) tries to get sparsity's efficiency without fixed-pattern's blindness, by learning the routing decision from content. Coarse token compression is combined with fine-grained learned token selection, and a sliding window, hardware-aligned from the start ^[31,32]. NSA's selector is a "Lightning Indexer": a distilled attention model that scores every query-key pair to decide what the sparse attention downstream should read ^[6].

That indexer is itself full attention, and in the released DeepSeek V3.2-style configuration it is cheaper than the sparse attention it feeds only below roughly 52,000 tokens; past that crossover its O(T²) scoring overtakes the O(T) sparse attention, reaching roughly 16x the cost of the attention it serves at 1M tokens and 190x at 12M ^[6]. DeepSeek V4's Compressed Sparse Attention inherits the identical problem in its indexer; its Heavily Compressed Attention alternative avoids learned selection but is still dense attention over a shorter sequence, a scalar win rather than a change in asymptotic shape ^[6]. The general lesson: moving selection from "fixed pattern" to "learned" tends to reintroduce, inside the selector, exactly the quadratic cost the selector was meant to eliminate from the main computation. Efficiency at the attention-read step and efficiency at the routing-decision step are two separate problems, and most learned-sparse systems solve only the first.

Does the learned selector actually learn to route on content, or does the rest of the network just adapt to whatever the gate currently does and route around it? Routing absorption from February 2026 measures this failure mode ^[26]. On a controlled 31M-parameter transformer, a soft gate trained end-to-end for 50,000 steps converges to 48.73 perplexity; a frozen random gate, never trained at all, converges to 49.83 (a 2.2% gap), capturing only 9% of the possible improvement between random and oracle routing ^[26]. Hard top-k gating, the kind most production sparse-attention systems (plausibly including NSA's downstream sparse read, and any per-query top-k selector generally) actually deploy, is worse. The mask is piecewise-constant, so the gradient through it is exactly zero, and learned versus frozen-random gates come out numerically indistinguishable (71.22 vs. 71.24 perplexity) ^[26]. Training a checkpoint trained without any mask (1,000 steps), freezing it, and distilling a small gate against it, gets within 6% of oracle routing. The same gate architecture, trained jointly for fifty times longer, barely beats a coin flip ^[26]. The difference isn't the gate but co-adaption (of whatever is routed) to the router. It specializes to the shape of the mask rather than its content, and a gate that reaches 0.804 F1 against an oracle mask still produces a twelve-fold perplexity blowup the moment you swap in a differently-shaped mask at the same predicted positions ^[26]. Worse, this gets more severe at larger scale (tested directly on Qwen3-1.7B, the random-vs-learned gap shrinks steadily as more layers are allowed to co-adapt) ^[26].

It's worth noting this trap is avoidable, and well-known. Reformer's LSH attention hashes queries and keys into buckets via a fixed random projection, so there is no gate to absorb because the routing function is fixed before training starts, giving O(L log L) ^[33,34]. Routing Transformer's online k-means clusters are learned and update via a slow exponential moving average ^[35]. H-Transformer-1D avoids a hard discrete choice altogether, computing a continuous, differentiable-everywhere approximation inspired by numerical-analysis H-matrices ^[36]. Every subquadratic selector that has actually worked in the published literature avoided joint, hard, per-query gating specifically. The routing-absorption paper alternatively decouples the router's training from the backbone's, training (or freezing) the backbone first and fitting the selector post-hoc by distillation (close to NSA's indexer) ^[26,6].

Family 3: replace comparison with a running memory

A third family doesn't prune the O(T²) computation. The pairwise comparison structure is eliminated entirely. The kernel trick is to factor the similarity between a query and key as an inner product of feature maps, φ(q)ᵀφ(k), then reorder the double sum in attention so a query only ever touches one fixed-size matrix, never the T individual keys that produced it ^[9]. That matrix, W, is a running memory where each token adds an outer product of its value and feature-mapped key, and each output is one read against the current W. Training cost drops to linear in T, and inference per token becomes constant time ^[9]. This is also a description of a linear RNN. Some popular architectures are RetNet's retention mechanism with an explicit recurrent/parallel/chunkwise duality ^[10,11]; RWKV's receptance-weighted recurrence, built to combine transformer-style parallel training with RNN-style constant-memory inference ^[12,13]; Griffin's RG-LRU gated linear recurrence, no attention at all in the "Hawk" variant ^[14]; S4's structured state-space parameterization, made input-selective by Mamba ^[15,16,37].

Mamba-2's State Space Duality result is the cleanest unification: a structured class of SSMs is exactly a form of linear attention with a semiseparable causal mask, so the same computation can be read either as a cheap recurrence or as a quadratic matrix multiply, and systems tricks transfer between the two readings ^[17,18,19]. That unification matters because it means this family's fixed-size state absorbing an unbounded sequence is a compression, and compression is lossy ^[6].

Family 4: don't just accumulate, correct

Naive linear attention just writes forever: W ← W + v⊗κ, with nothing to un-write, so old associations linger and interfere with new writes to overlapping key directions ^[20]. DeltaNet asks (before writing) what the memory already predicts for the current key, and writes only the residual (one step of online gradient descent on a reconstruction loss) ^[20,21]. The error-correction needs its own hardware-efficient parallelization: a chunked, WY-representation form of the delta rule (before it scales past toy sizes) ^[21,22].

DeltaNet still can't clear memory in bulk; every correction is local to one key. The lineage adds bulk forgetting one control dimension at a time. Gated DeltaNet applies a scalar decay to the whole memory before the delta-rule correction ^[23]; Kimi Delta Attention makes that decay channel-wise, so some feature subspaces are retained while others are aggressively cleared ^[24]; Gated DeltaNet-2 decouples the erase gate (which key-feature channels get removed) from the write gate (which value channels get committed), previously controlled by the same scalar ^[25]; CARVE argues Gated DeltaNet-2's gating is still over-parameterized relative to what a single hardware-friendly triangular solve supports, and restricts gating to the key axis to preserve that solve while conditioning erasure on the previous chunk's own content ^[38]. Each step is legible as one more knob on the same fast-weight object, motivated by a specific failure the previous step couldn't fix.

Family 5: prove the ceiling instead of chasing it

A fifth line of work stops optimizing architecture and asks how bad the fixed-size-state constraint fundamentally is. Jelassi et al. show theoretically that a two-layer transformer can copy strings of exponential length while any fixed-state generalized state-space model is bounded regardless of depth or training, and confirm empirically that pretrained transformers dramatically outperform pretrained SSMs at copying and retrieving context ^[39]. Zoology frames the same gap as a recall–throughput trade-off: a bounded state cannot do content-addressed recall beyond roughly its own dimension, however cleverly it's gated ^[27,28]. Mimetic initialization shows that the right initialization lets Mamba copy and recall over sequences several times longer than standard init achieves, but the gap to attention narrows rather than closes ^[29]. BASED responds pragmatically, combining cheap-but-imprecise linear attention with exact softmax attention in a small sliding window, tuning the window to trace the recall–memory Pareto frontier rather than picking one point ^[40]. Log-linear attention takes the more theoretical middle path: let the number of hidden states grow logarithmically with sequence length instead of staying fixed, admitting a matmul-rich parallel form at log-linear compute cost ^[41].

Josh Alman gives an impossibility proof, under the Strong Exponential Time Hypothesis, that calculating the gradients (the backward pass) in sub-quadratic time is mathematically impossible by any algorithm whatsoever ^[42]. A companion result for hybrid SSM+sparse-attention stacks makes the same point that solving "multi-query joint recall" with such a hybrid requires the SSM's state dimension to grow linearly with the number of table entries, which is exactly the O(n²)-in-disguise ^[43]. This is why empirically the frontier keeps flinching back toward dense attention: MiniMax shipped M1 as a hybrid combining Lightning Attention with full attention, then returned to full attention across every layer for their subsequent frontier model M2, reporting that hybrid variants matched full attention on standard benchmarks but showed clear deficits on higher-order multi-hop reasoning at scale, with less mature supporting infrastructure besides ^[6].

The claim that all four properties can be had at once

During this search for the holy grail, Subquadratic AI released its May 2026 technical report of Subquadratic Sparse Attention (SSA) that is simultaneously content-dependent, subquadratic including the selection stage itself, capable of arbitrary-position access, and practical to train at multi-million-token scale ^[6,30]. They report 99.12% on the 13-task RULER benchmark at 128K tokens, 100% single-needle retrieval through 2M tokens, and 98% retrieval accuracy (@ 12M context tokens and 1M training tokens) while attending to only 0.13% of token pairs ^[6]. SubQ's selector is roughly 17x cheaper at 1M tokens and 191x cheaper at 12M (compared to DeepSeek's Lightning Indexer @matched selected-position budget) because it doesn't reintroduce quadratic scoring inside the selection stage the way NSA's indexer does ^[6].

Scepticism is warranted since it's a single company's technical report on their own model, not independently replicated or peer-reviewed, and the content-dependent selection mechanism of SSA is explicitly excluded ^[6]. Reverse-engineering from public benchmark numbers shows that the data is consistent with content-dependent routing under a bounded budget but doesn't rule out a routing scheme closer to fixed than genuinely adaptive, and proposed forcing known-relevant tokens into the selected set as a diagnostic test ^[44,45]. The report's own findings include a real trade-off between retrieval-optimized checkpoints (measured on MRCR benchmark) and checkpoints that performed best on realistic multi-document synthesis and contract analysis. The authors then switched their primary development signal to RULER specifically ^[6].

Routing-absorption from Family 2 showed some similarity. If SSA's selector is a per-query, hard, jointly-trained top-k gate, then the mechanism could be described as choosing, per query, "which portions of the sequence should receive attention". This was the design most exposed to learning nothing beyond what a frozen random gate would already give ^[26,6]. The report is explicit that SSA's mechanism could differ structurally from the per-query gating the routing-absorption paper studies, in ways that might avoid the failure mode entirely ^[26]. Unfortunately, the public materials miss a comparison against a frozen or randomly-initialized selector at matched sparsity.

An orthogonal axis: sharing across depth, not just across sequence

Every mechanism above is about sequence mixing within a layer. A separate failure mode is dilution across layers: information written at layer 3 can be hard to recover by layer 20, because each layer only sees what survived the residual stream above it. For softmax stacks, value-residual learning feeds an early layer's attention values forward into later layers to counteract this over-smoothing ^[46,47]; Mixture-of-Depths lets tokens skip layers entirely via a learned router instead ^[48,49]. Applying a full depth-attention operator to a linear-memory stack partially defeats the point, though (reintroduces quadratic-ish cost across depth).

Tommaso Cerruti from ETH Zürich, along with Tim Rieder, George Rowlands and Lingfeng Jin, test the DeltaNet-flavored answer. They forward a lower layer's write error into the next layer's value target (Cross-Layer Error Residuals). This doesn't beat a matched baseline, because the routed error lands in the receiver's independently-learned value space, misaligned with that layer's own geometry, competing with rather than complementing its write target ^[50]. They (i) route into the shared residual stream instead, through a zero-initialized projection so the routed contribution starts at exactly zero and the model learns how strongly to use it; and separately, (ii) route the write value rather than the write error. That Cross-Layer Value Routing (CLVR) lowers final validation loss for both DeltaNet and Gated DeltaNet hosts. It cleanly establishes sharing across depth helps specifically where the naive version of it fails and that the fix is a change of injection space. The same paper's broader sweep found that a hybrid stack (one softmax layer per two linear-memory layers) beat every pure recurrent configuration tested ^[50], echoing the MiniMax M1-to-M2 story at a much smaller scale.

The throughline

The routing absorption shows a router can look trained and contribute nothing, because the much larger surrounding network absorbs the signal instead of the router learning anything real. NSA's indexer shows a router can be correctly decoupled and honest, yet still reintroduce the exact cost it was built to eliminate, just moved rather than removed. CLVR shows where to route, in the aligned hidden stream and forwarding the write value. Is a mechanism meant to carry a signal across some boundary (token position, depth, selection budget) actually carrying it, or is the rest of the network absorbing, ignoring, or fighting it? In every one of these cases, ablate against the null (random routing, zero-strength injection, a frozen gate) and check if the result actually depends on what the mechanism learned. Conspicuously, the ablation is missing from SubQ's report claiming to have reached O(n).

The shape of this problem looked familiar to me. The race to O(n) and continual learning asks a structurally identical question (across tasks instead of depth or token position) whether an update from a new process regime genuinely generalizes or gets absorbed and overwritten by what an earlier regime already encoded, depending on whether it's expressed in a shared geometry the receiver can actually use ^[51,52].