Improving Transformer with an Admixture of Attention Heads
Authors: Tan Minh Nguyen
Tam Minh Nguyen
Hai Ngoc Do
Khai Nguyen
Vishwanath Saragadam
Minh Pham
Nguyen Duy Khuong
Nhat Ho
Stanley Osher
Venue: NeurIPS 2022 Accept (2022)
Keywords: transformer
admixture
attentions
redundant heads

Abstract: Transformers with multi-head self-attention have achieved remarkable success in sequence modeling and beyond. However, they suffer from high computational and memory complexities for computing the attention matrix at each head. Recently, it has been shown that those attention matrices lie on a low-dimensional manifold and, thus, are redundant. We propose the Transformer with a Finite Admixture of Shared Heads (FiSHformers), a novel class of efficient and flexible transformers that allow the sharing of attention matrices between attention heads. At the core of FiSHformer is a novel finite admixture model of shared heads (FiSH) that samples attention matrices from a set of global attention matrices. The number of global attention matrices is much smaller than the number of local attention matrices generated. FiSHformers directly learn these global attention matrices rather than the local ones as in other transformers, thus significantly improving the computational and memory efficiency of the model. We empirically verify the advantages of the FiSHformer over the baseline transformers in a wide range of practical applications including language modeling, machine translation, and image classification. On the WikiText-103,  IWSLT'14 De-En and WMT'14 En-De, FiSHformers use much fewer floating-point operations per second (FLOPs), memory, and parameters compared to the baseline transformers. 

Improving Transformer with an Admixture of Attention Heads
Tan M. Nguyen'
Tam Nguyen' FPT Software AI Center ngryouniiiitraa@@2@gmaa....mc com
Department of Mathematics
University of California, Los Angeles tanmmuyenn89@ulla edu
Hai Do
Khai Nguyen
FPT Software Al Center haidn6@fsoft. com.
Department Statistics and Data Sciences University of Texas at Austin
khainbeutexas.com edu
Vishwanath Saragadam Department of ECE Rice University
Minh Pham
Department of Mathematics University of California, Los Angeles minhroseQucla. edu
vishwanath, www.gadammriic......om
Duy Khuong Nguyen
Nhat Ho
FPT Software AI Center shuongnd6@fsoft.c com. vn
Department of Statistics and Data Sciences University of Texas at Austin
minhnhat@utexas.o edu
Stanley J. Osher
Department of Mathematics University of California, Los Angeles s jjo@math, ucla.edu
Abstract
Transformers with multi-head self-attention have achieved remarkable success in sequence modeling and beyond. However, they suffer from high computational and memory complexities for computing the attention matrix at each head. Recently, it has been shown that those attention matrices lie on low-dimensional manifold and, thus, are redundant. We propose the Transformer with Finite Admixture of Shared Heads (FiSHformers), novel class efficient and flexible transformers that allow the sharing of attention matrices between attention heads. At the core FiSHformer is a novel finite admixture model of shared heads (FiSH) that samples attention matrices from set of global attention matrices. The number of global attention matrices much smaller than the number of local attention matrices generated. FiSHformers directly leam these global attention matrices rather than the local ones as in other transformers, thus significantly improving the computational and memory efficiency of the model. We empirically verify the advantages of the FiSHformer over the baseline transformers in a wide range of practical applications including language modeling, machine translation, and image classification. On the WikiText- 103, IWSLT' 14 De-En and WMT' 14 En- De, FiSHformers use much fewer floating-poin point operations per second (FLOPs), memory, and parameters compared to the baseline transformers.
Co-first authors. Co-last authors. Please correspond tanmnguyen&9@ucla.ed
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

