DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention
Authors: Bosheng Qin
Juncheng Li
Siliang Tang
Yueting Zhuang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Efficient Transformer

Abstract: Many studies have been conducted to improve the efficiency of the Transformer from quadric to linear over long sequence conditions. Among them, the low-rank-based methods aim to learn the projection matrices to compress the sequence length, thus achieving efficiency gain. However, the projection matrices are fixed once they have been learned, which compress the sequence length with dedicated coefficients for the tokens in the same position regardless of different sequences. Adopting such input-invariant low-rank 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 of different sequences. In addition, previous efficient Transformers only focus on the influence of sequence length while neglecting the effect of hidden state dimension to achieve further efficiency gain. 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 the information theory, with the 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 and achieves high-order small amount error, optimizing the attention in bilinear form. In addition, theoretical analysis shows that the DBA is proficient in capturing high-order relations in cross-attention problems. Experiments over tasks with diverse sequence length conditions show that the DBA achieves state-of-the-art performance compared with various strong baselines while maintaining less memory consumption with higher speed, demonstrating the effectiveness and efficiency of the DBA.

Under review as a conference paper at ICLR 2023
DBA: EFFICIENT TRANSFORMER WITH DYNAMIC BI- LINEAR LOW-RANK ATTENTION
Anonymous authors Paper under double-blind review
ABSTRACT
Many studies have been conducted to improve the efficiency of Transformer from quadric to linear over long sequence conditions. Among them, the low-rank-based methods aim to learn the projection matrices to compress sequence length, thus achieving efficiency gain. However, the projection matrices are fixed once they have been learned, which compress sequence length with dedicated coefficients for tokens in the same position regardless of different sequences. Adopting such input- input-invariant low-rank projections ignores the fact that the most informative part of sequence varies from sequence to sequence, thus failing to preserve the most useful information that lies in varied positions of different sequences. In addition, previous efficient Transformers only focus on the influence of sequence length while neglecting the effect of hidden state dimension to achieve further efficiency gain. To address the aforementioned problems, we present an efficient yet ef- fective attention mechanism, namely Dynamic Bilinear Low-Rank Attention (DBA), which compresses sequence length by imput-sensitive dynamic projection matrices and achieves linear time and space complexity by jointly optimizing se- quence length and hidden state dimension while maintaining state-of-the-ard per- formance. Specifically, first theoretically demonstrate that the sequence length can be compressed losslessly from a novel perspective information theory, with the compression matrices dynamically determined by the input sequence. Further- more, we show that the hidden state dimension can be approximated by extending the Jahhsson-Lindenseee optimizing the attention in bilinear form. In addition, theoretical analysis shows that DBA is proficient in capturing high-order relations in cross-attention prob- lems. Experiments over tasks with diverse sequence length conditions show that DBA achieves state-of-the-art performance compared with various strong base- lines while maintaining less memory consumption with higher speed, demonstrat- ing the effectiveness and efficiency of DBA.
lemma and achieves high-order small amount error,
INTRODUCTION
The Transformer (Vaswani et al. 2017) has shown immense capabilities in a wide range of areas,
including natural language processing (Dai et al.) 2019), computer vision (Dosovitskiy et al. 2021 time series analysis (Zerveas et al. 2021). and multi-modal tasks (Qin et al. 2022a Yu et 2019) However, the Vanilla Transformer suffers quadratic time and memory complexity.
Liu et al. 2021
raising concerns about its further application scenarios. Therefore, several efficient Transformers have been introduced (Tay et al. (2022). Among them, kernel-based methods have drawn much attention due to their optimization- friendllyi characteristic, which improves the efficiency by using the approximation in the attention mechanism (Katharopoulos et al. 2020 Wang et al.] 2020 Ma et al. 2021] Xiong et al.] [021] Qin et al., /eo2b///horoaask et al. 2021). One popular kernel- based technique is low-rank approximation, which compresses sequence length dimension using the same coefficients for all sequences. For instance, Wang et al. (Wang et al.) 2020) approximated the stochastic matrix in sequence length dimension by using sets of fixed coefficients learned in the training process to calculate the weighted sum of tokens in different positions. Xiong et al. (Xiong et al. 202T) adopted the Nyström method to approximate the attention mechanism to linear complexity, decreasing the sequence length with mean pooling.

---

Under review as a conference paper at ICLR 2023
64
Secuescu Langle $32
91
Suquaria Lengle 4t
10
Ours
Ours
Varila Transfrrer
Vas Transtemer Coulomeer
Synhesker
Unformer
Uneer Townls
Reforner
Relorner
Sirthom Transkmmrr
Liner Tonssarer
50
LocelAtertos
Lecs Arendsn
48
0.8
1.1
14
Reabte Spezd Concared Vanilaa Transfurrer
Reladic Sped Companes es wtt Vanila Transfome"
(a)
(b)
Figure 1: Performance (y-axis, higher is better), speed (x-axis, higher is better), and memory foot- print (circle sizes, smaller is better) of efficient Transformers on the Long-Range Arena benchmark (Tay et al. (021b) compared with Vanilla Transformer (Vaswani et al.) 2017) different sequence length conditions (512 and 4k). DBA could achieve state-of-the-art performance with the high- est speed and lowest memory consumption over various sequence length conditions.
However, the flexibility of low-rank projection in previous methods is limited. The projection ma- trices are pre-determined or fixed after the training process, which compress different sequences by using the same coefficients for tokens in the same position. Such input-invariant low-rank com- pressions ignore the fact that the informative part of a sequence varies from sequence to sequence. Hence, the compression might fail preserve the most informative parts lying in different positions and limit the performance over tasks where the most informative parts of inputs change significantly, such as image-related tasks. addition, previous efficient Transformers only focused on optimiz- ing the sequence length while ignoring the influence of hidden state dimension. The hidden state dimension also contributes to the computation cost and becomes more critical efficiency when processing moderate or short sequences. Previous efficient Transformers that achieve significant memory compression and speed-up rate long sequence conditions could end up with similar ef- ficiency when processing moderate short sequences compared with the Vanilla Transformer, as shown in Figure !
To address the aforementioned problems, we proposed an efficient yet effective attention mecha- nism, namely Dynamic Bilinear Low-Rank Attention (DBA), which compresses sequence length with input-sensitive dynamic projection matrices and achieves linear computation and memory ef- ficiency with bilinear optimization from both sequence length and hidden state dimension. Specif- ically, we first theoretically show that sequence length can be compressed losslessly from novel perspective of the information theory, where the projection matrices are dynamically determined by the input sequence to best preserve the most informative parts. Furthermore, we demonstrate that the hidden state dimension can be approximated by extending the Johmson-Lindenstraus lemma (Arriaga & Vempala, 2006; Lindenstrauss & Johnson 1984) with high-order small amount error. In addition, theoretical analysis shows that DBA is able to capture high-order relations in cross- attention problems, which is crucial to the performance multi-modality tasks.
Extensive experiments over tasks with various sequence length conditions are conducted on three different datasets, including Long-Range Arena (LRA) (Tay et al. (02Tb) as the long sequence benchmark, UEA multivariate time series classification archive (Bagnall et al.. (0188) to evaluate the performance of various sequence lengths, VQA-v2 (Goyal et al. 2017) 7) as the illustrations of DBA in capturing high-order relations. The DBA achieves ofate-of-the-an art performance with impressing speed-up and memory compression rate compared with other competitors over various sequence length conditions, demonstrating the effectiveness and efficiency of DBA in wide range of appli- cations.
Our main contributions be summarized as follows:
2

---

Under review as a conference paper at ICLR 2023
1) We introduce efficient and effective attention mechanism, namely Dynamic Bilinear Low- Rank Attention (DBA), which compresses sequence length by input-sensitive dynamic projection matrices. The DBA achieves efficiency gain over various sequence length conditions with linear time and space complexity by jointly optimizing sequence length and hidden state dimension.
2) Theoretical guarantee from information theory and matrix low-rank approximation demonstrates that DBA has similar capability to the Vanilla Attention with low expected error. addition, theoretical analysis shows that DBA is able capture high-order inter-relations in cross-attention problems.
3) Extensive experiments on tasks with various sequence length conditions show that DBA could achieve state-of- of-thh--fttttttto performance in wide range of applications with impressing efficiency gain. In addition, DBA is superior in capturing high-order relations in the cross-attention task, which outperforms the Vanilla Transformer based MCAN (Yu et al. 2019) with only 12% of parameters in the attention layer.
2 BACKGROUND AND RELATED WORK
2.1 VANILLA TRANSFORMER
The Vanilla Transformer /Vaswani et al. 2017) uses Vanilla Attention as its main algorithm, which is calculated via the softmax weighted sum of all values V concerning weights obtained by the multiplication of Q and K:
QKT
(&(K K, () = softmax
(1)
Vd
Attention (Po(K, Q)V
(2)
Here we define (2 Q) attention map, and later, we will abbreviate P& Q) as P. for simplicity. The Q E Raxd K Rnndd V E Randd and Pa E RR=x where n sequence length and d indicates hidden state dimension. Notice that the time and memory complexity for the Vanilla Attention is proportional dominant, and the influence of d becomes greater when facing moderate short sequences.
O (n²d). For long sequence applications, the impact of n becomes
2.2 EFFICIENT TRANSFORMERS
One kind of Efficient Transformers is by using sparsity. where each token could only access limited perspective fields with fixed or learned patterns, including the local attention (Parmar et al.
2018
Reformer (Kitaev et al. 2020), Sinkhorn Tay et al. 2020), Routing Transformer (Roy et al. ALiBi (Press et al. (022). Learning-te -ooinng-to-iae Hash Attention (LHA) (Sun et al. 2022). YOSO (Zeng et al,
2021
2021 ClusterFormer (Wang et al.). Poolingformer (Zhang et 20221, and Big Bird (Zaheer al.
To make the attention have wider perspective fields, some works concentrate on the inter- actions between near field and far field, such as Focal Attention (Yang al. 202T). FMMformers
2020
(guuenn et al., 2021), Long-Short Transformer (Zhu et al., 202 and Crossformer (Wang et al., 2022).
Another popular approach is kernel-based method, which improves the efficiency of Transformer by rewriting the multiplication in equations T and 2 such Linear Transformer (Parmar al., 2018).
PoNet (Tan et al. 2022). Random Feature Attention (Peng et al. (021). and LARA (Zheng et al., 2022). In (Choromanski et al., 202T; Qin al. 2022b; Chen al. 20216). the authors optimize the softmax kernel with faster reweighting functions. Since the kernels are the approximation in attention matrices, they can also be optimized by low-rank methods, such as Linformer (Wang al., 2020), Luna (Ma et al. 2021) l. and Nyströmformer (Xiong et al. (021). I). In (Zhuang et al.) [0222] Luo ct al. 2021; Kreuzer et al. 2021 Zhou et al. 2022), the authors improve the efficiency of attention kernel by exploring the frequency domain. Some works also focus on the multi-head characteristic in attention mechanism and optimize via reducing the parallel computations, such as FLASH (Hua
al. 2022 and Transformer-MGE (Nguyen al. 2022).
The proposed DBA is most similar to Linformer, which both approximate features Vanilla At- tention to the low-rank matrices and achieve linear complexity. The main differences in four
3

---

Under review as a conference paper at ICLR 2023
folds. First, the low-rank projection matrices in DBA are more flexible than in Linformer, which dynamically determined by the imput sequence rather than fixed after training to best preserve the most informative parts of sequence. Secondly, DBA could process sequences in various lengths as the dimensions of sequence length compression matrices are also determined by the input. Thirdly, various sequence length
DBA could achieve state-of-the-art performance with high efficiency conditions due to jointly considering the sequence length and hidden state dimension. Furthermore, DBA is proficient in capturing high-order relations with multi-stage interactions, whereas Linformer could only perform one mtast interaction.
METHOD
Our goal is design efficient attention mechanism with linear complexity, where the analysis starts with the Vanilla Attention defined in equations and 2 In Section [3.] we will theoretically demonstrate that the input sequence length can be compressed losslessly from the perspective of information theory. lcading to linear complexity in both time and space. In Section 3.2 we will extend the Johnson-Lindenstraaue lemma prove that the multiplication between Q and K can be reduced by low-rank approximation with high-order small amount error in the results, mitigating the impact of hidden state dimension on efficiency. In Section 3.3 will present the source of matrices newly introduced to DBA and show that the sequence length compression matrices are dynamically determined by the input features, leading to adaptive coefficients for tokens in the same position. In Section 3.4 we will show that DBA could capture high-order inter-relations in cross- attention problems and perform multi-stage interactions within a single attention layer.
3.1 OPTIMIZE THE SEQUENCE LENGTH WITH INFORMATION THEORY
In this section, we will optimize the quadric complexity of sequence length to Transformer by ana- lyzing the attention mechanism from the information theory perspective, leading to linear complex- ity in both time and space. Specifically, we will show that the attention matrix Pa E _axx could be replaced by set of smaller matrices without information loss.
Note that in the Vanilla Attention, Pg is deterministic for dedicated QK" Hence, we could derive that the conditional entropy between QKT and Po is O.
QK? Vd
H(P QKT) (softmax
QKQQ =0
Therefore, QK" contains all the information P. has. Notice that QK" could be reconstructed losslessly with the based of QK" and the reconstruction coefficients. Hence, the conditional en- tropy between the bases of QK" with reconstruction coefficients to the P is O.
HPp basis, (basis (QK")) W W =0
(4)
where basis, and basis, calculate the basis QK" the row and column spaces, respectively. W and W are the reconstruction coefficients for row and column, which values and dimensions are determined by QKT
From the properties of matrix rank in multiplication, we could get the following inequality.
Rank (QK")= < max (Rank (Q), Rank (K)) S min (n, d)
(5)
where Rank() calculates the rank of matrix.
Hence, the dimension of basis, rusiss,(asiss (basis, (K* are larger than (niin Therefore, with the help of equation given Pa can be represented losslessly with matrix P E Rd xd (dp < min (n, d)) and reconstruction coefficient W Ra and W e Raxd, practice, we could form:
P W
(6)
where P', W and W' are determined by the input and learned through the training process.
4

---

Under review as a conference paper at ICLR 2023
Softmax
X
d
K
)
W
Softmax
(+
QunA
x di Koza
)
Vera
Multi-Haad Attantion
DBA
Figure 2: Illustration of the algorithm of Vanilla Attention versus DBA. Compared with Vanilla Transformer /Vaswani et al., 2017), the Q, K in DBA are compressed to low-rank alternatives with bilinear form in both sequence length and the hidden state dimension. The DBA has the same input and output as Vanilla Transformer by using reconstruction matrix W which easily makes DBA plug and play with existing Transformers. The labels on the row and column of squares represent the dimension of features.
Here, could project Q E Ruxd K Baxd Qi RRaxd Kr E Rd to generate the Ps'. with Qi with K as the input for equation
| Therefore, we could derive the following equation:
QiKY
Ps = W.P''.' = W softmax
W
Vd
(W.Q)(K' W.
W.
softmax
W
Vd
where W, Rd W. x W E R"xd, and W' E Ruxd,
By proposing Pa' as the new attention map instead of Po. we avoid quadric complexity in time and space in attention map generation. However, notice that the reconstruction process using W and W still brings high complexity. Here, we first merge the W' and V first as VDBA then the VDBA is multiplied by Pa' The reconstruction process by W is set in the last. By optimizing the calculation order, the DBA achieves linear complexity.
DBA Q. = (P''P' V)) = W (P'VDBA))
(8)
where VDBA W V E gd
3.2
OPTIMIZE HIDDEN STATE DIMENSION WITH MATRIX APPROXIMATION
we optimize sequence length by analyzing from the information theory perspective, leading linear complexity. In this section, we will further increase the efficiency of DBA by mitigating the impact of hidden state dimension d on efficiency. Specifically, we extend the John- son-Lindenstrauss lemma (Arriaga & Vempala 2006 Lindenstrauss & Johnson 1984) to show the multiplication between Q and K can be approximated with high-order small amount error. Based on the Maansson-iinensstraate lemma, we could derive that when d 2 10log (dp) (c2 following equation holds.
In Section 3.1
c²), the
Pr (,Q) RR ("" (W,Q) K (1)
<
<
(w
K K"W
(9)
The proof details are in Appendix A.1
The equation 9 shows that the multiplication between Q and K could be replaced by alternatives with lower hidden state dimension (d vs. din) and achieves errors in high-order small quantities compared to full-rank multiplication. Therefore, we could further project Qi E 4 xd K, E R4, xd mentioned in Section 3.1 to QDBA x KDBA E xd., and finally, the DBA could be written follows:
DBA K, Q, V) = W/ (( ((sottmax
(R K W (
1) (W::T))
softmmx
Vdin
(10)
QDBAKDBA Vdi..
W
softmax
VDBA
5

---

Under review as a conference paper at ICLR 2023
The attention mechanism is now compressed with bilinear form in both sequence length and the hidden state dimension, increasing the efficiency for sequences with various lengths. The graphical comparison between Vanilla Attention and DBA is illustrated in Figure 2
3.3 THE SOURCE OF MATRICES
In this section, we will define the source of matrices that are newly introduced to DBA in self- attention situation, including the hidden state compression matrix R. the sequence compression matrices W,, W and the reconstruction matrices W". W We will show that the weights in se- quence compression matrices are determined by the input sequence, leading to dynamic coefficients for tokens in the same position between different sequences.
The R compress hidden state with fixed dimension. Therefore, it is set fully connected layer and learned through training. The W W are set as the input sequences propagate thought fully connected layers to obtain the expected hidden state dimension. The W, and W. are generated by combining the input sequence and an extra input Z x in shorter length.
W + (ZQ")
(11)
W 0 (ZK")
(12)
where yo is normalization function to stabilize the training process. In practice, set to softmax function.
Therefore, the compression matrices W, and We are dynamically determined by the input sequence, where every coefficient in W, and W. is the linear transformations of token features in the corre- sponding position. Each row in W, and W. is set of compression coefficients for all tokens in the input sequence, and the results of each position in the final compressed sequences W,Q and K" W. are the different weighted sum of tokens in the original sequence. The weights in the reconstruction matrices W,, W' are also determined by the input, where the rows also represent different sets of coefficients dynamically determined by the input sequence. Note that the dimen- sions for both Wr, We and W" W' are dynamically determined by the input, making them able to process sequences in various lengths without fixed padding. In practice, we set Z as learnable parameters propagating through different attention layers.
3.4 CAPTURE HIGH-ORDER RELATIONS IN PROSS-ATTENTIE
In this section, we will show that DBA is able to capture high-order relations with multi-stage interactions within an attention layer the cross-attention situation. We will first introduce the cross-attention algorithm in Vanilla Transformer and then compare it with the proposed DBA.
The cross-attention in Vanilla Transformer shares the same expression as self-attention in equations 1 and 2 The only difference is input. In cross-attention, one input X; from H1 is processed as QI. and the other imput X₂ from H2 is processed as K2, V2, where the subscript 1, indicate the variables in different hierarchies, and H,, H2 denote different hicrarchies. By leveraging the Vanilla Attention algorithm, Qı is fused with K2, leading to one-stage interaction within an attention layer.
Q1K2 Vd
Cross-Attention (K2, Q1, V22 softmax
V2
(13)
The DBA takes different inputs compared with Vanilla Attention in cross atteentttnn Instead of taking the full-length features X₂ as K2. Vz, DBA takes the compressed sequence W,2X, as Zi K2, and V2. Both models take X, as Q1.
As Wr2 formed K2, V/2 are already been compressed, we only need to compress sequence length in Q1 using WT1, which is obtained from Z,
Firstly, we compress sequence length following Section 3.1
W,1 ((zIf))= ((Linear W (1,2
(14)
where Lincar() denotes fully connected layer.
The advantages of using W,2X2 Z are in two folds. First, the features from two different hierarchies interact when generating W.,. Second, it compresses the sequence length of Q2 where the compression coefficients are guided by features in H2.

---

Under review as a conference paper at ICLR 2023
Table I: Speed and peak memory consumption of different models byte-level text classification with various sequence lengths (256, 512, 1k, 2k, 3k, and 4k). The average performances on the LRA task listed the right. The best model is made bold.
Speed
f
Peak Memory Usage
Model
Avg.
256
512
1k
2k
3k
4k
256
512
1k
2k
3k
4k
Vanilla Transformer
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
58.57
Local Attention
1.0
1.1
1.1
1.7
3.2
5.3
0.94
0.75
0.49
0.29
0.19
0.14
49.51
Linformer
1.0
1.2
1.2
1.9
3.7
5.5
0.90
0.70
0.44
0.21
0.18
0.10
$6.47
Reformer
1.0
0.6
0.5
0.4
0.7
0.8
1.21
1.06
0.70
0.37
0.28
0.24
$4.59
Sinkhorn Trans,
0.9
1.0
1.1
1.6
2.9
3.8
0.92
0.76
0.55
0.31
0.21
0.16
53.89
Synthesizer
1.2
1.2
1.1
2.9
1.06
0.91
0.76
0.75
0.74
0.74
57.95
Cosformer
0.9
1.0
1.0
2.8
1.24
0.58
0.28
0.25
0.19
55.23
Linear Transformer
3.7
1.16
0.44
0.22
0.15
$4.35
Performer
1.1
1.2
3.8
0.89
0.74
0.44
0.22
0.15
55.73
Luna
1.0
1.2
1.2
3.7
5.5
0.88
0.70
0.44
0.23
0.17
0.10
61.46
DBA
1.1
1.4
4.1
0.84
0.38
0.19
0.15
6.221
Table 2: Performance the LRA benchmark. The DBA is trained with 5 random seeds, and the average scores with accuracy variances are reported. The best model made bold.
Model
ListOps 1
Text 1
Retrieval
Image
Pathlinder
Avg.
Vanilla
(Varwani
42
Local Attention
Parmnar el a.
2013
15.82
52.98
70.65
41.46
66.63
49.51
Sparee
Sinkhorn
Tay cl AUK0
33.67
61.20
65 88
41 41.23
67.45
53.89
Lincar Transformor
Kaliiaopooooo
75.30
Reformer
Kilacy el a..
2020
37.27
56.10
73.03
38.07
68.50
$4.59
cosformer
70.33
Fnet Lee
Thurp al. 21
35.33
65.11
$9 61
38.67
77.80
$5.30
Performer
loromaansk
Longfornker
Betrag
2020
35.63
62.85
68. 32
42.22
69.71
55.75
Linformer
Wane
35.70
38
Synthesizer
Tay 0t
202
36.99
61.68
80 04
41.61
69.45
$7.95
Bird
7ancer
36.05
64.02
76.41
40.83
74.87
$8.44
Nyströnformst Xiinne of
2021
37.15
65.52
79. 36
41.58
70.94
$8.95
YOSO (Zeny
37.40
64.28
77.61
44.67
71.86
$9.16
Scallerbran (C hen 20
38.60
64.55
43.65
69.91
59.39
Pixelffy
2122
37.65
66.78
80.55
42.35
72.01
$9.87
Luma Ma Ma cl
37.43
65.74
79.38
46.39
78.36
61.46
DBA
38.
18.10:0044
06.25:+0.04
80.64:10.01
46.51=t0.00
79.56:10.10
62.21
After sequence length compression, we optimize the impact of d on efficiency following Section 3.2 and finally, we could get (QDBA)1. (DD2))2 and (VDBA)2 to perform second interaction be- tween two features as in equation 10 Therefore, DBA could capture inter-relations in the sequence compression matrices generation procedure and attention mechanism within single attention layer, where the compressed feature in H2 interacts with original and compressed features in Hj, making DBA able to capture high-order relations and perform multi-stage interactions.
EXPERIMENTS
We evaluate the performance of DBA on three datasets, covering long and diverse sequence condi- tions with self- and cross-altention tasks, including Long-Range Arena (LRA) (Tay et al. (02 | as the benchmark on long sequence, UEA multivariate time series classification archive (Bagnall et al. 2018) to evaluate performance performance of cross cross-attention. The detailed descriptions of datasets are in Appendix A.2 and the experiment settings are listed in Appendix A.3 A.3
various sequence lengths, VQA-v2 (Goyal et al. 2017) to test the

---

Under review as a conference paper at ICLR 2023
Table 3: Performance the UEA multivariate time series classification archive. The best model is made bold.
Task/ Model
Transformer
Linformer
Performer
Linear
Cosformer
Flowformer
DBA
Ethamolconcentration
32.7
32.6
31.2
33.5
31.9
33.8
35.411.11
Facedetection f
67.3
67.0
67.0
67.1
67.0
67.6
68.7.10.3
Handwriting
32.0
28.9
32.1
34.7
34.7
33.8
35.1.10.1
Heartheat
76.
76.1
78.0
75.6
76.6
77.6
78.0+11.4 1.0
Japanese vowels
98.6
98.1
99.2
99.2
98.9
99.6:1..1
Pems-Sf f
82.3
80.9
80.9
83.8
84.1+0.3
Selfregulationsepl
91.8
91.5
91.8
92.5
92.
Selfregulattonsee22
53.9
57.2
56.7
55.6
56.1
58.1+0.3
Spokenarabicdigits
98.4
98.8
98.4
98.8
98.0
98.8
99,5+0.1
Uwavegesturelibraayy
85.6
84.7
85.3
85.0
85.0
86.6
87.4+0.1
Average Accuracy
71.9
71.8
71.9
72.2
72.4
73.0
73,9+00.4
4.1 EFFICIENCY
The efficiency of DBA compared with Vanilla Transformer and other efficient Transformers illustrated Figure and Table We report the speed and peak memory usage of different atten- tions in 256-4k sequence lengths. The DBA achieves sfte-of-the-are efficiency in terms of speed and peak memory usage, which faster than the Vanilla Transformer and consumes fewer memo- ries over various sequence conditions. In the long sequence conditions, DBA is 6. times faster than Vanilla Transformer and only uses 9% of memory in 4k sequence length. As for shorter sequence length, DBA could also achieve the highest efficiency among others, with 1.4 times faster and only uses 66% of memories compared to the Vanilla Attention in 512 sequence length. The DBA only falls behind the Synthesizer when facing 256-sequence length in terms of speed. However, DBA uses much less memory with much-suppressed efficiency on the long sequence condition. In ad- dition, DBA achieves the best among others in terms of average performance on the LRA task, demonstrating the effectiveness and efficiency of DBA.
4.2 PERFORMANCE ON LONG SEQUENCE MODELING
We evaluate long sequence modeling performance of DBA and the previous methods on the LRA benchmark, as listed in Table The DBA achieves state-of-the ofttt--o-th--arttt performance in terms average score. By closer observation of each individual task, DBA achieves the best results on three out of five individual tasks. Notably, DBA suppresses Vanilla Transformer and previous low-rank- based methods in all five tasks and is exceptionally proficient in image-related tasks where the most informative parts change significantly for different inputs. Note that DBA has the fastest speed and lowest memory consumption in all tasks, demonstrating the effectiveness and efficiency of DBA.
4.3 PERFORMANCE ON TIME SERIES SIGNAL IN VARIOUS LENGTH
We use UEA multivariate time series classification archive evaluate the performance of models various sequence lengths. The results are illustrated Table 3 The DBA achieves the best performance compared with previous methods in all 10 tasks, with 2.3% improvement the av- erage accuracy compared with the Vanilla Transformer, highlighting the capability of processing sequences in various lengths.
4.4 PERFORMANCE ON CAPTURE CROSS-ATTENTIO RELATIONS
We use the VQA-v2 dataset to evaluate the performance of DBA in cross-attention tasks. The results are shown Table 4 Compared with the previous methods, where the image and question interact per layer, DBA could capture high-order relations between hierarchies and perform multi-stage stage interactions within an attention layer, making DBA achieve the best results on the VQA-v2 tasks in all four evaluation aspects with only 12% of parameters compared with Vanilla Transformer based
8

---

Under review as a conference paper at ICLR 2023
Table Performance on the val split VQA-v2 dataset. nPara denotes the number of parameters in attention layers. The best model is made bold.
Model
nPPara 4
All f
Y.N. 1
Num.
Other
MCAN Yu al. 2019
44M
67.17
84.82
49.37
58.48
BAN (Kim
2018
60M
66.00
83.61
47.04
57.62
Linformer Wang el al. 2020
39M
66.19
83.77
48.15
57.61
Performer (Choromanski ct al.
2021
38M
65.64
83.27
46.83
57.21
MCAoAN (Kahman et al. 2021
58M
67.24
84.95
49.51
58.45
DBA
5.2M
68.53-+0.00
85.60++0.07
50.60++0.17
60.30++0.02
Table 5: Efficiency and performance of DBA with state space model on LRA dataset.
S4
Gu et al.
2022)
S4+DBA Speed f
Task
Accuracy
Speed
Memory
Accuracy
Memory
ListOps
59.60
1.0
1.0
59.70
1.3
0.8
Text
86.20
1.0
1.0
85.40
1.2
0.9
Retrieval
90.90
1.0
1.0
91.39
1.4
0.9
Image
87.28
1.0
1.0
86.90
1.5
0.8
Pathfinder
94.20
1.0
1.0
93.98
1.4
0.8
Avg. 1
83.64
1.0
1.0
83.47
1.4
0.8
MCAN (Yu et al. 2019) in attention layer, highlighting the effectiveness of DBA in capturing cross- attention relations.
4.5
PERFORMANCE WITH STATE SPACE MODEL BACKBONE
As different approach from Transformer, the state space model has achieved promising results in long sequence modeling, The state space model takes the similar input X E nnxd as the Trans- former when processing the sequence, with its speed and memory consumption much influenced by the sequence length n1.
The DBA can also be directly plug-and-play to the state space model by compressing the sequence length the state space models need to process from R to IR x to improve the efficiency while maintaining the final performance. lustrated in T The $4 with DBA optimization could achieve 1.4x average speed boost and 0.8x average memory consumption with competitive performance compared to the baseline, highlighting the universality of DBA.
use the S4 (Gu al. 2022) as backbone. The results are il-
CONCLUSION
In this paper, we propose Dynamic Bilinear Low-Rank Attention (DBA), an efficient attention mech- anism that compresses sequence length by input-sensitive dynamic projection matrices and achieves linear time and space complexity by jointly optimizing sequence length and hidden state dimension. Theoretical analysis from the information theory and matrix low-rank approximation perspectives shows that DBA could achieve similar function to Vanilla Attention with high-order small amount error. In addition, DBA is capable of capturing high-order relations in cross-attentie problems. Ex- periments show that DBA is able to achieve state-off of of-the-art performance with faster speed and lower memory consumption compared with previous models, highlighting its efficiency and effectiveness.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rosa I. Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine Learning, 63(2):161-182, 2006. ISSN 0885-6125 1573-0565, doi: 10.1007/s10994-000
Anthony Bagnall, Hoang Anh Dau, Jason Lines, Michael Flynn, James Large, Aaron Bostrom, Paul Southam, and Eamonn Keogh. The uea multivariate time series classification archive, 2018. arXiv e-prints, pp. arXiv: 1.00075, 2018.
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv e-prints, pp. arXiv:2004.05150, 2020.
N. Birbaumer, N. Ghanayim, T. Hinterberger, I. Iversen, B. Kotchoubey, A. Kübler, J. Perelmouter, E. Taub, and H. Flor. A spelling device for the paralysed. Nature, (9866725),,77-298, 1999. ISSN 1476-4687. doi: 10.1038/18581.
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré. Scatterbrain: Uni- fying sparse and low-rank attention. Advances in Neural Information Processing Systems, 34: 17413-17426, 2021a.
Beidi Chen, Tri Dao, Kaizhao Liang. Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Re. Pixelated butterfly: Simple and efficient sparse training for neural network models. In Interna- lional Conference on Learning Representations, 2022. URL htttps:/ net/
Eorum?id-NEF - y7
Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian kernel and nystr)" "om method. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.). Advances Neural Information Processing Systems, volume 34, pp. 1122-2135.. Curran Associates, Inc., 2021b. URL Btss:tttse/////ceiiinoo neurips cc/ Paper. pdf
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv e-prints, pp. 19X4v 10509, 2019.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller. Rethinking attention with per- formers. In International Conference on Learning Representations, 2021. URL https: //openreview ew...w fest//forumiii d= 6zuk 6zuk OWRH
Z. H. Dai, Z. L. Yang. Y. M. Yang. J. Carbonell, Q Le, and R. Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. 57th Annual Meeting the Association for Computational Linguistics (Acl 2019), pp. 99778-988,, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recogni- tion at scale. In International Conference on Learning Representations, 2021. URL. https: 1/openrevis ew. net./ net/ffoumm d=Y cwFdNTTY
Y. Goyal, T. Khot, D. Summers-Star D. Batra, and D. Parikh. Making the in vqa matter: Elevating the role image understanding in visual question answering. In 2017 IEEE Conference on Computer Vision and Patern Recognition (CVPR), pp. 6325-6334, 2017. ISBN 1063-6919. doi:
10.1109/CVPR.2217.6600
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. International Conference on Learning Representations, 2022. URL. https:
//openrevic ew, net./ fett/forune d=uYLF ozl ol..fooovvlcc. ACA
C. R. Harris, K. J. Millman, S. van der Walt, R. Gommers, P. Virtanen, D. Cournapeau, E. Wieser, Taylor, Berg, N. J. Smith, R. Kern M. Picus, Hoyer, M. H. van Kerkwijk, M. Brett, A. Haldane, J. F. Del Rio, M. Wiebe, P. Peterson, P. MaraantMarchant, K. Sheppard, T. Reddy,
10

---

Under review as a conference paper at ICLR 2023
W. Weckesser, H. Abbasi, C. Gohlke, and T. E. Oliphant. Arra programming with numpy. Nature, 585(7825):357-362 2020. ISSN 1476-4687 (Electronic) 0028-0836 (Linking). doi: 1111038/41556--022-666999
K. He, X. Zhang. S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. ISBN 1063-6919. doi: 10.1109/CVPR.2066.000
Weizhe Hua, Zihang Dai, Hanxiao Liu, and Quoe Le. Transformer quality in linear time. In Chaud- huri Kamalika, Jegelka Stefanie, Song Le, Szepesvari Csaba, Niu Gang, and Sabato Sivan (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Series Transformer Quality in Linear Time, pp. 9099-91111 PMLR, 2022. ISBN ISBN.
Huaizu Jiang, Ishan Misra, Marcus Rohrbach, Erik Learned- and Xinlei Chen. In defense of grid features for visual question answering. In 2020 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), Series In Defense of Grid Features for Visual Question Answering, pp. 10264-10273, 2020. ISBN ISBN. doi: 10. 1109/cyp442600222200000000
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mnss: Fast autoregressive transformers with linear attention. III Hal, Daumé and Singh Aarti (eds.), Proceedings of the 37th International Conference Machine Learning, volume 119 of Se- ries Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, pp. 5156- 5165. PMLR, 2020. ISBN ISBN.
Jin-Hwa Kim, Jaehyun Jun, and Byoung-Tak, Zhang. Bilinear Attention Networks, volume 31 of Advances in Neural Information Processing Systems. 2018. ISBN ***************..
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020. URL.htttss::/ppeeeeeee
net/forum? dF
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34:21618 -21629, 2021.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Sori- cut. Albert: A lite bert for self-supervised learning of language representations. In International Conference Learning Representations, 2020. TtRl/httts///ppeeeeett id #1eA7AEtvS
net. fformm?
James Lee-Thorp, Joshua Ainslie, Ilya Eckstein, and Santiago Ontanon. Fnet: Mixing tokens with
fourier transforms. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 4296-4313, As- sociation for Computational Linguistics, 2022. doi: 10. (166:///122222.maccmmaaa
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft coco: Common objects context. In David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars (eds.), Computer Vision ECCV 2014, pp- 740-755. Springer International Publishing, 2014. ISBN 978-3-319-10602-1
W Johnson J Lindenstrauss and Johnson. Extensions lipschitz maps into a hilbert space. Con- temp. Math, 26(189-206):2 1984.
Drew Linsley, Junkyung Kim, Vijay Veerabadran, Charlie Windolf, and Thomas Serre. Learning long-range spatial dependencies with horizontal gated recurrent units. In Proceedings of the 32nd International Conference Neural Information Processing Systems, Series Learning long-range spatial dependencies with horizontal gated recurrent units, pp. 152-164, Curran Associates Inc., 2018. ISBN ISBN.
11

---

Under review as a conference paper at ICLR 2023
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer. Hierarchical vision transformer using shifted windows. In 2021 IEEE/CVF International Conference Computer Vision (ICCV), Series Swin Transformer: Hierarchical Vision Transformer using Shifted Windows, pp. 9992-10002, 2021. ISBN ISBN. doi: 10.1 (ccv48922.20211. 100966.........
Shengjie Luo, Shanda Li, Tianle Cai, He, Dinglan Peng, Shuxin Zheng, Guolin Ke, Liwei Wang. and Tie- Yan Liu. Stable, fast and accurate: Kernelized attention with relative positional encoding. Advances in Neural Information Processing Systems, 14:22795-228097 2021.
Xuezhe Ma. Xiang Kong, Sinong Wang. Chunting Zhou, Jonathan May. Hao Ma, and Luke Zettle- moyer. Luna: Linear unified nested attention. Advances Neural Information Processing Sys- tems, 34:2441 2021.
Andrew L., Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. Proceedings of the 49th Annual Meeting of the Association for Computational I. Linguistics: Human Language Technologies, pp. 142-150. Association for Computational Linguistics, 2011.
Nikita Nangia and Samuel Bowman. Listops: A diagnostic dataset for latent tree learning. Proceed- ings of the 2018 Conference of the North American Chapter of the Association for Computational Linguisties: Student Research Workshop, pp. 92-99. Association for Computational Linguisties, 2018. doi: 11865//11/118-400
Tam Minh Nguyen, Tan Minh Nguyen, Dung D. D. Le, Duy Khuong Nguyen, Viet-Anh Tran, Richard Baraniuk, Nhat Ho, and Stanley Osher. Improving transformers with probabilistic atten- tion keys. In Chaudhuri Kamalika, Jegelka Stefanie, Song Le, Szepesvari Csaba, Niu Gang, and Sabato Sivan (eds.), Proceedings the the 39th International Conference on Machine Learning, vol- ume 162 of Series Improving Transformers with Probabilistic Attention Keys, pp. 16595-16621. PMLR, 2022. ISBN ISBN.
Tan Nguyen, Vai Suliafu, Stanley Osher, Long Chen, and Bao Wang. Fmmformer: Efficient and flexible transformer via decomposed feeldfield and far-field field attention. Advances in neural infor- mation processing systems, 34:29449-29463. 2021.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In Dy Jennifer and Krause Andreas (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Series Image Transformer, pp. 4055 4064. PMLR, 2018. ISBN ISBN.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Ed- ward Yang. Zach Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: an imperative style, high-performance deep learning library, pp. Article 721. Curran Associates Inc., 2019.
Hao Peng, Nikolaos Pappas. Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference Learning Representations, 2021. URL
htttps://cpezzett .wteeeeeeeeete....... net/ htt/://ormmmiieeeeeeme -o
Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables
input length extrapolation. In International Conference on Learning Representations, 2022. URL
htttps://openreve iew net for
Bosheng Qin, Haoji Hu, and Yueting Zhuang. Deep residual weight-sharing attention network with low-rank attention for visual question answering. IEEE Transactions on Multimedia, pp. 1-1, 2022a. ISSN 1520-9210 1941-0077. doi: 10.1 10.1109/mm.2022.317777
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. In International Confer- ence on Learning Representations, 2022b. URL httptt:://ppeeeeeeeess B B18C0rx2Up4
net/ htt./forrmmmi.
12

---

Under review as a conference paper at ICLR 2023
Dragomir R. Radev, Pradeep Muthukrishnan, Vahed Qazvinian, and Amjad Abu-Jbara. The acl anthology network corpus. Language Resources and Evaluation, 47(4):919 944, 2013. ISSN 1574-020X 1574-0218.
doi: 00.10077/100579-00--921111 912-111--2
Tanzila Rahman, Shih-Han Chou, Leonid Sigal, and Giuseppe Carenini. An improved attention for visual question answering. In 2021 IEEE/CVF Conference Computer Vision and Patlern Recognition Workshops (CVPRW), Series An Improved Attention for Visual Question Answering, pp. 1653-1662, 2021. ISBN ISBN. doi: 10.1 h0tp:/pp0..5000822222000005303
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content- sparse attention with routing transformers. Transactions of the Association for Computational Linguis- lics, 9:53-68, 2021. ISSN 2307-387X. doi: 10. 1221///aa
Zhiqing Sun, Yiming Yang, and Shinjae Yoo. Sparse attention with learning to hash. In International Conference on Learning Representations, 2022. URLhttps: http:tppps//peeeeeiee...... www.:neettouuueee id=VGnOJhd501g
Chao-Hong Tan, Qian Chen, Wen Wang, Qinglin Zhang, Siqi Zheng, and Zhen-Hua Ling. Ponet: Pooling network for efficient token mixing in long sequences. In International Confer- ence on Learning Representations, 2022. URL httpt::t/////t http:::://pperevee..o net http://une//oommmeeeeee forum?id- 9jInD9JjicF
Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. In III Hal, Daumé and Singh Aarti (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Series Sparse Sinkhorn Attention, pp. 9438-9447. PMLR, 2020. ISBN ISBN.
Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Rethinking self-attention for transformer models. Meila Marina and Zhang Tong (eds.), Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 of Series Syn- thesizer: Rethinking Self-Attention for Transformer Models, pp. 10183-10192. PMLR, 2021a. ISBN ISBN.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena A benchmark for efficient transformers. In International Conference on Learning Representations, 2021b. URL https: //openzeview. wttp:/te//ooommmdd////epoooeoe
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, ACM Computing Surveys, 2022. ISSN 0360-0300 1557-7341. doi: 10.1145/353081..
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st In- ternational Conference on Neural Information Prucessing Systems, Series Attention is all you need, pp. 6000-6010, Curran Associates Inc., 2017. ISBN ISBN.
Ningning Wang, Guobing Gan, Peng Zhang, Shuai Zhang, Junqiu Wei, Qun Liu, and Xin Jiang. Clusterformer: Neural clustering attention for efficient and effective transformer. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2390-2402. Association for Computational Linguistics. doi: 10. 10.18653/1/2022. acl-long.170
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv e-prints. pp. arXiv:2006.04766 2020.
Wenxiao Wang, Lu Yao, Long Chen, Binbin Lin, Deng Cai, Xiaofei He, and Wei Liu. Cross- former: A versatile vision transformer hinging on cross-scale attention. In International Confer- ence on Learning Representations, 2022. URL httpsss//ppe.eeve...ntttttt wttp://ut/f/o/mtttt.moe/oo.o PHymLIxuI
Haixu Wu, Jialong Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Flowformer: Lineariz- ing transformers with conservation flows In Chaudhuri Kamalika, Jegelka Stefanie, Song Le,
13

---

Under review as a conference paper at ICLR 2023
Szepesvari Csaba, Niu Gang, and Sabato Sivan (eds.), Proceedings of the 39th International Con- ference on Machine Learning, volume 162 of Series Flowformer: Linearizing Transformers with Conservation Flows, pp. 24226-24243 PMLR, 2022. ISBN ISBN.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: A nystrôm-based algorithm for approximating self-attention. Pro- ceedings of the AAAI Conference on Artificial Intelligence. 35(16): 14138)1:::11110 14138-141488, 2021.
Jianwei Yang, Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao.
Focal attention for long-range interactions in vision transformers, Advances in Neural Information Processing Systems, 34:30008-30022 2021.
Z. Yu, J. Yu, Y. Cui, D. Tao, and Q. Tian. Deep modular co-attention networks for visual question answering. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6274-6283, 2019. ISBN 2575-7075 doi: (1109/CVPR.2219.00444
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, and Li Yang. Big bird: Transformers for longer sequences. Advances in Neural Information Processing Systems, 33:17283 0991223--12977, 2020.
Zhampeng Zeng, Yunyang Xiong, Sathya Ravi, Shailesh Acharya, Glenn M Fung, and Vikas Singh. You only sample (almost) once: Linear cost self-attention via bernoulli sampling. In Meila Marina and Zhang Tong (eds.). Proceedings of the 38th International Conference on Machine Learning, volume 139 of Series You Only Sample (Almost) Once: Linear Cost Self-Attenton Via Bernoulli Sampling, pp. 12321-12332. PMLR, 2021. ISBN ISBN.
George Zerveas, Srideepika Jayaraman, Dhaval Patel, Anuradha Bhamidipaty, and Carsten Eickhoff. A transformer-be based framework for multivariate time series representation learning. In Proceed- ings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, Series A Transformer-basee Framework for Multivariate Time Series Representation Learning, pp. 21 14 21 1124. Association for Computing Machinery, 2021. ISBN ISBN. doi: 10. 1 1114/3447548.3467400
Hang Zhang, Yeyun Gong, Yelong Shen, Weisheng Li, Jiancheng Lv, Nan Duan, and Weizhu Chen. Poolingformer: Long document modeling with pooling attention. In Meila Marina and Zhang Tong (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Series Poolingformer: Long Document Modeling with Pooling Attention, pp. 12437-12446. PMLR, 2021. ISBN ISBN.
Lin Zheng, Chong Wang, and Lingpeng Kong. Linear complexity randomized self-attention mech- anism. In Chaudhuri Kamalika, Jegelka Stefanie, Song Le, Szepesvari Csaba, Niu Gang, and Sabato Sivan (eds.), Proceedings of the 39th International Conference Machine Learning, vol- ume 162 of Series Linear Complexity Randomized Self-attention Mechanism, pp. 27011-2700 PMLR, 2022. ISBN ISBN.
Tian Zhou, Ziqing Ma, Qingsong Wen, Xue Wang, Liang Sun, and Rong Jin. Fedformer: Frequency enhanced decomposed transformer for long-term series forecasting. In Chaudhuri Kamalika, Jegelka Stefanie, Song Le, Szepesvari Csaba, Niu Gang, and Sabato Sivan (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Series FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting, pp. 27268- 27286. PMLR, 2022, ISBN ISBN.
Chen Zhu, Wei Ping, Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandkumar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision. Advances in Neural Information Processing Systems, 34:17723- 2021.
Yimeng Zhuang, Jing Zhang, and Mei Tu. Long-range sequence modeling with predictable sparse attention. Proceedings the 60th Annual Meeting of the Association for Computational Linguis- tics (Volume 1: Long Papers), pp. 234-243. Association for Computational Linguistics, 2022. doi: 10. 18653/ 10116553111022///
14

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 PROOF IN OPTIMIZING HIDDEN STATE DIMENSION
lemma. Let R Rdddi I3 din d, with i.i.d. entries from N(0, 1/d).
For any y, IR", we have
Pr XRR' Sc xy x) > 1 2e (e-(2==))
(15)
Based on the Johnson Lindenstraas lemma, we could obtain:
Pr Q||RR k;" -Qk;" Se Qk:") l)
Σ Pr (1 q. k. T q:k; | > 9. (,k 1 2ne (e2-(())) (16)
2 1 -
qi E Q
The K contain n rows. Here we could get:
Pr (I|QRR" -QK" = [<||@]])])
2 -1 Σ Pr Q| k. Qk: / > Qk: 1 >1 - -nne- - -C2-)))nn/ (17)
k K
Hence,
(W.Q) (K Pr (1] RR -K'W))
(K"W)) se | <e]( (K"W"))
(18)
> 22dp² ae
Let din 2 10log (dp) / -et), could derive the equation 9 then theorem follows.
A.2 DATASETS
LRA (Ta et al. 2021b) is a popular benchmark to test the efficiency of Transformers in long se- quence conditions, containing a suite of tasks (ListOps (Nangia & Bowman 22188,, byte-level text classification (Maas et al. (0011, document retrieval (Radev et 2013),, pixel-level image classi- fication (Krizhevsky & Hinton 2009), and Pathfinder (Linsley et al. 2018) with sequence length ranging from 1k to 4k.
UEA multivariate time series classification archive (Bagnall et al. 2018) collection of datasets to evaluate the time series classification algorithms, which contains wide range of problems in various sequence length conditions.
VQA-v2 Goyal et al. 2017) is popular benchmark for multi-mode models, containing 1.1 million huben-labeled image-question pairs with around 13 million associated answers on 200k images from the Microsoft COCO dataset (Lin et al. 2014), and it is split into the train, val, and test set.
Table 6: Summary of experiment benchmarks.
Dataset
Task
Sequence Length
LRA Tay 2021b)
Long Sequence Modeling
lk-4k
UEA Bagnall et al. 2018)
Time Series
29-1751
VQA-v2 Goyal et 2017
Visual Question Answering
5-625
A.3 EXPERIMENT SETTINGS
All the experiments are conducted using PyTorch (Paszke et al, 2019) and Numpy (Harris et al. 2020) with Nvidia GPU.
15

---

Under review as a conference paper at ICLR 2023
For the experiment the LRA dataset, DBA follows the configurations (Ma et al. 202 where all models use the same data processing strategy and model architecture for fair comparisons.
For the experiment the UEA multivariate time series classification archive, select 10 multi- variate datasets similar to (Wu et al. 2022) and use the same configurations following (Zerveas et al,, 2021]. As some of the tasks contain sequences of various lengths, padded the batched imput to the maximum length of the task during training process. During implementation, DBA takes the input without padding as DBA is able to process sequences in various lengths.
For the experiments on the VQA-v2 dataset, we use the ALBERT (Lan et al. 2020) to extract question features, resulting IR 768 embedding for every token in sentence. We the gird image features (Jiang et al., 2020) obtained from ResNet-152 model (He et al. (016) in the vision part. For the tt grid, represented as a feature 2; I 2048 with maximum 608 grid features. After cross-attention interactions, both language and vision parts perform intra autra-modality fusion following YYu et 2019). and the final answer predicted via addition.
For the performance on the state space model, we use the S4 (Gu et al. 2022) as backbone. Our goal is to improve efficiency the state space model while maintaining its performance. Note that DBA first compresses the input sequence from IRx to Rd,xd, then processes compressed feature and finally restores the sequence its original dimension TRaxd Therefore, we could extract the compressed feature in DBA the input of state space model to improve efficiency. We one layer of DBA to compress sequence length of the input, and DBA is plugged after the first layer of the S4 model.)
The detailed settings with paremeerssssssss are listed Tables and 10
Table 7: Experiment settings on the LRA.
Task
Depth
Heads
d
djfn
dp
din
ListOps
6
512
2048
16
24
Text
4
4
256
1024
16
24
Retrieval
128
512
16
24
Image
1
8
64
128
16
24
Pathfinder
1
128
128
16
24
Table 8: Experiment settings the UEA multivariate time series classification archive.
Task
Depth
Heads
d
difn
dp
d
Ethanolconcentration
1
8
64
256
24
Facedetection
3
8
128
256
16
24
Handwriting
1
8
128
256
24
Heartbeat
1
8
64
256
16
24
Japanesevowels
3
8
128
256
16
24
Pems-Sf
1
8
128
512
16
24
Selfregulationscpl
3
8
128
256
16
24
Selfregulattonssc22
3
8
128
256
24
Spokenarabicdigits
3
8
128
256
16
24
Uwavegesturelibraryy
3
16
256
256
24
Table 9: Experiment settings the VQA-v2.
Task
Depth
Heads
d
d
dp
din
VQA-v2
3
256
1024
24
64
16

---

Under review as a conference paper at ICLR 2023
Table 10: Experiment settings for the S4 with DBA optimization.
S4 Configuration
DBA Configuration
Task
Depth
d
Depth
Heads
d
dp
din
ListOps
8
128
4
128
1024
64
Text
6
256
1
4
256
2048
128
Retrieval
6
256
1
4
256
2048
128
Image
6
512
1
4
512
512
256
Pathfinder
256
4
256
512
128
Ban ROCc
Cynamic Weight Himaaaadd
Comprasedi wwrpaaacciipaaaeeeeeeaa
11 Mg
Figure Visualization of sequence length compression matrices. The first column the input sequence. The second column compares the dynamic sequence length projection matrix in DBA and the learned input invariant projection matrix Linformer. The third column illustrates the compressed input by DBA and Linformer, respectively. Different rows represent different input samples.
A.4 VISUALIZATION OF DYNAMIC SEQUENCE LENGTH PROJECTION MATRICES
We visualized the dynamic sequence lengths compression matrices in DBA and compared them with the input invariant compression matrices in Linformer the Selfregulationsepl task (Bir- baumer et al., 1999), as shown in Figure 3, The Selfregulationscpl record the EEG data and is one of the UEA multivariate time series classification archives. Results show that the sequence length projection matrix is determined by the input, which highlights values in different positions for dif- ferent inputs, while Linformer concentrates on the same position for different samples. In addition. the sequence compression matrices in DBA are "smoother" between adjacent positions and have a more noticeable trend than the compression matrices in Linformer. From the characteristics of Selfregulationscpl task and how people diagnose such diseases (Birbaumer et al. 1999), the con- centrated position shall be different for different inputs and share more coherent trends between adjacent points like in DBA rather than oscillate. The DBA process the signals more human - and could achieve higher performance, demonstrating the superiority of dynamic sequence length projection matrices.
17

---

Under review as a conference paper at ICLR 2023
(a) Training loss- Eposh
Val accuracy-Eppe
(c) Val accuracy- accuracy-Training Training loss
Figure 4: Comparison of training loss and validation accuracy of DBA with ablation variants, in- cluding DBA without hidden state dimension compression and DBA without sequence length com- pression.
A.S
ABLATION EXPERIMENTS
We conduct ablation studies on the LRA dataset to investigate the influence of dp and din on ef- ficiency and final performance, as shown in Tables [I] and [2 Results show that both sequence length and hidden state dimension compression contribute to the efficiency, where the sequence length compression contributes higher speed-up ratio with the increase of sequence length (from 1.0x to 5.9x speed-up with 256-4k sequence length), and the compression in hidden state dimension contributes to dedicate speed-up rate (around 1.1x) for all inputs with different length. We also in- vestigate the different settings of dp and din the efficiency, and DBA has faster speed with less memory consumption with the decrease of dp and d.n-
Table 12 illustrates dp and din the final performance. Results show that DBA could achieve sim- ilar performance compared with the counterparts without sequence length or hidden state dimension compression on three out of five tasks on the LRA dataset, which is consistent with our theory that the optimization in DBA is either lossless or with high-order small amount error. The DBA achieves higher performance on the image and pathfinder tasks, which we believe the optimization DBA contributes to the generation capability and ease of optimization. The DBA achieves higher valida- tion accuracy under the same training loss and has faster coverage speed, as detailed shown in Figure 4 Note that DBA is faster and uses less memory than the ablation counterparts without sequence length or hidden state dimension compression, demonstrating the efficiency and effectiveness of DBA.
Different settings of dp and di, to the final performance are also illustrated in Table 12 We set dn 24 for the experiment of dp and dp 16 for the experiments of d Increasing the dp from 8 to 128, DBA achieves higher performances, especially on the retrieval, image, and pathfinder tasks, while keeping similar performances the other two tasks. However, the performance on the pathfinder task drops when increasing the d, to 256. Increasing the di, from to 64, DBA also achieves higher performances on the same three tasks. For the balance between performance and efficiency, we set d, = 16 and din = 24 for all tasks on the LRA dataset, as shown in Table 7
18

---

Under review as a conference paper at ICLR 2023
Table 11: Inference speed and peak memory consumption of DBA with different dp and dia byte-level text classification with various sequence lengths (IK, 2K, 3K, and 4K). The average performances are listed on the right. DBA coverage faster than the controlled groups with higher validation accuracy in the same training loss.
Speed
Peak
Memory Usage
!) 3k
Model
Avg.
256
512
1k
3k
4k
256
512
1k
4k
Vanilla Transformer
1.0
1.0
1.0
1.0
1.0
1.0
58.57
w/o optimize n
1.1
1.1
1.1
1.1
1.1
0.96
0.96
0.96
0.96
0.98
0.99
59.75-0.24 0.24
256
1.1
2.6
1.00
0.97
0.58
0.31
0.25
0.16
62.17=0.20
64
1.3
3.9
5.6
0.87
0.72
0.42
0.21
0.17
0.10
62.26-0.10
16
1.4
4.1
6.1
0.84
0.66
0.38
0.19
0.15
0.09
62.21=0.21
8
1.2
1.4
1.5
2.1
4.2
6.4
0.83
0.65
0.37
0.19
0.15
0.09
61.73 0.28
wlo optimize
1.4
4.0
5.9
0.85
0.68
0.39
0.20
0.16
0.09
60.95-0.32
64
1.1
1.4
1.4
1.9
4.1
5.9
0.84
0.67
0.38
0.20
0.16
0.09
62.26 0.16
dm
24
1.1
1.4
1.4
2.0
4.1
6.1
0.84
0.66
0.38
0.19
0.15
0.09
62.21=0221
12
1.2
1.4
1.4
2.0
4.2
6.3
0.84
0.66
0.38
0.19
0.15
0.09
6.137_0.18
Table 12: Performance DBA on the LRA benchmark with different dp and din-
Model
ListOps
Text f
Retrieval
Image
Pathfinder
Avg. f
Vanilla Transformer
36.37
64.27
78.38
42.44
71.40
58.57
w/o optimize
38.08-03
66.00++0.10
78.53-00.4
0..76+0.54
74.37+0.28
59.75
256
37.53-0.08
66.20:t0.14 14
80.81=0.14
48.03+t0.17
78.30:#0446
62.17=0.20
37040=0.05
17.0011.11
80.69=0.09
46.98:10.09
80.05=0.11
62.26=0.10
38.10-0.40
66.25-40.04
80.64=0.01
46.51+0.50
79.56=2011
62.21=0.21
37.88 0.33
66.016+0.11
80.37-0.19
45.70+0.30
78.65+0046
61.73-0.28
w/o optimize d
37.55-0.25
65.9210.10
79.98-0.19
45.3910.34
75.90-10.3
60.95-0.32
64
37.50-0.05
19.099
80.22=0.13
17.64+0.16
79.76-+0.35
62.26=0.16
dem
24
38.10-0.40
66.25:10.04
80.64=0.01
46.51+0.50
79.56=t0.10
62.21=0.21
12
37.65=0.15
66. 18.1010111
08.14-0.13
46.24:10.66
78.65
61.37=0.18
19


Reviews:
[{"review_id": "ws4hvWlX2U", "reviewer": "Reviewer_tdpB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a low-rank attention mechanism named DBA. Several experiments have been conducted to validate the proposed method's effectiveness.", "summary_of_the_review": "My major concern is about the novelty of the proposed method. It would be great if the authors can make a table to compare the proposed method w/ other low-rank based attention modules on the their differences and why the contribution is not incremental. The authors do mention that the the proposed projection is not pre-determined, it would be better if the authors can better motivate why this pre-determination is not ideal and validate this from experiment results.\n\nThe authors list the hyper-parameters used in Sec. A.2, I wonder how these parameters may affect model performance. It would be better if the authors can conduct more ablation study to analyze the robustness of the proposed approach.\n\nI also suggest the authors to describe how many seeds/repetitions each model has been trained in the experiments and report the accuracy variance.", "strength_and_weaknesses": "Strength:\n* The technical details are presented clearly and with details\n* The experiments include state-of-the-art methods as baselines\n* The paper is structured well and easy to follow\n\nWeakness:\n* The novelty needs to be further justified\n* More ablation studies would be ideal to better understand the model", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pd1rB0qFct", "reviewer": "Reviewer_PZVd", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed to learn the projection matrices for reducing the dimension of intermediate matrices in Transformer models and achieves significant speedup while achieving better performance than previous efficient attentions.", "summary_of_the_review": "In summary, the method in this paper is novel and interesting, while some minor modifications are needed to clarify the paper.", "strength_and_weaknesses": "Pros:\n- The learnable projection in the paper is novel and squeezes the computation not only in terms of sequence length but also in terms of hidden dimension. It is encouraging to see that simply choosing d_p and d_in to be fixed suffices for achieving good performance.\n- The empirical results are promising compared to other linear attention-based models.\nCons:\n- The presentation in Section 3.1 is a little confusing because the W_r' and W_c' depend on the input QK, while Equation (4) makes readers feel they are given.\n- Table 2 in the paper is a little misleading because the methods are not sorted by any meaningful order (e.g., Avg)\n- (Minor) the performance cannot be comparable with new models based on state-space models. It might be helpful to apply similar ideas as this paper to those models to achieve further gain.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gIGXj9eRjQ", "reviewer": "Reviewer_9GWA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a new low-rank method, called DBA, to approximate the attention mechanism used in transformer layers. It has two main differences from previous approaches:\n\n1. DBA maps the input sequences $Q, K \\in \\mathbb{R}^{n \\times d}$ to shorter sequences $Q', K' \\in \\mathbb{R}^{d_p \\times d}$ via a linear transformation that captures information from the input matrix itself, e.g., $Q' = \\phi(WQ^\\top)Q$, where $W \\in \\mathbb{R}^{d_p \\times d}$ are learnable parameters. \n2. DBA also projects queries and key vectors to lower dimensionalities ($d_{in} \\ll d$)\n\nResults show that DBA is faster and consumes less memory than related approaches while achieving strong predictive accuracies on several tasks.\n\n", "summary_of_the_review": "This paper proposes a new efficient alternative to attention in transformers. The proposed method achieves impressive results on several tasks while being time and memory efficient. However, I believe this paper can be improved in terms of clarity and quality, especially regarding the experimental section.", "strength_and_weaknesses": "Things that I liked in this paper:\n\n- The authors explain all the matrix transformation steps in detail, making the linear algebra math easy to follow in section 3.1.\n- The idea of using information about the input sequence before projecting it to a shorter sequence.\n- The results are impressive.\n\nHowever, there are many things that I disliked:\n\n- The overall method is not novel, and most central ideas were proposed in previous approaches (Linformer and Performer).\n- The introduction is very repetitive.\n- Section 3.2 seems unnecessary and confusing. \n- The experimental section is uninformative, especially for sections 4.3 and 4.4.\n- Some math terms are not defined. For example, what is \"Linear\" in Equation 18? Is it needed? What is the actual function used as $\\psi$?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JYyqr_6WJXt", "reviewer": "Reviewer_YUik", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work suggests that the attention matrix, a key module in Transformer but computationally inefficient, can be approximated by low-rank matrix multiplications. Given the arguments, the authors proposed a new efficient Transformer variant using random projections. Experiments, including popularly used LRA benchmarks, are conducted to analyze the empirical performance of the model with comparisons to several baselines.", "summary_of_the_review": "I believe proposing efficient Transformer is essential but the current quality of the work (writing, analysis, empirical results) are not ready to publish in the venue, and I recommend rejection.", "strength_and_weaknesses": "I believe the paper is far below the paper acceptance threshold and here are several critical points that needs to be essentially addressed.\n\n[Writing Quality]\n\nThr writing is rather poor and there are plenty of mistakes. I list some of them as below but there are much more in the paper.\n\n1. In most places, term \"the\" is not correctly used. \n2. In section 3.1, what is non-destructively?\n3. In section 3.1, what is conditional extropy?\n4. In section 3.2, why you call Johnson–Lindenstrauss lemma as \"JS lemma\"\n5. In section 3.2, \"an d \\times d matrix\"\n\n[Math]\n\nA critical flaw occurs in equation (6). It is ok to assume that QK is a low-rank matrix. However, P = softmax(QK), and softmax is a non-linear operator. There is no guarantee that a low-rank matrix passing through a non-linear operator is still a low-rank matrix. Furthermore, in practice, for the softmax function, P is usually a high-rank function. I recommend the authors have a try. Given this, we cannot get P=WrP'Wc, where all of them are low-rank.\n\nNote that in any case, you can always use JK lemma and random projections. But such an analysis has already been used in Linformer.\n\n[Experiment]\n\nThe author missed important effcient Transformer S4 (\"Efficiently Modeling Long Sequences with Structured State Spaces\"). In all of the LRA tasks, S4 is roughly better than the proposed DBA for 25 points. I have little reason to vote a paper for acceptance given the significant performance gap.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject