Transformers with Multiresolution Attention Heads
Authors: Tan Minh Nguyen
Tho Tran Huu
Tam Minh Nguyen
Minh Pham
Nhat Ho
Stanley Osher
Venue: Submitted to ICLR 2023 (2023)
Keywords: transformer
multiresolution analysis
attention heads

Abstract: We propose the Transformer with Multiresolution-head Attention (MrsFormer), a class of efficient transformers inspired by the multiresolution approximation (MRA) for approximating a signal f using wavelet bases. MRA decomposes a signal into components that lie on orthogonal subspaces at different scales. Similarly, MrsFormer decomposes the attention heads in the multi-head attention into fine-scale and coarse-scale heads, modeling the attention patterns between tokens and between groups of tokens. Computing the attention heads in MrsFormer requires significantly less computation and memory footprint compared to the standard softmax transformer with multi-head attention. We analyze and validate the advantage of MrsFormer over the standard transformers on a wide range of applications including image and time series classification.

Under review as a conference paper at ICLR 2023
MRSFORMER: TRANSFORMER WITH MULTIRESOLUTION-HEE HEAD ATTENTION NTTENNTTTIOON
Anonymous authors Paper under double-blind review
ABSTRACT
We propose the Transformer with Multiresolution-head Attention (MrsFormer), a class of efficient transformers inspired by the multiresolution approximation (MRA) for approximating a signal using wavelet bases. MRA decomposes a signal into components that lie on orthogonal subspaces at different scales. Similarly, MrsFormer decomposes the attention heads in the multi-head attention into fine-scale and coarse-scale heads, modeling the attention patterns between tokens and between groups of tokens. Computing the attention heads in MrsFormer requires significantly less computation and memory footprint compared to the standard softmax transformer with multi-heat attention. We analyze and validate the advantage of MrsFormer the standard transformers wide range of applications including image and time series classification.
INTRODUCTION
The transformer architectures (Vaswani et al., 2017) is popularly used in natural language process- ing (Devlin et al., 2018; Al-Rfou et al., 2019; Dai et al., 2019; Child et al., 2019; Raffel et al., 2020; Baevski & Auli, 2019; Brown al., 2020; Dehghani et al., 2018), computer vision (Dosovitskiy et al., 3021; Liu et al., 2021; Touvron et al., 2020; Ramesh et al., 2021; Radford et al., 2021; Arnab
et al., 2021; Liu et al., 2022; Zhao al., 2021: Guo et al., 2021: Chen et al., 2022), speech process- ing (Gulati et al., 2020; Dong et al., 2018; Zhang al., 2020: Wang et al., 2020b), and other relevant applications (Rives et al., 2021; Jumper et al., 2021; Chen et al., 2021; Zhang et al., 2019; Wang & Sun, 2022). Transformers achieve state-of tet-theearr art performance in many of these practical tasks, and the results get better with larger model size and increasingly long sequences. For example, the text generating model in (Liu et al., 2018a) processes input sequences of up to 1 11,000 tokens of text. Applications involving other data modalities, such as music (Huang et al., 2018) and images (Parmar al., 2018), can require even longer sequences. Lying at the heart of transformers the self-attention mechanism, an inductive bias that connects each token in the input through relevance weighted basis of every other tokens capture the contextual representation of the input sequence (Cho et al., 2014; Parikh et al., 2016; Lin et al., 2017; Bahdanau et al., 2014; Vaswani et al., 2017; Kim et al., 2017). The capability of self-attention to attain diverse syntactic and semantic representations from long input sequences accounts for the success of transformers in practice (Tenney et al., 2019; Vig & Belinkov, 2019; Clark et al., 2019; Voita et al., 2019a; Hewitt & Liang, 2019). The multi- attention (MHA) extends the self-attention by concatenating multiple attention heads to compute the final output as explained in Section 2.1 below.
In spite of the success of the MHA, it has been shown that attention heads in MHA are redundant and tend to Iearn similar attention patterns, thus limiting the representation capacity of the model (Michel al., 2019; Voita et al., 2019b; Bhojanapalli et al., 2021). Furthermore, additional heads increase the computational and memory costs, which becomes a bottleneck in scaling up transformers for very long sequences in large-scale practical tasks. These high computational and memory costs and head redundancy issues of the MHA motivates the need for a new efficient attention mechanism.
1.1 CONTRIBUTION
Levaraging the idea of the multiresolution approximation (MRA) (Mallat, 1999; 1989; Crowley, 1981), we propose a class of efficient and flexible transformers, namely the Transformer with Multiresolution. head Attention (MrsFormer). At the core of MrsFormer is to the novel Multiresolution head Attention (MrsHA) that computes the approximation of the outputs H h = 1...., H. of attention heads in MHA at different scales for saving computation and reducing the memory cost of the

---