MHA
FISH
X
Q:
K₁
K₂
Gn
Ks
Q:
Kr
Q₂
K2
A 0
Ag OgKe
Ag GgKKs
Gj G "
Gg GaKe'
0.85
Nayreaa 1420
AURU SOURN PL
20.00
0.85
0.75
0.7
2002
224
Mi-id +212 1C24
+234
4000
Der
Figure 1: Our proposed finite admixture model of shared heads (FiSH) vs. the standard multi-head (MHA) attention. FiSH samples local attention matrices from finite admixture of global attention matrices. Compared to MHA, FiSH is more efficient, saving computation and memory (See Fig. and Section 4).
1 Introduction
Transformers have become the totle-oo-the-are art model for solving many challenging problems in natural language processing [75, 1, 17, 80, 21, 10, 35, 61] and computer vision [19, 68, 22, 73]. Transformers learn from unlabeled data effectively and take advantage of the pre-trained models on downstream tasks that involve different data modalities with limited supervision [59, 60, 21, 82, 43). The success of transformer is credited the multi-head self-attention (MHA) mechanism as their fundamental building block. For each token in the sequence, self-attention in transformers aggregates information from other tokens by computing weighted average of their feature representations with weight proportional to similarity score between the representations. This attention mechanism allows arbitrary input-dependent interaction between tokens in the sequence where token can pay attention to other tokens and attain a contextual representation [6, 75, 38). Multi-head self- attention captures multiple such contextual representations, one at each head, thereby increasing the representation capacity of the self-attention. It has been argued that the representation capacity of the attention mechanism [72] and its flcxibility capturing diverse syntactic and semantic relationships [72, 76, 15, 77, 32] account for the impressive performance of transformers in practice.
1.1 Background: Self-Attention
For a given input sequence X :- [x1,... æN|
T E NxDx of N feature vectors, self-attention transforms X into the output sequence H in the following two steps:
Step The input sequence X is projected into the query matrix Q, the key matrix K, and the value matrix V via three linear transformations
Q XW WW k= xX xXVT,
where We. WK E DxD= and Wv D. are the weight matrices. We denote Q ==
(q, AN K = [k, kN] and V == lu,.... uN." where the vectors qis kú U. for
i 1, are the query, key, and value vectors, respectively.
Step 2. The output sequence H == [h1,... ... -NNlT is then computed as follows
QK
A
H softmax
VD V= softmax
VV
VD
where the softmax function is applied to each row of the matrix = (QKT). This matrix A e NxN and its component dg for i, 1, N are called the attention matrix and attention scores, respectively. For each query vector qi for = 1,... ... NN, an equivalent form Eqn. (I) to compute the output vector h; is given by
h Σ softmax (q. k /2g/VDDor
The self-attention computed by Eqn. (1) and (2) is called the scaled dot-product or softmax attention. In our paper, we call transformer that uses this attention the softmax transformer. The structure

---

that the attention matrix A learns from training determines the ability of the self-attention to capture contextual representation for each token.
Multi-head Attention (MHA) Fach output sequence H forms an attention head. In MHA, multiple heads are concatenated compute the final output. Let H be the number of heads and w D be the projection matrix for the output. The multi-head attention is defined as
MultiHead( (H)
fim1> = Concat (..... Hy) W
(3)
1.2 Eigenvalue Analysis of the Attention Matrices
The multi-head mechanism allows transformers to capture more diverse attention patterns and increase the capacity of the model. However, in many practical tasks, transformers learn re- dundant heads [47, 78]. whose learned attention matrices lie on a low-dimensional manifold [8]. To confirm this claim, in Figure 2, we follow the eigenvalue analysis in [8] and investigate the eigenvalues of the covariance matrix of vector- ized attention matrices aggregated over each layer of a transformer model trained on the WikiText- 103 dataset for language modeling. We observe that this covariance matrix is low rank with top 200 (1.2%) eigenvalues capturing more than 90% of the energy. This result verifies that the variability of learned attention matrices in transformers can be explained by relatively small number of principal components, and those attention matrices lie on a low- -iw-demensional manifold. Therefore, in multi-head attention, the effective number of heads is much smaller than the actual number of heads, and more effective way to compute multi-head attention is needed to improve the efficiency of transformers.
Chepp
CLoeastee Dpen
Eigan
Digen
Figure 2: (Left) Histogram of the top 50 eigen values and (Middle, Right) cumulative sum of eigen values of the layer-average attention scores covariance matrix.
1.3 Contribution
Leveraging the idea of the finite admixture model (FAM) [57, 9]. we propose new class of efficient transformer architectures, namely the Transformer with a Finite Admixture of Shared Heads (FiSHformer). At the core of FiSHformer is sample local attention matrices from an admixture of a small number of global attention matrices. This sharing mechanism between heads helps reduce the computational complexity and the model size compared the MHA softmax transformer. Our contribution is three-fold:
1. We construct an admixture model for shared attention matrices between heads and propose FiSHformer, a novel class of transformers that take advantage of this admixture model to efficiently compute multi-head attention.
2. We introduce a nonlincarity mapping from global heads to local heads into FiSH and propose the Generalized FiSHformer (GFiSHformer). We then explore different possibilities to design FiSHformer and GFiSHformer.
3. We empirically verify that FiSHformer and GFüSHformer achieve similar or even better accuracy but with much less computational cost in terms of FLOPs and smaller model complexity measured by the number of parameters. The advantages of our methods grow with the model/feature dimension D and the input sequence length N.
We also show that FiSHformer- based models help reduce head redundancy in our experiments.
Organization: We structure this paper as follows: In Section 2, we develop a finite admixture model of shared heads and then present our FiSHformer and its extensions. In Section 2.5 we analyze the reduction in model complexity and computational cost from FiSH. In Section 3 and 4, validate and empirically analyze the efficiency and accuracy of FiSHformer, as well as conducting ablation studies on the model. We discuss related works in Section 5. The paper ends up with concluding remarks. More results and details are provided in the Appendix.
Transformer with a Finite Admixture of Shared Heads
We first review the finite admixture model (FAM) and derive a FAM of shared heads for the multi-head self-attention. We then define Transformer with Finite Admixture of Shared Heads (FiSHformer).
2.1 A Probabilistic Viewpoint of Attention Matrices
Let A, denote the attention matrix at the 7th head, j = 1,2,,... H. From a probabilistic viewpoint, to have diversity among Ai...., AH. we can assume that A, comes from distribution P, for
3

---

all j. Since the distributions PI.....PP FH can have complex forms and be difficult to compute, our approach is consider approximated distributions of P3 and these approximated distributions have simple forms. A natural choice for each of these approximated distributions is via a finite mixture of Gaussian distributions, which can be summarized in the following lemma below.
Lemma 1. Assume that P E D a probability distribution supported on some compact set and admits differentiable and bounded density estimation p. Then, for any scale parameter >> 0 and for any O. there exists universal constant C and M I (C' (C))) P' such that we can find a mixture of M components EM P:N(0;, I'Ip)) where pı,..., are weight parameters and .1...., Ox are location parameters that satisfy the following inequality
M
sup Ip(x)) - pob( 02, oTIi: SERA
where ((110,02I is Gaussian density function with location parameter O and covariance matrix I'I
The proof of Lemma is in Appendix E. In light of Lemma 1, for each scale parameter a > and for each distribution Pj. we can find the corresponding number of components Mj. weight parameters Pıj....., Par and location parameters .1....., ,84,5 such that the mixtures F3J = EM (O L²LDr) can approximate the distribution P3 to a given accuracy e. How- ever, these approximations still involve II," M, number of location parameters, which can be computationally expensive. To overcome this issue, we assume that Mi M2 = -... = MH and the location parameters (0ij...., .,,,)) (0,,... ...... 0Mr) for all j. i.e., these approximated mixtures share a similar set of location parameters. This sharing information location parameters has a deep connection to finite admixture models, which are going to elaborate in the next sections.
2.1.1 Background
Finite admixture models (FAM) extensions of finite mixture models (FMMs), which served as workhorse in stochastic modeling. A finite mixture distribution of M components for a random array X E Xx is given by
M Fj Σ pxf((z;
M Σ Ph 1, km
Ph 2 0,
(4)
where 2, E RR- is the j-th row of X randomly sampled from the mixture distribution, f is a chosen probability measure, such as a Gaussian distribution, p {pi, PP,..P , are mixture weights, and Og denotes the parameter values for the k-th component.
A FAM is generalization of FMM where rows z. = distributions that share the components f(x; 0x), k = 1...., M but with different mixture weights
H. are drawn from different mixture
M
Pko fa 0k),
Σ Pkj
Pkj 0.
(5)
2.2 Multi-head as a Finite Admixture Model of Shared Heads (FiSH)
As demonstrated in Section 2.1, we propose a Finite Admixture Model of Shared Heads (FiSH), in which A, follows finite admixture distribution of M components given by
M
A,
Pky (A:
Σ Pkj = 1, Pkj 2 0.
(6)
k=1
Here M < H and f(A; 0k) are chosen probability measures. In particular, we choose f(A; to be Gaussian distributions (A; GR. Σ&), where G Q. and Σg = of are the cluster means and coveriances, respectively. FiSH is then defined as follows:
Definition 1 (Finite Admixture Model of Shared Heads). The multi-head attention admits a finite admixture model of shared heads if the attention matrices A, at the j*h head are sampled from the following finite admixture model:
M
A
NAA Q.K, T. .
Σ Pkj = 1, Pkj 2 0.
1=1

---

In FiSH defined in Def. I, we call {G, = QsKi "h=I.....M global attention matrices and {A,} j=.]=_.....!! local attention matrices. FiSH computes M global attention matrices Gg, and H local attention matrices A are sampled from FiSH as in Eqn. (7) with M < H.
Remark (FiSH vs. Baseline MHA). The baseline MIAA with H heads need compute H, e.g. H = 8, attention matrices, each of which requires (N22) computational costs where N is the length of the input sequence. In contrast, FISH only need to compule M < H, e.g. M 2, global attention matrices, each of which also requires (N2²) computational and memory costs. Then FiSH combines 8, local attention matrices are sampled as in Eqn. (7), This second step of sampling local attention matrices from a set of global attention matrices in FiSH requires very few computations. Thus, FiSH is more efficient than MHA.
those global attention matrices to form a FAM from which H, e.g.
Remark 2 (Connection to Topic Models). FiSH can be interpreted as a Probabilistic Latent Se- mantic Analysis (pLSA) model for topic modeling. Considering the document d that contains the word w whose topic is c, PISA models the occurrence of the word w in the document d as a mixture of conditionally independent Multinomial distributions p(wld)
Comparing this PISA with Eqn. (7) of FiSH, we can associate the mixture weights Pej and the distribution N(A; Qa ( in FISH with the distributions p(cld) and pl p(w)c) in pLSA, respectively. There- fore, it can be interpreted that the global attention matrices FiSH play the role of topics, and the local attention matrices in FISH are words sampled from those topics. It is interesting to note that pLSA is equivalent to the famous Latent Dirichlet Allocation model under a uniform Dirichlet prior on the per-document topic distribution p(cld).
2.3 Transformer with Finite Admixture of Shared Heads
FiSHformers are transformers that use FiSH instead of MHA. FiSH, as defined in Def. 1, is not differentiable, which poses difficulty in training FiSHformers. Applying the reparameterization trick [39], the attention matrices A can be written in differentiable form as follows:
M
M
Pkj QQ K. + + Oc), 6j NO,,
Σ Pkj=1 = Paj 2 0.
(8)
k=1 FiSHformers use the formulation of local attention heads in Eqn. (8) to implement FiSH.
Transformer with a Hard Finite Admixture of Shared Heads (Hard FisHformer) Hard FiSH-
former takes the zero-noise limit of Eqn. (8) reduce the computational cost. The attention matrices A, in Hard FiSHformer are then calculated as M
M Σ
A
Pky
Q.K
Pkj 2 0.
1c1
Remark 3 (Discriminative Relaxation). To take the advantage of learning from data, the convex combination condition of Pky, i.e. Ek=1 Pkj 1, paj 2 0, can be relaxed, and those mixing coefficients are made learnable parameters that are leurned from data during training Remark 4 (Transformers with a Mixture of Shared Heads). transformer with mixture of shared heads (MiSHformer) can be used to reduce the amount of computation with the cost of accuracy reduction. MiSH is special case of FiSH when the mixture weights Pka are the same for all j. The local attention matrices A, in MiSHformer are given by
M.
M
A, Σ PA T +ox0g), 4j N(O.I)
Pk 00. 0.
(10)
k=1
k=1
An empirical comparison between FiSHformer and MiSHformer is provided in Section 4.
2.4 Transformer with a Generalized Finite Admixture of Shared Heads
In order to increase the representation capacity of attention heads, follow a common approach in learning representation by replacing the linear mapping in Eqns. (8) and (9) by a nonlinear mapping such neural network with the rectified linear units (ReLU). The Transformer with Generalized Finite Admixture of Shared Heads (GFiSHrormer) is then formulated as
A
p(px) (Q, T +0x Og)), ((,,
where is nonlinear mapping and Pkj are relaxed to be learnable parameters. Similarly, formulate local attention matrices A, in the Transformer with a Generalized Hard Finite Admixture of Shared Heads (Hard GFiSHformer) as A, =MM 5(pks K, )).
5

---

A
Training
Testing
0.95
FLOPS Ratlo
0.9
Parameter Ralio
Test Memory Ratio
0.25
0.45
0.9
0.75
220
9027
SH07
500
2033
12
1100
1201
47
100
300
Sequence Length
Sequence Length
Model Dimension
Model Dimension
Model Dimensoon 258
512
1024
2046
4036
paremeters
Non-embecding paramoters
Figure 3: (Left) Training (A) and Inference (B) FLOP ratios between a 2-global-hens GFiSHformers with 8-head MHA baselines
different model dimensions D and sequence lengths N trained the WikiText- 103 language modeling task. (Right) Number of parameters (C) and GPU memory usage at test time (D) ratios between 2-global-head GFiSHformers with 8-head MHA baselines across different model dimensions D. 2-global-head GFiSHoormers are significantly more efficient than the baseline D and N increase, indicating the benefits of method for long-range and large-scale tasks.
Table 1: Perplexity (PPL) WikiText-103 compared to the baselines.
Method
Valid PPL
Test PPL
Softmax 8 heads
33.15
34.29
Softmax 4 heads
34,80
35.85
Hard FiSHformer global heads
33.10
34.11
Hard FiSHformer 2 global hcads
34.14
35.24
FiSHformmr 4 global heads
33.15
34.16
FiSHformer 2 global heads
34.01
34.96
Hard GFiSHformer 4 global heads
32.70
33.75
Hard GFiSHformer 2 global heads
33.31
34,63
GFiSHformer global heads
32.68
33.71
GFiSHformer 2 global hcads
33.21
34.48
2.5 Reduction in Model Complexity and Computational Cost from FISH
Compared to its H-head MHA counterpart, FiSH attention of M global heads and H local heads saves [2(H- - M)D - 2MH) + 2 H M)D(22, 1)N FLOPs in forward pass and 2(H M)DD, HM M parameters. Detailed derivations are provided in Appendix D.
3
Experimental Results
In this section, we empirically study the advantages of FiSHformer on various tasks and benchmarks, including language modeling WikiText-1033 (Section 3.1), machine translation IWSLT" 14 De-En and WMT' 14 (Section 3.2), image classification on ImageNet (Section 3.3), time series classi- fication the UEA benchmark (Section 3.4), and reinforcement learning the D4RL Benchmark (Section 3.5). We aim to show that: (i) FiSHformers improve the efficiency and accuracy upon the MHA baseline: (ii) FiSH universal method that be applied state-of-the-art transformer models to improve their performance on large-scale applications. In Section 4, we also show that FiSH helps reduce the redundancy between attention heads.
We compare FiSHformers, Hard FiSHformers, GFiSHformers, and Hard GFiSHformers with the baseline MHA softmax transformers. In our experiments, we apply the discriminative relaxation explained Remark 3 on our FiSHformers to make the mixture weights Pkj learnable parameters. For GFiSHformers/Hard GFiSHformers,
choose the nonlinear mapping linear neural network. All of our results are averaged over 5 runs with different seeds. More details on datasets, models, and training provided in Appendix A. Our PyTorch code with documentation can be found at
be a ReLU followed by
3.1 WikiText- 103 Language Modeling
Models and baselines We compare the and 4-global- head FiSHformers with the 8-head softmax transformers [75]. Each model has 16 layers, and our training follows the setting from [66].
Results Perplexity: Table 3.1 demonstrates that our 2/4-global-head (f)rirrrorerrs and their hard versions obtain comparable or better PPLs than the corresponding 8 head MHA baseline

---

Machine translation BLEU scores of 2- 2-global-head (C))iSHformers compared to the 4- head baseline on IWSLT14 De-En dataset. Our methods perform on par or better than the haseline while being more efficient.
Table 2:
Table 3: Machine translation BLEU scores of 2-global-heas -had (G)FiSH linear transformers com- pared to the 4-head baseline linear on the IWSLT14 De-En henchmark. Our methods significantly out- perform the linear baseline.
Method
BLEU score
Method
BLEU score
Sofmmax heads
34.42
Linear heads
28.22
Hard Fishformer global heads
34.31
Hard LFiSHformer 2 global heads
30.24
FiSHformer 2 glohal heads
34.38
1. FiSHformrr 2 global heads
29.63
Hard GFiSHformer 2 global heads
34.54
Hard GLFiSHformer global heads
29.20
GFiSHfomeer global heads
34.71
GLFiSHoonner 2 global heads
29.46
WikiText- 103. Interestingly, the 2-global-head (G)riSHformeess perform par with the 8-head baseline even though only global attention matrices are used to span all local attention matrices, indicating that the attention matrices in MHA indeed redundant and the representation capacity of local attention matrices in (G)FiSH, though being generated from only 2 global bases, is comparable those in the 8-head MHA.
Efficiency: In Fig. 3A and 3B, we presents the reduction ratio of train and test FLOPS, respectively, of our 2-global-head GFiSHformer vs. the baseline 8-head MHA transformer as functions of model dimension D and sequence length N. In Fig. 3C and 3D, we show the reduction ratio of model size and GPU memory usage at test time, respectively, of our 2-global-hear GFiSHformer same bascline. We observe that the efficiency advantage of GFiSHformer over the baseline grows with D and N, making it more suitable and superior for large-scale applications. Note that the model size in terms of the number of parameters does not depend on the sequence length N, and from our experiments,
the
observe that the GPU memory usage reduction ratio is almost the same for different sequence lengths. More efficiency analysis results on this language modeling task are provided in Section 4 and Appendix C. Also, Figure 5 in Appendix B.2 shows the train and test PPL of (frrrrrr and the MHA softmax transformers. In our experiment, 4-global-head GFiSHformers obtain the best validation PPL.
3.2 Machine Translation
In this section, we examine the performance of (G)FiSrformer on the neural machine translation task, an important task in natural language processing in which the sequence lengths of the input are not the same. We first compare (G)rrmrrrersss with the baselines MHA softmax transformers on the IWSLT' 14 De-En [11] and then scale up our experiments to the WMT' 14 En-De [45]. On these tasks, we calculate the BLEU scores for evaluation.
Models and baselines For the IWSLT' 14 De-En task, compare 2-global-heads (G)rrSerreerss with the baseline 4-head softmax transformer. Each model consists of 12 layers. 6 layers for an encoder and the other 6 layers for decoder. Our experiments follow the setting on fairseq. For the WMT 14 En-De task, we use similar models as in the IWSLT' 14 De-En task. However, we compare (G)rrrrrrrress of and global heads with the 16-head MHA softmax baseline. Our training and model setting are the same as those in [53].
Results As shown in Table 2 and 4, (G)rissoormess outperform at least par with the baseline MHA softmax transformers. Again, these results indicate rich representations of the local attention matrices generated by (G).i Furthermore, (ffrrer outperforming Hard FSfrrrrr in all settings suggests the positive value of adding noise into the models to turn them into proper probabilistic model. Nevertheless, it is worth noticing that Hard FSrromeeer is more efficient than (G)rirrrrerr.. Fig. 4 in Appendix B. summarizes the advantage in efficiency of 2-global- head GFiSHformer over the 4-head bascline on the IWSLT' 14 De-En task. These advantages of GFiSHformer grow with the model dimension D.
3.3 Image Classification on ImageNet
The advantages of FiSffrrrrr also hold across different data modalities. To illustrate this point, in this section, we apply (G)FiSH to Swin transformer [44], a
vision transformer architecture, for the image classification task on the ImageNet dataset [20]. The baseline Swin-T we use has total of 12 layers, across 4 stages of transformer blocks with 3, 6, 12, and 24 heads each. Our GFiSH Swin-T uses and 12 global attention heads at the last two stages. The model and training follow the settings in [44]. We summarize results in Table 5, Our GFiSHformer is only
7

---

Table 4: BLEU scores of FiSHoreesss with various numbers of shared heads compared the 16-head baseline on the WMT' 14 En-De machine translation. Our methods obtain comparable/better results than the baseline while being more efficient.
Table 5: ImageNet Image Classification accuracy scores, FLOPs, and number of parameters Swin Transformer. comparing between baseline Swin-T and our GFiSH Swin-TT Baseline results from [44] are provided in parentheses. The Swin-T baseline uses 12 and 24 attention heads in the last two stages while our GFiSH Swin-T uses only 6 and 12 global attention heads the last two stages.
Method
BLEL
Sofmax heads
29.38
Hard FiSHformer 8 glohal heads
29.32
HiSHformer global heads
29.57
Method
Acc
Acc
FLOPs
Params
Hard GFiSHformer 8 global heads
29.27
top-1
top-5
(10")
GroHHormerr global heads
29.42
Softmax-1222
81.20
95.50
4618.24
28.3M
Hard GFiSHformer 4 global heads
28.97
Hard GFSSH-6/12
81.11
95.44
4372.48
26.2M
GFiSHfommer 4 global heads
29.34
Table 6: The GFiSHformer vs. the baseline soft- max transformer on the UEA Time Series Classifi- cation Archive benchmark [5]. The GFiSHformer performs on par with the baseline while heing more efficient. We also include the reported results from [83] and [81] (in parentheses) in addition to our reproduced results. The experiment setups and configurations for the baseline and our GFiSH- former are the same as in [81] (for the PEMS- UWaveGestureLibbaay datasets) and [83] (for other tasks).
Table 7: The GFiSHFormer vs. the baseline soft- max transformer on the continuous control tasks from D4RL benchmark [29]. The GFiSHFormer yields comparable results to the baseline while be- ing more efficient. also include the reported results from [81] (in parentheses) in addition to our reproduced results.
Enviromment/MMdeel
Bexeline sefimax
GFiSHFormer
SP, SelfRegulationSCP2.
MEDIUM-EXPERR
CALFRHARTAH
(83.80)
HOPPER
1 (104.40)
110.60
Madaset/Model
Boseline softmax
Giishhormmer
WALKER
108.70 (107.70)
108.30
ETHANOL CONCENTRATON
32.08 (33,70)
33.70
MEDIUM- ROPLLY
FACEDETECTION
68.70 (68.10)
68.57
HANDWRIFING RITING
32,08 (M0.50)
31.55
HOPPER
85.61 (79.70)
HEARTBEAT
75.77 (77.60)
76.10
JAPANESEVOWELS
99.46 (99.40)
99.37
PEMS-SP
82.66 (82.10)
HALFCHECTAI
42.28 (42.40)
41.35
SELFREGULATIONSCT
91.46 (92.50)
90.56
HOPPER
61.47 (64.20)
63.44
EELFREGULATIONSCP.
54,72 (53.90)
54.81
SPOKENARARICDIGITS
99.33 (99.30)
WALKER
(70.60)
67.07
UWWVEGIITTURELLIRRARY
84.45 (85.60)
85.01
REWARD
81.19 (79.00)
AVERAGE ACCURACY
72.07 (72.27)
slightly more efficient than the bascline in this case because the sequence length per window for this task is small, i.e. N 49. However, like with the previous language tasks and as pointed by formula of computational cost and model complexity reduction in Section 2.5, these advantages grow with larger D and N.
3.4 UEA Time Series Classification
We compare the accuracy of the GFiSHformer and the baseline softmax transformers trained on the UEA Time Series Classification Archive benchmark [5]. In Table 6, we show that GFiSHformers perform on par with the baselines. For each classification task in this benchmark, the number of GFiSHformer's global heads is half the number of heads in the baseline softmax transformers. The experiment setups and configurations for the baseline and our GFiSHformer are the same as in [81] (for the PEMS-SF, SelfRegulationSCP2. UWaveGiestrrll.bbee
datasets) and [83] (for other tasks).
3.5 Reinforcement Learning on the D4RL Benchmark
We also demonstrate the benefits of GFiSHformers on reinforcement learning. In Table 7, we report the results of the GFiSHformer and the softmax transformer trained for the continuous control tasks from D4RL benchmark [29] to evaluate the model performance the offline reinforcement learning. On average, the 2-global-heads GFiSHformers perform comparably with the 4-head trans transformer baselines. For this benchmark, follow the architecture and training configuration from [81].
3.6 FiSHformer's is more effective than other methods for head-redundancy reduction
To futher demonstrate the effectiveness of our method, we compare FiSHformers against the head- redundancy reduction method in [16] on the WMT' 14 machine translation task. [16] proposes the adaptively sparse transformer (AST), reducing redundancy within each head by zeroing out low- attention scores. In comparison, the results further confirm the effectiveness of our method since the
8

---

Table 8: Sayer-Average mean and variance of L2 distances between heads of models trained for the WikiText- 103 language modeling task.
Table 9: Layer-average number of principal com- ponents for 95% variance explained of the covari- ance of attention matrices (WikiText- 103 models).
Method
Mean
Variance
Method
Meun
Softmax 8 heads
1.62
0.66
Softmax heads
296
Linear heads
1.90
0.06
Linear heads
GFiSHformer 2 globall heads
2.93
2.62
GFiSHformer 2 global heads
8955
GHSHHoomerr 4 global heads
3.59
3.95
GFISHformer global heads
1408
GFSSHoorerr 6 global heads
3.37
2.78
GFiSHformer global heads
1228
BLEU score of FiSHformer and GFiSHformer are 27.26 and 27.67, respectively, better than that of AST, which is 26.93. All models share the same architecture, with 12 transformer layers, 6 encoder, and 6 decoder layers. Our FiSHformers have 4 global heads and 8 local heads per layer while 8 attention heads are used in each AST layer.
3.7 Beyond Multi-Head Softmax Transformers
We show that (G)FiSH can be applied top of many transformer architectures improve their performance including the linear transformers [37] and the SoTA transformer with noisy back- translation [26]. More results of combining (G)FiSH with efficient transformers are in the Appendix.
Applying (G) on Linear Transformers Linear transformers [37] is a class of efficient trans- formers that linearize the softmax kernel in Eqns. and 2 when computing attention matrices. We apply FG) on linear transformers trained for the IWSLT14 De-En machine translation task and summarize the results in Table 3. The empirical results verify that applying (G)FiSH using only 2-global heads on a 4-head linear transformer improves the accuracy of the baseline model.
(G)FiSH Improves the -ftte-of-the-Art Noisy Back-Translation We apply an 8-global-head Hard GFiSH on the transformers trained with noisy back-translation [26] for the 1M En-De translation task and obtain the BLEU score of 33.45. This result is comparable to the SoTA result of 33.52 from the transformers trained with noisy tack-translation but our model is more efficient.
4 Empirical Analysis
We study models trained for the WikiText- 103 language modeling task this section.
Efficiency Analysis In this section, we further investigate the efficiency reduction of 2-global-head GFiSHformers over the 8-head baseline as function of the number of heads in Fig. 7 and 8 and compare the efficiency of our FiSH-based models in Fig. 6. Fig. 6, 7, 8 and details on our setting are provided in Appendix C. From Fig. and 8, we observe that when using fewer number of global heads. GFiSHformers achieve significantly more computation reduction (in both training and inference). Furthermore, Fig. 6 shows that the efficiency measures, i.c. FLOPs, model size, and GPU memory usage, of all FiSH-based models we study in this paper follow similar patterns.
FiSHformer Helps Reducing Head Redundancy We show that (G)rrrerrrr attain more significant distances between heads than the baseline. Thus, our models capture more diverse patterns across heads than the baseline. For a given pre-trained model, we compute the pair-wise La distances between heads in the same layer. We show the layer-average mean and variance of distances between heads in GFiSHformers compared with those in the MHA softmax baselines in Table 8. We provide additional results for Hard GFiSHformers and Hard FiSHformer in Table 12 in the Appendix.
Eigen Analysis We show that heads in GFiSHformer lic on digees-nim subspace compared to those in FiSHformer. This justifies our use of nonlinearity mapping to generate local heads from global heads. Using a pre-trained model, we first compute the covariance matrix of the vectorized attention scores of the I-th layer: C² 1 DM (A
T. We use spectral decomposition to represent Cl in terms of eigenvalues and eigenvectors, namely, C² = Σn Auano, Without losing generality, we assume that eigenvalues are sorted in descending order. We illustrate the layer-average number of principle components that are needed to explain 95% variance in Table 9. Interestingly. Table 9 shows that attention matrices in all of our proposed FiSH-based models lie on higher-dimensional subspace than those in the baseline MHA softmax transformers, which indicates that our models achieve better representational capacity than the baseline, confirming the advantage of FG)FiSH over MHA. Table 13 in the Appendix provide additional results for Hard (forrrrrrrmr..

---

Table 10: Perplexity (PPL) on WikiText- 103 of 2- global-head FiSHformer vs. 2-global-head MiSH- former compared to the 8-head baseline. MiSH- former attains worse PPL. than FiSHformer.
Table 11: Perplexity on WikiText- 103 of GFISH- former with various number of global heads com- pared with the 8-head baseline.
Method
Valid PPL.
Test PPL
Method
Valid PPI.
Test PPL.
Softmax heads
33.15
34.29
Sofumax 8 heads
33.15
34.29
GFiSHformer global heads
32.80
33,80
HSSHformer 2 global heads
34.01
34,96
GFiSHformer 4 global heads
32,68
33.71
MiSHformer global heads
35.11
36.28
GFISHformer 2 global heads
33.21
34.48
Admixture vs. Mixture of Heads We compare the transformer with a mixture of heads and the transformer with an admixture of heads. We show that the transformer with a mixture of heads yields worse accuracy. We summarize our results on the WikiText- 103 language modeling task in Table 10.
Ablation Study on the Effecc of the Number of Global Heads on FiSH-based Models We investigate the accuracy. efficiency. and representation capacity of FiSH-based models under different numbers of global heads on the WikiText-101 language modeling task. Since GFiSH obtains the best accuracy on this task, we use GFiSH as a study case in this section and report our results on accuracy in Table 11. Ablation results on efficiency are summarized in Fig. 7, 8 in Appendix C, and ablation results on representation capacity are provided in Table 8, 9.
Related Work
Efficient Transformers Efficient transformers have been developed to reduce the quadratic computa- tional and memory cost of transformers [62]. A class of efficient transformers are sparse transformers which design the attention matrix to have sparse structure [55, 42, 58, 12, 7J. Another class of efficient transformers are models that integrate different access patterns for better coverage [12, 33]. These access patterns can also be learned from the data [40, 62, 71]. In other works, a side memory module used to access multiple tokens simultancously [41, 69, 3, 7J. Recently, low-rank and kernelization methods have been proposed to improve the computational and memory efficiency of computing self-attention [74, 79, 37, 14, 50, 67, 52, 56]. Our (G)ssSrorrress are complementary to these methods.
Redundancy in Transformers Most of the neurons and heads in the pre-trained transformer redundant and can be pruned when applied on downstream tasks [18, 47, 23]. The contextualized embeddings in pre-trained networks under this redundancy have also been studied to demonstrate that the representations learned within these models are highly anisotropic [48, 27]. Knowledge distillation and sparse approximation have also been used enhance the efficiency of transformers, including [65, 70,7 78, 64]. Our FiSH-based approach are complementary to these methods
Mixture Models for Transformers Recently, mixture models have been employed study and enhance transformers. Among these works is switch transformers [28] that uses the routing algorithm in Mixture of Experts (MoE) to decrease the communication and computational costs in transformers. [49] derives a GMM for each attention head. Other works that combine mixture models with transformers include [51, 13, 36).
6 Concluding Remarks
In this paper, we proposed the FiSHformer, a class of transformers that samples local attention matrices from a finite admixture global attention matrices. FiSHformers and their generalized version GFiSHformers attain better computational cost and model complexity than their baseline MHA softmax transformer counterparts. Furthermore, Hfrrees help increase the diversity between attention heads. It is worth noting that there is potential negative societal impacts of FiSHformers. Also, global attention matrices in FiSHformers currenly do not have any structure, and this is limitation of our model. It is interesting to impose additional structures such low-rank and sparsity into the global attention matrices. Finally, establishing theoretical guarantee for optimization algorithms [25, 24, 34] for solving FiSHformers is also important future direction to improve the efficiency of FisHformers.
A Acknowledgements
This material is based on research sponsored by the AFOSR MURI 1495500-1-1-0550 the ONR grant 1-001-20-112092 the MURI N00014-20-1-2787. and the NSF under Grant# 2030859 to the Computing Research Association for the CIFellows Project (CIF2020-UCIAA-3) NH acknowledges support from the NSF IFML 2019844 and the NSF AI Institute for Foundations of Machine Learning.
10

---

References
[1] Rami Al-Rfou, DK Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. In Thirty-Third AAAI Conference on Artificial Intelligence, 2019.
[2] Rami AI-Rfou, Dokook Choe, 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, pages 3159-3166, 2019.
[3] Akari Asai and Eunsol Choi. Challenges in information seeking qa: Unanswerable questions and paragraph retrieval. arXiv preprint arXiv:2010. /1955, 2020.
[4] A. G. Bacharoglou. Approximation of probability distributions by convex mixtures of Gaussian measures. Proceedings of the American Mathematical Society, 138:2619-200 162892222,, 2010.
[5] Anthony Bagnall, Hoang Anh Dau, Jason Lines, Michael Flynn, James Large, Aaron Bostrom, Paul Southam, and Eamonn Keogh. The uea multivariate time series classification archive, 2018. arXiv preprini arXiv: 1811.0007, 2018
[6] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint (rXXv::409.047. 2014.
[7] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long long-document transformer. arXiv preprint w:Xiv2204.005/555 2020.
[8] Srinadh Bhojanapalli, Ayan Chakrabarti, Himanshu Jain, Sanjiv Kumar, Michal Lukasik, and Andreas Veit. Eigen analysis of self-attention and its reconstruction from partial computation. arXiv preprint wwXiv:2106.08822 2021.
[9] David M Blei, Andrew Y Ng. and Michael Jordan. Latent dirichlet allocation. the Journal of machine Learning research, 1022, 2003.
[10] Tom Brown and et al. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901, 2020.
[11] Mauro Cettolo, Jan Niehues, Sebastian Stüker, Luisa Bentivogli, and Marcello Federico. Report on the 1tth iwslt evaluation campaign, iwslt 2014. In Proceedings of the International Workshop on Spoken Language Translation, Hanoi, Vietnam, volume 57, 2014.
[12] Rewon Child, Scott Gray, Alec Radford, and llya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904. 10509, 2019.
[13] Sung Min Cho, Eunhyeok Park, and Sungjoo Yoo. Meantime: Mixture of attention mecha- nisms with multi-temporal embeddings for sequential recommendation. In Fourteenth ACM Conference on Recommender Systems, pages 515-520, 2020.
[14] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca 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 Representattinns, 2021.
[15] Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. What does BERT look at? analysis of BERT's s attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 276-286, Florence, Italy, August 2019. Association for Computational Linguistics.
[16] Gonçalo M Correia, Vlad Niculae, and André FT Martins. Adaptively sparse transformers. arXiv preprint arXiv: 2019.
[17] Zihang Dai, Zhilin Yang, Yiming Yang. Jaime Carbonell, Quoe V Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint 17X2v.190..02860,. 2019.
11

---

[18] Fahim Dalvi, Hassan Sajjad, Nadir Durrani, and Yonatan Belinkov. Analyzing redundancy in pretrained transformer models. arXiv preprint arXiv:2004. 04010, 2020.
[19] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. arXiv preprint arXiv: 0t0/8800..3...9 2018.
[20] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hicrarchical image database. 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Ieee, 2009.
[21] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 1810. 04805, 2018.
[22] 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 16x 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
[23] Nadir Durrani, Hassan Sajjad, Fahim Dalvi, and Yonatan Belinkov. Analyzing individual neurons in pre-trained language models. arXiv preprint arXiv:2010.0269) 2020.
[24] R. Dwivedi, N. Ho, K. Khamaru, M. J. Wainwright, M. I. Jordan, and B. Yu. Sharp analysis of innttatioo-maximizaaiion for weakly identifiable models. AISTATS, 2020.
[25] R. Dwivedi, N. Ho, K. Khamaru, M. J. Wainwright, M. I. Jordan, and B. Yu. Singularity, misspecification, and the convergence rate of EM. Annals of Statistics, 44:2726-2755, 2020.
[26] Sergey Edunov, Myle Ott, Michael Auli, and David Grangier. Understanding socktrranslttion at scale. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 489-500, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.
[27] Kawin Ethayarajh. How contextual are contextualized word representations? comparing the geometry of bert, elmo, and gpt-2 embeddings. arXiv preprint wwXiv:/90.0005//1 2019.
[28] William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2101.03661, 2021.
[29] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.
[30] S. Ghosal and A. van der Vaart. Entropies and rates of convergence for maximum likelihood and bayes estimation for mixtures of normal densities. Ann. Statist., 29: 1233-112,,,, 2001.
[31] Maosheng Guo, Yu Zhang, and Ting Liu. Gaussian transformer: a lightweight approach for natural language inference. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 33, pages 6489-6496, 2019.
[32] John Hewitt and Percy Liang. Designing and interpreting probes with control tasks. In Proceed- ings of the 2019 Conference Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing LEMNLP-JJCNLL pages 2733 2743, Hong Kong. China, November 2019. Association for Computational Linguistics.
[33] Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidimensional transformers. arXiv preprint arXiv:191..12190 2019.
[34] Nhat Ho, Tongzheng Ren, Sujay Sanghavi, Purnamrita Sarkar, and Rachel Ward. An exponen- tially increasing step-size for parameter estimation in statistical models. arXiv preprint arXiv: 2205.07999, 2022.
[35] Jeremy Howard and Sebastian Ruder. Universal language model fine-tuning for text classi- fication. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 328-339, Melbourne, Australia, July 2018. Associ- ation for Computational Linguisties.
12

---

[36] Junyan Jiang, Gus G Xia, Dave B Carlton, Chris N Anderson, and Ryan H Miyakawa. Trans- former vae: A hierarchical model for structure-aware and interpretable music representation learning. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 516-520. IEFF, 2020.
[37] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In International Conference Machine Learning, pages 5156-5165 PMLR, 2020.
[38] Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. Structured attention networks. arXiv preprint arXi:: 1702000887 2017.
[39] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
[40] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001. 04450,445111. 2020.
[41] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention- based permutation-invarian neural networks. In International Conference on Machine Learning. pages 3744-3753, PMLR, 2019.
[42] Peter J Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. arXiv preprini 180i 10198, 2018.
[43] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: robustly optimized bert pretraining approach. arXiv preprint arXiv 1692, 2019.
[44] 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 IEFE/CVF International Conference on Computer Vision (ICCV), pages 10022- October 2021.
[45] Matouš Macháëck and Ondřej Bojar. Results of the wmt14 metries shared task. In Proceedings of the Ninth Workshop on Statistical Machine Translation, pages 293-301, 2014.
[46] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[47] Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one? In H. Wallach, Larochelle, A. Beygelzimer, F. Bauché-BBue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[48] Jiaqi Mu and Pramod Viswanath. All-but-the-top: Simple and effective postprocessing for word representations. In International Conference on Learning Representations, 2018.
[49] Tam M Nguyen, Tan M Nguyen, Dung D Le, Duy-Khuong Nguyen, Viet-Anh Tran, Richard G Baraniuk, Nhat Ho, and Stanley Osher. Improving transformers with probabilistic attention keys. In International Conference on Machine Learning, pages 16595-16621. PMLR, 2022.
[50] Tan M Nguyen, Richard Baraniuk, Robert Kirby, Stanley Osher, and Bao Wang. Momentum transformer: Closing the performance gap between self-attention and its linearization. In Mathematical and Scientific Machine Learning, pages 189-204. PMLR, 2022.
[51] Tan M Nguyen, Minh Pham, Tam Nguyen. Khai Nguyen, Stanley J Osher, and Nhat Ho. Fourierformer: Transformer meets generalized fourier integral theorem. In Advances Neural Information Processing Systems (NeurIPS), 2022.
[52] Tan M Nguyen, vai Suliafu, Stanley Osher, Long Chen, and Bao Wang. Fmmformer: Efficient and flexible transformer via decomposed near-field and far-field attention. In Advances in neural information processing systems, volume 34, pages 29449-29463 2021.
13

---

[53] Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation. In Proceedings of the Third Conference on Machine Translation: Research Papers, pages 1-9, Brussels, Belgium, October 2018. Association for Computational Linguistics.
[54] Kishore Papineni, Salim Roukos, Todd Ward, and Wei jing Zhu. Bleu: a method for automatic evaluation of machine translation. pages 311-318, 2002.
[55] 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.
[56] Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference Learning Representations, 2021.
[57] Jonathan K Pritchard, Matthew Stephens, and Peter Donnelly. Inference of population structure using multilocus genotype data. Genetics, 155(2):945-95) 959, 2000.
[58] Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint wrxiv:191..02977 2019.
[59] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. OpenAl report, 2018
[60] 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.
[61] Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ ques- tions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2383 2392,, Austin, Texas, November 2016. Association for Computational Linguistics.
[62] 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.
[63] 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))
2015.
[64] Hassan Sajjad, Fahim Dalvi, Nadir Durrani, and Preslav Nakov. Poor man's bert: Smaller and faster transformer models. arXiv e-prints, pages arXiv 2004, 2020.
[65] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 108, 2019.
[66] Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers secretly fast weight programmers. In International Conference on Machine Learning, pages 9355-9366. PMLR, 2021.
[67] 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.
[68] David R So, Chen Liang, and Quoe V Le. The evolved transformer. arXiv preprint arXiv: /9011//1111 2019.
[69] Sainbayar Sukhbaatar, Edouard Grave, Guillaume Lample, Herve Jegou, and Armand Joulin. Augmenting
with persistent memory. arXiv preprint arXiv: 197.00147 2019.
[70] Siqi Sun, Yu Cheng, Zhe Gan, and Jingjing Liu. Patient knowledge distillation for bert model compression. arXiv preprint arXiv: 1908. 195555, 2019.
14

---

[71] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da- Ca-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.
[72] Ian 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, pages 4593 4601, Florence, Italy, July 2019. Association for Computational Linguistics.
[73] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. arXiv preprini arXiv: /2877, 2020.
[74] Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Phillppe Morency, and Ruslan Salakhutdinov. Transformer dissection: An unified understanding for transformer's attention via the lens of kernel. arXiv preprint arXiv: 1775, 2019.
[75] 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, pages 5998-6008, 2017.
[76] Jesse Vig and Yonatan Belinkov. Analyzing the structure of attention in transformer language model. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpret- ing Neural Networks for NLP, pages 63-76, Florence, Italy, August 2019. Association for Computational Linguistics.
[77] 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, pages 5797-5808, Florence, Italy, July 2019. Association for Computational Linguistics.
[78] 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, pages 5797-5808, 2019.
[79] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04760 2020.
[80] Adina Williams, Nikita Nangia, and Samuel Bowman. A broad 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 1 (Long Papers), pages 1112-1122. June 2018
[81] Haixu Wu, Jialong Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Flowformer: Lineariz- ing transformers with conservation flows. In International Conference Machine Learning, 2022.
[82] 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.000 1906.08237, 2019.
[83] George Zerveas, Srideepika Jayaraman, Dhaval Patel, Anuradha Bhamidipaty, and Carsten Eickhoff. A transformer-based framework for multivariate time series representation learning. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. pages 2114-2124, 2021.
15

---

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 6.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 6.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or 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 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 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? [N/A]
(b) Did you mention the license of the assets? [N/A]
(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 obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "rBNMwrEfE6P", "reviewer": "Reviewer_eA9U", "summary": "The authors report the transformer model with global attention heads rather than the local ones as in other types of transformer architectures.", "questions": "It would be interesting to see if the admixture of attention heads is applicable for the image domain as feature sharing is more natural there. Have the authors tried that?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well-written and interesting to read, math is described sufficiently. Learning shared information over the transformer head can be a well scalable feature that can be used in other transformer-like architectures.\n\nWeaknesses:\n\nThe authors performed several benchmarks, however, the improvement over the vanilla model is marginal. Even though the experiment was performed for 5 runs with various random seeds, it is hard to judge on this improvement as various parameters can affect performance.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "lG2ALRYec3", "reviewer": "Reviewer_tCZN", "summary": "This paper introduces FiSHformers, a Transformer model with a Finite Admixture of Shared Heads. FiSHformers calculate $M < H$ global heads and construct/sample the full attention heads from the $M$ heads, thus reducing a certain level of computations in constructing Transformer models.", "questions": "1. In this paper, the authors assume $A_j$ comes from different distributions ( the learned attention heads are diverse ) but with the same M and $\\theta$. I was wondering how this assumption is justified. \n\n2. Is it possible to measure and compare the sampled set of $A_j$s and original $A_j$s ? I mean, if there is a way to show that we can always construct original attention heads from sampled attention heads, or the former contains the latter, the claims on heads redundancy may be stronger. \n\n3. How to determine the number of $M$ for better or similar performance. ", "limitations": "No mentions of limitations, but do analyze the social impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nOverall, the idea is interesting. The analysis from a probabilistic viewpoint and applying the admixture model to attention calculation is novel. The paper is well organized and presented. The experimental results presented in this paper show that Fishformers obtained comparable or better results than Transformer models with the calculation of global attention matrices. In addition, the authors show that the purposed structure can also work with some linear Transformers.\n\nWeaknesses:\n\nMy main concern is about the significance of the work.\n\n1. There are no theoretical guarantees that we can obtain the same or better performance with a strictly less number of global shared components.\n\n2. Although the number of FLOPs is shown to be less (less global attention is calculated, depends on $H$) using FiSHFormer model and its variants, the computation complexity remains the same (depends on $N$).\n\n3. The author also mentions the head redundancy issue, but $L_2$ distances among heads are more like a reflection but not determinating factors for the claim that FiSHFormer is more efficient than other Transformer variants (low-rank, parameter sharing heads, etc) in terms of the issue. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "kw3NoAK5vW0", "reviewer": "Reviewer_ofWV", "summary": "The paper proposes to use a Transformer with a Finite Admixture of  Shared Heads.\nThe idea is to directly learn these attention matrices rather than the local ones as in other  transformers. At the core of the method they sample local attention matrices from an 73 admixture of a small number of global attention matrices. \nThe paper shows numerous results on various benchmarks which support their claims. \n", "questions": "I see areas of similarity to the work: https://arxiv.org/abs/2110.08678 (Improving Transformers with Probabilistic Attention Keys). Please explain how your work differs.", "limitations": "Please see questions section. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nI am not familiar with the literature, but the results are well established.\nThe experiments show advantages of their method, pointing to new directions of improving transformers.\nThe paper is fairly clearly written.\n\nWeaknesses:\nThe authors' description of the experimental results are not accurate enough. \nI would be happy to see results on more benchmarks. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept