Connections are Expressive Enough: Universal Approximability of Sparse Transformers
arXiv:2006.04862
Abstract
Recently, Transformer networks have redefined the state of the art in many NLP tasks. However, these models suffer from quadratic computational cost in the input sequence length to compute pairwise attention in each layer. This has prompted recent research into sparse Transformers that sparsify 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. We propose sufficient conditions under which we prove that a sparse attention model can universally approximate any sequence-to-sequence function. Surprisingly, our results show that sparse Transformers with only connections per attention layer can approximate the same function class as the dense model with connections. Lastly, we present experiments comparing different patterns/levels of sparsity on standard NLP tasks.
arXiv comment31 pages, NeurIPS 2020 Camera-ready
References in corpus (13)
- Longformer: The Long-Document Transformer
- XLNet: Generalized Autoregressive Pretraining for Language Understanding
- Generating Long Sequences with Sparse Transformers
- Reformer: The Efficient Transformer
- Big Bird: Transformers for Longer Sequences
- Theoretical Limitations of Self-Attention in Neural Sequence Models
- Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection
- On the Turing Completeness of Modern Neural Network Architectures
- BP-Transformer: Modelling Long-Range Context via Binary Partitioning
- Are Transformers universal approximators of sequence-to-sequence functions?
- On Controllable Sparse Alternatives to Softmax
- SAC: Accelerating and Structuring Self-Attention via Sparse Adaptive Connection
- Low-Rank Bottleneck in Multi-head Attention Models