Under review as a conference paper at ICLR 2023
model. The MRA has been widely used to efficiently approximate complicated signals like video and images in signal and image processing (Mallat, 1999; Taubman & Marcellin, 2002; Bhaskaran & Konstantinides, 1997), well to approximate solutions of partial differential equations (Dahmen et al., 1997; Qian & Weiss, 1993). While existing works have been proposed to approximate the attention matrices using the MRA (Zeng et al., 2022; Fan et al., 2021; Taoo et al., 2020; Li et al., 2022), our MrsHA is the first method that approximates the output of an attention head, resulting in a better approximation scheme compared other works that try to approximate the attention matrices. Our contribution is fhree-fold:
1. We derive the approximation of an attention head at different scales via two steps: Directly approximating the output sequence H, and ii) approximating the value matrix V, i.e. the dictionary that contains bases of H.
2. We develop MrsHA, novel MHA whose attention heads approximate the output sequences H h 1,...: H, at different scales. We then propose MrsFormer, a new class of transformers that use MrsHA in their attention layers.
3. We empirically verify that the MrsFormer helps reduce the head redundancy and achieves better efficiency than the baseline softmax transformer while attaining comparable accuracy to the baseline.
Organization: We structure this paper as follows: Section 2, we derive the approximation for the output sequence H h ..,.,, H. at different scales and propose the MrsHA and MrsFormer. In Section 3 and 4, we empirically validate and analyze the advantages of the MrsFormer over the baseline softmax transformer. We discuss related work in Section 5. The paper ends up with concluding remarks. More experimental details are provided in the Appendix.
2
TRANSFORMER WITH MULTIRESSOLUTION-IISS ATTENTION
2.1 BACKGROUND: SELF-ATTENTIO
The self-attention mechanism learns long-range dependencies via parallel processing of the input sequence. For a given input sequence X := [x1. ... xN E RNNxx of N feature vectors, the self-attention transforms X into the output sequence H == hh,,".. hxl E NxD, as follows
H = softmax QK
= AV,
where Q : 1q qvl_ K == -.,,... kn] and V == vi.... uN]] are the projections of the input sequence X into three different subspaces spaned by Wq. WR DxD.. and Wy DD.xD. Da,, i.e. Q XWT. K = XWT. k, V XWT. Here, in the context of transformers, Q, K, and V are named the query, key, and value matrices, respectively. The softmax function is applied to row-wise. The matrix A softmax
QK"
E NNN the attention matrix, whose component aij
vD
for i, j j= 1, 1,..., .... from data determines the ability of the self-attention to capture contextual representation for each token. Eqn. (1) is also called the scaled dot-product softmax attention. In our paper, we call transformer that uses this attention the softmax transformer.
N are the attention scores. The structure of the attention matrix A after training
Multi-head Attention (MHA). In MHA, multiple heads concatenated to compute the final output. ( ..... w! E D be the projection Let H be the number of heads and W Wimmli
matrix for the output where (!! (-( D...D. The multi-head attention is defined as
MultiHead(
) = (o
())) Wiilii
H
WAT = Σ (h)
h=1
The MHA enables transformers to capture more diverse attention patterns.
2.2 BACKGROUND: WAVELET TRANSFORM AND MULTIRESOLUTION APPROXIMATIONS
The wavelet transform uses time-frequue frequency atoms with different time supports to analyze the structure of signals. In particular, it decomposes signals over dilated and translated copies of fixed function
2

---

Under review as a conference paper at ICLR 2023
N
A
1,,
(4.1 A)V
4.1
D.
D.
1x
Ln 4et2
4e V
H²
Figure 1: Illustration Eqn. 11 (Left) and Eqn. (Right).
p. dictionary of time- freeufruy atoms is obtained by scaling by s and translating by t:
p
8
KER
Here, controls the dilation, i.c., the scale, and t controls the location, e.g., the time. Using this dictionary of time-frequency atoms, a signal f E LL((R) can be expanded in the following form:
+.0
+
0f (1)) dids.
(4)
The wavelet transform then maps the signal to the coefficient of as follows
L_ f(x) dr,
af = (f,+1))
(5)
where yp is the complex conjugate of yp. The coefficient of captures the measurement the signal f at scale and location (Mallat, 1999).
2.3 TRANSFORMER WITH MULTIRESOLUTIIO ATTENTION
2.3.1 FIRST LEVEL APPROXIMATION: APPROXIMATING THE OUTPUT SEQUENCE H AT DIFFERENT SCALES
of orthogonal expansion functions for possible translations at scale For simplicity, we assume that the sequence length N = 2*. The expansion functions f are chosen be the boxcar functions follows
Let B [1p] E R.W) be where s = 1, 4, ......,,
N. ...,,
oi = 1 if st - < S st
(6)
otherwise
for (1,2,4...,, and (1..... N/s). each scale s, we approximate the columns H|: [. d = 1.....D, D., of the output sequence H as follows
H d H',:d=
Σ aiui
(7)
EF
where the coefficient afd is computed as follows
oa (p; H(:
(8)
Plug Eqn. (1) and Eqn. (8) into Eqn. (7), we obtain
N/a
st
H H d R
[t
Σ
(g)
Hi:
Σ
H dl)
P.
1=1
s11
N/s
Σ
Ali.s]
Vli
30¹
(9)
t=1
i=st-s41 A)V(;dd).
=
((1s,1
(10)

---

Under review as a conference paper at ICLR 2023
Here, we employ the notations for downsampling and upsampling from signal processing. In particular, ts denotes the average pooling by the factor s along the 6 dimension, and t,, denotes the nearest-neighhor interpolation by the factor along the 4 dimension. Applying Eqn. (10) for d ,,..., D,, we achieve the approximation of H at scale follows:
H = H =f.,1 ((ts,1 A)V).
(11)
An illustration of Eqn. 11 is given in Figure. 1 (Left).
Remark (Approximating the columns of H independently) As pointed out in (Nguyen al., 2022), the features H df in the ouput sequence H. as well as the features Vi; d] in the value matrix V. d 1,...,I. Du, in the softmax attention are independent due to the use of the unnormalized Gaussian kernels with the isotropic covariance. This finding justifies our approach of approximating the columns of independently.
Remark 2 (Group-to-token attention) The downsampling bs,1 A of the matrix A in Eqn. (11) computes the attentions befween groups of tokens and individual tokens in the sequence.
2.3.2 SECOND LEVEL APPROXIMATION: APPROXIMATING THE HEAD BASES V AT DIFFERENT SCALES
In Eqn. (11) that approximates the output sequence H at scale by H we further approximate the bases V, i.e., the value matrix, by its approximation at scale s'. Following the derivation in Section 2.3.1 above, we can derive the approximation V [t. d] for the d columns of V as follows
N/5' Σ
Via dJ
Vli.d)
(12)
j=s't's'41
Plugging Eqn. (12) into Eqn. (9), we obtain the second level approximation of the head output H: H d =
H
d
N/a
Níć' Σ
Σ
A
Vli.d))
"pt
i=st-8t 8++1
fm1
jus't
+1
N/s
N/s
st Σ
de' Vib.aD)
A 1lp:
S
s+s
N/a
Nis'
st
Vli ))
Σ
Σ
Ali,a]
88
j= 1441
=fa,1 (1a,,145.2 A)(Eo, V(=.d)).
(13)
Same as above, by applying Eqn. (13) for d= I,..,, Dr, we achieve the full approximation of H at scale: of H and scale s' of V follows:
H H =tx,1 (44,,140,2 A) V)).
(14)
An illustration of Eqn. 14 is given in Figure. 1 (Right). Given the approximation Ha.e' of the attention matrix H. we have the following upper bound on the approximation error.
Theorem Assume that 8 > 0 is chosen such that the attention matrix A satisfies the following inequalities |Aij A < 6, |Ai
As.5=1 < for all 1 S i,j < N. Then, we obtain that
H |P (s (s+s'22)NV 28 H
V Vss
where ||-I|æ denotes the Frobenius norm and ||-1|2 denotes the spectral norm of a matrix.
Proof of Theorem 1 is in Appendix B. The result of Theorem shows that the approximation matrix H approximates H exactly when s' = 1, which is true. In the coarsest scale when 8 = N, the upper bound achieves the maximum value (N V)l||V
Remark (Group-to-groul attention) The downsampling 1a,1 A the the matrix in Eqn. (14) computes the attentions between groups of tokens and groups of tokens in the sequence.
4

---

Under review as a conference paper at ICLR 2023
D2
W
W
Q (h)
Q
WrlhT
D
N
(h)
D3
X
w
V(b)
D
D
D,
Wo
87 MrsHA((E)
hh-1)
Figure 2: Illustration of Eqn. 17.
2.3.3 EFFICIENT DOWNSAMPLING OF ATTENTION MATRIX A
As shown in Eqn. (1), A = softmax
OK
Since the softmax function needs access to the full vD
matrix QK downsampling A via average pooling still requires to compute the full product QK VD-
vD first. In order to avoid this redundant computation, we propose to compute the lower bound of this average pooling (due to the convexity of the exponential the softmax function). particular, we approximate the downsampling of A as follows:
te,14e',2 A softmax 4w.14''2 2 (QK))
softmax (Nh,1 Q)(ko, K T)
(15)
VD
VD
2.3.4 TRANSFORMER WITH MULTIRESOLUTION- HEAD ATTENTION: EACH HEAD APPROXIMATES THE ATTENTION AT A DIFFERENT SCALE
In this section, we formally define our Multiresolution- head Attention (MrsHA) and Transformer with Multiresolution-hett Attention (MrsFormer). MrsHA combines Eqn. (14) and (15) to implement the approximation of the output sequences (h), / 1,...,It H,, at different scales and s'.
Definition (Multiresolution-hee) Attention) Let И be the number of heads and Wmide D.DDD. be the projection matrix for the head outputs where O E DDDDs, Given a set of scales (8(1), g(h) 1 for the output Hh) and the value matrix (h)), h 1, H, at each head, the MrsHA is efficient attention mechanism that computes the approximation of (h) at scale (h)) using an approximation of V()) at scale s((h) by the following attention formula:
((1)
(H)
w()) ((H)
H
1a0,,1 ssotmmxx (Hhaa,,) Q)Crroo K)T " (barno v(al) Wha..
MrsHA
Σ
DD
h=1
(16)
The MrsFormer the class of transformers that use the MrsHA in their attention layers.
Remark 4 (Downsampling Q, K, and V) Downsampling Q K, and V can be efficiently imple- mented by downsampling the input sequence X before projecting it into the query matrix Q the key matrix K, and the value matrix V via the linear transformations W N. W K. and Wv. respectively. the Eqn. (16) of the MrsHA then becomes MrsHA((H))L
H
(Ham,))
(W Q
Mooorn (N) ) (L010)) XW(hT)) WHaT..
1
softmax
DD
(17)
An illustration of Eqn. 17 is given in Figure. 2.
5

---

