Encoding Recurrence into Transformers
Authors: Feiqing Huang
Kexin Lu
Yuxi CAI
Zhen Qin
Yanwen Fang
Guangjian Tian
Guodong Li
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Recurrent models
Transformers
sample efficiency
gated mechanism

Abstract: This paper novelly breaks down with ignorable loss an RNN layer into a sequence of simple RNNs, each of which can be further rewritten into a lightweight positional encoding matrix of a self-attention, named the Recurrence Encoding Matrix (REM). Thus, recurrent dynamics introduced by the RNN layer can be encapsulated into the positional encodings of a multihead self-attention, and this makes it possible to seamlessly incorporate these recurrent dynamics into a Transformer, leading to a new module, Self-Attention with Recurrence (RSA). The proposed module can leverage the recurrent inductive bias of REMs to achieve a better sample efficiency than its corresponding baseline Transformer, while the self-attention is used to model the remaining non-recurrent signals. The relative proportions of these two components are controlled by a data-driven gated mechanism, and the effectiveness of RSA modules are demonstrated by four sequential learning tasks.

Published as a conference paper at ICLR 2023
ENCODING RECURRENCE INTO TRANSFORMERS
Feiqing Huang +, Kexin Lu" Yuxi Cai', Zhen Qin', Yanwen Fang' Guangjian Tian', Guodong Li
Department of Statistics and Actuarial Science, The University of Hong Kong' Huawei Noah's Ark Lab²
(amieehuang, neithen, caiyuxi, u3545683) 1334463388ommmee @connect, hhu.hk hk gdli@hku.Ni hk, (qin. zhen, tian. guang ian) @huawei. com
ABSTRACT
This paper novelly breaks down with ignorable loss an RNN layer into a sequence of simple RNNs, each of which can be further rewritten into a lightweight positional encoding matrix of a self-attention, named the Recurrence Encoding Matrix (REM). Thus, recurrent dynamics introduced by the RNN layer can be encapsulated into the positional encodings of a multihead self-attention, and this makes it possible to seamlessly incorporate these recurrent dynamics into a Transformer, leading a new module, Self-Attention with Recurrence (RSA). The proposed module can leverage the recurrent inductive bias of REMs to achieve better sample efficiency than its corresponding baseline Transformer, while the self-attention is used to model the remaining non-recurrent signals. The relative proportions of these two components are controlled by data-driven gated mechanism, and the effectiveness of RSA modules are demonstrated by four sequential learning tasks.
INTRODUCTION
Sequential data modeling is an important topic in machine learning, and the recurrent networks such LSTM (Hochreiter & Schmidhuber 1997) and GRU (Chung et al.] 2014) have served as the benchmarks in this area over a long period of time. The success mainly contributes to the variety of recurrent dynamics introduced by these models, referred to as the recurrent inductive bias. More specifically, the dependence between any two inputs can be described by parametric form, which heavily depends on their relative temporal locations. However, the recurrent models are well known to suffer from two drawbacks. The first one is the gradient vanishing problem (Hochreiter et al., 200T), i.e. the recurrent models have difficulty in depicting the possibly high correlation between distant inputs. This problem cannot be solved fundamentally by the recurrent models themselves, although it can be alleviated to some extent, say by introducing long memory patterns (Zhao et al.) 2020). Secondly, the sequential nature renders these models difficult to be trained in parallel ( (Vaswani et al. 2017). In practice, many techniques were proposed to improve the computational efficiency of recurrent models, while they all come with compromises (Luo al. 2020
[ei et al.) (017).
In recent years, Transformers (Vaswani et al., 2017) have been revolutionizing the field of natural language processing by achieving the state-of of-thh-atttee ahetart performance on wide range of tasks, such as language modeling (Kenton & Toutanoval 2019), machine translation (Dai et al. (2019) and text summarization (Liu Lapata| 2019), etc. They have also demonstrated great potential in other types of sequence learning problems, for instance, time series forecasting (Zhou et al., 2021 Li et al.) 2019). The success of Transformers is due to the fact that the similarity between any two tokens is well taken into account (Vaswani et al. 2017). and hence they can model long range dependence effortlessly. Moreover, contrary to the recurrent models, the self-attention mechanism Transformers is feed-forward in nature, and thus can be computed in parallel on the GPU infrastructure /Vaswani ct al. 2017). However, the flexibility also leads to sample inefficiency in training a Transformer, i.c. much more samples will be needed to guarantee good generalization ability (d' Ascool et al. (021). Moreover, the chronological orders are usually ignored by Transformers since they are time-invariant, and some additional efforts, in the form of positional encoding, will be required further aggregate
the temporal information (Shaw et al. 2018 Vaswani et al. 2017 Dai et al. 2019).
"Equal contribution. This work was done during the author's internship at Huawei Noah's Ark Lab.
1 Cooresponndecee ggll@hhku.kk

---

Published as a conference paper at ICLR 2023
Matmmll d(p)
lyg
lage
(P(A)
Softmas
REM
Matuull
W
W
unal
scall
recanct
sample
sample signal Transformer
settle signal (c RSA (nun)
X No..
RNN
Ellvstration one KSA head
Figure I: (a) - (c) plot the two data features, namely the sample signal and the sample size as the I and axis, respectively. The model performance in each data region for the RNN, Transformer and RSA are given, where deeper color implies better performance. (d) In each attention head, the proposed RSA attaches an REM to a normalized self-attention score via gated mechanism, with gate value (μx). The REM depicts a type of recurrence dependence structure between the tokens in X, and is parameterized by one or two parameters, i.e. À or (7, 0), where À = tanh(n), == a(v).
In short, both recurrent and Transformer models have the pros and cons in modeling sequential data. On one hand, due to inductive bias, the recurrent models excel at capturing the recurrent patterns even with relatively small sample sizes; see Figure Ta). Mcanwhile, sample size is the performance bottleneck for the Transformer models and, when there sufficient samples, they are supposed to be able to depict any recurrent or non-recurrent patterns in the data; see Figure [b). On the other hand, sequential data have recurrent patterns more or less, and Transformers may have improved performance if the recurrent model can be involved to handle these patterns, especially when the sample size relatively small. Specifically, the recurrent and non-recurrent components are separable, then one can apply parsimonious recurrent model on the recurrent component and a Transformer on the non-recurrent one. As a result, the sample efficiency can be improved comparing to the Transformer-on/ baseline; see illustration in Figure (c).
There have been various attempts in the literature to combine the two models. Some earlier works were to simply stack them together in straightforward manner. Chen et al. (2018) mixed and matched a Transformer's encoder with an recurrent- based decoder. Hao et al. (2019) introduced an additional recurrent encoder to Transformer, while Wang et al. (2019) stacked recurrent layer prior to the multihead self-attention. These proposals inherit both the aforementioned shortcomings of Transformer and recurrent models. In particular, for a very long input sequence, the sequential operation in the recurrent layers become extremely expensive.
Recent efforts have been spent on integrating recurrence and self-attention systematically. Feedback Transformer (Fan et al. 2021) introduces the memory vectors to aggregate information across layers, and uses them to update the next token in a recursive manner. However, the computationally expensive sequential operation limits its attractiveness. Another line of research applies the recurrent operation only to aggregate the temporal information at coarser scale, while the token-by-token dependence is learned by self- self-attention instead. Transformer-X XL (Dai et al. 2019) partitions the long inputs into segments and introduces a segment-level recurrence. Meanwhile, Temporal Latent Bottleneck (TLB) (Didolkar et al. 2022) and Block-Recurrent Transformer (BRT) (Hutchins et al.) (022) further divide the segments into smaller chunks, and each chunk is summarized into a few state vectors. A recurrent relation is then formed on the sequence of state vectors. These hierarchical designs are useful to reduce the computational burden, while they overlook recurrent dynamics at a finer scale.
In attempt to simplify the numerical calculation of RNNs, we found surprisingly that an RNN layer with linear activation can be broken down into a series of simple RNNs with scalar hidden coefficients. Each simple RNN induces distinct recurrent pattern, and their combination forms the recurrent dynamics of the RNN layer. Hence the calculation time can be greatly reduced by training these simple RNNs in parallel. On top of that, can be equivalently rewritten into the positional encodings of multihead self-attention (MHSA). This spontaneously inspires a solution, the multihead Self-Attention with Recurrence (RSA), to combine self-attention with RNN into one single operation while maintaining parallel computation. This solution enables our design to preserve the merits from both Transformer and recurrent models, while their respective shorteomings are avoided. More importantly, it can be used to replace the self colf-attention of existing networks, such as Transformer XL, TLB and BRT, to further explore recurrent dynamics at the finer scale. Our paper makes three main contributions below.
With ignorable approximation loss, we demonstrate that an RNN layer with linear activation is equivalent to multihead self-attention (MHSA); see Figure Specifically, each attention
2

---

Published as a conference paper at ICLR 2023
head can be used recover type of recurrent dependence structure, and multiple heads working in syne replicate the complex temporal dynamics of the RNN layer.
2. In the above MHSA. recurrent dynamics of the RNN layer encapsulated entirely into the positional encodings, which we name the Recurrence Encoding Matrices (REMs). This makes it possible to add the REMs any existing Transformer architecture that has the self-attention mechanism, leading to the Self-Attention with Recurrence (RSA) module; see Figure [d). A gated mechanism is used to control the proportion of REMs, and the gate value may also be interpreted as the proportion of the recurrent signals in the data.
3. Our experiments on four sequential tasks demonstrate that the proposed RSA module can effectively enhance the baseline Transformers' forecasting power. Moreover, from the fitted gate values, we have an interesting finding that time series data have stronger recurrent signals than those of the regular languages, while the code or natural languages have much weaker recurrent signals.
1.1 OTHER RELATED WORKS
Relative positional encoding The proposed REMs can provide complementary positional encoding in the RSA module. Essentially, its recurrent pattern conveys relative location information. This property is inherited from the distance-awarenes, of the RNN. Compared to the relative positional encoding (RPE) in the existing literature, is more parsimonious and interpretable. The fully learnable RPE proposed by Shaw al. 2018) requires (TT²d) parameters, where ' is the number of tokens and d is the token dimension. Later, different variants are introduced by Huang et al. (2019) and Dai al. (2019), which reduce the number of parameters O(Td) and O(d), respectively. In contrast, our REMs have parametric forms of merely one or two parameters.
Time series forecasting Recent literature sees surge in deep learning models designed specially for time series forecasting tasks, which are not Transformer-basee
For instance, DLinear (Zeng et al. 2022) and Autoformer (Wu al.) (202T) decompose the series into trend and non-trend components. Autoformer and SCINet (Liu et al. (002)) further exploit the temporal dependence structure of time series via the autocorrelation function and multi-level convolution operations, respectively. FiLM (Zhou et al.) 2022a) and FEDformer (Zhou et al.) 2022b) transform the series to the frequency domain to capture meaningful signals while removing noises. This paper, however, differs from these literature in both target and method. We aim to add the recurrent inductive bias to general-purpor Transformers, and hence its performance rely heavily on the baseline Transformer that modifies.
2 RELATIONSHIP BETWEEN RNN AND MULTIHEAD SELF-ATTENTION
This section demonstrates that, without loss of much generality, an RNN layer can be approximated by a series of simple RNNs with scalar (hidden) coefficients, which can be further represented the form of multihead self-attention.
2.1 BREAKING DOWN AN RNN LAYER
Consider an RNN layer with the input variables {æ, E 1 T), and it has the form of
h; = g( W h + W. + b), where g(.) is the activation function, h; E Rd is the output or
hidden variable with hg = 0, b E IR is the bias term, W, E Rdxd and W., E Rdxdo are weights. When the activation function linear, i.e. g(x) = x, the RNN becomes
1-1
h Wr h + W or equivalently h,
Σ W2W j=0
(1)
Outpul
Pit
Output
Output
Output
Concat AXE
RNN
Hiddlnn state
Hodde state
state
pea (r.0)
Insut
at
Q-0
K=0
A 7,
RNN
simple RNNs
(c) Multhhad self-amantion
Figure 2: Illustration on how an RNN layer can be equivalently represented by a set of simple RNNs and further by multihead self-attention,
3

