Toeplitz Neural Network for Sequence Modeling
Authors: Zhen Qin
Xiaodong Han
Weixuan Sun
Bowen He
Dong Li
Dongxu Li
Yuchao Dai
Lingpeng Kong
Yiran Zhong
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Toeplitz Matrix
Sequence Modeling
Relative position

Abstract: Sequence modeling has important applications in natural language processing and computer vision. Recently, the transformer-based models have shown strong performance on various sequence modeling tasks, which rely on attention to capture pairwise token relations, and position embedding to inject positional information. While showing good performance, the transformer models are inefficient to scale to long input sequences, mainly due to the quadratic space-time complexity of attention. To overcome this inefficiency, we propose to model sequences with a relative position encoded Toeplitz matrix and use a Toeplitz matrix-vector production trick to reduce the space-time complexity of the sequence modeling to log linear. A lightweight sub-network called relative position encoder is proposed to generate relative position coefficients with a fixed budget of parameters, enabling the proposed Toeplitz neural network to deal with varying sequence lengths. In addition, despite being trained on 512-token sequences, our model can extrapolate input sequence length up to 14K tokens in inference with consistent performance. Extensive experiments on autoregressive and bidirectional language modeling, image modeling, and the challenging Long-range Arena Benchmark show that our method achieves better performance than its competitors in most downstream tasks while being significantly faster.

Published as a conference paper at ICLR 2023
TOEPLITZ NEURAL NETWORK FOR SEQUENCE MODELING
"Zhen Qin "Xiaodong Han
Weixuan Sun
Bowen He
Dong Li
Dongxu Li
2 Yuchaoo Dai 'I Lingpeng Kong
Yiran Zhong*
1 Shanghai AI Laboratory
Time Research
Australian National University
4 NNrtthwestern Polytechnical University
'The University of Hong Kong
ABSTRACT
Sequence modeling has important applications natural language processing and computer vision. Recently, the transformer-based models have shown strong per- formance on various sequence modeling tasks, which rely on attention to capture pairwise token relations, and position embedding inject positional information. While showing good performance, the transformer models are inefficient to scale long input sequences, mainly due to the quadratic space-time complexity of attention. To overcome this inefficiency, we propose to model sequences with a relative position encoded Toeplitz matrix and use Toeplitz matrix-vector pro- duction trick to reduce the space-time complexity of the sequence modeling to log linear. A lightweight sub-network called relative position encoder is pro- posed to generate relative position coefficients with fixed budget of parame- ters, enabling the proposed Toeplitz neural network to deal with varying sequence lengths. In addition, despite being trained on 512-token sequences, our model can extrapolate input sequence length up to 14K tokens in inference with consis- tent performance. Extensive experiments autoregressive and bidirectional lan- guage modeling, image modeling, and the challenging Long-Range Arena bench- mark show that method achieves better performance than its competitors in most downstream tasks while being significantly faster. The code is available at https//gtthhbbcoo//oeeaNLLLLLL/L
INTRODUCTION
75
TNN
12
1talu
Syn(D)
GSS
Lnn--Range Arena Score
Performer
Syn(R)
TNN
70
10
65
Log PPL
Transformer-LS
Flash
cosFormer
Transformer
60
Reformer
Performer
Nystomm
50
Fnot
10000
12000 14000
Speed (steps per sec)
Inference length
Figure 1: The left figure shows the training speed (æ-axis), performances (y-axis), and GPU memory footprints (circle sizes) of the TNN and competing methods on Long-Range Arena benchmark. The TNN beats the competitors with clear margin. The right figure plots the extrapolation results with different sequence lengths, where the z-axis denotes sequence lengths, and the y-axis denotes log PPL. demonstrates that regardless of the sequence length, the PPL of the TNN remains constant.
Indicates the corresponding author. Email: zhongyi ran@gma com

---

