Singularformer: Learning to Decompose Self-Attention to Linearize the Complexity of Transformer

Yifan Wu, Shichao Kan, Min Zeng, Min LiIJCAI 2023 · DOI

TL;DR

This paper introduces Singularformer, a novel Transformer variant that linearizes the quadratic complexity of self-attention by learning to decompose the attention matrix using neural networks. This approach significantly reduces computational cost and memory usage, making Transformers more efficient for long sequences without sacrificing performance.

What Problem Does This Paper Address?

Transformers have revolutionized many fields, particularly natural language processing, due to their ability to capture long-distance dependencies through the self-attention mechanism. However, this mechanism's core operation, calculating an $n \times n$ attention matrix for an input sequence of length $n$, leads to quadratic time and space complexity ($O(n^2)$). This computational bottleneck severely limits the length of sequences that can be processed, requiring extensive computational resources and time for training and inference. Existing methods to address this often involve approximations, sparsity, or introducing new hyperparameters, sometimes at the cost of accuracy or stability.

Methods

Singularformer tackles the quadratic complexity by leveraging the theoretical insight that the attention matrix ($A$) is often singular or low-rank. The authors propose decomposing the attention matrix into three factors based on Singular Value Decomposition (SVD): $A = U \Sigma V^T$. Instead of performing a direct SVD, which is computationally expensive, Singularformer uses neural networks to learn these factors ($U$, $\Sigma$, and $V^T$).

Specifically, the attention calculation is reformulated as $H = \alpha_u \Sigma' \alpha_v$, where $\alpha_u$ and $\alpha_v$ are learned matrices derived from the input sequence, and $\Sigma'$ is a diagonal matrix of singular values. The core idea is to learn projections that map the input sequence to a lower-dimensional space, perform attention in this reduced space, and then project back. This decomposition, learned by shared linear projection layers, effectively linearizes the attention computation to $O(n \cdot r)$ where $r$ is the rank of the learned decomposition (and $r \ll n$). To ensure the learned factors behave like SVD components, orthogonal and diagonal constraints are introduced as regularization terms in the loss function.

Datasets

The paper evaluates Singularformer on eight diverse real-world datasets:

  • Text Classification: R8, BBC, 20NG, IMDb
  • Medical Coding: MIMIC-III 50
  • Protein Structure Prediction: SCOPe95, SCOPe40
  • Computer Vision: CIFAR 100 (images treated as sequences of pixels)

No new benchmarks were introduced; standard datasets were used to demonstrate broad applicability.

Key Insights and Ideas

  • Attention Matrix Singularity is Key: The paper's foundational insight is that the attention matrix is often not full-rank. This mathematical property is the theoretical basis for reducing its complexity.
  • Learning SVD Components: Instead of direct SVD, learning the SVD components via neural networks offers a practical and efficient way to approximate the decomposition.
  • Linearization via Dimensionality Reduction: The core mechanism for achieving linear complexity is by projecting the input into a lower-dimensional "pseudo-vector" space, performing attention there, and then mapping back. This effectively bypasses the $n \times n$ matrix computation.
  • Soft Constraints for Stability: Using regularization for orthogonal and diagonal constraints, rather than hard constraints, allows the model to learn more flexibly while still guiding it towards the desired SVD-like structure.
  • Efficiency for Short Sequences: Singularformer shows significant advantages not just for very long sequences, but also for shorter ones, where some other linear Transformers might not offer substantial benefits.

Key Results

  • Performance: Singularformer achieves comparable accuracy to standard Transformers across all eight datasets, and in some cases, even outperforms them (e.g., on R8, BBC, 20NG, IMDb).
  • Efficiency:
    • Time Complexity: Achieves linear time complexity ($O(n \cdot r)$), significantly outperforming standard Transformers ($O(n^2)$).
  • Space Complexity: Demonstrates substantially lower memory consumption, especially as sequence length increases. For a sequence length of 1024, it uses 26.9% to 56.4% less memory than FLASH, Linformer, and BigBird.
  • Scalability: Singularformer can train 64 sequences of length 4096 in parallel on a single NVIDIA TESLA V100 GPU.
  • Robustness: The model's performance is relatively stable across different values of the learned rank parameter $r$.

Limitations and Future Work

  • Correlation on Complex Datasets: While generally showing high correlation with standard Transformer attention, Singularformer's attention correlation is weaker on very complex datasets like SCOPe95 and SCOPe40. The authors speculate this is due to the inherent complexity of these tasks and potentially insufficient data for learning robust representations.
  • Future Work: The authors suggest exploring Singularformer for large-scale pre-training and multi-modal modeling. They also mention the potential for further investigation into the optimal choice of $r$ and its impact on performance and complexity.

Summary updated

BibTeX
@inproceedings{wu2023singularformer,
  author = {Yifan Wu and Shichao Kan and Min Zeng and Min Li},
  title = {{Singularformer: Learning to Decompose Self-Attention to Linearize the Complexity of Transformer}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/493},
}
Figure