nyströmformer
**Nyströmformer** is an efficient Transformer architecture that approximates the full softmax attention matrix using the Nyström method—a classical technique for approximating large kernel matrices by sampling a subset of landmark points and reconstructing the full matrix from this subset. Nyströmformer selects m landmark tokens (via segment-means or learned selection) and uses them to approximate the N×N attention matrix as a product of three smaller matrices, achieving O(N·m) complexity.
**Why Nyströmformer Matters in AI/ML:**
Nyströmformer provides **high-quality attention approximation** that preserves the softmax attention's properties more faithfully than linear attention or random feature methods, achieving near-exact attention quality with significantly reduced computational cost.
• **Nyström approximation** — The full attention matrix A = softmax(QK^T/√d) is approximated as à = A_{NM} · A_{MM}^{-1} · A_{MN}, where M is the set of m landmark tokens, A_{NM} is the N×m attention between all tokens and landmarks, and A_{MM} is the m×m attention among landmarks
• **Landmark selection** — The m landmark tokens are selected by averaging consecutive segments of the sequence: each landmark represents the mean of N/m consecutive tokens, providing a uniform coverage of the sequence; this is simpler than random sampling and provides consistent quality
• **Pseudo-inverse stability** — Computing A_{MM}^{-1} requires inverting an m×m matrix, which can be numerically unstable; Nyströmformer uses iterative methods (Newton's method for matrix inverse) to compute a stable pseudo-inverse without explicit matrix inversion
• **Approximation quality** — With m=64-256 landmarks, Nyströmformer achieves 99%+ of full attention quality on standard NLP benchmarks, outperforming Performer, Linformer, and other efficient attention methods on long-range tasks
• **Complexity analysis** — Computing A_{NM} costs O(N·m·d), A_{MM}^{-1} costs O(m³), and the full approximation costs O(N·m·d + m³); for m << N, this is effectively O(N·m·d), linear in sequence length
| Component | Dimension | Computation |
|-----------|-----------|-------------|
| A_{NM} | N × m | All-to-landmark attention |
| A_{MM} | m × m | Landmark-to-landmark attention |
| A_{MM}^{-1} | m × m | Nyström reconstruction kernel |
| Ã = A_{NM}·A_{MM}^{-1}·A_{MN} | N × N (implicit) | Full attention approximation |
| Landmarks (m) | 32-256 | Segment means of input |
| Total Complexity | O(N·m·d + m³) | Linear in N for fixed m |
**Nyströmformer brings the classical Nyström matrix approximation method to Transformers, providing one of the highest-quality efficient attention approximations through landmark-based reconstruction that faithfully preserves softmax attention patterns while reducing quadratic complexity to linear, achieving the best quality-efficiency tradeoff among efficient attention methods.**