Published as a conference paper at ICLR 2023
Sequence modeling is a fundamental problem in natural language processing. speech processing, and computer vision. Various sequence modeling methods have been proposed in the literature, including recurrent (Hochreiter & Schmidhuber 1997), convolutional architectures (LeCun et al. 1989), and transformers (Vaswani et 20.1) These models utilize various properties of sequential data for their modeling. For example, recurrent models (Hochreiter & Schmidhuber 1997) mimic the sequential property by sequentially processing the input while maintaining hidden states through steps. Convolutional models (LeCun al. 1989) enforce the locality bias sequentially and only in- teract elements within local patches. Transformers use attention matrices to model pairwise relations regardless of the distance between them. Recently, Transformers (Vaswani et al. 2017] Dosovitskiy et al. 2021) show strong performance on wide range of applications across domains and become arguably one of the most successful architectures for sequence modeling in general.
There are two main components in transformers: the attention mechanism that learns pairwise correlations of tokens from data, and the position embedding to introduce positional inductive bi- ases. The vanilla attention mechanism requires quadratic space-time complexity, which precludes Transformers from handling long sequences. Numerous attention variants have been proposed re- cently to reduce the complexity, including linear transformers (Katharopoulos al., 2020), and Performer (Choromanski et al. 2021). Although the types of attention vary, the position embedding remains in every method, which indicates the importance of position information in sequence mod- eling. This motivates us to ask the following question: since position information is important, can we design a model that relies entirely on the position information of its elements regardless of their content, thus alleviating the quadratic computation cost of the vanilla attention mechanism?
In this paper, we give an affirmative answer to this question by introducing Toeplitz neural network, a new efficient architecture that solely exploits relative position relations for sequence modeling, In specific, instead of attention matrices, the Toeplitz neural network uses Toeplitz matrices to capture relations between each token pair. There are two motivations for selecting the Toeplitz matrix. One is that it compactly represents relative positional relations between tokens with much fewer parameters, ie., 2n parameters for an x n. Toeplitz matrix. 'he other is that the Toeplitz matrix-vector production can be efficiently processed in On log n) complexity. which is exactly what we used in our token mixing operation. In this way, we avoid computing content similarities between tokens and effectively reduce the quadratic computation complexity of transformers to log linear, rendering more efficient sequence modeling architecture.
We further propose relative position encoder, a lightweight module that generates relative posi- tion parameters assemble the Toeplitz. matrices, that the number of the TNN's parameters will no longer depend on the sequence length. Moreover, it allows TNN to deal with varying se- quence lengths without retraining. In addition, the input sequence length extrapolation becomes an important ability in sequence modeling as training on longer sequences can be prohibitively expen- sive (Press et al. 2022). We propose an exponential decay bias that directly applies to the Toeplitz matrix. Our model achieves consistent performance to sequence length of 14K tokens in infer- ence when training on sequences of 512 tokens. We also show analytically that the Toeplitz neural network represents general form of sequence modeling methods, and derives transformers, CNNs, and the recently proposed State-space-
methods (Gu et al. 2022) as its special forms.
We validate our model on a wide range of sequence modeling tasks and benchmarks. These include auto-regressive language modeling, text classification, image classification, and the Long-Range Arena benchmark. As illustrated in Fig. D our model achieves -att-offthheart performance most tasks at a favorable log linear space-time complexity. also demonstrates superior extrapolation capabilities when training on shorter sequences and evaluating longer ones off-the-shelff
2 PRELIMINARY
In this section, introduce concepts used throughout the paper, including positional embedding, token and channel mixing, and the Toeplitz matrix. Notations used can be found in Appendix A
Positional embedding is introduced in transformers (Vaswani et al. 2017 to inject positional in- ductive bias. It often uses fixed or learned parameters to encode making the model position-aware. There are mainly two types of positional embeddings: the abso- lute positional embedding (Vaswani et al.] (017) and the relative position embedding (Shaw et al. 2018). In this work, we focus on the relative position embedding to emphasize pair-wise token
specifff information, thus
2

---

Published as a conference paper at ICLR 2023
relations. A typical relative positional embedding
Raffel et al. 2020) is formulated
Eij = q; / wi-j-
(I)
where j. i are two positional indices, Caj denotes the attention score before softmax. The qu kj represents the queries and keys the attention. The wi-; is positional coefficient. In this case, the relative position information is added to the attention
bias.
Token and channel mixing are used by (Yu et al. 2022 to refer to the two main procedures in sequence modeling. The token mixing refers to the process of mixing information between token pairs and the channel mixing for those between feature channels. In the Transformers, given the attention matrix A E _xxx" and token matrix X _axd the attention operation AX can be regarded as a token mixing process and the FFN module is used for channel mixing.
Researchers often classify various sequence modeling techniques based the token mixing tech- niques used. MLP-based methods (Liu et al. [021] Tolstikhin et al. (202]) use matrix multiplication on the sequence dimension for token mixing. FFT-based methods (Lee-Thorp al. 2022) utilize the FFT on the sequence dimension to mix token-wise information. The State-space space-based meth- ods (Gu et al. 2022) leverage the state equations and hidden states model sequences, as well as perform interactions between tokens.
Toeplitz matrix special form of matrix that has constant values along each diagonal running from left to right, i.e.
Ts T-+1--1 t4-5 T T R"X"
There two nice properties of a Toeplitz matrix: 1). For an nxn Toeplitz matrix, efficiently describe it with 2n 1 parameters. 2). The Toeplitz vecrox-vector production faster than standard vecrox production. In particular, have:
Theorem 2.1. For a Toeplitz matrix T R"x* and any vector x E IR",, the time complexity of Tx On l)..
We provide detailed proof in Appendix This property enables us to use the Toeplitz matrices to perform efficient token mixing.
3 TOEPLITZ NEURAL NETWORK
In this section, we provide a detailed design and analysis of our proposed Toeplitz Neural Network (TNN) by giving glance at the overall structure of our model first and then describing each of its components. We also discuss the connection between the TNN and other sequence modeling methods the end of this section.
3.1 THE OVERALL ARCHITECTURE
Our model consists of stack of Gated Toeplitz Units (GTU) and GLU (hazeer 2020). GTU is a modified GLU layer injected with the proposed Toeplitz Neural Operator (TNO), as illustrated in Fig. 2 A TNO is used to perform token mixing with Toeplitz matrix. To generate relative position coefficients for the Toeplitz. matrix, we propose a Relative Position Encoder (RPF), a lightweight fully-connected sub-network encode the relative position information. An exponential decay bias is also added to the Toeplitz matrix to enable extrapolation on longer inputs.
3.2 TOEPLITZ NEURAL OPERATOR
Here, we will show how to use a Toeplitz matrix to represent relative positional information. Let us consider i, to be positions in ID sequence, by using the relative position embedding in Eq. we can define a Toeplitz matrix T E Ra*n, where Tú = tz Specifically, given a sequence x of n tokens, x [oo Li...., 2,-1, E R", we use a scalar f. to represent the relative position coefficients between 2; and xz. Then Toeplitz matrix T R can be formed by gathering 4--3
3

---

Published as a conference paper at ICLR 2023
2n-1
Output Embeddiiggs
Ouiput
X
TNN
TNO
RPE
Toeplitz matrices
Linear
GLU
Norm
GTU
Linear
Lincar
N
TNO
K x
Norm
RPE
Linear
Linear
Linear
2n-1
Input Embeddings
Input
26-1
Figure 2: Network structure overview of the proposed Toeplitz Neural Network. The proposed sequence modeling block is composed of Gated Toeplitz Unit and GLU [Shazeer (2020) and. We propose the TNO to perform token mixing with only relative position information. We use a small fully-connected network named RPE encode relative position information.
for every token pair:
L-1
L-+t1
f
to
T
E RRxX
(3)
to
t-1
fn-1
t1
to
Let us define token mixing operation as:
Tx TR."" where y is the token mixing result. For any d-dimensional sequences, the token mixing is performed on each dimension individually.
(4)
As aforementioned in Theorem 2.1 the computation complexity of Eq, Dis O(n log n). As we need perform token mixing on d dimensions, our TNO has computation complexity of O(nd n). One following question is how to calculate the relative position coefficients in T. A naive solution to make the coefficients learnable parameters, such that the model can directly learn them from training data. However, this solution has some drawbacks: 1). Parameter explosion. For d- dimensional sequence of n tokens, there are a total (2n 1)d learnable parameters, which can be prohibitively large
increases. It also shows unsatisfactory performance in our ablation studies in Sec. [4.3, 2). Fixed input sequence length. Since the sequence length n is fixed training, are unable to adjust the sequence length during inference, i.e., it will cause crucial performance drop when the sequence length changes. To address these drawbacks, we propose a relative position encoder generate the relative position coefficients.
3.3 RELATIVE POSITION ENCODER
We illustrate the network structure of our RPE in Fig. 2 which is fully connected network with K layers. The input of the network is a I-dimensional scalar, i.e., the value of -(n - I),..., . (n 1), Vn E N+, and output a dimension vector, which is used assemble the Toeplitz matrix. In this case, the number of the TNN's parameters will no longer depend on the input sequence length and the TNN will have the flexibility to deal with various sequence lengths in the inference stage.
Note that recent literature Mildenhall et al. 2021) claims that projecting the scalar input to a higher dimensional space with high frequency functions, iee., sin and cos functions, before passing net- work can lead to better performance. However, our ablations, we find that using the original integer achieves better performance.
Exponential decay bias Previous models (Vaswani et al. 2017 Qin et al. 2022) often use a fixed sequence length in both training and inference. If we need infer longer sequence, the model
4

---

Published as a conference paper at ICLR 2023
needs to be retrained the longer sequence length to maintain the performance, which can be prohibitively expensive the application.
ALiBi (Press et al. 2022) shows that by applying a simple penalty to the query-key attention scores, the Transformer can handle longer sequence length in inference without compromising the perfor- mance. The penalty is linear bias that is proportional to the distance between tokens. Inspired by this technique, we propose an exponential decay bias that directly applies to the Toeplitz matrix achieve the same goal. In specific, let us define decay rate of [0, 1], and the new relative position coefficients f in T can be expressed as:
(5)
ALiBi can be seen as special case of our method. Given the equation ALiBi:
Sig q k2kkv mli - -il exp(6ij) expla k,/v exp(mli jl),
(6)
and
Sij q. /
X - exp(m))
we have:
exp(5,)) = exp(st))A
It means the ALiBi applies exponential decay the softmax attention matrices whereas applies it on the Toeplitz matrices.
3.4 RELATION TO OTHER SEQUENCE MODELING MODELS
In this section, we will show the relationship between our model and other sequence modeling models such as the Transformers (Vaswani et al. (017). CNNs (LeCun et al. 1989), and the State space (Gu al., 2022). We also compare the theoretical space-time complexity of our model with previous sequence modeling models in Table.
Transformers A Transformer with relative position embedding can be expressed as:
O = Softmax(QK" /vá T)V.
Comparing it with Eq. the TNN can be regarded as an attention -fre transformer, i.e., removing the Q, K, and the Softmax, while only keeping the relative position matrices T.
CNNs convolutional layer can be viewed as Toeplitz matrix of special structure. Considering 1D convolution:
y h Eh. h RR "ET, E Rutm-1
(10)
Let's define a Toeplitz matrix T E [
Ts { hi-s O m 1,00- s 2
(11)
others,
0m-1
Then:
T= E p=+m-1
(12)
Therefore, a CNN can be viewed as special case of the TNN with a zero-padded input. For better illustration, we provide matrix form of CNN operation in Appendix C.I
State space The equation of the State space can expressed as:
u, Au;11 1 Bx; y; Cu,, A hx B hx1 C Rxx 1x 1,
(13)
where x; is the input, y; is the output,u; is the intermediate state. According to (Gu et al. the output of the State space is:
2022
y1 Σ ki-jaj,- k (CB, CAB,..,, CA E R".
(14)

---

Published as a conference paper at ICLR 2023
Let's define the Toeplitz matrix T E R
ki-ji 1 Ti-; 0, 0
(15)
Then:
= T
(16)
In this case, the State space can be regarded special form of TNN with the coefficients that
are calculated by the State space. We also provide the matrix form in Appendix C.2 for better illustration.
Table 1: Comparison of theoretical space-time complexity of several models. Parallel indicates whether parallel training is possible, indicates the sequence length, and d indicates the feature dimension, e indicates the CNN kernel size. Here we only list about ID CNN.
Vanilla Attention
Linear Attention
State
Method
CNN
RNN
MLP
FFT
TNN
space
Time
ned
nd
nd'd
nd?
n²d
nd nd logn ndd log
complexity
Space nd
nd
n2d nd
ndd
nd nd nd
complexity
Parallel
True False True True True True True True
4 EXPERIMENT
We compare method four kinds of sequential modeling methods including iitention-based methods, MLP-based methods, FFT-based methods, and State-space-based methods. In particular, select the following methods:
Attention-based: Vanilla transformer(Vaseee Vaswani et al. 2017). Transformer-LSS2Zm et al.,
2021 FLASH. (Hua al., 2022). 1+elu (Katharopoulos et 2020). Performer (Choro- manski et al.) (020). cosFormer (Qin et al. (002)..
MI.P-based: gMLP(Liu et al. 2021). Synthesizer (Random), Synthesizer (Dense) Tay
et al. 2021).
FFT-based: LeetLee-Thhrp et al. 2022), GFNet (Rao et al. 2021}.
2021), ), AFNO et al,
State-space-based S4(Gu et
2022). DSS Gupta al.
2022 GSS al. 2022
We evaluate methods the WikiText-103 (Merity et al. modeling and the input length extrapolation ability, and the GLUE benchmark (Wang et al. 2018)
2017) for autoregressive language
for bidirectional language modeling. We also validate the accuracy and efficiency of our methods in handling long-range dependencies on the Long-Range Arena benchmark (Tay et al.) 2020). To
demonstrate the robustness of model, we implement model in DeiT (Touvron et al.) 2021)
structure and compare its performance with the vanilla DeiT (Touvron et al. 2021) on the ImageNet- IK (Deng al., 2009) for image classification.
4.1 SETTING
We implement our models in Pytorch (Paszke et al.) (0199) and train them on 8 V100 GPUs. We adopt the same training configuration for all competitors, including batch size, learning rate, training epochs/updates, eíc. More detailed hyper-parameters are listed in Appendix D
For the autoregressive language modeling, all models are trained on the WikiText- 103 dataset (Mer- ity et al.) 2017) for 50K steps with a learning rate of 0.005. We use perplexity (PPL) the evaluation metric.
For the bidirectional language modeling, choose the Roberta (Liu et al. 2019) model as the base model structure for all methods. All models are pre-trained on the Wixi 103 (Merity et al.) 2017) for 50K steps with Ir=0.005 and fine-tuned on the GLUE dataset (Wang et al. 2018). We use different learning rates among 1e-5, 3e-5, 6e-5, le-4 and choose the best result after fine-tuning for 3 epochs.

---

Published as a conference paper at ICLR 2023
For the Long-Range Range Arena benchmark, adopt the same experimental configurations from the Skyformer Chen et al. (021). We ensure that performances and efficiencies all methods are obtained with similar parameter size and the same training hyperparameters.
For the image classification on the ImageNet- Ik dataset, we adopt the Deit (Touvron et al. 2021 network structure and replace the transformer layers with our model.
4.2 RESULTS
Autoregressive language modeling Autoregressive language modeling a crucial task that requires the models to estimate causal probability distribution given the previously seen tokens. In Table we compare the proposed TNN with competing sequence modeling models. First, compared to existing Mip-based methods, TNN shows better performances with a clear margin both val set and test set. Transformer-based methods are currently dominant sequence modeling methods. As strong baseline, Transformer adopts standard self-attention module with quadratic complexity, TNN still outperforms it on both val and test sets. in addition, TNN achieves better results than most efficient transformers including FLASH, 1+elu, Performer, and cosFormer. Finally, compared with recent emerging State-space-base based sequence modeling methods, TNN achieves superior per- formance all competing methods. it proves the effectiveness of method in causal models.
Further, we also compared the extrapolation ca- pabilities of each method. In Figure [ we show that our method outperforms all other methods and is comparable ALiBi (Press al. (022). Complete results can be found in Appendix 15
Table 2: Performances comparison of autore- gressive language modeling on the Wikitext- 103 dataset. The best result is highlighted and the second in underline. 4 means lower is bet- ter. Attn stands for Attention, Ss stands for State space, Trans stands for Transformer, LS stands for Transformer-LS.
bold
Bidirectional language modeling We bench- mark bidirectional modeling methods on the TNN achieves
GLUE datasets in Table. competitive results across all tasks. Further, worth noting that TNN boosts the results of CoLA by significant margin, showing the ability of reasoning logistic information from sequences. It demonstrates the effectiveness of TNN in bidirectional language modeling.
PPL (val)
PPL (test)
Params (m)
Method
Aftn-based
Trans
24.40
24.78
44.65
LS
23.56
24.05
47.89
FLASH
25.92
26.70
42.17
Itelu
27.44
28.05
44.65
Performer
62.50
63.16
44.65
Long-Range Arena benchmark As shown in Table 4 we compare TNN with competing methods across five tasks of the LRA bench-
cosFormer
26.53
27.06
44.65
MLP-based
Syn(D)
31.31
32,43
46.75
mark. The results before the Transformer-L.5 are taken from Skyformer (Chen al., (021). As demonstrated. TNN achieves the best scores on three tasks and the second places on the left two tasks. In terms of overall results, TNN out- performs all other competing methods includ-
Syn(R)
33.68
34.78
44.65
gMLP
28.08
29.13
47.83
Ss-hased
S4
38.34
39.66
45,69
DSS
39.39
41.07
45.73
GSS
29.61
30.74
43.84
ing S4 (Gu al. 2022
Our
TNN
23.98
24.67
48.68
For speed comparison, we compare training speed of the TNN with other methods in Table 5 For fair and comprehensive comparison, we follow exactly the same configurations the Skyformer Chen et al. (202I) and report step per second under different sequence lengths. Timing is conducted on an Nvidia A6000 GPU with 48G GPU memory.
Image modeling We report classification results the ImageNet- 1k dataset in Table 6 As shown, under similar parameter sizes, TNN achieves better results than Deit- Deit-Tiny and comparable results with Deit-Small. It demonstrates the capability of method in encoding visual signals.
We re-run the S4 experiments with the new configuration match the number of parameters. For the sake of completeness, we also compare TNN with $4 in the original size of S4 using the suffix "-Large" in Table14] which validates ability to encode long sequences.

---

Published as a conference paper at ICLR 2023
Table 3: Performances comparison of bidirectional sequence modeling on the GLUE bench- mark. MNLI is reported by the match/mismatch splits. MRPC is reported by Fl score. CoLA is reported by Matthews correlation coefficient. All the other tasks are measured by accuracy. The best result is highlighted in bold and the second in underline. The larger the better for all metrics. "_" means unconverted. Attn stands for Attention, Ss stands for State space, Trans stands for Trans- former, LS stands for Transformer-LSS
Method
MNLI
QNLI
QQP
SST-2
MRPC
CoLA
AVG
Params(m)
Attn-based
Trans
79.37/79.07
87.79
88.04
90.25
88,35
38,63
78.79
124.70 70
LS
77.01/76.78
84.86
86.85
90.25
82.65
40.65
77.01
128.28
FLASH
79.45/80.08
87.10
88.83
90.71
82.50
29.40
76.87
127.12
1+clu
74.87/75.37
82.59
86.90
87.27
83.03
70.00
124.70
Performer
58.85159.52
63.44
79.10
81.42
82.11
19,41
63.41
124.70
cosFormer
75.10/75.95
82.61
86.12
89.45
81.93
33.03
74.88
124.70
MLP-based
Syn(D)
50.93/51.02
62.80
81.33
82.34
81.79
58.60
131.00
Syn(R)
52.82/52.13
62.29
78.11
82.22
81.38
4.63
59.08
129.42
gMLP
73.30/73.60
80.56
86.48
90,25
82.30
36.06
74.65
131.08
FFT-based
FNet
62.45/64.71
73.31
79.43
81,88
82,91
63.53
124.70
GFNet
66.75/67.45
65.42
80,25
84.40
82.44
9.62
65. 19
130.06
AFNO
68.79/69.28
73.20
85.12
88.88
82.35
36.19
71.97
121.57
Ss-based
68.45/68.42
72.14
84.61
87.04
83.36
23.01
69.58
131.79
DSS
35.46/35.22
50.80
65.18
65.37
80.95
6.14
48.45
123.76
GSS 50.53/51.58
62.58
80.98
85.67
82.11
6.56
60.00
122.80
Ours
TNN
76.72/76.06
85.06
88.30
90.60
82.96
49.85
78.51
126.40
Table 4: Performances Comparison the Long Range Arena benchmark. We bold and underline to highlight the best and the second result of each task respectively. The proposed TNN achieves the best performances and outperforms all competing methods.
Model
Text
ListOps
Retrieval
Pathfinder
Image
AVG.
Transformer
61.95
38.37
80.69
65.26
40.57
57.37
Kernelized Attention
60.22
38.78
81.77
70.73
41.29
58.56
Nystromformer
64.83
38.51
80.52
69.48
41.30
58.93
Linformer
58.93
37.45
78.19
60.93
37.96
54.69
Informer
62.64
32.53
77.57
57.83
38.10
$3.73
Performer
64.19
38.02
80.04
66.30
41.43
58.00
Reformer
62.93
37.68
78.99
66.49
48.87
58.99
BigBird
63.86
39.25
80.28
68.72
43.16
59.05
Skyformer
64.70
38.69
82.06
70.73
40.77
59.39
LS
66.62
40.30
81.68
69.98
47,60
61.24
cosFormer
67.70
36.50
83.15
71.96
51.23
62.11
FLASH
64.10
38.70
86.10
70.25
47,40
61.31
$4
85.92
50.60
67.30
72.44
78.07
70.87
TNN
86.39
47.33
89.40
73.89
77.84
74.97
4.3
ABLATION STUDY
Network structure configuration We ablate different structure configurations on the autoregressive language modeling task in Table 7 We consider three options configuration: the GTU+GLUU GTU only, and attention+GLU, We empirically find that the GTU+GLU one achieves better perfor- mance than other options and choose it as our structure in TNN.
Input of relative position encoder In Table 8 we ablate different RPE inputs language mod- eling. (-(n-1)...., (n-))) denotes that we feed 2n - constants into the RPE. (-1n-1)..... (n-))))) de- notes normalized constants. The sin. denotes the absolute position embedding method used in (Vaswani et al. 2017). We empirically find that using the original integers as the input for the RPE leads to better performance.
8

---

Published as a conference paper at ICLR 2023
Relative position encoder There are two ways generate relative position coefficients for the Toeplitz matrix. One is to set these coefficients as learnalee parameters and allow TNN to learn them from data. The other is compare these two strategies in Table The TNN with our RPE network achieves an improvement of 2.47 PPL in language modeling.
proposed RPE network generate these coefficients. We
Table 5: Speed comparison on Long-Range Arena benchmark. We mark it with dash if method ex- hausts GPU memory. The higher the better for met-
Table 7: Performances comparison
with different structure configurations. GTU+GLU achieves better performance in language modeling.
rics. The 1K. represent the input sequence length.
Steed(steps per scc)
Method
(P[(val)
model
1K
2K
3K
4K
5K
GTU+GLU
23.98
Transformer
15.34
3.05
GTU only
25.19
FLASH
20.49
11.06
8.47
7.23
6.93
Attention+GLU
27.40
LS
15.43
8.68
6.28
5.24
4.76
Performer
28.41
16.23
12.02
10.04
9.06
cosFormer
22.94
12.82
9.19
7.79
7.14
Table 8: Results comparison with differ-
Linformer
27.17
15.63
11.26
8.77
7.42
RPE inputs.
Reformer
20.16
10.87
7.46
5.69
4.70
Nystorm
14.12
9.62
7.46
6.11
5.26
Method
(PI,(vl)
State space
25.99
14.88
8.35
6.66
5.40
(n-II)....(n-I)
23.98
FNet
24.61
14.37
9.18
8.39
7.44
(-(n-I)....(nII))) (n-))//
24.11
TNN
25.72
15.35
9.90
8.07
7.00
sin, COS
24.04
Table 6: Performances comparison of image classifi-
Table 9: Performances comparison of
cation on the ImageNet-1k dataset.
TNN with and without RPE. RPE brings an improvement in language modeling.
DeiT-Tiny
DmillSmall
Model
Acc
Param
Acc
Param
Method
PPL(val)
Transformer
72.20
5.7M
79.90
22.0M
TNN
23.98
TNN
72.29
6.4M
79.20
23.4M
TNN w/o RPE
26.45
Exponential decay rate We ablate different ex- ponential decay rates in Table [0] on the lan- guage modeling. We train these model variants with fixed sequence length of 512 and test them on series of sequence lengths from 512 14336 and compute the average PPL. When there is no exponential decay, the model fails to extrapolate to longer sequence length. We also test our model with a learnable decay rate, but does not show better performance. We empirically select 0.99 the exponential decay rate in our method.
Table 10: Ablation of exponential decay rates in input length extrapolation. The model vari- ants are trained on a fixed sequence length 512 and tested on series of sequence lengths ranging from 512 to 14336. We compute the average PPL for all sequence lengths.
PPL
Avg PPL (extrapolation)
Decay rate
(val)
0.99 (ours)
23.98
23.70
0.90
25.28
25.22
0.95
24.56
24.63
0.999
23,98
24.56
(no decay)
24.03
672.72
learnable
27.65
24.39
CONCLUSION
In this paper, we propose Toeplitz neural network, a new efficient architecture that relies entirely on relative positional information for sequence modeling. The proposed model enjoys a favorable log linear space-time complexity. Thanks to the proposed relative position encoder and exponential decay techniques, Toeplitz neural network generalizes to long sequences with a fixed budget of pa- rameters while obtaining consistently superior performance than competing methods across multiple challenging tasks, including language modeling, image modeling. and sequence modeling on long inputs, iee. the Long- Range Arena benchmark. Toeplitz neural network is also generic sequence modeling approach, which renders various popular architectures, such as Transformers, CNNs, and State-space-bant -aaed methods, as its special forms, offering unified view for sequence modeling.

---

Published as a conference paper at ICLR 2023
REFERENCES
Ronald Newbold Bracewell and Ronald N Bracewell. The Fourier transform and its applications, volume 31999. McGraw-hill New York, 1986.
Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian kernel and nyström method. In Advances Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, 2021.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv: 14794, 2020.
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J Colwell, and Adrian Weller. Rethinking attention with per- formers. In International Conference Learning Representations, 2021. URL https: 7/open ew. net./ for.m/orrmmmm/m d= 6WRR
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248 255. leee, 2009.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recogni- tion at scale. In International Conference on Learning Representations, 2021. URL https: //openeviiew wwwts//ooumiidiiiieoee.o
Robert M Gray al. Toeplitz and circulant matrices: A review. Foundations and Trends@ in Communications and Information Theory, 2(3):155-23) 2399, 2006.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In The International Conference on Learning Representations (ICLR), 2022.
John Guibas, Morteza Mardani, Zongyi Li, Andrew Tao, Anima Anandkumar, and Bryan Catanzaro. Efficient token mixing for transformers via adaptive fourier neural operators. In International Conference on Learning Representations, 2021.
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are effective as structured state spaces, 2022.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Weizhe Hua, Zihang Dai, Hanxiao Liu, and Quoe V Le. Transformer quality in linear time. arXiv preprint arXiv:2202.10444 10447, 2022.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In International Conference on Ma- chine Learning, pp. 5156-5165. PMLR, 2020.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard Howard, Wayne Hub- bard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, (()):411555) 1989.
James Lee-Thorg Joshua Ainslie, Ilya Eckstein, and Santiago Ontanon. FNet: Mixing tokens with Fourier transforms. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 4296-4313, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 18.15vv//v1/ 2022.naade mann- URL htl.ttts::// h http::::/ol/aaaaaahoooloo/o///// wtwpolooo.org//22222 naacl ma n. 319
10

---

Published as a conference paper at ICLR 2023
Hanxiao Liu, Zihang Dai, David So, and Quoe V Le. Pay attention mlps. Advances in Neural Information Processing Systems, 34:9204- 9215, 2021.
Yinhan Liu, Myle Ou, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint
2019.
Harsh Mehta, Ankit Gupta, Ashok Cutkosky, and Behnam Neyshabur. Long range language model- ing via gated state spaces. arXiv preprint 1.XXi:2206.1394477 2022.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. 5th International Conference on Learning Representations, ICLR, Toulon, France, 2017.
Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng. Nerf: Representing scenes as neural radiance fields for view synthesis. Communications of the ACM, 65(1):99-106, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lever, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations, 2022. URL
httpp:://openrewe ew net wttp:/ewwwweee/rreeeeeeeeeee woorummid=R8ssa
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 Confer- ence on Learning Representations, 2022. URL B18C0rx2Up4
www.eeiiwwww..... ew net./ fo forum? id=
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, al. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., 21((40):1-67 2020.
Yongming Rao, Wenliang Zhao, Zheng Zhu, Jiwen Lu, and Jie Zhou. Global filter networks for image classification. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representa- tions. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lunguage Technologies, Volume 2 (Short Pupers), pp- 464-468, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18653/v
11118655/1///18-/11 1//18-211744 URL h wwwpo//ooo..rr/////77740
Noam Shazeer. Glu variants improve transformer. arXiv preprint arXiv:2002.05202 2020.
Yi Tay, Mostafa Dehghani. Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sehastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2020.
Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Re- thinking self-attention for transformer models. In International conference on machine learning, pp. 10183-10192. PMLR, 2021.
llya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et Mlp-mixer: An all-mlp architecture for vision. Advances in Neural Information Processing Systems, 34:24261- 24272, 2021.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve Jegou. Training data-efficient image transformers &amp; distillation through attention. In International Conference on Machine Learning, volume 139, pp. 10347-10357. July 2021.

---

Published as a conference paper at ICLR 2023
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 informa- tion processing systems, 30, 2017.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman, Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353-355, 2018.
Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng, and Shuicheng Yan. Metaformer actually what you need for vision. In Proceedings the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 10819-10829, 2022.
Chen Zhu, Wei Ping. Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandkumar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL //ttpse//openrevee net http://wwwwett/totm1111ee1. 1kFOwVdYc
12

---

Published as a conference paper at ICLR 2023
Appendix
A
MATHEMATICAL NOTATIONS
Notation
Meaning
Hidden state. Query, key, value. Attention output. Feature dimension. s-th row of matrix M. All-ones vector with dimension d. Identity matrix with dimension d.
Q K
V
O
m
1,
La
Table 11: Mathematical notations used in the paper.
B PROOF OF THEOREM
In this section, will prove Theorem 2.1 matrix and Toeplitz matrix:
Before doing that, let's first introduce the circulant
Definition B.1. matrix C RRxn is circulant matrix if and only if Ciy = c(s-s+n) mod i.e.,
co
Cp-1
Cn-2
C1
Co
On 1
C
C2
C1
E Ruxn
(17)
".
Cn
Gn-2
Cu-1
Cn-1
C2
C1
Co
Definition B.2. matrix T _x is Toeplitz matrix if and only if ti-j i...
to
t-
1_2
n+
t
to
t-
l/
11
T
E Ruxn
(18)
t-1
In-2
11
lp
1-1
fn-1
t2
t
to
Based on the definition, we can give a key lemma:
Lemma B.3. circulant matrix C Raxn is orthogonally equivalent the diagonal matrix A, in particular, the orthogonal matrix F is a n x n. DFT matrix:
F FTAF,
2 sti
(19)
= diag a1, an- [] E Raxa F.r = exp
-1
n
The proof can be found in GGry et al. 2006). Based on this, we can prove a key lemma: Lemma B.4. can be done in O log n) time.
vector x R. and circulant matrix C RRaxn, matrix multiplication Cx
Proof of Lemma B Because F, is a DFT matrix, so Fx and F x can be done O log time (Bracewell & Bracewell 1986). Since A is diagonal matrix, Ax be done in O(n) time,
13

---

Published as a conference paper at ICLR 2023
note that its diagonal elements F Flav, 01,...,an-1. can also be computed in O l) time com- plexity, therefore,
=x= =F Fxx= (A(Fx)),
(20)
can be done in O(n nog..
Based on this, we can prove Theorem 2.1
Proof of Theorem 2.1 We first fill the Toeplitz matrix T E I into a circulant matrix C 12anx2n;
E
tu: 0 < k S n
to, k = n
(21)
2n- ni +
2n -1
i.e,
lo
10
l-
12
t
to
l-++1
t
t2
to
t-1
t-2
n-
C
t--1
t
to
t-1
1-2
to
E 22x2n
to
t
to
1-1
t-
t-++1
t2
t
to
l/
t-2
t--1
:
to
t-1
f-1
t-2
to
fn-1
to
(22)
Using the notation of block matrix, we can define:
C
C2
C
r
2nx2n
C2 x = 1,2,3,4, C₁ = TT
(23)
C3
C4
For the vector x E RR., let's define:
X1
On
E 22
(24)
C
C2
Cix
Tx C3x
Cx1
E 2R
(25)
C3
C
O
C3x
therefore:
Tx
I
O
Cx₃
[
Onxn]
= Tx.
(26)
C3x
Note that:
Computing Cx, has time complexity of O(2n log(2)) lognn...
In Onxn ] Cxx is equivalent selecting the first rows of Cx₁, the time complexity
is O(n).
So the total time complexity is O(n log
C MATRIX FORM OF SEQUENTIAL MODELS
In this section, we give the matrix form of some sequence models mentioned in section 3.4
14

---

Published as a conference paper at ICLR 2023
C.I
CNN
The matrix form of CNN mentioned in Eq.
10 is:
ho
h1
ho
h2
h1
Yo
hg
ho
X0
Y1
XI
Y2
m
h
ho
X2
E -p+m--1
(27)
h
hm-
h
Yn+m-1
hm-1
hm-3
Xp-1
hm-2
hm-3
hm-1
hm-2
h
C.2
STATE SPACE
The Toeplitz matrix mentioned in Eq. 15 is:
Kg
k1
ko
K2
k1
T
R
(28)
k1
kg
k
k2
kj
ko
D CONFIGURATIONS
Table 12: Detailed training configurations used in our experiments. "Total batch size" means
batch.per-gpa update num npus. "ALM" stands for Autoregressive Language Model. "BLM" stands for Bidirectional Language Model. "IM" stands for Image Modeling.
AML
BLM
IM
Data
WikiText-103
Wiki 103
ImageNet-Ik
Tokenizer method Sre Vocab size Sequence length
BPE
BPE
50265
50265
512
512
Total batch size
128
512
2048
Number of updates/epochs
50k updates 4k steps
50k updates
300 epochs
Warmup steps/epochs
3k steps
5 epochs
Peak learning rate
5e-4
5c-4
2.5e-4
Leamingg scheduler
Inverse sqrt Adam
Polynomial decay Adam
cosine
Optimizer
Adamw
Adam
le-8
le-6
le-8
Adam (31, 32))
(0.9, 0.98)
(0.9. 0.98)
(0.9, 0.98)
0.2 for TNN,
0.2 for TNN,
Weight decay
0.1
0.1 for others
0.1 for others
Gradient clipping
1.0
15

---

Published as a conference paper at ICLR 2023
Table 13: Detailed model configurations used in our experiments.
Model
LM
Roberta
Deit-tiny
Deit-small
TNN
Layer
6
12
12
12
Feature dim
512
768
192
384
GTU
GTU dim
1536
2304
576 SiLU
1152
GTU act
SiLU
SiLU
SiLU
GLU
GLU dim
512
768
192
384
GLU act
SiLU
SiLU
SiLU
SiLU
RPE
RPE layer
RPE dim
64
64
48
48
RPE act
ReLU
ReLU
ReLU
ReLU
Exponential
0.99
0.99
0.95
0.9
decay bias
Table 14: Performances Comparison the Long Range Arena benchmark. We bold and underline to highlight the best and the second result of each task respectively. The proposed TNN achieves the best performances and outperforms all competing methods.
Model
Text
ListOps
Retrieval
Pathfinder
Path-X
Image
AVG.
S4-Large
86.82
59.60
90.90
94.20
96.35
88.65
86.09
TNN-Large
87.90
61.04
90.97
93.00
96.10
88.24
86.21
E EXPERIMENTS
F EXTRAPOLATION
G
VISUALIZATION
In this section, we visualize Tnn, in particular, choose the Toeplitz matrix used in Roberta for visualization.
16

---

Published as a conference paper at ICLR 2023
Figure 3: Visualization of the Toeplitz matrix used by each layer in Roberta, each element of the matrix represents the interaction between tokens. The Toeplitz matrices show similar behaviors conventional transformer attention matrices where the diagonal concentrates the most attention.
(i) Layer 1.
(ii) Layer 2.
i Layer
0315
632
(iv) Layer 4.
(v) Layer 5.
(vi) Layer
10000
0005
5006
628
(vii) Layer 7.
(vii)) Layer
(ix) Layer 9.
05.0
8.0
1410
0415
088
(x) Layer 10.
(xi) Layer 11.
(xii) Layer 12.
-0203
6000
-10
0022
-000
17

---

Published as a conference paper at ICLR 2023
TNN
PPL.1
24.67
24.25
24.05
23.91
23.83
23.79
23.73
23,63
23.58
23.54
23.53
23.51
23.51
23.49
23.48
23.48
23.48
23.47
23,46
23.70
Table 15: The extrapolation performance each method. The best result highlighted in bold and the second in underline. J. means lower is better.
ALiBi
PPL.
24.15
23.38
22.98
22.74
22.57
22.52
22.43
22.24
22.17
22.11
22.08
22.07
22.05
22.03
22.02
22.00
22.00
22.00
21.99
22.40
GSS
PPL.
39.66
39.76
40.82
41.04
41.08
41.53
44.08
48.27
53.32
57.73
60.25
63.36
74.92
81.87
87.67
92.11
96.00
101.47
60.26
39.90
DSS
PPL.
41.07
40.50
40.22
40.03
39.94
39.85
39.79
39.64
39.59
39.54
39.51
39.49
39.49
39.46
39.45
39.46
39.44
39.43
39.43
39.75
PPL1
30.74
30.41
30.24
30.15
30.08
30.04
30.00
29.91
29.88
29.85
29.83
29.82
29.82
29.80
29.79
29.79
29.79
29.78
29.78
29.97
S4
8.93E+12
1.58E+15
4.96E+16
5.67E+17
3.59E+18
2.19E+20
1.61
5.08E+21
1.16E+22
1.98E422
2.78E+22
3.93E+22
4.93E+22
5.70E+22
7. 7.18E+22
8.04E+22
9.41E+22
2.41E+22
gMLP PPL.
1.34E+9
29.13
Syn(R)
PPL.
34.78
107.36
184.57
250.57
302.48
48
345.80
390.13
515.35
589.30
661, 11.449
716.61
739.98
775.63
799. 67.67
802.38
810.71
837.11
844.62
861.72
556.33
Syn(D)
PPL1
32.43
101.6
169.45 48
224.44
265.4 465.44
298.55
322.86 86
399.63
454.85
495.7
527.2
551.69
565.78
576.15
588.74
598.33 33
610.25
618.42
627.03
422.56
cosFormer PPL.
102.88
175.26
267.65
368.02
820.77
1335.51
1735.50
2146.19
2494.79 79
2902.24
3028.72 72
3247.83
3341.91 91
3644.8 81
1851.70
3951.26
1764.75
27 76
32 90
55.28
Performer
PPL.
159.74
504.30
1020.28
1568.83
2138.50 50
2693.89 3.9
4945.82
7170.91
8443.15
10234.07
11420.56
12557.09
14847.6 66
13623.83
14661.71 77
17959.8 85
20026.35 35
20971.31
8684.79
63.16
1+elu
PPL.
47.35
70.47
91. 91.88
111.56
129.92
147.09
206.88 88
267.88 87
299.31
352.62
389.02
411.50
453.27
457.06
504.19
555.38
584.01
589 83
299 86
28
FLASH
16950.45
174165.47
346502.89
647788.11 12
1719873.5
6.25E+6
4.17E+10
2.67E+13
1.26E+15
1.58E+16
8.11E+16
3.40++17
1,22E+18
4.03E+18
1.07E+19
2.52E+19
4,96E+19
1,28E+20
1.16E+19
PPL
24.69
LS
PPL.
24.05
23.49 33.49
23.21
23.07
22.97
22.97
22.99
23.25
23.83
24.56
25.45
26.42
27.11
28.78
30.13
31.14
33.21
34.72
36.05
26.71
Transfomner
PPL.
24.78 78
41.36
62.35
82.52
100.17
118.42
133.44
188.95
246.06
270.93
311.65
346.58
372.18
387.29
395.94 94
426.54
463.50
506.35
486.86
261.36
Seqlen
512
768
1024
1280
1536
1792
2048
3072
4096
5120
6144
7168
8192
9216
10240
11264
12288
13312
14336
Avg
18


