Linear Attention and Performer Kernels
Linear attention replaces the quadratic softmax attention in Transformers with a math trick that scales linearly with sequence length.
Overview
Performer is a landmark method that approximates softmax using random feature kernels, making very long sequences computationally affordable.
Deep Dive
Standard Transformer attention computes a score between every pair of tokens, costing time and memory that grow with the square of sequence length (O(n^2)). Linear attention rewrites the computation so cost grows only linearly (O(n)). The key idea: softmax attention is softmax(QK^T)V, but if you replace softmax with a kernel feature map phi, you get phi(Q)(phi(K)^T V). Because matrix multiplication is associative, you compute phi(K)^T V first (a small d-by-d matrix), avoiding the giant n-by-n score matrix entirely. Performer, from Google in 2020, makes this a faithful approximation of true softmax using FAVOR+ (Fast Attention Via positive Orthogonal Random features), drawing random projections that keep the kernel estimates unbiased and stable.
Technical Insight
Performer's FAVOR+ approximates the softmax kernel exp(q.k) using positive random features: it maps queries and keys through random Gaussian projections wrapped in an exponential, guaranteeing non-negative attention weights and avoiding the numerical instabilities of earlier estimators. Using orthogonal random features reduces variance. Crucially, the n-by-n attention matrix is never materialized, so memory drops from quadratic to linear, enabling sequences of tens of thousands of tokens.
Strategic Impact
Cost and budget
Architecture decisions drive performance and operating cost for years.
Clearer decisions
Technical education helps teams choose the right stack, not just the newest one.
Quality control
Better engineering choices reduce reliability incidents in production.
The Future of Linear Attention and Performer Kernels
Pure linear attention often trails softmax on quality, so the field is converging on hybrids: state-space models (Mamba), gated linear attention, and architectures that mix a few full-attention layers with many linear ones. As context windows push toward millions of tokens, linear and sub-quadratic mechanisms are increasingly attractive for cost, and recurrent-style linear attention is being revisited for efficient streaming inference and on-device models.
Real-World Implementation
Processing long genomic or protein sequences where full quadratic attention would exhaust GPU memory
Document-level summarization over very long reports without chunking, using a Performer-style backbone
Efficient long-form audio or time-series modeling where sequences span tens of thousands of steps
Reducing inference cost in long-context chat models by replacing some softmax layers with linear-attention variants
Risks & Guardrails
Optimizing one benchmark can hide broader system weaknesses.
Infrastructure and maintenance costs are often underestimated.
Security and observability gaps can grow as systems become more complex.
Implementation Roadmap
Define latency, quality, and cost targets before implementation.
Benchmark under realistic load and data conditions.
Instrument monitoring for errors, drift, and user impact.
Prepare rollback and incident response paths before scaling.
Keep Exploring
Free newsletter
Get the daily AI briefing
Three verified AI stories every weekday morning, written in plain English. Free forever, no ads.
One email each weekday. Unsubscribe in one click. We never sell or share your address.
Test yourself
Take the Linear Attention and Performer Kernels quiz
Instant feedback on every answer, and a shareable certificate with a verifiable ID once you pass a course.
Support free AI education. AI Understanding is a 501(c)(3) nonprofit — no ads, no paywall, ever. Make a donation
Next guide
RWKV Linear Attention
Frequently asked questions
What is Linear Attention and Performer Kernels?
Linear attention replaces the quadratic softmax attention in Transformers with a math trick that scales linearly with sequence length. Performer is a landmark method that approximates softmax using random feature kernels, making very long sequences computationally affordable.
Why does standard softmax attention scale poorly with sequence length?
Softmax attention compares every pair of tokens, producing an n-by-n score matrix, so cost grows as O(n^2).
What mathematical property lets linear attention avoid the n-by-n matrix?
Because matrix multiplication is associative, you can compute phi(K)^T V first, a small d-by-d matrix, instead of phi(Q)phi(K)^T.
What does Performer's FAVOR+ mechanism approximate?
FAVOR+ uses positive orthogonal random features to approximate the exponential softmax kernel without forming the full attention matrix.
Why does Performer use positive random features rather than the earlier trigonometric ones?
Positive features keep the kernel estimates non-negative, avoiding the instabilities and negative values that plagued earlier sin/cos feature maps.
What is the approximate complexity of Performer-style linear attention in sequence length n?
By reordering the computation and never building the n-by-n matrix, cost scales linearly with sequence length.