Linformer Low-Rank Attention

Standard self-attention compares every token to every other token, so its cost grows with the square of sequence length $n$, doubling the input length quadruples the work. Linformer's authors observed something empirical: in trained transformers, the $n \times n$ attention matrix is usually approximately low-rank, meaning most of its information could be reconstructed from a much smaller number of "directions" than $n$. If that's true, you don't need to compute the full $n \times n$ matrix at all.

Linformer acts on this by projecting the keys and values, normally $n \times d$ matrices, down to a fixed, much smaller size $k \times d$ using two learned projection matrices, where $k$ is chosen once (e.g. 256) regardless of how long the sequence is. Attention is then computed between the full-length queries and these $k$-row keys and values, producing an $n \times k$ attention matrix instead of $n \times n$. Since $k$ is fixed, total cost scales linearly in $n$, not quadratically.

Concretely, a sequence of $n = 4{,}096$ tokens with standard attention costs on the order of $n^2 = 16{,}777{,}216$ score computations; with Linformer and $k = 256$, it costs on the order of $n \times k \approx 1{,}048{,}576$, roughly a sixteen-fold reduction, growing larger as $n$ increases further.