Transformer and its variants achieve state-of-the-art results by capturing contextual information from the entire sequence using the self-attention mechanism. Each self-attention block takes three matrices, namely \(Q\)  (query), \(K\)  (key), and \(V\)  (value), as its inputs. These three matrices will be used to capture the relation between tokens in a given sequence. The computation of attention includes two matrix multiplications, a scaling operation and a softmax operation. The two matrix multiplications introduce the quadratic computational complexity with respect to the sequence length. As transformers are being extensively applied in many areas, the model size increases greatly, together with the lengths of input sequences.
For example, BERT-base [1]} and GPT-3 [2]} have 110 million and 175 billion parameters, respectively. Due to the quadratic complexity of self-attention w.r.t the sequence length, the model complexity is further exacerbated in scenarios with long input sequences. Such considerable workload brings about heavy computational and memory burdens, making it difficult to train and deploy these models, especially for tasks with long input sequences.
