Year: 2019

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(nd) from O(nd) 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.

heading: 1 INTRODUCTION
text: 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 on attention to drastically improve the state-of-the 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 et 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 in a 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 the representation of the current time-step as a weighted sum of the past input elements (Vaswani et al., 2017). Self-attention (Shaw et al., 2018) is a particular case of attention (Bahdanau et al., 2014; Chorowski et al., 2015; Luong et 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 a local neighborhood of context around the current time step.
This advantage however comes at a price: unlike recurrent networks or convolution networks, the time and space complexity of self-attention is quadratic in n, the length of the sequence. Specifically, for every position i ≤ n, self-attention computes weights for its whole context of length i, which induces a complexity of ∑ i≤n 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.
Therefore, an 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 et 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 to representations summarizing a 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 a full dense attention matrix prior to sparsification through variants of L0-sparsity or sparsemax approximations (Blondel et al., 2019).
The present work builds upon these two lines of research and proposes to retain the modeling flexibility 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 a 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 is relevant to the sparsification of non-negative matrices like attention matrices.
Our proposed model, Routing Transformer, combines our efficient clustered-based sparse attention with classical local attention to reach excellent performance both for language and image generation. 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 enwik-8) and unconditional image generation (ImageNet-64). Routing Transformer sets new state-of-the-art while having comparable or fewer number of self-attention layers and heads, both on Wikitext-103 (15.8 vs 18.3 perplexity) and on ImageNet-64 (3.43 vs 3.44 bits/dim). We also report competitive results on enwik-8 (0.99 vs 0.98 perplexity).

