Since the vanilla Transformer is inefficient in processing long sequences, many methods explore to improve the efficiency of Transformer in different ways [1]}.
One direction is computing a sparse attention matrix rather than a dense one by only computing attention on a sparse number of query and key vector pairs [2]}, [3]}, [4]}, [5]}.
For example, Sparse Transformer [2]} is a Transformer variant that combines local self-attention and stride attention.
It uses half of the attention heads to attend tokens within a region and the rest attention heads to attend tokens with certain strides.
Longformer [3]} combines sliding window attention and global attention at certain positions to capture local and global contexts, respectively.
BigBird [4]} further introduces a random attention mechanism that attends several randomly selected pairs of tokens.
However, the token pairs that are randomly sampled or selected by fixed rules may not be helpful for context modeling, which limits the performance of these methods.
<FIGURE>