Linear attention

On this page 7

Linear attention is a family of attention mechanisms that replaces the softmax similarity with a kernel feature map, so that the cost of attending over a sequence grows linearly rather than quadratically with sequence length. In neural networks built on the Transformer design, it is the main alternative to standard softmax attention for long contexts and memory-constrained inference.

The idea rests on a simple algebraic step: once the softmax is removed, the order of matrix multiplications can be rearranged. That rearrangement turns attention into a running summary that can be updated token by token, which is why linear attention is often described as a bridge between Transformers and recurrent models.

How linear attention reorders the attention computation

Standard attention computes softmax(Q K^T) V, where Q, K and V are the query, key and value matrices for N tokens of dimension d. The product Q K^T is an N by N score matrix, so time and memory scale with N squared. At 100,000 tokens, that matrix holds ten billion entries per head.

Linear attention writes the similarity as a dot product of feature maps, phi(q) · phi(k), where phi is a nonnegative function such as elu(x) + 1. Because matrix multiplication is associative, the output becomes phi(Q) (phi(K)^T V). The inner product phi(K)^T V is only d by d, so it is computed once and reused for every query, giving cost proportional to N times d squared.

A normalizer term, phi(Q) (phi(K)^T 1), replaces the softmax denominator so that weights still sum to one. The table compares the resulting costs for a single attention head.

QuantitySoftmax attentionLinear attention
Training timeProportional to N squared times dProportional to N times d squared
Training memoryN by N score matrixd by d summary matrix
Inference state per layerKey-value cache growing with NFixed d by d state
Generation cost per tokenGrows with context lengthConstant
ExactnessExact softmax weightsApproximation or different similarity
Asymptotic cost of softmax and linear attention per head

The recurrent form and causal decoding

In causal language modeling, each token may attend only to earlier tokens. Linear attention handles this with a recurrent state update: S_t = S_(t-1) + phi(k_t) v_t^T, and the output is phi(q_t) S_t divided by the matching normalizer. The state S is a fixed-size matrix that summarizes the entire history.

This makes generation behave like a recurrent neural network: memory does not grow with context, and each new token costs the same. Training, however, needs parallelism. Modern implementations use a chunkwise parallel form that computes exact attention inside short chunks and passes the recurrent state between chunks, which keeps GPU utilization high.

The three computational forms of the same model are summarized below, together with the situation in which each is used.

FormHow it computesTypical use
Parallel formMasked quadratic product without softmaxShort sequences, reference checks
Recurrent formToken-by-token state updateAutoregressive generation
Chunkwise formParallel within chunks, recurrent across chunksEfficient long-sequence training
Equivalent computational forms of causal linear attention

Main variants of linear attention

Variants differ chiefly in how they choose the feature map and how they update or forget the state. Early work aimed to approximate softmax; later work accepted a different similarity and focused on expressive state updates instead.

VariantKey mechanismMain motivation
Kernelized attentionFixed feature map such as elu plus oneSimplest linear form
Random feature attentionRandom projections approximating the softmax kernelUnbiased softmax approximation
Decay-based retentionExponential decay applied to the stateForget distant tokens gradually
Gated linear attentionData-dependent gates on the stateSelective forgetting
Delta rule attentionState corrected toward the new key-value pairBetter associative recall
Representative linear attention variants

Approaches such as low-rank key projection also reach linear cost but do not use a recurrent state, so they cannot decode in constant memory. They are usually grouped with efficient attention rather than linear attention in the strict sense.

Linear attention is one of several answers to the quadratic cost of self-attention. Its closest relative is the state space model: work on structured state space duality showed that models such as Mamba-2 can be written as a form of gated linear attention, which blurred the line between the two families.

ApproachCost in sequence lengthKeeps all tokensMain weakness
Linear attentionLinearNo, compressed stateWeaker exact recall
Sparse attentionBelow quadraticPartlyFixed patterns may miss links
Sliding window attentionLinearOnly recent windowNo direct long-range access
State space modelLinearNo, compressed stateSimilar recall limits
Full softmax attentionQuadraticYesCost at long contexts
Linear attention compared with neighboring approaches

Limitations and practical trade-offs

The fixed-size state is both the strength and the central weakness. A d by d matrix cannot store an unbounded number of distinct key-value associations, so linear attention struggles with precise retrieval tasks such as copying a passage or finding a specific fact deep in the context.

  • Attention dilution: without softmax, weights are less peaked, so the model focuses less sharply on the most relevant tokens.
  • Normalizer instability: small denominators can cause numerical problems, and many recent designs drop the normalizer in favor of output normalization.
  • Hardware reality: at short sequence lengths, highly optimized softmax kernels are often faster, so the advantage appears mainly beyond several thousand tokens.
  • Quality gap: pure linear models have usually trailed softmax Transformers of equal size on recall-heavy benchmarks.

The prevailing remedy is a hybrid architecture that interleaves many linear attention layers with a small share of full attention layers, often in ratios around three to one or higher. This keeps most of the memory savings while restoring exact retrieval where it matters.

The short version

Normal attention lets every word in a text look back at every other word, which becomes very expensive as the text grows. Linear attention keeps a running summary instead, a bit like a notebook that is updated after each sentence rather than rereading the whole book.

That notebook has a fixed size, so it is fast and cheap for very long texts. The cost is that some details get blurred, which is why many modern models mix both kinds of attention.

Where it makes a difference

An engineering team deploys a language model to summarize lengthy legal case files of around 200,000 tokens on GPUs with limited memory. With full softmax attention in every layer, the key-value cache for a single request would exhaust the available memory and leave no room for concurrent users.

The team chooses a hybrid model in which most layers use gated linear attention and roughly one layer in four uses full attention. The linear layers keep a constant-size state regardless of document length, so memory per request drops sharply and several documents can be processed in parallel. The occasional full attention layers preserve the model’s ability to quote exact clauses, and the outcome is higher throughput with summary quality close to that of the all-softmax baseline.