heading: 2 RELATED WORK
text: 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 sized-chunks.
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 a 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) that alternates coarse layers (attending to the whole sequence at a lower temporal resolution) with local layers (attending to a 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 a strategy using a 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 to get state-of-the-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 it is possible to obtain further sparsity by letting the model learn the length of the temporal context
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 to 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 et 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/entmax formulations require instantiating the full attention matrix prior to sparsification. This is a 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 representations/activations 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 straight-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, a related work is the sparsely gated Mixture-of-experts (MOE) (Shazeer et al., 2017) where sparsity is induced by experts and a trainable gating network controls the routing strategy to each sub-network.

heading: 3 SELF-ATTENTIVE AUTO-REGRESSIVE SEQUENCE MODELING
text: Auto-regressive sequence models decompose the probability of a sequence x = (x1, . . . , xn) as
p(x) = n∏ i=1 pθ(xi+1|x≤i). (1)
In neural models, the conditional distribution pθ(xi+1|x≤i) is modeled by a neural network with learned parameters θ 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-art 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., 2018). Transformer models compose a series of attention modules. Each module refines the input representation by taking a weighted average of the representations from the previous modules.
For every module, the input representation is a sequence of n vectors x = (x1, . . . , xn) from a continuous space of dimension d. Thus one may actually treat the input sequence as a n× d matrix X . A self-attention layer operates on this representation. It first applies three linear projections,
Q = XWQ, K = XWK , V = XWV , (2) where Q,K and V are referred to as keys, queries and values, while WQ,WK ,WV are learned projection matrices.
The key and the query matrices determine the n× 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 a matrix of weights in [0, 1] where Aij 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 ( ltr(QK> ) ) (3)
where ltr denotes the lower triangular operator. Given the attention matrix A, the next layer representation X ′ is computed simply as AV . In summary,
X ′i = n∑ j≤i AijVj , (4)
In practice, Transformer (Vaswani et al., 2017) adds several extensions to this basic self-attention mechanism. In particular, the result X ′ of performing self-attention is scaled by 1/ √ d. 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 a learnable non-linear transformation (multi-layer perceptron, mlp) followed by a residual connection and a normalization step, i.e.
X ′ = layernorm(X ′ +X) (5)
X ′′ = layernorm(mlp(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 (learnable representation for symbols and their positions) and followed by a logistic classification module (learnable linear classifier to predict the next symbol).
Our work is interested in the application of the Transformer to long sequences, a 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.

heading: 4 EFFICIENT CONTENT-DEPENDENT SPARSE ATTENTION
text: Attention-based 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× 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 Si as the set of key positions that the query at position i can attend to, i.e.
X ′i = ∑ j∈Si AijVj . (7)
For example, classical causal self attention can attend to every key prior to the current query, which translates to Si = {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, Si = {j | i− k ≤ j < i}. Child et al. (2019) propose block sparse attention where half the heads perform local attention, and half the heads perform strided attention given by Si = {j | i − j (mod k) = 0, j < i}. Sukhbaatar et al. (2019) is also a variant of local attention where the cardinality of |Si| is learned from data with an L1 penalty to trade-off sparsity with modeling accuracy. 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., a scaled up ImageTransformer (Parmar et al., 2018) gets 3.48 bits/dim compared to the 3.44 bits/dim reported in (Child et 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 Wikitext-103 and 1.10 bits per byte on enwik-8, while the state-of-the-art results using Transformer-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 in memory and known in advance.
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 = f(x). 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 we need to avoid instantiating full attention matrices at any point in time.
For instance, Correia et al. (2019) infer sparsity from data but their formulation instantiates a full attention matrix before finding its sparse counterpart. Next section explains how a natively sparse approach can actually be devised inspired by non-negative matrix factorization (NMF).

heading: 4.1 CLUSTER ATTENTION WITH NON-NEGATIVE LOW RANK APPROXIMATIONS
text: For any given n× n matrix A, a low-rank non-negative approximation to it is of the form H = FG> where F,G ∈ Rn×k and F,G ≥ 0. This factorization can be interpreted as follows: n 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 G. Therefore, the whole attention matrix passes through a bottleneck of size k.
NMF studies algorithms to find such approximations (Tandon and Sra, 2010), for instance minimizing the Frobenius norm,
H = arg min G>G=I,F,G≥0 ∥∥A− FG>∥∥2 . (8) Different algorithms have been proposed for that problem, with different trade-offs in terms of theoretical guarantees, actual accuracy and efficiency (Lee and Seung, 2001; Hoyer, 2004; Gemulla et al., 2011). In particular, k-means clustering (Lloyd, 1982) has been studied as a 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 our work but cannot however be applied directly in our case. In particular, we want to avoid instantiating A before approximating it. Furthermore, although we 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. Moreover, 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.

heading: 4.2 ROUTING ATTENTION WITH CLUSTERING
text: Our strategy follows the motivation we delineated 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 to clusters. Then only queries and keys from the same cluster are considered for attention.
Precisely, our model projects keys K and queries Q into a routing matrix R ∈ Rn×d as follows
R = [Q,K] [ WR WR ] (9)
where WR is a fixed random orthonormal d× d routing projection matrix. The vectors of R undergo k-means clustering in order to factorize the full attention matrix. The clustering parameters are the centroid vectors (µ1, · · · , µk) ∈ Rk×d. These parameters are model parameters shared across sequences. There are learned online along with the rest of the parameters, as delineated in Bottou and Bengio (1995). Once cluster membership for each position i in the sequence is determined, we denote with Ci the cluster corresponding to the routing vector Ri. This allows us to define our sparse attention strategy as
X ′i = ∑
j∈Ci,j≤i
AijVj (10)
where Ci denotes the cluster of the vector Ri. In summary, queries are routed to keys belonging to the same cluster. Therefore, our attention sparsity pattern is of rank k, i.e. FG> 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. It is important to note that this low rank property only concerns the sparsity pattern, while the resulting attention matrix ltr(FG> ∗A) = ltr(FF> ∗A) can however be of higher rank (∗ denotes element-wise product). As a 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.,
2016) is useful to link cluster memberships with proximity of queries and keys, as outlined below. We also assume that the max norm of WQ and WK are close to each other - for more details see Appendix A. This can be enforced by adding an auxiliary loss or by explicitly setting WQ =WK . Since WR is a distance preserving transform, we can write
‖Ri −Rj‖2 = ‖WR(Qi +Ki)−WR(Qj +Kj)‖2 (11) ' ‖WR‖2 ( ‖Qi −Kj‖2 + ‖Qj −Ki‖2 ) (12)
= 4− 2 ( Q>i Kj +Q > j Ki ) . (13)
Thus, it follows that ‖Ri −Rj‖ ≤ ε⇒ Q>i Kj+Q>j Ki ≥ 2−ε2/2. This means that, ‖Ri −Rj‖ ≤ ε⇒ Q>i Kj ≥ 1− ε2/4. Therefore, when two time steps i > j are assigned the same cluster due to a small ‖Ri −Rj‖ distance, it also means that their attention weight Q>i Kj is high. This analysis shows that our clustering routing strategy preserves large attention weights as non-zero entries.
Since, we route attention via the matrixR we dub our model Routing Transformer. The computational complexity of this variant of sparse attention is O(nkd+ n2d/k). Cluster assignments correspond to the first term, i.e. it compares n routing vectors to all k centroids in a space of size d. Query/key dot products corresponds to the second term, i.e. assuming balanced clusters, each of the n queries is compared to n/k in its cluster through a dot product of dimension d. Therefore the optimal choice of k is √ n as in Child et al. (2019), thereby reducing overall memory and computational cost to
O ( n1.5d ) instead of O(n2d) (Vaswani et al., 2017).
In practice, we apply regular online k-means to train the cluster centroids. However, in order to infer balanced routing patterns, we define the sets Ci to be of equal size roughly n/k ∼ √ n, i.e. for every centroid µi we sort tokens by distance to µi 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 in terms of computational efficiency on parallel hardware like graphic cards. As a 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 k-means (Malinen and Fränti, 2014) which is not common in an online setting.

heading: 5 EXPERIMENTS
text: We evaluate our sparse attention model on various generative modeling tasks including text and image generation. The following sections report our results on Wikitext-103 (Merity et al., 2016), enwik-8 (Mahoney, 2011), as well as ImageNet-64. We find that local attention is a surprisingly strong baseline and that our Routing Transformer outperforms Transformer-XL (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× 10−4 with β1 = 0.9 and β2 = 0.98 following the learning rate schedule described in Vaswani et al. (2017).

heading: 5.1 WIKITEXT-103
text: Wikitext-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 an average of 3.6K tokens per article, which makes it a 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 et 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 2 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 a local attention with relative position encoding baseline (Huang et al., 2018). We find that local attention is a 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.

heading: 5.2 ENWIK-8
text: The enwik-8 (Mahoney, 2011) 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. It 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 a 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 k = 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.

heading: 5.3 IMAGENET 64× 64
text: In order to evaluate the ability of our model to capture long term dependencies on a modality other than text, we report results on the ImageNet 64 × 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 a 24 layer model with 16 attention heads, with half the heads performing local attention, and the other half routing attention as in Section 3. For routing attention we set k = 8, attention window 2048, batch size 1 and train our model for roughly 70 epochs as in (Child et al., 2019). We compare our model to a scaled-up ImageTransformer model with local attention (Parmar et al., 2018) and the SparseTransformer model of Child et al. (2019).
We find that local attention (Parmar et al., 2018) is a 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-art of 3.437 bits/dim (Child et al., 2019), thereby showing the advantage of the content based sparsity formulation of Section 4.2.

heading: 6 ANALYSIS
text: 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 a random subset of heads in our network on the Wikitext-103 data-set. The divergence is computed over the entire sequence length of 4096. We average over 10 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 is almost always very close to the upper-bound of 0.6931. Divergence between different routing attention heads falls somewhere in between, being closer to the upper-bound. This shows that the attention distribution inferred by the routing attention of Section 4.2 is highly non-local in nature and different heads specialize in attending to very different parts of the input.

heading: 7 CONCLUSION
text: 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 contentbased 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, it does not require computing a full attention matrix but still selects sparsity patterns based on content similarity.
Our experiments over text and image generation draw two main conclusions. First, we show that a carefully tuned local attention model establishes a strong baseline on 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-103 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 to local attention.
Overall, our work contributes an efficient attention mechanism that applies to the modeling of 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 or protein interactions.

heading: A MATRIX NORM ANALYSIS
text: In order to formally derive Equation 11, we assume that the linear projection matrices WQ and WK used to infer the queries and keys respectively are close to each other in max norm. More precisely, we assume the existence of a δ ≥ 0 such that ‖WQ −WK‖∞ ≤ δ. This assumption implies that for any vector u ∈ Rd it holds that:
uWQ ≤ uWK + δ1 ‖u‖∞ , (14)
where the inequality is entry-wise and 1 is the vector in Rd with all 1’s. In this case we first show that for any pair i, j the queries and keys satisfy the following:
(Qi −Kj)>(Qj −Ki) = (XiWQ −XjWK)>(XjWQ −XiWK) (15) ≤ (δ1 ‖Xi‖∞ + (Xi −Xj)WK) >(δ1 ‖Xj‖∞ − (Xi −Xj)WK) (16)
≤ δ2 ‖1‖2 max { ‖Xi‖∞ , ‖Xj‖∞ }2 − ‖(Xi −Xj)WK‖2 (17) Therefore, for small enough δ, we get that (Qi −Qj)>(Qj −Ki) / 0 and so Equation 11 follows:
‖Ri −Rj‖2 = ‖WR(Qi +Ki)−WR(Qj +Kj)‖2 (18) = ‖WR‖2 ( ‖Qi −Kj‖2 + ‖Qj −Ki‖2 − 2(Qi −Kj)>(Qj −Ki) ) (19)
' ‖WR‖2 ( ‖Qi −Kj‖2 + ‖Qj −Ki‖2 ) . (20)
Note that a special case of this assumption is when WQ =WK , i.e. queries and keys are shared, in which case δ = 0.

heading: B JENSEN-SHANNON DIVERGENCE OF ATTENTION DISTRIBUTIONS
text: In Table 4 we presented the Jensen-Shannon divergence between random local heads and random 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.

heading: C SAMPLES
text: 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 we
generate unconditional samples using random sampling with a temperature of 1.0. The generation from the Routing Transformer is in Table 6 while the generation from Local Transformer is in Table 7, with spelling mistakes highlighted in red. Comparing the two samples we see that the Local Transformer makes significantly more spelling mistakes, especially for long words and phrases.

Review summaries:
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.