Composite Slice Transformer: An Efficient Transformer with Composition of Multi-Scale Multi-Range Attentions
Authors: Mingu Lee
Saurabh Pitre
Tianyu Jiang
Pierre-David Letourneau
Matthew J Morse
Kanghwan Jang
Joseph Soriaga
Parham Noorzad
Hsin-Pai Cheng
Christopher Lott
Venue: ICLR 2023 poster (2023)
Keywords: transformer
efficient transformer
efficient attention

Abstract: Since the introduction of Transformers, researchers have tackled the notoriously expensive quadratic complexity problem.  While significant computational efficiency improvements have been achieved, they come at the cost of reduced accuracy trade-offs. In this paper, we propose Composite Slice Transformer (CST), a Transformer-based network equipped with a composition of multi-scale multi-range attentions, boosting both efficiency and modeling capability.
After stacking fixed-length slices of the input sequence, each layer in CST performs a pair of fine-and-coarse-grained attentions with short-long ranges in a sequential manner, coupled with volatile instant positional embedding, enabling efficient token interactions {\em and} improving expressiveness of the model.
In addition to significantly reduced $O(NL+N^2/L^2)$ complexity for sequence length $N$ and slice length $L$, CST achieves superior performance on a variety of tasks.  We show that CST surpasses recently published efficient Transformers on the Long Range Arena benchmark, demonstrating the bidirectional long-range dependency modeling capability of our model. It outperforms the standard Transformer by a margin of $6.9$\% in average accuracy across the five classification tasks of the benchmark, while being of complexity comparable to other efficient transformers. Furthermore, on the word-level autoregressive language modeling task with the WikiText-103 dataset, CST performs competitively against the Transformer model with only $2$\% gap in the test perplexity while outperforming other efficient Transformers.

