If your “constant-time” attention still scans a million tokens, we need to talk.
“Linear attention” is becoming the gluten-free of AI architecture terminology: everyone puts it on the label, nobody agrees what it means, and you still have to inspect the ingredients.
Depending on the paper, linear may mean:
- linear computation during prompt prefill;
- constant computation per generated token;
- a constant-size recurrent state;
- a smaller—but still linearly growing—KV cache;
- sparse attention over a fixed number of selected tokens; or
- “most of our layers are linear, except for the ones that aren’t.”
These are not minor variations of the same claim. They describe different resource requirements and can produce radically different behavior on real hardware.
Recent surveys distinguish hardware-efficient, compact, sparse, and algebraically linear attention. That taxonomy is useful, but for systems analysis we need an even cleaner separation: capacity, traffic, and computation.
Before declaring another attention mechanism “linear,” let us ask three questions:
**How much memory does it occupy?****How much data does it load?**How much computation does it perform?
If a paper answers only one of these and lets the adjective linear imply the other two, hide your asymptotic wallet.
The Three Bills Attention Sends You #
Let L be the current sequence length. For simplicity, assume dimensions, head counts, window sizes, state sizes, and selection counts remain fixed as L grows.
1. Occupied Memory Capacity: What Must Stay Resident?
After processing L tokens, how much persistent state must the model retain to generate the next one?
Conventional attention keeps a key and value representation for every previous token: M
. Using grouped-query attention, multi-query attention, quantization, or Multi-Head Latent Attention can make each entry much smaller. This is extremely valuable. But if the architecture still keeps one entry per token, occupied capacity remains KV = O(L)O(L).
A recurrent linear-attention or state-space layer instead folds the history into a fixed-size state: M
. That state might be a rather chunky matrix. “Constant” does not mean “tiny”; it means that token number 1,000,001 does not require another cache entry.state = O(1) with respect to L
A KV cache is a warehouse that grows with every token. A recurrent state is a fixed-size suitcase. The suitcase is wonderfully portable—but eventually you must decide what to forget, overwrite, or compress.
2. Memory-Load Traffic: What Must Be Dragged Through the Machine?
Occupied memory is not bandwidth.
A system can retain a huge history but touch only a few entries for each query. Conversely, a cache may fit comfortably in high-bandwidth memory while the model rereads the entire thing for every generated token.
The relevant quantity is: T
. The corresponding bandwidth floor is approximately: mem(L) = bytes transferred per decode stept
. Dense attention usually stores mem >= Tmem / BeffectiveO(L) KV state and reads O(L) KV state for every token. The cache is not merely taking up space; it is demanding a complete guided tour on every decode step.
FlashAttention showed why data movement deserves its own axis. It does not change exact attention’s arithmetic asymptotics. Instead, it tiles and fuses the computation so that intermediate results are kept out of high-bandwidth memory wherever possible, greatly reducing IO and temporary materialization.
Same mathematical attention. Same asymptotic flops. Much less pointless furniture moving.
A more interesting design point is data-driven sparse attention, where the system retains an O(L) cache but does not load every full KV entry for every decode step. Instead, a lightweight, query-dependent selector identifies a small set of relevant positions, and only those k KV entries are fetched for the expensive attention operation. If selection can be performed using a compact index—or through a genuinely sublinear retrieval structure—the main KV traffic falls from O(L) to O(k), even though occupied cache capacity remains O(L). In other words, the model keeps the whole library but carries only a few books to the desk. This creates a useful combination that recurrent methods do not offer: unbounded token-addressable memory capacity with potentially constant full-KV traffic per decode step.
DeepSeek Sparse Attention is an instructive—but not yet fully sublinear—example. Its lightning indexer scans compact, low-precision index representations for all preceding tokens, selects the top-k positions, and loads the larger MLA cache entries only for those positions. DSA therefore avoids all full KV entries, reducing expensive KV traffic to O(k); however, it still loads or processes O(L) compact index data to discover them. Its total selection traffic consequently remains linear in L, although with a much smaller coefficient than dense MLA. Future hierarchical, hashed, clustered, or learned indexes could push this toward sublinear retrieval—producing architectures with O(L) occupied capacity but sublinear, or even approximately constant, memory traffic and attention computation per decode step.
3. Computational Complexity: How Much Arithmetic Happens?
For dense causal attention:
- prompt prefill costs O(L²); - one decode step costs O(L); and - generating Gadditional tokens costs approximatelyO(GL + G²) for attention.
These quantities must be reported separately. A mechanism can reduce expensive attention computation without reducing persistent memory. It can reduce memory traffic without changing flop complexity. It can also have linear total prefill
complexity while using constant computation per decode step.
Calling all of these “linear” is mathematically legal in roughly the same way that calling a tiger “a cat” is zoologically legal.
The Attention Complexity Zoo #
The following table summarizes the sequence-length scaling of prominent mechanism families. All O(1) entries are with respect to L, assuming fixed dimensions, state sizes, windows, ranks, or selection counts.
| Mechanism | Occupied state | Decode traffic | Decode compute | Prefill compute |
|---|---|---|---|---|
| Dense MHA | O(L) | O(L) | O(L) | O(L²) |
| FlashAttention | O(L) KV; smaller working memory | O(L), better IO constants | O(L) | O(L²) |
| MQA/GQA | O(L), smaller coefficient | O(L), smaller coefficient | O(L) | O(L²) |
| MLA | O(L), compressed | O(L), compressed | O(L) | O(L²) |
| Sliding window with eviction | O(1) | O(1) | O(1) | O(L) |
| Sparse access, all history retained | O(L) | O(1), if locations are known | O(1) | O(L) |
| DSA-style exhaustive index plus top-k | O(L) | O(L) scan + O(k) retrieval | O(L) indexing + O(k) attention | Potentially O(L²) indexing |
| Performer/kernel linear attention | O(1) | O(1) | O(1) | O(L) |
| GLA/DeltaNet/Gated DeltaNet/KDA layer | O(1) | O(1) | O(1) | O(L) |
| Mamba/SSM layer | O(1) | O(1) | O(1) | O(L) |
| Fixed-ratio recurrent/dense hybrid | O(L) | O(L) | O(L) | O(L²) |
The table’s main message is not that one row wins. It is that the columns can move independently.
Dense Attention: Expensive, Honest, and Easy to Classify #
Dense attention is refreshingly straightforward.
It retains one KV entry per previous token: capacity = O(L)
. It reads and interacts with those entries for each new token: decode traffic = O(L) decode compute = O(L)
. During prefill, every prompt token can interact with every earlier token: prefill compute = O(L²)
. One frequent source of confusion is the statement that attention requires “quadratic memory.” Naive prefill or training implementations may materialize an L × L score matrix, which is indeed quadratic. Persistent inference KV capacity, however, is linear.
FlashAttention avoids materializing that quadratic intermediate in HBM while still performing exact dense attention. It reduces working memory and IO—not the quadratic number of prefill interactions.
FlashAttention is faster attention, not asymptotically less attention.
MLA: Compressed Is Excellent, but Compressed Is Not Linear #
MQA, GQA, and MLA attack the number of bytes stored per token:
MQA shares one KV head across query heads.GQA shares KV heads within groups.- MLA stores a compressed latent representation rather than full per-head keys and values.
MLA can substantially reduce KV-cache capacity and bandwidth pressure. Hardware analyses show that the compact latent representation can move decode execution away from a bandwidth-bound regime, depending on how reconstruction and projection are implemented.
That is a major systems improvement.
But MLA still retains a representation for each token: capacity = O(L)
. Dense MLA still incorporates all previous entries for each query: decode compute = O(L) prefill compute = O(L²)
.
MLA is compressed dense attention—not linear-time attention.
A suitcase with vacuum-packed clothes still gets heavier as you add shirts.
Sparse Attention: Fewer Accesses, Same Attic #
Suppose each query attends to a fixed number k of earlier tokens. If those locations are already known, the main attention operation costs: O(k) per decode step O(Lk) during prefill
. With fixed k, that is constant decode work and linear prefill work. But what happens to all the unselected tokens?
Sliding-Window Attention
If tokens older than a fixed window w can never be referenced again, their KVs can be evicted: capacity = traffic = decode compute = O(w) = O(1)
. This is the clean version. The mechanism forgets old details and admits it.
Sparse Access to Arbitrary History
If a future query may select any previous position, every old representation may need to remain somewhere: capacity = O(L)
. Yet each query may retrieve and process only k entries: traffic = O(k) attention compute = O(k)
. BigBird-style patterns reduce the attention graph to a linear number of local, random, and global edges instead of evaluating all token pairs. But a linear-sized sparse graph does not automatically imply a constant-size autoregressive state.
Large memory capacity, small per-query traffic, and small attention compute.
The model keeps the whole attic but retrieves only one box.
DSA: Top-k Attention Does Not Make Top-k Discovery Free #
DeepSeek Sparse Attention is particularly interesting because it exposes a cost that sparse-attention descriptions often politely escort out of the room:
How do you find the k relevant tokens?
DSA uses a lightweight “lightning indexer” to score preceding tokens. It then selects the top-k entries and applies the more expensive MLA attention operation only to those selected entries. The indexer has a small number of heads and can operate in FP8, making it much cheaper than full attention.
The expensive attention portion is fixed in k: core attention compute = O(k)
. But the current indexer still scores the query against the preceding sequence: indexer compute = O(L)
. The index representations and MLA cache entries remain token-indexed: occupied capacity = O(L)
. A more accurate description is therefore:
DSA performs O(L) cheap retrieval work to avoid O(L) expensive attention work.
That can be an outstanding trade. A linear FP8 index scan may be far cheaper than full MLA over a million tokens. Asymptotic notation does not pay the electricity bill; constants and arithmetic intensity matter.
Still, a million cheap comparisons are not zero comparisons.
During prefill, query-to-history index scoring can remain quadratic over the complete sequence, while selected core attention is linear for fixed k. NVIDIA’s DSA implementation similarly exposes index scoring, top-k selection, and sparse-attention kernels as separate components.
To obtain genuinely sublinear or constant decode retrieval, DSA would need a different index structure—perhaps hierarchical, hashed, clustered, or otherwise sublinear. That would introduce new update costs, approximation behavior, and hardware complexity.
There are no free lunches. There are only increasingly sophisticated meal plans.
Recurrent Linear Attention: The History Becomes a State #
Kernel linear attention changes the algebra. The layer does not retain every key and value separately. It updates a sufficient statistic: S
. For fixed feature dimensions:t = St-1 + f(kt)vtT
capacity = O(1)
decode traffic = O(1)
decode compute = O(1)
prefill compute = O(L)
Performer approximates softmax attention through random features, while GLA, DeltaNet, Gated DeltaNet, and KDA use learned decay, gating, or delta-rule updates to manage a recurrent matrix state more effectively.
Mamba and related state-space models occupy a similar systems regime. They maintain fixed-size recurrent state and use hardware-aware parallel algorithms for training and prefill, producing computation that scales linearly with sequence length.
This sounds strictly superior—until we remember the suitcase.
A dense KV cache retains explicit token-indexed information. A recurrent model compresses an arbitrarily long history into a finite state. Gating enables rapid forgetting, while delta updates enable targeted replacement, but the information capacity remains bounded by the state dimension.
Recurrent attention eliminates cache growth by answering:
“What should we remember?”Dense attention answers:“Yes.”
Kimi Linear: Three Linear Layers in a Trench Coat with MLA #
Now for the provocative part.
A Kimi Delta Attention layer is genuinely linear-time in prefill and recurrent at decode. It maintains a fixed-size state rather than a token-indexed KV cache.
But Kimi Linear, the complete architecture, is not asymptotically linear.
The published model uses a 3:1 ratio of KDA to global MLA layers: three recurrent KDA layers followed by one dense MLA layer. The authors accurately call it a hybrid architecture and report up to a 75% reduction in KV-cache usage relative to an all-MLA baseline.
That is a very good engineering outcome.
It does not change the asymptotic complexity of the complete model.
If a fixed fraction p > 0 of layers uses dense global attention, then:
capacity = O(pL) + O(1) = O(L)
decode traffic = O(pL) + O(1) = O(L)
decode compute = O(pL) + O(1) = O(L)
prefill compute = O(pL²) + O(L) = O(L²)
Reducing the coefficient by four can produce enormous speedups. But: (1/4)L² = O(L²)
Big-O notation is famously unmoved by branding.
KDA is a linear recurrent attention mechanism. Kimi Linear is a hybrid architecture with mostly KDA layers and periodic dense MLA layers.As a complete model, it retains O(L) cache growth, O(L) decode attention cost, and O(L²) prefill attention cost.
“Hybrid linear” is a reasonable architectural name. “Constant-time decoding” would not be a reasonable model-level complexity claim.
We Need Better Labels #
Rather than asking whether an architecture is “linear,” papers and systems reports should use more precise terms:
Prefill-linear: total prefill arithmetic is O(L). - Decode-constant: arithmetic per generated token is O(1) in prior
context length. - State-constant: persistent attention state is O(1) in L. - Traffic-constant: data movement per generated token is O(1) in L. - Cache-compressed: persistent state remains O(L), but bytes per
token are reduced. - Sparse-access: each query uses only O(k) history entries. - Linear-indexed: selection scans O(L) compact index entries before
sparse attention. - Hybrid-linear: recurrent layers coexist with dense layers;
model-level complexity must be reported separately.
These terms are less glamorous than “linear attention.”
They also have the unfortunate property of telling us what the architecture actually does.
The Future Is a Matrix, Not a Leaderboard #
There is no single road from quadratic attention to “linear attention.” There is a multidimensional design space.
Large Capacity, Small Accesses
Retain an enormous external history but retrieve only a fixed number of entries for each query.
Fixed State, Constant Decode
Compress the entire past into recurrent state, accepting bounded information capacity.
Cheap Linear Search, Sparse Expensive Attention
Scan a compact index over the history, then run full attention on only the best candidates—as in current DSA.
Local State Plus Occasional Global Access
Use constant-cost local or recurrent mechanisms most of the time and periodically invoke global attention.
Hierarchical Memory
Keep a small recurrent state on-chip, a larger compressed cache in HBM, and an enormous sparse history in host or storage memory.
These architectures may all be described as “efficient attention,” but they optimize different resources.
Conclusion: Show Us All Three Bills #
The phrase linear attention has become too ambiguous to carry a serious systems argument by itself.
An architecture can:
- have linear prefill computation but a substantial fixed state;
- have constant selected-attention compute but linear retrieval work;
- retain O(L) memory while only O(1) entries;
- compress KV capacity without changing sequence-length exponents; or
- use linear layers three-quarters of the time while remaining quadratic overall.
So the next time someone says, “Our model uses linear attention,” the correct response is not applause.
Linear in what?
Ask for:
- occupied memory capacity;
- memory traffic per token;
- prefill computation;
- decode computation;
- selection or indexing cost; and
- model-level complexity—not merely the complexity of its favorite layer.
If those quantities are separated, the confusion disappears.
If they are not, linear may be doing less mathematical analysis and more marketing.
And unlike the KV cache, our patience does not need to grow with sequence length.
References #
Sun et al.,
https://arxiv.org/abs/2507.19595
“Efficient Attention Mechanisms for Large Language Models: A Survey”
. - Zhang et al.,
“Efficient Attention Methods: Hardware-efficient, Sparse, Compact, and Linear Attention”. - Dao et al.,
.
“FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness”
Geens and Verhelst,
https://arxiv.org/abs/2506.02523
“Hardware-Centric Analysis of DeepSeek’s Multi-Head Latent Attention”
. - Zaheer et al.,
.
“Big Bird: Transformers for Longer Sequences”
DeepSeek-AI,
.
“DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models”
NVIDIA,
.
“DeepSeek Sparse Attention—cuDNN Frontend”
Choromanski et al.,
.
“Rethinking Attention with Performers”
Yang, Kautz, and Hatamizadeh,
https://arxiv.org/abs/2412.06464
“Gated Delta Networks: Improving Mamba2 with Delta Rule”
. - Gu and Dao,
.
“Mamba: Linear-Time Sequence Modeling with Selective State Spaces”
Kimi Team,
.
“Kimi Linear: An Expressive, Efficient Attention Architecture”