Efficient Content-Based Sparse Attention with Routing Transformers
Authors: Aurko Roy*
Mohammad Taghi Saffar*
David Grangier
Ashish Vaswani
Venue:  (2020)
Keywords: Sparse attention
autoregressive
generative models

Abstract: Self-attention has recently been adopted for a wide range of sequence modeling
problems. Despite its effectiveness, self-attention suffers quadratic compute and
memory requirements with respect to sequence length. Successful approaches to
reduce this complexity focused on attention to local sliding windows or a small
set of locations independent of content. Our work proposes to learn dynamic
sparse attention patterns that avoid allocating computation and memory to attend
to content unrelated to the query of interest. This work builds upon two lines of
research: it combines the modeling flexibility of prior work on content-based sparse
attention with the efficiency gains from approaches based on local, temporal sparse
attention. Our model, the Routing Transformer, endows self-attention with a sparse
routing module based on online k-means while reducing the overall complexity of
attention to O(n^{1.5}d) from O(n^2d) for sequence length n and hidden dimension
d. We show that our model outperforms comparable sparse attention models on
language modeling on Wikitext-103 (15.8 vs 18.3 perplexity) as well as on
image generation on ImageNet-64 (3.43 vs 3.44 bits/dim) while using fewer self-attention layers.
Code will be open-sourced on acceptance.

Under review as a conference paper at ICLR 2020
EFFICIENT CONTENT-BASED SPARSE ATTENTION WITH ROUTING TRANSFORMERS
Anonymous authors Paper under double-bling review
ABSTRACT
Self-attention has recently been adopted for wide range of sequence modeling problems. Despite its effectiveness, self-attention suffers quadratic compute and memory requirements with respect sequence length. Successful approaches reduce this complexity focused on attention to local sliding windows or a small set of locations independent of content. Our work proposes learn dynamic sparse attention patterns that avoid allocating computation and memory to attend content unrelated to the query of interest. This work builds upon two lines of research: it combines the modeling flexibility of prior work on content- content-based sparse attention with the efficiency gains from approaches based on local, temporal sparse attention. Our model, the Routing Transformer, endows self-attention with sparse routing module based on online k-means while reducing the overall complexity of attention O(n d) from O(n²d) d) for sequence length n and hidden dimension d. We show that our model outperforms comparable sparse attention models on language modeling Wikitext- -00 (15.8 18.3 perplexity) as well as image generation on ImageNet - 64 (3.43 vs 3.44 bits/dim) while using fewer self-attention layers.
INTRODUCTION
Generative models of sequences have witnessed rapid progress driven by the application of attention to neural networks. In particular, Bahdanau et al. (2014); Cho et al. (2014); Vaswani et al. (2017) relied attention to drastically improve the state-of-th ofe art in machine translation. Subsequent research (Radford et al., 2018; Devlin et al., 2018; Liu et al., 2019; Yang et al., 2019) demonstrated the power of self-attention in learning powerful representations of language to address several natural language processing tasks. Self-attention also brought impressive progress for generative modeling outside of language, e.g. image (Parmar al., 2018; Menick and Kalchbrenner, 2018; Child et al., 2019) and music generation (Huang et al., 2018; Child et al., 2019).
Self-attention operates over sequences step-wise manner: at every time-step, attention assigns an attention weight to each previous input element (representation of past time-steps) and uses these weights to compute
representation of the current time-step as a weighted sum of the past input elements (Vaswani et al., 2017). Self-attention (Shaw et al., 201 8) is particular case of attention (Bahdanau al., 2014; Chorowski al., 2015; Luong al., 2015).
Self-attention is commonly used in auto-regressive generative models. These models generate observations step-by-step, modeling the probability of the next symbol given the previously generated ones. At every time step, self-attentive generative models can directly focus on any part of the previous context. In contrast, recurrent neural networks (RNNs) and convolutional neural networks (CNNs) have direct interactions with only local neighborhood of context around the current time step.
This advantage however comes price: unlike recurrent networks convolution networks, the time and space complexity of self-attention is quadratic in n. the length of the sequence. Specifically, for every position 5 n. self-attention computes weights for its whole context of length which induces complexity of Eisn i n(n- - 1)/2. This makes it difficult to scale attention based models to modeling long sequences. However, long sequences are the norm in many domains, including music, image, speech or video generation.

---

Under review as a conference paper at ICLR 2020
Therefore, important research direction is to investigate sparse and memory efficient forms of attention in order to scale to tasks with long sequence lengths. Previous work has proposed data independent or fixed sparsity patterns bounding temporal dependencies, such as local or strided attention. At each time step, the model attends only to a fix number of time steps in the past (Child al., 2019). Extensions to local attention have suggested learning the length of the temporal sparsity for each attention module in the network (Sukhbaatar et al., 2019). These strategies draw their inspiration from RNNs and CNNs and bound their complexity by attending only representations summarizing local neighborhood of the current time step. Their attention matrices (matrices containing the attention weights for every pair of previous, current time-step) are natively sparse and requires instantiating only non-zero entries. While these approaches have achieved good results, fixing the sparsity pattern of a content based mechanism such as self-attention can limit its ability to pool in information from large contexts.
As an alternative to local attention, Correia et al. (2019) considers content-based sparsity, an approach allowing for arbitrary sparsity patterns. This formulation however does require instantiating full dense attention matrix prior to sparsification through variants of Lu-sparsity or sparsemax approximations (Blondel et al., 2019).
The present work builds upon these two lines of research and proposes to retain the modeling flcxibility of content-based sparse attention while leveraging the efficiency of natively sparse attention matrices. Our formulation avoids sparsemax variants and relies on clustering of attention instead. Each attention module considers clustering of the space: the current time-step only attends to context belonging to the same cluster. In other word, the current time-step query is routed to a limited number of context through its cluster assignment. This strategy draws inspiration from the application of k-means clustering to Non-negative Matrix Factorization (NMF) (Lee and Seung, 2001; Ding et al., 2005; Kim and Park, 2008), which relevant the sparsification of non-negative matrices like attention matrices.
Our proposed model, Routing Transformer, combines our efficient clustered- sparse attention with classical local attention to reach excellent performance both for language and image genera- tion. These results are obtained without the need to maintain attention matrices larger than batch length which is the case with the segment level recurrence mechanism used in Dai et al. (2019); Sukhbaatar et al. (2019). We present experimental results on language modeling (Wikitext 103 and anwik-8) 8) and unconditional image generation (ImageNet-64 64).. Routing Transformer sets new state-of -hee----thaeaeeee tttthe-rrt art while having comparable or fewer number of self-attention layers and heads, both Wi k text-10: 03 (15.8 vs 18.3 perplexity) and ImageNet-66 (3.43 vs 3.44 bits/dim). We also report competitive results on Snwik-8 (0.99 vs 0.98 perplexity).
RELATED WORK
Attention with Temporal Sparsity: Research on efficient attention neural models parallels the advent of attention-based architectures. In the context of speech recognition, Jaitly et al. (2015) proposed the Neural Transducer which segments sequences in non-overlapping chunks and attention is performed in each chunk independently. Limiting attention to a fixed temporal context around the current prediction has also been explored in Chorowski et al. (2015), while Chiu and Raffel (2017) dynamically segment the sequence into variable
Hierarchical attention strategies have also been explored: the model first considers which part of the inputs should be attended to before computing full attention in contiguous neighborhood of the selected area (Gregor et al.. 2015; Xu et al., 2015: Luong et al., 2015). Later, hierarchical attention has been simplified by Liu et al. (2018 8) that alternates coarse layers (attending to the whole sequence at lower temporal resolution) with local layers (attending to neighborhood of the current prediction).
This alternating strategy is also employed by Child et al. (2019), which introduces bounded and strided attention, i.e. attending to a fixed context in the past at a subsampled temporal resolution. This work formalizes such strategy using sparse attention formalism, showing how it relates to full attention with a specific sparsity pattern in the attention matrix. It shows that sparse attention is sufficient get ofate-of-the-an art results in modeling long sequences over language modeling, image generation and music generation. Sukhbaatar et al. (2019) builds upon this work and shows that is is possible to obtain further sparsity by letting the model learn the length of the temporal context
2

---

Under review as a conference paper at ICLR 2020
for each attention module. This work also makes use of the attention cache introduced in Dai et al. (2019), a memory mechanism to train models over temporal contexts which extend beyond the length of the training batches.
Attention with Content-Based Sparsity: The above work mainly relies on two efficient ideas: attending to less elements by only considering a fixed bounded local context in the past, and attending to less elements by decreasing the temporal resolution of context. These ideas do not allow arbitrary sparsity patterns in attention matrices. Content-based sparse attention has been introduced allow for richer patterns and more expressive models. Martins and Kreutzer (2017); Malaviya et al. (2018) propose to compute attention weights with variants of sparsemax. Correia al. (2019) generalizes this approach to every layer in a Transformer using entmax which allows for more efficient inference. This line of work allows for learning arbitrary sparsity attention patterns from data, based on the content of the current query and past context. However, sparsity here cannot be leveraged to improve space and time complexity since sparsemax/entmaal formulations require instantiating the full attention matrix prior to sparsification. This is drawback compared to temporal sparsity approaches. Our work is motivated by bridging this gap and allows for arbitrary sparsity patterns while avoiding to instantiate non-zero entries of attention matrices.
Sparse Computation beyond Attention: Learning models with sparse representationn/actiitttoo for saving time and computation has addressed in the past in various context. Previous work often refers to this goal as gating for conditional computation. Gating techniques relying on sampling and stright-through gradient estimators are common (Bengio et al., 2013; Eigen et al., 2013; Cho and Bengio, 2014). Conditional computation can also be addressed with reinforcement learning (Denoyer and Gallinari, 2014; Indurthi et al., 2019). In the domain of language modeling, related work is the sparsely gated Mixture-of-expee (MOE) (Shazeer et al., 2017) where sparsity is induced by experts and a trainable gating network controls the routing strategy each sub-network.
SELF-ATTENTIN AUTO-REGRESSIOE SEQUENCE MODELING
Auto-regressive sequence models decompose the probability of a sequence x = In) as
p(x) II polsoot1ooee (
(1)
In neural models, the conditional distribution pe (2i+1 is modeled by a neural network with learned parameters 0 and these parameters are typically learned to maximize the likelihood of the training data. In particular, Transformer architectures have shown to reach state-of-the-ane accuracy in several domains, including language modeling (Vaswani et al., 2017; Radford et al., 2018), image generation (Parmar et al., 2018) and music generation (Huang et al., 2). Transformer models compose series of attention modules. Each module refines the input representation by taking weighted average of the representations from the previous modules.
For every module, the input representation is sequence of n vectors x (x (..,,..,,,)) from continuous space of dimension d. Thus one may actually treat the input sequence as a n x matrix X. A self-attention layer operates on this representation. first applies three linear projections,
Q = XWQ. K = XWK, V = XWv,, where Q, K and V are referred to as keys, queries and values, while Wo. WK. Wv are learned projection matrices.
The key and the query matrices determine the n x n attention matrix A = softmax (QK)) where the softmax operator over matrices denotes that the softmax function has been applied to each row. A may be interpreted as matrix of weights in [0, 1] where A; denotes how much query position i at the next layer must pay attention to key position j at the previous layer. In the case of self-attention for auto-regressive models, queries attend only over keys from previous time-steps, i.e.
A = softmax (Itr(QKT)
(3)
where Ir denotes the lower triangular operator. Given the attention matrix A, the next layer represen- tation X' is computed simply as AV. In summary.
X
A
(4)
3

---

Under review as a conference paper at ICLR 2020
In practice, Transformer (Vaswani al., 2017) adds several extensions to this basic self-attention mechanism. In particular, the result X' of performing self-attention is scaled by 1/vd. Moreover, each layer relies on multiple attention heads, i.e. each layer performs multiple projections onto triplet (queries, keys, values) and attention is performed for each head. The attention results from all heads are then concatenated. This strategy allows each head to specialize on different aspects of the input sequence. In addition, Transformer further processes the result of attention through learnable non-linear transformation (multi-layer perceptron, mip) followed by a residual connection and normalization step. i.e.
X' layernorm X' + X)
(5)
X layernorm(mip(X') X),
(6)
where layernorm denotes the parameterized normalization step from Ba et al. (2016). A full Transformer model is therefore a chain of attention modules (Eq. 6) preceded by an embedding module (lcarnable representation for symbols and their positions) and followed by logistic classification module (learnable linear classifier to predict the next symbol).
Our work is interested in the application of the Transformer long sequences, challenging problem since space and time complexity of attention is quadratic in sequence length n. We describe various approaches to sparse attention including ours in the next section.
EFFICIENT
SPARSE ATTENTION
Attention-base models can be problematic for long sequences. For a sequence of length n, the full attention matrix A, as introduced in Section 3, is n x n-dimensional and can be prohibitive to instantiate. This motivates sparse attention models, i.e. models relying on attention matrices which have a majority of zero entries.
For each query, a sparse attention model defines a set of keys which can be attended to. In the following, we introduce the set S; as the set of key positions that the query at position can attend to, ie.
x Σ A.V. JES.
For example, classical causal self attention can attend to every key prior to the current query, which translates to S; {j j < i}. Most previous work on attention sparsity defined such sets purely based on positions, independently of actual query and key vectors. For example, local attention (Luong et al., 2015) considers attending only to a k-long time window prior to the current query, h: S < ij. Child et al. (2019) propose block sparse attention where half the heads perform local attention, and half the heads perform strided attention given by S = {j i j (mod k) = 0, < i}. Sukhbaatar et al. (2019) is also variant of local attention where the cardinality of [S|| is learned from data with an Ln penalty to trade-off sparsity with modeling accuracy.
S =
These local attention sparsity variants are effective in practice since correlation between observations naturally decrease with time for many problems. In our experiments, we actually find that local attention is a surprisingly strong baseline in both image generation and language modeling: for e.g., scaled up Trangrrranfoomerr (Parmar et al., 2018) gets 3.48 bits/dim compared to the 3.44 bits/dim reported in (Child al., 2019). Similarly, scaled up versions of Transformer with local attention and the relative positional encoding scheme of Shaw et al. (2018) are able to get 19.8 perplexity on Rikitext-li Transformer-X XL (Dai et al., 2019) are 18.3 and 0.99 respectively. From an efficiency perspective, local attention is also interesting since sparsity patterns are regular, contiguous memory and known in advance.
and 1.10 bits per byte on enwik-8, 8, while the state-of-the the- results using
In this work, however, we are interested in a more generic formulation of attention sparsity and would like the sparsity pattern to be informed by the data, i.e., S = fxx). This approach has several modeling advantages: it can accommodate data without a clear ordering over observations. For temporal data, it can also discover patterns with greater sparsity if some types of queries have a longer lasting effect on future observations than others. Content- based sparse attention should however be carefully implemented if need to avoid instantiating full attention matrices at any point in time.
4

---

Under review as a conference paper at ICLR 2020
For instance, Correia et al. (2019) infer sparsity from data but their formulation instantiates full attention matrix before finding its sparse counterpart. Next section explains how a natively sparse approach actually be devised inspired by non-negative matrix factorization (NMF).
4.1 CLUSTER ATTENTION WITH NON-NEGATIVE Low RANK APPROXIMATIONS
For any given X n. matrix A, low-rank non -en-tteteeve approximation to it is of the form H = FGT where F, G E Faxk and F, 2 O. This factorization can be interpreted as follows: total items are routed to k representatives determined by the attention matrix F, while each of the representative k items perform full attention on the n items determined by matrix Therefore, the whole attention matrix passes through bottleneck of size k.
NMF studies algorithms to find such approximations (Tandon and Sra, 2010), for instance minimizing the Frobenius norm,
H arg
min
|| FG
GT G=T,F,
Different algorithms have been proposed for that problem, with different trade-off's in terms of theo- retical guarantecs, actual accuracy and efficiency (Lee and Seung, 2001; Hoyer, 2004; Gemulla et al., 2011). In particular, k-means clustering (Lloyd, 1982) has been studied tractable approximation to non-negative low-rank matrix factorization problem (Ding et al., 2005; Kim and Park, 2008).
This relation between k-means and NMF motivates work but cannot however be applied directly in our case. In particular, we want to avoid instantiating before approximating it. Furthermore, although are interested in low rank sparsity patterns, our application context does not require H itself to be low rank. We therefore propose a simpler strategy where k-means is applied to find the routing pattern, while the attention matrix itself remains full rank. Morcover, our approach maintains a single set of cluster centroids shared across examples, which allows for fast training and inference. We describe this strategy in the next section.
4.2 ROUTING ATTENTION WITH CLUSTERING
Our strategy follows the motivation delincated in the previous section: we model sparse attention matrices with a low rank sparsity patterns relying on k-means clustering. Our strategy first assigns queries and keys clusters. Then only queries and keys from the same cluster are considered for attention.
Precisely, our model projects keys K and queries Q into routing matrix R Raxd as follows
WR WR
R R= [Q, K]
where WR is fixed random orthonormal d x routing projection matrix. The vectors of R undergo k-means clustering in order factorize the full attention matrix. The clustering parameters are the centroid vectors (Ji, 14s) E R These parameters are model parameters shared across sequences. There are learned online along with the rest of the parameters, delineated in Bottou and Bengio (1995), Once cluster membership for each position in the sequence is determined, we denote with C, the cluster corresponding to the routing vector R, This allows to define our sparse attention strategy as
X
Σ A JEC.JSS
(10)
where C, denotes the cluster of the vector R. In summary, queries are routed to keys belonging to the same cluster. Therefore, our attention sparsity pattern is of rank k. i.c. FGT where F and G are binary matrices denoting cluster memberships of queries and keys respectively. Note that since we route both queries and keys via the routing matrix R, it follows that F G. is important to note that this low rank property only concerns the sparsity pattern, while the resulting attention matrix Itr (FT A) Itr A) can however be of higher rank (+ denotes element-wise product).
As last technical point, we work with keys and values which are unitary vectors, projecting them onto the unit ball immediately before computing them. This differentiable normalization (Ba et al.,
5

---

Under review as a conference paper at ICLR 2020
2016) is useful to link cluster memberships with proximity of queries and keys, outlined below. We also assume that the max norm of Wo and WK are close to each other for more details see Appendix A. This can be enforced by adding auxiliary loss by explicitly setting We = WK Since Wn is a distance preserving transform, we can write
|| R - R2l 2 = [[n(Q + K2) - Wn(Qj + K2)1?
(11)
こ |Will (10): - K2,l+ +1Q, - K:1l²)
(12)
= 4 - 2 (0. K3 + Q3 K:).
(13)
Thus, it follows that || R,ll S Q Q K; 2 2 2 This means that, [R, R
1 E = Q, K3 2 1 - //4 Therefore, when two time steps > j are assigned the same cluster due to small ||, - R distance, it also means that their attention weight Q, K3 high. This analysis shows that our clustering routing strategy preserves large attention weights as non-zero entries.
Since, we route attention via the matrix R we dub our model Routing Transformer. The computational complexity of this variant of sparse attention is O(nkd + n²d//)) Cluster assignments correspond to the first term, i.c. it compares n routing vectors to all & centroids in a space of size d. Query/key dot products corresponds to the second term, i.c. assuming balanced clusters, each of the n queries is compared to n/k k in its cluster through a dot product of dimension d. Therefore the optimal choice of l is /n as in Child et al. (2019), thereby reducing overall memory and computational cost to O (n 1.5 instead of O(n2d) d) (Vaswani et al., 2017).
In practice, apply regular online h-means to train the cluster centroids. However, in order to infer balanced routing patterns, we define the sets Cj to be of equal size roughly n/kk ~~ vn, i.e. for every centroid l4 we sort tokens by distance 14; and cluster membership is determined by this threshold (top-k). This strategy is simple and efficient. In particular, it guarantees that all clusters have the same size, which is extremely interesting terms of computational efficiency on parallel hardware like graphic cards. As downside, this assignment does not guarantee that each point belongs to a single cluster. In the future, we want to investigate using balanced variants of h-means (Malinen and Fränti, 2014) which is not common in an online setting.
5 EXPERIMENTS
We evaluate our sparse attention model on various generative modeling tasks including text and image generation. The following sections report our results on e (Mahoney, 201 I), as well as ImageNet - 64. We find that local attention is a surprisingly strong baseline and that our Routing Transformer outperforms Transformer-Xi (Dai et al., 2019) and the Sparse Transformer model of (Child et al., 2019) on all tasks. In all our models, we allocate half the heads to do local attention and the other half to route attention as in Equation 10. We use the Adam optimizer (Kingma and Ba, 2014) with learning rate 2 x 10-4 with 31 = 0.9 and 82 0.98 following the learning rate schedule described in Vaswani et al. (2017).
(Merity et al., 2016),
5.1 WIKITEXT-103
Wikitext-10 103 (Merity et al., 2016) is a large public benchmark data-set for testing long term dependencies in word-level language models. It contains over 100 million tokens from 28K articles extracted from Wikipedia with average of 3.6K tokens per article, which makes it reference data-set to model long-term textual dependencies. We train a 10 layer Routing Transformer with 16 heads using the relative position encoding of Shaw al. (2018) and with attention and ReLU dropout rate of 0.3 each. For routing attention as in Section 4.2 we choose k = 16 and attention window to be 256 during both training and evaluation. We describe our results in Table and compare it to other recent work on sparse or recurrent attention such as Adaptive Inputs (Baevski and Auli, 2018) and TransformerXL (Dai et al., 2019) as well as local attention with relative position encoding baseline (Huang et al., 2018). We find that local attention is great inductive bias for sparse attention and is better than the adaptive methods proposed in Baevski and Auli (2018); Sukhbaatar et al. (2019). Moreover, our Routing Transformer model is able to get a test perplexity of 15.8 improving on the 18.3 obtained by TransformerXL (Dai et al., 2019) while having fewer self-attention layers, and without the need for segment level recurrence.

---

Under review as a conference paper at ICLR 2020
5.2 E
The enwik-8 (Mahoney, 2011) I) is a data-set to benchmark text compression algorithms in the context of the Hutter prize. This data-set consists of the first 100M bytes of unprocessed Wikipedia. is typically used to evaluate character-level language models. Similar to the prior work of Dai et al. (2019); Child et al. (2019) we use sequence length n 8192 and benchmark our results against various baselines including local attention. We train a 24 layer model with 8 attention heads with an attention and ReLU dropout rate of 0.4 each and using the relative position encoding of Shaw et al. (2018). For routing attention as in Section 4.2 we set l = 32 and attention window 256. We report perplexity of 0.99 like TransformerXL and Sparse Transformer, slightly under 0.98 from Adaptive Transformer. We show how samples of our model differs from Transformer with local attention in Appendix C.
5.3 IMAGENET 64 64
In order to evaluate the ability of our model to capture long term dependencies modality other than text, we report results on the ImageNet 64 x 64 data-set as used in Child et al. (2019). For auto-regressive image generation, this data-set consists of images of 64 64 3 bytes represented as long sequences of length 12, 288 presented in raster scan, red-green-blue order. We train 24 layer model with 16 attention heads, with half the heads performing local attention, and the other half routing attention in Section 3. For routing attention we set h = 8, attention window 2048, batch size and train our model for roughly 70 epochs as in (Child al., 2019). We compare our model to a scaled-up TrangeTrannfrmmer model with local attention (Parmar et al., 2018) and the Sparse Transfrraaffommer model of Child et al. (2019).
We find that local attention (Parmar et al., 2018) is strong baseline for image generation, obtaining 3.48 bits/dim when scaled up to 24 layers and 16 heads, compared to later work like Sub-scale Pixel Networks (SPN) (Menick and Kalchbrenner, 2018). Our Routing Transformer model achieves a performance of 3.425 bits/dim (see Table 1) compared to the previous state-of-the-an of 3.437 bits/dim (Child al., 2019), thereby showing the advantage of the content based sparsity formulation of Section 4.2.
Model
Layers
Heads
Bits/dim
Glow (Kingma and Dhariwal, 2018)
3,81
PixeICNN (Van den Oord et al., 2016)
3.57
PixelSNAIL (Chen et al., 2017)
3.52
SPN (Menick and Kalchbrenner, 2018)
3.52
Image'Transfone Transforrnrr (Parmar al., 2018)
24
16
3.48
Sparse Transformer (Child et al., 2019)
48
16
3,44
Routing Transformer
24
16
3.43
Table Results on image generation on ImageNet 64 x 64 in bits/dim.
Model
Layers
Heads
Perplexity
LSTMs (Grave al., 2016)
40.8
QRNNs (Merity et al., 2018)
33.0
Adaptive Transformer (Sukhbaatar et al., 2019)
36
20.6
Local Transformer
16
16
19.8
Adaptive Input (Baevski and Auli, 2018)
16
18.7
TransformerXI. (Dai et al., 2019)
18
16
18.3
Routing Transformer
10
16
15.8
Table 2: Results on language modeling on Wikitext - 103 data-set. Local Transformer refers to Transformer (Vaswani et al., 2017) with relative position encoding (Shaw al., 2018) together with local attention. Perplexity is reported on the test set.

---

Under review as a conference paper at ICLR 2020
Model
Layers
Heads
Bits per byte
T64 (Al-Rfou et al., 2019)
64
1.13
Local Transformer
24
8
1.10
TransformerXL. (Dai et al., 2019)
24
0.99
Sparse Transformer (Child et al., 2019)
30
8
0.99
Adaptive Transformer (Sukhbaatar et al., 2019)
24
8
0.98
Routing Transformer
12
8
0.99
Table 3: Results on language modeling on enwik-8 data-set. Local Transformer refers to Trans- former (Vaswani et al., 2017) with relative position encoding (Shaw et al., 2018) together with local attention. Bits per byte (bpe) is reported on the test set.
ANALYSIS
We evaluate the difference in attention patterns between local and routed attention and compute the Jensen-Shannon divergence between local attention and routed attention for random subset of heads in network on the Wikitext tetteeettlee -00xxt-1333 data-set. The divergence is computed over the entire sequence length of 4096. We average over runs and all the self-attention layers, and report means and standard deviations of the JSD in Table 4. For mean JSD per layer, see Appendix B. Note that the JSD is always non-negative and is upper-bounded by 0.6931 when computed using the natural logarithm. We observe that the divergence between the different local heads is always very low compared to the divergence between local and routing attention heads, which almost always very close the upper-bound of 0.6931. Divergence between different routing attention heads falls somewhere in between, being closer to the bound. This shows that the attention distribution inferred by the routing attention Section 4.2 highly non-local in nature and different heads specialize in attending to very different parts of the input.
(Ioolaall)loca)
|
JSD(local(rrouting
JSD(roudinglrouting
0. 0.1776 + 0.0649 0.6044 + 0.0181
0.4181 + 0.0415
Table Jensen- Saasen-Shannon divergence between the attention distributions of a random local attention head and random head that routes attention as in Section 3 averaged across all layers on the Wikitext- -103 data-set. We report means and standard deviations computed over runs.
7 CONCLUSION
Transformer models constitutes the state-of-the-art in auto-regressive generative models for sequential data. Their space-time complexity is however quadratic in sequence length, due to their attention modules. Our work proposes a sparse attention model, the Routing Transformer. It relies on content- based sparse attention motivated by non-negative matrix factorization. Compared with local attention models, it does not require fixed attention patterns but enjoys similar space-time complexity. In contrast with prior work on content-based sparse attention, does not require computing a full attention matrix but still selects sparsity patterns based on content similarity.
Our experiments over and image generation draw two main conclusions. First, we show that carefully tuned local attention model establishes strong baseline modern benchmark, even compared to recent state-of-the-art models. Second, we show that the Routing Transformer redefines the state-of-the-art in large long sequence benchmarks of Wikitext- - and ImageNet 64, while being very close to do so on enwik- 8 as well. Our analysis also shows that routed attention modules offer complementary attention patterns when compared local attention.
Overall, our work contributes an efficient attention mechanism that applies to the modeling long sequences and redefines the state of the art for auto-regressive generative modeling. Our approach could prove useful in domains where the inputs are already sparse, such as 3D point clouds, social networks protein interactions.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Rami Al-Rfou, Dokook Choc, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3159-3166, 2019. 8
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXivv1607.064500 2016. URL http: www.a.xivv org/ has//ab///ae /1677. 06450. 4,5
Alexei Baevski and Michael Auli. Adaptive input representations for neural language modeling. arXiv preprint arXiv:1809.1055 2018.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. CoRR, abs/1409.0473, 2014. URL http:://ta//ii..t/////// org/ abs/
1409. 0473.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXivv/308..343: 2013. 3
Mathieu Blondel, André Martins, and Vlad Niculae. Learning classifiers with fenchel-young losses: Generalized entropies, margins, and algorithms. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pages 606-615, 2019. URL http::/proceeeeeee html. 2
mlr paress/88l wwweess/v///bornee httpb/looneeee11
Leon Bottou and Yoshua Bengio. Convergence properties of the k-means algorithms. In Advances in neural information processing systems, pages 585-592, 1995. 5
Xi Chen, Nikhil Mishra, Mostafa Rohaninejad, and Pieter Abbeel. Pixelsnail: An improved autore- gressive generative model. arXiv preprint arXiv: 2017.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: 10509, 2019. 1, 6,
Chung-Cheng Chiu and Colin Raffel.
Monotonic chunkwise attention.
arXiv preprint
arXiv:1712.00338, 2017. 2
Kyunghyun Cho and Yoshua Bengio. Exponentially increasing the sapacitytoo-compuattin ratio for conditional computation in deep learning. arXiv preprint arXiv: 7362, 2014.
Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. CoRR, abs/1406.1078, 2014. URL http: aawpaaxxivvv...../.aaa orw. 1406 1078.
Jan K Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, Kyunghyun Cho, and Yoshua Bengio. Attention-based models for speech recognition. In Advances in neural information processing systems. pages 577-585, 2015. 1,2
Gonçalo M. Correia, Vlad Niculae, and André F, T. Martins. Adaptively sparse transformers, 2019. 3,5
Zihang Dai, Zhilin Yang, Yiming Yang, William W Cohen, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. arXiv preprint arXiv:1901 022660, 2019. 2, 3, 4, 6,
Ludovic Denoyer and Patrick Gallinari. arXiv:1410.0510. 2014.
Deep sequential neural network. arXiv preprint
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1800021810.04805. 201 8.
Chris Ding, Xiaofeng He, and Horst D Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the 2005 SIAM International Conference on Data Mining, pages 606-610. SIAM, 2005. 2.5

---

Under review as a conference paper at ICLR 2020
David Eigen, Mare' Aurelio Ranzato, and llya Sutskever. Learning factored representations in deep mixture of experts. arXiv preprint 13124:131 2013. 3
Rainer Gemulla, Erik Nijkamp, Peter J. Haas, and Yannis Sismanis. Large-scale matrix factorization with distributed stochastic gradient descent. In SIGKDD International Conference on Knowledge
Discovery and Data Mining, KDD '11, 2.11. 5
Edouard Grave, Armand Joulin, and Nicolas Usunier. Improving neural language models with continuous cache. arXiv preprint arXiv:1612.04423 2016.
Karol Gregor, Ivo Danihelka, Alex Graves, Danilo Jimenez Rezende, and Daan Wierstra. Draw: A recurrent neural network for image generation. arXiv preprint arXiv: 102.0:/502.04633, 2015.
Patrik O Hoyer. Non-negative matrix factorization with sparseness constraints. Journal of machine learning research, 5(Nov): 2004.
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Ian Simon, Curtis Hawthorne, Noam Shazeer, Andrew M Dai, Matthew Hoffman, Monica Dinculescu, and Douglas Eck. Music transformer: Generating music with long- term structure. 2018. 1, 1,3,
Sathish Reddy Indurthi, Insoo Chung, and Sangha Kim. Look harder: A neural machine transla- tion model with hard attention. In Proceedingy of the 57th Conference of the Association for Computational Linguistics, pages 3037-3043, 2019.
Navdeep Jaitly, David Sussillo, Quoe V Le, Oriol Vinyals, Ilya Sutskever, and Samy Bengio. A neural transducer. arXiv preprint
2015. 2
Jingu Kim and Haesun Park. Sparse nonnegative matrix factorization for clustering. Technical report, Georgia Institute Technology, 2008. 2,5
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, ftbs/1412.69900 2014. URL http: /ttp///aaxvvvv//v///ee/eeeea.wvs hwt.///rgggab/aslaaeee 6980.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1xl convolutions. In Advances in Neural Information Processing Systems, pages 10215-10224, 2018. 7
Daniel D Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. In Advances in neural information processing systems, pages 556-562, 2001. 5,
Peter Liu, Mohammad Saleh, Etienne Pot, Ben Goodrich, Ryan Sepassi, Lukasz Kaiser, and Noam Shazeer. Generating wikipedia by summarizing long sequences. arXiv preprint arXiv:1801.10198 2018. 2
Xiaodong Liu, Pengeheng He, Weizhu Chen, and Jianfeng Gao. Multi-task deep neural networks for natural language understanding. arXiv preprint arXiv:1901.11504 2019.
Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2): 129-137, 1982.
Minh-Thang Luong, Hieu Pham, and Christopher Manning. Effective approaches to attention- neural machine translation. arXiv preprint arXiv: 150.00050 2015. 2,
Matt Mahoney. Large text compression benchmark. URL: http///ww. mattmahoney: net/text/text.
html, 2011. 6, 7
Chaitanya Malaviya, Pedro Ferreira, and André F. T. Martins. Sparse and constrained attention for neural machine translation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 370-376, Melbourne, Australia, July 2018. Association for Computational Linguistics. doi: 10.18653/v//18.. 2059. URL https: // //www. acl web. org/ aatthoooogg wow /P1 80118-20599 2059.
Mikko I Malinen and Pasi Fränti. Balanced k-means for clustering. In Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pages 32-41. Springer, 2014.
10

---

Under review as a conference paper at ICLR 2020
André F. T. Martins and Julia Kreutzer. Learning what's easy: Fully differentiable neural easy-first taggers. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Pro- cessing, pages 349-362, Copenhagen, Denmark, September 2017. Association for Computational Linguistics. doi: 10. 1/118163/11/ URL https: : /ww. ac web. org/ anthology: D17-1036.
Jacob Menick and Nal Kalchbrenner. Generating high fidelity images with subscale pixel networks and multidimensional upscaling. arXiv preprint arXiv:1812.01600 2018. 7,
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv: (et.:.:600.78444 2016.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. An analysis neural language modeling at multiple scales. arXiv preprint arXiv: 082240, 2018.
Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. arXiv preprint arXiv:1802.05751, 2018. 1,4,4,
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. URI. https://s3-us-west22 amazonaws. comfopenai- understanding paper. pdf, 2018. 1,
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self Self-attention with relative position representations.
arXiv preprint arXiv: 1803.02 2018. 6,
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely- gated mixture-of-exee -x-eret layer. arXiv preprint arXiv:1701.065..0 2017. 3
Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive attention span transformers. arXiv preprint (905.00900007799 2019. 2, 6,
R. Tandon and S. Sra. Sparse nonnegative matrix approximation: new formulations and algorithms. Technical Report 193, Max Planck Institute for Biological Cybernetics, Tübingen, Germany, September 2010.
Aaron Van den Oord, Nal Kalchbrenner, Lasse Espeholt, Oriol Vinyals, Alex Graves, et al. Conditional image generation with pixelcnn decoders. In Advances neural information processing systems, pages 4790-4798, 2016. 7
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. CoRR, 2017. URL http:
//aaxii..rrg//ee aas//bbs///// /106 03762. 1, 6, 7,
Kelvin Xu, Jimmy Lei Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhutdinov, Richard S. Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In ICML, 2015.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoc Le. Xlnet: Generalized autoregressive pretraining for language understanding. arXiv preprint 18872777.6.082377, 2019. 1

---

Under review as a conference paper at ICLR 2020
A MATRIX NORM ANALYSIS
In order to formally derive Equation 11, we assume that the linear projection matrices Wq and W K used infer the queries and keys respectively are close to each other max norm. More precisely, we assume the existence of 5 2 0 such that l|We Wxll S 8. This assumption implies that for any vector Rd it holds that:
WWo S uWK + 51 ||
(14)
where the inequality is entry-wise and 1 is the vector in E with all I's. In this case we first show that for any pair j the queries and keys satisfy the following:
(Q. K,) - K2) = (X: x,W (x - x,Wx)
(15)
- |x + (X, (X) (x1 ||,
(X, - X,)Wx)
(16)
I 62 | max { x0 |1xillo0 2 -I((;- - xx
(17)
Therefore, for small enough 6, get that (Q; (0- (Q) K2) E 0 and Equation 11 follows:
RR R& [[WR(Q (Q: + K;) - WR (R(Qj + Kj)l1
(18)
||Wall (10) - K2 2 + |1Q, -K,ll - - K2)
Ki))
(19)
|| (10) - K,l1² |1Q, -K,11)
(20)
Note that a special case of this assumption is when Wi WK, i.e. queries and keys are shared, in which case 8 O.
B JENSEN-SHANNON DIVERGENCE OF ATTENTION DISTRIBUTIONS
In Table 4 we presented the Jensen-Shannon divergence between random local heads and ran- dom routing attention heads averaged across the 10 layers of the Routing Transformer model on wikitext-103. Table 5 presents the mean and standard deviations of the JSD per layer instead of averaging them.
JSD(local|local)
JSD(loco/|/routing)
[SD(rautingg|
layer 0
0.0038 + 0.0018
0.4706 + 0.0319
0.1579 0.0576
layer 1
0.3071 + 0.1217
0.6674 + 0.0153
0.5820 0.0104
layer 2
0.2164 + 0.0803
0.5896 = 0.0249
0.4015 0.0121
layer 3
0.1163 + 0.0336
0.6047 0.0181
0.4144 = 0.0264
layer
0.1840 + 0.0562
0.6266 = 0.0062
0.4191 0.0879
layer 5
0.2284 + 0.0225
0.6463 0.0155
0.4687 0.0449
layer
0.1901 + 0.0525
0.6471 = 0.0040
0.5175 0.0469
layer 7
0.1566 + 0.0685
0.5798 + 0.0235
0.4350 0.0139
layer 8
0.1638 + 0.0739
0.5993 = 0.0148
0.4268 0.0291
layer
0.2095 + 0.0560
0.6127 = 0.0053
0.3581 0.0019
Table 5: Sensen-Shannor divergence between the attention distributions of a random local attention head and random head that routes attention in Section 3 per layer the Wi k text-100 data- set. We report means and standard deviations computed over 10 runs and use the natural logarithm so that divergences are upper-bounded by 0.6931.
C SAMPLES
We generate samples from the Routing Transformer model for the task of character level language modeling on the enwik-8 data-set. We compare the generation to that from a Local Transformer model with the same number of self-attention layers and attention heads. For both the models
12

---

Under review as a conference paper at ICLR 2020
generate unconditional samples using random sampling with temperature of 1.0. The generation from the Routing Transformer is in Table while the generation from Local Transformer in Table 7, with spelling mistakes highlighted in red. Comparing the two samples see that the Local Transformer makes significantly more spelling mistakes, especially for long words and phrases.
13

---

Under review as a conference paper at ICLR 2020
Modern Least Rule hon air and dogmatic television articles several systems: expanding the world usually. The story differs, that would its part flex poctry will support the very little able to put the name by oppose the stories and motoreycle transecurity and biggest life, see the guardian article and looks extraction of large story in storage by meanching up biggest among other items. During that time, Nevis had biggest the Very left record the party's 's tissues. The London meining.biggest guardians of the West; in the 1980s and 1980s. The composer Albert Director boards the capture to the beginning.
The Son Revised publicity and Revisionism board was way of to enough a descendant the President solely changed from [[Eddie Ie. but in fact that assembly was to become common.
The President has poor party detonation the decisions; Telling guards [[Pope University of New York]], student [[Advisor]]
especially [[Canes CombustionlCaness], and thus bhhankruptcylhankuupphh include the latter that the swash of its populatiis churches,
not in steel [[Libertarianism peaceful anti-inss andi-instancelsave the matter's pieces]]. and has been languaged efforts taken in 58,000 sections of anthropic perimeter. The great
precision exists in 2004, with an assistant to feature vault on other great Peaceful themes in America, the nose of highly [lartificial rate|Jes, the discussions of cause,
simply soon because they order to setting out the institution political party activity. As of 2004, anthropology saves them as chiefs derivation from the princess of the Executability can be run all down by deriving the executability understand the scientific additional British family traitirity. These intermediate are unproperly equipped, more unprofitability the officiely competite
mass best science fiction between the notion of a brought Executive school. This project proves the materiel of controversy and high-school intervention and thoughts of as specurety.
[[Danceholding]]. one can specure even the mission to bind its dusting intervention.
At its original time, he current in the cost of moral intervention, in an 2006 slight, tracement saw for the passagecomic belief between the city and applying its uncurrent binary placement, one applies to specure the [[biography (itpappahhiggghy I] of regions, his conserved reference election in the letter the most part of the [[Dominicus]]. [[Algebraizing theory/A|gebrrie]] [[critic]]s, which operate the [[third typelthird]] uncut to the [[militity]] of the country, her brother's
deduction may not be denying cases of militity. In the period, [[Bninity Memory]] plus how [[Jewish Thiloogy/Philloopphe part of [[p-cyclic memoryll, Il. which have been ruleful out for military conventions and have unknown orders, of their proposition (because of the political magnitude circumference of other classness and [[forgery]]). This highly proposing not with member of
with a series of voruments of cach other can be defined
[[ohn Hope (fiction)John Hope]]: Their chief acceptance, or that rapidly proposes C-them by bluetooth sentiments another time. The sentence of the
[[North American Executive DepartmentIDED]] was did not believe the pocket currently by critic, and the reaction by 2004 roughly 400
people and King John Hope was used by the capabalance of other executive organizers in the circumstance of the chief
post-John chief of the 3000 pects. Independences improved [[North American sattram__wwer__tuuiinng the Education]] For throughout
in _thee educationinorth the end of [[1990]]. After prizes of those of the John Hope, Generic Attempts from London rivers Genero helped to prevent any anti-coume anti-country packaging in London. Long term helped by all the Jury before the Council of Zoroastries develop for packet (since [[1990]]] which conspires. any preventing them, which offered the Native American forces to meet them up them to be referred to unto [[first Friendlsouthwest the first VO]].
The symbol was based on the canon of [[St. Francisco]] that bring through this force, some position of north the Graduate Agency (which constituted third) or the other medium in the Friend. Military as it is clear for all the first development of one [[aar-port]], which examined by fraud through the [[Saujuk Earth, IllinoisSSaujuk Earth]] for jewning the [[French Ten Moment]] (2006 to 2006). At the Movement, Aar-port wanted, the city became the [[19th century]] [[[linoos]] of Vice Presidential Aar-ranked Voyage. In the mid left. it includes a river of the Movement through [[Nise]]. Craft dissipatable from the promiser:
Kumat Thurberson; includes [[Modern India]], North, and the [[Illinois Orchestra]]. when three more stronger citics neighbor than Illinois in the country. Literally, Spanish [[July 2005]] helps the city then character spiritually ultimately northern Hinduism of [|German legislature/German]] and [[German legislature German)) "[[Sir John Watching the Public]]", which proves him into the port and the Public's successes.
Table 6: Example unconditional character level text generation from the Routing Transformer model trained on enwik-8 8 with random sampling.
14

---

Under review as a conference paper at ICLR 2020
0 ]oter sonries as refrien ritu] serm host teen serm hostul ritu'; baron, in one ritu': Refriendamonium rite host teen confricndamonium in the ritu's role of ritual resolution. The ritual monitor was baron mentalists for hostilities on the rational series; this river was dubion until the confriendamonitor emerged with this concept into intermedies in witnessing. They introduced the series of not confriendamonium (very relief). They continued to increase the time/ India's ' power down. The ritual production to batted conway choosing by the products of the whole choosing as happens as [[alignment]], and an aircraft happened to the kind. As it returned to the operation of the whole producting the large small scale axis. They were reproduced as logts (intwiting they also affected this drip to the easily life) and our shall materials and provided relative shallow to the motorum. Batted chirality as to the operations of the ANCUP system material to comment adults was bad, as an invasive shallow to be pressure that the program, the subject of ANCUP has been celebrated, since the easily long casily more commonly functions should casily be proved to prevent and group divisions. Batted chirality from the relative community that the controversies came under the writing community led to the legal revolt From the time and from program that they had become explicitly especially in the following year. In [[1984]], and depictions of the government by a subject were used, proved by manticians, confering from their structure [[Mid From Los Angelesl Angeles]]. disputes control and implementing the programming of Hannibal least proposionals of the [[dependency of Philharmos and Winds would make control of the protest actress from much of their sources, making any process thates of [[contention]] of channing the column to inland any time where neardy Rube. Philharmos gives protest to any great b(axis). Namely one of his reigns characterization of unofficial competitive structural did attempt to win some results, myrmonisms, which have been successfully greatly monthly. But Anamos meant that his reasons to his harmonists analog was cold and officials success, quickly denominate a Japanese continued to bring the army various times some full terms of the suffix of obficial réligious religions were surcessful older in Coloniaas and was set. One London, last names, comprising him to succedulate to him deeper. Over the remarkable Submission was, Submission might mussel upon his loyal rebuilding dynasty, program and young by Coloniaas (erasmol), the troops law, with their humans. Less, Miss missions and Cathar with their significance, the troops led by the massive society of the Holy Roman Holy Mission document in the Coloniaan Committee, hence is headby which the course of Summoniacs. "Black Writers", recognizing him the body, Suspense), within the next member of the troops. ref name=Cathar Lesson de Les Rise is derived from the 1990s. Suspense that she missed the course of the erasmolents, part of the character in the member of the 1990s Character acted in some of his coar, the 4 hill belonging the eight members of the member of the 1990s. It was threatened in 1997, and let directly affluencing in saltiming exponents within the study emerge in the 1990s and [[canon]]s working in 1992, and roadly fought in other sections to saltimine races. But failed to thought in the significant shot [[Leibniz]]. (Fulham banned 1990 to 1999, when primitively [[eldest]]).
his dcadly 299 primitive style of Aghai 2001". Symmonists were silicated by the [[Jocy Forces]] and Net. Making the eldest years, he published a finite similar racing, revealed by him a straight just greatly killed beyond a latest-sale public bridge that two great first soundtracking, which "Bolumeck Coal"". "[[Mononymile]] beginning, Dom., the head of the same racing of him of the eldest day Japanese amount in the storm of the sense of Caw celebrated on Monthly appearing instead of cross- cross-music. When overslanding"' (which during his visual) is raised in both the placement and which different from the storm, recent elements, Bolumeck Winters Sense Miller which runs up raising ameth.;Caj is analogy.
Table 7: Example unconditional character level text generation from the Local Transformer model trained on k-8 with random sampling.
15


Reviews:
[{"review_id": "rklzdDukcB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a novel way to increase efficiency for self-attention based sequence modeling neural networks. The proposed approach is incremental by combining content-based sparse attention with local/temporal sparse attention.\n\nWhile the extension is incremental, they are able to reduce the overall complexity and achieve new state-of-the-art on wiki-text 103 dataset.\n\nThe paper is also very well written and easy to follow and understand.\n\nOne negative of the paper is section 4.1. I find the discussions around NMF to be somewhat orthogonal, especially considering the paper does not use NMF techniques for their clustering algorithm in section 4.2.\nWould sparse coding in general be a good high level motivation for the proposed clustering?\n\nIt is also appreciated that the authors have released demo code for reproducibility.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1gjcoEa_B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[EDIT: After reading the other reviews and discussion among reviewers, I have decided to downgrade my score. In particular, in addition to points raised by reviewer 2 there are concerns with regard to lack of ablation studies, and major clarity issues.]\n\nThis paper proposes content-based sparse attention to reduce the time/memory complexity of attention layers in Transformer networks. The method essentially boils down to keep a set of K mean vectors (which are learned/updated during training), which are used to provide clusters to be attended over. When combined with prior work on local attention (i.e. half of the heads are local attention, the other half are the newly proposed routing attention), but model is found to outperform, or be on par with, existing Transformer models despite generally being smaller.\n\nOverall the empirical performance is quite impressive, especially on the highly-competitive Wiktext-103 dataset. The fact\nHowever I had some detailed comments/questions:\n\n- In equation 3, isn't A_{ij} still the output from the full (lower triangular) attention? Or do you change the softmax normalization such that it is over C_i?\n\n- Some natural ablation studies are missing. How does the model do if it only uses routing attention? What about only local attention? Finally, what about full attention with O(n^2)? I understand some of the listed baselines are already working with local attention, but there are differences in setup that could contribute to differing performance. Therefore it would be good to ablate on these aspects, holding the other parts (layers/initialization/optimization algorithm etc.) constant.\n\n- What is the *actual* running time/memory for local/routing/full attention layers? My guess is that the actual, rather than theoretical, difference would not be that great. It seems like the routing layer requires additional operations (i.e. online k-means) which could increase running time. Also, sorting by distance to mu_i doesn't seem very GPU-friendly.\n\n- I found the connection to NMF somewhat tenuous, especially given the different objective (i.e. A is not fully instantiated). I feel that it would be more informative to have some of the ablation studies mentioned above instead.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xBV-VpuB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes a new mechanism for computing the attention scores efficiently in Transformers to avoid the quadratic computational cost in conventional Transformers (i.e., when computing the QK^T for self-attention). With a content-based \"routing\" technique (\"group/cluster attention\" may be a more accurate term to differentiate with the dynamics of Capsule Networks), the time steps of each layer form different clusters, and the self-attention mechanism is only performed within each such cluster. The authors verify their approach on very large-scale and challenging sequence benchmarks such as WikiText-103 (WT103) and enwik-8.\n\nPros:\n+ The math notations are generally clear (e.g., dimensionality) and the paper is well-organized.\n+ The paper addresses a very important (efficiency) question in Transformers, and gave a proper review to prior related works (such as Child et al.).\n+ The experiments used to evaluate the model are all large-scale, high-dimensional and challenging tasks. The routing Transformer seems to be able to do very well on the WikiText-103 word-level language modeling task.\n+ I especially like the analysis of the local vs. routing attention via the JSD score. It's a very interesting and useful way to compare the attention maps without visualizations (which many other works use). \n\n--------------------------------\n\nCons/Questions:\n\n1. Please number your formulas and equations. \n\n2. Based on your definition of X' (at the end of page 3, $X_i' = \\sum_{j < i}^n A_{ij} V_j$) and the subsequent Eq. (2), it seems that you did not add layer normalization and residual connection to the self-attention block. However, almost all prior works that use the Transformer architecture, such as Vaswani et al. [1], Child et al. [2] and Dai et al. [3] has two residual blocks: 1) X' = layernorm(SelfAttention(X) + X); and 2) X'' = layernorm(mlp(X') + X'). Is there any reason that you abandoned this design and used Eq. (2)? Could that have impacted the model performance? In addition, it seems you didn't scale QK^T by 1/\\sqrt{d}, as did in prior works?\n\n3. How are the k-means centroid vectors (\\mu_1, ..., \\mu_k) initialized? Picking the initial centers for k-means clustering has been long known as an interesting/challenging problem, especially in a high-dimensional space (which tasks like language modeling deal with). This challenge spawned works such as K-means++ [4]. I suggest the authors discussing their initialization scheme as well as the initialization's impact on the effectiveness of their approach.\n\n4. In Section 4.2, you said \"$FG^\\top$ where $F$ and $G$ are binary matrices denoting cluster memberships of queries and keys respectively\". However, your previous description seems to suggest that the clusters are formed based on the R matrix (with shape n x d), which contains both Q and K. Does this mean F = G^T? Or could position i in query and position i in key be in different clusters? (I think $ltr(FG^\\top * A)$ would only make sense if F=G^T.) This part is confusing in the paper; please clarify.\n\n5. The inequality at the bottom of page 5 (**feel free to clarify if I missed some assumptions from the paper**): given that $\\|a-b\\|^2 = (a-b)^\\top(a-b) = a^\\top a + b^\\top b - 2a^\\top b$, it's unclear in this case ($a = Q_i-K_j$ and $b = Q_j-K_i$) whether $2a^\\top b$ is positive or negative (even if $Q_i, K_i$ are unit vectors). Therefore, I'm not sure why it is a >= relation here.\nIf this is incorrect indeed, then the subsequent analysis the authors made on \\epsilon would be a bit problematic, too. (Additionally, the authors seem to suggest that $Q_i^\\top K_j = Q_j^\\top K_i$ in the subsequent analysis, which should not be the case, unless W_Q = W_K.) Also, just curious, how did you regularize $W_R$ to be orthonormal while training?\n\n6. The authors acknowledge at the end of Section 4 that their method of assigning clusters \"does not guarantee that each point belongs to a single cluster\". This means that even with balanced cluster sizes, each cluster will have more than n/k routing vectors (i.e., time steps). This makes the $O(nkd + n^2d/k)$ bound the authors mentioned potentially inaccurate. On the other hand, without forcing such cluster balance, in the worst case, the complexity is still O(n^2d), correct?\n\n7. The paper proposes to use $\\sqrt{n}$ clustering centers, which makes sense from the perspective of minimizing total computations. However, since the cluster centroids are learned parameters, does this mean the trained routing Transformer cannot easily generalize to different sequence lengths easily? (e.g., train on sequence length 256 but test on sequence length 2000, or simply 15?) Moreover, on longer sequences, won't the sorting/clustering be increasingly inefficient?\n\n8. What is the motivation of using half of the heads for local attention and the other half for routing attention (cf. the intro paragraph of Section 5)? Why not just use all of the heads with routing attention? Without ablations on this, it's hard to tell which part is contributing how much exactly.\n\n9. Could you also show the # of parameters used by your model in Table 1-3 (as did in prior works)?\n\n10. Do you observe better performance with deeper layers (which seems to be the case for the sparse Transformer [2])?\n\n11. Except the computational concern, I still don't quite exactly see the motivation behind clustering attention. For language modeling, for instance, the time steps should be mutually dependent, and it's more like a connected, chain-like structure (where each word depends strongly on its neighbors). However, the cluster attention seems to group the words together, and there is no cross-cluster attention (i.e., the graph is broken into smaller components). In addition, the authors said the centroid parameters (\\mu_1, ..., \\mu_k) are shared across sequences. So in a certain sense, are they like the \"anchors\" in the (transformed) word embedding space? Are we then, in language modeling tasks, performing attentions among words only around these \"anchors\"?\n\n12. While the theoretical complexity may be lower, how does the wall-clock time of an L-layer routing Transformer compare to an L-layer conventional Transformer (on the same sequence length, batch size)? In particular, although the routing mechanism avoids computing A, having to deal with each of the $\\sqrt{n}$ clusters means that one will need to process the cluster-based attentions sequentially (and, as mentioned, you have 8 heads for local attention and 8 for routing attention, which I think are also processed in two steps?). Would this make the model actually slower on GPUs?\n\n=====================\n\nMinor issues that didn't impact the score:\n\n13. In the equation at the bottom of page 3 (the definition of X_i'), shouldn't it be (j <= i) instead of (j < i), in the case of autoregressive sequence modeling? E.g., in language modeling, you do use the current word when predicting the next word.\n\n14. At the end of Section 5.1, you said: \"while having fewer [...] attention heads\". I believe the released Transformer-XL model also used 16 heads? (https://github.com/kimiyoung/transformer-xl/blob/master/pytorch/run_wt103_large.sh) \n\n15. How does the number of cluster centers influence the performance of the model? I think this would be an interesting ablation study to make.\n\n=====================\n\nWhile I'm impressed with the result the routing Transformer achieved on WikiText-103, I am not fully convinced the effectiveness of the approach (e.g., on the other tasks, the routing Transformer seems to be slightly worse than the SOTA transformer; this is less surprising, as the authors didn't change the underlying design of the Transformers). I think the paper can be improved by including more elements, such as ablative experiments and runtime benchmarking. Also, there seem to be some problems with the derivations that the authors made in the current version of the paper. \n\n\n[1] https://arxiv.org/abs/1706.03762\n[2] https://arxiv.org/abs/1904.10509\n[3] https://arxiv.org/abs/1901.02860\n[4] http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new model, the Routing Transformer, which endows self-attention with a sparse routing module based on online k-means while reducing the overall complexity of attention from O(n^2) to O(n^1.5). The model attained very good performance on WikiText-103 (in terms of perplexity) and similar performance to baselines (published numbers) in two other tasks.

Even though the problem addressed (reducing the quadratic complexity of self-attention) is extremely relevant and the proposed approach is very intuitive and interesting, the reviewers raised some concerns, notably: 
- How efficient is the proposed approach in practice. Even though the theoretical complexity is reduced, more modules were introduced (e.g., forced clustering, mix of local heads and clustering heads, sorting, etc.)
- Why is W_R fixed random? Since W_R is orthogonal, it's just a random (generalized) "rotation" (performed on the word embedding space). Does this really provide sensible "routing"?
- The experimental section can be improved to better understand the impact of the proposed method. Adding ablations, as suggested by the reviewers, would be an important part of this work.
- Not clear why the work needs to be motivated through NMF, since the proposed method uses k-means.

Unfortunately several points raised by the reviewers (except R2) were not addressed in the author rebuttal, and therefore it is not clear if some of the raised issues are fixable in camera ready time, which prevents me from recommend this paper to be accepted.

However, I *do* think the proposed approach is very interesting and has great potential, once these points are clarified. The gains obtained in WikiText-103 are promising. Therefore, I strongly encourage the authors to resubmit this paper taking into account the suggestions made by the reviewers. 
Decision: Reject