Published as a conference paper at ICLR 2023
COMPOSITE SLICE TRANSFORMER: AN EFFICIENT TRANSFORMER WITH COMPOSITION OF MULTI-SCALE MULTI-RANGE ATTENTIONS
Mingu Lee'
Saurabh Pitre*
Tianyu Jiang'
Pierre-David Letourneau'
Matthew Morse' Kanghwan Jang'
Joseph Soriaga'
Parham 2
Hsin-Pai Cheng'
Christopher Lott
"ualccom Al Research
Qualcomm Technologies Inc.
(mingul, clott]eqth qua comm. com
ABSTRACT
Since the introduction of Transformers, researchers have tackled the expensive quadratic complexity of the attention mechanism. While significant complexity improvements have been achieved, they often come at the cost of reduced accuracy. In this paper, propose Composite Slice Transformer (CST), Transformer- based network equipped with a composition of multi-scale multi-range attentions, boosting both efficiency and modeling capability. After stacking fixed-length slices of the input sequence, each layer in CST performs pair of fine-and-coarse-gn grained attentions with short and long ranges in sequential manner, coupled with a volatile instant positional embedding. In addition to significantly reduced O(NL+N? N2/?²²) complexity for sequence length N and slice length L, CST achieves superior performance variety of tasks. We show that CST surpasses recently published efficient Transformers on the Long Range Arena benchmark, demonstrating the bidirectional long-range dependency modeling capability of our model with comparable complexity. also outperforms the standard Transformer by a margin of 6.9% in average accuracy across the five classification tasks. On the word- level Wiki'Text- autoregressive language modeling task with various sequence lengths, and the masked language modeling followed by GLUE benchamrk, CST outperforms most other efficient Transformers while being competitive against the Transformer.
INTRODUCTION
Transformers (Vaswani et al. 2017) are one of the most important recent advances in artificial intelligence. Since they can combined in a straightforward fashion with advanced training methods and auxiliary modules, Transformers have proven extremely effective as versatile backbone architecture for achieving state-of-the-an performance in many domains such as natural language
processing (Devlin al., 2018 Yang et al. 2019 Brown et al. 2020 Raffel et al. 2020 Sanh et al.) 2022), vision processing (Dosovitskiy et al. 2020 Liu et al.
2021b Radford et al. (2021). visual
language modeling (Alayrac et al.) (022)) speech recognition (Dong et al.) 2018 Gulati al. 2020
Shi et al. 2021), and reinforcement learning (Chen et al. 2021b Janner et al. (021).
Despite this versatility, Transformers possess expensive memory and computational complexity of ((N2) with respect to input length N in the multi-head self-attention computation. As a result, Transformers often not applied to long sequence data. Since the introduction of Transformers in (Vaswani et al.] (007)), recent work has focused on improving Transformer complexity through various techniques, achieving efficiency gains in complexity and memory requirements (Tay et al. 2020c), with several models attaining O(N) complexity (Wang et al. 2020 Katharopoulos et al.
WWor was completed during employment at Qualcomm Technologies, Inc. "Qullcomm Al Research is initiative of Qualcomm Technologies, Inc

---

Published as a conference paper at ICLR 2023
2020: Ma et al., 2021). Unfortunately, these efficiencies come at the cost of reduced accuracy and often lack the ability to model fine- greeggaided token dependencies, limiting the application of these recent improvements to wider range of practical problems. Recent studies (Zhu et al. 2021: Ren et at. 2021] Nguyen et al. 2021 Zhu & Soricut 2021 Han et al. (021) show that combining efficient techniques for global sequence modeling with fine-grained limited range attention can improve accuracy, maintain low complexity, and enable longer context windows, allowing such models to outperform the standard, full-resolution Transformer on certain tasks. However, optimally combining sequence modeling at different levels of granularity remains an open problem.
To this end, we propose the Composite Slice Transformer (CST), an efficient Transformer-basee network architecture, consisting of a composition of attentions applied to stacked slice representation of the input sequence at different scales, coupled with multi-scale volatile instant positional embedding. For fixed slice length I., CST has a complexity of O(NT+ N2 /T²²), which is comparable or more efficient to linear complexity in many practical settings (Section (A.4). Since slicing restricts fine-grained token interaction across boundaries, CST also leverages an extended local attention, preventing context fragmentation (Dai et al. 2019b) and enabling seamless sequence modeling. These improvements allow CST outperform the standard Transformer on several benchmark tasks. Similar to (Dosovitskiy et al., 2020), CST abstracts the input sequence into another with fewer tokens to compute low-resolution attention with longer range and a fixed-size segment-wise embedding. With a segment length L, the reduced sequence has length N/ Lı; evaluating attention on this reduced sequence has complexity O(N2/L²), With an appropriately chosen L. CST can achieve a significant complexity reduction without loss of performance. Along with the segment-level attention. CST also leverages a full-resolution local attention form multi-scale multi--ange attention (MSMRA)
through composition with the global attention, improving model expressiveness (Section A.5).
unlike (Zhu & Soricut 202T Zhu et al. 2021 Nguyen et al. 2021 Ren al. 2021 Han et al.) 2021).
CST extends the ideas of position-infused attention (Press et al. [022]) and applies them to MSMRA,
which we refer to as multi-scale volatile instant positional embedding (MS-VIPF). In addition to its effectiveness as positional embedding, MI-VIPE provides further parameter efficiency by only requiring storage of reduced lengths of local (L) and global (N/L) attentions instead of the full sequence length N. We evaluate model on bidirectional long-range dependency modeling tasks, an autoregressive language modeling task, and natural language understanding tasks. In our experiments (Section 5). CST achieves state-of of-thee-rt performance among all Transformer based models (including the standard Transformer and recently proposed efficient Transformers) and demonstrates strong performance on a wide variety of tasks.
The paper is organized as follows. In Section and Section we discuss recent efficient Transformer developments, diseuss strengths and weaknesses, and outline the inspiration for CST. In Section 4 we present our model, Composite Slice Transformer, and describe its features. In Section 5 we provide our experimental results on the Long Range Arena, WikiText-103 autoregressive language modeling, and the GLUE benchmarks, demonstrating the efficiency and versatility of CST. In Section σ we conclude with a summary of our work.
2 RELATED WORK
Tay et al. (2020c) provides comprehensive study of proposed approaches to accelerate the attention
mechanism of Vaswani et al. (2017). The key differentiating factor among the approaches presented the modeling assumptions used approximate the original attention map. For example, common
assumptions include sparsity (Child et al. 2019 [o et al. 2019 Beltagy et al. 2020 Ainslie et al.
2020 Zaheer et al.) 2020 Tay al. [020aa] Kitaev et al. 2019) and low-rankness (Wang et 20020 Choromanski et al. 2020; Katharopoulos et al. 22200. Chen et al. (2021a) combines these two assumptions. Other architectures leverage additional memory for compressing the global context (Lee) et al. 2019 Ma et al. [221] Jaegle et al. [2021). In order to capture fine-gra ine-grained token interactions that might be missing in the abstractive attention, (Zhu & Soricut 2021 Zhu et al.) 202 Nguyen ct al. 2021 Ren et al. 2021) use process akin to leverage a full-resolution local attention to form a mulri-scale multi-range attention (MSMRA). These approaches, however, do not compose the local full-resolution attention and global eeduced-resolution attentions in a series. Absent from this literature, serial composition and positional embedding would improve accuracy while preserving the efficiency (see the following sections for how we address this enhancement). More recently,
2

---

Published as a conference paper at ICLR 2023
there also have been proposed sequence models with structures strong inductive biases achieving significant improvements in benchmarks such as (Gu et al. 2021 Mehta et al. 20222 Ma et al. 2022 Liet al., 2022). (Press et al. 2021) propose the position- position-infused infused attention (PIA), which is an attention module with a layer-wise positional embedding applied only to queries and keys, to address token representation reusability issue in increasing window attention due to positional information draft, while avoiding expensive computation of relative position encoding (Dai et al., 2019b). Another study of adding positional embedding to values is conducted in (Tsai et al. 2019 concluding that positional embedding on value does not lead to performance improvement. We extend these ideas in CST and apply in MSMRA.
PRELIMINARIES
3.1 TRANSFORMERS AND BULTI-HEAJ SELF-ATTENTIO
A Transformer layer consists of multi-head self-attention sublayer followed by feed-forward network (Vaswami et al. (017)) with an optional cross- atteettnnn sublayer when used as decoder. The multi-head self-attention defined as the concatenation of the self-attention output of all attention heads:
Y= Yo, Y,,..., Y Y
where [:], denotes concatenation in the nhh dimension, and each of the outputs Y,, E Xxd is scaled dot-product attention computed from the input X RNNDD as
Qn T Vdn
n softmax
V AV
In Eq. 2 Q XW, g.h. K, XW k.A. k.A, and V XW,,, u.h are queries, keys and values, respec- tively, expressed linear transformations of the input X by W. .A E R We assume the queries, keys, and values have the same hidden dimension: d,, D/ H. For the rest of the paper, we omit the head index and scaling factor 1/ V for simplicity. We denote the query, key and value at some position index by k,, Vi, qi 1xd respectively. In this context, the attention output the 7h token position y; R xdd, corresponds to
y; softmax (q. V.
(3)
Due to the nonlinearity and normalization property of the softmax function, QK must be computed obtain the attention weight, followed by value aggregation through the attention weights, AV, resulting in ) complexity with respect to the sequence length N for the self-attention.
3.2 ABSTRACTIVE ATTENTIONS AND MULTI-SCALE MULTI-RANGE ATTENTION (MSMRA)
We refer to the family efficient attention approaches in which the lengths of the attention operands reduced to M N by applying abstraction function <(-) as abstractive attentions. This approach results reduced attention complexity while retaining the form basic attention compu- tation in Eq. Many recent approaches follow this template (Wang al. 2020 Ma et al. 102 Dosovitskiy et al. 2020). We focus on cases where the operands of attention, i.e., query, key, and value, abstracted, noting that there are other possible choices, e.g., abstracting only query and key.
In such cases, the attention mechanism is reduced to
yP softmax (q, K
V.
(4)
where Q, K, and V are abstracted queries, keys, and values, respectively, q. is 7t row of Q, and Yv is the attention output token with the abstracted query token qr obtained by
qे o ((qien,)))
(5)
In order to restore the resolution of the output, since the query is abstracted, we define me-to-many mapping function (-) as
yien, {w/ (yr)).
3

---

Published as a conference paper at ICLR 2023
Input Sequence
P
P
Slicing
K
K
Y
Pooling
S
S
Local Attention
De-Sliinng
Sequence
Figure Illustration of Composite Slice Attention. CSA consists of full-resolution local attention with computational complexity O(NL) and a low-rcsolution global attention with complexity O(N2/IA).
A more detailed description of abstractive attention is presented in Section A.1
Although many previous abstractive attention approaches have achieved sub-quadratic or linear complexities, they typically result in degraded benchmark performance. However, Transformer-bise based models that leverage multi-scale attention by combining local attention and global attention perform competitively against the standard Transformer. In fact, these models can outperform the standard Transformer on certain tasks, while still maintaining efficiency (Zhu & Soricut [001]] Zhhu et al.] 2021 Nguyen al. [202I] Ren et al., (202I). While other types of MSMRA are described in Section A.2 our proposed attention mechanism is essentially an MSMRA of the form
= Y1, + +// (yg.r),
where Yı, is the local attention output and yg.i is the global attention output, leveraging a one- dimensional version of the token abstraction used in (Dosovitskiy al. 2020) for the global attention, but with additional composition of local attention.
4 COMPOSITE SLICE TRANSFORMER
We describe the key ideas of Composite Slice Attention (CSA) and CST network, a Transformer- based model with CSA replacing the full softmax dot-product attention in the standard Transformer. CSA leverages both full-resolution attention in limited ranges and abstracted attention capture long-range interactions. Unlike previous approaches, the multi-scale, multi-range attentions are combined through function composition in serial connection, which allows information passing across representations at different scales and improves expressiveness of the model. See Figure [o an illustration of the CSA module and Appendix A.3 for full architecture diagrams.
4.1 SEQUENCE REPRESENTATION AS STACKED SLICES AND CSA
In high-level categorization, the multi-scale multi-range attention of the CST corresponds to the combination of block wise local window attention (Beltagy et al.) 2020) and patch- global attention (Dosovitskiy et al. 2020) in one-dimensional form. CSA layer starts with converting the input sequence X XD into stack of slices S E Nx by slicing it with fixed length L. implemented simply as Reshape operation. Two attentions with different granularity are then performed sequentially in each direction. First, the batch size B and the number of slices N/L is combined as new batch size BN/L: L, so that we parallelize the local attention for all slices. Then, the local attention performed across the tokens within each of these new batches:
Yi = softmax (QıKT) V1
where Q₁ K1, and V1 RBN/LxLxd are the queries, keys, and values for each local attention head, computed as SW 1. SW1,s. and SW respectively, with Wi Dxd Next, the dimension of length L in the local attention output collapsed using an abstraction function to get the slice embedding S BN/LLD, Specifically, use simple mean pooling S, o(Y,,)
4

---

Published as a conference paper at ICLR 2023
Eizo ms,YY. ...// Eizo m, where and I denote the slice index and the token index, respectively, and E RN/LLL is the stack of slices of the binary attention mask that is optionally given in the case that the input sequence is padded; c.g., when data batch has samples with different lengths. ! Then the second, global attention along the slice dimension is performed to model full-range slice-wise interaction in a reduced resolution:
Y = softmax Qg K
V
where Og Kg. and Vg is the abstracted queries, keys, and values for the global attention obtained by applying W g.g. We g. and W g.v to S. Finally, the output of the global attention is broadcasted to the original resolution and added to the local output:
Y, Y1, Y Y1, + vp g.
(10)
where ei( ( g.)) a broadcasting function that restores only the sequence length, i.e., Yg. = Y g. for i E Sy, since the output of the local attention still holds the full resolution. This process can be implemented as a simple broadcast-add operation.
Slice Extension: Addressing Fine-Grained Context Fragmentation The local attention of the stacked slice representation of the sequence S is strictly bounded, resulting in potential context fragmentation (Dai al., 2019b). Although the global attention models the slice-wise interactions, may not be sufficient to capture the important fine- fine-grained token dependencies. To allow token-level interaction between slices, we slightly extend each slice into its neighbors, allowing slices share tokens. This extended local attention can be computed by having keys K, exi and values Vi, transformed from extended stacked slices Seu. where a denotes the extension ratio. The extension can be implemented by concatenating shifted-slices in keys and values:
Sext (0 -
S, [S (1,,0:(a 1)1./,, O (a- ((-1))/22112 N/LxalDD (11)
for < 3 where the Python notation of indices selection is used.
Slice Extension and Multi-Scale Causal Mask for Autoregressive Sequence Modeling In order to apply CST to autoregressive sequence processing tasks, we propose custom causal masking and slice extension schemes. For the local token-level attention, we apply an L x L causal mask map with oo above the main diagonal and zero elsewhere to the score tensor Q,K," However, since the leftmost tokens in each slice have few (and possibly zero) tokens to attend to, we extend the keys and values only on the left-hand side to encourage better fine- ine-gndieed dependency modeling, i.e.,
SAR ext
[[0 [[ S. (311, .S]
(12)
For the global attention, an extra care must be taken to prevent leftward information leakage while computing the slice embedding via mean pooling. The diagonal elements in the N/L x N/L casual mask are set to be -c in contrast the local counterpart. In addition, at the slice index t, the shifted query Qg is used for query instead of Qg. (note that Kg. is handled by the global casual mask).
Increased Expressiveness of CST We mathematically motivate the improved performance of CST over competing efficient Transformer models. We show that a given function that CST is able to represent is away from rational function with Euclidean degree 4d(e), while competing approaches such as H- H-Transformer-II ID (Zhu & Soricut, 202T) can only approach rational function with Euclidean degree d(e). This implies that CST is more expressive than other approaches that do not involve compositions of multi-scale attentions. We state the main result below and present the details in Appendix A.5
Proposition 1. For any fixed > 0, there exists some Euclidean degree d(e) O(lo((e) such that,
y C Siaaee and yCS C (MMAd())
(13)
where M corresponds to the total number of weights in CST, and S is the space of ratios of real analytic functions that are e away from a rational function with Euclidean degree d with input in M
Normalization with the sum of the binary mask, i.e., the number of nonzero mask values, instead of the slice length I., avoids biases in the mean computation induced by masked tokens.
5

---

Published as a conference paper at ICLR 2023
4.2 MULTI-SCALE VOLATILE INSTANT POSITIONAL EMBEDDING (MS-VIPE,
Since we reduce the input lengths of both global and local attentions, the full positional embedding of the maximum imput sequence length is no longer necessary. For the local attention, we can limit the positional embedding length to the attention range (i.e., the slice length L),, sharing the embedding across slices. In addition, as we aggregate the tokens from each slice for the global attention, is more natural to have separate positional embedding of length N at the scale of slice embedding instead of aggregating the full-resolution positional embedding with the same process as the token embedding. The total number of parameters is ((L + N))) less than that of conventional positional embedding (ND).
To this end, CST uses two positional embeddings P1 E I and Pg E N/LXD applied at different scales, in a fashion similar to that used by (Han et al. 202I, but with a few crucial differences: first, instead of adding the positional embedding to the stacked slices of token embedding at the embedding layer and having aggregated positional information as the layers stack up (Press) eet al. 2021). CST applies them instantly at the corresponding attentions in each layer before the linear transformations. Second, the positional embeddings are applied for the queries and the keys, not for the values, to prevent accumulation of positional information in sequence representations. Since the positional embedding and can undesirably dominate the contextual information at top layers which potentially leads to performance degradation. Our experiments in Section A.662 show that the multi-scale volatile instant positional embedding (MS-VIPE) is more effective as compared to the conventional absolute full-length positional embedding. Equations (8) and (9) are rewritten as:
all layers are added, they can be accumulated over the layers
YI softmax (L(S + Pi) Wi, P1) WI.)) SWI...
(14)
Y softmax (((S + Pg) W ((5 W wg,x)") SW g.u.
(15)
For the extended local attention, we modify the corresponding positional embedding P1 to have the extended length aL, similarly to Kj,
4.3 COMPLEXITY AND PARAMETER REDUCTION IN CST
CST has linear plus decimated quadratic complexity O + N2/L²) compared to the O(N2) complexity of the standard Transformer. However, in practical range of sequence lengths, e.g.. from a few hundreds to a few tens of thousands, CST has a comparable or better efficiency than other efficient transformers with linear complexity O M) with choices of the abstraction lengths M, e.g., from 64 to 256 or higher for even longer sequences, since the slice length L for CST is typically less than M, even with additional for query, key, and value transformations of 3(N/ almost negligible. Furthermore, unlike most efficient transformers that can have similar or higher complexity than the standard transformers with short input sequences, CST has better efficiency even in such cases. See Section A.4 for more details of practical complexity analysis.
which is
EXPERIMENTS
To demonstrate the computational efficiency and sequence modeling capability of CST, we evaluate model in three different contexts: (1) bidirectional long-range dependency modeling classifi- cation tasks (2) word-level auto-regressive language modeling and (3) masked language modeling short sequences. Throughout this section,
and transfer learning to natural language understanding unless stated otherwise, it is implied that we train each model from random initialization, reporting its test performance from the model with the best validation result in each case.
5.1 BIDIRECTIONAL LONG-RANGE DEPENDENCY MODELING
Datasets and Baselines The Long Range Arena (LRA) benchmark (Tay et al. 2020b) is a suite of classification tasks that evaluate long-range dependency modeling capabilities with datasets from several different modalities with lengths ranging from 1k to 16k. We evaluate CST on the five tasks broadly used in literature, ListOps, Text, Retrieval, Image, and Pathfinde, where the maximum

---

Published as a conference paper at ICLR 2023
CST (L=8) @C (CT(LL (L=16)
Transtormer
LS Transformer
TTTansformer11
Otystromformer Luna
Linear Transtormer
LRA Score
10
60
Performar
Untorrer
0.0
06
56
44
54
Retormer
02
52
Relative
Figure LRA score (y-axis), relative speed (x-axis), relative GPU memory usage (circle radius), and parameter count (color). With competitive efficiency and smaller model sizes, CSTs outperform strong efficient Transformer baselines as well as the standard Transformer hy significant margins. The speed and memory usage measurements can be different depending devices and implementations.
Table I: Test accuracy on Long Range Arena (LRA) benchmark.
Model
ListOps
Text
Retrieval
Image
Pathfinder
Average
Transformer (ours)
39.92
64.20
82.11
44.25
74.79
61.05
Transformer (Tay et al. 2020b
36.37
64.27
57.46
42.44
71.40
54.39
Transformer (Xrong el al. 2021)
37.10
65.02
79.35
38.20
74.16
58.77
FNet
36.74
64.37
74.29
44.08
50.22
53.94
Linear Transformer
37.40
65.16
82.73
43.81
74.74
60.77
Performer
37.25
64.65
81.69
41.73
72.91
59.65
Cosformer
38.26
64.59
82.17
41.91
67.72
59.73
Reformer
18.04
60.94
79.19
40.38
67.66
53.24
Linformer
38.71
58.73
79.88
45.31
70.11
58.55
Luna
38.36
65.20
81.88
43.16
74.04
60.53
Nyströmformer
37.50
65.01
80.42
51.13
69.73
60.76
H-Transformer-ID 1D
38.21
66.09
84.19
46.03
72.45
61.39
Long Short Transformer Scatterbrain
38.86
64.93
83.88
47.45
75.28
62.08
38.71
63.52
81.12
41.01
70.11
58.89
CST (L 8) CST (L = 16)
37.45
77.23
84.15
51.27
76.32
65.28
37.90
73.60
84.00
51.39
76.97
64.77
sequence length is 4k. We compare CST's efficiency and performance against several state-of- the-art efficient Transformer models. Specifically, we evaluate our model and other Transformer models from group of non-abstractive attention methods: FNet (Lee-Thorp al.) 202T). Linear Transformer (Katharopoulos et al. 2020), Performer (Choromanski et al.) [002)). Cosformer (Qin et al.
202T) group of abstractive attention methods: Reformer (Kitaev al.190 Linformer (Wang et al. 2020). Luna (Ma et al. (021). Nyströmformer (Xiong et al. 2021). and another group of multi-scale multi-range attention methods: T-Transformer-11 (Zhu & Soricut [202)) Long Short Transformer (Zhu et al.] 20211, and Scatterbrain (Chen et al.) 2021a).
well the standard Transformer (Vaswani et al. 2017). We outline experimental setup for the Long Range Arena in Appendix I Our setup is favorable the baseline Transformer provide fair condition the challengers, explaining the difference in performances of Transformers from previous work.
Results Our experimental results on the LRA benchmark are given in Table I We observe that CST surpasses the state-of-the-art efficient Transformers with large margins. The best performance achieved using a slice length 8, outperforming the Transformer baseline by 4.23 points average score across all tasks. The largest improvements tasks, while a minimal degradation is observed on the ListOps task. addition, as discussed in CST has the added benefit of requiring fewer parameters for given model size thanks
observed the Text. Retrieval, and Image
Section 4.1

---

Published as a conference paper at ICLR 2023
Table 2: Autoregressive language modeling perplexity on WikiText-103 with N 256. Results for other models are taken from (Nguyen et al. (02T).
Model
Validation Perplexity
Test Perplexity
Transformer
33.15
34.29
Linear Transformer
37.27
38.40
FMMFormer (2-kernel Band20)
35.10
36. 16
CST (T. = 32, = 3)
34.18
34.98
Table 3: CST ablation study Wiki with varied slice length L and extension ratio a with
Table 4: CST WikiText- 103 test perplexity with N 1024. Results for other models taken from
N 256.
CCen et al. 202
L
a
Valid PPL
Test PPL
Relative Speedup
Attention
Test PPL.
8
1
39.15
39.78
1.50x
8
2
36.59
37.33
1.51
Full Attention
25.258
3
36.10
36.78
1,49x
Reformer
27.68
16
2
35.78
36.52
1,52x
Performer
66
16
3
35.28
36.04
1.47x
Scatterbrain 26.72
32
2
34.83
35.60
1.54x
CST(L 32,
26.82
32
3
34.18
34.98
1.51x
its positional embedding characteristics, although this benefit may be marginal the network size increases.
We also measure relative speed, and relative GPU memory usage for each model under comparison on a NVIDIA Tesla V100 GPU with 32GB memory on Retrieval dataset with the sequence length of 4k and report the results Figure 2 Here, relative speed is computed as the number of training steps per second divided by that of Transformer, and GPU memory usage is measured using the Py PyTorch command, torch. cuda. max meax__moorr__
ocated (), both on the Retrieval task. clearly seen that CST outperforms all models while having competitive computation and memory efficiency to other efficient Transformer models.
We present an ablation study regarding the choice of positional embedding and aggregation method on the LRA benchmark in Section A.6.2 In summary, variants of CST consistently outperform all other efficient models (Table 7. except that switching the MSMRA composition order, i.c. attentions in global-local order, performs slightly worse than Long Short Transformer (Zhu et al. (022). We demonstrate that the composition of MSMRA in the local-global order and the proposed positional embedding are the most important components contributing to CST's accuracy. While the best overall performance is achieved with L 8, we find that the slice length L has less effect than other hyperparameters. We also find that attention outperforms an MLP-based local token mixing scheme and that mean pooling aggregation outperforms max pooling and linear projection (Table
5.2 AUTOREGRESSIVE LANGUAGE MODELING
In this section, to evaluate its applicability language model, we conduct an autoregressive language modeling experiment on the wevd- WikiText- 103 dataset (Merity et al. 2016).
Dataset and Experimental Setup The Wiki'Text- 103 (Merity al. 2016) dataset is collection of featured articles on Wikipedia. It has 103M/218K KK/46KK words in suining/validationness sets, respectively. The task in this experiment is to predict the next word given the history of past words. We follow the experimental setup in (Nguyen et al. 202T) and that in (Chen et al., (2021a) for the context window length 256 and 1024, respectively, and train CSTs to compare the results with their reported results. While the dataset allows for a larger context, we used the 256 and 1024 context window lengths to match the baselines. CST also uses the causal mask and slice embedding described in Section 4.1 More discussion of the experimental setup can be found in Appendix A.7.1
Results We report the perplexities of the best performing variant of CST (L = 32, a = 3) compared to other ofate-of-the-art efficient Transformer models in Table 2 and Table 4 CST outperforms other efficient Transformer including Linear Transformer (Katharopoulos et al. 2020
and Performer (Choromanski et al. 2020), kernel method-based linear-complexity models, and
8

---

Published as a conference paper at ICLR 2023
Table 5: Bidirectional MLM and NLU transfer learning evaluation GLUE benchmark.
Model
MLM
COLA
MNLI
MRPC
QNLI
QQP
RTE
SST
STSB
GLUE Average
BERT
4.84
60.63
83.35
91.17
90.04
87.67
69.68
92.89
87.43
82.86
Nyströmformer (64)
6.77
39.39
78.75
87.23
87.35
85.64
54.87
90.48
84.28
76
Performer (64)
6.44
46.64
77.48
82.23
85.7
85.8
$7.76
90.02
78.00
75.46
Luna (64)
5.63
42.63
78.26
82.94
85.78
84.18
59.21
90.94
75.89
74.98
FNet
8.62
44.58
75.15
84.00
84.15
84.61
63.18
89.33
82.84
75.98
CST (T. 16,
6.00
58.49
76.45
81.76
84.44
85,24
59.57
91.74
73.77
76.43
CST (L. 16,
5.42
58.87
78.04
82.39
85.52
85.70
60.29
92.20
75.59
77.33
CST (L 16, a 3)
5.28
55,98
79.68
83,49
84.83
86,90
61.37
92.20
81.67
78.27
CST (T. = 32, = 1)
5.77
60.34
78.47
83.06
85.17
86.36
59.93
91.74
78.26
77.92
CST (T, = 32, a 2)
5.30
57.34
80.73
85.85
86.31
87.08
59.21
91.97
85.95
79.31
CST (L- 64, 0
5.56
59.69
81.12
89.42
88.21
87.42
61.37
92.43
87.76
80.93
FMMformer, while being comparable to Scatterbrain (Chen al. 202 la), noting that the latter two are MSMRA-based models. Table 3 we provide an ablation study demonstrating the impact of L and on validation and test perplexity. We observe that longer local attention length leads to better perplexities while being much shorter than the the context window length, c.g. CST with L 32, 3 has the local window length 64 that is 4 and 16 times smaller than the context window lengths 256 and 1024, respectively. We believe that addressing the missing global context, as discussed in A.9 and better hyperparameter search will improve the perplexity. We also observe consistent 1.5x speed-ups across configurations compared to the standard Transformer in Table
Additional Experiment on PG-19 We additionally conduct an experiment on PG-19 dataset (Rae et al., 2019). We use various combinations of sequence length N,, slice length L, and extension ratio a to match the attention complexity of CSTs to those of Transformers with = 256 and 512. While the validation and the test perplexities with discussion can be found in A.7.2 we observe CST consistently outperforms the Transformer counterparts with the same attention complexities.
5.3 BIDIRECTIONAL LANGUAGE MODELING AND TRANSFER LEARNING
We further evaluate CST on bidirectional language modeling and transfer learning on GLUE bench- mark with relatively short input sequences, i.e., N 128. Masked language modeling (MLM) was proposed in (Devlin et al. 2018) as a pretraining method of transformer encoder models and greatly improves downstream natural language understanding (NLU) performances when fine-tuning the pretrained models. We follow the experimental setup of (Devlin et al.) 2018) for conducting both pre-training and fine-tuning including datasets, masking rate, batch size, optimizer settings, and evaluation metrics with a few exceptions. We report the MLM validation perplexities and GLUE scores with accuracy on each task for variation of L and a in Table Further experimental details, more experimental results, and discussion can be found in A.8. CST consistently outperforms other efficient transformers and closes the gap to the baseline BERT model by 0.46 validation perplexity and 2.45 points in GLUE score.
6 CONCLUSION
In this paper, present Composite Slice Transformer (CST), efficient Transformer-basee network equipped with composition multi-scale maulti-range attentions. Using stacked slice representation of input sequences, CST layer performs grained attention in a sequential manner at a low complexity cost of O + N2 [.2). In addition to the reduced complexity, we also show that CST improves performance on various sequence modeling tasks. On Long Range Arena, word-level autoregressive language modeling on WikiText-103. masked language modeling. and natural language understanding benchmarks, CST significantly surpasses strong baselines including recently proposed efficient Transformers, and sometimes the standard Transformer. We highlight limitations and potential directions for future work A.9
of local fine-grained attention and global coarse-
REFERENCES
Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. Etc: Encoding long and structured

---

Published as a conference paper at ICLR 2023
inputs in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 268-284, 2020.
Jean- Cran-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, lain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, et al. Flamingo: a visual language model for few-shot learning. arXiv preprint 11Xx:2224..1198,, 2022.
Iz Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.00 10004440555000 /50, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal,
Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré. Scatterbrain: Unifying sparse and low-rank attention approximation. arXiv preprint arXiv:21 10. 15343, 2021a.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems, 34, 2021b.
Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv: 1904v 10509, 2019.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. In International Conference on Learning Representations, 2020.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V Le, and Ruslan Salakhutdi- nov. Transformer-xl: Attentive language models beyond fixed-length context. arXiv preprint 1rXiv:1901.02860, 2019a.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. Transformer-xl: Attentive language models beyond fixed-length context. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pp. 2978-2998899 2019b.
Zihang Dai, Guokun Lai, Yiming Yang, and Quoc Le. Funnel-transformer Filtering out sequential redundancy for efficient language processing. Advances in neural information processing systems, 33:4271-4282, 2020.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805. 2018.
Linhao Dong, Shuang Xu, and Bo Xu. Speech-transformerr a no-recurrence sequence-to-sequence model for speech recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5884-5888. IEEE, 2018
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint DrXiv:2010.11922 2020.
Albert Gu. Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. arXiv preprint 11X0v:211..00396, 2021.
Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, et al. Conformer: Convolution-augment transformer for speech recognition. Proc. Interspeech 2020, pp- 5036-5040, 2020.
Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. Advances in Neural Information Processing Systems, 34, 2021.
10

---

Published as a conference paper at ICLR 2023
Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidi- mensional transformers. arXiv preprint arXiv:1912.12100 2019.
Andrew Jaegle, Felix Gimeno, Andy Brock, Oriol Vinyals, Andrew Zisserman, and Joao Carreira. Perceiver: General perception with iterative attention. In International Conference on Machine Learning, pp. 4651-46660 PMLR, 2021.
Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcement learning as one big sequence modeling problem. In Advances in Neural Information Processing Systems, 2021.
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference Machine Learning, pp. 5156-5165. PMLR, 2020.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference Learning Representations, 2019.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set trans- former: A framework for attention- based permutation-invarian neural networks. In International Conference on Machine Learning, pp. 3744-3753. PMLR, 2019.
James Lee- teorp, Joshua Ainslie, Ilya Eckstein, and Santiago Ontanon. Fnet: Mixing tokens with fourier transforms. arXiv preprint arXiv:2105.03824 2021.
Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. What makes convolutional models great on long sequence modeling? arXiv preprint arXiv:2210.09299 2022.
Hanxiao Liu, Zihang Dai, David So, and Quoc V Le. Pay attention mlps. Advances in Neural Information Processing Systems, 34:9204-9222 9215, 2021a.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 10012-10022, 2021b.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint 1rXiv:1711.05101. 2017.
Xuezhe Ma, Xiang Kong, Sinong Wang, Chunting Zhou, Jonathan May, Hao Ma, and Luke Zettle- moyer. Luna: Linear unified nested attention. Advances in Neural Information Processing Systems, 34, 2021.
Xuezhe Ma. Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Luke Zettlemoyer. Mega: Moving average equipped gated attention. arXiv preprint arXiv:2209.1066 2022.
Harsh Mehta, Ankit Gupta, Ashok Cutkosky, and Behnam Neyshabur. Long range language modeling via gated state spaces. arXiv preprint arXiv:2206. 13947, 2022.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint arXiv: vrXiv:1609.07844 2016.
Tan Nguyen, Vai Suliafu, Stanley Osher, Long Chen, and Bao Wang. Fmmformer: Efficient and flexible transformer via decomposed near-field and far-field attention. Advances in Neural Information Processing Systems, 34, 2021.
Ofir Press, Noah A Smith, and Mike Lewis. Shortformer: Better language modeling using shorter inputs. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguisties and the 1 11th International Joint Conference on Natural Language Processing ( (Volume I: Long Papers), pp. 5493-5505, 2021.
11

---

Published as a conference paper at ICLR 2023
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. In International Conference Learning Representations, 2021.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748 8763. PMLR, 2021.
Jack W Rac, Anna Potapenko, Siddhant M Jayakumar, Chloe Hillier, and Timothy P Lillicrap. Compressive transformers for long-range sequence modelling. In International Conference on Learning Representations, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1-67, 2020.
Hongyu Ren, Hanjun Dai, Zihang Dai, Mengjiao Yang, Jure Leskovee, Dale Schuurmans, and Bo Dai. Combiner: Full attention transformer with sparse computation cost. Advances in Neural Information Processing Systems, 34, 2021.
Victor Sanh, Albert Webson, Colin Raffel, Stephen Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Teven Le Scao, Arun Raja, et al. Multitask prompted training enables zero-shot task generalization. In The Tenth International Conference on Learning Representations, 2022.
Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers secretly fast weight programmers. In Proc. Int. Conf. on Machine Learning (ICML), Virtual only, July 2021.
Yangyang Shi, Yongqiang Wang. Chunyang Wu, Ching-Ferge Yeh, Julian Chan, Frank Zhang, Duc Le, and Mike Seltzer. Emformer: Efficient memory transformer based acoustic model for low latency streaming speech recognition. In ICASSP 2021-2021 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 6783-6787. IEEE, 2021.
Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da- Pa-Cheng Juan. Sparse sinkhorn attention. In International Conference on Machine Learning, pp. 9438-9447. PMLR, 2020a.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. Long range arena: benchmark for efficient transformers. In International Conference on Learning Representations, 2020b.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, arXiv preprint ar XxXiv:2009.06332. 2020c.
Ilya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lueas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mlp-mixer: An all-mip architecture for vision. Advances in Neural Information Processing Systems, 34: 24261-24272, 2021.
Lloyd Trefethen. Multivariate polynomial approximation the hypercube. Proceedings of the American Mathematical Society, 145(11):4837 2017.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philipee Morency, and Ruslan Salakhut- dinov. Transformer dissection: A unified understanding of transformer's e''s attention via the lens of kernel. arXiv preprint arXiv: 1908. 1775, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones. Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017
12

---

Published as a conference paper at ICLR 2023
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv.1804.07461, 2018.
Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04477 2020.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-ar natural language processing. In Proceedings of the 2020 Conference Empirical Methods in Natural Language Pro- cessing: System Demonstrations, pp. 45, Online, October 2020. Association for Computational Linguisties. URL https: www. ac wweb http.//rr..aaaooooo//2222222
semnlp-demos 6
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pp. 10524-10533. PMLR, 2020.
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. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35:16, pp. 14138-14144 2021.
Jianwei Yang. Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao. Focal self-attention for local-global interactions in vision transformers. arXiv preprint arXiv:2107.00641 2021.
Zhilin Yang. Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. Advances in neural information processing systems, 32, 2019.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang. Li Yang, et al. Big bird: Transformers for longer sequences. Advances in Neural Information Processing Systems, 13:17283-17297, 2020.
Chen Zhu, Wei Ping, Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandkumar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision. Advances in Neural Information Processing Systems, 34, 2021.
Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards tike visual explanations by watching movies and reading books. In The IEEE International Conference on Computer Vision (ICCV), December 2015.
Zhenhai Zhu and Radu Soricut. H-transformer--le Fast one-dimensional hierarchical attention for sequences. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 3801-3815, 2021.
A APPENDIX
A.I ABSTRACTIVE ATTENTIONS
Abstractive attentions are the family of efficient attention approaches in which the lengths of the attention operands are reduced to M(< NN by applying an abstraction function, resulting in reduced complexity of the attention while retaining the form of basic attention computation in Eq. 3 Abstrac- tive attentions can be further categorized to either resolution preserving or non non-preserving, according to which operands are chosen to be abstracted. Resolution non poeseererniing attention is the result of abstracted queries, further producing abstracted output. This categorization is determined by the requirement of the given task. For example, tasks such language modeling and machine translation
13

---

Published as a conference paper at ICLR 2023
require the full resolution at the output be retained. In such cases, it is common to have only abstracted keys and values while the query resolution is retained; the abstractive attention can be expressed as
softmax (q:K V.
(16)
K ko, .... ky, KNAA11.
(17)
ky Φ (kkee
(18)
where By denotes the abstraction range with the cardinality [22r = M2 for the jth key abstraction
ky and o(.) k E RlayIxd. + ky E I 1xd, many-to-one abstraction function. The
abstracted values V can be expressed similarly. The queries can be similarly abstracted to as
q dg (fq.e.,)) ))
(19)
where q is the 1th row of Q. The attention mechanism is reduced to
softmax
(q. K V.
(20)
where attention output vector y, is obtained at each abstract position i'. In order restore the resolution the output, we define a one-to-many mapping function by as
yie (V' (yo)).
(21)
Resolution non- prespereerii abstraction is often used for the tasks where the full-resolution output is not needed such as sequence-level classification problem. However, in some cases, with additional processing leveraging representations at lower layer, e.g., attention with input tokens, is possible to restore the resolution (Dai et al. 2020 Jaegle et al. 2021
A.2 MULTI-SCALE MULTI-RANGE ATTENTIONS (MSMRA)
Although many previous abstractive attention approaches have achieved sub-quadratic or linear com- plexities, they typically come at the cost of degraded benchmark performance. However, Transformer- based models that leverage multi-scale attention by combining local attention and global attention perform competitively against the standard Transformer; in fact, these models can outperform the standard Transformer on some benchmarks, while still maintaining efficiency (Zhu Soricut 2021
Zhu al. 2021 Nguyen al. 2021 Ren al. 202T..
The local attention, also known as sliding window attention, limits the attention range to the vicinity of query locations. That is, the key abstraction with the whole abstraction range and the query location- sliding
dependent abstraction function becomes K,, = Φk (K) K ( (Hii-j- j--jjju- w w/2) (iijj (-ljj++//00 w/2) for the th query token, where H is the Heaviside step function, w is the window length, and O is the element-wise product. This results in the following equation:
y1, softmax (q.K...) V1
(22)
For better computational efficiency, block-wise key abstraction in Equation equation 22 can be adopted K1,; = k, (K) K ② (H4 - (iflcjjww/il w/2) H (1; w/22) for block-wise attention where t, (b- 1/2)w for the block index b such that
1)w S bw.
For the global attention, abstractive attention with either positional abstractions Zhu & Soricut 2021 Yang et al.) (2211|Ren Ren et al.] (021)) contextual abstractions (Ma et al.) [2021 Zhu et al. (2021) can be employed. The former can be loosely seen as having patch embedding in VIT (Dosovitskiy et al. 2020).
MSMRAs can also be categorized according to how the two attentions are combined. While one approach involves concatenating the abstractions of multi-scale keys and values for single attention
operation (Zuu & Soricut 2021 Zhu et al. 2021 Yang et al. 2021):
softmax (q: K Kz]]) [V Vol
(23)
14

---

Published as a conference paper at ICLR 2023
another separates attentions different scales and combining the outputs (Han et al. 2021 (possibly with some weighting coefficients):
Y4 = V1, + + (yg,a).
(24)
In this case, other non-attentive methods such as kernel method (Nguyen et al. 2021 can also be used for the global attention.
CST belongs to the latter of the two approaches, where the local and global attentions are performed separately and their outputs are combined. This is closely related to Transformer-In- Traasforrmme (TNT) (Han et al. 202T); however, since TNT has a path for the local attention that is independent of the global attention, information exchange between patches is not allowed for the features in the local attention path. Unlike TNT, the composition of multi-granular attentions in CST enables two-way information passing. This is more suitable for modeling highly non-stationary data, such as natural language text data for example, where the locality assumption does not hold.
A.3 ARCHITECTURE OF COMPOSITE SLICE TRANSFORMER NETWORK
We present the overall architecture of CST alongside the detailed CSA architecture in Figure 3 CST consists of a fine ine-grained local attention with computational complexity O(NL) and coarse-gras -gaiine global attention with complexity (INN/LL²) A shared multi-scale positional embedding, MS- VIPE, is applied to all layers. CSA replaces self-attention sublayer in each Transformer block to form Composite Slice Transformer (CST) network.
Two sets of W gs WR, W. transformations in CST may also affect the parameter count. While TNT (Han et al. 2021) reduces the hidden dimension for local attention to limit the network size increase, we keep the same dimension for representations different scales and share the weights between local and global attentions, resulting in no increase in parameter count.
A.4 CONSIDERATION ON PRACTICAL EFFICIENCY AND EFFECTIVENESS OF CST
In this section, we provide an intuition for how and why multi-scale multi-range attention with O(N + N²/ L²) complexity can be a better alternative to the vanilla self-attention than abstraction attentions with linear complexities in terms of both complexity and modeling capability. Improved expressiveness from composition of them is further discussed in Section A.5 A linear complexity can be easily considered to be more efficient than a quadratic complexity. A linear complexity often accompanies another variable; i.e., the abstraction length M in the case of abstractive attention such as (Wang et al. 2020 Ma et al. (021), resulting O(NM) complexity. It is obvious that the quadratic complexity =( is higher than the linear complexity whenever the abstraction length M is smaller than the sequence length, which is mostly true by the definition of abstraction.
However, when notion of sequence decimation comes into play, we come to a little different conclusion. Consider an attention on an abstracted sequence of patch embeddings in (Dosovitskiy et al, 2020) or slice embeddings in CST. Then the complexity of the abstractive attention becomes a decimated quadratic O(N / L2). ). In addition to this, if a full-resolution local attention is used multi-scale multi-range attention, the complexity becomes O(N2 (22//L++NNLLLNN ) = O( L L). We plot the comparison of the linear complexity O(N M) Figure 4a with several practical choices of the number of abstractions M and the decimation ratio, e.g., slice length, L. Here, one can find that a decimated quadratic complexity attention can have better efficiency linear complexity attention, when the sequence length less than few tens of thousands which is considered as practical range of sequence lengths in many tasks and data types.
in CST or (Ha et al. 2021
and D(N2/13+NLL
Figures 4b shows effective number of tokens for each abstraction for both cases with the same choices M and T.. While a decimation, e.g., slicing, retains constant numbers of tokens in each abstraction, the linear complexity attention methods that uses fixed number of abstraction has lincarly increasing effective number of tokens per abstraction with respect to the sequence length. Given a fixed hidden dimension, larger number of effective tokens per abstraction requires the abstraction process to compress more information, resulting in loss of potentially important information and negatively affecting the modeling capability.
Since the complexity of CST has a decimated quadratic term N / the efficiency benefit compared to linear-complexity method keeps closing the sequence length becomes larger, and eventually
15

---

Published as a conference paper at ICLR 2023
Input Token Indices
Input Sequence
Embedding Layer
Ax1
R NILLLDD
Ermbedding
Pj R RxLxD
Slice
Ny LxLxD
W
W
W
m!
Vi
K
Q
Mayer X
Fine-Grained
LayerNorm
Local Attention
R Ny Lx
Slice Embedding
CSA
N/LxD
R
P
LayerNorm
W
K
FFN
Coarse Grarsed
Global Attention
R N/Lx1KD
R A/LxLxx
R
N/LxLxD
Linear
De-Slice
R
Output Sequence
(a) CST Network Architecture
(b) CSA Architecture
Figure 3: Architectures of CST and CSA.
the efficiency order is reversed, it can be seen in 4a However, argue that model can still be beneficial in two aspects. First, it is still more efficient than the standard Transformer. Second, it is possible to find optimal set of hyperparameters such as the slice length 1. and the extension ratio a which result in comparably efficient and more effective in modeling capability to the linear- complexity counterpart, considering the discussion made in this section the effective number of tokens per abstraction.
A.5 IMPROVED EXPRESSIVENESS OF CST SLICE ATTENTION
Recall from Eq.equation 10 that the attention mechanism under consideration takes the form,
Y Y= Y th (Y,)
(25)
where Yi represents local attention, Y, represents global attention and v/(-) is (linear) one-to-many map. In this section, we will compare CST with the H-transformer described in Zhu Soricut (202T). In particular, argue that, for given number of weights (degrees of freedom), our proposed attention mechanism, which involves the composition of attention mechanisms, is more expressive than the H-matrix-base approach proposed Zhu & Soricut (202I) Zhu & Soricut (2021) shares similar characteristics with CST, but does not involve composition, which explains our superior prediction performance (Section 5).
To explain why this so, we first define
y X:: W Wt. W.) softmax (XWW, y) () (XW (XW.).
(26)
which is the standard attention mechanism found Eq.equation [] Here, X is generally a matrix or 3-tensor; in the latter case, apply attention independently to each matrix slice along the third
16

---

Published as a conference paper at ICLR 2023
10a
N/M (M--44
UM (M 64)
500
(M=128))
128)
(M-256)
2561
L-8
10a
MP/22 AL. (8)
11912244 (1-16)
Effective number tokens Abstraction
Lm26
WPI2 nL. 32)
400
complexity
300
10a
200
10a
100
10a
10a
10
5000 10000 15000
20000 25000 30000 sequence length
sequence length
(a) M(NM) vs. O(N3/22+NA
(b) Effective number of tokens/abstraction
Figure 4: Comparison between linear complexity attention and CSA. CSA with the complexity O(N? NN more efficient than linear complexity methods with ((NM) for practical sequence lengths and choices of mpeel-specific hyperparameters M and L. Due to increasing effective number of tokens per abstraction,
performance of abstractive attention with linear complexity degrade as the sequence length gets large.
dimension. Expressing our local and global attention using this notation leads to
Y = (S; WT. WLK Wi,) N/LLLDD
(27)
Yes g = (Y X2 u2 W g.g1
g.k Wg.) R
(28)
where μ F. F.
is fixed vector of mask values, S corresponds to the stack of L-length slices of X described in Section 4.1 and X2 indicates a tensor product along the second dimension, i..,
[Y X2 141
Σ 1=
ligk
14
(29)
which corresponds mean pooling within each slice. For the purpose of comparison, focus 2-level H H-trrasformer where each element at level 1 has L children at level 0 In this case, it can be
shown that the H- H-tranformer approximation takes the form of Eq. equation 25 with
Y (S; Wig. WLA WT.) = Y,M N/LXLLD
(30)
Y# 7 (S X2 JG W 2.99 Wg. W g..) N/LXD
(31)
Note that the main difference between H-Transformer these and CST lies in Eq.equation 31 and Equequtioon 28) in the former, the argument to the global attention is S X2 μ. whereas is Y X2 in the latter.
"In practice. it common have equal weights local and global scales. ie., Wi, W This is special case of the analysis presented here and changes the conclusion no significant way.
"More levels have little impact on our conclusion since H-transformers ultimately exhibit the same level of nonlinearity in the weights whatever the number of levels.
*Refer to (2)) in Zhu & Soricut (2021) for two levels, i.e., Y = y- + p(0) y-))) In this case, p()) corresponds to the one to- many map v-() whereas σa)) A (Ra)" V) corresponds applying the level-1
matrix (1) to the vector V after averaging over slices (i.e,, applying R()))), In this context, this is analogous applying glohal attention the averaged slices vector, namely, S X2 μ..
17

---

Published as a conference paper at ICLR 2023
To demonstrate our claim, let us first introduce quantities of interest, starting with the families of parameterized functions that the aforementioned attention mechanisms encompass. First, assume without loss of generality that all the weights limited to the interval [-1, 1 Then, any attention function learned during the training process must belong to the following sets.
yjs : (Y R Yigk Vyk(SS Wi. WI. WT.)) Vijjk ycs B = (YYERNINDD Yij = ( x2 Wg. W. Wg,))., a(.) E 2i
(32)
(33)
in the case of CST and.
1rth (YER Yije >G WT.: WI,E, WI, Vi,jk -/
(34)
1TH = -YERNNLDD Yi = (5 22 W 2.09 W Wg. W
(35)
in the case H- H-transformer. We want to show that y has more expressive set than ye which explains why CST exhibits better empirical prediction performance than its competitors. To this end, let us introduce the following quantities:
Definition Let p(z); g(x) be polynomials of Euclidean degree d from R.M. to R. We denote by SM, the set of rational functions with numerator and denominator of Euclidean degree at most d, i.e.,
p(x) (xx
SM.d
deg(p), deg(g) S d, x E RM
imbued with the metric
6
p(x) a(x)
d
= llp(x) - a(x) + +ll((x) - b(x)
(36)
q(x) b(x)
where [If(x) maxxe!-1.1) (x We also introduce S to indicate the space of ratios of
real analytic functions, which is a vector space. Further, given any fixed positive E IR, we define,
SMa = [(x))
E SM d (p(x) SM.dd ((x))
SE
(37)
((x))
as the e-ball surrounding SMa in the topology induced on SM,c0 by the metric.
Clearly, for any fixed dimension M, 0 and Euclidean degrees d' d, the family of functions SM. is more expressive than Ma. since the latter a proper subset of the former, i.e., SM,d C SM...
Next, we show that the families of functions y and D are in fact subsets of Sia and Sird respectively, for appropriately chhoonn values of e, d' and d with d' > d. To do so, we need the following result adapted from Trefethen (2017).
Theorem 1. Let fxx be an analytic function from M to RR. Then for every fixed e > 0, there exists polynomial p(x) of Euclidean degree dic) O(lo(()) such that,
[1 - p(x) = max lf(x) - p(x) Se
(38)
xc[-1.1jo
We are now ready to demonstrate our main result, Proposition 2. For any fixed > there exists some Euclidean degree d(e) (llo(E)) such that,
y C Shaaae
(39)
and,
ycs C (MMAd))))
(40)
where M corresponds to the total number of weights.
Any finite bound may be use and has little impact as long as all expressions are subject to the same constraints.
't can be shown that d(--)) is in fact proper metric SMa.a-
18

---

Published as a conference paper at ICLR 2023
Proof. First, recall that (assuming single head) the parameterized functions 7()) from Eq. equa- tion 26 takes the following form
Yo (X; We WA. W.) Σs ellxW,, [XW. Em,n el(XW,) Jmn
(41)
This should be recognized as the ratio of two analytic functions (because the exponential is analytic) paramatrized by the elements of the weight matrices. Following Theorem [ for every fixed set W
of weights W, 9 [ g Wk. W.), there exists polynomials {p,) ((x)), { 9, (x)) of Euclidean
w
degree d(c) = (l))(c)) such that
W, Σ MXW. [WW.ls Pij (x)
max xE|- 1,1
S
(42)
((x..)XX.))....
W. (x)
E
max xE(-1.10
965
S
(43)
2
m2,7
This means that
Pij (xx
d Ya (X; W W.. W.).
Se
(44)
and that No( Wa. W.. W.) Siraat) In particular, this shows that V C. SM,aae d(e) since every element of H has the form of Eq.equation 41 A similar conclusion can be reached for ) and yjcs since elements of these families have the same functional form those of y
All that remains JCS. In this case, it suffices to note that the result of polynomial composition creates polynomials with Euclidean degree bounded by the sum of the degree of the polynomials involved in the composition. Indeed, the above analysis shows that elements of ycs are within c distance from rational functions of the form,
g
Wi (xx)
Pess
Pij"
I
2
Rmm
W
Bask (x)
(45)
w
1 E
Pizk (x)
9i5"
4ish (x)
Wi for some polynomials {Payk (x)]. expressing terms using a common denominator, this expression should be recognized as the ratio of two polynomials, each of which has degree 4d(c), following polynomial composition. Thus, we conclude that y/cs C MM))(()) This proves our claim.
{ Wi
0.jk } of degree d(e). Upon expanding the polynomials and
L
In other words, Proposition 2 shows that our proposed family of attention mechanisms belongs to d())(()) which possesses more expressive power (since 4 d(e) > d(e) ) than the family of functions S M,d(() to which global attention mechanism without composition, such as H-transfomers
Of + (>/ )), belong.
We claim that this is the reason why proposed approach performs better than the approach proposed by (Zhu & Soricut 202I) and other similar mechanisms where linear combinations of attentions, rather than composition, are used. In other words, for the same number of parameters (weights), our proposed approach can capture more complex attentive interactions than that of (Zhu & Sorieut 202T) and related mechanisms, which leads richer of attentions which train the network and, ultimately, better performance.
A.6 MORE INFORMATION AND DETAILS ON LRA BENCHMARK
A.6.1 EXPERIMENTAL. SETUP
We follow the experimental setup described in (Xiong et al., 2021) with a few exceptions in hyperpa- rameters, Specifically, the same Transformer encoder network backbone that consists of
19

---

Published as a conference paper at ICLR 2023
Table 6: Hyperparameterss for LRA benchmark
Network Configuration
D Dembed
Dmodel
DEFN
dn
Thead
Player
Pdropout
256
256
1024
64
4
2
0.1
Task-Specift Training Configuration
Task
N
Batch Size
LRD
Dstep.warmup
step.train
ListOps Text
2k
32
1 x 10-3
1000
20k
4k
32
2 x 10
8000
20k
Retrieval
4k
32
5 x 10-5
800
30k
Image
1k
256
2 x 10-4
175
35k
Pathfinder
1k
256
1 10-4
312
62k
transformer layers with pre-norm (Xiong et al. 2020) with 4 attention heads and the model dimension 256 across all tasks. Further, we replace the self-attention sub-layer by efficient attention alternatives including the slice attention of CST. To obtain label output for classification, we additionally use a classification head network with fully-connected layers of the same hidden dimension with the feed-forward network in the backbone network and ReLU layer between them. We aggregate the output sequence from the encoder by a mean pooling across the length dimension and feed to the classification head. For fair comparison between models with different characteristics, we optimize the learning rates for the baseline Transformer model on each task while keeping all other hyperpa- rameters fixed. For the experimental setup, this allows for strong baseline model, advantageous for the standard Transformer. We then evaluate each model with a learning rate search within a small bracket [0.54o, 4n. 2l.]. where is the base learning rate providing the highest validation accuracy of the Transformer in each task, and report the test accuracy of the model trained with learning rate that gives the highest validation accuracy among the bracket. We note that our experiments have stronger baselines than those found in literature (Tay et al.) 22220b] Xiong et al., 202I) as highlighted in Table D For other efficient Transformer models, we perform a model-specific hyperparameter search as described below and report the test accuracy of the best models.
For the Long Range Arena benchmark, we performed experiments on our PyTorch version imple- mentation of the original source JAX/Flax code (Tay et al., (0220) where we followed its dataset preparation procedure and verified the results, and implemented our model on it. Since we found the performances of LRA tasks have relatively high variances, especially on certain tasks such as ListOps, we first performed a hyperparameter search with the standard Transformer with the base setup in (Xiong al., 2021). The hyperparameters we used for the search include number of layers (2, 4}. number of attention heads {2. 4), and model dimension { {128, 256}. and learning rate 5) x (00-3, 5,)) 66) In addition, for better convergence, we also increased the number of training steps in some tasks. The hyperparameters we determined after the search
be found in 6 As this step is essentially a hyperparameter tuning for the baseline Transformer, we note that we have stronger baseline Transformer model than those reported in (Tay et al. (020b) and (Xiong cet al. 2021), and compare them in Table [ While fixing all other hyperparameters, we performed a learning rate sweep using learning rate bracket as described in 5.1] For each model and task, we pick the best model on the validation dataset with early stopping. and report its accuracy on the test dataset. For the model training, we used Adam W optimizer (Loshchilov & Hutter (017) with linear learning rate warmup and decay, but without weight decay and other training hyperparameters as shown in Table
Since each efficient Transformer has its own hyperparameters and they can affect the performance, we tried a few different values, around the default values used each paper. Specifically, they are: the number of random features {64, 128, 256} in Performer (Choromanski et al. 2020 the projection length (64, 128, 256} in Linformer (Wang et al. 2020) and Luna (Ma et al. 2021). ). the number of landmarks (64, 128, 256} in Nyströmformer (Xiong et al. 20211, the number of hashes
(2, 4] in Reformer (Kitaev et al. (2019). the numerical rank of off-diagonal blocks {16 132, 64, 128) in H-Transformer-11 1DD (Zhu & Sorieut 2021), and the local window segment size {8. 16, 32) and
20

---

Published as a conference paper at ICLR 2023
Table 7: Performances of CST with various slice lengths L, extension ratios a, positional embeddings P. combinations of local and global attentions, on LRA benchmark
and
a
P
Local-Global
ListOps
Text
Retrieval
Image
Pathfinder
Average
8
MS-VIPE
Composition
37.45
77.23
84.15
51.27
76.32
65.28
16
MS-VIPE
Composition
37.90
73.60
84.00
51.39
76.97
64.77
32
MS- MS-VIPE
Composition
39.01
69.24
83.92
54.21
76.73
64.62
64
MS-VIPE
Composition
38.91
66.87
83,59
51.83
78.12
63.86
8
Conventional
Composition
38.26
69.39
83.21
47.77
70.46
61.82
16
Conventional
Composition
39.31
68.22
82.68
49.02
71.30
62.11
32
Conventional
Composition
38.81
66.09
82.16
47.81
71.16
61.21
Conventional
Composition
37.60
65.28
82.27
47.58
72.49
61.04
16
2
MS-VIPE
Composition
37.90
72.81
84.62
53,41
74.87
64.72
16
MS-VIPE
Composition
37.60
70.08
84.42
48.95
74.52
63.11
16
MS- VIPE
Parallel
37.85
71.15
84.02
46.05
75.13
62.84
16
VI-E
Global First
36.19
73.09
84.16
43.36
71.30
61.62
Table 8: Performances of CST with different local modeling and slice aggregation methods, on LRA benchmark.
(L=16, a=l)
Local Modeling
Aggregation
ListOps
Text
Retrieval
Image
Pathfinder
Average
Attention
Mean Pooling
37.90
73.60
84.00
51.39
76.97
64.77
MLP (chidden 16)
Mean Pooling
37.65
66.12
81.66
45.47
74.51
61.08
MLP
(dhidden 32)
Mean Pooling
37.25
69.70
83.63
46.79
74.19
62.31
Attention Attention
Max Pooling
38.05
73.72
84.61
47.88
73.97
63.65
Linear Projection
37.70
73.36
82.33
50.24
72.79
63.28
the rank of dynamic projection {32, 64) in Long Short Transformer Zhu al. 2021). For Long Short Transformer, we optionally used additional ID depth-wise convolution with the kernel 35 as described in (Zhu al., 202T). For scatterbrain (Chen al., (021 we follow the default setting for the model specific hyperparameters as in the official code release. Specifically, for text task, we have cluster size for query/key 16, number of features 16. For Listops task, have cluster size for query/key= = 32 and number of features = 32. For image and pathfinder task, we have cluster size 16 and number of features 16. For retrieval task, have cluster size for query/key 64 and number of features = 64. Additionally, we have number of hashes 2 for all tasks. While each option produces different performances requiring different computation and memory costs, we found variants in each model have similar accuracy and report only the best accuracy among them and the corresponding complexity as comparing them out scope of this paper.
A.6.2 ABLATION STUDY ON LRA
We investigate the effect of each component in CST by performing an ablation study. We the slice length of 16 without extension for local attention as the base configuration. Then, we train CST variant from scratch where one component is changed. Specifically, we consider the variations in: 1) Slice length, 2) Extended local attention, 3) Positional embedding, and 4) Composition of MSMRA. The test accuracics of the variants are given in Table We note that all variants of CST consistently outperforms other models, except for case of the global first composition.
Slice Length First, we vary the slice length and test how the local attention range and abstraction length for the global attention affects the accuracy. Intuitively, one can expect trade-off between fine-grained token interaction modeling and coarse-grained global context capturing, since in the extreme cases either local attention global attention converges to the standard self-attentior While each task has its own best L, shorter slice length tends to give better overall accuracy. One possible
CCSA converges to the standard self-attention with the global attention I. 1 or the local attention .V with V XW?
21

---

Published as a conference paper at ICLR 2023
interpretation is that L 8 16 provides better-formed tokens to the global attention in dynamic manner by the local attention.
Local Attention Extension Ratio While slight improvements are observed on Retrieval and Image tasks, on the contrary to our expectation, extended local attention does not always improve the accuracy on LRA tasks. We conjecture is because LRA datasets has tokens of very fine granularity, ie., byte-level pixel-level, and abstraction of the extended local attention output may result in redundant information for global attention. Thus, we evaluate the effect of the extension ratio on a dataset with coarser-grained tokenization in the Section 5.2
Position Embedding We compare the MS-VIPE with the conventional leamned positional em- bedding that is applied at the bottom embedding layer of the network. MS-VIPE shows consistent improvement over the conventional positional embedding except for the ListOps task where the ined-grained order of each token is essential in this particular task.
Combination MSMRA Instead of the proposed composition of MSMRA that has serial connection of MSMRA in the local-global order, we try two different connections, i.c., parallel and global-local connection. Both of them degrade the accuracy compared to the local-global composition, supporting effectiveness of our design.
Local Modeling with MLP As shown in (Tolstikhin et al. 2021 and (Liu et al., 2021 a),
multilayer perceptron (MLP) can effectively replace the attention without loss of accuracy in some applications. In CST, since the slice length is fixed and relatively short, use of MLP instead of attention can be considered as another source of efficiency with a small increase of parameters. We evaluate variant of CST with 2-layer MLP replacing the local attention, with 2 different hidden dimensions dhidden = 16 or 32 while L = 16 and a 1. MLP in each slice is equivalent to ID convolution with the kernel size and the stride set to the same with the slice length. We observe that using attention for local modeling module is still preferred in terms of accuracy.
Slice aggregation We further evaluate use of different aggregation methods from the simple mean pooling. Similarly to (Rae et al., 2019), we try max pooling and linear projection. Again, linear projection is equivalent to ID convolution with the kernel size and stride set to L. While showing comparable results, they lead degraded performances in Image and Pathfinder tasks. One can expect better accuracy from the linear projection as it is general form of other pooling methods, but this result can be interpreted as limitation of a simple linear projection for modeling sequence translations. The mean pooling has already generalized well, and with better initialization, linear projection expected to converge to the mean pooling or slightly better.
A.7 MORE INFORMATION AND DETAILS ON AUTOREGRESSIVE LANGUAGE MODELING
A.7.1 EXPERIMENTAL DETAIL OF AUTOREGRESSIVE LANGUAGE MODELING
For the autoregressive language modeling experiment, we use an open-source language modeling experiment framework (Schlag al. 2021) and plug in our CST implementation. We follow all training setup including dataset preparation and hyperparameters given in (Dai et al. 2019a), and evaluate with the small-sized network configuration: 16 layers, 8 attention heads, 128 model dimension, and 2,048 hidden dimension. We train all models using the Adam optimizer (Kingma Ba 20,4), the cosine annealing learning rate scheduler with 2000 warmup steps while the base learning rate is 2.5 10-4 for 500K steps with the batch size of 96.
We also conduct autoregressive language modeling experiments with 1024 sequence length. Here, we roughly follow the experiment setup used in (Chen al. 202 The larger model has 512 model dimension instead of 128, and we change the learning rate to x 10-4 number of steps to 90K, and batch size to 32, while keeping all the remaining hyperparameters same that of the small model.
Different choices slice length L and extension ratio a results in the same local attention range. For instance, the combination of L 8, = 16, a = 1 setting, i.e., Lx (3-1) = L. However, since the abstraction length and the resulting granularity of the global attention only depends I., the choices of these hyperparameters affect
has the same key/value lengths with those in the
22

---

Published as a conference paper at ICLR 2023
Table 9: Autoregressive language modeling results on PG-19. Models within double-lined sections have matched attention complexities. Models the top of each section the baseline Transformer while others are CST variants.
Network
L
Context Length N
Valid PPL
Test PPL
Attention Complexity
Transformer
256
19.66
18,70
C1 ((566))
CST
64
3
512
17.61
16.67
1.00 x C1
CST
32
3
1024
16.55
15.60
1.02 x C1
CST
16
2
2048
16.19
15.28
1.00 x C1
CST
16
3
2048
15.93
15.01
1.25 x C1
Transformer
512
17.29
16.39
C2 O(512²) 1.00 C2 (0.25 Ca)
CST
3
2048
15.29
14.39
CST
32
3
4096
15.11
14.15
1.06 x C2 (0.27 x Ca)
Transformer
1024
15.57
14.76
C3 = O(1024")
the performance differently. We examine how the performance is affected by this configuration. To this end, we evaluate CST with combinations of set of slice lengths {8, 16, 32} and set of extension ratios a 21)..
To ensure that the current query token has no interaction with the future key tokens, we design the causal mask and local attention extension scheme better suit CSA as described in Section 4.1 and use it throughout this experiment.
A.7.2 AUTOREGRESSIVE LANGUAGE MODELING WITH MATCHED ATTENTION COMPLEXITY TO TRANSFORMERS ON PG-19
We additionally perform evaluation of CST on PG-19 dataset (Rae et al. 2019) compare Trans- formers where their attention complexities are matched, i.e., O(N3/N* +.5 1 = We use GPT-2 (Radford al. 2019) implementation in Huggingface transformers library (Wolf eet al. 2020), and use the same architecture to implement CST equipped with CSA and MS-VIPE. We train all models for 1M training steps using the batch size 32. We use AdamW optimizer with the learning rate= le - 3, _ = [0.9, 0.99]. and the weight decay= 0.1. We report the validation and test perplexities in Table 9 Efficient attention in CST enables longer context length with the same complexity in attention computation, leading to significantly improved perplexity compared to the Transformer baseline. Note that, with the current architecture in these cases, the overall complexity can be higher in CST since there still are complexity increases in linear layers when they are processing longer inputs. We leave application of caching techniques as future work, that saves complexity in linear layers to match the overall network complexity while enjoying the long- gangrrngge attention.
O22)).
A.8 MORE INFORMATION AND DETAILS ON BIDIRECTIONAL MASKED LANGUAGE MODELING AND GLUE BENCHMARK
In this section, we present more details about the experimental setup and results on the bidirectional masked language modeling (MLM) task Devlin et (2018) and the natural language understanding tasks in the GLUE benchmark Wang et al. (2018) with discussion.
A.8.1 EXPERIMENTAL SETUP
We pre-train transformer models with the masked language modeling (MLM) objective on Book- Corpus Zhu et al.) (2015) and English Wikipedia. After pre-training, the models are fine-tuned on downstream natural language understanding tasks from GLUE benchmark [Wang et al. (2018). We follow the experimental setup of Devlin et al. (2018) for conducting both pre-training and fine-tuning experiment, including datasets, masking rate, batch size, and optimizer settings, with several excep- tions. We pre-trate pre-train the models for 900k steps with sequences of 128 tokens. This corresponds to the first phase BERT pre-training and we consider it to be enough for evaluating on GLUE tasks while expediting the experiment.
23

---

Published as a conference paper at ICLR 2023
With the baseline network architecture of BERT base Devlin et al. (2018), replace its celf-attnnionn layer with different types of efficient attentions such as Nyströmformer, Performer, Luna, and FNet.
For downstream NLU tasks, also follow the setup of Devlin et al. (2018) with one minor change: instead of prepending [CLS] token in the input sequence. we use mean pooling to get the classifier input vector from the sequence output, discussed in the following part of this section.
A.8.2 RESULTS AND DISCUSSION
As shown in Table 5 we can see that CST outperforms competing efficient transformers in terms of MLM perplexity. It can be seen that, while CSTs achieve consistently lower perplexity than most of the efficient transformers, its perplexity decreases as slice length and extension ratio increases. However, CST does not outperform BERT base on contrary to our results on the LRA benchmark. We conjecture this is due to fine-grained masking strategy in the original MLM objective. The MLM pre-training stage involves replacing random tokens in the input sequence with dummy token that the model must predict. After applying the positional embedding, replacing a standard token with a dummy token, i.c., [MASK], translates to injecting high-frequent noise into the input sequence. approximations to the full attention, which must modes in exchange for faster evaluation. In MLM pre- vre-training, all of the
CST and other efficient attention alternatives truncate the input sequences have tigh-frequency content that attention approximations have difficulty capturing. Meanwhile, the sequences in the LRA benchmark are long, low-frequency sequences which can be efficiently compressed. An alternative pre-training method could eventually be developed specifically for efficient transformers that circumvents this issue.
On downstream NLU classification tasks, CST also outperforms among the efficient transformers. But with under-performing pre-trained models compared to BERT, similar degradation trend is observed in evaluation on downstream tasks after fine-tuning them.
One drawback of the current version of CST in the original setting is that the use of [CLS] token is not trivial. [CLS] token can be seen as a global token that summarizes the sequence in the context of the given classification task, and it is often prepended in the input sequence to summarize information from the sequence for the classification purpose. In CST, naively prepending it limits attention range in local attention part and also make the summarization in the global attention highly implicit. We believe this can be addressed by an additional well-designed architecture that uses global tokens and input them to classifier. We leave this as a future work and we instead use mean pooling for the experiment for all models.
While the efficiency gain is reduced due to the short sequence length, can still expect reduction in total FLOPS from using CST. For instance, in the simple case of N 128, L = 64 and a = 1, the complexity of CST is (128 188-64++ + 128 /642) which is almost half of that of the standard transformer (1188)).
A.9 LIMITATIONS AND FUTURE WORK
A.9.1 LIMITATIONS
We summarize limitations of CST discussed in the previous sections.
As discussed in A.8 there mismatch of using token-wise random masking for MLM pretraining. In the abstraction of sequence slices for global attention, high-frequency modes are truncated, i.e., smoothed out, that leads loss of information. While similar arguments can be made to other transformers with abstractive attention, we plan to carefully analyze it and address the issue by designing an alternative pretraining method.
There are some limitations on the casual mask and slice embedding introduced in Section In the global attention, no information of tokens in current slice is taken into account because of the query shift and the attention mask excluding diagonal elements. As result, there is missing information from coarse carse-grained modeling in the current design. This is only happening during the training phase, not in the testing, since the next token prediction with sliding window always has access to all tokens in the sequence up to the current time step. Therefore, this mismatch may prohibit the full modeling capability of CST. To address the issue, we plan design more suitable yet efficient
24

---

Published as a conference paper at ICLR 2023
training objective that allows full use of abstractions in the global attention during training. We leave design of more advanced autoregressive modeling as a future work.
CST requires additional computations of the complexity O(N/L) for the Q, K, and V transformation for the global attention, from the local attention output. However, this increase in complexity is negligible compared to the overall computation, especially when N/L L is small, discussed in 4.3
A.9.2 FUTURE WORKS
There are several potential avenues for extending CST. First, can easily generalize work to multi-level slicing with a higher level than two. This will lead to more improvement in expressiveness of the model while adding more degree of freedoms for better efficiency while enabling its application to much longer sequences. Second, as discussed in Section 4.1, more advanced design autoregres- sive sequence modeling scheme will further improve the performance. Third, while CST is based on fixed-length slicing of the sequence, dynamic or semantic slicing would further improve applicability non-stationary sequences. With end-to-end training, the model can learn the optimal slicing of the data for given tasks and provide layer-wise dynamic tokens. To this end, efficient realization of the dynamic slicing would be the most challenging task. Finally, meaningful next step, modification of CST to better fit vision tasks or training CST-based large language model would lead to more general and practical impacts.
25


Reviews:
[{"review_id": "PifDzsNzU1r", "reviewer": "Reviewer_i8cg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new module that reduces the quadratic complexity of standard Transformers. The key idea is to slice the input sequence into various groups and then perform local and global attention respectively. Experimental results indicate that the local-to-global approach can indeed accelerate the processing speed and save memory costs. Also, the proposed model achieves state-of-the-art performance on several popular NLP benchmarks.", "summary_of_the_review": "I acknowledge the originality and effectiveness of the proposed method, but the paper presentation is not self-contained and should be carefully re-organized. ", "strength_and_weaknesses": "[ Strength ]\n+ The general idea is new. Existing studies on reducing the quadratic complexity focus on either the global or the local pattern, and their combination is seldom explored. The proposed local-to-global method can have benefits from both patterns, i.e., local for higher efficiency and global for higher accuracy. Therefore, the idea is new and technically sound. \n+ Theoretical analysis is solid. The authors give very detailed theoretical analysis on the motivation of the proposed method, which makes the theory solid and rigorous.\n+ The performance on several benchmarks is consistently state-of-the-art.\n\n[ Weakness ]\n- The main body of the paper is not self-contained. Unfortunately, many important statements and analysis are put into Appendix, e.g., the formulation of CSA at the beginning of Section 4. Without these, readers can hardly understand the content clearly. It is not realistic for all readers to refer to Appendix frequently.\n- Some important ablations are not in the main paper. Again, critical ablations such as the speed with respect to the sequence length and the impact of primary hyper-parameters are all put in Appendix, making the paper not self-contained. I strongly advise the authors to re-organize the paper structure and move some important ablations in the experimental section. For example, the two figures in Figure 1 indicate the same meaning, so only retaining one of them could save more space for text. \n- Lack of the comparison to some SOTA linear Transformers, e.g., \n[1] Flowformer: Linearizing Transformers with Conservation Flows\n[2] COSFORMER : RETHINKING SOFTMAX IN ATTENTION", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KM3ITs_P9Os", "reviewer": "Reviewer_LFNY", "summary": "", "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": "", "summary_of_the_paper": "The authors propose a hierarchical attention mechanism to model sequence data efficiently. Several experiments have been conducted to demonstrate the effectiveness of the proposed method.", "summary_of_the_review": "My major concern is on the novelty of the proposed method. It would be better if the authors can further justify how the proposed model is different from MSMRA-based methods, and why the contribution is considered not incremental.\n\nIt would be also better if the authors can explore how more slice length choices may affect model performance from the ablation study. The authors use L=8/16 in LRA benchmark and 32/64 in the MLM/NLU transfer learning evaluation, it would be great if the authors can justify why selecting different slice lengths and how this may affect performance here.\n\nSome technical terms also need to be better presented, e.g., the extension rate is not well introduced in the main paper.", "strength_and_weaknesses": "Strength:\n* The authors focus on an important problem in sequence modeling\n* The paper is organized well and easy to follow\n* The technical details are presented well\n\nWeakness:\n* The novelty needs to be better justified\n* More ablation study may benefit understanding the proposed method\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BHee76RQa1", "reviewer": "Reviewer_z3gP", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "In this paper the authors propose the Composite Slice Transformer (CST) which consists of a composition of attentions applied to a stacked, slice representation of the input sequence at different scales, coupled with a multi-scale volatile instant positional embedding.\n\nTo do this, first the input sequence of length N is divided into N/L slices of size L. Then, local self-attention is performed within each slice of text, to obtain a local context vector for each input token. \nThese context vectors also go through a mean-pooling layer (one per slice) to obtain a vector that represents each slice. Then global self-attention is performed using the vectors outputted by the pooling layer. Finally, the final context vector that corresponds to each input token is obtained by summing the local context vector with the global context vector (broadcasted with the broadcast-add operation, to restore the sequence length).\n\nAs CST has two attention mechanisms with different granularities, it uses two positional embedding layers, one for the local attention and another for the global attention. These embeddings are only summed to the queries and keys, to prevent the accumulation of the positional information over the layers of the model.\n\nFor a fixed slice length L, CST has a complexity of O(NL + N^2/L^2) while the vanilla transformer has a complexity of O(N^2), where N is the input sequence length.\n\nThe authors perform experiments in three tasks: Long Range Arena, auto-regressive language modeling, and masked language modeling, and compare the results with a broad set of efficient transformers and the vanilla transformer.\n\nOn the Long Range Arena, CST leads to the best average score while being the fastest model and one of the efficient transformers that requires less GPU memory.\n\nOn auto-regressive language modeling, experiments on the Wikitext-103 with a sequence length of 256 show gains in perplexity when comparing with the Linear Transformer and the FMMformer while having 1.5x speed-up when compared to the vanilla transformer.\nFurther experiments, using a sequence length of 1024, show improvements over Reformer, Performer, and Scatterbrain.\n\nOn masked language modeling with input sequences of 128 tokens, CST leads to a lower perplexity and better GLUE average score than Nystromformer, Performer, Luna, and FNet.\n", "summary_of_the_review": "To sum up, I really liked reading this paper and found the model proposed very interesting and widely applicable (as shown by the wide set of experiments in which the model performs well).\n\nHowever, I found the experiment's setting to be a bit disappointing since the authors only considered small sequence lengths for the language modeling tasks.\n", "strength_and_weaknesses": "Strengths:\n- The model description (besides the extension ratio) is quite clear and well written.\n- The proposed way to combine the local and global attention is quite simple and intuitive.\n- The authors perform experiments on a wide set of tasks, which show the model’s advantages and wide applicability.\n\nWeaknesses:\n- Despite performing experiments on a wide set of tasks, the lengths of the inputs used for auto-regressive and masked language  are always quite small (256 and 1024 for autoregressive LM and 128 for MLM). As the complexity problems of the vanilla transformer are more problematic for long inputs, I do not understand why the authors chose these lengths for the experiments.\n- The autoregressive LM experiments are only performed on Wikitext-103. In my opinion the paper would benefit from having experiments on a dataset with more long-range dependencies, such as PG-19 (https://github.com/deepmind/pg19), using a bigger input length. This would allow the reader to understand how good the global attention mechanism is. \n- I also think that it would be interesting to have an experiment in which the computational requirements of CST equal the ones of the vanilla transformer (for example by having longer sequences for CST than for the vanilla transformer)  to understand the gains obtained while having the same computational requirements.\n- There is no reference to the S4 model (Efficiently Modeling Long Sequences with Structured State Spaces, Gu et al., CLR 2022), which according to the S4 paper results is far better than the CST on the Long Range Arena tasks.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1ByI2sqLvz2", "reviewer": "Reviewer_jNhA", "summary": "", "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": "", "summary_of_the_paper": "This paper proposed an effecient self-attention block for transformer structure. The proposed block first splits the input sequence into multiple local sequences. Then it first conducts self-attention on the local sequences and then aggregates local sequences and conducts self-attention on the aggregated sequences to achieve global attention. The proposed method is evaluated on multiple datasets and shows better performance than previous efficient transformer.", "summary_of_the_review": "I think the paper is well written and the proposed method has some new technical contributions. But I am not sure how significant these contributions are and I would like to see the response from the author.", "strength_and_weaknesses": "Strength\n1. The paper is well written and easy to follow.\n2. Although local+global attention has been used in previous works to reduce computational complexity, the author proposed a new form.\n3. The proposed method achieves better performance than previous efficient transformer.\n\nWeakness\n1. The proposed CSA is similar to previous axial attention [1,2], where they conduct self-attention sequentially along one dimension and then another. The difference may be that the proposed method also used attention abstraction and multi-scale position embedding. It would be better if the author could give some more detailed discussions about the difference from previous works.\n2. I am not sure I understand the multi-scale position embedding. First, I am not sure why it is called multi-scale, is it just because the length of local and global sequences are different? Second, how is this different from previous relative positional embedding? And there should be an ablation study to show its effect.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster