# Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention

**Authors:** Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, Vikas Singh  
**arXiv:** [2102.03902](https://arxiv.org/abs/2102.03902)  
**Date:** 2021-02-07  
**Summary page:** https://www.summarizepaper.com/en/paper/2102.03902v1/

## Key points

- Transformers are powerful in natural language processing
- Self-attention mechanism is a key component for their success
- Quadratic complexity limits self-attention's application to shorter sequences
- Nyströmformer is proposed as a solution with linear complexity (O(n))
- Nyströmformer can handle longer sequences without sacrificing performance
- Nyströmformer performs comparably or better than standard Transformer in most cases
- Code for implementing Nyströmformer is available on GitHub

## Summary

Transformers have become a powerful tool in natural language processing due to their impressive performance on various tasks. A key component that contributes to their success is the self-attention mechanism which captures the influence and dependencies between tokens in a sequence. Unfortunately, the quadratic complexity of self-attention limits its application to shorter sequences. To address this limitation, the authors propose Nyströmformer - a model that offers favorable scalability with respect to sequence length. This is achieved by adapting the Nyström method to approximate standard self-attention with linear complexity (O(n)). As such, Nyströmformer can handle longer sequences with thousands of tokens without sacrificing performance. The authors evaluate Nyströmformer on multiple downstream tasks using the GLUE benchmark and IMDB reviews dataset and find that it performs comparably or even slightly better than the standard Transformer in most cases. The code for implementing Nyströmformer is available on GitHub for further exploration and experimentation.