---

Published as a conference paper at ICLR 2023
where the bias term b is suppressed for simplicity. Although it has feedforward form, the RNN cannot be trained in parallel, and this is mainly caused by the power j of recurrent weights Wh. where S t t- 1. This section makes effort block diagonalize W,, such that the RNN at T can be broken down into a sequence of simple RNNs with scalar (hidden) coefficients.
Lemma 1 (Theorem 1 in Hartfiel (1995)) Real matrices with R distinct nonzero eigenvalues are dense in the set of all x d real matrices with rank at most R, where 0 < RRS d.
Suppose that the weight matrix W,, has rank R S d. By Lemma] I without loss of much generality, all distinct. Specificallly, W, has real nonzero eigenvalues X1,-..; .....,,,,, Ay, and 8 pairs of complex nonzero eigenvalues 1,+ - Ar+2s. where (y -YEE -00) for result, we have the real Jordan form, WA = BJB where B E R _d is invertible and J E Rdxd a block diagonal matrix. It holds that W BJ B for all j 2 1, and we can then break down the recurrence induced by WA into that of the p x block matrices in J with 1 or 2.
assume that the nonzero eigenvalues of Wh
(Ar+2x-1,Ar=p
< s, is the imaginary unit, and R. r ++ 2s. As
Similar to L we define three types of RNNs with linear activation below,
[-1
(A) = Σ
h (7,0)
Σ cos(j0) W Zz-j.
-ド sin(jo) Rt where the first one corresponds to the real eigenvalues, i.e. the 1 x block matrices in J. while the last two correspond the complex eigenvalues, i.e. the 2 x 2 block matrices in J. Note that each of the three RNNs has the recurrent weights of À or (7, 0), and its form with a nonlinear activation function given the Appendix.
and
Proposition 1. Suppose that Wn, has rank R = + 2s S d, and its eigenvalues are defined above. Let ho.: Wy and then the RNN with linear activation 4 can be equivalently rewritten into
h Σ (B())) +
he C1
(1k, 0k)
Σ
h C2 (7k, 0k) ho
R=1
2.2 AN EQUIVALENT MHSA REPRESENTATION
Consider the RNN of (h.), and X = (#i1,... )T)' RR Txd= be an input matrix consisting of T tokens with dimension din. where the transpose of matrix A is denoted by A' throughout this paper. We first give the value matrix V by projecting with a linear transformation, i.e. V X XWy with
Wv T E Rd xd and the relative positional encoding matrix is set to
0
f1(A)
0
PR mask (A)
f2(A)
(1(A)
0
fr-)(A) fr-
fr-s(A)
where fe(A) = for <t 1. As a result, the first RNN at 2 can be represented into a self-attention (SA) form,
(h.....,, BRY SA (X) = [softmax QK") PR [
We call mask the recurrence encoding matrix (REM) as it summarizes all the recurrence in {h.} For the RNN of (, 1 or 2, the REM is denoted by P (7,0), which has the form of
33 with (e(A) being replaced by fe(7, 0) =²² cos(10)) i = 1 or fe(7, 0) =-' )in((())), = 2 for
SiS 1-1. 1. And the value matrix has the form of V XWv with Wr wC E Rdd xd
Thus, these two RNNs (2) can also be represented into SA forms,
(h
yiy SA Ci (X) (" PCi (1, with i 2.
The remaining term in Proposition I lag depends on x, only, and there is no inter-dependence involved. Mathematically, we can represent into SA with the identity relative positional encoding matrix. Finally, all the query and key matrices Q and K are set to zero in the above reformulations. Proposition 2. If the conditions of Proposition / hold, then the RNN with linear activation at ( can be represented into a multihead self-attention (MHSA) with r + 2s + 1 heads, where the query and key matrices are zero, and relative positional encoding matrices are {PR (PRasseAAk) < (PC1 (7k, 0k), PC2 p 0z), 1 & k E 8) and an identity matrix, respectively. mikk
r).
4

---

Published as a conference paper at ICLR 2023
The three simple RNNs at (2) provide different temporal decay patterns: he provides the regular exponential decay induced by the real eigenvalues X 's and (h.²) h2²)) provide the cyclical damped cosine or sine decay induced by the pair of complex cigenvalues (rxe2 , -00)) yss
These tem- poral decay patterns are further summarized into the regular REM, (a), (A), and cyclical REMs, ( mask (7, f) and P mask (7) f), respectively; see Figure 2 for the illustration. From Proposition 2 the combination of these three types of patterns forms the recurrent dynamics of the RNN layer ①
For each head, the REM has one or two parameters, and Wv can be regarded as one d X d learnable matrix. This leads to a parameter complexity of O (RRd)) ). and it is slightly larger than that of the RNN at I since R is usually much smaller than d (Prabhavalkar et al., (016)) Moreover, the MHSA representation in Proposition givee us a chance to make use of parallel matrix calculation on the GPU hardware; see Appendix D.3 for an illustration of the computational efficiency of REMs.
ENCODING RECURRENCE INTO SELF-ATTENTION
While the query and key matrices are set to zero in the MHSA representation at Proposition 2 they play central role in a standard Transformer. This motivates us to propose the Self Self-Attention with Recurrence (RSA) module to seamlessly combine the strengths of RNNs and Transformers:
(4) for each head, where P is regular or cyclical REM, and (1) E |0. 1] is gate with a being the sigmoid function and μ being the learnable gate-control parameter. Figure (d)) provides a graphical
RSA(X)= = {[1 ())))
P))
illustration of one RSA head.
Note that the REMs in Section 2 are all lower triangular matrices, which correspond to unidirectional RNNs. In the meanwhile, for non-causal sequential learning tasks (Graves et al. 2005 Zhou et al. 2016). bidirectional RNNs are usually applied, and accordingly we can define the unmasked versions of RÉMs. Specifically, the regular REM is pit
[ mask (A)J'. and the cyclical and 2. In practice, these REMs will be explosive when [^] > 1 or hi > 1. To avoid this problem, we further bound these two parameters by transformations in this paper, i.e. x = tanh(n) and 7 sigmoid(v). and these notations then become PR (T). PC (v, 0) and (,, 0) with k E {mask, unmask) accordingly.
unmask (A) = -P mask (A) +
REMs are PCI
unmask (7, 0) PCI mmakk(7 (7, +
[Pei mask (7; 0)}' with i
Sequential data usually have some recurrent patterns, which can be captured by REMs. In the meanwhile, the remaining non-recurrent patterns can be modeled by the baseline Transformer via softmax QK'. The allocation of weights between REMs and self-attention is adjusted by the learnable gate o (H). On one hand, comparing with the baseline Transformer, the inclusion of REMs will lead to a significant improvement of sample efficiency in modeling the recurrent patterns, and hence higher accuracy in prediction can be expected from the proposed RSA. On the other hand, comparing with the recurrent models, the Transformers, and hence the representation power of the RSA module is good as that of the baseline Transformer.
patterns can be taken care of by the flexible
In addition, the REM can act as complementary positional encoding scheme further provide relative location information. For the multihead RSA, the gate-control parameter μ only varies across layers, while the parameters controlling the matrix P vary across all heads and layers.
Initialization. The gate-control parameter μs is initialized in the interval [-3,3] for all the layers. For (2,7,0) which determine the recurrent patterns, we initialize X's at different heads to spread out between [-2, -1] U [1. 2] and v's to spread out between [1, 2]. and 0 is initialized at π 7/4. to encourage REMs to be non- non-zero and well-diversified.
Dilated REM variants. The dilated REMs can be further obtained by considering the block matrix formed by the first 7 columns and first 7 rows of P @ Ia, where d is the dilating factor. In fact, the dilated REMs can encapsulate the recurrence patterns of the dilated RNNs (Chang al. 2017): see Proposition 4 in the Appendix. They describe potentially periodic recurrence over a long-term timespan, and can significantly enrich the temporal dynamics of our RSA.
Hyperparameters! h; and d. In each multihead RSA layer with H heads, the number of the six types of REMs, namely one regular, two cyclical, one dilated regular and two dilated cyclical REMs, are denoted by A - kg. respectively. Since Σn= k; = H. we can apply constrained hyperparameter search to optimize over the choices of k; 's. For simplicity, we can set k₂ = Ky and Kş ke which indicates that the cyclical REMs come in pairs. The search for d, on the other hand, can be guided by various data analytic tools. For instance, can be observed from the autocorrelation plots as the
5

---

Published as a conference paper at ICLR 2023
0.75
0.76
0.74
0.05
0.1
0.73
0.2
0.72
0.21
0.0
E7hh1
ETTh2
ETTml
WTH
02
D4
Parity T3
T6
Defect Detection Text8
Eraik WWlTTott
Sores
Regulor Langugge
Code Natural Language
Figure The boxplot for gate values at different attention layers of RSA models.
seasonal period length for time series data CCryer & Chan 2008); while for the language-related data,
can be heuristically deduced from the recurrence plots WWebber al. 2016).
More discussions on REMs. Each type of REMs is basically masked or unmasked linear aggrega- tion of tokens, and we may alternatively consider more general Toeplitz, or even a fully learnable, matrix P at (4) such that all kinds of temporal decay patterns be automatically captured. Although more flexible than REMs, it will need (T)) or (TT²) additional parameters, where I is the sequence length, while each REM requires merely one two parameters. Note that the proposed RSA at (4) also includes standard self elf-attention, which is flexible enough for the remaining nonlinearities that failed be captured by REMs, and hence it may not be necessary to consider a more general yet less efficient structure for REMs. see Appendix B for both theoretical and empirical evidences.
4 EXPERIMENTS
This section contains four sequential modeling tasks and, for each task, we modify some popular Transformer baselines by adding the REMs to their attention weights via a gated mechanism as in 44.. The modified models are named with the prefix "RSA-" The trained gate (J²) controls the percentage of weights allocated to the REMs, and it hence provides rough measure for recurrent signals in the data. From Figure 3 we may argue that time series have the strongest recurrent signals, followed by the regular language You 1997) and finally the code or natural languages. The gate values also vary across different layers of Transformer models, indicating that the proportion recurrent signals may change as the data propagate through layers. Moreover, the data-driven gated mechanism can help maintain the optimal allocation between REM and self-attention to achieve better sample efficiency and improved performance. All experiments conducted on Nvidia V V100 32GB GPUs.
4.1 TIME SERIES FORECASTING
Time series data possess unique attributes, such strong recurrent signals, that can improve forecast- ing accuracy. Although Transformers are not currently the state-of-the-art model for this task, interesting to explore how the proposed RSA module could enhance their performance.
Our experiments are performed on two public benchmark datasets: the ETT dataset is comprised of seven features related the electric power long-term deployment, where (ETTh;, ETTha recorded by the hour and ETTm, is recorded by 15-minute intervals; and the Weather dataset contains twelve climate indicators collected every hour over a 4-year period. For the bascline models, we adopt Informer (Zhou et al.] 202T), LogSparse Transformer (Li et al. (019) and Transformer-XI. (Dai et al. 2019). In particular, to accommodate the cases where the attention map is non-square, we extend the recurrent patterns and adjust the shape of our REMs; see details in Appendix D.2] All hyperparameters in baseline models are set to the optimal setting in Zhou et al. (202I), and we also follow their train/val/test division and training schemes to conduct our experiments.
Table summarizes the mean squared error (MSE) and mean absolute error (MAE) for the three baselines against their RSA counterparts, averaged across 5 repetitions. Overall, the revised models show significant improvement in performance over their baselines. Moreover, it is interesting to see that the REMs can act as effective substitutions for positional encoding. For Transformer-Xi in particular, although we remove their learnable relative positional encoding, superior performance attained by RSA-XI. while the total number of parameters reduced. Since more than 70% of weights are allocated to the REMs in Figure 3 it numerically verifies that the recurrent signals dominate the non-recurrent ones for time series data.
Accessible at httpa/////a//gaaa.ooo//ooooooa/a
Accessible at https::t////...... ht.pps://www.cet http://wwwww...aaaoooooooococeee now..
w 1-dat//

