Linear Attention › Linear Attention

Standard self-attention computes a weighted sum of value vectors, where the weights come from a softmax over query-key similarities. This produces an $n \times n$ attention matrix that must be explicitly computed and stored, leading to the quadratic bottleneck that limits transformers to modest sequence lengths. Linear attention takes a radically different approach: by replacing the softmax with a decomposable kernel function, it enables a clever reordering of matrix operations that eliminates the quadratic term entirely.

The main point is mathematical: if we can factor the attention weights into a product of separate functions applied to queries and keys, we can change the order of operations from $(QK^T)V$ to $Q(K^TV)$. The first form requires computing the full $n \times n$ attention matrix. The second form computes $K^TV$ first, which has shape $d \times d$ (model dimension squared), independent of sequence length. This simple reordering maps $O(n^2d)$ complexity into $O(nd^2)$. This makes attention linear in sequence length.

In this chapter, we explore how linear attention achieves this transformation, examine the kernel feature maps that make it possible, implement the mechanism from scratch, and analyze both its theoretical elegance and practical limitations. We also survey variants like Performer that address some of softmax attention's properties that linear attention initially sacrifices.