Nyströmformer: Approximating self-attention in linear time and memory via the Nyström method

TL;DR

Nyströmformer is an efficient Transformer variant that approximates the standard self-attention mechanism to achieve linear time and memory complexity, $O(n)$, instead of the traditional quadratic complexity, $O(n^2)$. This allows the model to handle significantly longer input sequences while maintaining competitive performance across NLP and Computer Vision tasks.

The Nyström Method for Matrix Approximation

The Nyström method approximates a large matrix $P^{n \times n}$ by sampling a subset of $m$ rows and columns. By arranging these samples into a block matrix, the original matrix is divided into four submatrices: $A_{P}$ ($m \times m$), $B_{P}$ ($m \times (n - m)$), $F_{P}$ ($(n - m) \times m$), and $C_{P}$ ($(n - m) \times (n - m)$).

Because the entries of $A_{P}$, $B_{P}$, and $F_{P}$ are known through sampling, the unknown submatrix $C_{P}$ can be estimated as:

$$C_{P} = F_{P} A_{P}^{+} B_{P}$$

where $+$ denotes the Moore-Penrose pseudoinverse. The resulting Nyström approximation $\hat{P}$ is expressed as a product of three matrices, reducing the computational burden of calculating the full matrix.

Adapting Nyström to Self-Attention

Standard self-attention relies on a softmax matrix $S = \text{softmax}(\frac{QK^T}{\sqrt{d}})$. Direct application of the Nyström method to $S$ is impossible because calculating a single column of a softmax matrix requires knowledge of all other columns to compute the row-wise softmax denominator.

To solve this, Nyströmformer samples "landmarks" (Nyström points) from the queries ($Q$) and keys ($K$) rather than sampling from the resulting softmax matrix. The model defines three matrices based on query landmarks $\tilde{Q}$ and key landmarks $\tilde{K}$:

  • $\tilde{F} = \text{softmax}(\frac{Q\tilde{K}^T}{\sqrt{d}})$
  • $\tilde{A} = \text{softmax}(\frac{\tilde{Q}\tilde{K}^T}{\sqrt{d}})^{+}$
  • $\tilde{B} = \text{softmax}(\frac{\tilde{Q}K^T}{\sqrt{d}})$

The approximated softmax matrix $\hat{S}$ is then calculated as $\hat{S} = \tilde{F} \tilde{A} \tilde{B}$. By multiplying this approximation with the values ($V$), the model achieves linear approximation of self-attention without ever computing the full $QK^T$ product.

Landmark Selection and Implementation

Nyströmformer constructs $\tilde{Q}$ and $\tilde{K}$ using segment means. The $n$ tokens are divided into $m$ segments, and the mean of each segment is computed to serve as a landmark. Research indicates that using as few as 32 or 64 landmarks provides competitive performance even for sequence lengths of $n = 4096$ or $8192$.

Implementation Details

  • Depthwise Convolution: The architecture includes a 1D depthwise convolution (DConv) as a skip connection added to the values.
  • Complexity: The approach successfully avoids $O(n^2)$ complexity, enabling efficiency on long sequences.

Availability and Usage in Hugging Face

Nyströmformer is available for Masked Language Modeling (MLM) via the Hugging Face Transformers library. Four checkpoints are provided based on sequence length: nystromformer-512, nystromformer-1024, nystromformer-2048, and nystromformer-4096.

Users can control the number of landmarks $m$ using the num_landmarks parameter in the NystromformerConfig. The model can be deployed using the NystromformerForMaskedLM class or the high-level pipeline API for tasks such as fill-mask.

Sources