This is an explainer of the 2020 Linformer by Wang, Li, Khabsa, Fang, and Ma. Its central idea is that the n by n self-attention matrix is approximately low-rank, its information living in a tiny subspace, so you can compress the keys and values from n tokens down to k much smaller than n and attend to those, turning the n by n attention matrix into n by k and reducing time and memory to order n. The evidence is spectral: a trained transformer’s attention matrix P equals softmax of Q K transpose over root d has singular values that decay fast, so almost all the energy sits in the top few singular directions and P is well approximated by a rank k matrix for a small constant k independent of sequence length. The Johnson-Lindenstrauss lemma backs this: you can project to a target dimension depending on the desired error not the number of points, and Linformer shows the softmax attention matrix can be approximated to error epsilon by a rank k matrix with k equal to order d over epsilon squared, independent of n, so k stays fixed as sequences grow. The mechanism adds two learned projection matrices E and F, each k by n, that shrink the sequence dimension from n to k: K prime equals E K is k by d and V prime equals F V is k by d, then attention is softmax of Q times K prime transpose over root d, which is n by k, times V prime. The queries stay full length so they attend to only k compressed keys, making the attention matrix a tall thin n by k strip instead of a giant square; E and F are trained end to end and learn which combinations of positions to summarize, and can be shared across heads and layers. It is order n because Q times K prime transpose is order n k d, the softmax over n by k is order n k, and the final multiply by V prime is order n k d, all linear in n for fixed k, with memory order n k and no n by n matrix ever formed; in the paper k as small as 128 to 256 matched full-attention RoBERTa across tasks even as n grew into the thousands. Caveats: because E and F are k by n the projection is tied to a specific n so Linformer wants a fixed or bounded sequence length, ideal for encoders like classification and retrieval but awkward for autoregressive generation where n grows one token at a time and a global length n projection is ill defined; global compression loses precise reach so the low-rank bet fails on tasks needing genuinely high-rank attention like exact copying or precise long-range retrieval; and it approximates so the error is real when the attention matrix is not actually low-rank as in early layers or some heads. In the lineage Linformer defines the low-rank projection branch of efficient attention, distinct from skipping pairs (sparse) or hashing them (Reformer), compressing the whole interaction into a smaller matrix; its sibling is the kernel branch which reaches order n differently by rewriting softmax as a product of feature maps, namely the Performer. Two interactive widgets let the reader drag the retained rank k on a synthetic decaying-spectrum matrix and watch the Frobenius reconstruction error collapse, and compare full n by n versus Linformer n by k size and cost as sequence length grows with k fixed.