Transformer-based models are widely used in natural language processing
(NLP). Central to the transformer model is the self-attention mechanism, which
captures the interactions of token pairs in the input sequences and depends
quadratically on the sequence length. Training such models on longer sequences
is expensive. In this paper, we show that a Bernoulli sampling attention
mechanism based on Locality Sensitive Hashing (LSH), decreases the quadratic
complexity of such models to linear. We bypass the quadratic cost by
considering self-attention as a sum of individual tokens associated with
Bernoulli random variables that can, in principle, be sampled at once by a
single hash (although in practice, this number may be a small constant). This
leads to an efficient sampling scheme to estimate self-attention which relies
on specific modifications of LSH (to enable deployment on GPU architectures).
We evaluate our algorithm on the GLUE benchmark with standard 512 sequence
length where we see favorable performance relative to a standard pretrained
Transformer. On the Long Range Arena (LRA) benchmark, for evaluating
performance on long sequences, our method achieves results consistent with
softmax self-attention but with sizable speed-ups and memory savings and often
outperforms other efficient self-attention methods. Our code is available at
this https URL

本文介绍了一种基于二项分布采样的局部敏感哈希（LSH）注意力机制，可以将自注意力的复杂度从二次降到线性。我们在 GLUE 和 LRA 基准测试中测试该算法并发现性能优于标准的预训练变压器模型和其他自注意力方法。