---

Published as a conference paper at ICLR 2023
Table 1: Multivariate long sequence time-series forecasting results reported on different prediction window sizes. We compare the MSE and MAE of RSA models with their baselines under all settings, and highlight the better results in bold letters. Note that XL requires sequential ordering for training. and the same scheme are adopted for all models to make the results comparable.
Methods
Informer
RSA-Infomer
LogSperse
RSA-LoggSurse
XL
RSA-XL
Metric
MSE
MAE
MSE
MAE
MSE
MAE
MSE
MAE
MSE
MAE
MSE
MAE
24
0.762
0.632
0.414
0.450
1.124
0.826
0.858
0.668
0,514
0.518
0.466
0.493
ETTh2 ETTT
48
1,006
0.763
0.467
0.493
1.161
0.841
0.818
0.659
0.571
0,556
0.528
0.535
168
1.411
0.823
0.753
0.659
1.104
0.818
1.042
0.781
0.898
0.734
0,813
0.694
336
1.416
0.987
0.895
0.755
1.178
0.851
0.972
0.774
0.963
0.758
0.942
0.756
24
2.558
1.253
1.264
0.879
2.894
1.375
1.076
0.844
0.763
0,699
0.705
0.660
48
2.487
1.268
18788
1.067
3.009
1.363
1.362
0.975
1.293
0.917
1.171
0.877
2. 2.869
1.324
2.830
1.301
2.876
1.307
2,165
1.235
2.780
1.288
2.671
1.290
336
2.055
1.113
2.113
1.124
3.005
1,350
2.909
1,365
2.447
1.231
2.461
1.238
24
0.536
0.511
0.534
0.507
1.105
0.837
0.619
0,553
0.561
0.537
0.591
0.549
ETTml
48
0.781
0.633
0.644
0.612
1,150
0,852
0,541
0,519
0,562
0,543
0,556
0.536
96
0.823
0.697
0.732
0.665
1.227
0.897
0.526
0.520
0.714
0.640
0.707
0.645
1.371
0.945
0.835
0.710
1.167
0.862
0.955
0.766
0.969
0.795
0.967
0.795
0.316
0.371
0,328
0
0.560
0.553
0.394
0.441
0.364
0.411
0.367
0.414
Weather
48
0.606
0.566
0.432
0.464
0.582
0.567
0.432
0.466
0.473
0.490
0.466
0.484
168
1.009
0.771
0.862
0.702
0.929
0.754
0.602
0.580
0.684
0.616
0.592
0.572
336
1.096
0.801
0.846
0.697
0.874
0.734
0.638
0.602
0.895
0.713
0.816
0.679
Table 2: Prediction accuracy of the vanilla Transformer, the Transformer with learnable relative positional encoding ("Transformerr") on the six languages, together with the RSA-Transforma under different hyperparameter settings. All Transformers are 5-headed, and the hyperparameter settings for Ars-sSrasformer, Cases I-IV, are denoted by the tuple (k1, k2 his, ka, ks, kj).
Methods
Transformer
Transformer*
RSA- ASA-Tranfformer II: (3,0,0,2,000)
I: (5..0.0.0000.
III: (3.1..0...0)
IV: (3.00.0...I))
Bin 0
Bin 1
Bin
Bin
Bin 0
Bin 1
Bin 0
Bin
Bin 0
Bin 1
Bin 0
Bin
Da
0.2
0.2
0.87
0.94
1
1
1
D,
1
0.08
0.99
0.9
1
1
1
Parity
0.29
0
0.13
0.99
0.67
0.97
0.53
0.91
0.62
0.9
0.52
Tomita (T3)
0.89
0.11
0.98
0.48
0.97
1
0.97
1
0.98
1
0.98
Tomita (T5)
0.07
0.01
0.63
0.16
0.82
0.17
0.49
0
0.72
0.35
Tomita (I6)
0
0
0
0.78
0.35
0.89
0.38
0.95
0.46
0.64
0.39
4.2 REGULAR LANGUAGE LEARNING
Regular languages are intimately related the linear recurrence sequences, such as Fibonacci numbers (Kotek& & Makowsky 2010). Some works report that Transformers have difficulty in generalizing the rules of regular languages (Bhattamishra et al.) 2020 Tran et al.) 2018 Hahn 2020). Experiments are conducted to show that the proposed RSA module can leverage the recurrent inductive bias of the
REMs to improve Transformer's s sample efficiency, and subsequently its generalization ability.
For the experiments, we deliberately choose six types of regular languages on which the Transformer model has been shown to perform poorly, namely Parity. Tomita 3, 5 & 6 (Tomita 1982). D2 and DA (Bhattamishra et al. 2020). We use the decoder-only vanilla Transformer model as the baseline, and modify its self-attention layers into our RSA forms under four hyperparameter settings (detailed in Table As a comparison, another benchmark model (denoted by Transformer") is obtained by replacing the absolute sinusoidal positional encoding with the learnable relative positional encoding DDai et al. 2019). To evaluate their generalization ability, the test set is further separated into two bins, where bin I contains longer test samples than bin 0. Following Bhattamishra al. (220), we recast the prediction task into a classification one, where the prediction is deemed a success only when the output values at all positions
correct, and a failure otherwise.
From Table it can be seen that the vanilla Transformer model fails to grasp the recurring rules of these languages. With assistance of the learned relative positional encoding, they can learn better on D2, D4 and Tomita 3, but not the others. However, the RSA-Transformer not only achieves near 100% accuracy on D2, Da and Tomita 3, but also gains a significant boost in performance on the other three languages. In particular, Figure 3 shows that approximately 60% of weights are allocated to the REMs, implying strong recurrent signals in the datasets. We further provide some visualization of the REMs under Cases I IV and their interpretaions in Appendix H.2
7

---

Published as a conference paper at ICLR 2023
Table 3: (a) The defect accuracy is reported for the SodeTT-smmal baseline and the RSA-CodeT55- small. In addition, we report the percentage of the parameters added by the RSA model against its
baseline. (b) The number of Bit-per-character (BPC) is reported for Enwik8 and Text8 (lower is better), and the perplexity (PPL) is reported for WikiText- 103 (lower is better).
Models
Defect Accurucy (%)
Models
XL
RSA-XL
BKT
RSA-BRI
CodeTS--mall
64.60
Enwik8
1.074
1,068
1,076
1.668
RSA-CodeTT--sm
65.96
Tex18
1.163
1.163
1,165
1.163
Wikilext-103
23,83
23.73
23.76
23.64
Params Added (%)
5 x 10-1
Averaged Params Added (%)
1.01
10-4
8.68 10-6
(a) Code defect detection
(b) Natural language modeling
4.3 CODE AND NATURAL LANGUAGE MODELING
Different from regular languages, the recurrence relationship in programming or natural languages is weaker and harder interpret. Nevertheless, they have wide range of applications on which the Transformers are serving as the baseline models. Our experiments show that the baseline models can improve the performance with inclusion of a small percentage of REMs.
We first conduct a defect detection task based on the C language dataset provided by Zhou et al. (2019) which is a binary classification task to evaluate whether a code is vulnerable to external attacks. The pretrained CodeT5 (Wang et al. 2021 is adapted to this downstream task. Specifically, we use CodeT5-small as our baseline model with 12 layers and heads, and directly add the REMs on top of the self-attention with fully learnable RPE via gated mechanism. The gate-control parameter yi is initialized at 3 and we fine-tune both the baseline and our RSA models for 20 epochs with early stopping. It can be observed from the boxplot in Figure 3 that the gate values at different layers remain close to the initialization, with only 5% of weights allocated to the REMs. Although the recurrent signals in the code language is apparently much weaker than those in time series or regular language, our RSA-Code -ssmall is still able to achieve a significant improvement against the CodeT5-small baseline as shown in Table 3) a). The RSA-CodeT5-smal model has only about 320 additional parameters over the baseline with 66 million parameters, which is equal to 5 x 10 10-4%. More surprisingly, it surpasses the current SOTA result of 65.78%, which is achieved by the CodeT5- base model with total number of 220 million parameters (Wang et al., 2021). Due to limited resources, we have not yet fine-tuned RSA-CodeT5. T--base model.
The natural language modeling task is conducted on three standard NLP datasets, namely the word- level WikiText- 103 (Merity et al. 2017). Enwik8 (LLC. 2009) and Text8 (LLC.) 2009). We use two baseline models: Transformer-X XL and Block Recurrent Trasnformer (BRT), and their corresponding RSA models are formed by directly adding the REMs on top of some of the self-attention heads via a gated mechanism. For Wikitext- 103, all transformers
16-layer with 12 heads. In the meantime, for both Enwik8 and Text8 there are 14 layers and 8 heads. The details of model structures can be referred to Appendix E.3 We follow the training schemes of Transformer-XL. and the results are reported in b). Overall, it can be seen that RSA models can achieve better performance than their corresponding baselines. The gated values for RSA-XL on the three datasets are presented in Figure 3, and we can see that REMs contribute more substantially for Text8 and Enwik8 than WikiText- TO3, which may imply stronger recurrent signals for these two datasets.
4.4 ABLATION STUDIES
This section conducts three experiments to analyze how RSA scales with respect to sample size, data size and sequence length, and its performance compared against the baseline models.
Model scaling The first ablation studies the performance of RSA-XL on Text8 dataset when the number of parameters increases. Baseline models include Transformer-2 XL, and two other benchmarks suggested by reviewer, which replace the parsimonious matrix function P in RSA (see equation (4) with (1) a Toeplitz matrix, or (2) a fully Iearnable matrix. They are incorporated into Transformer- XL baseline and are hence referred to as TL-XL and FL-XL, respectively. To have comparable parameter counts, the number of layers in FL-XL varies from to 14, whereas that in others varies from 10 to 16. We adopt the original training schemes of Transformer-XL. From the results presented in Figure (left), it can be observed that RSA-XL is the most parameter efficient across all model scales. See Appendix E.4 for similar results comparing BRT and RSA-BRT on model scaling performance.
Pretrriieed weights available from ht httpst:tt//ttttott com com / sa 1eallesooo Foreeorc//ooo11
8

---

Published as a conference paper at ICLR 2023
1.22
2.0
06
1.20
FLAt.
TLXL
504
1.10
0.
0.0
Number pararmtters (N)
Proportion Staining data 196)
Proportion training data
Figure 4: The left panel presents the BPC on Text8 for XL, RSA-XL, TL-XL and FL-XL at different model sizes. The middle panel compares the sample efficiency of RSA-XL on with that of the baseline XL by training them on restricted portions of the Enwik8 training set. Meanwhile, the gate-values at different attention layers of RSA-XL are presented in the boxplot.
100
8 20
ACCUrOCy
1.5
1.0
DITILY
T1.113
CITTES)
06
Sequuetce length
Suquance lergth
Gradhant stap
Gradlent step
Figure 5: Accuracy for BRT vs RSA-BRT and TLB RSA-TLB on the copy task is plotted on the first and second panels respectively, where "S" means a small training sample size of 6400, and "L" means a large training sample size of 12800. When sequence length 512, the cross entropy loss of the four models for the first 9000 gradient steps are plotted in the third and fourth panels.
Data scaling The second ablation study compares the sample efficiency of RSA-XL against Transformer-Xe XL. Specifically, we use different proportions of training data from Enwik8 to train the models, and maintain the same evaluation and test sets. Results are presented in middle panel of Figure 4, and we further visualize the gate values (v)) allocated to REMs at every layer in the right panel. It shows that, available training samples shrink, learnable gate will automatically increase the weights of the parsimonious REMs, and this subsequently helps RSA-XL to maintain a consistently higher sample efficiency than the baseline XI. model.
Sequence length scaling In this ablation study, we adopt synthetic copy task akin to the one in Nguyen et al. (20TT) or Katharopoullss et al. (2020). It requires the model to copy a sequence of symbols with different maximum lengths. For every sample, sequence of ten symbols is randomly generated and repeated multiple times, with a reserved symbol separating each replication. Four models are used: BRT, TLB, RSA-BRT and RSA-TLB, and we adopt small training sample size of 6400 as well as a larger one of 12800. The implementation is detailed in the appendix. Figure [ first depicts the accuracy with respect to the sequence length and then shows the cross entropy loss with respect to the number of gradient steps. can be observed that RSA-BRT BRT and RSA-TLB converge faster than their baselines, respectively, and achieve perfect accuracy across all sequence lengths.
5 CONCLUSION AND DISCUSSION
By formulating RNN into an MHSA form, we novelly propose RSA module to incorporate the recurrent dynamics of an RNN into Transformer. Specifically, the lightweight REMs are combined with the self-attention weights via a gated mechanism. maintaining a parallel and efficient computation on the GPU infrastructure. Experiments on four sequential learning tasks show that the proposed RSA module can boost the sample efficiency of the baseline Transformer, supported by significantly improved performance. In addition, with the fitted gate values to measure the recurrent signal strength in the data, it can be observed that the code natural languages have much smaller proportion of recurrent patterns, which further explain the superiority of Transformer models in these two data domains, while the inclusion of REMs still can boost the baseline performance.
This paper can be extended along three directions below. Firstly, while six typical examples of REMs are introduced, we may also consider other types of REM designs, such as the non-distinct eigenvalues of the RNN weight matrix Wn. and long-memory filters operated top of the RNNs (Zhao et al., 2020). Secondly, the proposed RSA module can be further applied to other types of sequential learning tasks such as video learning (Bulat et al. 2021) and skeleton- based human motion detection (Shu et al. 202T). Finally, is of interest to incorporate the REMs into models other than Transformers, to apply it directly standalone recurrent unit.

---

Published as a conference paper at ICLR 2023
6 REPRODUCIBILITY STATEMENT
To ensure the reproducibility and completeness this paper, we include the Appendix with five main sections. Appendix A discusses the relationship between RSA and some important related works. Appendix [B] provides a theoretical and empirical study on the performance gap between linear and nonlinear RNNs. Appendix [C]ontainn the complete proofs for all propositions presented in this paper. An efficient method to compute the REMs is detailed in Appendix D together with an extension to non-square REMs and an empirical study on the time efficiency of the proposed method. The experiments in the paper are reproducible with additional implementation details provided in We also include the hyperparameter settings for all results contained Tables and Appendix F
ACKNOWLEDGMENTS
We would like to thank the three anonymous reviewers for spending time and efforts and bringing in constructive questions and suggestions, which help us greatly to improve the quality of the paper. We would like to also thank the Program Chairs and Area Chairs for handling this paper and providing the valuable and conprehensive comments.
REFERENCES
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In EMNLP, pp. 7096-7116, 2020.
Adrian Bulat, Juan Manuel Perez Rua, Swathikiran Sudhakaran, Brais Martinez, and Georgios Tzimiropoulos. Space-time mixing attention for video transformer. Advances in Neural Information Processing Systems, 34: 34:195999 19119-9999996 2021.
Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Witbrock, Mark Gasegawa-Johnsonn and Thomas S Huang. Dilated recurrent neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 76-86, 2017.
Mia Xu Chen, Orhan Firat, Ankur Bapna, Melvin Johnson, Wolfgang Macherey, George Foster, Llion Jones, Mike Schuster, Noam Shazeer, Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Zhifeng Chen, Yonghui Wu, and Macduff Hughes. The best of both worlds: Combining recent advances in neural machine translation. In Proceedings of the 56th Anmual Meeting of the Association for Computational Linguistics (Volume I: Long Papers), pp. 76-86, Melbourne, Australia, 2018. Association for Computational Linguistics.
Junyoung Chung, Caglar Gulcehre, Kyunghyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks sequence modeling. In NIPS 2014 Workshop on Deep Learning, December 2014 4, 2014.
Jonathan Cryer and Kung-Sik Chan. Time series analysis: with applications in R, volume 2. Springer, 2008.
Zihang Dai, Zhilin Yang, Yiming Yang. Jaime G Carbonell, Quoe 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-2988, 2019.
Aniket Rajiv Didolkar, Kshitij Gupta, Anirudh Goyal, Alex Lamb, Nan Rosemary Ke, and Yoshua Bengio. Temporal latent bottleneck: Synthesis of fast and slow processing mechanisms in sequence learning. In Advances in Neural Information Processing Systems, 2022.
Stéphane d' Ascoli, Hugo Touvron, Matthew L Leavitt, Ari S Morcos, Giulio Biroli, and Levent Sagun. Convit: Improving vision transformers with soft convolutional inductive biases. In International Conference on Machine Learning, pp.
PMLR, 2021.
Angela Fan, Thibaut Lavril, Edouard Grave, Armand Joulin, and Sainbayar Sukhbaatar. Addressing some limitations of transformers with feedback memory. arXiv preprint arXiv:2002.088 094000 2021.
Alex Graves, Santiago Fernández, and Jürgen Schmidhuber. Bidirectional 1stm networks for improved phoneme classification and recognition. In International conference on artificial neural networks, pp. 899.804, Springer, 2005.
10

---

Published as a conference paper at ICLR 2023
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 8:156-171, 171, 2020.
Jie Hao, Xing Wang, Baosong Yang, Longyue Wang, Jinfeng Zhang, and Zhaopeng Tu. Modeling recurrence for transfommr. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Papers), pp. 1198- 1207, Minneapolis, Minnesota, 2019. Association for Computational Linguistics.
Darald Hartfiel. Dense sets of diagonalizable matrices. Proceedings of the American Mathematical Society, 123:1669-1672, 1995.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural compulation, 9(8):
1735-1780, 1997.
Sepp Hochreiter, Yoshua Bengio, Paolo Frasconi, Jürgen Schmidhuber, and Corso Elvezia. Gradient flow in recurrent nets: the difficulty of learning long-term dependencies. A Field Guide to Dynamical Recurrent Networks, pp. 237-243, 2001.
Roger A. Horn and Charles Johnson. Matrix Analysis. Cambridge University Press, New York, 2nd edition, 2012.
Cheng-Zhi Anna Huang, Ashish Vaswani, Jakob Uszkoreit, Ian Simon, Curtis Hawthorne, Noam Shazeer, Andrew M. Dai, Matthew D. Hoffman, Monica Dinculescu, and Douglas Eck. Music transformer. In International Conference on Learning Representations, 2019. URL hhhttss //openreview, / forum?2derrJ+-hhAcFF
DeLesley Hutchins, Imanol Schlag, Yuhuai Wu, Ethan Dyer, and Behnam Neyshabur. Block-recurrent transformers. In Advances in Neural Information Processing Systems, 2022.
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mnss: Fast autoregressive transformers with linear attention. In International Conference Machine Learning, pp. 5156-5165. PMLR, 2020.
Jacob Devlin Ming-Wos Wei Chang Kenton and Lee Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, pp. 4171- 4186, 2019.
Tomer Kotek and Johann A Makowsky. Definability of combinatorial functions and their linear recurrence relations. In Fields of Logic and Computation, pp. 444-462. Springer, 2010.
Tao Lei, Yu Zhang, Sida I Wang, Hui Dai, and Yoav Artzi. Simple recurrent units for highly parallelizable recurrence. arXiv preprint urXiv: Tot::1700 170.00275, 2017.
Shiyang Li, Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, Yu-Xin Yu-Xiang Wang, and Xifeng Yan. Enhancing the locality and breaking the memory bottleneck of transformer on time series forecasting. Advances in Neural Information Processing Systems, 32, 2019.
Minhao Liu, Ailing Zeng, Zhijian Xu, Qiuxia Lai, and Qiang Xu. Time series is a special sequence: Forecasting with sample convolution and interaction. arXiv preprint 206.v:2106.092: 2021.
Yang Liu and Mirella Lapata. Hierarchical transformers for multi-document summarization. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 5070-5081, Florence, Italy, 2019. Association for Computational Linguistics. doi: 10.18653/v1/ 150-1
MultiMedia LLC. Large text compression benchmark, 2009.
Yi Luo, Zhuo Chen, and Takuya Yoshioka. Dual-path RNN: efficient long sequence modeling for time-domain single-channel speech separation. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 46-50. IEEE, 2020.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations, 2017. URL https: :// www.eewwwww.fooumtmeemmm http:/oorrummm.ddyyyy2u

---

Published as a conference paper at ICLR 2023
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, 01194449294465 2021.
Rohit Prabhavalkar, Ouais Alsharif, Antoine Bruguier, and Lan McGraw. On the compression of recurrent neural networks with an application to Ivesr acoustic modeling for embedded speech recognition. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5970-5974, 2016. doi: 10. 11199CAASSP2011.77778222
David Salinas, Valentin Flunkert, Jan Gasthaus, and Tim Januschowski. Deepar: Probabilistic fore- casting with autoregressive recurrent networks. International Journal Forecasting. 36(3): 181- 1191, 2020. ISSN 0169-2070. doi: http/////aaeeeeer.r.r///////////
07 0001, URL https
7/www www.nsscieceddiio rect. com/
Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. Self-attention with relative position representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers). pp. 464 468. Association for Computational Linguistics, 2018.
Xiangbo Shu, Liyan Zhang, Guo-Jun Qi, Wei Liu, and Jinhui Tang. Spatiotemporal co-attention recurrent neural networks for human-skeleten motion prediction. IEEE Transactions on Pattern Analysis and Machine Inielligence, (4(6))3300-3311 2021.
M. Tomita Dynamic construction of finite automata from examples using hill-climbing. In Proceed- ings of the Fourth Annual Conference of the Cognitive Science Society, pp. 105-108, Ann Arbor, Michigan, 1982.
Ke Tran, Arianna Bisazza, and Christof Monz. The importance of being recurrent for modeling hierarchical structure. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. -736,, Brussels, Belgium, 2018. Association for Computational Linguistics. doi: 1..18853/11/18--111
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Yue Wang, Weishi Wang, Shafiq Joty, and Steven C.H. Hoi. Codet5: Identifier-aware unified pre- trained encoder-decoder models for code understanding and generation. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. EMNLP 2021, 2021.
Zhiwei Wang. Yao Ma, Zitao Liu, and Jiliang Tang. R-transformer: Recurrent neural network enhanced transformer. arXiv preprint arXiv: 1007:0107..0572. 2019.
Charles L Webber, Cornel Ioana, and Norbert Marwan. Recurrence plots and their quantifications: expanding horizons. Springer Proceedings in Physics. doi: https://ooi. 0rg/10.1007/978-33199 29922-8, 2016.
Haixu Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Autoformer: Decomposition transformers with auto-correlation for long-term series forecasting. Advances in Neural Information Processing Systems, 34:22419-2222 -24400, 2021.
Sheng Yu. Regular languages. In Handbook of formal languages, pp. 41-110 Springer, 1997.
Ailing Zeng, Muxi Chen, Lei Zhang, and Qiang Xu. Are transformers effective for time series forecasting? arXiv preprint XXIv:2205.13504 2022.
Jingyu Zhao, Feiqing Huang, Jia Lv, Yanjie Duan, Zhen Qin, Guodong Li, and Guangjian Tian. Do RNN and LSTM have long memory? In Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pp. 11365-11375. PMLR, 13-18 Jul 2020.
Haoyi Zhou, Shanghang Zhang. Jieqi Peng. Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of AAAI, 2021.
12