Reviews:
[{"review_id": "g_2fOjbuCB", "reviewer": "Reviewer_k2X2", "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": "The paper proposes a new token mixing architecture called Toeplitz Neural Networks (TNN). In particular the attention in the popular transformer architecture is replaced with a Gated Toeplitz Unit which is a GLU but before the scalar multiplication the transformed input is multiplied (\"mixed\") with a toeplitz matrix. The parameters for the matrix are predicted by a neural network in order to make the architecture compatible with any sequence length. The paper shows in various experiments that TNNs work equally well to transformers while being significantly faster both in practice and asymptotically.", "summary_of_the_review": "I believe that the paper has sufficient novel contributions and adequate experimental evaluation to make a very good ICLR paper. My only grievances had to do with the evaluation which at the same time is both lacking and thorough. Namely lacking larger and more convincing experiments, but also has enough ablations and experiments with different modalities to be sufficient.", "strength_and_weaknesses": "Strengths\n------------\n\n- The idea of the paper is very intuitive and has several precursors like S4s.\n- The use of a network to predict the toeplitz matrices based on the sequence index is interesting.\n- The results show that TNNs perform equally well to transformers in the example tasks.\n\nWeaknesses\n---------------\n\n- The tasks except the LRA benchmark are not particularly large sequence tasks. It would be great to have some experiments for instance on autoregressive image generation or larger scale transformer experiments.\n- Similarly to the above, LRA is not a particularly good indicator of real world performance as it can be seen also by the rest of the experiments.", "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": "BSWXf4VjJ5j", "reviewer": "Reviewer_kNVV", "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": "For modeling long sequences, as an alternative to the attention+softmax based weights that are typically utilized in the transformer models, this paper proposes to use relative position dependent weights that are generated by a ‘relative position encoder’ network, together with an exponential decay bias on the weights.  Due to the use of position encoder network to generate weights the number of parameters in the model is fixed regardless of the length of sequence being modeled.  Also, since relative position dependent weights naturally occur in a Toeplitz structure, the paper proposes to utilize special properties of Toeplitz matrix-vector multiply to achieve computation efficiency.", "summary_of_the_review": "See pros and cons above.  My main reason for a 'reject' rating is unclarity around the LRA baseline numbers.", "strength_and_weaknesses": "Pros:\n* An efficient approach for long range dependency modeling that relies only on relative position dependent weights\n\nCons:\n* The performance of baseline S4 model is substantially lower (AVG. 70.87) as compared to that reported in the S4 paper by Gu et al. (AVG. 80.48).  What is the reason for this discrepancy?\n* Paper lacks clarity, especially in describing the proposed model.  For instance:\t\n\t* Define d in Eq. 1\n\t* What role does W play in Section 3.2?  Does Eq. (4) need a +W term?\n\t* Section 3.3 states that inputs to the position encoder network are -(n-1) … (n-1).  Does this mean the network has 2n-1 inputs?  Or is it a single positive integer as input?\n\t* Similarly, section 3.3 states that output of the position encoder network is a d dim vector, but Fig. 2 indicates it is (2n-1) d dim vectors?\n\t* Is there a separate T matrix for every layer?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ab4KrYf9rgI", "reviewer": "Reviewer_4U54", "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": "This paper proposes a new attention mechanism that depends only on the relative positions of tokens and is independent of the features themselves. Since the attention coefficient depend only on the relative positions, the resulting attention matrix is Toeplitz. This results in a reduction in the number of parameters and in time complexity of feature updates, since Toeplitz matrices can be applied in O(n log n) time, where n is the sequence length. The authors demonstrate that the proposed method closely matches the performance of conventional attention models, while being faster in terms of training time. ", "summary_of_the_review": "The paper presents a very interesting and novel idea. The  proposed ideas are backed up with good experimental evidence. Overall, this paper is quite refreshing to read and I recommend acceptance. ", "strength_and_weaknesses": "Strengths: \n\nThe proposed idea is very interesting and novel. It is quite surprising to see that attention coefficients that depend on just relative positions perform well. The paper is well-written and the the flow if ideas is great. The provided experimental evidence is sufficient to demonstrate the merit of the proposed ideas. \n\nWeaknesses:\n\nThe paper is quite good as is and does not have many weaknesses. I do have the following suggestions/ questions to the authors:\n\n1. In designing the RPE, the authors claim that learning the weights of Toeplitz matrix performs worse compared to the RPE network. This is a bit unintuitive, since the former should be able to degenerate to the latter. I am surprised to see that learning the weights directly does not perform well. Maybe the authors could shed more light on this. \n\n2. It would be great to have visualizations of the learnt attention. I am curious to see the kind of associations that are learnt on the datasets considered. Does the model identify semantic relationships in the language? What is the intuition behind using only relative position based attention to capture associations between words?\n\n3. Are there any extensions possible to incorporate multi-headed attention?", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "1v7Mr4IKAU", "reviewer": "Reviewer_gJML", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new way to model the attention mechanism in the transformer architecture for sequence modeling. The proposed approach, while retaining comparable performance compared to other transformer architectures and approaches, improves the efficiency of transformer's capability in sequence modeling in two respects: 1) efficiency of the attention matrix operation (via the Toeplitz matrix formulation); and 2) efficiency of long sequence (which can be longer than the sequence on which the model is being trained) modeling during inference (via a generalized exponential decay bias on the attention scores). \n\nThe experiments demonstrate improved efficiency and performance in particular in long range sequence modeling. In addition, the authors also demonstrate comparable performance of the proposed approach with baselines in various text modeling tasks and an image modeling task, with a table showing the theoretical improved efficiency in the matrix operation.\n", "summary_of_the_review": "The proposed approach is a very interesting idea of exploiting Toeplitz matrices' structure for improving transformer architecture's computational efficiency. However, I think the empirical evidence does not fully substantiate the efficiency claim: empirical computational efficiency results are missing for all experiments except for LRA. It is also unclear how the proposed approach compares to other works in exploiting matrix sparsity/structure for improving transformer's efficiency. I think this paper has a lot of potential. I'm very open to increase my score. ", "strength_and_weaknesses": "### strengths \n- The idea of using Toeplitz matrices is interesting and, to my knowledge, new\n- Combining Toeplitz matrices and exponential decay bias lead to improved performance and efficiency in long range sequence modeling\n\n### weaknesses\nOne of the main contributions of the proposed approach, in my opinion, is the improved efficiency without sacrificing performance. However, I wish the experiments can include more evidence to support this contribution.\n\n- My first concern is a lack of clear explanation of the role of Toeplitz matrices and exponential decay bias, respectively, in modeling long sequences (e.g., for the LRA benchmark). It seems to me that, what enables the proposed approach to be able to operate on long sequences is not because of Toeplitz matrices but because of a generalized version of ALiBi. Since ALiBi and the proposed approach have similar performance (according to Table 14, last two columns), an experiment comparing the **efficiency** between ALiBi and the proposed approach would make it very clear that Toeplitz matrices are indeed more efficient for long sequence modeling during inference. \n- Since the performance of the proposed approach is similar in the other experiments, I wish the authors can also include, in addition to the performance metrics, the computational efficiency for the experiments in addition to the LRA experiment. I understand that the authors have a table on the theoretical efficiency improvement; I think some empirical evidence would make this efficiency claim much stronger. For example, Table 2, 3, and 6 do not seem to demonstrate the proposed method's advantage because 1) performance is similar to the baseline(s) and 2) efficiency comparison is missing.  \n\nSome other comments/questions\n- Does multi-head attention change any part (e.g., implementation) of the proposed approach?\n- Another approach for improving the efficiency of transformers is to leverage sparse/structured matrices (e.g., [1]). It seems that references to this body of work is missing from the paper (or not discussed much). Could the authors comment how their work relates to prior work in speeding up transformers by leveraging sparse/structure matrices?\n- What is the unit of the metric being reported in Table 4?\n- Why do the authors choose GLU instead of other operators (also: GLU is introduced without defining it)?\n- It seems that a citation in third paragraph above Section 2 is not anonymized (in the third line from the last line in that paragraph). But I think it does not matter at this point.\n\n[1] https://openreview.net/pdf?id=Nfl-iXa-y7R", "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: notable-top-25%