  Many studies have been conducted to improve the efficiency of Transformer
from quadric to linear. Among them, the low-rank-based methods aim to learn the
projection matrices to compress the sequence length. However, the projection
matrices are fixed once they have been learned, which compress sequence length
with dedicated coefficients for tokens in the same position. Adopting such
input-invariant projections ignores the fact that the most informative part of
a sequence varies from sequence to sequence, thus failing to preserve the most
useful information that lies in varied positions. In addition, previous
efficient Transformers only focus on the influence of sequence length while
neglecting the effect of hidden state dimension. To address the aforementioned
problems, we present an efficient yet effective attention mechanism, namely the
Dynamic Bilinear Low-Rank Attention (DBA), which compresses the sequence length
by input-sensitive dynamic projection matrices and achieves linear time and
space complexity by jointly optimizing the sequence length and hidden state
dimension while maintaining state-of-the-art performance. Specifically, we
first theoretically demonstrate that the sequence length can be compressed
non-destructively from a novel perspective of information theory, with
compression matrices dynamically determined by the input sequence. Furthermore,
we show that the hidden state dimension can be approximated by extending the
Johnson-Lindenstrauss lemma, optimizing the attention in bilinear form.
Theoretical analysis shows that DBA is proficient in capturing high-order
relations in cross-attention problems. Experiments over tasks with diverse
sequence length conditions show that DBA achieves state-of-the-art performance
compared with various strong baselines while maintaining less memory
consumption with higher speed.
