Linear Attention

Linear attention is a family of attention mechanisms that approximates standard softmax attention while scaling linearly with sequence length instead of quadratically, enabling Transformers to process long contexts efficiently.

What It Is

Standard Transformers get very slow on long inputs because their attention step compares every token to every other token. For a ten-thousand-token document, that is one hundred million comparisons, and the cost grows with the square of the input length. Linear attention is the umbrella term for a family of techniques that cut that cost down to grow in a straight line with input length instead of a curve — which is what makes long-context models and modern hybrid architectures like Mamba-3, Jamba, and Nemotron-H practical to serve.

The core trick is to avoid ever computing the full n-by-n attention matrix. Instead of applying softmax (the function that turns raw scores into probabilities) directly across all token pairs, linear attention either projects keys and values into a smaller fixed-size space, or rewrites softmax using kernel feature maps — small mathematical transformations that let you reorder the matrix multiplications so the expensive step runs only once. The output is a carefully designed approximation of standard attention, not an exact copy, but one with provable error bounds.

Several flavors exist inside the family. According to Linformer arXiv, Linformer reduces self-attention from quadratic to linear time and space via a low-rank projection of keys and values, with a one-and-a-half-times inference speedup and a one-point-seven-times larger maximum batch over a standard Transformer at sequence length five hundred twelve. According to Performer OpenReview, the Performer architecture takes a different route: its FAVOR+ method — Fast Attention Via positive Orthogonal Random features — provably approximates full-rank softmax attention at linear cost without assuming sparsity or low-rank structure. According to IJCAI Proceedings, more recent work approximates the underlying graph filter instead of softmax directly, showing the design space is still opening up.

How It’s Used in Practice

Most product managers and developers encounter linear attention indirectly, through long-context models and hybrid architectures. When you feed a two-hundred-thousand-token document to a modern model and get a response in seconds, linear-time attention or a related state-space mechanism is often doing the work behind the scenes. The architecture choice is invisible in the user interface but very visible in the bill.

Where this becomes decision-relevant is when you evaluate models for long-context tasks. A pure Transformer pays a quadratic price for every extra token. Models using linear attention or hybrid blocks keep latency roughly proportional to input length, which translates into lower costs per token on long inputs and faster time-to-first-token on document-scale prompts. Two models advertising the same context window can differ by an order of magnitude on long inputs, and the architecture page often tells you why before the benchmarks do.

Researchers and engineers interact with linear attention directly when building or fine-tuning efficient architectures. According to lucidrains GitHub, the linear-attention-transformer reference implementation in PyTorch is a widely used starting point with clean baselines for Linformer, Performer, and kernel variants.

Pro Tip: When you compare long-context models, do not assume a bigger window means better latency. Check whether the architecture uses linear-time attention, state-space blocks, or a hybrid of both. Two models advertising the same context length can differ sharply in cost and time-to-first-token once prompts get long.

When to Use / When Not

Common Misconception

Myth: Linear attention and State Space Models are two names for the same idea. Reality: Both achieve linear-time complexity, but through different paths. State Space Models derive a linear-time recurrence from state-space discretization, carrying a hidden state that evolves step by step. Linear attention rewrites the softmax attention formula itself using feature maps or low-rank projections. Modern hybrid architectures often combine both in the same stack, which is why the two are easy to confuse.

One Sentence to Remember

Linear attention keeps Transformer-style attention workable on long inputs by trading the perfect softmax calculation for an approximation whose cost grows in a straight line rather than a curve.

FAQ

Q: Is linear attention as accurate as standard softmax attention? A: Modern kernel and delta-rule variants close most of the quality gap on long-sequence tasks, but exact softmax still wins on some benchmarks. The right choice depends on input length and tolerance for approximation error.

Q: Can I swap standard attention for linear attention in an existing pretrained model? A: Not without retraining or heavy adaptation. The attention formulation is baked into the weights, so replacing softmax attention with a linear variant usually means fine-tuning or retraining the model from scratch.

Q: How does linear attention relate to FlashAttention? A: They solve different problems. FlashAttention makes exact softmax attention faster through memory-aware GPU kernels. Linear attention changes the attention math itself to a linear-time approximation. A model can combine both ideas in the same stack.

Sources

• Linformer arXiv: Linformer: Self-Attention with Linear Complexity - Low-rank projection approach that reduces self-attention to linear time and memory
• Performer OpenReview: Rethinking Attention with Performers (ICLR 2021) - FAVOR+ random-feature method that provably approximates softmax attention at linear cost