linformer
**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
| Configuration | Projected Dim k | Quality (vs Full) | Speedup | Memory Savings |
|--------------|----------------|-------------------|---------|----------------|
| k = 64 | Small | 95-97% | 8-16× | 8-16× |
| k = 128 | Standard | 97-99% | 4-8× | 4-8× |
| k = 256 | Large | 99%+ | 2-4× | 2-4× |
| Shared heads | k per layer | ~98% | 4-8× | Better |
| Shared layers | Same k everywhere | ~96% | 4-8× | Best |
**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.**