Under review as a conference paper at ICLR 2023
Remark 5 (Choosing s(h and (((h) ((h) and s(() are hyperparameteers that can be tuned for each head. In our experiments, we use s(h) g((h) 26th) where k(h) an integer.
Remark 6 (Choosing the expansion functions oi and 1-D convolution) In order to derive the MrsHA in Eqn. (16), we have chosen the expansion functions op to be the boxcar functions. Other expansion functions, such as the wavelet bases the triangular functions, can be used to derive different forms of the MrsHA. In a general case, the average pooling and the nearest-neighhor interpolation in Eqn. (16) and (17) can be replaced by the 1-D convolution operators with sp as the corresponding filters.
3 EXPERIMENTAL RESULTS
In this section, we empirically justify the advantages of our propsed MrsFormer model. We compare the performance of the MrsFormer with the baseline softmax transformer, the MRA-2 (Zeng et al., 2022), and the MRA-2-s (which is the sparse version of the MRA-2) on various benchmarks. Unlike our method, the MRA-2 and MRA-2-s perform multiresolution analysis for each head by approximat- ing the attention matrix by blocks of different scales, while the MrsHA in our MrsFormer computes the approximation of each head H at a specific scale. The benchmarks studied in our experiments include 10 tasks from the UEA time series classification dataset (Bagnall et al., 2018), 3 tasks from Long Range Arena (Tay et al., 2021b) (LRA) benchmark, and ImageNet image classification task (Russakovsky et al., 2015). In addition, we also study the performance of the MrsHA when being combined with other attention mechanism such as the linear attention (Katharopoulos et al., 2020), the MRA-2 attention, and the MRA-2-s attention (Zeng et al., 2022). We aim show that: (i) the MrsFormer can achieve better or comparable accuracy over the baseline softmax, MRA-2, and MRA-2-s transformers; (ii) the MrsFormer saves significant amount of FLOPs and memory compared to the baseline softmax transformer, and this advantage grows with the sequence length; (iii) the MrsHA can be combined with other attentions to achieve similar or better performance with better efficiency; and (iv) the MrsFormer reduces redundancy between heads comparing to the softmax baseline.
In our experiment, we keep the hyperparameters the same for all models for fair comparisons. All of our results are averaged over 5 runs with different seeds.
3.1
UEA TIME SERIES CLASSIFICATION
Models and baselines. We adapt code from (Wu et al., 2022; Zerveas et al., 2021) for our experiments. Following the same setting from these papers, we set the number of heads and layers to 8 and 2. respectively. For the MrsFormers, we use the same set of scales at each layer, which is given by s = [1, 1, 2, 4, 4, 8, 8). For MRA-2 and MRA-2-s models (Zeng et al., 2022), each head is approximated by blocks of scales [1, 32] as suggested in their paper. The percentage of blocks with scale I in these MRA-2 models is set to 25% of the full attention matrix. Other hyperparameters have the same values as in (Wu et al., 2022) (for the PEMS-SF, SelfRegulationSCP2. and UWaveGestureeLibbaayy tasks) and (Zerveas et al., 2021) (for other tasks)
Results. We summarize the results in Table 1. The MrsFormer achieves bettter test accuracy than the baseline softmax transformer for out of 10 tasks while being much more efficient. Among these tasks, the MrsFormer outperforms the baseline by at least 1% accuracy. For the remaining tasks, besides Handwriting, our model maintains an accuracy gap less than 0.8% compared to the baseline. Our model gets the best accuracy for 4 out of the 10 tasks. In addition, it achieves second best accuracy for 4 out of the remaining tasks. The MrsFormer achieves the average accuracy across all tasks. Note that among heads at each layer, our model computes 6 of them with the size of only 1 I 1 I. 1 and 1 of the size of the corresponding heads in the baseline softmax transformer. 4. 4' 16. T6. 64 Thus, the MrsFormer has a significant smaller FLOPS and memory usage compared the bascline.
54
3.2 LONG RANGE ARENA
Models and baselines. We follow the same settings and adapt code for LRA task from (Zeng et al., 2022), which uses transformer with 2 heads and layers. We choose the same set of scales s = [1, for all the layers in MsFormer.
Results. Table 2 summarizes our results. Although being an approximation of the softmax attention, it is evidently from Table 2 that MrsFormer can consistently achieve better than or comparable accuracy as the baseline softmax attention on the LRA tasks. The MRA-2 and MRA-2-s models (7eng et al.,

---

Under review as a conference paper at ICLR 2023
Table 1: Accuracy (%) of the MrsFormer vs. the baseline softmax transformer on the UEA Time Series Classification task averaged over 5 seeds. The best model for each task is highlighted in bold, while the second best one is underlined. We also include the reported results for the softmax transformer from (Wu et al., 2022) and (Zerveas al., 2021) (in parentheses). The MrsFormer attains the best average accuracy across all tasks while being much more efficient than the baseline softmax transformers.
DATASET / MODEL
BASELINE SOFTMAX MRSFORMER MRA-2
MRA-2-s
32.08 (33.70)
35.87
34.35
34.48
FACEDETECTION
68.70 (68.10) 10)
68.23
68.28
68.24
HANDWRITING
32.08 (30.50)
30.24
29.49
29.68
HEARTBEAT
75.77 (77.60)
78.86
77.24
78.05
VOWNESS
99.46 (99.40)
99.10
99.01
99.01
PEMS-SF
82.66 (82.10)
84.2
86.13
82.85
SELFREGULLAIOONSCI
91.46 (92.50)
91.81
91.70
92.04
DEFREGULATIOONSCS
54.72 (53.90)
56.85
55.56
56.29
SPOKENARARICDIGITS
99.33 (99.30)
98.73
98.60
98.62
UWWVEERRSTURRLLIBR....
84.45 (85.60)
86.67
86.67
86.56
AVERAGE ACCURACY
72.07(72.27)
73.06
72.70
72.58
Table 2: Accuracy (%) of the MrsFormer vs. the baseline softmax transformer averaged over 5 seeds. The best model for each task is highlighted in bold, while the second best one is underlined. The MrsFormer attains the best average accuracy across all tasks while being much more efficient than the baseline softmax transformers.
DATASET MODEL BASELINE SOFTMAX MRSFORMER
MRA-2
MRA-2-5
LISTOPS
36.84 (37.10)
37.52
37.10 (37.2 2)
37.05 (37.4)
RETRIEVAL
79.52 (79.6)
80.22
78.88 (79.6)
79.76 (80.3)
TEXT
64.93 (65.2)
65.05
65.09 (65.4)
64.43 (64.3)
AVERAGE ACCURACY
60.43 (60.63)
60.93
60.36 (60.73) 60.41 (60.67)
Table 3: Accuracy (%) of the MrsFormer DeiT vs. the baseline softmax DeiT and the MRA-2-s DeiT the ImageNet image classification task. The MrsFormer DeiT outperforms the MRA-2-s DeiT and yields comparable accuracy to the softmax DeiT.
MODEL NAME
ToP-1 ACCURACY TOP-5 ACCURACY
SOFTMAX DEIT
72.178
91.126
MRA-2-s DEIT
70.784
90.154
MRSFORMER DaIT]
71.342
90.566
2022) are also included for comparison. Our MrsFormer's performance is comparable with these MRA baselines. Overall, the MrsFormer yields the best average accuracy across the LRA tasks.
3.3 IMAGENET
Models and baselines: this section, we apply the MrsFormer to the Deit model (Touvron et al., 2020) with 4 heads. Since Deit uses special class token [CLS) for the classification, we do not downsample this token along with other tokens in the sequence. For our MrsFormers, we use the set of scales = [1, 2, 2, 4] at each layer. We also study the MRA-2-s attention on this task. As reported in (Zeng et al., 2022), the MRA-2-s is better model than the MRA-2 on the ImageNet image classification task since sparse attention structure is more effective for modeling images.
We present our results in Table 3. The MrsFormer DeiT's top-1 accuracy is about 0.5% higher than MRA-2-s DeiT and is the closest model to the performance of the softmax DeiT baseline. The performance gap of less than 1% of MrsFormer DeiT is very promising for applying the MrsFormer-based model in large scale tasks to reduce the computational and memory cost while maintaining comparable performance with the baseline transformer.
Results:
4 EMPIRICAL ANALYSIS
In this section, we use the models trained on the LRA retrieval task for our analysis.
4.1 EFFICIENCY ANALYSIS
We study the efficiency of MrsFormer over the baseline softmax transformer. Figure 3 demonstrates the reduction ratio of train and test flops of the MrsFormer over the softmax transformer. Although
7

---

Under review as a conference paper at ICLR 2023
A Training
Testing
FLOPS Ratio
120
021 322
1224
3324
040
235
2040 4000 0.6
256
2004 2048
Sequence Length
Sequence Length
Figure 3: Training (A) and inference (B) FLOOP ratios between the MrsFormer and the baseline softmax transformer across different model dimensions D (dim) and sequence lengths N on the LRA retrieval task. The MrsFormer requires fewer FLOPs compared the baseline, and this advantage grows with sequence length for very long sequences. The efficient advantage of the MrsFormer holds for large-scale models with the large D.
A
B Testing
Training
5m 126
cin 120
Memory Ratio
5m
51 4004
0i1 4300
6:7
0.30
0.75
0.70
256 1024
2043
4005
0.65
312
3324
2042
Sequence Length
Sequence Length
Figure 4: Training (A) and inference (B) memory ratios between the MrsFormer and the baseline softmax transformer across different model dimensions (dim) and sequence lengths N the LRA retrieval task.
Table 4: Layer-average mean and standard deviation of La distances between heads of the MrsFormer the softmax transformer trained the retrieval task. The MrsFormer obtains greater distances between heads compared to baseline, indicating that the MrsFormer captures more diverse attention patterns.
MetrieModel
Baseline Sofimux
MisFormer
Mean Std
2.01
2.68
0.39
0.54
in this experiment, only approximate one head with scale 2 and preserve the other head the same as in the baseline, the FLOP saving ratio over softmax attention still ranges from 18% up to more than 36% and grows with sequence length in both the training and testing phases. Figure 4 presents the memory saving ratio of the MrsFormer over the softmax transformer. This figure shows similar trend of more memory saving when the sequence length increases. Our model achieves up to 49% and 31 % decrease in memory usage in the training and testing phases, respectively. This indicates that our model scales well with long sequences and takes significantly less resource than the baseline softmax attention in both training and testing.
4.2 MRSFORMER HELPS REDUCE HEAD REDUNDANCY
To show that the MrsFormer captures more diverse attention patterns, compare the average Ca distances between the heads of our trained MrsFormer model (on the retrieval task) and the softmax baseline. Table reports the layer-average mean and standard deviation of distances between heads. Since the MrsFormer attains higher L2 distances, it reduces the risk of learning redundant heads compared the softmax baseline.
4.3 BEYOND THE SOFTMAX ATTENTION: COMBINING MRSHA WITH OTHER ATTENTIONS
The MrsHa is complementary to many other types of attentions. Therefore, a natural question arises is whether can combine the MrsHa with other attentions besides the softmax attention? To answer this question, we combine the MrsHA with the MRA attention (Zeng et al., 2022) and the linear attention (Katharopoulos et al., 2020) and train these combined models for the LRA tasks (Tay et al.,
8

---

Under review as a conference paper at ICLR 2023
Table 5: Accuracy (%) of the models that combined MIsHa with the MRA and linear attentions vs. the original MRA and linear transformers on the LRA tasks. The combined models are indicated by the prefix "Mrs", results are averaged over 5 seeds (In this experiment, we use the set of scales [1. 2)).
DATASET MODEL
M (MRA-2) MRSMRA-2-S (MRA-2-S)
MRSLINEAR (LINEAR)
LISTOPS
37.05 (37.10)
37.17 (37.05)
36.97 (36.90)
RETRIEVAL
79.24 (78.88)
80.05 (79.76)
81.36 (81.13)
TEXT
64.92 (65.09) .09)
65.21 (64.43)
66,57 (5..6)
AVERAGE ACCURACY
60.40 (60.36)
60.81 (60.42)
61.63 (61.24)
a021a) as in Section 3.2. The results are presented in Table 5. It is interesting to see from Table 5 that all combined models gain an improvement in average test accuracy over the original models despite being an approximation. This observation suggests that the MrsHa can be applied to other attention mechanisms besides softmax reduce computation and memory while maintaining the accuracy of the original models.
5 RELATED WORK
Efficient Transformers. To reduce the quadratic computational cost and memory usage of transform- ers, many efficient transformer models have been developed (Roy et al., 2021). Sparse transformers line of works in this branch, which explore and design the sparsity structure of attention matrix, resulting in more efficient models (Parmar et al., 2018; Liu et al., 201 8b; Qiu et al., 2019; Child et al., 2019; Beltagy et al., 2020). Another class of efficient transformers is patterns integration, combining different attention patterns to cover diverse and wide range of dependencies (Child et al.. 2019; Ho al., 2019). These patterns can be set as pre-specified or learnable during training, along with model parameters (Kitaev et al., 2020; Roy et al., 2021; Tay et al., 2020). In another attempt, multiple tokens can be accessed simultaneously with a side memory module, saving the cost of computing and memory storage(Lee et al., 2019; Sukhbaatar et al., 2019; Asai & Choi, 2020; Beltagy et al., 2020). In different approach, observing that the attention matrices are low-rank, kernelization and low-rank approximation methods have been proposed to replace the softmax attention with more efficient attentions (Tsai et al., 2019; Wang et al., 2020a; Katharopoulos et al., 2020; Choromanski et al., 2021; Shen al., 2021; Nguyen et al., 2021; Peng al., 2021; Jaegle al., 2021). From signal processing perspective, wavelet- based and multiscale methods has been used lately to learn a multiresolution
approximation of self-attention (Zeng et al., 2022; Fan al., 2021: Tao et al., 2020; Li et al., 2022), which flexibly discover the coarse and fine attention patterns, Our approach decomposes the attention heads into coarse- and fine-scale heads, diversely modeling the dependencies between tokens and between group of tokens to reduce the computational and memory costs of the model in both training and testing.
Redundancy in Transformers. Pre-trained transformers contain redundant neurons and heads which can be pruned away for downstream tasks (Dalvi al., 2020; Michel et al., 2019; Durrani et al., 2020). Studying the contextualized embeddings in these pre-trained networks shows the anisotropicity of the learned representation from these models under this redundancy (Mu & Viswanath, 2018; Ethayarajh, 2019). Multiple approaches have been proposed to reduce this redundancy and improve the efficiency of transformers, such as the knowledge distillation and sparse approximation (Sanh et al., 2019; Sun et al., 2019; Voita et al., 2019b; Sajjad et al., 2020). Our MrsHA/MrsFormer represent the attention heads at different scales and are complementary to these methods.
6 CONCLUDING REMARKS
In this paper, we propose the MrsFormer, class of efficient transformers that calculates the approxi- mation of the attention heads at different scales using the Multiresolution-heal Attention (MrsHA). The MrsFormer achieves better computational and memory cost than the corresponding softmax transformers bascline. Furthermore, the MrsFormer helps reduce the redundancy between attention heads and can be casily combined with other attention mechanisms. In the MrsFormer, use the boxcar function to form a set of orthogonal expansion functions. It is natural to further develop the MrsFormer using other basis functions including the popular wavelets. Furthermore, in our derivation of the MrsHA and MrsFormer in Section 2.3, we employ the observation from (Nguyen et al., 2022) that the features H d] in the output sequence H are independent. We leave the extenson of the MrsHA and MrsFormer to capture dependent output features as future work.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Rami Al-Rfou, Dokook Choc, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3159-3166 2019.
Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučié, and Cordelia Schmid. Vivit: A video vision transformer. In 2021 TEEE/CVF International Conference Computer Vision (ICCV), pp. 6816-6826, 2021. doi: 10.1 10.10099CC444992.221...oo 2.0166....
Akari Asai and Eunsol Choi. Challenges in information seeking qa: Unanswerable questions and paragraph retrieval. arXiv preprint arXiv:2010.1191) 2020.
Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. In International Conference on Learning Representations, 2019. URL https:/oppeneviie.nee/fomum id=ByxZX20qFQ.
Anthony J. Bagnall, Hoang Anh Dau, Jason Lines, Michael Flynn, James Large, Aaron Bostrom, Paul Southam, and Eamonn J. Keogh. The UEA multivariate time series classification archive, 2018. CoRR, abs/181 0/bs/1811..000 1.00755, 2018. URL http://arxiv.org/abb// 181 1.00075.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint
2014.
Pierre Baldi, Peter Sadowski, and Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5:4308, 07 2014. doi: 10. 10.1038/ncomms530..
Iz Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint 20Xx:20004.055500 2020.
Thierry Bertin-Mahieux Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011), 2011.
Vasudev Bhaskaran and Konstantinos Konstantinides. Image and video compression standards: algorithms and architectures. Springer Science& & Business Media, 1997.
Srinadh Bhojamapalli, Ayan Chakrabarti, Himanshu Jain, Sanjiv Kumar, Michal Lukasik, and Andreas Veit, Eigen analysis self-attention and its reconstruction from partial computation. arXiv preprint arXiv:21066 08823, 2021.
Jock A. Blackard and Denis Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Com- puters and Electronics in Agriculture, 24(3):131-151, 1999. ISSN 0168-1699, doi: https:
wtt.:/oo/1111111...... 100110066801111119999900666666 1699(99)0004600. URL http::/www..iiieeddddeetctttttee pi/S001811600 16999000040.
Tom Brown, Benjamin Mann, Nick Ryder, Melanic Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. arXiv preprint arXiv:2005. 111220005..11..... 14165, 2020.
Olivier Chapelle and Yi Chang. Yahoo! learning to rank challenge overview. In Olivier Chapelle, Yi Chang, and Tie-Yan Liu (eds.), Proceedings of the Learning to Rank Challenge, volume of Proceedings of Machine Learning Research, pp. 1-24, Haifa, Israel, 25 Jun 2011. PMLR. URL https//ppooceedinss.lmrrrrss
4/chapelle la.html.
Liangyu Chen, Xiaojie Chu, Xiangyu Zhang, and Jian Sun. Simple baselines for image restoration. arXiv preprint 2xXx:2204.004766 2022.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in newral information processing systems, 34:15084-15099 2021.
10

---

Under review as a conference paper at ICLR 2023
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint 1rXiv:1944.105000 2019.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1734, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.31 1.3115////114-112 URL https://www..clwwe.. org/anthology/D14- 1179.
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 performers. In International Conference on Learning Representations, 2021. URL https: "npernvviooane///ooumnii---uuuud
Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. What does BERT look at? an analysis of BERT's attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 276 286, Florence, Italy, August 2019, Association for Computational Linguisties. doi: 10. 11.18653/1/W1--48888
URL hitps:
www..e/weh.ogg/athhoogg//// 19-48888
James L. Crowley. representation for visual information. Technical report, BARNEGIE-MELLLOG
UNIV PITTSBURGH PA ROBOTICS INST, 1981.
Wolfgang Dahmen, Andrew Kurdila, and Peter Oswald. Multiscale wavelet methods for partial differential equations. Elsevier, 1997.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoe Le, and Ruslan Salakhutdi- nov. Transformer-xl: Attentive language models beyond fixed-length context. arXiv preprint arXiv:1901.02860, 2019.
Fahim Dalvi, Hassan Sajjad, Nadir Durrani, and Yonatan Belinkov. Analyzing redundancy in pretrained transformer models. arXiv preprint 2000::2000.04000, 2020.
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals. Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. arXiv preprint arXiv:1807.03819 2018
Jacob Devlin, Ming-Wes Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint
2018.
Linhao Dong, Shuang Xu, and Bo Xu. Speech transforrran... no-recurrence sequence-to-sequemt model for speech recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5884-5888. IEEE, 2018
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL httpss//openreiewwneel Yorum?id-ViebFaNNTYy
Nadir Durrani, Hassan Sajjad, Fahim Dalvi, and Yonatan Belinkov. Analyzing individual neurons in pre-trained language models. arXiv preprint vrXiv:2010.02699 2020.
Kawin Ethayarajb. How contextual are contextualized word representations? comparing the geometry of bert, elmo, and gpt-2 embeddings. arXiv preprint arXiv: 1909.00599 2019.
Haoqi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li. Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer. Multiscale vision transformers. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 6835. 2021.
Jan-Mark Geusebroek. Gertjan Burghouts, and Arool Smeulders. The amsterdam library of object images. International Journal of Computer Vision, 61:103-112, 01 2005. doi: 1023/BB VISI.0000022993558833 13.60.
11

---

Under review as a conference paper at ICLR 2023
Yury Gorishniy, Ivan Rubachev, Valentin Khrulkov, and Artem Babenko. Revisiting deep learn- ing models for tabular data. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 18932-18943. Curran Associates, Inc., 2021. URL http://pooeednngsssnrriicccppppp
Anmol Gulati, James Qin, Chung- -henng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al. Conformer: anvolution-augmentte transformer for speech recognition. arXiv preprint arXiv:2005.08/00 2020.
Meng-Hao Guo, Jun-Xiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R Martin, and Shi-Min Hu. Pot: Point cloud transformer. Computational Visual Media, 7(2):187-199, 2021.
Isabelle Guyon, Lisheng Sun-Hosoya, Marc Boullé, Hugo Jair Escalante, Sergio Escalera, Zhengying Liu, Damir Jajetic, Bisakha Ray, Mehreen Saeed, Michèle Sehag, Alexander Statnikov, Wei-We Wei Tu, and Evelyne Viegas. Analysis of the AutoML Challenge Series 2015-2018, pp. 177-219. Springer International Publishing, Cham, 2019. URL https//bbii.rr1110000///99/ 000100000000007--000000-------00
John Hewitt and Percy Liang. Designing and interpreting probes with control tasks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-IJCNPP), pp. 2733- 2743, Hong Kong, China, November 2019. Association for Computational Linguisties. doi: (0.18653/v1/D19 12755. URL http://www..wwwwb...////tttt////
Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidi- mensional transformers. arXiv preprint 191. 2019.
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Ian Simon, Curtis Hawthorne, Noam Shazeer, Andrew M Dai, Matthew D) Hoffman, Monica Dinculescu, and Douglas Eck. Music transformer: Generating music with long-term structure. In International Conference on Learning Representations, 2018.
Andrew Jaegle, Felix Gimeno, Andy Brock, Oriol Vinyals, Andrew Zisserman, and Joao Carreira. Perceiver: General perception with iterative attention. International conference on machine learning, pp. 4651 166144 PMLR, 2021.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Židek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873).583--58) -889 2021.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pp.
PMLR, 2020.
R. Kelley Pace and Ronald Barry. Sparse spatial autoregressions. Statistics & Probability Letters, 33 (3):291-297, 1997. ISSN 0167-7152. doi: http://oo....o..omo0o000o6777111 URL
Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. Structured attention networks. arXiv preprint arXiv:/702.00880 2017.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.0445// 2020.
Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. KDD'96, pp. 202-207. AAAI Press, 1996.
Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set trans- former: framework for attention- based permutation invvrrian neural networks. In International Conference Machine Learning, pp. 3744-3753. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2023
Yanghao Li, Chao- Yuan Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer. Mvitv2: Improved multiscale vision transformers for classification and detection. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 4804-48 4814, 2022.
Zhouhan Lin, Minwei Feng, Cícero Nogueira dos Santos. Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. A structured self-attentive sentence embedding. CoRR, abs/1703.031300 2017. URL http://arxiv.orr/abbb.. http://wwwrrrrbb///0001111...3 703.03310.
Peter J. Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. International Conference on Learning Representations, 2018a. URL https://oocneiiiiwwwwo/ooonn//// woype//f
Peter Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. arXiv preprint 101.19180...0198, 2018b.
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 Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 10012-10022, 2021.
Ze Liu, Jia Ning, Yue Cao, Yixuan Wei, Zheng Zhang, Stephen Lin, and Han Hu. Video swin transformer. In IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2022.
Xuezhe Ma, Xiang Kong, Sinong Wang. Chunting Zhou, Jonathan May, Hao Ma, and Luke Zettle- moyer. Luna: Linear unified nested attention. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances Neural Information Processing Systems, volume 34, pp. 2441-2453 Curran Associates, Inc., 2021. URL https:/procedings.nurri.ccc paper/2021/file/ 431999cfc6123333 11e11111111000200000 308777880099ba33---- Papp:erd Paper.pdf.
Andrew L. Maas, Raymond E. Daly, Peter Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL https: //ww.adlwehorg/antooogyy 11-1015.
Stéphane Mallat. A wavelet tour of signal processing. Elsevier, 1999.
Stephane G Mallat. A theory for multiresolution signal decomposition: the wavelet representation. IEEE transactions on pattern analysis and machine intelligence, 11(7):674-693, 1989.
Paul Michel, Omer Levy. and Graham Neubig. Are sixteen heads really better than one? In
H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alccé-Bue, E. Fox, and Garntt (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL
Jiaqi Mu and Pramod Viswanath. All-but-the-top: Simple and effective postprocessing for word representations. In International Conference on Learning Representations, 2018. URL https: Coopeneeiee..eefforumiii--e Hid-ouunniid-HHHHHkkkCC..
Nikita Nangia and Samuel Bowman. ListOps: A diagnostic dataset for latent tree learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pp. 92-99, New Orleans, Louisiana, USA, June 2018. Association for Computational Linguistics. doi: 00.18653/1/N1184400 URL
http://www..llloooogg/bb/gg/////
Tan Nguyen, Minh Pham, Tam Nguyen, Khai Nguyen, Stanley J Osher, and Nhat Ho. FourierFormer: Transformer meets generalized Fourier integral theorem. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Tan M. Nguyen, Vai Suliafu. Stanley J. Osher, Long Chen, and Bao Wang. Fmmformer: Effi- cient and flexible transformer via decomposed near-field and far-field attention. arXiv preprint arXiv:2 108. 02347, 2021.
13

---

Under review as a conference paper at ICLR 2023
Ankur Parikh, Osear Täckström, Dipanjan Das, and Jakob Uszkoreit. A decomposable attention model for natural language inference. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pp. 2249 2255, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.1 10.18653/1/D11--- 1244. URL htt.Li/ss//wwwwaalce....nb/bbbb D1161224,
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4055-4064. PMLR, 10-15 Jul 2018. URL http://proccediings www.eeeiiinn............. v80/parmar 8a.html.
Hao Peng, Nikolaos Pappas, Dani Yogatama. Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference on Learning Representations, 2021. URL
Sam Qian and John Weiss. Wavelets and the numerical solution of partial differential equations. Journal of Computational Physics, 105(1):155-175, 1993.
Tao Qin and Yin Liu. Introducing letor 4.0 datasets. ArXiv, 306.259767
Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint a9Xiv:1911, 1.09922, 2019.
Dragomir Radev, Pradeep Muthukrishnan, Vahed Qazvinian, and Amjad Abu-Jbara. The acl anthology network corpus. Language Resources and Evaluation, 47(4):919-944, 2013.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. International Conference on Machine Learning, pp. 8748-8763. PMLR, 2021.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1-67, 2020. URL
http://jmll.org//apers///// 21200077..0.....
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. In International Conference on Machine Learning, pp. 6821-8831. PMLR, 2021.
Alexander Rives, Joshua Meier, Tom Sercu, Siddharth Goyal, Zeming Lin, Jason Liu. Demi Guo, Myle Ott, C Lawrence Zitnick, Jerry Ma, et al. Biological structure and function emerge from scaling unsupervised learning 250 million protein sequences. Proceedings of the National Academy of Sciences, 118(15), 2021.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, .tacl- 1.4.
9:53 68, 2021. doi: 16.1/t2/ a000353. URL
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211225 252,, 2015.
Hassan Sajjad, Fahim Dalvi, Nadir Durrani, and Preslav Nakov. Poor man's bert: Smaller and faster transformer models. arXiv e-prints, pp. arXiv-2004, 2020.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 1910.0/ 108, 2019.
Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention: Attention with linear complexities. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 3531-35399 2021.
14

---

Under review as a conference paper at ICLR 2023
Sainbayar Sukhbaatar, Edouard Grave, Guillaume Lample, Herve Jegou, and Armand Joulin. Aug- menting self-attention with persistent memory. arXiv preprint WwXiv:190.001400 2019.
Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. Patient knowledge distillation for bert model compression. arXiv preprini arXiv::908.000 0935, 2019.
Andrew Tao, Karan Sapra, and Bryan Catanzaro. Hierarchical multi-scale attention for semantic segmentation. arXiv preprint arXiv:2005. 2020.
David Taubman and Michael W Marcellin. JPEG2000 Image Compression: Fundamentals, Standards and Practice. Springer, 2002.
Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse Sinkhorn attention. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 9438-9447.
PMLR, 13-18 Jul 2020. URL http://prooeeeding..mlee www.eeediiing.....r...s..e 1aee1199/ttt 19/tay20.html..
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 Learning Representations, 2021a. URL https: (ippereview..nefformmmiii VeeeiiddgggWWggnreeeee..re grC2k.
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: //openteeiew.nne/formmm/ VyeeaiidddygWgeeeeee
lan Tenney, Dipanjan Das, and Ellie Pavlick. BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 4593-4601, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/
v1/P19- 1452. URL https://www.aclweb.orrg http://wwwww...g/./////////.////
1452.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers distillation through attention. arXiv preprint arXiv:2012.12877 2020.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhut- dinov. Transformer dissection: An unified understanding for transformer's attention via the lens of kemell. arXiv preprint 190..v:900.11700 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in transformer language model. In Proceedings of the 2019 ACI. Workshop BlackboxNI.P: Analyzing and Interpreting Neural Networks for NI.P, pp. 63-76, Florence, Italy, August 2019. Association for Computational Linguistics. doi: 10.18653/v1/W1191 14-444888. URL httpp:/wwww..lllw...o////tttgggt
19-4808.
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 5797-5808, Florence, Italy, July 2019a. Association for Computational Linguistics. doi: 10. 10.18853/v 1/113/111P1-1191 URL hutps//www.attwe.og/aathooooo
1580.
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. arXiv preprint arXiv:1905.09448, 2019b.
Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04760 2020a.
15

---

Under review as a conference paper at ICLR 2023
Yongqiang Wang. Abdelrahman Mohamed, Due Le, Chunxi Liu, Alex Xiao, Jay Mahadeokar, Hongzhao Huang, Andros Tjandra, Xiaohui Zhang, Frank Zhang, et al. Transformer based acoustic modeling for hybrid speech recognition. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6874-6878. IEFF, 2020b.
Zifeng Wang and Jimeng Sun. TransTab: Learning Transferable Tabular Transformers Across Tables. In Advances Neural Information Processing Systems (NeurIPS 2022). 2022.
Haixu Wu, Jialong Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Flowformer: Linearizing transformers with conservation flows. In International Conference on Machine Learning, 2022.
Zhanpeng Zeng, Sourav Pal, Jeffery Kline, Glenn M Fung, and Vikas Singh. Multi resolution analysis (mra) for approximate self-attention. In International Conference on Machine Learning, PMLR, 2022.
pp.
George Zerveas, Srideepika Jayaraman, Dhaval Patel, Anuradha Bhamidipaty, and Carsten Eick- hoff. A transformer-based framework for multivariate time series representation learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery; Data Mining, KDD '21, pp. 2124,2124, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383325. doi: 10. (..11443444548.34444
URL
Qian Zhang, Han Lu, Hasim Sak, Anshuman Tripathi, Erik McDermott, Stephen Koo, and Shankar Kumar. Transformer transducer: A streamable speech recognition model with transformer encoders and mn-t loss. In ICASSP 2020-200220 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7829-7833. IEEE, 2020.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys (CSUR), 52(1):1-38, 2019.
Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun. Point transformer. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 16259-16268, 2021.
16

---

Under review as a conference paper at ICLR 2023
Supplement to "MrsFormer: Transformer with Multiresolation-head Attention"
A ADDITIONAL DETAILS ON THE EXPERIMENTS
A. UEA TIME SERIES CLASSIFICATION
Datasets and metrics The benchmark (Bagnall al., 2018) consists of 30 datasets. Following (Wu et al., 2022), we choose 10 datasets, which vary in input sequence lengths, the number classes, and dimensionality, evaluate our models temporal sequences.
Models and baselines We adapt code from (Wu et al., 2022; Zerveas al., 2021) for our experiments. Following the same setting from these papers, we set the number of heads and layers to 8 and 2, respectively. For the MrsFormers, we use the same set of scales at each layer, which is given by 8 = 1, 2, 2, 4, 4, 8, 8, For MRA-2 and MRA-2-s models (Zeng et al., 2022), each head is approximated by blocks of scales 32] as suggested in their paper. The percentage of blocks with scale 1 in these MRA-2 models is set to 25% of the full attention matrix. Other hyperparameters have the same values as in (Wu et al., 2022) (for the PEMS-SE, SelIRegulationSCPP. and UWaveGiestureLibbrayy tasks) and (Zerveas al., 2021) (for other tasks). Hyperparameters for these tasks are presented in Table 6.
A.2 LONG RANGE ARENA BENCHMARK
Datasets and metries We adopt the tasks: Listops (Nangia & Bowman, 2018), byte-level IMDb reviews text classification (Maas et al., 2011), and byte-level document retrieval (Radev al., 2013) in the LRA benchmark for our experiments. They consist of long sequences of length 2K, 4K, and 4K, respectively. The evaluation protocol and metric the same in (Tay et al., 2021b).
Models and baselines We follow the same settings and adapt code for LRA task from (Zeng et al., 2022), which transformer with 2 heads and layers. We choose the same of scales [1,2] for all the layers in MsFormer. Hperparameters for these tasks are presented in Table 7.
A.3 IMAGE CLASSIFICATION ON IMAGENET
Dataset and metric: We perform classification task on ILSVRC-2012 ImageNet dataset to validate the performance of our model on large dataset. This dataset has 1000 classes and about 1.28 million images.
Models and baselines this section, we apply the MrsFormer to the Deit model (Touvron et al.. 2020) with 4 heads. Since Deit uses special class token [CLLS] for the classification, we do not downsample this token along with other tokens in the sequence. For our MrsFormers, we use the set of scales [1, 2, 2, 4] at each layer. We also study the MRA-2-s attention on this task. As reported in (Zeng et al., 2022), the MRA-2-s is better model than the MRA-2 on the ImageNet image classification task since its sparse attention structure is more effective for modeling images.
B PROOF OF THEOREM
Recall from Eqn. (14) that
H& H =ta,1 ((h,, (lor, V)).
Let T, be the down-sampling operator (matrix multiplication) on the first dimension of a matrix corresponding the scale T, is the Kronecker product (or outer product) between an identity matrix I and the row vector 1 of size x 8, i.e. T, I 60 TT. Under this notation, the s, up-sampling operator is the transpose of T,, In addition, the womn-sampiing operator on the second dimension of a matrix is also T but with the right multiplication instead. Then, we can rewrite the
approximation s follows:
H = T (TT,T (T, V)) = TT
From the above equation, we have
H H (A
T...T..AT. V.
17

---

Under review as a conference paper at ICLR 2023
Dataset
dim. model
dim. feedforward
learning rate
batchsize
SelfRegulationSCP22
512
2048
0.001
16
PEMS- SF
512
2048
0.001
16
UWaveGestureLLibrryy
512
2048
0.001
16
EthanoiConneentattoon
64
256
0.001
128
Handwriting
128
256
0.001
128
Heartbeat
64
256
0.001
128
Japanese Vowels size
128
256
0.001
128
SelfRegulationSCCP size
128
256
0.001
128
SpokenArabicDDigits size
64
256
0.001
128
FaceDetection size
128
256
0.001
128
Table 6: Hyperparameter configuration for UEA time series classification task.
Dataset
embedding dim
hidden dim
head dim
learning rate
listops
64
128
32
0,0001
retrieval
64
128
32
0,0001
text
64
128
32
0.0001
Table 7: Hyperparameter configuration for LRA task.
From the inequality with the Frobenius norm, we have
H-
|F - T. ToleelV
Therefore, it suffices to approximate the upper bound |A TT T. Let A TTT, ATT.. and obviously A contains blocks matrices of the same values. We can rewrite and 6,6" as block matrices of size s': A - [Am,nmm, and A s,ss' (As.s' mm where 0, 1, ... qle./s,,/s, and 0, I,... alen/s'. Note that all elements of A m. have identical value to the average of all elements of the sub-matrix Am.n-
Now decompose the above quantity into sum of Frobenius norms:
A T T, AT T
Σ ElAmm
A m.n 11
Recall that from the hypothesis, we have
|Ai Ait15l S 5, |Aij - Aijil S
(18)
Then, by applying Popoviciu's inequality, we have
Var [X] (M m)²
where m = inf X and M = sup X. Since matrix is finite, the infimum and the maximum become the maximum and minimum respectively. By Assumption 18, we can approximate the upper bound of M m as follows:
(M m)² - (8 - 2)2
Integrate the sum, we find that
qlen klen
(s s' 2)2 2)
A A
When we plug in klen = qlen = N, we obtain simpler version:
8 s s's N
A - 9.66
Vss 2
As consequence, we obtain the conclusion of the theorem.
C ADDITIONAL EXPERIMENTS
C.1 COMBINING MRSHA WITH OTHER EFFICIENT ATTENTIONS
In this section, combine the proposed MrsHA architecture with other efficient attention mech- anisms to demonstrate MrsHA can be combined with other efficient transformer to reduce mem- ory and computation requirements. We our experiments 5 efficient transformer including
18

---

Under review as a conference paper at ICLR 2023
Table 8: Accuracy (%) of the models that combined MrsHa with other efficient transformers versus the accuracy of the original efficient transformers on the UEA Time Series Classification task. The combined models are indicated by the prefix "Mrs", results are averaged over 5 seeds (In this experiment, use the set of scales 1, 2, 4, 4,8, 8).
DATASET MODEL.
MESIIIFORRER (LINPORMER) MESLINEAR (LINPAR)
MRsFMM (PMM)
MESPERFORMER (PIRFORMER)
MRSI.UNA (LUNA)
CRAANOLCONCENTRATION
32.70 (32.95)
35.49 (34.35)
34.47 (34.22)
33.21 (33.59)
33.71 (33.59)
FACEDETECTION
68.83 (68.53)
68.91 (68 (6)
69.53 (68.9) .7))
68.90 (68.96) 96)
68.64 (68.92)
HANDWRITING
32.55 (32.47)
32.98 (33.29)
33.02 (31.57)
30.51 (30.47)
32.94 (32.32)
75.12 (75.12)
75.45 (76.75)
76.42 (75.77)
75.61 (75.93)
75.61 (75.77)
98.56 (98.65)
99.46 (99.28)
99.64 (99.64)
99.01 (99.19)
99.46 (99.46)
PEMS-SP
87.67 (86.51)
83.43 (79.96)
86.9 (82.47)
84.59 (84.59)
81.31 (81.12)
SELI RELL/EGULAAN REGULATIONCPII
92.61 (91.47)
91.13 (91.24)
93.06 (92.26)
91.13 (91.01)
91.24 (90.78)
SELI RTTUNSSNNN
55.19 (57.41)
54.26 (53.33)
54.82 (54.44)
54.44 (55.19)
55.74 (55.37)
SPOKENARABICDIGITS
98.91 (98.88)
98.76 (98.86)
99.48 (99.38)
99.02 (98.84)
99.03 (99.06)
UWAVEGESTURELIBRARY
86.25 (85.62)
82.19 (80.63)
86.46 (85.73)
85.10 (85.00)
86.25 (87.08)
AVERAGE ACCURACY
72.84 (72.76)
72.21 (71.61)
73.38 (72.45)
72.15 (72.28)
72.39 (72.35)
Table Accuracy (%) of models that combined MrsHa with other efficient transformers versus accuracy of the original efficient transformers (in the parentheses) in LRA task. The combined models are indicated by the prefix "Mrs", results averaged over 5 seeds (In this experiment, use the set of scales [1, 2)).
DATASET MODEL
MissLINFORMER (LINFORMER) MIsLINEAR (LINEAR)
MRSFMM (FMM)
MRSPERFORMER (PERFORMER) MESLUNA (LUNA)
LISTOPS
36.93 (36.59)
36.97 (36.90)
37.77 (30.67)
37.12 (36.41)
37.03 (37.02)
RETRIEVAL
78.38 (78.17)
81.36 (81.13)
81.65 (80.91)
78.93 (78.67)
74.54 (69.55)
TEXT
57.39 (56.50)
66.57 (65.69)
68.39 (68.57)
65.20 (65.17)
64.51 (66.13)
AVERAGE ACCURACY
57.57 (57.09)
61.63 (61.24)
62.60 (60.05)
60.42 (60.08)
58.69 (57.57)
Table 10: The resutls of the comparison between MrsFT- Transformer and FT-Transformer. The t symbol denotes that the metric being reported is accuracy (the higher the better), the 4 symbol denotes that the metric being reported is root mean square error (the lower the better).
DATASET / MODEL
FT-TRANSFORMER
MrSFT-TRANSFORME
HOUSING
0.4671
0.468
ADULT INCOME f
85.76
85.87
HELENA 1
37,99
38.23
JANNIS
72.46
72.54
HIGGS
72.50
72.44
ALOFT
95.48
95,52
EPSILON' 1
89.65
89.58
YEAR 1
8.905
8.904
COVERTYPE
96.67
96.84
YAhOO
0.7567
0.7586
MICROSOFT
0.7474
0.7468
Linformer (Wang et al., 2020a), Linear transformer (Katharopoulos et al., 2020), FMM trans- former (Nguyen et al., 2021), Performer (Choromanski al., 2021) and Luna transformer (Ma et al., 2021). All experiments settings in this section follows directly from subsections 3.1 and 3.2 unless stated otherwise.
C.1.1 UEA TIME SERIES CLASSIFICATION
Results in Table 8 presents the accuracy of the combined and original models on the UEA Time Series Classification task. All the efficient transformers in this experiment either maintain comparable performance or experience boost in average accuracy when combined with MrsHA.
C.1.2 LONG RANGE ARENA
In Listops experiments, we increase the number of training step from 5000 to 15000 to ensure convergence for all models. Table 9 further consolidates the advantage of the proposed MrsHA architecture. fact, all the combined models obtain better average accuracy than the original models in the LRA task.
19

---

Under review as a conference paper at ICLR 2023
C.2 TABULAR DATA
We include a diverse set of 11 tabular dataset for our benchmarking: California Housing (Kelley Pace & Barry, 1997), Adult (Kohavi, 1996). Helena (Guyon et al., 2019), Jannis (Guyon et al., 2019), Higgs (Baldi et al., 2014), ALOI (Geusebroek et al., 2005), Epsilon (EP, simulated physies experi- ments), Year (Bertin-Mahieux et al., 2011), Covertype (Blackard & Dean, 1999), Yahoo (Chapelle & Chang. 201 1), Microsoft (Qin & Liu, 2013). We follow all the train settings and use the default set of hyperparameters used in paper (Gorishniy et al., 2021) for all models. For simplicity, omit the ensemble step from paper (Gorishniy et al., 2021). We report average accuracy over random seed for both FT- Transsfffrrer (Gorishniy et al., 2021) and the combined model of MrsHA and FT- Transforrrr which we denote MrssFT-Transformer.
Table 10 evidently shows that our combined model obtained better results in 7 over 11 tasks, while other tasks maintain comparable performance. This result consolidates the benefit of combining MrsHA with other transformer models in a diverse set of tasks.
C.3 EFFICIENCY WHEN COMBINING MRSHA WITH OTHER EFFICIENT TRANSFORMER
For illustration, we present FLOP and memory reduction ratios of train and test phases of our MrsFMM transformer comparing the original FMM transformer for LRA retrieval task in Figure 5. Our model saves up to 35% of the original FLOP and has lower memory footprint, less than 65% and 85% of the original model for training and testing phases, respectively.
A
B
O Training
D Testing
Training
Testing
0.60
0.80
FLOPS ratio
0.75
0.75
Memory rato
6.60
0.74
0.50
0.70
0.70
0.70
0.65
0:65
1024
2010
2350
3234
2244
Sequence Longth
Sequence Length
Sequence Length
Sequence Length
64
dim
128
dm
-im
dmm 6f dmm
188
dn 253
-mm-mmmm-1 512
Figure 5: ieffning-inference FLOP ratios (A-B) and memory ratios (C-D) between the MrsEMM transformer and FMM transformer across different model dimensions and sequence lengths on the LRA retrieval task (8 1, 2).
Training
Testing
80.0
80.0
Accuracy (96)
77.5
77.5
75.0
75.0
72.5
72.5
70.0
70.0
10a
10a
10a
Memory (MiB)
Memory (MiB)
MrsLinear
MrnLuna
MrsPerformer
Mrol informer
MrsFMM
Linear
Luna
Performer
Linformer
Figure 6: Scatter-plots for the relations between the memory usage and accuracy of the MrsHA-based based efficient transformers vs. the baseline efficient transformers (s [1,2]) trained the I.RA retrieval task.
C.4 SCATTER-PLOO FOR THE RELATIONS BETWEEN THE MEMORY USAGE AND ACCURACY OF THE MRSHA-BASED EFFICIENT TRANSFORMERS VS. THE BASELINE EFFICIENT TRANSFORMERS
We have included the scatter-plots for the relations between the memory usage and accuracy of the MrsLuna, Lnforerrr MrsPerformer, MrsL and MrsFMM the Luna, Linformer,
20

---

Under review as a conference paper at ICLR 2023
Performer, Linear, and FMM baselines trained for the LRA retrieval task in Figure 6. We observe that in both train and test cases, the scatter-plos plots of our MrsHA-bast -bssed models are above and on the left of the scatter-plos plots of the baselines, suggesting that our MrsHA- -bssed models more memory efficient while achieving comparable or better accuracies than the baseline models.
21


Reviews:
[{"review_id": "iHE_DyPRq8t", "reviewer": "Reviewer_fFTA", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 multi-resolution based attention mechanism named MrsFormer. Various experiments have been conducted to validate the effectiveness of the proposed method over several baselines", "summary_of_the_review": "OnThe authors needs to better justify the novelty and the motivation of the proposed method. From the introduction, the authors only briefly introduce some technical description without any motivation or rationale of proposing MrsHA. I suggest the authors move the background knowledge parts (e.g., self-attention description) into Sec. 2 then highlight the motivation and justify the novelty.\n\nThe paper also misses many state-of-the-art efficient transformer variants such as Luna, Linformer, Performance, etc.. I suggest the authors include these relevant methods as baselines in the evaluation or better justify the criteria of why selecting the existing baseline methods.", "strength_and_weaknesses": "Strengths:\n* The authors focus on an important problem in sequence modeling\n* The technical details are presented well\n\nWeakness\n* The novelty needs to be further justified\n* The draft needs to be better organized\n* The experiments need to be strengthen", "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": "_eOYvlQpEKv", "reviewer": "Reviewer_sjo4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposes a technique to improve the efficiency of multi-head attention. \nThe idea is to apply the multi-resolution decomposition with orthogonal bases inspired by wavelets to attention matrics or the V matrices. \nThe Haar Wavelet (box-car like) is considered in this paper, resulting in up/down sampling combined with multi-head attention. \nExperimental results show that the proposed method improves FLOPS and memory uses compared to a naive softmax and the block-diagonal attention matrix approximation. ", "summary_of_the_review": "The technical idea is clear. But the novelty and the impact of experimental results are not enough for recommend to accept. ", "strength_and_weaknesses": "(+) Multi-resolution decomposition with orthogonal bases is a well-studied and proven-to-be-effective strategy for approximate signals. A reasonable choice. \n\n(+) The paper reads easily, and straightforwardly. No logical jumps. \n\n(--) Less technical novelty\n\n(--) Less impact in experimental results\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "Roijn7mcEn", "reviewer": "Reviewer_VX4u", "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 explores the idea of using wavelet transform to compress the input data length to achieve the approximation of attention map and value matric in a Transformer. The experimental results show that it outperforms some state-of-the-art methods. And the proposed method performs better computational and memory cost than the vanilla Transformer.", "summary_of_the_review": "The paper proposes an improved model of Transformer, Multiresolution-head Attention, to reduce computation and memory overhead. The proposed method is more efficient through additional experiments and complexity analysis than the original Transformer. However, the experimental part lacks a comparison with the algorithmic complexity of existing methods. The overall organization of the paper is clear.", "strength_and_weaknesses": "The proposed approach has higher computational efficiency and lower memory overhead than the original Transformer at the cost of a small amount of performance. Although the proposed method is more efficient than the current version of the vanilla Transformer, a comparison with the computational efficiency and memory cost of existing methods is missing.", "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": {}}]

Author rebuttal:

Decision: Reject