---

Published as a conference paper at ICLR 2023
Peng Zhou, Zhenyu Qi, Suncong Zheng, Jiaming Xu, Hongyun Bao, and Bo Xu. Text classification improved by integrating bidirectional Istm with two-dimensional max pooling. arXiv preprint arXiv:1611.06639 2016.
Tian Zhou, Ziqing Ma. Qingsong Wen, Liang Sun, Tao Yao. Rong Jin, al. Film: Frequency improved legendre memory model for long-term time series forecasting. arXiv preprint arXiv:2205. 288008897 2022a.
Tian Zhou, Ziqing Ma, Qingsong Wen, Xue Wang, Liang Sun, and Rong Jin. FEDformer: Frequency enhanced decomposed transformer for long-term series forecasting, In Proc. 39th International Conference on Machine Learning (ICML 2022), 2022b.
Yaqin Zhou, Shangqing Liu, Jingkai Siow, Xiaoning Du, and Yang Liu. Devign: Effective vulner- ability identification by learning comprehensive program semanties via graph neural networks. Advances in neural information processing systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2023
APPENDIX
This Appendix contains five sections. The first section provides illustrative plot for multiscale recurrence various Transformer models. The theoretical and empirical gaps between the linear and nonlinear RNNs are studied in the second section. The third section presents Proposition 3, and then gives the detailed proofs for Propositions - 3. An efficient method to compute the REMs detailed in Section 4, and we further extend it non-square REMs and conduct an empirical study on the training time per batch for the RSA models against their baselines. Section 5 provides additional implementation details for the experiments, additional ablation studies and visualization of the learned patterns.
A MULTISCALE RECURRENCE
For sequential learning tasks, the recurrence relationship can be well observed different levels of temporal granularity. This feature has inspired new designs to add recurrence to Transformers from varying scales; illustration in Figure 6 Transformer-Xi (XL) (Dai al.. (019)) partitions long input sequence into segments, and places them into consecutive batches. A segment-level recurrence is then introduced by using cached hidden state to pass historical information iteratively to the next segment. Temporal Latent Bottleneck (TLB) (Didolkar et al. 2022) further divides the segment within one batch into smaller chunks, and then adopts the state vectors aggregate both high-level information across layers and temporal information across chunks. 'he chunk-level recurrence helps create a slow information stream in the sequence to learn more condensed representation. Block-Ree Recurrent Transformer (BRT) (Hutchins et al. 2022) also establishes recurrence across chunks (or blocks), while their recurrent states are layer-specific and updated with an LSTM-style gated design. As comparison, the proposed RSA follows the RNN account for the recurrence between individual inputs. In other words, it models the token-level recurrence, which is at the most fine- grained scale. Subsequently, it can be easily incorporated into the aforementioned coarser- coarser-grained designs, and may potentially bring benefits to their performance. For illustration, we use XI. and BRT our baseline models in Section 4.3.
Batch-1]
Trunsformer-XL:
Couse
segment-level recurence
Sayment
Temporal Latent Bottleneck
Bluck-Recarret
Chunk
Chunk
Chink
chunk recurence
+
tokken-loral resumeree
Tokers inside chank
Figure 6: An illustration for multiscale recurrence. From top to bottom, Transformer-X has the most coarse -raieegrridddddeee segment-level recurrence, while both the Temporal Latent Bottleneck and the RecckrReeurrent Transformers share the finer-grained chunk-level (or block-level) recurrence. The proposed RSA has the most fined-grained token-level recurrence.
B THEORETICAL AND EMPIRICAL GAPS BETWEEN LINEAR AND NONLINEAR RNNs
B.1 THEORETICAL GAP
This subsection theoretically evaluates prediction errors when a linear RNN model is used to train the data generated by nonlinear RNN. For simplicity, consider 1D case only, and many-to-many RNNs are assumed.
Specifically, the nonlinear RNN model used to generate the data has the recursive form of
St (u())) with 4t wight1 + w + b*.
(5)
14

---

