Linformer is an efficient Transformer architecture that reduces the self-attention complexity from O(N²) to O(N) by projecting the key and value matrices from sequence length N to a fixed lower dimension k, based on the observation that the attention matrix is approximately low-rank. By learning projection matrices E, F ∈ ℝ^{k×N}, Linformer computes attention as softmax(Q(EK)^T/√d)·(FV), operating on k×d matrices instead of N×d.

Why Linformer Matters in AI/ML: Linformer demonstrated that full attention is often redundant because attention matrices are empirically low-rank, and projecting to a fixed dimension achieves near-identical performance while enabling linear-time processing of long sequences.

• Low-rank projection — Keys and values are projected: K̃ = E·K ∈ ℝ^{k×d} and Ṽ = F·V ∈ ℝ^{k×d}, where E, F ∈ ℝ^{k×N} are learned projection matrices; attention becomes softmax(QK̃^T/√d)·Ṽ, computing an N×k attention matrix instead of N×N • Fixed projected dimension — The projection dimension k is fixed regardless of sequence length N (typically k=128-256); this means computational cost grows linearly with N rather than quadratically, enabling theoretically unlimited sequence lengths • Empirical low-rank evidence — Analysis shows that attention matrices have rapidly decaying singular values: the top-128 singular values capture 90%+ of the attention matrix's energy across most layers and heads, validating the low-rank assumption • Parameter sharing — Projection matrices E, F can be shared across heads and layers to reduce parameter count: head-wise sharing (same projections per layer) or layer-wise sharing (same projections across all layers) with minimal quality impact • Inference considerations — During autoregressive generation, Linformer's projections require access to all previous tokens' keys/values simultaneously, making it less suitable for causal (left-to-right) generation compared to bidirectional encoding tasks

Linformer is the foundational work demonstrating that Transformer attention is practically low-rank and can be efficiently approximated through learned linear projections, reducing quadratic complexity to linear while preserving model quality and establishing the low-rank paradigm that influenced all subsequent efficient attention research.