Let’s Stop Calling Everything “Linear Attention” | Torsten Hoefler's blog

“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: MKV = O(L). 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 O(L) .

A recurrent linear-attention or state-space layer instead folds the history into a fixed-size state: Mstate = O(1) with respect to L. 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.

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: Tmem(L) = bytes transferred per decode step. The corresponding bandwidth floor is approximately: tmem >= Tmem / Beffective. Dense attention usually stores O(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 loading 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...