Published as a conference paper at ICLR 2023
and (.) is the activation function satisfying
(0) < 1, (0) = =1 and (x) I 1 for any x E R.
(6)
Note that many commonly used activation functions, including Tanh and Sigmoid, satisfy the above condition. We further consider additive error Et, i.. Yt St Es, where & has mean zero and finite variance denoted by 7-
For the generated data {yt), we train linear RNN model.
he he(0) w//h (0) + wyTt +
where the parameters = (w), Wz. b). Then the mean squared prediction error can be defined as
Cpred == min (y h,)))))
0
and its theoretical bound is provided in the following proposition.
Proposition 3. Suppose that K(u)) I and [(u I 3 for all t, E E. If |w 1 and the condition at o holds, then
(w (1 + B/4)+ +
Cpred
misspecification evvor
irreducible system ervor
where the first part due to the misspecification of using the linear activation to approximate σ (-).
Proof of Proposition 3 Let 0" = (we, w b*), and denote h4 = h₂(0") for all t E Z, i.c.
1y w li-1 1 + w + b²
(7)
By the definition of épred holds that
Epred I E(y h2)² = E(gt h2)² + +%
(8)
where the equality comes from E(e, 0 and var(Er) 7i By applying second-order Taylor
expansion at zero and from (5) and 66 we have
2 and ū lies between de and zero. This, together with 7 leads to h4 σ (0) + w (9:-1
1
= on + us + (O), where |R((0)| 2 oh
h1-1) + (0).
Let de = - hrs and it then holds that
= 0 0 Re(0) - or j=0
Σ Re j=0
where the second equality is obtained by applying the first equality recursively. As a result, by the condition that (o, < 1, E(²)) I and E(u?u?) I 3 for all t, Z, we can show that
B(O < 2 + E
L W R2-
+ E Σ | (
3 5² 1 a + 8
where { = Ei= |. If l < 1, we have & = (1-[w)])= -1, This, together with (
accomplishes
the proof.
B.2 EMPIRICAL GAP
This subsection conducts synthetic experiment to evaluate the performance of linear RNNs when there is nonlinearity in the data.
We first generate the data by using two-layer nonlinear RNN model with the form of
h ( w(()
w(( (i-1) + ((+)
agi (5) + (1 a)h
and
g oh ( ( (8)
h
2-1 +
2 W D 2((")) b(0)
(9)
with = 1 and 2, where 2; x,, z E R for 1 < s 3, (.). is a nonlinear activation function, (2)
and < 1 is the weight of nonlinearity. An additive error is further assumed, i.e. y: = Et
15

---

Published as a conference paper at ICLR 2023
Tanh
Sigmold
ReLU
Linear
Linea
Linear
RSA
1.10
RSA
RSA
1.01
1.04
1.00
Monlinear RMN
1.00
Noninnar RNN
1.00
Nonlinear RNN
0.95
0.90
0.98
0.85
0.92
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.5
0.8
1.0
0.0
0.2
0.4
0.0
0.8
1.0
Figure 7: The MSPE ratios for the linear RNN and RSA as the nonlinearity proportion a changes from 0 1. From the left, middle to right panels, set o-)()) in (9) to Tanh, Sigmoid or ReLU activation, respectively.
where } and } are independent and follow the standard multivariate normal distribution. Three nonlinear functions are considered for (.).,,, Tanh, Sigmoid and ReLU. a increases from to 1, the data generating process gradually changes from a strictly linear RNN to nonlinear one, i.e. essentially controls the proportion nonlinearity involved.
The sequence (y:, 1 < f S T) is fitted separately by linear RNN, nonlinear RNN with the corresponding activation, and linear RNN combined with a self-attention, i.e. the proposed RSA. Specifically, we generate sequence of length 10000 and then divide it into 100 segments, each of length 100. In each segment, we train with the first 99 observations and calculate the prediction error for the last observation. The Adam optimizer is adopted for training, and the training procedure will be terminated when the training loss drops by less than 10 The mean squared prediction (MSPE) averaged over 100 segments denoted by <peca epedd and eSA for the three models, respectively. Using nonlinear RNNs the benchmark, the MSPE ratio for the linear RNN or the RSA defined as
pred
MSPE ratio for model
NL where i RSA].
pred
Figure presents the MSPE ratios for three types of activation functions. It can be seen that, when 1, nonlinear RNNs perform the best, while linear RNN suffers from misspecification error. Alternatively, when a 0. the opposite can be observed. Moreover, as a increases, i.e. there are more nonlinearity, it is expected that linear RNNs become less favorable, while the proposed RSA can remedy the problem to some extent. Especially when >> 0.6, the RSA consistently achieves better prediction performance than the pure linear RNN.
C PROPOSITION AND PROOFS FOR ALL PROPOSITIONS
C.1 PROPOSITION 3 FOR DILATED RNNS
mask be the block matrix formed by the first T columns and the first mask & Ig. And pc, can be defined similarly for 1 or Consider dilated RNN (Chang et al. 2017) with the dilating factor d. It has the form h, = gW,,,, h4 Wa + b) where g(-) the activation function, h, Rdd the output or hidden variable with hg = 0, b E Rd the bias term, W, E Rdxd and W E Rdxdu are weights. When the activation function is linear, i.e. g(x) = I, the RNN becomes
For some positive integer d, let PR rows of PR
[-1
h = Wihh Wa or h, Σ 1=0
W.
(10)
where the bias term b is suppressed for simplicity. We have the following proposition.
Proposition 4. If the conditions of Proposition [ hoold for Wn in (TO.. then the RNN with linear activation at (TO) can be represented into multihead self-attention (MHSA) with r + 2s + 1 heads, where the query and key matrices are zero, and relative positional encoding matrices are {PR P (Ax), < k r}. {PC1 Epack macx("ik (Tk. 0x), respectively.
PC2 m 0x), l < s) and an identity matrix,
Proof. The proof follows directly from Propositions and
16

---

Published as a conference paper at ICLR 2023
C.2 PROOF FOR PROPOSITION
Let Wt be d x d real matrix with distinct eigenvalues, and from Chapter 3 of Horn & Johnson (2112) we have the Jordan decomposition, W, = BJB where B E Rdxd is invertible, and R has real Jordan form, J diag(>1,.... Ay, Cl...., C, 0} with
cos(fx) sin(Ox) E R2x2
C - 7h (-sin(0)) cos(On))
1skss.
Then.
- BJ
Σ
X G + Σ re { {cos(j0s)(k sin(j0s) for all j 2 1,
where G s, G and G ' are d x d real matrices determined jointly by B and B B-1 Let ho.: Wz and then,
--
h4 Σ WWw-
1=0
G W.WWa W
th (cos()O))Gr sin(j0+)Gk Wa W
j=1k=1
5=1k=1
Σ m (xx) +
h1
(1k: 0k)
ht (7k, 0k) ho.t=
k=1
k=1
where
1-1
h
WG or equivalently, h. = g(h + G Σ 1=1
(11)
g(-) being the identity function and h
Σド cos(jo) Wa
h
E 7 (.,jj) which can be obtained via the recursive relationships,
{
h Cl = g(> cos 0h C1 + (7 cos #GW #4 sin oh. h g(r cos oh
(12)
C2 + sin ((h + GW GW));-1)),
with being GCI or C2 respectively. For more general form, we can further assume that the activation function g(-) is nonlinear for the simple RNNs at (11) and (12)
C.3 PROOF FOR PROPOSITION
Using the SA form, we can represent the three types of the RNNs by
(h (Ax), ... h (A+)) = SA X) and
(h (Th 0x), h (TH, 0x)) SA Ci (X) for i 1 2.
Therefore, the first term in Proposition T caan be represented
Enf(Aa))
MHSA(X) concat (SA X), ).... SA = Σ ((x))
(13)
where W, (Ja; ... Iay Rrdxd with Ia being d-dimensional identity matrix. Similarly the MHSA for second and third term in Proposition [ given by
MHSA(X) concat (i))
(X),
SA (X))W.
Σ
(Tu. .x)..... .....
hT (rkk 0k)
Ci
(14)
where W = (Ia,... Lay E Redd
And we define the additional head as SAp (ha h (softmax(QKK)) + I with
We Wx and Wy W Combine with (1) and (14) we have
17

---

Published as a conference paper at ICLR 2023
MHSA(X) concat| Concaa((SA]) (SA) (S (X)ss (SA) (X), (X))ssS SAo (15)
where W. (Ia...., Ia)' E (R(++2++))
D COMPUTATION OF THE REMS
D.1 EFFICIENT COMPUTATION OF THE REMS
For any matrix A, cos A) and sin A) refer to applying the cosine and sine functions to each element of A. To compute the REMs, we first construct the exponent matrix L that has Toeplitz form:
T T-2 2
-
L
T-1 T -
Denote the square matrix whose elements all equal to À as A. Similarly, define and for y and 0, respectively. Extending the conventional power notation, we let X = pow(X L) and yb pow(y, L). i.e., (A4)is) = Lus and (-²)s,) = %,.j
L,s Then we can calculate the REMs by
D - IT
for regular REM, for cyclical REMs with 1 S i i
P = D Ir
where DR= DC = T @ cos(O o L). D = 7h @ sin @ L) and @ the Hadamard circumvent redundant computations and achieve parallelization
product. Such design allows as much as possible. To avoid extremely large or small values, we mask the entries that have power larger than preset number K. practice, set K 200.
Moreover, we can easily extend the above calculation to dilated REMs by substituting L with La- where (La)..) = [i,,, d=0) / and the dilating factor. The remaining operations are unchanged.
D.2 FLEXIBLE ADAPTATION TO DIFFERENT ATTENTION SHAPES
In cases, the query and key have different time spans with overlapping period; examples including the cross-atte attention and all attention the Transformer-Xi XL. We show this section that our REMs can be adapted for such cases. Typically, the historical information will be mostly stored the query matrix, and the new information will be included in the key and the value matrices. Assume that the query matrix contains the tokens from time 1 to time T, and the key matrix contains that from time T'- K to time T where K > is the overlapping period length and length of new information. Then the REM is of size (I. + K + T and takes the form the
T-K-1
T-K
T-K
1--
2--K-2(3)
((3
0
(K-1(3)
fK(3)
T-K+1
(B3
(--
J2(B)
fx-2(3)
fK-1(8)
T-1
fr)
fr-)(9)
fx(3)
fK-1(8)
A(
(r-
(r-2(8)
fx+1(8)
fx(8)
f1(9)
T41
fr(()
fr-1(8)
fx+2(8)
fK+1(8)
f2(8)
fi(8)
T+L
(r+
fr+L-2(3)
fK+L+1(3)
fK+1(8)
fz+1
which maintains the recurrent patterns while considering the shift in the relative time locations.
where 3 = À for regular REM (7, 0) for cyclical REMs. And we can extend to the dilated REMs similarly.
D.3 THE COMPUTATIONAL EFFICIENCY THE REMS FOR VARIOUS TRANSFORMER BASELINES
We first conduct an empirical study on the Weather dataset to evaluate the computational time the REMs for RSA-Informer, RSA-LogSparse and RSA-XI. Specifically, record the training time per
18

---

Published as a conference paper at ICLR 2023
RSA-Infarmer
RSA-1 Spparse
0.5
REW
0.5
REM Others
0.5
REM Dehers
treeing time per bance
Dcters
0.3
0.3
0.3
0.2
02
0.2
0.0
0.0
0.0
168
336
prodiction
sindow
prediction window
Figure 8: The training time ber batch for each RSA model, which can be decomposed into the additional computation time due to the REMs (green bar) and the others (blue bar).
6.5
Informer
25
LogSsaame
0.5
traniig time pert hates
Roforr
RS4Log5pprss
RSA AL.
0.3
3.1
0.1
130
700
150
200
150
250
150
predecton
simw
pawdl mnddow NL2
prediction
Figure 9: Comparison of the training time of ber batch between RSA-Informer and Informer (left panel), RSA-Logsparse Transformer and Logsparse Transformer (middle panel), RSA- Transformer- XL and Transformer-Xt (right panel). The experiment is performed Weather dataset.
batch for the RSA models, while simultaneously exclude the REMs from the models and record the training time again. The difference between the two gives the additional computation time due to the REMs, shown by the green bar in Figure 8 It can be seen that the calculations involving the REMs account for less than 20% of the total training time in general.
In the next experiment, we further compare the computational time between the RSA models and their respective baseline models. Note that the original Informer and LogSparse Transformer use absolute positional encoding (APE), while Transformer - adopts learned relative positional encoding (RPE). These positional encoding schemes are excluded from the RSA models. The training time batch for all the models are reported Figure We can observe a small increase in computational time for RSA-Informer and RSA-LogSparse against their baselines, while that for RSA-XI. remains nearly unchanged. This implies that the REMs requires a more computation effort than the APEs, and the same computation effort as the RPE introduced by TrLLsformer-XL.
E ADDITIONAL EXPERIMENTS AND RESULTS
E. TIME SERIES FORECASTING
We apply the same time series datasets as the Informer paper (Zhou et al. 2021), and the details given below for completeness. The first dataset is the Electricity Transformer Temperature (ETT). contains the records for seven electric power indicators over a two-year period from two separated counties in China. Zhou et al. (2021) created three separate datasets ETTh; and ETTh; for hourly level, and ETTm; for the fifieen-minute level. The train/val/test is 12/4/4 months. The second dataset consists of climatological data US. The train/val/test is 28/10/10 months. To ensure the quality of our baselines models, we make reference the following two github repositories, namely Informer202d1 and transformer-x Since Transformer-X XL requires a sequential order for training, testing and validation sets, we generate the training samples by sliding window starting from different points of the original time series following the practice in Salinas et al. (2020).
four-year period from 2010 2013 for various locations in
In this task, we the REMs substitute the original positional encoding scheme in the RSA models. Moreover, since the distilling operation in the original Informer design is likely to distort the relative
*The link to the repository is hhtp:///ghhaaccm///haaaoiiinnnnn under Apache-2.0 license. htg.g//rrrroooggggimmmmmmooooonr "The link to the repository https///gthaaccommmmmmmooommmmmn under Apache-2.0 license.
19

---

Published as a conference paper at ICLR 2023
Table 4: Multivariate long sequence time-series forecasting results on ETT and Weather datasets. The standard deviation of the 5 repetitions is included in brackets below the mean value. The results are reported on different prediction window sizes. We compare the MSE and MAE of RSA models with their baselines under all settings (a total of 32 comparisons), and report the number of times each model surpasses its comparing model in the last row.
Methods
Informer
RPSA-Informee
LogSparse
RPSA-LogSpane
XL
RPSA-XL
Metric
MSE
MAE
MSB
MAE
MSE
MAE
MSE
MAE
MSE
MAE
MSE
MAE
24
0.762
0.632
0,414
0,450
1.124
0.826
0,858
0.668
0.514
0,518
0,466
0.493
(0.144)
(0.076
(0.014)
(0.012)
(0.012)
(0.014) )
(0.052)
(0.034)
(0.031)
(0.018) )
(0.003
(0.002)
1,006
0.763
0,467
0.493
1.161
0.841
0.818
0.689
0.571
0.556
0,528
0,535
ETTh1
(0.024) ) (0.020) )
(0.018)
(0.017)
(0.094)
( (0.059) )
(0.021)
(0.010)
(0.010)
( (0.009) )
(0.009)
(0.008
168
1.141
0.823
0.753
0.659
1.104
0.818
1,042
0.781
0.898
0.734
0.813
0.694
(0.02)
(0003) )
(0,03)
(00118
(0.010)
(0.016) )
(0.02))
(0.007
(0.010)
(0.00)
(0.011
(0.008
336
1.416
0.987
0.895
0.755
1.178
0.851
0.972
0.774
0.963
0.758
0.942
0.756
(0.07)
(0.04) ) (0,04)
(00016)
(0,055)
( (0.036)
(0.013)
(0.008
(0,03)
( (0.012)
(0.012)
(0.008
24
2.558
1,253
1.264
0.879
2. 2.894
1.375
L077
0.844
0.763
0.699
0.705
0.660
(1.177)
(0.275
(0479)
(0.135)
(0.131)
(0.029)
(0.034)
(0.017)
(0.042)
(0.021)
(0.050)
(0.018)
48
2.487
1,268
1.878
1.067
3.009
1.363
1.362
0.975
1.293
0.917
1.171
0.877
E17h2
(0.088)
(0018)
(0455)
(0.128)
(0.034)
(0.012)
(0.089)
(0.043)
(0.061
(0.031)
(0.082)
(0.030)
168
2,869
1.324
2,830
1.301
2.876
1.307
2.165
1.235
2.780
1,288
2.671
1,290
(0.124)
(0.01)
(0.188)
(0,039)
(0.068)
(0.012)
(0.131)
(0.030)
(0.157)
(0.045)
(0.026)
336
2.055
1,113
2,113
1.124
3.005
1,350
2,909
1.365
2.447
1.231
2.461
1.238
(0.058)
(0.01)
(0.120)
(0,039)
(0,073)
(0.015)
(0.091)
(0.017)
(0.080)
(0.020)
(0.083)
(0.028)
24
0,536
0,511
0,534
0,507
1,105
0,837
0.619
0,553
0.561
0.537
0,591
0,549
(0023)
(0014)
(0023)
(0.011)
(0.053
(0.034) )
(0.063 )
(0.031
(0.02)) )
(0.011) )
(0.012) )
(0.011)
48
0.781
0,633
0,644
0.612
1.150
0,852
0,541
0,519
0.562
0,543
0,556
0,536
Em7ml
(0.265)
(0.135) ) (0.079)
(0.019)
(0.015)
(0.016) )
(0.010)
(0.005)
(0.009)
(0.005) )
(0.020)
(0.012)
96
0.823
0.697
0,732
0.665
1.227
0,897
0,526
0,520
0.714
0.640
0,707
0.645
(0.095)
(0.052) ) (0.079)
(0.05L)
(0.057)
(0.035) )
(00900
(0.057)
(0.075)
(0.019)
(0.015)
(0.029)
288
1.371
0.945
0.835
0.710
1.167
0,862
0,955
0,766
0.969
0.795
0,967
0.798
(0.246)
(0.059) ) (0.058)
(0.036)
(0.026)
(0.019) )
(9.149)
(0.072)
(0.093)
( (0.051)
(0.007)
(0.003
24
0.316
0,371
0.328
0.380
0.560
0,553
0.394
0,441
0.364
0,411
0.367
0.414
(0.003
(0.002) ) (0.001)
(0.001)
(0.069)
( (0.046) )
(0.015) )
(0.012)
(0.001)
(0.001
(0.000)
(0.000
0.606
0.566
0,432
0,464
0.582
0.567
0,432
0,466
0.473
0,490
0,466
0.484
Weather
(0.194)
(0.100) ) (0.004)
(0.002)
(0.029) )
( (0.021) )
(0.012)
(0.009)
(0.002)
(0.002)
(0.001 ) (0.001
168
1,009
0.771
0.862
0.702
0.929
0.754
0.602
0,580
0.684
0.616
0.592
0,572
(0.006
(0.003) ) (0.189)
(0.088)
(0.200)
(0.101) )
(0.027 )
(0.017)
(0.176)
( (0.085) )
(0.017) )
(0.012)
336
1.096
0
0.846
0.697
0.874
0.734
0.638
0.602
0.895
0,713
0.816
(0.236)
) (0.069)
[0.167)
(0.084)
(0.132)
( (0.071) )
(0.025)
(0.014)
(0.155)
( (0.071) >
(0.167)
(0.079)
4
8
24
positions, we exclude it from both our Informer baseline and the RSA-Informer. The hyperparameters in RSA are fine tuned via grid search.
Table reportts the fine-tuned hyperparameter settings considered in Table 1 of the main paper. To provide additional information about the standard deviation, we provide a more detailed version of Table 1 of the main paper, given in Table
Ablation on the hyperparameters To shed light on the importance of different recurrent dynamics, we provide an ablation study with RSA-Informer on ETTh, The model has a total of 8 heads, and we set 1 lss to some positive integer and ks ks to some positive integer 3. In particular, when 5 = 0, we also take bG = 0 and hence there are not any dilated REMs, Icading to k1 = 8 - 2s. Otherwise, we take ka = 4 28 and k = 4 2s. It can be observed from Table the inclusion of dilation and the cyclical patterns can significantly improve the forecasting performance. The concurrence of dilated and non-dilated RSA heads allows the model to capture both the short- and long-term recurrent dynamics.
Gate-control parameter learning To study how much proportion of the RSA output is accounted for by the REMs, Figure I0 plots the change in its relative importance i.e. (p)) during training for all the attention layers, starting from different initializations. As the learning rate drops rapidly, all curves are flattened towards the end. The relative positional attention is the most effective for the cross- attsntnttnntinn layer, and the least effective for the self-attention layer in the decoder, whose recurrent patterns may be disrupted by zero paddings. We observe a decrease in MSE as the initialization increases from 1 to 1, which provides empirical support for initializing at μ 1.
20

---

Published as a conference paper at ICLR 2023
Table 5: The fine-tuned hyperparameter settings used for the RSA models in Table 1. The tuple (k1, l2, K3. ka, ks, kis) refer to the number of the six types of REMs. The values of different dilating factors are listed, where those for regular heads are followed by those for the cyclical heads. d= means no dilated REMs are considered.
Methods
RSA-Informer
RSA-LogSparse
RSA-XL
Setting
(kg, Ag.
(kg Ag. As)
d
(Kg, fg. As, As. Ag)
(0.2.2.0:2.2)
224244,242241
(4.0.D..000))
124,24,24224
(4.0,0.4.0,0)
[24.24,24424]
48
(0.2.2.2.1.1)
(24,24.24.24]
(4.0.0,4..0))
[24.24.24.24]
(1.00044.000)
[24.24.2424]]
168
(0.2.2.211.))
224.24,24.24
(4.0.0...00))
[24.24.2424]]
(0.2.2.0.2.2)
[48.24.48,24]
336
(4,0,0.400,0)
(24,24,24.24]
(0.2.2.0..22)
[48,24,48.24]
(1.2,2.1.1.1)
[48,24,24]
24
(4.2.2.0,0.0)
(4.0.0,40,0)
[24,24.24.24]
(4.0,0.4..0)
[24.24.24424]
E1
(0.2.2.0.2.2)
[24.24,24.24]
(8.0.0...0.0)
(0.2.2.0.2.2)
[48.24.48,24 24]
168
(4,2,2.0.0.0)
(4.0.0,4.00))
[24,24,24,4]
(4,0.0,4.0,0)
[24.24,24.24]
(0.2.2.0.2.2)
[24,24.24.24]
(4.0.0.4.0.0)
[24,24.24.24]
(4.0,004.0.0)
[24.24.24,24]]
24
(0.0,0.0.4.4)
[2,3,6,24,2.33 6,2,44
(4.0.0,4.0.))
996.96.96.96
(0.1.1.0.1.)
[48,24,24,4, 28,2444
Weather ETTml
(0.2.2.022.))
196.96,990 96,
(4.0.0.4.0.))
(96,9696,99
(0.1.1.2.2.2)
[48,24,48 48.99)
(0.2.2.0.2.2)
196.96,90 96, 96]
(4.0.0.4...))
996.96.96.96)
(0.1.1.2.222)
[48,24,48,95 96,4489999889
288
(0.2.2.0,2.)
[96,96,996 96]
(4,0,0,4,0,0)
[96,9696696]
(0,1,122.222)
[48,24,48,96 96, 98,96)
(0.0.0.0.4.4)
(3.3.7.24.3.57.2241
(4.0.0
124.24.24.24)
(0.2.2.0.2.2)
[24.24.24,24]
48
(0,2,2,0,2.2)
(24,24,24224)
(4,0.0,4.0.9)
[24.24,24.24]
(0,2,2002222)
[48.24,48,24]
(0.2.2.0.2.2)
124,24.24,241
(4.0.0.40.0))
[24,24,24.24]
(1.2.2.1.111)
[48,24.24]
336
(0.2,2.0222))
[24,24,2.24]
(8.0.0.0.0.0)
(0,2.2.0..22)
[48,24.48.24]
Table Ablation study on the hyperparameters for the 8-headed RSA- on ETTh; dataset. and correspond to the number of dilated and non-dilated cyclical REMs. And ş ="_" refers to the case where no dilated REMs are considered. Otherwise, 4 out of dilated REMs are considered. The MSEs are averaged over 5 repetitions.
2
0
2
0
2
0.997
0.962
0.878
1.071
1.072
1.066
1.254
1.183
1.089
1.507
1.382
1,239
0
0.455
0.472
0.430
0.586
0.561
0.572
0.800
0.795
0.994
0.895
1.048
0.946
0.475
0.505
0.414
0.558
0.548
0.584
0.772
0.806
1.005
1.076
1.150
0.895
0.521
0,511
0.422
0.473
0.467
0.469
0.777
0.753
0.879
1.192
1.198
1,060
pred window = 24
pred window = 48
pred window = 168
pred window = 336
E.2 REGULAR LANGUAGE LEARNING
The six types of regular language datasets are obtained from the github repository Transformer- Formal- Langaa-Languge 6 We briefly describe the rules these languages:
The Parity language contains the numbers (0, 1) with even number of 1 I's. For example,
the string 0110 belongs to the language but 01 11 does not.
The D,, language defined on the alphabets {a,b). The Dj language can be written using the regular expression (ab)*, where "x" represents the Kleene star operation. Then for n 2 1, D, can be expressed by the recursive relationship D,, (aDn-1 We choose Da and Da, where D2 (a(ab)"b) and D4 = (a(a( (o(a(a((a) baab)"")"""****
The Tomita languages also use the numbers (0. 1) and include seven different grammars. In our experiment, we choose Tomita 3, 5 and 6. In Tomita 3, consecutive I's must be of an odd number and consecutive O's must be of an even number. In Tomita 5, the total numbers of I's and 0's must both be even. Finally, Tomita 6 requires the difference between the total number of I's and (I's to be a multiple of 3.
In this experiment, we adopt simple setting with layers and 5 heads for all models. The embedding size is set to 20. During training, the Adam optimizer is initialized at 0.005 with 0.5x decay every 5 epochs. And all models are run for 25 epochs without early stopping. Both the training set and bin O contain samples with length in the range of [2, 50) for Parity and Tomita, and [2, 100] for D... while bin contains longer test samples with length in the range of [51, 100) for Parity and Tomita, and [101, 200] for D,.. The models are trained on 10K samples and tested on 2K samples per bin for Parity and Tomita, and trained on 5K samples with 1K test samples per bin for D,, Following Bhattamishra al. (2000), train the models as below: starting from the first position of input sequence, the model outputs a string of possible characters for the next position, and this continues
'The link to the repnsitory is http:///ittalaccomssss////////aa Langaeaaanggaggggssssssaaaasaae under MIT license.
21

---

Published as a conference paper at ICLR 2023
encoderlayyy eyer Lself attention
encoderlayee eyer2..sef attention
decoder.eyerr byyrllself sttention
CIUSS attention
0.734
2,504
0:731
0.22
0.737
0.495
0.731
Sp001g
opacns
(4l inttallieed
pi inttallieed
(40 inttiialll
Figure 10: (a) (c) report the change in a(u) at each attention layer during training. where is initialized at -, 0, and 1, respectively. An 8-headed RSA-Informer applied to the ETTh, dataset with settings reported in Table The prediction window size equals to 24.
(a) Partt:
(b)
(c) b;
3:0
010010
000660116611
110001:110 00o0:11111100
Figure 11:
We visualize four recurrent patterns provided by the RSA heads on different languages (top), and their corresponding output, averaged over embedding dimension (bottom). The correspond- ing input sequence is given on æ-axis.
until the sequence is exhausted. The prediction task is recast into classfication task, where the prediction is deemed success if and only the output values at each position are correct, and failure otherwise.
From Table we can see that the Transformer-onk models may require much more training samples to learn these patterns. Moreover, when the training samples shorter than the test samples, they will have difficulty in extending the learned patterns to longer sequences, even with absolute or learned relative positional encoding. Meanwhile, REMs can easily extend its learned patterns to any sequence length, which may account for the better generalization ability of RSA-Transformec help interpret the results in Table 2 we provide some visualizations of the learned recurrent patterns on different languages in Figure and then decide whether 1) that leads to regular oscillations when encountering an even odd number of I's. Tomita has an additional requirement that the number of is also even, and hence learning can be assisted by dilated patterns; see (b) for illustration. Although Tomita 6 is more complicated, the regular cyclical patterns at (c) seems sufficient for it to learn well. This gives us glimpse of how the CSA-Transformer manages to learn the regular languages.
To
Learning Parity requires the model to count the number of 1 I's, an even number. Its recurrent pattern at (a) mainly consists of alternating
E.3
CODE AND NATURAL LANGUAGE MODELING
For RSS-madl our code based on the original CodeT5, which can be referred to in the repository /tttps://
com/ s walesforce// CodeT5
For the RSA-XL models adopted for the natural language modeling, only some of the heads are replaced with the RSA heads, while the remaining ones are still the original XL heads.
In the RSA-BRT and baseline BRT models, the recurrent layer put the third layer counted from the top, i.e., the recurrent layer is at layer 12 for 14-layer models and at layer 14 for 16-layer models. The nonrecurrent layers are of the same structure RSA-XL and XL respectively.
In Table 7 report the detailed hyperparameters settings for the RSA and their baseline models used Table 3, where "n RSA _SA_heads" refers to the number heads that are changed to the RSA heads.
22

---

Published as a conference paper at ICLR 2023
Table 7: The hyperparameter settings for the RSA and their baseline models used Table
Dutasct
Model
layyerr
nchaass
R_RSs_bedds
R.init
#Params
CodeT5-smaall
60492288
Devign
-SA-aaleTS-mmall
12
8
00,00.8.0.00
64
3
60492:99
Text8
RSA-XL
14
4
(0.0.0.0,222))
6,6,12,12
47789665
BRT
55464987
RSA-BRT
4
(0.0.0.0.222)
5,5,10,10
55165052
XL
47880396
Enwik8
RSA-XI
(0,000,0.222))
3,6,9,12
478801666
BRT
14
55555788
RSA-BE BR
4
(0.0...0.222))
3,6,9.12
55555653
XL
153797302
WikiText- 103
RSA-XI XL
12
(0.0002..222))
12.24.12.24.2.22
153797414
159627039
RSA-BR BR
16
12
6
(0.0.0.2,2.2)
12.24.12.24.2.22
-2
159627144
1.13
BRT
1.11
1.10
1.08
Number parameters (M)
Figure 12: Bit-per- Bit-per-character for BRT and RSA-BRT with respect to the model size (i.c. number of parameters millions) on Enwik8.
E,4 ABLATION STUDY
This subsection contains additional ablation experiment to compare the parameter efficiency of Block Recurrent Transformer (BRT) against its RSA variant i.e. RSA-BRT, and implementation details of the sequence length ablation study.
We conduct an additional experiment to compare the scaling performance of RSA-BRT and BRT with respect the number parameters Enwik8 dataset. Specifically, the number of layers in both models varies in [8, 10, 12, 14], and the training schemes for NI.P task in Section 4 is adopted. From the results presented in Figure T2] can be observed that RSA-BRT consistently achieves better performance than its bascline.
Next, we provide implementation details for sequence length scaling experiement. For all four models (i.e. BRT, TLB, RSA-BRT, RSA-TLB)), layer transformer with 8 attention heads trained using a batch size of 16 and the Adam optimizer with a learning rate of 0.0001 which is reduced by half every 5 epochs for BRT and RSA-BRT.
23


