Several existing accelerators [1]}, [2]}, [3]}, [4]} have been proposed to accelerate the attention computation. FTRANS [1]} compresses its model with the block-circulant matrix-based weight representation, but brings no sparsity to the quadratic attention computation. \(A^3\)  [2]} accelerates the attention mechanism by dynamically selecting the elements in the key matrix that are more likely to influence the dot product of \(q\)  and \(k\) . However, this method stores the whole preprocessed key matrix on the SRAM buffer, making it difficult to scale up when the memory storage is insufficient given long input sequences. SpAtten [3]} adopts coarse-grained pruning techniques to prune tokens and heads. However, its relatively low pruning ratio leads to low sparsity and cannot effectively reduce the input size when the sequence length is long. Sanger [4]} approximates the attention mechanism by masking out elements below the threshold in the predicted score matrix \(\hat{S}\) . The pre-computation of the mask will be expensive in the case of long sequences due to the quadratic attention matrix multiplications. Moreover, these methods introduce intrusive modification of the attention mechanism to leverage the sparsity. Users need to tune task-specific parameters for a suitable trade-off between accuracy and speed. Our work, in contrast, can accelerate the attention computation with long input sequences efficiently and fit in various sparse attention mechanisms without any modification of the algorithm.
