$O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers

By Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, Sanjiv Kumar. 2020

108 citations recorded by the source corpus.

Transformer networks use pairwise attention to compute contextual embeddings of inputs, and have redefined the state of the art in many NLP tasks. However, these models suffer from quadratic computational cost in the input sequence length $n$ to compute attention in each layer. This has prompted recent research into faster attention models, with a predominant approach involving sparsifying the connections in the attention layers. While empirically promising for long sequences, fundamental questions remain unanswered: Can sparse transformers approximate any arbitrary sequence-to-sequence function, similar to their dense counterparts? How does the sparsity pattern and the sparsity level affect their performance? In this paper, we address these questions and provide a unifying framework that captures existing sparse attention models. Our analysis proposes sufficient conditions under which we prove that a sparse attention model can universally approximate any sequence-to-sequence function. Surprisingly, our results show the existence of models with only $O(n)$ connections per attention layer that can approximate the same function class as the dense model with $n^2$ connections. Lastly, we present experiments comparing different patterns/levels of sparsity on standard NLP tasks.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Yi Tay
2. Mostafa Dehghani
3. Donald Metzler
4. Dara Bahri
5. J. Ainslie
6. William W. Cohen
7. Dacheng Tao
8. Ruslan Salakhutdinov

In Computer Vision and Pattern Recognition

1. Dacheng Tao
2. Yunhe Wang
3. Kai Han
4. Luc Van Gool
5. Yi Tay
6. Jianyuan Guo
7. Mostafa Dehghani
8. Chunjing Xu

In Model Architectures

1. Yi Tay
2. Mostafa Dehghani
3. Donald Metzler
4. J. Ainslie
5. Dara Bahri
6. Santiago Ontañón
7. Yunhe Wang
8. Kai Han

Citations in the corpus

• Big Bird: Transformers for Longer Sequences (2020, background): “We note that this property was also explored theoretically in contemporary work Yun et al. [106].”
• Efficient Transformers: A Survey (2020, background): “We refer interested to (Yun et al., 2020) for some additional theoretical analysis about the expressiveness of the Sparse attention mechanism.”
• MATE: Multi-view Attention for Table Transformer Efficiency (2021, methodology): “Yun et al. (2020a) showed that Transformers are universal approximators for any continuous sequence-to-sequence function, given sufficient layers.”
• One Fits All: Power General Time Series Analysis by Pretrained LM (2023, background): “In the literature on network memorization ability (e.g., Vardi et al. (2021); Yun et al. (2020)), the deep learning model tends to have better memorization ability when feature maps are well separated.”
• Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, background): “[61] Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar.”
• A Survey on Vision Transformer (2020, background): “[141] prove that a sparse transformer with O(N) complexity is enough to reflect any kind of relationship between tokens and can make universal approximation, which provides theoretical guarantees for further research about transformer with O(N) complexity.”