Long-Short Transformer: Efficient Transformers for Language and Vision
Authors: Chen Zhu
Wei Ping
Chaowei Xiao
Mohammad Shoeybi
Tom Goldstein
Anima Anandkumar
Bryan Catanzaro
Venue: NeurIPS 2021 Poster (2021)
Keywords: Efficient Transformer
Long-sequence Modeling
Language Models
Vision Transformer

Abstract: Transformers have achieved success in both language and vision domains. However, it is prohibitively expensive to scale them to long sequences such as long documents or high-resolution images, because self-attention mechanism has quadratic time and memory complexities with respect to the input sequence length. In this paper, we propose Long-Short Transformer (Transformer-LS), an efficient self-attention mechanism for modeling long sequences with linear complexity for both language and vision tasks. It aggregates a novel long-range attention with dynamic projection to model distant correlations and a short-term attention to capture fine-grained local correlations. We propose a dual normalization strategy to account for the scale mismatch between the two attention mechanisms. Transformer-LS can be applied to both autoregressive and bidirectional models without additional complexity. Our method outperforms the state-of-the-art models on multiple tasks in language and vision domains, including the Long Range Arena benchmark, autoregressive language modeling, and ImageNet classification. For instance, Transformer-LS achieves 0.97 test BPC on enwik8 using half the number of parameters than previous method, while being faster and is able to handle 3x as long sequences compared to its full-attention version on the same hardware. On ImageNet, it can obtain the state-of-the-art results (e.g., a moderate size of 55.8M model solely trained on 224x224 ImageNet-1K can obtain Top-1 accuracy 84.1%), while being more scalable on high-resolution images. The source code and models are released at https://github.com/NVIDIA/transformer-ls.

Long-Short Transformer: Efficient Transformers for Language and Vision
Chen Zhu Wei Ping Chaowei X2a Mohammad Shoeybi?, Tom Goldstein', Anima Anandkumar and Bryan Catanzaro"
University of Maryland, College Park
NVIDIA Arizona State University 'California Institute of Technology ((wping, chaoweix @nvidia.com
Abstract
Transformers have achieved success in both language and vision domains. However, it is prohibitively expensive to scale them to long sequences such as long documents high-resolution images, because self-attention mechanism has quadratic time and memory complexities with respect to the input sequence length. In this paper, we propose Long-Short Transformer (Transformer-L.S) an efficient self-attention mechanism for modeling long sequences with linear complexity for both language and vision tasks. aggregates a novel long-range attention with dynamic projection to model distant correlations and short-term attention to capture fine-grained local correlations. We propose a dual normalization strategy to account for the scale mismatch between the two attention mechanisms. Transformer-LS can be applied to both autoregressive and bidirectional models without additional complexity. Our method outperforms the state-of-the-ant models multiple tasks in language and vision domains, including the Long Range Arena benchmark, autoregressive language modeling, and ImageNet classification. For instance, Transformer-L.S achieves 0.97 test BPC on enwik8 using half the number of parameters than previous method, while being faster and is able handle 3 long sequences compared to its full-attention version on the same hardware. On ImageNet, it can obtain the state-of-the-art results (e.g., a moderate size of 55.8M model solely trained on 224 x 224 ImageNet-Il 1 can obtain Top-1 accuracy 84. 1)), while being more scalable on high-resolution images. The source code and models are released at https: htt//ggtttbbt///t/////e/ett com/ COo/N//III/////
Introduction
Transformer-basee models [1] have achieved great success in the domains of natural language processing (NLP) [2, 3] and computer vision [4-6]. These models benefit from the self-attention module, which can capture both adjacent and long-range correlations between tokens while efficiently scaling on modern hardware. However, the time and memory consumed by self-attention scale quadratically with the input length, making it very expensive process long sequences. Many language and vision tasks benefit from modeling long sequences. In NLP, document-level tasks require processing long articles [c.g.. 7, 8], and the performance of language models often increases with sequence length [e.g., 9, 10]. In computer vision, many tasks involve high-resolution images, which are converted to long sequences of image patches before being processed with Transformer models [4, 6, 11]. As result, it is crucial to design an efficient attention mechanism for long sequence modeling that generalizes well across different domains.
Work done during internship at NVIDIA.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Various methods have been proposed to reduce the quadratic cost of full attention. However, an efficient attention mechanism that generalizes well in both language and vision domains is less explored. One family of methods is to sparsify the attention matrix with predefined patterns such as sliding windows [e.g., 12-15] and random sparse patterns [16]. These methods leverage strong inductive biases to improve both computational and model performance, but they limit the capacity of a self-attention layer because each specific token can only attend to a subset of tokens. Another family of methods leverages low-rank projections to form a low resolution representation of the input sequence, but the successful application of these methods has been limited to certain NLP tasks [e.g.. 17-19]. Unlike sparse attention, this family of methods allows each token to attend to the entire input sequence. However, due to the loss of high-fider fideliiilitty token-wise information, their performance sometimes is not good as full attention or sparse attention tasks that require fine- fine-grained local information, including standard benchmarks in language [20] and vision [21].
Despite the rapid progress in efficient Transformers, some proposed architectures can only be applied to bidirectional models [e.g.. 15, 16, 18). Transformer-bant autoregressive models have achieved great successes in language modeling [22], image synthesis [23], and text-to-image synthesis [24], which also involve long texts or high-resolution images. It is desirable to design an efficient trans- former that can be applied to both autoregressive and bidirectional models.
In this work. we unify a local window attention and novel long-range attention into single efficient attention mechanism. We show that these two kinds of attention have complementary effects that together yield the state-of-the-ar results on a range of tasks in language and vision, for both autoregressive and bidirectional models. Specifically, we make the following contributions:
We propose Long-Short Transformer (Transformer-LS), an efficient Transformer that integrates a dynamic projection based attention model long-range correlations, and a local window attention to capture fine-grained correlations. Transformer-LS can be applied to both autoregressive and bidirectional models with linear time and memory complexity.
We compute a dynamic low-rank projection, which depends on the content of the input sequence. In contrast previous low-rank projection methods, our dynamic projection method more flexible and robust to semantic-preserving positional variations (e.g., insertion, paraphrasing). We demonstrate that it outperforms previous low-rank methods [17. 18] on Long Range Arena benchmark [20].
We identify a scale mismatch problem between the embeddings from the long-range and short- term attentions, and design a simple but effective dual normalization strategy, termed DualLN, to account for the mismatch and enhance the effectiveness of the aggregation.
We demonstrate that Long-Short Transformer, despite its low memory and runtime complexity, outperforms the state-of-the-art models on set of tasks from Long Range Arena, and autore- gressive language modeling on enwik8 and text8. In addition, the proposed efficient attention mechanism can be easily applied the most recent vision transformer architectures [6, 11] and provides state-of-the-ar results, while being more scalable to high-resolution images. We also investigate the robustness properties of the Transformer-LS on diverse ImageNet datasets.
2 Related Work
2.1 Efficient Transformers
In recent years, many methods have been introduced for dealing with the quadratic cost of full atten-
tion. In general, they can be categorized follows: i) Sparse attention mechanism with predefined patterns (c.g., sliding window), including Sparse Transformer [12], Image Transformer [13]. Axial
Transformer [25] for modeling images, and Longformer [14], blockwise self-attention [26]. ETC [15], Big Bird [16] for modeling language. ii) Low-rank projection attention, including Linformer [17]. Nyströmformer [18], Synthesizer [19]. For example, Linformer uses linear layers to project the original high resolution keys (K) and values (V) with length n to low resolution with size (r < n) and allows all query tokens (Q) to attend these compressed representations. iii) Memory-based mechanisms like Compressive Transformer [10] and Set Transformer [27], which use extra mem- ories for caching global long-range information for use computing attention between distant tokens. iv) Kemel-based approximation of the attention matrix, including Performer [28], Linear

---

Projectin
Proeetd key (saba)
frrm
Shor-torm Attention
Long ferm Altentoo
Aggregation
Figure 1: Long-short term attention of a single attention head. Here, the sequence length = 8, hidden dimension d d= 3, local window segment size 2, and rank of dynamic projection = 3. Within the figure, ((V) denotes key K or value V. In the left figure, we virtually replicate K or I into n rows, and highlight the keys and values within the attention span (denoted as (V)) of all queries Q for the short-term attention. In the middle figure, all queries attend the attention. In the right figure, K( (V) and (VV are first normalized with two sets of LayerNorms, and the queries attend to normalized (VV and (V) within their attention span simultaneously.
projected keys K and values V within the long-term
Transformer [29], and Random Feature Attention [30]. vi) Similarity and clustering based methods, including Reformer [31], Routing Transformer [32], and Sinkhorn Transformer [33].
Our method seamlessly integrates both low-rank projection and local window attentions, to leverage their strengths for modeling long-range and short-term correlations. In particular, our longrrange attention uses dynamic low-rank projection to encode the input sequence, and outperforms the previous low-rank projection method used by the Linformer [17]. In the similar vein, a few other methods also try to combine the strengths of different methods. For example, Longformer [14] and ETC [15] augment local window attention with task motivated global tokens. Such global tokens may not be applicable for some tasks (e.g., autoregressive modelling). BigBird [16] further combines local window and global token attention with random sparse attention. It is not applicable in autoregressive tasks because the global token and random sparse pattern introduced. To compress the model footprint on edge devices, Lite Transformer [34] combines convolution and self-attention, but it still has quadratic complexity for long sequences.
2.2 Vision Transformers
Vision Transformer (ViT) [4] splits images as small patches and treats the patches as the input word tokens. uses standard transformer for image classification and has shown outperform convolutional neural networks (e.g., ResNet [35]) with sufficient training data. DeiT [36] has applied the teacher-student strategy to alleviate the data efficiency problem of ViT and has shown strong comparable performance using only the standard ImageNet dataset [37]. Instead of applying transformer at a single low resolution of patches (e.g., 16 16 patches), very recent works, including Pyramid Vision Transformer (PVT) [5]. Trin--rranfoomer [38], VIT [39], Vision Longformer (ViL) [1 I] and Convolutional Vision Transformer (CvT) [6], stack a pyramid of ViTs to form a multi-scale architecture and model long sequences of image patches at much higher resolution (e.g.. 56 x 56 = 3136 patches for images with 224 x 224 pixels). Most of these methods have quadratic complexity of self-attention with respect to the input image size.
To reduce the complexity. tion of self-attention only within each local window. HaloNet [40] applies local attention on blocked images and only has quadratic complexity with respect to the size of the block. Perceiver [41] uses cross-attention between data and latent arrays to replace the self-attention on data to remove the quadratic complexity bottleneck. Vision Longformer (ViL) [11], another concurrent work, achieves linear complexity by adapting Longformer [14] to Vision. Vil. augments local window attention with task-specific global tokens, but the global tokens are not applicable for decoding task (e.g., image synthesis [23, 24]). In contrast, our method reduces the quadratic cost to linear cost by combining local window attention with global dynamic projection attention, which can be applied to both encoding and decoding tasks.
[38] achieves linear complexity by limiting the computa-
3 Long-Short Transformer
Transformer-L.S approximates the full attention by aggregating long-range and short-term attentions, while maintaining its ability to capture correlations between all input tokens. In this section, we first
3

---

introduce the preliminaries of multi-head attention in Transformer. Then, we present the short-term attention via sliding window, and long-range attention via dynamic projection. respectively. After that, we propose the aggregating method and dual normalization (DualI.N) strategy. See Figure I for an illustration of our long-short term attention.
3.1 Preliminaries and Notations
Multi-head attention is core component of the Transformer [1], which computes contextual represen- tations for each token by attending the whole input sequence at different representation subspaces. It is defined as
MultiHead(Q,,ke V) Concat(Hı, ...... Ho)
(1)
where Q. K,V E Raxd are the query, key and value embeddings, W E Raxd x is the projection matrix for output, the i-th head H; E Ruxds is the scaled dot- dot-product attention, and d₃ d/h h is the embedding dimension of each head,
QWw? ( T vdg
H: AQtention(QW, KW.", vWY) softmax
VW = AVVY. (2)
where W.O W.K W.Y E Rdxd are learned projection matrices, and A, E Rxxx denotes the full attention matrix for each attention head. The complexity of computing and storing A; (n?²). which can be prohibitive when n is large. For simplicity, our discussion below is based on the case of ID input sequences. It straightforward to extend the 2D image data given a predetermined order.
3.2 Short-term Attention via Segment-wise Sliding Window
We use the simple yet effective sliding window attention to capture fine-grained local correlations, where each query attends to nearby tokens within fixed-size neighborhood. Similar techniques have also been adopted in [14, 16, 11]. Specifically, we divide the input sequence into disjoint segments with length w for efficiency reason. All tokens within a segment attend to all tokens within its home segment, as well as w/2 consecutive tokens on the left and right side of its home segment (zero-padding when necessary), resulting in an attention span over total of 2w key-value pairs. See Figure in Appendix for an illustration. For each query Q2 at the position within the i-th head, we denote the 2w key-value pairs within its window as K,, V E 2 For implementation with PyTorch, this segment-wise sliding window attention is faster than the per-token sliding window attention where each token attends to itself and w tokens to its left and right, and its memory consumption scales linearly with sequence length; see [14] and our Figure for more details.
The sliding window attention can be augmented capture long-range correlations in part, by introducing different dilations to different heads of sliding window attention [14]. However, the dilation configurations for different heads need further tuning and an efficient implementation of multi-head attention with different dilations is non-trivial. A more efficient alternative is to augment sliding window attention with random sparse attention [16], but this does not guarantee that the long-range correlations are captured in each layer in full attention. In the following section, propose our long-range attention to address this issue.
3.3 Long-range Attention via Dynamic Projections
Previous works have shown that the self-attention matrix can be well approximated by the product of low-rank matrices [17]. By replacing the full attention with the product of low-rank matrices [42, 19, 18, 43, 28), each query is able to attend to all tokens. Linformer [17] is one of the most representative models in this category. It learns fixed projection matrix reduce the length of the keys and values, but the fixed projection is inflexible to cemantic-preservii
positional variations.
Starting from these observations, we parameterize the dynamic low-rank projection at i-th head as P: = ʃ(K) E Raax,, where < n is the low rank size and P; depends on all the keys K RRx d of input sequence. It projects the (n x dy dimeesiins key embeddings KW.K and value embeddings VW: into shorter, (r x dz) ddimensional key K; and value V; embeddings. Unlike Linformer [17]. the low-rank projection matrix dynamic, which depends on the input sequence and is intended be more flexible and robust to, e.g., insertion, deletion, paraphrasing, and other operations that change
sequence length. See Table 2 for examples. Note that, the query embeddings QW?? e gaxde are kept

---

at the same length, and we let each query attend to K2 and V. In this way, the full (n x n) attention matrix can be decomposed into the product of two matrices with r columns or rows. Specifically, we define the dynamic projection matrix P; E TR and the key-value embeddings K2, V2 E Rexde of low-rank attention as
P. roftmax(KW,)). = V, = P.VWW.
(3)
where W E RRxxr are learnable parameters, 2 and the softmax normalizes the projection weights on the first dimension over all n tokens, which stabilizes training in our experiments. Note that K V in all the experiments we have considered, P. remains the same if it depends on V. The computational complexity of Eq. is O(rn).
To see how the full attention is replaced by the product of low-rank matrices, we compute each head H; E Raxdx of long-range attention as,
QW
K
H softmax
V A.(.WWW)
(4)
ddk
A.
so the full attention is now replaced with the implicit product of two low-rank matrices A E Bexr and PT E grx", and the computational complexity is reduced to (rn)). Note the effective attention weights of a query on all tokens still sum to Our global attention allows each query to attend to all token embeddings within the same self-attention layer. In contrast, the sparse attention mechanisms [14, 16] need stack multiple layers to build such correlations.
Application to Autoregressive Models: In autoregressive models, each token can only attend to the previous tokens, so the long-range attention should have a different range for different tokens. A straightforward way to implement our global attention is to update K; V; for each query recurrently, but this requires re-computing the projection Eq. (3) for every token due to the nonlinearity of softmax, which results in O(rn²) computational complexity. To preserve the linear complexity, for autoregressive models, we first divide the input sequence into equal-Length segments with length 4, and apply our dynamic projection to extract K; V; from each segment. Each token can only attend to K,, V; of segments that do not contain its future tokens. Formally, let Qe be the query at position t, ()==t)s Vit-s be the key- dayuvalue pairs from the s-th segment, and s, [t/l]. For autoregressive models, we compute the long-range attention of Q2 by attending to K,,e, V1,, defined as
(5) In this way, the dynamic low-rank projection is applied to each segment only once in parallel, preserving the linear complexity and the high training speed. By comparison, Random Feature Attention [30] slow training due to the requirement for recurrence.
K2, = [PT, Kı.i...; P.,,, K( ((=-esse W Vr, = [PT, Vi.ii...; P.T. V(-I)ecde.
3.4 Aggregating Long-range and Short-term Attentions
To aggregate the local and long-range attentions, instead of adopting different attention mechanisms for different heads [12. 14, 34], we let each query i-th head attend to the union of keys and values from the local window and global low-rank projections, thus it can learn to select important information from either of them. We find this aggregation strategy works better than separating the heads in our initial trials with the autoregressive language models. Specifically, for the i-th head, denote the global low-rank projected keys and values K,, V Rxx, and the local keys and values as K,, Ve E R2 within the local window of position & for the query Q.- Then the i-th attention H at position / is
Quwa
K.W.K; K.
Ha, softmax
(WW. Vi).
Vdg
where [ denotes concatenating the matrices along the first dimension. Furthermore, we find scale mismatch between the initial norms of K2 K.W.K and K, which biases the attention to the local window at initialization for both language and vision tasks. We introduce a normalization strategy (DualLN) to align the norms and improve the effectiveness of the aggregation in the following.
For the CyT-based vision transformer model, we replace w:" with depth- wish separable convolution, just its query, key and value projections.
5

---

Compare Local to Global Vey/V Norm Ratios
Compare Validation Loss
1.25
w/o DualLN (enwik8)
2.5
Validation Loss
1.20
w/ DualLN (enwik8)
Nor Ra
w/o DualLN (text8)
2.0
1.15
w/ DualLN (text8)
DualLN (emwik8) weo DusiLN (texiB) weo DuaILN (ImageNie)
1.10
1.5
DuaLN
1.05
1.0
1
3
4
5
8 Layer Index
7
10 11
12
Ok
100k
200k
300k
400k
Training Iterations
Figure 2: Left: Ratios of the average norms of the local window global low-rank key/value embeddings initialization. Without DualLN, the sparse and low-rank embeddings have a magnitude mismatch. With DualLN, the ratios will be 1.0 at every layer. which will facilitate optimization. Right: The validation loss of Transformer-LS with and without DualLN on enwik8 and text8.
DualLN: For Transformers with Layer Normalization (LN) (see [44] for illustration), the K,, V, embeddings are the outputs of LN layers, so they have zero mean and unit variance at initialization. The & norm of vectors with zero-mean entries is proportional to their variance in expectation. We note a weighted average will reduce the variance and therefore the norm of such zero-mean vectors. As result, the embedding vectors from low-rank attention in the weighted average K2 Vi of Eq. (3) will have smaller norms than the regular key and value embeddings from sliding window attention (see Figure 2 Left for illustration). This scale mismatch causes side effects. First, the inner product Q. RT from local-ran component tends have smaller magnitude than the local window one, thus the attention scores on long-range attention is systematically smaller. Second, the key-value pairs K, V; for the low-rank attention will naturally have less impact on the direction when low-rank and local window are assigned with same attention scores, since Vú has smaller norms. Both effects lead to small gradients on the low-rank components and hinders the model from learning to effectively use the long-range correlations.
H, even
To avoid such issues, we add two of Layer Normalizations after the key and value projections for the local window and global low-rank attentions, so that their scales are aligned at initialization, but the network can still learn re-weight the norms after training. Specifically, the aggregated attention is now computed
Q. (NW. Vdl
Ha softmax
[N (VW,
where (-), L-N(-) denote the Layer Normalizations for the local and global attentions respec- tively. In practice, to maintain the consistency between the local attention and dynamic projection, we use ( (V) instead of K, V compute K, Vi Eq. As illustrated in Figure Right, the Transformer-LS models trained with DualLN has consistently lower validation loss than the models without DualL.N.
Experiments
In this section, we demonstrate the effectiveness and efficiency of our method in both language and vision domains. We use PyTorch for implementation and count the FLOPs using fvcore [45].
4.1 Bidirectional Modeling on Long Range Arena and IMDb
To evaluate Long-Short Transformer as bidirectional encoder for long text, we train our models on the three NLP tasks, ListOps. Text, and Retrieval, from the recently proposed Long Range Arena (LRA) benchmark [20], following the setting of Peng et al. [30] and Tay al. [46]. For fair comparisons, we use the PyTorch implementation and the same data preprocessing/split. training hyperparameters and model size from [18], except for Retrieval where we accidentally used more warmup steps and improved the results for all models. See Appendix B for more details. The results

---

Table 1: Accuracy (%) and FLOPs (G) on Long Range Arena (LRA), with the model configs annotated (see
Table 7 for more). All results averages of 4 runs with different random seeds.
Task
ListOps
Text
Retricval
Avcrage
(mean + std.) of sequence length
(888 1 339)
(1296 + 893)
(3987 1 560)
Model
Acc.
FLOPs
Acc.
FLOPs
Acc.
FLOPs
Acc.
Full Attention [1]
37.13
1.21
65.35
4.57
82.30
9.14
61.59
Reformer [31] (2)
36.44
0.27
64.88
0.58
78.64
1.15
59.99
Linformer [17] (k=256)
37.38
0.41
56.12
0.81
79.37
1.62
57.62
Performer [28] (r 256)
32.78
0.41
65.21
0.82
81.70
1.63
59.90
Nyströmformer [18] 128)
37.34
0.61
65.75
1.02
81.29
2.03
61.46
Transformer-LS (w. r = 8,32)
37.50
0.20
66.01
0.40
81.79
0.80
61.77
Dynamic Projection (best)
37.79
0.15
66.28
0.69
81.86
2.17
61.98
Transformer-LS (best)
38.36
0.16
68.40
0.29
81.95
2.17
62.90
Table 2: Comparing the robustness of the models under test-time insertions and deletions. DP refers to long-range attention via Dynamic Projection, and Win. refers to sliding window attention.
Task
Text
Retrieval Insertion
Test Perturb
None
Insertion
Deletion
None
Deletion
Linformer
56.12
55.94
54.91
79.37
53,66
51.75
DP
66.28
63.16
58.95
81.86
70.01
64.98
Linformer Win.
59.63
56.69
56.29
79.68
52.83
52.13
DP + Win. (ours)
68.40
66.34
62.62
81.95
69.93
64.19
Table 3: Comparing the results of pretrained language models fine-tuned on IMDb.
Model
RoBERTa-base RoBERTa-large Longformer-base LSSbase LS-large
Accuracy
95.3
96.5
95.7
96.0
96.8
on these three tasks are given in Table 1. Results of the other two image-based tasks of LRA, as well models implemented in JAX, given in Appendix C and C.2.
In addition, we follow the pretraining procedure of Longformer [14] to pretrain our models based on RoBERTa-beel basee and RoBERTa-large [47], and fine-tune it on the IMDb sentiment classification dataset. The results are given in Table 3.
Results. From Table 3, our base model outperforms Longformer-base, and our large model achieves improvements over RoBERTa-large demonstrating the benefits of learning to model long sequences. Comparisons with models on LRA are given in Table 1. Transformer-LS (best) with the best configurations of w. r for each task are given in Table in Appendix B. We also report the results of using fixed hyperparameter w = 8, = 32 on all tasks. Overall, our Transformer-LS (best) is significantly better than other efficient Transformers, and the model with w, r 8, 32 performs favorably while using only about 50% to 70% computation compared to other efficient Transformers on all three tasks. The advantage of aggregating local and long-range attentions is the most significant on ListOps, which requires the model to understand the tree structures involving both long-term and short-term relations. On Retrieval, where document-level encoding capability is tested, we find our global attention more effective than window attention. The test accuracy of using only dynamic projection is about 10% higher than Linformer on Text (i.c., 66.28 vs. 12.. which has the highest variance in sequence length (i.e. standard deviation 893). This demonstrates the improved fiexibility of dynamic projection at learning representations for data with high variance sequence length, compared to the learned but fixed projection of Linformer. Similarly, Linformer, Nyströmformer and our model outperform full attention on ListOps, indicating they may have better inductive bias, and efficient Transformers can have better efficacy beyond efficiency.
Robustness of Dynamic Projection. In Table 2, we compare the robustness of Linformer and the proposed Dynamic Projection (DP) against insertion and deletion on Text and Retrieval tasks of LRA. We train the models on the original, clean training sets and only perturb their test sets. For insertion, we insert 10 random punctuations at 10 random locations of each test sample. For deletion, we delete
7

---

Forward Forward-backon backprop Peak GPU M Memory (Autoregressive LM)
Forward-basxxrop Time Iteration (Autoregressive
(G8)
25
20
Timelteraaion (e)
1.6
Batchm2
Batchee
Transformer>Xi
15
Transformen-US
Batche1
1.0
10
Batchn2
Transformr- XL
Trensfomar-LS
0.0
0
2000
4000
0000
8000
10000
12000
14000
0
2000
4000
1:000
8000
10000
12000
14000
Sequence Langth
Sequance Length
Figure 3: Running time and memory consumption Transformer- XL (full attention) and our Transformer- LS on Char-LM. We increase the sequence length until we use up the 32GB of memory on a V100 GPU. Transformer-LS is the same smaller model in Table 4. We use dashed lines to represent the full attention Transformer and solid lines to represent our model. We use different colors represent different batch sizes.
Table BPC (L) smaller models on enwik8 and lext8 (left), and larger models on enwik8 (right).
text8
enwik8
Method
#Param Test BPC
Method
#Param
Dev Test
Dev
Test
Transformer-Xi [9]
88M
1.03
T12 [49]
44M
1.18
1.11
Transformer-Xl. [9]
277M
0.99
Transformer XL [9]
41M
1.06
Routing [32]
223M
0.99
Reformer [31]
1.05
Longformer [14]
102M
0.99
Adaptive [50]
38M
1.05
1.11
1.04
1.02
Sparse [12]
95M
0.99
BP- Tran [51]
38M
1.11
1.02
Adaptive [50]
209M
0.98
Longformer [20]
41M
1.04
1.10
1.02
1.00
Compressive [10]
227M
0.97
Transformer-LS
44M
1.03
1.09
1.01
0.99
Transformer-LS
110M
0.97
all punctuations from the test samples. Both transforms are label-preserving in most cases. By design, dynamic projection is more robust against location changes.
4.2 Autoregressive Language Modeling
We compare our method with other efficient transformers on the character-level language modeling where each input token is a character.
Setup. We train and evaluate our model on enwik8 and text8, each with 100M characters and divided into 90M, 5M, 5M for train, dev, test, following [48]. Our smaller 12-layer and larger 30-layer models are Pre-LN Transformers with the same width and depth as Longformer [20], except that we add relative position encoding to the projected segments in each layer. We adopt the cache mechanism of TrL [9], setting the cache size to be the same as the input sequence length. We follow similar training schedule as Longformer, and train our model in phases with increasing sequence lengths. The input sequence lengths are 2048, 4096 and 8192 respectively for the 3 phases. By comparison, Longformer trains their model in 5 phases on GPUs with 48GB memory (The maximal of ours is 32GB) where the sequence length is 23,040 in the last phase. The window size of Longformer increases with depth and its average window size is 4352 in phase while our effective number of attended tokens is 1280 on average in the last phase. Each experiment takes around 8 days finish on V100 GPUs. Detailed hyperparameters are shown in Appendix D. For testing, same as Longformer, we split the dataset into overlapping sequences of length 32K at step size of 512, and evaluate the BPCs for predicting the next 512 tokens given the previous 32K characters.
Results Table 4 shows comparisons on text8 and enwik8. Our method has achieved state-of-the-a results. On text8. we achieve test BPC of 1.09 with the smaller model. On enwik8, our smaller model achieves test BPC of 0.99, and outperforms the state-of-the-art models with comparable number of parameters. Our larger model obtains Transformer with 2x parameters. Our results are consistently better than Longformer which is trained on longer sequences with stages and 48 GPU memory. In Figure we show our model is much more memory and computational efficient than full attention.
BPC of 0.97, on par with the Compressive
8

---

Table 5: Test accuracies on ImageNet, ImageNet Real [52], and ImageNet V2 [53] of models trained on ImageNet- IK. Grey-colored the non-official CvT implementation. models with LS suffixes are our long-short term attention based on the official ViI. implementation with relative positional bias. also provide the latency of models tested using batch size 32 on the same V100 GPU. Our improvements over ViL is mainly from a better implementation of the short-term attention.
results. CvT' -LS denotes our long-short term attention based
Model
#Param Image FLOPs ImageNet Real (M)
V2
Latency
Size
(G) top-1 (%) top-1 (%) top-1 (%)
(s)
ResNet-50
25 224
4.1
76.2
82.5
63.3
RcsNct-101
45 224
7.9
77.4
83.7
65.7
ResNet-152
60 224
11
78.3
84.1
67.0
DeïT-S [36]
22 224
4,6
79.8
85.7
68.5
DeïT-B [36]
86 224
17.6
81.8
86.7
70.9
PVT-Medium [5]
44 224
6.7
81.2
PVT-Large [5]
224
9.8
81.7
Swin-S [38]
50 224
8.7
83.2
Swin-B [38]
224
15.4
83.5
0.115
PVTv2-B4 [54]
62.6 224
10.1
83.6
PVTv2-B5 [54]
82.0 224
11.8
83.8
ViT-B/16 [4]
86 384
55.5
77.9
ViT-L/16 [4]
307 3842
191.1
76.5
DeïT-B [36]
86 384
55.5
83.1
Swin-B [38]
3842
47.1
0.378
CvT-13 [6]
224
6.7
81.6
70.4
0.122
CvT-21 [6]
32 224
10.1
82.5
87.2
71.3
0.165
CVT1-
20.3
224
81.9
87.0
70.5
0.083
CvT*-LS--17
23.7 224
9.8
82.5
87.2
71.6
CVT'-1S-21
32.1 224
7.9
82.7
87.5
71.9
0.122
-LS--LS-218
30.1 224
11.3
82.9
87.4
71.7
CvT-13 [6]
20 3842
31.9
83.0
87.9
71.9
CvT-21 [6]
32 384
45.0
83.3
87.7
71.9
CvT*-LS-21
32.1 3842
23.9
83.2
88.0
72.5
-VT--
32.1 448
34,2
83.6
88.2
72.9
ViL-Small [14]
24.6 224
4,9
82.4
ViL-Medium [14]
39.7
224
83.5
0.106
ViL--Base [14]
55.7
224
13.4
83.7
0.164
ViL-LS-Medium
39.8
224
8.7
83.8
0.075
ViL-LS-Bart
55.8
224
13.4
84.1
0.113
ViL-LS-Medium
39.9
3842
28.7
84.4
0.271
4.3 ImageNet Classification
We train and evaluate the models on ImageNet- 1K with 1.3M images and 1K classes. We use CvT [6] and ViL [11], state-of-the art vision transformer architectures, the backbones and replace their attention mechanisms with our long-short term attention, denoted CVT*-LS and ViL-size-LS Table 5. CvT uses overlapping convolutions to extract dense patch embeddings from the input images and feature maps, resulting in long sequence length in the early stages (e.g., 56 x 56 3136 patches for images with 224 pixels). For ViL, our sliding window uses the same group size w, but each token attends to at most 2w x 2w (rounding when necessary) tokens inside the window, instead of 3w x 3w as ViL, which allows adding our dynamic projection without increasing the FLOPs. We set 8 for the dynamic projections for both FiL-LS-Medium and ViL-LS-Base. Note that, efficient attention mechanism does not depend on the particular architecture, and it can be applied to other vision transformers [e.g., 4, 36, 5]. Please refer Appendix E for more details.
The results are shown the Table 5, where we also list test accuracies on ImageNet Real and ImageNet V2. Except for CvT, we compare with the original VIT [4] and the enhanced DeiT [36], PVT [5] that also uses multi-scale stragey, Vil. [11] that uses window attention and global tokens to improve the efficiency. Training at high-resolution usually improves the test
Classification Results.

---

Table 6: Robustness evaluation on various ImageNet datasets. Top-1/Acc. Top-1 accuracy. mCE: Mean
Corrupution Error. mixeedsaame/Mixede accuracies
BRAN subsets.
Model
Params| ImageNet IN-C
IN-A [57]
IN-R [58]
ImageNet-9 [59]
(M)
Top-1
mCE (L)
Acc.
Acc.
Mixed-same Mixed-rand
ResNet-50 [35]
25.6
76.2
78.9
6.2
35.3
87.1
81.6
DeiT-S [36]
22.1
79.8
57.1
19.0
41.9
89.1
84.2
CvT-13
20
81.6
59.6
25,4
42,9
90.5
85.7
CvT-21
32
82.5
56.2
31.1
42.6
90.5
85.0
CvI7-LSS-13
20.3
81.9
58.7
27.0
42.6
90.7
85.6
CvT*-18--21
32.1
82.7
55.2
29.3
45.0
91.5
85.8
accuracy of vision transformer. With our long-short term attention, we can easily scale the training to higher resolution, and the performance of CVS and ViL-LS also improves. Our best model with CvT (CvT"-LS-
at 448²) achieves 0.3% higher accuracy than the best reported result of CvT while using the same amount of parameters and 76% of its FLOPs. CvT architecture, the spatial dimension of feature maps in earlier stages large, representing more fineigrained details of the image. Similar to training with high-resolution images, the model should also benefit from denser feature maps. With our efficient long-short term attention, feature maps with less concerns about the computational budget. In this way, our CVS"-L-S-17 achieves better result than CvT-21 at resolution 224 using fewer parameters and FLOPs, and our CVT'-LS-21S model further improves our -LS21 model.
better utilize these fine-grained
Our ViL-LS-Medium and ViL-LS-Base with long-short term attention improve the accuracies of ViL-Medium and ViL-Base from 83.5 and 83.7 to 83.8 and 84.1 respectively, without an increase in LL-LS-MMeiium from 224 to 3842, the FLOPs increased (upproximately) linearly and the accuracy improved by 0.6%, showing our method still benefits greatly from increased resolution while maintaining the linear complexity in practice.
FLOPs. When increasing the resolution for training
Short-term Attention Suppresses Oversmoothing. By restricting tokens from different segments to attend to different windows, our short-term sparse local attention encourages diversity of the feature representations and helps to alleviate the over-smoothing problem [55] (where all queries extract similar information in deeper layers and the attention mechanism is less important), thus can fully utilize the depth of the network. As in [55], we provide the cosine similarity patch embeddings of our -VS--LS-13 13 and re- re-implemented CvT-13 (81.1 accuracy) in Figure 6 within Appendix. This is one of the reasons why our efficient attention mechanism can get even better results than the full attention CvT model in the same setting.
Robustness evaluation on Diverse ImageNet Datasets. As vision models have been widely used in safety-critical applications (e.g. autonomous driving), their robustness is vital. In addition to out-o--distributio robustness (ImageNet-Reall and Imageet-v2), we further investigate the robustness of our vision transformer against common corruption (ImageNet-C), semantic shifts (ImageNet-R), Background dependence (ImageNet-9) and natural adversarial examples (ImageNet-A), We compare our methods with standard classification methods, including CNN-based model (ResNet [35]) and Transformer- based models (DeiT [36]) with similar numbers of parameters. As shown in Table 6, we observe that our method significantly outperforms the CNN-based method (ResNet-50). Compared to DeiT. our models also achieve favorable improvements. These results indicate that the design of different attention mechanisms plays an important role for model robustness, which sheds new light on the design of robust vision transformers. More details and results can be found in Appendix E.
5 Conclusion
In this paper, we introduced Long-Short Transformer, an efficient transformer for long sequence modeling for both language and vision domain, including both bidirectional and autoregressive models. We design novel global attention mechanism with linear computational and memory complexity in sequence length based on a dynamic projection. We identify the scale mismatch issue and propose the DualLN technique to eliminate the mismatch at initialization and more effectively aggregate the local and global attentions. We demonstrate that our method obtains the state-of-ther -fttt--rt results on the Long Range Arena, char-level language modeling and ImageNet classification. We look forward to extending our methods to more domains, including document QA, object detection and semantic segmentation on high-resolution images.
10

---

References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention all you need. In NIPS, volume 30, 2017.
[2] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirec- tional transformers for language understanding. NAACL, 2019.
[3] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl blog. 1(8)9, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesmikov, Dirk Weissenhorn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghami, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
[5] Wenhai Wang, Enze Xic, Xiang Li, Deng- Long-Ping Fan, Kaitao Song. Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pyramid vision transformer: A versatile backbone for dense prediction without convolutions. arXiv preprint arXiv:2102.1 /2/22, 2021.
[6] Haiping Wu, Bin Xiao, Noel Codella, Mengehen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang. Cvt: 2021.
Introducing convolutions to vision transformers. arXiv preprint
[7] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein. Illia Polosukhin. Jacob Devlin, Kenton Lee, et al. Natural questions: benchmark for question answering rescarch. TACI, 7:453-466, 2019.
[8] Raghavendra Pappagari, Piotr Zelasko, Jesús Villalba, Yishay Carmiel, and Najim Dehak. Hierarchi- cal transformers for long document classification. In 2019 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), pages 838 844. IEEE, 2019.
[9] Zihang Dai, Zhilin Yang. Yiming Yang, Jaime Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transfomme-xl: Attentive language models beyond fixed-length context. In ACL, 2019.
[10] Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy P Lillicrap. Compressive Transformers for long-range sequence modelling. In ICLR, 2020.
[11] Pengchuan Zhang, Xiyang Dai, Jianwei Yang, Bin Xiao, Lu Yuan, Lei Zhang, and Jianfeng Gao. Multi- scale vision longformer: A new vision transformer for high-resolution image encoding. arXiv preprint 10X3v:2103.15338, 2021.
[12] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: 10509, 2019.
[13] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In /CML, pages 4055 4064, 2018.
[14] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint 200.::00000005500000 2020.
[15] Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula. Sumit Sanghai. Qifan Wang, and Li Yang. Ete: Encoding long and structured inputs in transformers. In EMNLP, pages 220882842222 2020.
[16] Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big Bird: Transformers for longer sequences. In NewrIPS, 2020.
[17] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang. and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint (tf::20000047665. 2020.
[18] Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung. Yin Li, and Vikas Singh. Nyströmformer: A nyström-based algorithm for approximating self-attention. AAAI, 2021.
[19] Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng, Synthesizer: Rethinking self-attention in transformer models. In /CML, 2021.
[20] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham. Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. Long Range Arena: A benchmark for efficient transformers. In ICLR, 2021.
11

---

[21] Pengchuan Zhang, Xiyang Dai, Jianwei Yang. Bin Xiao. Lu Yuan, Lei Zhang, and Jianfeng Gao. Multi- scale vision longformer: A new vision transformer for high-resolution image encoding. arXiv preprint (rXiv:2103.15355) 2021.
[22] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, al. Language models are few-shot leamnrrs. arXiv preprint arXiv:2005. 14165, 2020.
[23] Ali Razavi, Aaron van den Oord, and Oriol Vinyals. Generating diverse high-fidelity images with vq-vae-2. arXiv preprint arXiv: (eeeii99600044 00446, 2019.
[24] Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford. Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. arXiv preprint arXiv:2102.12092, 2021.
[25] Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidimensional transformers. arXiv preprint arXiv:1912.12180, 2019.
[26] Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang. and Jie Tang. Blockwise self- attention for long document understanding. arXiv preprint arXiv: 191 1.02972, 2019.
[27] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invarian neural networks. In ICML, 2019.
[28] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins. Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. ICLR, 2021.
[29] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers mns: Fast autoregressive transformers with linear attention. In ICML, 2020.
[30] Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. ICLR, 2021.
[31] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In ICLR, 2020.
[32] Aurko Roy. Mohammad Saffar, Ashish Vaswani. and David Grangier. Efficient content- sparse attention with routing transformers. TACL, 9:53-68, 2021.
[33] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da Da-Cheng Juan. Sparse sinkhorn attention. In ICML. PMLR, 2020.
[34] Zhanghao Wu, Zhijian Liu, Ji Lin, Yujun Lin, and Song Han. Lite transformer with long-short range attention. arXiv preprint arXiv:2004.18886 2020.
[35] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016.
[36] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. arXiv preprint arXiv:2012. 12877 2020.
[37] Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: large-scale hierarchical image database. In CVPR, 2009.
[38] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. arXiv preprint 1rXiv:2103.14030 2021.
[39] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zihang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan. Tokens-to-token vit: Training vision transformers from scratch on imagenet. arXiv preprint ar 2 1986, 2021.
[40] Ashish Vaswani, Prajit Ramachandran, Aravind Srinivas. Niki Parmar, Blake Hechtman, and Jonathon Shlens. Scaling local self-attention for parameter efficient visual backbones. arXiv preprint arXiv:2103.12731 2021.
[41] Andrew Jaegle, Felix Gimeno, Andrew Brock, Andrew Zisserman, Oriol Vinyals, and Joao Carreira. Perceiver: General perception with iterative attention. arXiv preprint arXiv:2103.03006 2021.
12

---

[42] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rans: Fast autoregressive transformers with linear attention. In ICML. PMLR. 2020.
[43] Hao Peng. Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. Random feature attention. ICLR, 2021.
[44] Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang. and Ticyan Liu, On layer normalization in the transformer architecture. In ICML. PMLR, 2020.
[45] fvcore: Flop counter for pytorch models. http:://ggtaa..ccc/cc/eeeee/r/rp master master/docs// _ooot_ccuutt....ooccc md, 2021.
[46] Yi Tay, Mostafa Dehghani, Vamsi Aribandi. Jai Gupta, Philip Pham, Zhen Qin, Dara Bahri, Da-Cheng Juan, and Donald Metzler. Omninet: Omnidirectional representations from transformers. ICML, 2021.
[47] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach, arXiv preprint 1691
[48] Matt Mahoney, Large text compression benehmark. URL http:///haaammmhhhoeeeeeeecchtit 6, 2009.
[49] Rami Al-Rfou, Dokook Choe, Noah Constant, Mandy Guo, and Llion Jones. Character-level language modeling with deeper self-attention. In AAAI, volume 33, pages 31,59-1666, 2019.
[50] Sainbayar Sukhbaatar, Edouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive attention span in transformers. ACL, 2019.
[51] Zihao Ye, Qipeng Guo, Quan Gan, Xipeng Qiu, and Zheng Zhang. Bp-transformer: Modelling long-range context via binary partitioning. arXiv preprint (xXiv:991.04007) 2019.
[52] Lucas Beyer, Olivier Hénaff. Alexander Kolesnikov, Xiaohua Zhai, and Aäron van den Oord. Are done with imagenet? arXiv preprint arXiv:2006.07159, 2020.
[53] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference on Machine Learning, pages 5389-5400, PMLR, 2019.
[54] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pvtv2: Improved basclines with pyramid vision transformer. 2021.
[55] Chengyue Gong, Dilin Wang, Meng Li, Vikas Chandra, and Qiang Liu. Improve vision transformers training by suppressing over-smoothing. arXiv preprint arXiv:2104: 12753, 2021.
[56] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In International Conference on Learning Representations, 2019.
[57] Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. arXiv preprint arXiv:190..07174 2019.
[58] Dan Hendryckss Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al. The many faces of robustness: A critical analysis of out-of-distribution generalization. arXiv preprint arXiv:2006. 162..1116..61,, 2020.
[59] Kai Xiao, Logan Engstrom, Andrew Ilyas, and Aleksander Madry. Noise signal: The role of image backgrounds object recognition. ArXiv preprint 09999440060 2020.
[60] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. CVPR, 2015.
[61] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In AISTATS, 2010.
[62] Nikita Nangia and Samuel Bowman. Listops: A diagnostic dataset for latent tree learning. In NAACL: Student Research Workshop, pages 92-99 2018
[63] Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng. and Christopher Potts. Learning word vectors for sentiment analysis. In ACL, 2011.
13

---

[64] Dragomir R Radev, Pradeep Muthukrishnan, Vahed Qazvinian, and Amjad Abu-Jbara. The acl anthology network corpus. Language Resources and Evaluation, 47(4)9919-944, 2013.
[65] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts, arXiv preprint a6Xiv: 03983, 2016.
[66] François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 1251-1258, 2017.
[67] Lei Huang, Xianglong Liu, Yang Liu, Bo I Lang, and Dacheng Tao. Centered weight normalization in accelerating training of deep neural networks. In Proceedings the IEEE International Conference Computer Vision, pages 2803-2811. 2017.
[68] Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Micro-batch training with batch-channel normalization and weight standardization. arXiv preprint arXiv:1903. 10520, 2019.
14


Reviews:
[{"review_id": "twlGUNGVq7M", "reviewer": "Reviewer_K8ya", "summary": "This paper proposed Long-Short Transformer (Transformer-LS), which aggregates sliding window attention (i.e. short-term attention) with linear attention via low-rank projection (i.e. long-term attention), by simply concatenating the two sets of keys.\nDue to the scale mis-match of the keys from the long and short term attentions, the authors further proposed the dual layernorm (DualLN) method.\n\nExperiments were conducted on Long-range Arena (LRA), auto-regressive language modeling and ImageNet classification. Transformer-LS achieves improvements over previous efficient transformer models on both accuracy and efficiency.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is clear and generally well written. \n\nHowever, there are some weaknesses:\n\n1. The proposed architecture of Transformer-LS is not novel. The two key components of Transformer-LS, i.e. the sliding window attention and low-rank projection (or similar architectures), have been introduced in existing works. For example, the sliding window attention has been extensive explored in LongFormer and Big-Bird models (with some slight differences), and the low-rank projection approach is a straight-forward extension of LinFormer. Actually, a recent work (Goyal et al., 2021) proposes a more general low-rank projection approach which captures contextual information in the projection, instead of just using a learnable parameter (like W_i^{P} in E.q 3). Thus, the contribution of this work is to combine the two types efficient attention mechanisms and empirically evaluate it on language and vision tasks.\n\n\n2. The experimental results, especially  those on language tasks, are not entirely convincing.\nFor the experiments on LRA, they did not follow the default setting in the LRA paper, and the efficiency comparison is indirect. It is highly recommended to follow the default setting in the LRA paper to fairly compare the accuracy with previous efficient transformer models, and directly compare the speed and memory efficiency by steps per second and memory usage.\nMoreover, it is highly recommended to conduct more challenging language tasks, including machine translation and pre-trained language models (such as BERT), to demonstrate the effectiveness of Transformer-LS.\n\nReferences:\n\nCoordination Among Neural Modules Through a Shared Global Workspace. Goyal et al., 2021.\n\n================Updates after reading authors' response=============================\n\nThanks for the authors' great effort on the response, which mostly addressed my concerns. Thus, I upgraded my score to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "soF12wP2wSP", "reviewer": "Reviewer_8e8m", "summary": "In this paper, the authors focus on reducing the quadratic computation complexity of the self-attention mechanism in the standard Transformer. They combine local and global context through sliding window attention and matrix projections. During aggregating long-range and short-term attention, they employ two sets of Layer Normalizations to make sure that the model will use both long and short range effectively. Experiments show some promising results on various tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Their model tries to model both the long-range and fine-grained local correlations using two different attentions, both of which have linear computation complexity. Their method is easy to understand but I do think it is not rival to implement this model so it would be great if authors could release their code to the public. Their paper is easy to follow and extensive experiments has shown the effectiveness of their method. I just have a few questions:\n1. For aggregating the local and short-range attention, you concatenate their attention matrix. Will this introduce extra computation, could you just simply add them together, and will this hurt the performance much?\n2. Will you apply your method for the pre-trained language model to further demonstrate the effectiveness and efficiency of your proposed method?\n3. For efficiency, FLOPs are used to compare different models, and could you compare their wall time speed?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": " Although they do not explicitly mention the societal impact, I think their method could help us to build the efficient Transformer. However, I still suggest authors add this section to their draft.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "cfJ-mk7mOpE", "reviewer": "Reviewer_J3tL", "summary": "The paper introduces Long-Short Transformer, an efficient Transformer model that combines local sliding window attention with low rank global attention. This is an attempt in combining the two dominant paradigms of making Transformers more efficient: Sparsifying attention and Low-rank methods. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There are two main ideas presented in the paper: 1- Combining sparse local attention with low-rank methods. 2- Using dynamic low-rank projection with a function that depends on the Keys instead of a fixed learned projection. \nThe general ideas are very interesting and results are encouraging. However, there are few key weaknesses with the paper:\n\nFirst, while I found the first idea to be very interesting, the impact of the second idea is less clear as I couldn't find any ablations comparing the full model with the model that combines the local attention with a fixed low-rank projection methods. I.e., What would happen if we replace the dynamic projection with fixed learned projection (similar to the Linformer paper)? \nSimilarly, the impact of the local sliding window is also not very clear, what would happen if the queries only attended to global projections? The only place such results exists appears to be on the 3 Long Range Arena tasks. Another useful ablation would have been comparing dynamic projection with fixed projection in the setting without the addition of local sliding window attention.\n\nThe second weakness is the general evaluation tasks. I appreciate the experiments on LRA and char language modeling, but there is no evaluation on actual downstream NLP tasks, which makes the effectiveness of the model in real-world applications less clear. Instead of expensive char LM experiments, I would have much preferred experiments on NLP tasks similar to those evaluated by Longformer and Big Bird papers. \n\nI was a bit disappointed to see some of the tasks of LRA excluded from evaluations. The authors mention that this is because the data is small and tasks are synthetic, but in general other LRA tasks are also not realistic and I was a bit confused about this evaluation setup. About the size of data, does this mean that the model will have harder time training in low-resource setting?\n\nOn Robustness results (Table 4), how does a CvT model (without the addition of Long Short Transformer) work? This comparison seems to be missing. \n\nThe paper mentions that dynamic projections are \"more flexible and robust to, e.g., insertion, deletion, paraphrasing, and other operations that change sequence length\" (L164-165). However, I didn't find any empirical evidence or analyses about this. \n\nMinor: A figure about the main idea would have been nice to include. \n\nUpdate: The authors included new experiments addressing most of the above concerns. I'm updating my score. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would have liked to see some discussion on limitations of the work and societal impacts. \nSome that come to mind are potential environmental impacts of training and experimenting with such models at scale (e.g., https://arxiv.org/pdf/1907.10597.pdf). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "YPY-w4-PKiu", "reviewer": "Reviewer_TUYw", "summary": "This paper addresses the quadratic complexity issue in Transformer, and proposes a long-short efficient Transformer model. It aggregates a long-range attention with dynamic projection to model distant correlations and a short-term attention to capture fine-grained local correlations. A dual normalization strategy is used to address the scale mismatch between the two attention mechanisms. The method is applied to both autoregressive and bidirectional models without additional complexity. Experiments on both vision and language benchmarks verify the efficacy of the method.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n* This paper is well-written and easy to follow. I enjoy reading this paper. The summarization of the previous efficient Transformer is good.\n\n* The experiments on both vision and language, as well as both autoregressive and bidirectional models, are interesting and comprehensive.\n\n\nCons:\n\n* Overall, the novelty of this work is not strong, because the efficiency issue has been addressed by several previous works, which are also discussed in the related work. The long-short idea is also discussed before, such as \"Lite Transformer with Long-Short Range Attention\" (although the method is different). It is suggested to add more discussions on key differences.\n\n* The main focus of this paper is the efficiency of Transformer. However, the latency (or model inference time) is not reported and compared. Though the FLOPs reduction is clearly demonstrated, yet FLOPs is still the theoretical metric for efficiency measurement. Models may not run fast even when they have smaller FLOPs. I would like to see the comparisons on latency on GPU, CPU, etc. This is very important for practical applications.\n\n* In Sec. 4.3, your re-implementation of CvT gets worse performance, what's the concrete top-1 accuracy? Btw, CvT recently released their official implementation.\n\n* Why you do not run your method on Swin models? It is suggested to add an experiment. Besides hand-designed models, whether the proposed long-short attention can be used in automated search models, such as HAT (https://arxiv.org/abs/2005.14187), BossNAS (https://arxiv.org/abs/2103.12424) and AutoFormer (https://arxiv.org/abs/2107.00651)?\n\n* The improvements on high-resolution images (from 384x384 to 448x448) seems not competitive. \n\n* In Fig.6 (Appendix), it is a little bit strange why the similarity drops significantly from layer #12 to #13? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "235phN2JGYd", "reviewer": "Reviewer_YUM1", "summary": "This work presents Long-Short Transformer (Transformer-LS), which integrates a dynamic projection based long-range attention and a local window short-term attention to capture both global and local features. Specifically, 1) the long-range attention is implemented by projecting the Key and Value embeddings into shorter ones (in terms of number of tokens) based on the projection matrix generated from the original Key embeddings and 2) the short-term attention is implemented by dividing the input sequences into disjoint segments. A scale mismatch is identified from the long-range and short-term attention and solved by the proposed DualLN. The experiments are conducted in both NLP and CV tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "> + Originality: Are the tasks or methods new? Is the work a novel combination of well-known techniques? (This can be valuable!) Is it clear how this work differs from previous contributions? Is related work adequately cited?\n\nThis work claim 3 contributions: 1) integrating long-range and short-term attention; 2) input-dependent dynamic low-rank projection in long-range attention; 3) DualLN to handle the norm mismatch problem when integrating long-range and short-term attention. Although each of them are not novel enough, such a combination seems to be quite effective in both NLP tasks and CV tasks, which is also valuable.\n\n> + Quality: Is the submission technically sound? Are claims well supported (e.g., by theoretical analysis or experimental results)? Are the methods used appropriate? Is this a complete piece of work or work in progress? Are the authors careful and honest about evaluating both the strengths and weaknesses of their work?\n\n1. A better performance breakdown (ablation studies) on the contritions 1), 2) and 3) mentioned above: Although some ablation studies about the effectiveness of each components are given in Section 3 and 4. It would be better if how each of them contributes to the final performance improvements are given, e.g., how the performance of simply combining the Linformer and the window attention in Big Bird using contrition 1) and 2)? Will the benefit of DualLN (Figure 1) and Dynamic project still exists in CV tasks, which usually have relatively shorter sequences?\n\n2. Some confusing details: What's the f function in Line 162, is it a Linear layer? In Table 3, CvT*-LS-21 seems to have comparable or even better accuracy than CvT*-LS-17 and CvT*-LS-21S with much less FLOPs, any insight or analysis about it?\n\n> + Clarity: Is the submission clearly written? Is it well organized? (If not, please make constructive suggestions for improving its clarity.) Does it adequately inform the reader? (Note that a superbly written paper provides enough information for an expert reader to reproduce its results.)\n\nThis submission is clearly written and well organized.\n\n> + Significance: Are the results important? Are others (researchers or practitioners) likely to use the ideas or build on them? Does the submission address a difficult task in a better way than previous work? Does it advance the state of the art in a demonstrable way? Does it provide unique data, unique conclusions about existing data, or a unique theoretical or experimental approach?\n\nThe results can help the researchers to build more efficient Transformer models w/ the proposed Transformer-LS as the building block.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to advance the efficient transformer by integrating long-range attention and short-term attention. The reviewers identified several risks of this paper. Most of reviewers had concerns about the novelty, as the presented method is a combination of existing techniques. The reviewers also raised questions regarding the architecture choices, evaluation setups for LRA and lack of experiment for downstream NLP tasks. During the rebuttal, as acknowledged by the reviewers, the authors have successfully addressed most of the experimental concerns by adding more results. Despite the fact that the methodology is rather incremental, the empirical results seem quite strong and possibly be impactful to massive CV and NLP downstream tasks. 
Decision: Accept (Poster)