To remedy the full attention's quadratic dependency on the sequence length, several models with sparse attention mechanisms [1]}, [2]}, [3]}, [4]} have been proposed. They successfully reduce the complexity of the attention module to linear or sub-quadratic one, enabling longer sequences for training and inference. Moreover, these variants introduce locality into Transformer, which is a good inductive bias for data like long texts and images. We list some of the representative sparse attention mechanisms in Figure REF  (We flatten the 2D patches of an image into a 1D sequence in Figure REF ). These patterns specify pairs of \(q\)  and \(k\)  vectors attending to one another, and can be regarded as masks on the resultant matrix \(S\) : if a position \((i,j)\)  in the pattern is blank, the element \(S_{ij}\)  at corresponding position in \(S\)  will be ignored in the following calculation. In other words, the impact that token \(j\)  has on token \(i\)  is ignored. For example, in Figure REF , the 6th row contains 3 blue blocks from the 5th column to the 7th column, which indicates that the query \(q_6\)  should attend to \(k_5\) , \(k_6\) , \(k_7\) . We could see that these sparse attention mechanisms share some sparse patterns in common and we mark them with different colors. Our insight is that it is possible to fully exploit the data reuse in these common sparse patterns, which motivate us to design our accelerator enabling hybrid sparse attention mechanisms.
