FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention
Authors: Tan Minh Nguyen
Vai Suliafu
Stanley Osher
Long Chen
Bao Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Efficient attention
near-field and far-field decomposition
fast multipole method

Abstract: We propose FMMformers, a class of efficient and flexible transformers inspired by the celebrated fast multipole method (FMM) for accelerating interacting particle simulation. FMM decomposes particle-particle interaction into near-field and far-field components and then performs direct and coarse-grained computation, respectively. Similarly, FMMformers decompose the attention into near-field and far-field attention, modeling the near-field attention by a banded matrix and the far-field attention by a low-rank matrix. Computing the attention matrix for FMMformers requires linear complexity in computational time and memory footprint with respect to the sequence length. In contrast, standard transformers suffer from quadratic complexity. We analyze and validate the advantage of FMMformers over the standard transformer on the Long Range Arena and language modeling benchmarks. FMMformers can even outperform the standard transformer in terms of accuracy by a significant margin. For instance, FMMformers achieve an average classification accuracy of $60.74\%$ over the five Long Range Arena tasks, which is significantly better than the standard transformer's average accuracy of $58.70\%$.


FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention
Tan M. Nguyen Department of Mathematics University of California, Los Angeles Los Angeles, CA, USA
Vai Suliafu
School of Computing
Scientific Computing and Imaging (SCI) Institute University of Utah, Salt Lake City, UT, USA
Stanley J. Osher
Department of Mathematics
University of California, Los Angeles, Los Angeles, CA, USA
Long Chen Department of Mathematics University of California, Irvine Irvine, CA, USA
Bao Wang
Department of Mathematics
Scientific Computing and Imaging (SCI) Institute University of Utah, Salt Lake City, UT, USA
Abstract
We propose FMMformers, a class of efficient and flexible transformers inspired by the celebrated fast multipole method (FMM) for accelerating interacting parti- ele simulation. FMM decomposes particle-particle interaction into near- near-field and far-field components and then performs direct and graiined computation, respectively. Similarly, FMMformers decompose the attention into near-field and far-field attention, modeling the near-field attention by banded matrix and the far-field attention by low-rank matrix. Computing the attention matrix for FMM- formers requires linear complexity computational time and memory footprint with respect to the sequence length. In contrast, standard transformers suffer from quadratic complexity. We analyze and validate the advantage of FMMformers over the standard transformer on the Long Range Arena and language modeling benchmarks. FMMforrmrs can even outperform the standard transformer terms of accuracy by a significant margin. For instance, FMMformers achieve an average classification accuracy of 60. 74% over the five Long Range Arena tasks, which significantly better than the standard transformer's average accuracy of 58. 70%.
1 Introduction
Transformers [58] have achieved state-of-ther art performance in sequence processing tasks, including
machine translation and language modeling [58 2 15
4 61 16 9.. Also. transformers can effectively
transfer knowledge from a pre-trained model to tasks with limited supervision (43 44 16, 64 (34).
Transformers rely on the attention mechanism and particularly self-attention a fundamental building block for their modeling
58 27
1.1 Self-attention
The self-attention mechanism is used to learn range dependencies while enabling parallel
processing of the input sequence. For a given input sequence X : [z), .2. [NN] E IR Nx D. of
'Equal contribution and Co-first author
Please correspond to: wangbaonje @ gmail.ccm chenlong math.uci.edu
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

N feature vectors that have been encoded in Dz-dimensional vector space, self-attention transforms X into an output sequence V in the following two steps:
Step 1. Project the input sequence X into three matrices via the following linear transformations
Q = xW K XWW;V = XWV.
where WQ. Q. WK DxD, and Wv D2 are the weight matrices. We denote
qNN K ........ kN]", and v [U1.... uN]", where the vectors q: ki, U2 for i = 1, ... N are the query, key, and value vectors, respectively.
Step 2. For each query vector qi for = 1,... ..... .N, we compute the output vector é; as follows
q h
V= QK V
softmax
AV,
(I)
where the softmax function is applied to each row of the matrix (QK
For long sequences, the computational time and memory footprint of transformers are dominated by ① It evident that the memory is O(N2) store the attention matrix A. Also, the computational complexities of computing the matrix-matrix products QK and AV are both ((N)). These limitations impede the application of transformers to many important settings that involve very long sequences 33 25
39]. When applying self-attention for long sequence modeling, we have to limit the context window to a reasonable size to make it computationally feasible, limiting the effectiveness of learning long-range dependencies. Efficient transformer models have been proposed, including leveraging sparse and low-rank attention. Many of the existing efficient transformers gain computational and memory efficiency at the cost of significant accuracy degradation.
1.2 Contribution
Leveraging the idea of the fast multipole method (FMM) 19 and expressive transformers, namely FMMformers. At the core of FMMformers to replace the self-attention V AV in with the following matrix-man matrix product
we propose a class of efficient, flexible,
V =D+
(2)
where D is banded matrix with bandwidth is < N and L is a low-rank matrix of rank r N. In practice, we normalize matrix D + L such that the sum of each row is 1; for the sake of presentation, we ignore this normalization step below. Both DV and LV can be computed with linear computational and memory complexity; they model the near-field and far-field attention, respectively. FMMformers are flexible in designing the sparse banded matrix and the low-rank matrix for modeling near-field and far-field attention. In particular, we can control the bandwidth of the banded matrix D and the rank of the low-rank matrix for expressivity and efficiency tradeoff. In addition to the efficiency and flexibility, FMMformers gain significant accuracy improvement over linear transformers and can even outperform standard transformer in terms of accuracy. We illustrate the idea of FMMformers in Figure IT Instead of modeling the full attention by dense unstructured matrix, we employ a sparse banded matrix to model the near near-field attention and several rank one matrices to model the far-field attention.
Full attention
Near-field attention
Far-field attention
Figure Left- hant- side: we visualize a randomly selected full attention map (the matrix A in from the standard transformer trained for the CIFARIO image classification task in the Long Range Arena (LRA) benchmark. Right-hand side: we illustrate how this atlention map can be decomposed into near-field and far-field attention, which modeled sparse banded matrix and the sum of several rank matrices in FMMformer, respectively.

---

1.3 Organization
We structure this paper as follows: In Sec. we briefly review the celebrated FMM and establish the connection between FMM and self-attention. In Sec. we present a practical implementation of FMMformer that leverages existing techniques for low-rank approximation of the self-attention mechanism. We validate and empirically analyze the efficiency and accuracy of FMMformers in Sec. 4 We discuss related works in Sec. [ The paper ends up with concluding remarks. Technical prools and more experimental details are provided in the Appendix.
2 Fast Multipole Method and Self-attention Mechanism
In this section, we review FMM and present an algebraic interpretation of FMM, see Sec. 2.1 Then, in Sec. 2.2 we explore the structure of the attention matrix, showing that FMM can be used to accelerate the self-attention mechanism.
2.1 Fast multipole method vs. sparse and low-rank matrix approximation
FMM is numerical method that was originally developed to speed up the calculation of long- range forces in the n-body problem [9] and has been regarded as one of the top 10 algorithms in scientific computing in the 20th century [1]. The key idea is that the far-field interaction can be well-approximated by separable low-rank matrices, while the near-fiel interaction can be calculated directly. We use the following simple example illustrate mathematical reasoning. Without ambiguity, we reuse notations in the previous section and assume:
k;)) depends the distance of two vectors qi and kj, where A(i is the (i,j)-th entry of the matrix A N
(A1) A(i,j) = o( q:
(A2) The function gs) is smooth for + O.
(A3) The function satisfies ( = (t))
One noticeable example in the physical application is the gravitational potential g(1q: k 1/1q: - k for which the key vectors { are the location of source particles and the query vectors {q: are the location of the target points. Assumption (A3) is not essential, which is presented here for the convenience of proof and can be replaced by other separable forms, e.g., g(s) = g(s) + g(t). The near-field and far-field are defined through the distance |g: kzl-
We now explain the low-rank approximation based on the well-separated condition. For illustrative purpose, we assume the index set 21, ,N is partitioned into two groups T2}.
Definition 1. Group T1 is called well well-separated from T2 if there exists a vector k* and number 8 E (0, 1) such that
kg
k- S 10g
kk" Vi Ei T2.
The vector k" is representative vector of (kj,j E T2), e.g., the center of vectors in T2. For any qe, i E Ti, it far away from [kj j E T2} and the far-field interaction A j), E Ti, j E T2 can be approximated by o(14 k=)), i.e. each row of A(T1, T2), the submatrix of A with the row index set Ti and the column index set T2, is constant. For example, when calculating the gravitation of a galaxy from the Earth, we can simply treat the galaxy as one single point, although the galaxy may contain hundreds of millions of stars. By including terms of the Taylor series, the approximation can be more accurate by using rank p instead of rank 1 matrix approximation.
Lemma 1. Let (Ti, T23 be two well-separated index sets. Assume (A1)-(33 hold. For any > the sub-matrix A(T,, T2) can be uniformly approximated by a rank matrix to a tolerance E > 0 in the sense that: there exists rank p matrices U E IR Tilx,, , V E Talx,, with p 2 C| logs e| for some positive constant C. such that
A(i.))- - (UV
WETTeeTT
The applicability of the analytic kernel function g was limited to partial differential equations or integral equations where Green's 's function satisfying (A1)-(A3). In the application of machine learning, it is hard to verify (A1)-(A3) Instead, we use the definition of matrices from the book 6 Definition 1.10]. We use MATLAB/Numpy notation tri((K,)) to denote the lower triangular matrix with zeros above the pth suhhsuuddaagona of K and similar notation triu K,y) for the upper triangular part.
3

---

Definition 2. 16 Definition I.10] A matrix A E RNNN is called (p, seeemi---eea if there exist
matrices U, V XV and W Z Nx such that
A = trin(UVT
tril Z ,1).
is called seagoonnl-plus--smm--e--e--e
if
D triu(UV ,1) (Wil ,))
with some diagonal matrix D.
Definition can be naturally extended to include a banded matrix D and sum several low-rank matrices. Moreover, One verify the semi-separable property of matrix K by checking the decay of singular values of the matrix. As often used in low-rank approximation methods, numerical rank or e-rank of matrix K, for tolerance e, is the number of singular values of K that are greater than K 12-
The low rank approximation relies on the well separateness of two subsets. Based on hierarchical partition of the index set, H-mmarix [1] can constructed; see Figure an illustration. Further compression leads to -mamia 20 22 and the hierarchically semi-separable (HHS) matrix [1] 62
Other variants include hierarchically block-separable (HBS) [36]. and hierarchically off-diagonal low-rank (HODLR) [3] matrices, etc.
In our application, we write the decomposition
A A Σ di (Q 1=1
(3)
In the query and key spaces, the vectors qi and k, may not be well-separated. Then nonlinear feature maps (b) 1, 1......... to higher dimensions, which are trainable, can be used make the mapped datasets more separable. In (3), each kernel function 61
R is a vector function of length N. We can mimic the hierarchical decomposition used in H-matrix to use low rank kernel approximation di (Q(11 N/2, o) (K/N2 + N,:) with halved length. Such approximation can be recursively applied to get multilevel decomposition the low rank approximation component. Our numerical results show that simple one level wear-field and far-field decomposition is good enough.
Figure 2: A H- H-mmarix based on hierarchical decomposition of the index set. The red part is banded matrix and the green part can be written as sum of low rank matrices.
1.2
1.0
0.8
Singubr
0.0
E0.4
0.0g
50
160
240
160
245
Index
Index
600
600
8
400
400
200
200
200
200
100 150 200 Rank
250
50
200
150
200
10 20 Rank
Rank
Rank
Figure 3: First row: plot of randomly selected attention matrices (left) and their singular values (right) from the transformer trained for WikiText- 103 language modeling; see Sec. [4.3 for details. Second row: distributions of the rank of randomly selected 1000 attention matrices, from the same transformer. after removing banded matrix D of bandwidth (not remove anything from the matrix A), 5, 10, and 20 (from left to right). Matrix
A D is of low rank, and the rank becomes smaller in general when the bandwidth of D inereases.
2.2 Sparse and low-rank patterns in attention maps
In this section, we explore the sparse and low-rank structure of the attention matrix A. particular, consider the attention matrix A e 256xx56 obtained from the standard transformer trained for

---

WikiText- 103 language modeling; see Sec. 4.3 for the experimental details. We randomly select 1000 different attention matrices, and exclude banded matrix D with bandwidth 5, 10, and 20 from each of such matrices. Then, we perform singular value decomposition (SVD) to compute the rank of each matrix A D, and we threshold the small singular values with a magnitude of 10-6. Figure (top row) plots two randomly selected self-attention matrices and the distribution of the rank of the matrix A D. is clear that matrix A has only a few large singular values and all other singular values are very small. Moreover, matrix A D is of low rank, and the rank becomes smaller in general when the bandwidth of D increases, which consistent with the assumptions in Sec. 2.1 motivating FMMformers.
3 FMMformer: Practical Near-field and Far-field Attention
In this section, we present practical algorithms for implementing the proposed FMMformer defined by (2). In particular, we present fast algorithms for computing the near-field attention DV and the far-field attention LV.
3.1 Banded matrix modeling of near-field attention
We model the gear-field attention with the following banded matrix
D softmax (banda
QK
(4)
VD
where the operator band, (*) represents taking only the banded part of the matrix * with bandwidth (k < N). In practice, there is no need to calculate the matrix product QKT. Instead, we only need to calculate the products of the vectors that correspond to the nonzero entries of the banded matrix band QKT /VD). Note that for long sequences, both the time and memory complexity of computing are (KkN).
3.2 Low-rank matrix modeling of far-field attention
We consider practical and efficient low-rank matrix modeling of the far-field attention LV in (I. In principle, any existing off-the-shelf low-rank attention can be integrated into FMMformer to model the far-field attention. In particular, we model the far-field attention by leveraging the kernel trick used in 226 13 47,, which is flexible in selecting different kernels to modulate the rank of the far-field attention.
3.2.1 Low-rank attention via kernelization
Suppose we model the far-field attention using rank matrix L E NxN, which can be written as the sum of rank one matrices, i.e.,
L = abb + azb, +... a,
(5)
where a 022 a,; bi, b2
b, R.V. Note that
LV ba + azb + .... + a. b, V = a1 + +2z6, + +....++a(((( +0
(6)
which indicates that we can compute LV with (r-N) time complexity. Also, we only need to store the vectors u1 u, V., v, E N. resulting in linear complexity in memory footprint.
We borrow the idea of kernelization from the linear transformer (26) for practical implementation of (6). In particular, the authors in 26 generalize the softmax function in ( to a general kernel function k(g;, k,). i.e.
6, = 1 exp(qi, kjju,
Σ j= k(gi, kz)U;
6, =
(7)
Σ exp(q;,k))
Σ k(q k;))
self-attention
generalized self-attention
If kiq,,,,)) ((q.) (kk,) for a certain feature map Φ(-). then we have
ΣE ki k;
En ((q:) (k;)) ((q)) T Ex (kz)
0, Ejn klgit k;))
(8)
Σj T ((g.)T Σソ=1 (kk))
Here, exp(g: k,) exp(a] k//
5

---

Note that 8 can be regarded as a rank one approximation of self-attention. We can rewrite 8 the following compact form
into
V of (QQ)(( (Q))((K)
(9)
To generalize { to the rank r approximation, we select a set of linearly independent feature maps (db(-))]=1- Together with the sparse banded matrix modeling of the near-field attention, we propose the following efficient attention model for the FMMformer
(o(())) VVV)
= DV
(10)
(r(Q)ri(K)
is evident that both computational time and memory complexity are linear in computing (TO). Our design is flexible selecting feature maps and the sparse banded matrix, which the users can customize. Moreover, causal masking can be implemented easily by truncating the sum from 1 to in ①8 together with masking out the corresponding part of the banded matrix D.
Proposition 1.
Let (x)))) E RRN (1 = 1,2,..., , and <. N) for R.. If (or(x))] are linearly independent at then the following matrix L(x) E NNN has rank
((x) = 01 (x) + )2(x))2(())
+ (z))
(1I)
Feature map selection. The feature map selection is crucial for the success of far-field attention modeling. In this work, we adopt the existing successful feature map @1 (z) = elu (x) + used in the linear transformer [26] together with (2 == elu(- + 1, which is a straightforward modification of Φi (z). Moreover, we consider the third feature map Ø3 (x) := tanh(x) (z). It is easy to check that σ1 (z)). 62 (z),, and (x) are linearly independent for almost all æ. We leave how to design a set of
feature maps to optimize the far-field attention modeling as future work.
3.3 Blending of near-field and far-field attention
Based on our experiments, adding a learnable weight in front of each attention component benefits training and generalization. As such, we propose the following scheme to blend the near-field attention and far-field attention
v (w, W2
(12)
where W/ and Wy are two learnable weights, and we enforce their positivity via sigmoid map.
Experimental Results
In this section, we numerically verify the efficiency of FMMformers and empirically analyze the effects of near-field and far-field attention on various benchmarks, including synthetic sequence copy (Sec. I. Long Range Arena (LRA) (Sec. 4.2), and language modeling (Sec. 4.3). We aim to show that: (i) FMMformers are efficient in both computational time and memory footprint. (ii) Multiple kernels benefit learning of the far-field attention. (iii) Blending near-field attention with far-field attention can boost the performance of linear transformers. Throughout this section, we compare FMMformers with linear transformers (linear, r = (T)). standard softmax transformers (softmaax) and softmax transformers that use banded attention matrix of bandwidth & (bands). All experiments are conducted on a server with 4 NVIDIA 3090TI GPUs.
4.1 Synthetic sequence copy task
We first consider synthetic copy task with various sequence lengths, including 128, 256, and 512. In this task, the model has to duplicate a sequence of symbols. Each training and test sample is sequence of maximum length 128/256/512 12 with ten different symbols separated by dedicated separator symbol. We train all transformers for this task using the same setting as in 266
Boosting performance of linear transformers with near-field attention. We first compare FMM- formers, obtained by blending the linear transformer with banded attention matrix of bandwidths 10, 20, and 30, respectively. Figure 4 shows that for shorter sequences of length 128, all transformers reach similar loss; the standard softmax transformer converges much faster than the linear transformer while blending the linear transformers with near-field attention can improve training. Moreover, the benefits of near- near-field attention become more significant as the sequence length increases.

---

2.5
2.5
softmax
Cross entrogy loog
2.0
Gress entrogy lozs
2.0
linear
lod
linear + band
banda
to
1.0
1.0
linear bandy.
0.5
0.5
10
2000 4000 6000 8000 10000 Gradient
0.0
2000
4000 6000 8000 10000 0.90
2000 4000 6000 8000 10000
Gradient staps
Gradient stips
Figure 4: Convergence comparison of softmax, lincar, and blend of lincar transformer with banded matrix on a sequence duplication task with different sequence lengths (left: 128, middle: 256, right: 512). Adding near-field attention into linear attention consistently improves the training for different sequence lengths.
2.5
2.0
Cross entroppy lost
Inear
2o
entropy
1.5
1.5
rank
1.0
2.0
M 4000
10
10500
0.0g
10000
0.6g
steps
Gradient steps
Figure 5: Convergence comparison of softmax, linear, and different low-rank attention on sequence duplication task with different sequence lengths (left: 128, middle: 256, right: 512). Attention with higher rank improves triniigg for different sequence lengths.
Enhancing far-field attention with multi-kernels. After observing that the linear transformer performs poorly as the sequence length increases, we consider augmenting the linear transformer with multiple feature maps; in particular,
consider the three feature maps mentioned above, i.c., on (x: = clu(x) + 1, Φ2(x) (x) = clu( (x) + 1, and Φ5(x) = tanh(x:). Figure compares different transformers different sequence lengths, where rank consists of the feature maps di (æ) and (2(x), and rank 3 consists of all three feature maps. These results show that multiple kernels can improve the learning of far-field attention.
Computational and memory complexity. In this part, we compare different transformers in computational time and memory cost. Following (26). we compute the attention and gradient for input sequences with different lengths N E {29, 2 ... ,..) and measure the peak allocated GPU memory and the required time for each transformer model. We conduct this experiment NVIDIA 3090TI with 24GB memory, and we report the time and memory cost per sample in the same way in [66. Figure contrasts the time (left) and memory (right) costs of different models.
an
4.2 Long Range Arena (LRA) Benchmark
In this experiment, we evaluate our model on tasks that involve longer sequence lengths in the Long Range Arena benchmark [54] We show that the FMMformer outperforms the baseline linear transformer and standard softmax transformer (58), justifying the advantage of the FMMformer in capturing long-range dependencies. We provide model and training details the Appendix.
Time (mlllzzaan)
GPU Memory (MG)
softimax linear
banda
Sequence Length
Sequence Lengthi
Figure 6: Comparison of computational and peak memory cost of forward/backward pass for standard softmax transformer, linear transformer. rank linear transformer, rank 3 linear transformer, and the blend of rank 3 linear transformer with a banded attention matrix of bandwidth 30. All transformers are of lincar complexity in time and memory except the softmax transformer.

---

Model
TiatOss (2K)
(eR)(AK]
Retrieval (4K)
Image (TK)
Pathinddr (IK)
Avg
Sollmaxx
37.10(37.10)
64.17665.02 02)
80.71 (7.71)99335)
(3)
72.48 (74.16)
(5870)
Linear [26]
18.30
64.22
81.37
38.29
71.17
54.67
Bardly
32.16
66.31
79,41
43.33
67.44
57.73
FMMformer (1-kemec++ Band,)
33.22
60.52
81.50
45.01
71.29
59.51
FMMformer (2-kemnel Bands)
36.74
67.84
81.88
45.10
72.12
60.74
Table 1: Results on the LRA benehmark. We report the test classification accuracy for each task and average accuracy across tasks. The FMMformer outperforms the linear transformer and attains similar or better results than the standard transformer. Across tasks, the FMMformer achieves the best average accuracy. Also, the FMMformer with 2 kernels enhances the performance of the FMMformer with I kernel. The numbers in the parenthesis are from the paper [63]. Note that use near-field attentions of bandwidth 5 for all FMMformers reported here, and Band, are softmax transformers with banded attention matrix bandwidth 5.
Datasets and metrics. We consider all five tasks in the LRA benchmark, including Listops [38, byte-level IMDb reviews text classification (35). byte-level document retrieval [42), CIFAR- 10 image classification on sequences of pixels [30], and Pathfinder [2). These tasks involve long sequences of
length 2K, 4K, 4K, 1K, and 1 K, respectively. We follow the setup/evaluation protocol in (54) and report the test accuracy for individual task and the average result across all tasks.
Results. We summarize our results in [ Like in the copy task, we observe that adding near-field attention modeled by banded attention matrices improves the performance of linear transformers. More interestingly. using bandwidth 5 already yields good results across all LRA tasks while significantly reducing the computational and memory cost of calculating the attention matrix. For example, in the byte-level document retrieval [42 task, banded matrix with bandwidth 5 only accounts for 0. 0.15%% of the corresponding full attention matrix. The FMMformer with kernel (blending banded matrix of bandwidth 5 with the linear transformer using feature map Φ1 (x)) outperforms the linear transformer and yields similar or better results than the standard softmax transformer in all tasks. Furthermore, the FMMformer with 2 kernels (blending banded attention matrix of bandwidth 5 with the linear transformer using feature maps Φ1 (z) and (2(x)) further improves the FMMformer with kernel, justifying the need of better low-rank approximation for the far-field attention. Across tasks, the FMMforrmr obtains the best average accuracy. Also, it is worth noting that tasks in the LRA benchmark cover different data modalities include text and images. Good performance of the FMMformer on these tasks demonstrates that the advantages of our model over the linear and standard transformers are consistent across data modalities.
4.3 Language Modeling on WikiText-103
Experiments on the copy task in Sec. illustrate the effect of combining near-field and far- firlfield attention. Results on the LRA benchmark in Sec. [4.2 show the ability of our FMMformer to capture very long-range dependency and extend to different data modalities. Now our goal is to confirm the advantage of the FMMformer on a large-scale application. We consider the word-level language
modeling task on WikiText- 103 37
Datasets and metrics. WikiText- 103 consists of articles from Wikipedia and is a dataset with long contextual dependencies. The training set is made up of about 28K articles containing 103M running words; this corresponds to text blocks of about 3600 words. The validation and test sets are composed 218K and 246 running words, respectively. Each of them contains 60 articles and about 2 words. Our experiment follows the standard setting 37 47 and split the training data into L-word independent long segments. For evaluation, we use a batch size of 1, and go through the text sequence with a sliding window of size L. We consider only the last position for computing perplexity (PPL) except in the first segment, where all positions are evaluated as in 22
Results. Table 2 shows the validation and test perplexity of our models versus the linear and standard softmax transformer on WikiText-103. Here, we also compare with the linear attention with the fast weight trick proposed in (47). Consistent with previous experiments, the FMMformer outperforms the linear transformer with or without fast weight. The standard softmax transformer obtains the best results in this task, but the gap between the FMMformer and the standard transformer is very small when a larger bandwidth is used for near- near-field attention in the FMMformer. This is justified by the improvement in terms of PPL of the FMMformer with a near-field attention of bandwidth 20 compared to the FMMformer with a near- field attention of bandwidth 5. Also, FMMformer with 2 kernels ( (z) and (x))) still improves over FMMformer with kernel (c) (az)). Consider the linear complexity of computational time and memory advantage of FMMformers, the small performance gap of FMMformers to standard softmax transformers can potentially be overcome by using the multilevel hicrarchical near-field and far-field decomposition.
8

---

Method
Valid PPL.
Test PPL.
Softmax [58]
33.15
34.29
Linear 226
37.27
38.40
Fast weight [47
35.75
36.63
Fast weight [47] + Linear 26
34.78
35.95
Bandyy
38.18
39.19
FMMformer (1-kernel linear + Band20
35.41
36.43
FMMformer (I -kcernel fast weight Bandgo)
34.54
35.47
FMMiormmr (2- (2-kernel linear + Band
35.10
36.11
FMMformr (2-kernel fast weight BBnd2o)
34.16
34.71
Table 2: WikiText- -03 language model perplexities of FMMformers compared the baselines. The number of parameters (40 M) is almost the same for all models, up to the small difference introduced by additional weights on the far-field attention in EMMformers. FMMformers outperform linear transformers (26). The performance gap compared to softmax transformers is reduced when using larger bandwidth in near-field attention and more kernels in far-field attention. Note that Band, and Bandzu are softmax transformers with banded attention matrix of bandwidth and 20, respectively.
5 Related works.
Low-rank transformers. Low-rank approximation of the self-attention matrix A has been popular method in reducing the quadratic computational and memory complexity of transformers to linear. Linearized attention that leverages kernelization tricks can be considered as the rank one approximation of the self-attention matrix 660
the choice of the feature map function is crucial for the success of linearized attention. Fast weight memories [8] have been used to improve memory capacity of linearized attention 47.. The Nyström method has also been leveraged for developing efficient attention with linear computational complexity [63]. Many other low-rank attention models exist, e.g., 8 45 50 40 FMMformers employ low-rank attention to model far-field attention; in principle, the merits of existing low-rank attention can be integrated into FMMformers.
26
13 49
Sparse transformers. Attention matrices have been enforced with different sparsity patterns to gain efficiency, including fixed sparsity patterns [1 39 7 65). combination of different sparsity
patterns 12 24], and aata-dependen//eaamable sparsity patterns [33 60 52 53
46 59
Informer
666] is another efficient attention scheme using sparse query. Note that the existing sparsity pattern can be very complicated, while we adopt a sparse banded matrix to model the near- field attention.
Other efficient transformers. Reformer reduces the cost of self-attention to O(N log N) via locality-sensitive hashing [29]. Linformer [60] and Longformer 77) obtain the linear complexity using random projection and local window attention, respectively. Galerkin transformer in [10] uses a Galerkin self-attention for the encoder. See (55) for a review of efficient transformers.
Sparse and low-rank interpretation of FMM. The fast multipole method is introduced by Green- gard and Rokhlin [19] for the efficient computation of gravitational/llcctrsstttt potentials and fields. Applications of FMM to machine learning can be found in [8] 31 [7]. FMM can be generalized alge- braically for efficient computation the dense matrix-vector product. Algebraic counterpart of FMM
include H-matrix (21). 2 -atrix (20 22). hierarchically semi- separable (HSS) [I] 62], hierarchi-
cally block-separable (HBS) [36), and hierarchically off-diagonal low-rant (HODLR) B matrices.
The common feature is to compress the off-diagonal sub-matrices by low-rank approximations.
Concluding Remarks
In this paper, proposed FMMformers, class of efficient and flexible transformers with linear time and memory complexity, inspired by the fast multipole method. In FMMformers, we decompose the full attention into near-field and far-field attention; banded matrix and model the far-field attention using a low-rank matrix leveraging ideas the linear transformer (26]. We validate the efficiency of FMMformers
model the near-field attention with a sparse
various benchmark tasks, including synthetic sequence copy, LRA benchmark, and WikiText- 103 language modeling. Our numerical results show that FMMformers consistently outperform the linear transformer all benchmarks and outperform the standard softmax transformer on the LRA tasks. In our work, we select linearly independent feature maps enhance the learning of far-field attention. is natural to ask how to design set of feature maps to optimize the performance of FMMformers? Furthermore, we leave the application of FMMformers for improving the vision transformer [17 56) as future work.

---

7 Acknowledgement
This material is based on research sponsored by NSF grants DMS-1924933 DMS-2012465, DOE grant DE-SC0021142, and ONR grant 990014-18-1-220 and the MURI grant N00014-20-1-2787. We thank Professor Jack Xin for helpful discussions.
and
References
[1] Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. ETC: Encoding long and structured inputs in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 268 284, Online, November 2020. Association for Computational Linguistics.
[2] Rami AI-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3159-3166, 2019.
[3] Sivaram Ambikasaran and Eric Darve. An (n log fast direct solver for partial hierarchically semirsbpe matrices. Journal of Scientific Computing, 57(3):477-501, 2013.
[4] Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. In International Conference on Learning Representations, 2019.
[5] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: 1e...44090004 09990,43,..00 2014.
[6] Mario Bebendorf. Hierarchical Matrices. Springer, 2008
[7] Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long- -ocummettnnt transformer. arXiv preprint arXiv:2004.05/500 2020.
[8] Guy Blanc and Steffen Rendle. Adaptive sampled softmax with kernel based sampling. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 590-599 PMLR, 10-15 Jul 2018.
[9] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Vore Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler. Mateusz Litwin, Scott Gray. Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[10] Shuhao Cao. Choose transformer: Fourier or galerkin. arXiv preprint 210::2105.1499. 2021.
[11] Shiv Chandrasekaran, Ming Gu, and Timothy Pals. A fast ULV decomposition solver for hierar- chically semiseparable representations. SIAM Journal on Matrix Analysis and Applications, 28(3):603-622, 2006.
[12] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: 10509, 2019.
[13] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. International Conference Learning Representations, ICLR 2021, 2021.
[14] Barry A Cipra. The best of the 20th century: Editors name top 10 algorithms. SIAM news, 33(4):1-2, 2000.
10

---

[15] Zihang Dai. Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-Xe XL: Attentive language models beyond fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2978-2988, Florence, Italy, July 2019, Association for Computational Linguistics.
[16] Jacob Devlin, Ming-Weir Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Confer- ence of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume (Long and Short Pupers), pages 4171-4186, Minneapolis. Minnesota, June 2019, Association for Computational Linguistics.
[17] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. / 1929, 2020.
[18] Alexander G Gray and Andrew W Moore. N-body' problems in statistical learning. Advances in neural information processing systems, pages 521-527, 2001.
[19] Leslie Greengard and Vladimir Rokhlin. A fast algorithm for particle simulations. Journal of computational physics, 73(2):325-34,, 1987.
[20] W. Hackbusch, B. Khoromskij, and S. A. Sauter. On H2 matriccss. In Hans-Joachim Bungartz, Ronald H. W. Hoppe, and Christoph Zenger, editors, Lectures Applied Mathematics, pages 9-29, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.
[21] Wolfgang Hackbusch. A sparse matrix arithmetic based on H-matrices, part i: Introduction to H H-matrices. Computing, 62 1999.
[22] Wolfgang Hackbusch and Steffen Börm. Data-sparse approximation by adaptive HC2 -matrices. Computing, 69(1):1-355 2002.
[23] Stephen José Hanson. stochastic version of the delta rule. Physica D: Nonlinear Phenomena, 22(1-3):265-272, 1990.
[24] Jonathan Ho. Nal Kalehbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidimensional transformers. arXiv preprint 19X.i::912.12/402 2019.
[25] 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 Learning Representattonss, 2018
[26] Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Hal Daumé IIII and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5156-5165. PMLR, 13-18 Jul 2020.
[27] Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. Structured attention networks. arXiv preprint arXiv: 070000080777... 2017.
[28] Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations (ICLR), 2015.
[29] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
[30] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[31] Dongryeol Lee, Richard Vuduc, and Alexander G Gray. A distributed kernel summation frame- work for general-dimension machine learning. In Proceedings of the 2012 SIAM International Conference Data Mining, pages 391-402. SIAM, 2012.

---

[32] Drew Linsley, Junkyung Kim, Vijay Veerabadran, Charles Windolf, and Thomas Serre. Learning long-range spatial dependencies with horizontal gated recurrent units. In S. Bengio, H. Wallach. H. Larochelle, K. Grauman, N. Resa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[33] Peter J. Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. In International Conference on Learning Representations, 2018.
[34] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 16692, 2019.
[35] Andrew L. Maas, Raymond E. Daly, Peter T. 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 Linguisties: Human Language Technologies, pages -50, Portland, Oregon, USA, June 2011. 1. Association for Computational Linguistics.
[36] Per-Gunnar Martinsson and Vladimir Rokhlin. A fast direct solver for boundary integral equations in two dimensions. Journal of Computational Physics, 205(1): 2005.
[37] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In Sth International Conference on Learning Representattinns, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[38] 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, pages 92-99, New Orleans, Louisiana, USA, June 2018. Association for Computational Linguistics.
[39] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 4055 4064. PMLR, 10-15 Jul 2018.
[40] Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference Learning Representations, 2021.
[41] Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint arXiv: 1.0992,, 2019.
[42] Dragomir R Radev, Pradeep Muthukrishnan, Vahed Qazvinian, and Amjad Abu-Jbara. The acl anthology network corpus. Language Resources and Evaluation, 47(4))911449)) 919-944, 2013.
[43] Alec Radford, Karthik Narasimhan, Tim Salimans, and llya Sutskever. Improving language understanding by generative pre-training OpenAl report, 2018
[44] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9 2019.
[45] Ankit Singh Rawat, Jiecao Chen, Felix Xinnan X Yu, Ananda Theertha Suresh, and San- jiv Kumar. Sampled softmax with random fourier features. In H. Wallach, H. Larochelle, Fox, and R. Garnett, editors, Advances in Neural Informa- tion Processing Systems, volume 32. Curran Associates, Inc., 2019.
A. Beygelzimer, F. d' d'Alché-Bur
[46] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68, 2021.
[47] Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers are secretly fast weight memory systems. arXiv preprint arXiv:2102. 2021.
[48] Imanol Schlag, Tsendsuren Munkhdalai, and Jürgen Schmidhuber. Learning associative in- ference using fast weight memory. International Conference on Learning Representations, 2021.
12

---

[49] 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, pages 3531-3539, 2021.
[50] Kyungwoo Song, Yohan Jung, Dongjun Kim, and Il-Chul Moon. Implicit kernel attention. arXiv preprint arXiv:2006.061 047.0 2021.
[51] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting The journal of machine learning research, 15(1):1929-199) 1958, 2014.
[52] Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Rethinking self-attention in transformer models. arXiv preprint arXiv:2005.00743, 2020.
[53] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse Sinkhorn attention. In Hal Daumé III and Aarti Singh, editors. Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 9438-9447. PMLR, 13-18 Jul 2020.
[54] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. Long range arena : benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
[55] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, arXiv preprint urXiv:2009.06732. 2020.
[56] 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.
[57] Laurens Van Der Maaten. Accelerating t-sne using tree-based algorithms. The Journal of Machine Learning Research, 15(1):321133245 2014.
[58] 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 Informa- tion Processing Systems, pages 5998-6008, 2017.
[59] Apoorv Vyas, Angelos Katharopoulos, and François Fleuret. Fast transformers with clustered attention. Advances in Neural Information Processing Systems, 33, 2020.
[60] Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.00 05768, 2020.
[61] Adina Williams, Nikita Nangia, and Samuel Bowman. A broed-coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long Papers), pages 1112- 1122, New Orleans, Louisiana, June 2018. Association for Computational Linguistics.
[62] Jianlin Xia, Shivkumar Chandrasekaran, Ming Gu, and Xiaoye S Li. Fast algorithms for hierarchically semiseparable matrices. Numerical Linear Algebra with Applications, 17(6):953- 976, 2010.
[63] 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. 2021.
[64] Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. arXiv preprint arXiv: 1906.08237 2019.
[65] Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. arXiv preprint 14062 2021.
13

---

[66] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In The Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, page online. AAAI Press, 2021.
14

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 4.1.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4.1.
(b) Did you include complete proofs of all theoretical results? [Yes] See Supplementary Materials
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "nQHU0Y3VReQ", "reviewer": "Reviewer_pp7v", "summary": "This paper proposed FMMformers, and propose to combine banded attention with low-rank attention in a single model. They conduct experiments on wikitext, copy and long range arena. ", "questions": "", "limitations": "", "rating": 4, "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": "The combination of different types of attention is not new. Models like BigBird, ETC, long short transformers, luna etc. already proposed this idea. The authors learn to blend the attention types together by a linear combination. I don't think this paper is terribly interesting given this naive composition. \n\nThis paper combines banded attention with kernel (low-rank) attention by combining the attention weights before multiplying by V. I think we can think of it as linear/performer transformers with a sprinkle of local attention.  I really think the FMM (fast multipole) angle is **not** main text worthy as it can be just distracting and does not add much value to the understanding of the method. \n\nI think the authors can be upfront that this method is simply add(low rank attention, local_attention). The story does not seem to contribute anything to the understanding of the method and is making things \"fancy\" unnecessarily. Please consider a more down to earth method if we hope that this method to be more widely adopted. I would appreciate a model name and title that better explains what the method is doing (local+kernel attention) seems to be more appropriate. \n\nSome concerns/weaknesses:\n1. The choices of sub-modules \"near field\" and \"far-field\" are quite arbitrary. \n2. Is the banded matrix just local attention? it seems so. if so, please call it a local attention so it is just less confusing or at least tell us why it is different.\n3. Not all models are compared in the long range arena even though the results are already in the original paper. \n4. is language modeling the right choice of experiments for long range transformers? \n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "0.5"}, "extra_text": {}}, {"review_id": "jbJ0YtX_J7O", "reviewer": "Reviewer_MHtR", "summary": "The work proposes FMMformer, which borrows ideas from fast multipole method (FMM) to approximate the quadratic Softmax attention with a linear complexity. Specifically, the approximation consists of a near-field Softmax term (i.e. local attention) and a far-field multi-kernel linear attention. Some theoretical analysis is included to support the idea. The proposed model is evaluated on one synthetic copy task, long range arena and wikitext-103 language modeling. On the three tasks, the proposed model has a better quality compared to linear attention, though the gap between FMMformer and the standard transformer is still significant.", "questions": "", "limitations": "", "rating": 5, "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": "The key idea of the proposed model is intuitive and well motivated. The theoretical analysis is easy to follow. The practical instantiation of the proposed model is also neat. \n\nHowever, the empirical study of the work is relatively weak. \n- First of all, in terms of baseline, Sparse Transformer (i.e. local + sparse low rank) should be included given its closeness to the proposed model. In addition, the work only considers local attention baselines of bandwidth of at most 20, which could be too limited and won't be able to utilize the full parallelization of GPUs anyway. As the bandwidth increases, local attention could be a strong baseline.\n- Secondly, for the 3 tasks in consideration, synthetic copy is overly simplified and long-range arena has relatively large variance and noise. As for wikitext-103, the reported performances of the baselines & proposed model are generally far from the SOTA, weakening the overall credibility of the evaluation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall speaking, there won't be any additional negative social impact from the proposed model. In terms of limitation, it would be helpful if authors can discuss that the empirical studies are performed in relatively small scales and in text domain mainly. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "LaixDHkM8SB", "reviewer": "Reviewer_zdGe", "summary": "The paper proposed the new efficient transformer (FMMformers), which decomposes the attention computation into direct and coarse-grained computations. The coarse-grained computation is handled by the low-rank matrix and the direct computation is handled by a banded matrix. The proposed method shows better performance on the LRA dataset and comparable performance on the language modeling with the original transformer \n", "questions": "", "limitations": "", "rating": 6, "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": "The paper is well written and easy to follow. \n\nThe proposed method is well-motivated from the physical computation of n-body problems, which seems to be a good extension to the linear kernel attention. It is also developed with the solid support of both theoretical and experimental results for the approximated softmax with certain error bounds. Experiments with multiple random seeds might be preferable to show the significance of the proposed methods. The attached code makes the paper easier for reproduction. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "(1) Implementation details: given that local window approach like Big-Bird or Longformer generally needs to have a customized kernel to achieve real speedup due to the caching issues. Just wondering if there exists any specific modification w.r.t the real implementation of the proposed method. \n\n(2) It is possible to have a full theortical time and memory complexity that takes the k also into account? Given that from the language modeling experiments, large bandwidth may affect a lot in the final performance. (20 v.s. 256 context length might not be eligible to be considered as \"<<\") \n\n(3) More experimental details: \nfor Figure 5, is there missing one line about high rank with banded attention?\n\nfor the language modeling experiments, could the authors provide the sliding window that is used in the main text as well (256 in the appendix)? Moreover, is it able to have the results where the computation of the FMMformer and the transformer have the same compute while the FMMformer could have a longer context window, wondering if that is the more real application we want from the efficient transformer design? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "KldT6RXMr6", "reviewer": "Reviewer_bVJZ", "summary": "A fast and memory-efficient transformer architecture based on a sparse attention mechanism inspired by the fast multipole method (FFM). It decomposes attention matrices into the sum of a banded matrix (capturing near-range interactions) and a low rank matrix (capturing long-range interactions). This low rank matrix is itself expressed as a sum of rank 1 matrices, each characterized by a given feature map. Experiments on the LRA benchmark and WikiText-103 show promising results in terms of test accuracy/perplexity Vs training/inference speedups.", "questions": "", "limitations": "", "rating": 4, "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": "**Overall appreciation (originality, quality, clarity, and significance)**\n- Originality: Adapts the intuition from the fast multipole method to sparsify attention maps, and leverage several tricks (e.g., kernel trick for linear transformers from ​​Katharopoulos et al.) to obtain a simple and intuitive formulation.\n- Quality: Method is well motivated and there are a few promising experimental results. However the experimental design has significant gaps (see suggestions below).\n- Clarity: Easy to read overall. There are some subsections that felt unnecessary / not concisely written (see below).\n- Significance: Although difficult to draw conclusions given the shortcomings of current experiments, the idea appears to have potential. The duality of local attention vs long-range attention controlled by two separate components is compelling. Additional guidance/analyses on relative performance tradeoffs between widening the banded matrix Vs adding more feature maps in low rank matrix, as well as on the way to choose these feature maps would be very valuable.\n\n**Clarifying questions**\n- Fig 4 & 5: Are these showing cross entropy loss on the training set or validation set? If on the training set then results are not surprising (you are training networks with strictly more parameters). If on validation set, then the language (line 201) is a bit misleading\n\n**Suggestions**\n- Section 2.1 - This subsection could be made more concise: several definitions and propositions are introduced but subsequently not used anywhere (could be moved to appendix)\n- Section 3 - Guidance on how to select / craft these feature maps would strengthen your paper \n- Fig 4 & 5 - It appears you have not yet converged on the longer sequences experiment (length=512) which makes your conclusion on line 202 not clear. Additionally, I would keep consistent the y-axis scales between the three columns: as such they are a bit hard to compare across.\n- Section 4 - This section is lacking a speed vs acc/perplexity analysis (in particular on LRA). Currently, section 4.1 has . Would be good to have in table format for speedups to appreciate actual gains. FIg. \n- Section 4 - It would be very helpful to perform a thorough ablation analysis that shows relative trade-offs (on accuracy/perplexity, speed, memory) from increasing the banded matrix bandwidth Vs increasing the number of feature maps considered for the low rank matrix.\n- Section 4 - There are many sparse attention transformer architectures out there (e.g., Performer, Linformer). It is important to compare FMMformer to these other methods (besides linear transformers) to understand relative performance trade-offs\nSection 4 - Would recommend keeping things more consistent in terms of choice of parameters across experiments (number of kernels and bandwidth in particular)\n\n**Minor points**\n- Line 72/73: “and has been regarded as one of the top 10 algorithms in scientific computing in the 20th century” → unnecessary, would suggest to drop this sentence\n- Line 86-87: “For the illustration purpose” → “For illustrative purposes”\n- Line 94: Define C (e.g., positive constant)\n- Line 153: ‘using the fact that LV= …” → would drop -- you have the same identity just above\n- Line 159: Would indicate what these assumptions are here\n- Line 174/175: “It is easy to check that [...] linearly independent for almost all x” → Add proof in appendix\n- Line 220: “capturing long-term dependency’ → “long-range dependencies”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are discussed, although they are a bit scattered throughout -- would be helpful to synthesize them in conclusion.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed a fast and memory-efficient transformer approximation, inspired by the fast multiple method (FFM), which combined the sparse and low-rank approximation. The method is well-motivated and easy-to-follow. The authors demonstrated the benefits of the proposed neural architecture empirically on synthetic data, LRA benchmark, and language modeling on WikiText-103.  

There are several existing work on combining sparse transformer with low-rank transformer,  as pointed by the reviewers (pp7v and MHtR), however, since these are the co-current work, the novelty of the submission should not be discounted. Actually, as opposite. it actually strengthens the significancy of the method. I personally like Sec 2.1 to motivate the FMM. 

The major criticism from most of the reviewers actually lies in the empirical experiment part, which makes the claim of the paper relatively weak. In my opinion, these suggestions are reasonable. For example, the comprehensive comparison with more baselines, detailed ablation study on the trade-off between accuracy, speed, memory vs. architecture parameters, and more practical tasks on real-world benchmarks should be included. The authors rebuttal addressed some of them, but some of them are still missing. 

In sum, the idea and new architecture proposed by this paper is novel and well-motivated, however, the benefits of this architecture is not well empirically justified. I hope in the final version, the authors can take the reviewers' comments into account to improve the weakness of the paper. 

 
Decision: Accept (Poster)