Reviews:
[{"review_id": "yHyVx8ZKWON", "reviewer": "Reviewer_ZrmK", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 small-scaled sequential data, transformers tend to overfit, while RNNs has better inductive bias that prevents the overfitting. However, RNN can't be trained in a parallel way like transformers. In this work, the authors find that a linear RNN has a simple form of masked linear aggregation, which can be formulated as a specific self-attention module, thus can be easily incorporated in to transformers and jointly trained in a parallel way. The authors propose to combine regular self-attention and RNN module together, and use a gating function to decide the weight of the two paths, making it possible to fit data with different scales. Experiments on several sequential modeling tasks show the advantage of the proposed combination of transformers and RNNs.", "summary_of_the_review": "Overall the paper is solid in both theoretical and empirical parts, although comparisons to the baseline models are missing.", "strength_and_weaknesses": "+ The motivation is clear and the algorithm is sensible.\n\n+ The proposed method is tested on several benchmarks.\n\n- RNN block discussed in the paper is basically a masked linear aggregation of the tokens (``masked'' means each token can only attend to the previous tokens), with the aggregation weights ($P_{mask}$) specially designed. It would be helpful if the authors can compare to the baseline where the $P_{mask}$ is learnable, i.e., using a learnable masked linear aggregation. Another baseline would be a learnable unmasked linear aggregation. These comparisons can tell us if it's the RNN formulation that matters or just the linear aggregation.\n\n- The authors argue that, transformers on small-scale recurrent data will overfit, thus introducing the RNN module which has a better inductive bias can help prevent the overfitting. However, there is a learnable gate-control parameter to decide whether the model should rely more on self-attention or RNN. Won't that encourage the model to rely more on self-attention in order to overfit the training data?\n\n- Since the authors use a linear RNN, I wonder how much model capacity are we losing by linearizing the RNN, i.e., how huge is the gap between linear and non-linear RNN, performance-wise?\n\n- In Section 3, the authors denote by $p_{total}$ the total temporal patterns in the data. How is this value defined?\n\n- Section 2.1, $b \\in \\mathbb{R}^{d_{in}}$ -> $b \\in \\mathbb{R}^{d}.\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": "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": "LVq6RJH4O-3", "reviewer": "Reviewer_f1my", "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": "Transformers have less inductive bias; while it is well generalized. RNNs have large inductive bias; while it is sample-efficient. Authors proposed the REM which combines the advantages of Transformer and RNNs which are famous sequential models. Experimental results have shown the effectiveness of the proposed model.\n", "summary_of_the_review": "I think the novelty of this draft is enough for the publication and the experimental results are impressive. English is good enough as well. I recommend weak accept for the draft.\n", "strength_and_weaknesses": "It is novel enough to combine the advantages of two famous models (Transformer, RNN). Also, the combining method looks applicable to a variety of scenarios. The experimental results are impressive, showing superior performance to previous Transformer.\n\nI think the draft would become better if there is a more complete explanation and figures about the self-attention with recurrence (RSA) operation. \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": "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": "F19iOIELCf9", "reviewer": "Reviewer_mvWh", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper tackles the problem of endowing Transformers with the ability to encode information about the past via recurrence. The proposed architecture can leverage the recurrent connections to improve the sample efficiency while maintaining expressivity due to the use of self-attention. ", "summary_of_the_review": "The paper proposes a way to incorporate recurrence and self-attention by modifying the positional encoding. ", "strength_and_weaknesses": "Strengths:\n\n- The paper is easy to read, and generally well written.\n- The paper evaluates the proposed method on various different tasks such as time-series forecasting, code and language modelling. The paper augments the proposed method to various different transformer variants and compares the performance with respect to the unmodified baseline. \n\nWeakness:\n\n- The problem of integrating recurrence and self-attention is an important research problem. There exists some existing ways on how to augment transformers with recurrence such as Temporal Latent Bottleneck [1] and Block-Recurrent Transformers [2]. The idea behind TLB is to \"divide\" the sequence into chunks, and within a chunk use self-attention and to access information across chunks the model needs to use recurrence. It would be useful to compare the proposed method to these variants to futher analyse the pros and cons. \n- It may also be useful to study the proposed method by varying the capacity of the network to see how well the underlying idea scales. \n\n[1] Temporal Latent Bottleneck: Synthesis of Fast and Slow Processing Mechanisms in Sequence Learning, https://arxiv.org/abs/2205.14794 (NeurIPS'22) \\\n[2] Block Recurrent Transformers, https://arxiv.org/abs/2203.07852 (NeurIPS'22)", "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": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%