Pyraformer: Low-Complexity Pyramidal Attention for Long-Range Time Series Modeling and Forecasting
Authors: Shizhan Liu
Hang Yu
Cong Liao
Jianguo Li
Weiyao Lin
Alex X. Liu
Schahram Dustdar
Venue: ICLR 2022 Oral (2022)
Keywords: sparse attention
pyramidal graph
Transformer
time series forecasting
long-range dependence
multiresolution

Abstract: Accurate prediction of the future given the past based on time series data is of paramount importance, since it opens the door for decision making and risk management ahead of time. In practice, the challenge is to build a flexible but parsimonious model that can capture a wide range of temporal dependencies. In this paper, we propose Pyraformer by exploring the multiresolution representation of the time series. Specifically, we introduce the pyramidal attention module (PAM) in which the inter-scale tree structure summarizes features at different resolutions and the intra-scale neighboring connections model the temporal dependencies of different ranges. Under mild conditions, the maximum length of the signal traversing path in Pyraformer is a constant (i.e., $\mathcal O(1)$) with regard to the sequence length $L$, while its time and space complexity scale linearly with $L$. Extensive numerical results show that Pyraformer typically achieves the highest prediction accuracy in both single-step and long-range forecasting tasks with the least amount of time and memory consumption, especially when the sequence is long.

Published as a conference paper at ICLR 2022
PYRAFORMER: LOW-COMPLEXITY PYRAMIDAL AT- TENTION FOR LONG-RANGE TIME SERIES MODELING AND FORECASTING
Shizhan Liu Hang Yu'; Cong Liao", Jianguo Li Weiyao Lin", Alex X. Liu',
and Schahram Dustdar
Ant Group, Shanghai Jiaotong University, TU Wien, Austria
ABSTRACT
Accurate prediction of the future given the past based on time series data is of paramount importance, since it opens the door for decision making and risk man- agement ahead of time. In practice, the challenge is to build a flexible but parsi- monious model that can capture wide range of temporal dependencies. In this paper, we propose Pyraformer by exploring the multi-resolution representation of the time series. Specifically, we introduce the pyramidal attention module (PAM) in which the inter-scale tree structure summarizes features at different resolutions and the intra-scale neighboring connections model the temporal dependencies different ranges. Under mild conditions, the maximum length of the signal travers- ing path in Pyraformer is a constant (i.e., O(1)) with regard to the sequence length L, while its time and space complexity scale linearly with L. Extensive experi- mental results show that Pyraformer typically achieves the highest prediction ac- curacy in both single-step and long-range multi-step forecasting tasks with the least amount of time and memory consumption, especially when the sequence is long"]
INTRODUCTION
Time series forecasting is the cornerstone for downstream tasks such as decision making and risk management. As an example, reliable prediction of the online traffic for micro-services can yield early warnings of the potential risk in cloud systems. Furthermore, also provides guidance for dynamic resource allocation, in order minimize the cost without degrading the performance. In addition to online traffic, time series forecasting has also found vast applications in other fields, including disease propagation, energy management, and economics and finance.
The major challenge of time series forecasting lies in constructing a powerful but parsimonious model that can compactly capture temporal dependencies of different ranges. Time series often exhibit both short-term and long-term repeating patterns (Lai et al.) 2018). and taking them into account is the key accurate prediction. Of particular note is the more difficult task of handling long-range dependencies, which is characterized by the length of the longest signal traversing path (see Proposition 2 for the definition) between any two positions in the time series (Vaswani al., 2017). The shorter the path, the better the dependencies are captured. Additionally, to allow the models to learn these long-term patterns, the historical input to the models should also be long. To this end, low time and space complexity is priority.
Unfortunately, the present state-of-the-art methods fail accomplish these two objectives simul- taneously. On one end, RNN (Salinas et al. 2020) and CNN (Munir et al. (018)) achieve a low time complexity that is linear terms of the time series length I., yet their maximum length of the signal traversing path is (L),, thus rendering them difficult to learn dependencies between distant positions. On the other extreme, Transformer dramatically shortens the maximum path to be O1))
"Equal contribution. This work done when Shizhan Liu was research intern at Ant Group
1 'Corresoonding author
Code is available at: http:///gthhbbcoomaaaag///rrooee

---

Published as a conference paper at ICLR 2022
Connectin examole
dignal beversing path
Attentiinn
Layer Emboddingg
Iidden States
Laper Entesciins
Fibeiddigs
Inpues
Emtbedzinngs
I6IETC
Layer Fiteedings
Layer2 Entedsings
Layer Fibeedings
Irpet Embeddings
Figure 1: Graphs of commonly used neural network models for sequence data.
Table 1: Comparison the complexity and the maximum signal traveling path for different models, where G' is the number of global tokens in ETC. In practice, the G' increases with L, and so the complexity of ETC is super-linear
Method
Complexity per layer
Maximum path length
CNN Munir ct al.
2018
O(L)
(L))
RNN Salinas et al.
2020
O(L)
O(L)
Full-Attentio
(aaswani et
2017
O(L?)
O(1)
ETC Ainslie
2020
O(GL))
0(1)
Longformer Beltagy ct al.
2020
O(L)
O(L)
LogTrans Li et al. 2019
O(Llog L)
L)
Pyraformer
O(L)
0(1)
at the sacrifice of increasing the time complexity to ( As a consequence, it cannot tackle very long sequences. To find compromise between the model capacity and complexity, variants of Transformer are proposed, such as Longformer (Beltagy et al., 2020). Reformer (Kitaev et al., 2019, and Informer (Zhou et al., 2021). However, few of them can achieve maximum path length less than (L) while greatly reducing the time and space complexity.
In this paper, we propose novel pyramidal attention based Transformer (Pyraformer) to bridge the gap between capturing the long-range dependencies and achieving low time and space com- plexity. Specifically, we develop the pyramidal attention mechanism by passing messages based on attention in the pyramidal graph as shown in Figure [d). The edges in this graph can be divided into two groups: the inter-scale and the intra-scale connections. The inter-scale connections build multiresolution representation of the original sequence: nodes at the finest scale correspond to the time points in the original time series (e.g.. hourly observations), while nodes the coarser scales represent features with lower resolutions (e.g., daily, weekly, and monthly patterns). Such latent coarser-scale nodes are initially introduced via a coarser-scale construction module. On the other hand, the intra-scale edges capture the temporal dependencies each resolution by connecting neighboring nodes together. As a result, this model provides a compact representation for long-range temporal dependencies among far-apart positions by capturing such behavior coarser resolutions, leading to smaller length of the signal traversing path. Moreover, modeling temporal dependencies of different ranges different scales with sparse neighboring intra-scale connections significantly reduces the computational cost. In short, our key contributions comprise:
We propose Pyraformer to simultaneously capture temporal dependencies of different ranges in compact multi-resolution fashion. To distinguish Pyraformer from the state- of-the-art methods, we summarize all models from the perspective of graphs in Figure
Theoretically. we prove that by choosing parameters appropriately, the maximum path length of ((1) and the time and space complexity of O(T) can be reached concurrently. To
2

---

Published as a conference paper at ICLR 2022
highlight the appeal of the proposed model, further compare different models in terms of the maximum path and the complexity in Table !
Experimentally, we show that the proposed Pyraformer yields more accurate predictions than the original Transformer and its variants various real-world datasets under the sce- nario of both single-step and long-range multi-step forecasting, but with lower time and memory cost.
RELATED WORKS
2.1
TIME SERIES FORECASTING
Time series forecasting methods can be roughly divided into statistical methods and neural network based methods. The first group involves ARIMA (Box & Jenkins 1968) and Prophet (Taylor & Letham 2018 However, both of them need to fit each time series separately, and their performance pales when it comes to long-range forecasting.
More recently, the development of deep learning has spawned tremendous increase in neural net- work based time series forecasting methods, including CNN (Munir et al.) 2018), RNN (Salinas) al. 2020) and Transformer (Li et al. 2019). As mentioned in the previous section, CNN and RNN enjoy a low time and space complexity (i.e., O(L)), but entail path of (L) to describe long-range dependence. We refer the readers to Appendix for a more detailed review on related RNN-based models. By contrast, Transformer (Vaswani et al. 2017) can effectively capture the long-rann range de- pendence with a path of (1) steps, whereas the complexity increases vastly from (L) to O (L)) To alleviate this computational burden, LogTrans (Li et al. 2019) and Informer (Zhou et al 2021 are proposed: the former constrains that each point in the sequence can only attend to the point that is 2" steps before it, where
2, and the latter utilizes the sparsity of the attention score, resulting in substantial decrease in the complexity (i.e., O(L log L) at the expense of introducing a longer maximum path length.
2.2 SPARSE TRANSFORMERS
In addition the literature on time series forecasting, plethora of methods have been proposed for enhancing the efficiency of Transformer in the field of natural language processing (NLP). Similar CNN, Longformer (Beltagy et al.) (020) computes attention within local sliding window or dilated sliding window. Although the complexity is reduced to O(AZ), where A is the local window size, the limited window size makes it difficult to exchange information globally. The consequent maximum path length is AT) As an alternative, Reformer (Kitaev et al. 2019) exploits locality sensitive hashing (LSH) to divide the sequence into several buckets, and then performs attention within each bucket. It also employs reversible Transformer to further reduce memory consumption, and so an extremely long sequence can be processed. Its maximum path length is proportional to the number of buckets though, and worse still, large bucket number is required reduce the complexity. On the other hand, ETC (Ainslie et al. 2020) introduces an extra set of global tokens for the sake of global information exchange, leading to (GL) time and space complexity and an ((1) maximum path length, where G is the number of global tokens. However, G typically increases with L, and the consequent complexity is still super-linear. Akin ETC, the proposed Pyraformer also introduces global tokens, but in multiscale manner, successfully reducing the complexity to (I.) without increasing the order of the maximum path length as the original Transformer.
2.3 HIERARCHICAL T'RANSFORMERS
Finally, we provide a brief review on methods that improve Transformer's ability to capture the hierarchical structure of natural language, although they have never been used for time series fore- casting. HIBERT (Miculicich et al.) 2018) first uses a Sent Encoder to extract the features a sentence, and then forms the EOS tokens of sentences in the document as new sequence and input it into the Doc Encoder. However, it is specialized for natural language and cannot be generalized to other sequence data. Multi-scale Transformer (Subramanian et al. 2020) lears the multi-scale representations of sequence data using both the top-down and bottom-up up network structures. Such multi-scale representations help reduce the time and memory cost of the original Transformer, but
3

---

Published as a conference paper at ICLR 2022
Prediction Strategy 1
Positional Encoding
Gather Features
Output Predictions
Nx
Add & Norm
Linear
Observations+
Observation Embedding
Feed Forward
CSCM
Prediction Strategy
Covariates
Covariates Embedding
Add &
Attention Decoder
Output Predictions
Linear
PAM
The architecture of Pyraformer: The CSCM summarizes the embedded sequence differ- ent scales and builds a multi-resolution tree structure. Then the PAM is used to exchange information between nodes efficiently.
Figure 2:
it still suffers from the pitfall of the quadratic complexity. Alternativey, BP- Teaanfooorrrr YYe al, 2019) recursively partitions the entire input sequence into two until a partition only contains a single token. The partitioned sequences then form binary tree. In the attention layer, each upper-scale node can attend to its own children, while the nodes at the bottom scale can attend to the adjacent A nodes at the same scale and all coarser-scale nodes. Note that BP- Transfoffrrm initializes the nodes at coarser scale with zeros, whereas Pyraformer introduces the coarser-scale nodes using a construc- tion module in more flexible manner. Moreover, BP-Transformer associated with denser graph than Pyraformer, thus giving rise to higher complexity of OLL log L).
3 METHOD
The time series forecasting problem can be formulated as predicting the future M steps 2 given the previous steps of observations 2t-++1: and the associated covariates 14-L+11:++ (e.g., hour-of-the-day), To move forward to this goal, we propose Pyraformer in this paper, whose overall architecture is summarized in Figure shown the figure, we first embed the observed data, the covariates, and the positions separately and then add them together, in the same vein with Informer (Zhou et al., 202T). Next, we construct a multi-resolution C-ary tree using the coarser- scale construction module (CSCM), where nodes at coarser scale summarize the information of nodes at the corresponding finer scale. To further capture the temporal dependencies of different ranges, introduce the pyramidal attention module (PAM) by passing messages using the attention mechanism in the pyramidal graph. Finally, depending on the downstream task, we employ different network structures to output the final predictions. In the sequel, we elaborate on each part of the proposed model. For ease of exposition, all notations in this paper are summarized in Table
3.1 PYRAMIDAL. ATTENTION MODULE (PAM)
We begin with the introduction of the PAM, since it lies at the heart Pyraformer. As demonstrated in Figure d)), leverage pyramidal graph to describe the temporal dependencies of the observed time series a multiresolution fashion. Such a multiresolution structure has proved itself an effec- tive and efficient tool for long-range interaction modeling in the field of computer vision (Sun al. 2019 Wang et al. 2 and statistical signal processing (Choi et al. 2008 Yu et al. 2019). We can decompose the pyramidal graph into two parts: the inter-scale and the intra-scale connections. The inter-scale connections form a C-ary tree, in which each parent has C children. For example, if we associate the finest scale of the pyramidal graph with hourly observations of the original time series, the nodes at coarser scales can be regarded as the daily, weekly, and even monthly features of the time series. a consequence, the pyramidal graph offers a multi-resolltion representation of the original time series. Furthermore, it is easier to capture long-range dependencies (e.g., monthly dependence) in the coarser scales by simply connecting the neighboring nodes via the intra-scale connections. In other words, the coarser scales are instrumental in describing long-range correla- tions in manner that is graphically far more parsimonious than could be solely captured with a sin- gle, finest scale model. Indeed, the original single-scale Transformer (see Figure [[a)) adopts full graph that connects every two nodes at the finest scale so as to model the long-ran long-range dependencics, leading computationally burdensome model with ( time and space complexity (Vaswani
4

---

Published as a conference paper at ICLR 2022
et al. 2017). In stark contrast, illustrated below, the pyramidal graph in the proposed Pyraformer reduces the computational cost to (L) without increasing the order of the maximum length of the signal traversing path.
Before delving into the PAM, we first introduce the original attention mechanism. Let X and Y denote the input and output of single attention head respectively. Note that multiple heads can be introduced to describe the temporal pattern from different perspectives. X is first linearly trans- formed into three distinct matrices, namely, the query
X XWQ. the key K X XWK. and the value V X Wv, where Wq. WK. Wv TRLxDR For the i-th qi in Q, it can attend to any rows (i.e., keys) in K. In other words, the corresponding output yi can be expressed as:
L explq.k? /VDx//D/ v
y: - Σ 1=1 Ei=1en ex /ilaa////VDD /Dk))
where kr denotes the transpose of row in K. We emphasize that the number of query-key dot products (Q-K pairs) that need to be calculated and stored dictates the time and space complexity of the attention mechanism. Viewed another way, this number is proportional to the number of edges in the graph (see Figure [ Since all Q-K pairs are computed and stored in the full attention mechanism TT. the resulting time and space complexity is ((L²).
As opposed the above full attention mechanism, every node only pays attention a limited set of keys in the PAM, corresponding to the pyramidal graph in Figure 1d. Concretely, suppose that (s) denotes the ε-th node at scale 8, where sequentially. In general, each node in the graph can attend to a set of neighboring nodes N(*) at three scales: the adjacent A nodes the same scale including the node itself (denoted as A,()), the C' children it has in the C-ary tree (denoted as c(,),, and the parent of it in the C-ary tree (denoted ) that is,
1, , represents the bottom scale the top scale
N(0) A uCt UP(()
A (m/") =1 f 1-1 d
C( (n(--));( <(= (C) if 2 2 clse 0
P! (n) :j= (-=(š1} if S else 0
It follows that the attention at node ni (0) can be simplified as: explg;k?"' Vdx)er E EvENTO explq.k) /dx))
yi Σ
EEN!))
We further denote the number of attention layers as N. Without loss of generality, we assume that L is divisible by CS-1 We can then have the following lemma (cf. Appendix B for the proof and Table 4 for the meanings of the notations).
Lemma 1. Given A, C, L, N, and S that satisfy Equation 44, after N stacked attention layers, nodes at the coarsest scale can oblain a global receptive field.
CS-1 -15 (A 1)N
L
(4)
2
In addition, when the number of scales S is fixed, the following two propositions summarize the time and space complexity and the order of the maximum path length for the proposed pyramidal attention mechanism. We refer the readers to Appendix C Cand for proof.
Proposition 1. The time and space complexity for the pyramidal attention mechanism is O(AL) for given A and L and amounts ((L) when A is constant w.r.t. L.
Proposition 2. Let the signal traversing path between two nodes in a graph denote the shortest path connecting them. Then the maximum length of signal traversing path between two arbitrary nodes the pyramidal graph is O(S + L/CS-1/AN /A) for given A, C, L, and S. Suppose that A and are fixed and C sutisfies Equation 5) the muximum path length is ((1) for time series with length L.
L
VVV2222
(5)
1 (A-1))//2
5

---

Published as a conference paper at ICLR 2022
8xLxD
Bxixdy
EX(C/C)xBy
Conv with stride
Inouts
Linear
Linear
DxL + 1/0 6/67 + +2/0))0
Conv with stride
Corv with stride
Figure 3: Coarser-scale construction module: B is the batch size and D is the dimension of node.
In our experiments, we fix S and N, and A can only take 3 or 5, regardless of the sequence length L. Therefore, the proposed PAM achieves the complexity of O(L) with the maximum path length of ((1). Note that in the PAM, a node can attend to at most A + C + nodes. Unfortunately, such a sparse attention mechanism not supported in the existing deep learning libraries, such as Pytorch and TensorFlow. A naive implementation of the PAM that can fully exploit the tensor operation framework is to first compute the product between all Q-K pairs, i.c., q for =
1,... L. and then mask out & &f N!". However, the resulting time and space complexity of this implementation is still O(L²). Instead, we build customized CUDA kernel specialized for the PAM using TVM (Chen et al,, 2018), practically reducing the computational time and memory cost and making the proposed model amenable to long time series. Longer historical input is typically helpful for improving the prediction accuracy, as more information is provided, especially when long-range dependencies considered.
3.2 COARSER-SCALE CONSTRUCTION MODULE (CSCM)
CSCM targets at initializing the nodes at the coarser scales of the pyramidal graph, so as to facilitate the subsequent PAM exchange information between these nodes. Specifically, the coarse-scale nodes are introduced scale by scale from bottom to top by performing convolutions on the corre- sponding children nodes c(a) As demonstrated in Figure several convolution layers with kernel size C' and stride C' are sequentially applied to the embedded sequence in the dimension of time, yielding sequence with length L/C" at scale s. The resulting sequences different scales form C-ary tree. We concatenate these finetto-caarse sequences before inputting them to the PAM. In order to reduce the amount of parameters and calculations, we reduce the dimension of each node by fully connected layer before inputting the sequence into the stacked convolution layers and restore after all convolutions. Such a bottleneck structure significantly reduces the number of parameters in the module and can guard against over-fitting.
3.3 PREDICTION MODULE
For single-step forecasting, we add an end token (by setting 24+1 = 0) to the end of the historical sequence 4-L+1a before inputting it into the embedding layer. After the sequence is encoded by the PAM, we gather the features given by the last nodes at all scales in the pyramidal graph, concatenate and then input them into fully connected layer for prediction.
For multi-step forecasting, we propose two prediction modules. The first one is the same with the single-step forecasting module, but maps the last nodes all scales to all M future time steps in a batch. The second one, on the other hand, resorts to a decoder with two full attention layers. Specifically, similar to the original Transformer (Vaswani al.) 2017), we replace the observations at the future Mf time steps with O, embed them in the same manner with the historical observations, and refer to the summation of the observation, covariate, and positional embedding as the "prediction token" Fz- The first attention layer then takes the prediction tokens F, as the query and the output of the encoder F. (i.e., all nodes the PAM) as the key and the value, and yields Fan. The second layer takes Fa the query, but takes the concatenated Fai and F. as the key and the value. The historical information F, fed directly into both attention layers, since such information vital for accurate long-range forecasting, The final prediction is then obtained through fully connected layer across the dimension of channels. Again, we output all future predictions together to avoid the problem of error accumulation in the autoregressive decoder of Transformer.

---

Published as a conference paper at ICLR 2022
Table 2: Single-step forecasting results three datasets. "Q-K pairs" refer the number of query- key dot products performed by all attention layers in the network, which encodes the time and space complexity. We write the number of attention layers by N. the number of attention heads by H, the number of scales by S, the dimension of node by D. the dimension of a key by Dx. the maximum dimension of ferd-forward layer by Dr, and the convolution stride by C.
Methods
Parameters
Datasets
NRMSE
ND
Q-K pairs
Electricity
0.328
0.041
456976
Full-attention
O(NHDDR DD+))
Wind
0.175
0.082
589824
App Flow
0.407
0.080
589824
Electricity
0.333
0.041
50138
LogTrans
((((DDx=DD+))
Wind
0.173
0.081
58272
App Flow
0.387
0.073
58272
Electricity
0.359
0.047
677376
Reformer
D((HDDD-DDD))
Wind 0.183
0.086
884736
App Flow
0.463
0.095
884736
Electricity
0.324
0.041
79536
ETC
O DDr))
Wind
0.167
0.074
102144
App Flow
0.397
0.069
102144
Electricity
0.330
0.041
41360
Longformer
O( DD+))
Wind
0.166
0.075
$2608
App Flow
0.377
0.07
$2608
Electricity
0.324
0.041
17648
O(N(DDRR + DDF) +(8 (18-1JCD) I)CD$)
Pyraformer
Wind
0.161
0.072
20176
App Flow
0.366
0.067
20176
4 EXPERIMENTS
4.1 DATASETS AND EXPERIMENT SETUP
We demonstrated the advantages of the proposed Pyraformer on the four real-world datasets, in- cluding Wind, App Flow, Electricity, and ETT. The first three datasets were used for single-step forecasting, while the last two for long-range multi-step forecasting. We refer the readers to Ap- pendix E and Forr for more details regarding the data description and the experiment setup.
4.2
RESULTS AND ANALYSIS
4.2.
SINGLE-STEP FORECASTING
We conducted single-step prediction experiments on three datasets: Electricity, Wind and App Flow.
The historical length is 169, 192 and 192, respectively, including the end token. We benchmarked Pyraformer against other attention mechanisms, including the original full-attention (Vaswani ct al., 2017). the log-sparse attention (i.e., LogTrans) (Li al. (219). the LSH attention (i.c., Re- former) (Kitaev et al.] 2019), the sliding window attention with global nodes (i.e., ETC) (Ainslic) al. 2020), and the dilated sliding window attention (i.e., Longformer) (Beltagy et al. 2020). In particular for ETC, some nodes with equal intervals at the finest scale were selected as the global nodes. A global node can attend to all nodes across the sequence and all nodes can attend to in turn(see Figure ())). The training and testing schemes were the same for all models. We fur- ther investigated the usefulness of the pretraining strategy (see Appendix G the weighted sampler, and the hard sample mining all methods, and the best results were presented. We adopted the NRMSE (Normalized RMSE) and the ND (Normalized Deviation) as the evaluation indicators (see Appendix H for the definitions). The results summarized in Table 2 For fair comparison, except for full- -ateeattenion, the overall dot product number of all attention mechanisms was controlled to the same order of magnitude.
Our experimental results show that Pyraformer outperforms Transformer and its variants in terms of NRMSE and ND, with the least number of query-key dot products (a.k.a. Q-K pairs). Con-

---

Published as a conference paper at ICLR 2022
Table 3: Long-range multi-step forecasting results.
ETTh1
ETTml
Electricity
Methods
Metries
168
336
720
96
288
672
168
336
720
MSE
1.075
1.329
1.384
0.556
0.841
0.921
0.745
1,579
4.365
Informer
MAE
0.801
0.911
0.950
0.537
0.705
0.753
0.266
0.323
0.371
Q-K pairs
188040
188040
423360
276480
560640
560640
188040
188040
423360
MSE
0.983
1,100
1.411
0.554
0.786
1.169
0.791
1.584
4.362
LogTraas
MAE
0.766
0.839
0.991
0.499
0.676
0.368
0,340
0.336
0.366
Q-K pairs
74664
74664
216744
254760
648768
648768
74664
74664
216744
MSE
0.860
0,975
1.091
0.526
0.767
1.021
0.766
1,591
4.361
Longformer
MAE
0.710
0.769
0.832
0.507
0.663
0.788
0.311
0.343
0.368
Q-K pairs
63648
63648
249120
329760
1007136
1007136
63648
63648
249120
MSE
0.958
1.044
1.458
0.543
0.924
0.981
0.783
1,584
4.374
Reformer
MAE
0.787
0.987
0.528
0.722
0.332
0.334
0.374
Q-K pairs
1016064
1016064
2709504
5308416
14450688
14450688
1016064
1016064
2709504
MSE
1.025
1.084
1.137
0.762
1.227
1.272
0.777
1,586
4.361
ETC
0.326
0.340
0.368
Q K pairs
125280
125280
288720
331344
836952
836952
125280
1 125280
288720
MSE
0.808
0.945
1.022
0.480
0.754
0.857
0.719
1.533
4.312
Pyraformer
MAE
0.683
0.766
0,806
0.486
0.659
0.707
0.256
0.291
0.346
Q-K pairs
26472
26472
74280
57264
96384
96384
26472
26472
74280
cretely, there are three major trends that can be gleaned from Table (1) The proposed Pyraformer yields the most accurate prediction results, suggesting that the pyramidal graph can better explain the temporal interactions in the time series by considering dependencies of different ranges. Inter- estingly, for the Wind dataset, sparse attention mechanisms, namely, LogTrans, ETC, Longformer and Pyraformer, outperform the original full attention Transformer, probably because the data tains a large number of zeros and the promotion of adequate sparsity can help avoid over- weet-fitting. (2) The number of Q-K pairs in Pyraformer is the smallest. Recall that this number character- izes the time and space complexity. Remarkably enough, it is 65.4% fewer than that of LogTrans Trans and 96.6% than that of the full attention. It is worth emphasizing that this computational gain will continue to increase for longer time series. (3) The number of parameters for Pyraformer is slightly larger than that of the other models, resulting from the CSCM. However, this module is very lightweight, which incurs merely 5% overhead in terms of model size compared to other models. Moreover, in practice, we can fix the saper-parameters A, 5 and N, and ensure that C' satisfies C> s- (V/ 1)N/2 + 1). Consequently, the extra number of parameters introduced by the CSCM is only O((S - 1)CD3> R O VL..
4.2.2 LONG-RANGE MULTI-STEP FORECASTING
We evaluated the performance of Pyraformer for long-range forecasting three datasets, that is, Electricity, ETTh1, and ETTm1. In particular for ETTh1 and ETTm1, we predicted the future oil temperature and the 6 power load features the same time, which is multivariate time series forecasting problem. Both prediction modules introduced in Section 3.3 were tested for all models and the better results are listed in Table
is evident that Pyraformer still achieves the best performance with the least number of Q-K pairs for all datasets regardless of the prediction length. More precisely, in comparison with In- former (hhou et al. 2021), the MSE given by Pyraformer for ETTh1 is decreased by 24.8%, 28 28.9%, 26.2% respectively when the prediction length is 168, 336, and 720. Once again, this bolsters our belief that it is more beneficial to employ the pyramidal graph when describing the temporal depen- dencies. Interestingly, we notice that for Pyraformer, the results given by the first prediction module are better than those by the second one. One possible explanation is that the second prediction mod- ule based on the full attention layers cannot differentiate features with different resolutions, while the first module based in an automated fashion. To better elucidate the modcling capacity Pyraformer for long-range forecasting, we refer the readers to Appendix for detailed example synthetic data.
single fully connected layer can take full advantages of such features
8

---

Published as a conference paper at ICLR 2022
Time
Memory
175
full attention
150-
spar-s attention
10
Pyraforme-TVV
125
ms/batch
100
6-
full attention
prob-sparse attention
Pyraformer- TV-
25
2-
0-
2000 4000 6000
100001 14000 sequence length
8000
2000 4000 6000 8060 10000 12000 4000 16000
sequence length (b)
(a)
Figure 4: Comparison of the time and memory consumption between the full, the prob-sparse, and
the TVM implementation of the pyramidal attention: (a) computation time; (b) memory occupation.
4.2.3 SPEED AND MEMORY CONSUMPTION
To check the efficiency of the customized CUDA kernel implemented based on TVM, we depicted the empirical computation time and memory cost as function of the sequence length L in Fig- ure 4 Here we only compared Pyraformer with the full attention and the prob-sparse attention in Informer (Zhou al. 2021). All the computations were performed with Ubuntu 16.04, CUDA 11.0, and TVM 0.8.0. Figure 4 shows that the time and memory cost of the proposed Pyraformer based TVM is approximately linear function of L, expected. Furthermore, the time and memory consumption of the TVM implementation can be several or- ders of magnitude smaller than that of the full attention and the prob-sparse attention, especially for relatively long time series. Indeed, for 12GB Titan Xp GPU, when the sequence length reaches 5800, full attention encounters the oft-orymemory (OOM) problem, yet the TVM implementation of Pyraformer only occupies IGB of memory. When it comes to a sequence with 20000 time points, even Informer incurs the OOM problem, whereas the memory cost Pyraformer only 1.91GB and the computation time per batch is only 0.082s.
12 GB Titan Xp GPU
4.3 A ABLATION STUDY
We also performed ablation studies to measure the impact of A and C, the CSCM architecture, the history length, and the PAM on the prediction accuracy of Pyraformer. The results are displayed in the results can be found in Appendix Here, only provide
Tables 10 Detailed Discussions an overview of the major findings: (1) it is better to increase C' with L but fix A to a small constant for the sake of reducing the prediction error; (2) convolution with bottleneck strikes balance between the prediction accuracy and the number of parameters, and hence, we use it as the CSCM; (3) more history helps increase the accuracy of forecasting; (4) the PAM essential for accurate prediction.
CONCLUSION AND OUTLOOK
In this paper, we propose Pyraformer, a novel model based on pyramidal attention that can effec- tively describe both short and long temporal dependencies with low time and space complexity. Concretely, we first exploit the CSCM to construct a C-ary tree, and then design the PAM to pass messages both the inter-scale and the intra-scale fashion. By adjusting C' and fixing other parame- ters when the sequence length L increases, Pyraformer can achieve the theoretical ((L) complexity and O()) maximum signal traversing path length. Experimental results show that the proposed model outperforms the state-of-the-an models for both single-step and long-range multi-step pre- diction tasks, but with less computational time and memory cost. So far we only concentrate on the scenario where A and S are fixed and C' increases with L when constructing the pyramidal graph. On the other hand, we have shown in Appendix I Ihht other configurations of the hyper- parameters may further improve the performance of Pyraformer. In the future work, would like to explore how to adaptively learn the hyper-parameters parameters from the data. Also, is interesting to extend Pyraformer to other fields, including natural language processing and computer vision.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENT
In this work, Prof. Weiyao Lin was supported by Ant Group through Ant Research Program and in part by National Natural Science Foundation of China under grant U21B2013.
REFERENCES
Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. Etc: Encoding long and structured inputs in transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 268-284, 2020.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05/50, 2020.
George EP Box and Gwilym M Jenkins. Some recent advances forecasting and control. Journal of the Royal Statistical Society, Series C (Applied Statistics), 17(2):91-109, 1968.
Shiyu Chang, Yang Zhang, Wei Han, Mo Yu, Xiaoxiao Guo, Wei Tan, Xiaodong Cui, Michael Witbrock, Mark Hasegawa-Johnson, and Thomas $ Huang. Dilated recurrent neural networks. Advances in Neural Information Processing Systems, 2017:77-87, 2017.
Tianqi Chen, Thieny Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, et al. (TVM): An automated end-to-end optimizing compiler for deep learning. In 13th {USENIX) Symposium on Operating Systems Design and Implementation ((OSDI) 18), pp. 578-594, 2018.
M. J. Choi, V. Chandrasekaran, D. M. Malioutov, J. K. Johnson, and A. S. Willsky, Multiscale stochastic modeling for tractable inference and data assimilation. Computer Methods in Applied Mechanics and Engineering, 197(43-44:3492-33111 2008.
Junyoung Chung, Sungjin Ahn, and Yoshua Bengio. Hierarchical multiscale recurrent neural net- works. In 5th International Conference on Learning Representations, ICLR 2017, 2019.
Marta R Costa-jussà and José AR Fonollosa. Character-based neural machine translation. In Pro- ceedings of the 54th Annual Meeting of the Association for Computational Linguistics ( (Volume 2: Short Papers), pp. 357-361, 2016.
Jacyoung Kim, Mostafa El-Khamy, and Jungwon Lee. Residual Istm:
Design of a deep recurrent architecture for distant speech recognition. arXiv preprint Xiv:17701.03660, 2017.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2019.
Guokun Lai, Wei-Cheng Chang, Yiming Yang, and Hanxiao Liu. Modeling long-and short-term temporal patterns with deep neural networks. In The s1 International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 95-104, 2018.
Shiyang Li, Xiaoyong Jin, Yao Xuan, Xiyou Zhou, Wenhu Chen, 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, 02:5243-5255 2019.
Lesly Miculicich, Dhananjay Ram, Nikolaos Pappas, and James Henderson. Document level neural machine translation with hierarchical attention networks. Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), number CONF, 2018.
Mohsin Munir, Shoaib Ahmed Siddiqui, Andreas Dengel, and Sheraz Ahmed. Deepant: A deep learning approach for unsupervised anomaly detection in time series. Ieee Access, 7:1991-2005, 2018.
David Salinas, Valentin Flunkert, Jan Gasthaus. and Tim Januschowski. Deepar: Probabilistic fore- casting with autoregressive recurrent networks. International Journal of Forecasting. 36(3): 1181- 1191, 2020.
10

---

Published as a conference paper at ICLR 2022
M. Schuster. Bi-directional recurrent neural networks for speech recognition. In Proceeding of IEEE Canadian Conference on Electrical and ComputerEnginnerring,, pp. 7-12, 1996.
Sandeep Subramanian, Ronan Collobert, Marc' Aurelio Ranzato, and Y-Lan Boureau. Multi-scale transformer language models. arXiv preprint arXiv:2005.000 00581, 2020.
Ke Sun, Bin Xiao, Dong Liu, and Jingdong Wang. Deep high-resolution representation learning for human pose estimation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5693-5703, 2019.
Sean J Taylor and Benjamin Letham. Forecasting at scale. The American Statistician, 72(1):37-45, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
W. Wang, E. Xie, Li, D. Fan, and L. Shao. Pyramid vision transformer: versatile backbone for dense prediction without convolutions. 2021.
Zihao Ye, Qipeng Guo, Quan Gan, Xipeng Qiu, and Zheng Zhang. Bp-transformer: Modelling long-range context via binary partitioning. arXiv preprint arXiv: 1XXv:0911.00070, 2019.
Hang Yu, Luyin Xin, and Justin Dauwels. Variational wishart approximation for graphical model selection: Monoscale and multiscale models. IEEE Transactions on Signal Processing, 67(24): 6468-6482, 2019,
doi: 10.1 10.110999P.2219.225552
Hsiang-Fu Yu, Nikhil Rao, and Inderjit $ Dhillon. Temporal regularized matrix factorization for high-dimensional time series prediction. Advances in neural information processing systems, 29: 847-855, 2016.
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.
Simiao Zuo Haoming Jiang, Zichong Li, Tuo Zhao, and Hongyuan Zha. Transformer hawkes process. In International Conference on Machine Learning, 11692-11702. PMLR, 2020.

---

Published as a conference paper at ICLR 2022
Table 4: Meanings of notations.
Notation
Size
Meaning
L
Constant
The length of historical sequence.
G
Constant
The number of global tokens in ETC.
M
Constant
The length of future sequence to be predicted.
B
Constant
Batch size.
D
Constant
The dimension of cach node.
Dr
Constant
The dimension of key.
X
B x L x D
Input of single attention head.
Y
B L D
Output of single attention head. The query.
Q
B X L X DR
K
B L DR
The key.
V
Bx L DR
The value.
We
x DR
The weight matrix of the query.
WK
D X DR
The weight matrix of the key. The weight matrix of the value.
Wv
D x DR
S
Constant
Number of scales.
A
Constant
Number of adjacent nodes at the same scale that a node can attend to.
C
Constant
Number finer scale nodes that a coarser scale node can summarize.
Constant
Number attention layers.
The f-th node scale s.
N
len(N!
The set of neighboring nodes node ni
A
len(A, (5))
The adjacent nodes the same scale with ni
len(C!"))
The children nodes of ni
P(
len(P!")) D
The parent node of ni (+)
F2
B M D
The prediction tokens.
F.
B Lint D
The output of the encoder. List represents the output length of the encoder.
Fa
B MXX
The output of the first attention-based decoder layer.
H
Constant
The number of attention heads.
DF
Constant
The maximum dimension of the feed-forward layer.
A
A BRIEF REVIEW ON RELATED RNN-BASER MODELS
In this section, we provide a brief review on the related RNN-based models. Multiscale tempo- ral dependencies are successfully captured in HRNN (Costa-jussà Fonollosal 2016) and HM- RNN (Chung et al. 2019). The former requires expert knowledge to partition the sequence into different resolutions, while the latter learns the partition automatically from the data. Note that the theoretical maximum length of the signal traversing path in both models is still O Another line of works aim to shorten the signal traversing path by adding residual connections (Kim et al. 2017) or dilated connections to LSTMs (Chang et al.) 2017). However, they do not consider the multires- olution temporal dependencies explicitly. Furthermore, all aforementioned RNNs only propagate information in one direction from the past the future. An appealing approach that allows bidirec- tional information exchange is Bi-LSTM (Schuster) 1996). The forward and backward propagation realized through different LSTSS though, and still incurs long signal traversing path.
12

---

Published as a conference paper at ICLR 2022
As opposed to the abovementioned RNN-based models, the proposed Pyraformer enables bidirec- tional information exchange that can better describe the temporal dependencies, while providing a multiresolution representation of the observed sequence at the same time. We also notice that due to the unidirectional property of RNNs, it is difficult the realize the pyramidal graph in Figure T based RNNs.
B PROOF OF LEMMA
Proof. Let S denote the number of scales in the pyramidal graph, C' the number of children nodes in the finer scale s that a node in the the coarser scale 8 can summarize for s = 2, S. A the number of adjacent nodes that node can attend to within each scale, N the number of attention layers, and the length of the input time series. We define the term "receptive field" an arbitrary node in graph as the set of nodes that na can receive messages from. We further define the distance between two arbitrary nodes in a graph as the length of the shortest path between them (i.e.. the number of steps to travel from one node to another). Note that in each attention layer, the messages can only travel by one step in the graph.
Without sacrificing generality, assume that L is divisible by CS-1, and then the number of nodes at the coarsest scale S L/CS-1, Since every node connected to A closest nodes at the same scale, the distance between the leftmost and the rightmost node at the coarsest scale is 2(L/CS-1 1)/(A - 1). Hence, the leftmost and the rightmost node in the coarsest scale are in the receptive field of each other after the stack of N 2(L/CS-1 1)/(A pyramidal attention. In addition, owing to the CSCM, nodes at the coarsest scale can be regarded as the summary of the nodes the finer scales. As result, when Equation (4) is satisfied, all nodes at the coarsest scale have a global receptive field, which closes the proof.
1) layers of the
C PROOF OF PROPOSITION 1
Proof. Suppose that [,() denotes the number of nodes at scale 8, that is,
L
I C
1sas S
For node n2 the pyramidal graph, the number of dot products p(() it acts as the query can be decomposed into two parts:
pl = p(+)
+ (())
inter
intra?
where p! intra and (())
inter denotes the intra-scale and the inter-scale part respectively. According to the structure of the pyramidal graph, have the following inequalities:
p(a)
inira < A,
(8)
pls)
inter CC+
(9)
The first inequality (8) holds since node typically attends to most adjacent nodes the same scale but for the leftmost and the rightmost node, the number of in-scale nodes it can attend to is smaller than A. On the other hand, the second inequality ( holds because node typically has C' children and 1 parent in the pyramidal graph but nodes the top and the bottom scale can only attend to fewer than C + 1 nodes at adjacent scales.
In summary, the number of dot products that need to be calculated for scale is:
((v)
pla) Σ (p(#) intra + p(s) inter) (A+CC))) E=1
(10)
Note that P(1) < L(A 1) for the finest scale (i.e., s 1) since nodes at this scale do not have any children. It follows that the number of dot products that need to be calculated for the entire pyramidal attention layer is:
g
P
p(s)
13

---

Published as a conference paper at ICLR 2022
(8) + (A+
S
8-1
L
C (-(a-1) A
(-(0-1)
Σ
(-(0=1) +
<((A+ 2) Σ (-(=-11) +1).
(11)
In order to guarantee that the nodes at the coarsest scale have a global receptive field, we choose C
such that C' x VT. Consequently, the complexity of the proposed pyramidal attention is:
O(P) O
(--1) + 1))
==1
O(L(+ 2)
Σ (-(+-1))
(A 21++))==-
0
L -1
AL
0
(12)
L
When L approaches infinity, the above expression amounts to O(AL). Since A can fixed when L changes, the complexity be further reduced to O(L).
D PROOF OF PROPOSITION 2
Proof. Let n represent the E-th node of the s-th scale. evident that the distance between ni (1) is the largest among all pairs of nodes in the pyramidal graph. The shortest path to travel
and n..
from nj to n is:
(9) m -
1.5
(S)
ni
(S-1) .... nt 1,S-1)
(13)
Correspondingly, the length of the maximum path between two arbitrary nodes in the graph is:
((L(5)) -1)
1)+ 1) Lmax = -
(14)
A-1
When C' satisfies Equation
5) that is, [S( -1 (4 - 1), we can obtain:
(L 0 2(S 1) ((L -
A-1
o 2(S - 1) + 2 C - 1)
A-1
- - +
O(S N
(15)
Since A, S and N are invariant with L, the order of the maximum path length Lmux be further simplified as O(1).
E DATASETS
We demonstrated the advantages of the proposed Pyraformer the following four datasets. The first three datasets were used for single-step forecasting, while the last two for long-range multi-step forecasting.
14

---

Published as a conference paper at ICLR 2022
This dataset contains hourly estimation of the energy potential in 28 countries between 1986 and 2015 as a percentage of a power plant's 's maximum output. Compared with the remaining datasets, it is more sparse and periodically exhibits large number of zeros. Due to the large size of this dataset, the ratio between training and testing set was roughly 32:1.
Wind
This dataset was collected at Ant Grouf It consists of hourly maximum traffic flow for 128 systems deployed on 16 logic data centers, resulting in 1083 different time series in total. The length of each series is more than 4 months. Each time series was divided into two segments for training and testing respectively, with a ratio of 32:1.
App Flow:
Electricity Yu al. 2016): This dataset contains time series of electricity consumption recorded every 15 minutes from 370 users. Following DeepAR (Salinas et al., 22020), we aggregated every 4 records get the hourly observations. This dataset was employed for both single-step and long- range forecasting. We trained with data from 201 1-01-01 to 2014-09-01 for single-step forecasting, and from 2011 2011-04-01 to 2014-04-01 for long-range forecasting.
ETT Zhou et al. 2021): This dataset comprises 2 years of 2 electricity transformers collected from stations, including the oil temperature and 6 power load features. Observations every hour (i.e., ETTh1) and every 15 minutes (i.e., ETTml) are provided. This dataset is typically exploited for model assessment on long-range forecasting. Here, we followed Informer (Zhou et al. 2021) and partitioned the data into 12 and 4 months for training and testing respectively.
F EXPERIMENT SETUP
We set S = 4 and N = 4 for Pyraformer in all experiments. When the historical length L is not divisible by C, we only introduced [T//C] nodes the upper scale, where [.] denotes the round down operation. The last I, - (L [LT/C]= 1)C' nodes at the bottom scale were all connected to the last node at the upper scale. For single-step forecasting, we set C = 4, A = 3, and H 4 in all experiments. Both training and testing used a fixed-size historical sequence to predict the mean and variance of the Gaussian distribution of a single future value. We chose the MSE loss and the log-likelling ligllikl (Zuo et al., 2020) our loss functions. The ratio between them was set to 100. For optimization, we used Adam with the learning rate starting from 10-5 and halving in every epoch. We trained Pyraformer with 10 epochs. Weighted sampler based on each window's average value and hard sample mining were used to improve the generalization ability of the network. On the other hand, for long-range forecasting, we tested four combinations of A and C in each experiment, and the best results were presented. Specifically, when the prediction length is smaller than 600, we tested A 3, 5 and C' 4, 5. When the prediction length larger than 600, we tested A 3, 5 and C = 5, 6. The resulting choice of hyper-parametert for each experiment is listed in Table 5 In addition, the loss function was the MSE loss only. We still used Adam as our optimizer, but the learning rate started from 10-4 and was reduced to one-tenth every epoch. We set the number of epochs to be
G PRETRAINING
For single-step forecasting, the value be predicted is usually close to the last value of history. Since we only use the last nodes of all scales to predict, the network tends to focus only on short- term dependencies. To force the network to capture long-range dependencies, we add additional supervision in the first few epochs of training. Specifically, in the first epoch, we form our network as an auto-encoder, as shown in Figure Apart from predicting future values, the PAM is also
Wind dataset can be downloaded at 'The App Flow dataset does not contain any Personal Identifiable Information and is desensi- tized and encrypted. Adequate data protection was carried out during the experiment to prevent the risk of data copy leakage, and the dataset was destroyed after the experiment. for academic research, it does not represent any real husiness situation. The download link is httph//hwww/m.mlp///a/a/reeeeeee
www.kkawgge...m//shrrr333000 wowp://---yaaar---ooroopaaaa wind-generattin
is only used
zone rpc hour enerypted.csw Flecttrcitty dataset can he downloaded at https://archive..e ies wtt../.........//aaaa//////tttra wad.iiiaaLLaDDiaaamaaea..
12011
'ETT dataset be downloaded hups:/// http:///htttb.oo//obaao///TTDea
15

---

Published as a conference paper at ICLR 2022
Table 5: Hyper-parameter settings of long-range experiments.
Dataset
prediction length
N
S
H
A
C
historical length
168
4
4
6
3
4
168
ETTh1
336
4
4
6
3
4
168
720
4
4
6
5
4
336
96
4
4
6
3
5
384
ETTml
288
4
4
6
5
5
672
672
4
4
6
3
672
168
4
4
6
3
4
168
Elect
336
4
4
6
3
4
168
720
4
4
6
3
5
336
Figure 5: The pretraining strategy for one-step prediction. Features of nodes surrounded by the dashed ellipses are concatenated to recover the corresponding input value.
trained recover the input values. Note that test all methods with and without this pretraining strategy and the better results are displayed in Table
H METRICS
Denote the target value 2μ, and the predicted value as &j.t, where j is the sample index and t is the time index. Then NRMSE and ND are calculated as follows:
Σ
T
(2z, 22,)2
NRMSE
(16)
NT EE= Σt 12
ND Σ - 12 2
N
(17)
En E1=1 Σt= Ezg.el
I EXPERIMENTS ON SYNTHETIC DATA
To further evaluate Pyraformer's ability to capture different ranges temporal dependencies, we synthesized an hourly dataset with multi-range dependencies and carried out experiments it.
16

---

Published as a conference paper at ICLR 2022
Specifically, each time series in the synthetic dataset is linear combination of three sine functions of different periods: 24, 168 and 720, that is,
2T 1) + 32 sin
2 1) + 33 sin(
2T
((1) = 30 + 81 sin(
720 1)-
(18)
24
168
In the above equation, the coefficients of the three sine functions 31. B2. and 33 for each time series are uniformly sampled from [5. 10). 30 is Gaussian process with covariance function Et,,, [t 121 121-1 and Σt, Σ₁g 1, where 1 and &2 denote two arbitrary time stamps. Such polynomially decaying covariance functions are known to have long-range dependence, as oppose to the exponentially decaying covariance functions (Yu et al. 2019). The start time of each time series to is uniformly sampled from [0, 719]. We first generate 60 time series of length 14400, and then split each time series into sliding windows of width 1440 with a stride of 24. In our experiments, we use the historical 720 time points predict the future 720 points. Since both the deterministic and stochastic parts of the synthetic time series have long-range correlations, such dependencies should be well captured in the model in order to yield accurate predictions of the next 720 points. The results are summarized in Table Here, we consider two different configurations of Pyraformer: 1) C' for all scales in the pyramidal graph (denoted as Pyraformere,,, C 12, 7, and 4 for the three layers sequentially from bottom to top (denoted as Pyraformer1g,7,.u.
Table 6: Long-range forecasting results on the synthetic dataset.
Method
MSE
MAE
Full attention
3.550
1.477
LogTrans
3.007
1,366
ETC
4.742
5,509
Informer
7.546
2,092
Longformer
2.032
1,116
Reformer
1.538
3.069
Pyraformere...e
1.258
0.877
Pyraformer12.7.1
1.176
0.849
can be observed that Pyraformere,o,e with the same C for all scales already outperforms the benchmark methods by a large margin. In particular, the MSE given by Pyraformer is decreased by 18.2% compared with Reformer, which produces the smallest MSE among the existing variants of Transformer. On the other hand, by exploiting the information of the known period, Pyraformerı2.77 performs even better than Pyraformere,6.5 Note that Pyraformer12.7.4 nodes scale 2, 3, and characterizes coarser temporal resolutions respectively corresponding to half a day, half a week, and half a month. We also tested Pyraformer24.7.4 but setting C in the second scale degrades the performance, probably because the convolution layer with kernel size of 24 is difficult train.
We further visualized the forecasting results produced by Pyraformer12.74 solid curve and red dashed curve denote the true and predicted time series respectively. By capturing the temporal dependencies with different ranges, the prediction resulting from Pyraformer closely follows the ground truth.
Figure The blue
On the other hand, to check whether Pyraformer can extract features with different temporal resolu- tions, we depicted the extracted features in randomly selected channel across time at each scale in the pyramidal graph in Figure / It is apparent that the features at the coarser scales can be regarded lower resolution version of the features the finer scales.
J ABLATION STUDY
J.1 IMPACT OF A AND C
We studied the impact A and on the performance of Pyraformer for long-range time series forecasting, and showed the results in Table 7 Here, focus the dataset ETThi. The history
17

---

Published as a conference paper at ICLR 2022
Ground truth
Predicted values
(a)
Figure 6: Visualization of prediction results on the synthetic dataset.
Valur
60-
Value
-00
200
200
200
Intra-
index
index
(a)
(b)
Figure 7: Visualization of the extracted features across time in second channel different scales:
(a) scale 1; (b) scale 2: (c) scale 3.
length is 336 and the prediction length is 720. From Table we can conclude that the receptive fields of the nodes the coarsest scale in the PAM play an indispensable role in reducing the prediction error of Pyraformer. For instance, there are 42 nodes at the coarsest scale when C' 2. Without the intra-scale connections, each node can only receive messages from 16 nodes the finest scale. As the number of adjacent connections A in each scale increases, the receptive fields of the coarsest- scale nodes also extend, and therefore, the prediction error decreases accordingly. However, long as the nodes at the top scale have global receptive field, further increasing A will not bring large gains. For C' 5, the performance does not improve even though A increases. Such observations indicate that is better to set A to be small once the uppermost nodes in the PAM have global receptive field. In practice, we only increase with the increase L, but keep small.
J.2 IMPACT OF THE CSCM ARCHITECTURE
In addition to convolution, there exist other mechanisms for constructing the C-ary tree, such as max pooling and average pooling. We studied the impact of different CSCM architectures on the performance for long-range forecasting on dataset ETThl. The history and the prediction length are both 168 and C 4 for all mechanisms. The results are listed in Table g From Table 8 we can tell that: (1) Using pooling layers instead of convolution typically degrades the performance. However, the performance of Pyraformer based demonstrating the advantages of the PAM over the prob-sparse attention in Informer. (2) The MSE of convolution with the bottleneck is only 1.51% 11% larger than that without bottleneck, but the number
pooling is still superior to that of Informer,
18

---

Published as a conference paper at ICLR 2022
Table 7: Impact of A and C on long-range forecasting. The history length is 336.
A
13
MSE
MAE
Q-K pairs
MSE
MAE
Q-K pairs
MSE
MAE
Q-K pairs
L035
0.811
73512
1,029
0.815
162648
1.003
0.807
221112
C
1,029
0.817
58992
1.009
0.798
128976
1,056
0.805
174672
0
1.001
0.802
53208
1.028
0.806
115848
1.027
0.804
156696
C =
0.999
0.796
49992
1.005
0.796
108744
1.017
0.797
147192
Table 8: Impact of the CSCM architecture on long-range forecasting. Parameters introduced by the normalization layers are relatively few, and thus, are ignored.
Table 9: Impact of history length. The prediction length is 1344.
History Length
MSE
MAE
CSCM
MAE
Parameters
84
1.234
0.856
Max-pooling
0.842
0.700
0
168
1.226
0.868
Average-pooling
0.833
0.693
0
336
1.108
0.835
Conv.
0.796
0.679
3147264
672
1.057
0.806
w/bottleneck
328704
1344
1.062
0.806
Table 10: Impact of the PAM.
Method
Metries
96
288
672
MSE
0,576
0.782
0.883
CSCM Only
MAE
0.544
0.683
0.752
MSE
0.480
0.754
0.857
Pyraformer
MAE
0.486
0.659
0.707
of parameters is reduced by almost 90%. Thus, adopt the more compact module of convolution with bottleneck as our CSCM.
J.3 IMPACT OF THE HISTORY LENGTH
We also checked the influence of the history length on the prediction accuracy. The dataset is ETTml, since its granularity is minute and contains more long-range dependencies. We fixed the prediction length 1344 and changed the history length from longer history typically improves prediction accuracy. On the other hand, this performance gain starts to level off when introducing more history stops providing new information. As shown in Figure 8 the time series with length 672 contains almost all periodicity information that is essential for prediction, while length 1344 introduces more noise.
1344 in Table As expected,
J.4 IMPACT OF THE PAM
Finally, we investigated the importance of the PAM. We compared the performance of Pyraformer with and without the PAM on the dataset ETTm1. For a fair comparison, the number of parameters of the two methods were controlled to within the same order of magnitude. More precisely, we increased the bottleneck dimension of "Conv. w/bottleneck"" for the model only with the CSCM. The results are shown Table TO Obviously, the PAM vital to yield accurate predictions.
K DISCUSSION ON THE SELECTION OF
We recommend to first determine the number of attention layers N based on the available computing resources, this number is directly related to the model size. Next, the number of scales S can be determined by the granularity of the time series. For example, for hourly observations, we typically assume that may also have daily, weekly and monthly periods. Therefore, We then focus on the selection of A and C. According to the ablation study, we typically prefer a small A, such 3 and 5. Lastly, in order to ensure the network has receptive field of L,, we can
set S to be 4.
19

---

Published as a conference paper at ICLR 2022
27.5
18
Value
20.0
16-
17.5
15.0
8-
Time
Time
(a)
(b)
25.0
27.5
22.5
25.0
20.0
17.5
Value
20.9
15.0
17.5
12.5
12.5
10.0
10.0
200
400
600
600
1000
1200
1400
200
400
6.00
800
1000
1200
1400
Time
Time
(c)
(d)
Figure 8: Time series with different lengths in the ETTml dataset. The sequence length in (a) and (b) is 672, and that (c) and (d) is 1344. The time series (a) and (b) corresponds to the latter half of those in (c) and (d) respectively.
select that satisfies Equation 5) In practice, we can use validation set to choose C' from its candidates that satisfies (5). It is also worthwhile to check whether choosing different C' for different scales based on the granularity the time series can further improve the performance as we did in Appendix] I
20


Reviews:
[{"review_id": "M90iHKf04Ns", "reviewer": "Reviewer_cdAe", "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": "## Strengths\n1. The paper is well-written and well-motivated with sufficient technical details\n2. The extensive empirical results demonstrate the effectiveness and efficiency of the proposed method\n3. A proof is provided to guarantee the linear complexity of long sequence encoding\n\n## Comments\n1. More datasets for multi-step forecasting would be helpful in evaluating the method.\n2. The reason of using the second prediction module in multi-step forecasting need more justification, e.g. why take the concatenation as key/value in the second layer.", "summary_of_the_paper": "This paper presents a new hierarchical transformer architecture with constant connection path length and linear time and space complexity for long-range time series modeling. The module at core is a pyramidal attention network that makes multi-resolution representations in a tree structure and perform attention operations on the tree. A stack of convolutions is used to initialize the pyramidal tree. Experiments show the proposed method is able to make more accurate predictions with significantly fewer attention operations and, as a result, less time and memory expenses.", "summary_of_the_review": "Overall I find this paper quite interesting with great potential contribution to the community, and recommend an accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CKJIoK4PE-P", "reviewer": "Reviewer_17as", "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": "__Pros__\n\n1. Overall I like the idea conceptually. As mentioned in the summary it makes a lot of sense for time-series data as it has an implicit bias of summarizing the past at different resolutions. \n\n2. This architecture as claimed, can handle long sequences with computational complexity O(L) where $L$ is the number of elements in the sequence. It can also maintain short attention path distance between any node. This distance is O(1) w.r.t L. \n\n3. The experiments are good enough to demonstrate the advantage of this network over other attention mechanisms.\n\n4. The implementation has been done efficiently using TVM and when released the code base would be of value. I hope the paper is reproducible even though no code has been provided.\n\n5. The empirical speed and memory consumption graphs are useful.\n\n__Cons__\n\nI have certain clarifying questions. i would be happy to raise my scores if these are answered. Further I have some comments that would hopefully make the paper better.\n\n1. It would be better to formally define Signal Traversing Path and forward reference it from the introduction.\n\n2. While reading the initial description in the introduction, it is not fully clear what the nodes at each resolution represent. This is only evident to me after reading section 3.2 which states that convolutional layers with specific strides are applied repeatedly to get the coarser levels. It would be better if one states upfront that some external mechanism is used to extract the initial states of the coarser nodes. Related comment: I think the clarity of section 3,2 can be improved.\n\n3. I might be wrong but I believe N is not defined in section 3.1 before it is used. Please check this (ignore if I missed this somehow).What is the relation between N and S ? I would suggest defining A, L, C, N, S clearly in one place with some indentation in Section 3.1, for ease of reading.\n\n4. Please be slightly more clear in the second paragraph of section 3. 3. I would like to verify my understanding of the multi-step forecasting modules. In the first module, we just have a fixed output layer which is a dense mapping to F outputs, where F is the future prediction length. In the second mapping, there is a decoder that sequentially generated the multi-step output and the decoder is equivalent to the decoder in the original transformer paper. Is my understanding correct?\n\n5. In the experiments the information of the datasets and the experimental setup is not 100% clear to me even after reading the appendix. Please clarify or point me to the relevant places in the paper. In multi-step forecasting what is the length of the future prediction window. Also, is the task rolling prediction over the test set? These should be clearly defined. \n\n6. is there a validation set? Typically I would prefer if A and C are tuned on a validation set per dataset and the best results are reported. the ordering would stay the same I guess, because fixed set of A, C are used in all experiments.\n\n7. Is there a relation between A, C vs the granularity of the dataset. For example if the data is hourly, then one could build a resolution graph such that groups of 24 are constructed in the first level (24 hours in a day), then groups of 7 (7 days in a week), then 4 weeks in a month. Such a non-uniform pyramidal structure might be very useful. Can the authors comment on this or better yet try this? -- not absolutely essential but it would be interesting.\n\n8. Generally, it would be better if we could rank pyramidal attention vs state of the art models on the well known benchmarks used in the DCRNN paper and newer papers like https://arxiv.org/abs/2103.07719. For instance one could just do the evaluation of pyramidal attention in the same tasks as the linked paper and report the numbers. This would reveal the rank of pyramidal attention in the SOTA table and would be a useful signal for the community. Again this is not required but a nice to have.\n\n\n", "summary_of_the_paper": "The paper proposes a variant of the transformer architecture called pyramidal attention. In this architecture one forms a pyramid graph over the sequence at different resolutions and then applies attention among the neighbors of that graph. This leads to a network that can attend to long sequences of length L with O(L) computation but at the same time attention path between two sequence positions is O(1). This is especially relevant for time-series forecasting as it has potential to summarize the time-series at different scales like hourly, daily, monthly etc. Some experiments are performed on 4 datasets to show the advantage of this architecture over other transformer variants.", "summary_of_the_review": "I like the overall idea and the execution is decent (please see the pros and cons above). In my mind the pros outweigh the cons and I am currently rating it as above the acceptance threshold. I can strengthen my reviews if the authors answer the questions asked in the cons section.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5yfE4drbghP", "reviewer": "Reviewer_f9f9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. The paper is well written and the proposed architecture is easy to understand. I believe the equations are correct, and the included model illustrations makes the model design very intuitive.\n2. Extensive evaluation is provided, and the proposed model consistently outperforms baseline models.\n3. A ablation study is provided to justify the effectiveness of each component in the proposed architecture.\n\nWeakness:\n1. Although I couldn't find any specific publication, I believe hierarchical structure illustrated in Figure 1 (d) has been explored before in the context of LSTM/RNN. In addition, another line of work trying to apply the residual connections from ResNet to RNNs (e.g., https://arxiv.org/pdf/1701.03360.pdf) also provides a means for long-range time-series modelling. \n2. The paper states that Pyraformer simultaneously capture temporal dependencies of different ranges in a compact multi resolution fashion. This is intuitively understandable. However, it would be more convincing if the evaluation could also illustrate this perspective. To be more specific, how do we know from the current evaluation setting that the model indeed learns multi resolution temporal dependencies?\n3. Connected to comment 2, it would be better if the authors could illustrate a bit more on why these datasets can be used to evaluate long-term dependency modelling. In my understanding, long-term dependency modelling could be a bit different from long-term prediction. The former focuses on extract meaningful information from long-term previous steps, and the latter focuses on accurate prediction into the far future. If the real-world dataset does not include the long-term dependency in it, some study on a synthetic dataset would help readers understand the benefit of the proposed model. In other words, inaccuracy in long-term prediction could be resulted from (1) accumulated noise in predictions along time, and (2) lack of long-term temporal dependency modelling. How does the authors distinguish the result from these two perspectives? \n4. The proposed method uses a factor of 2 to construct the hierarchy. This number seems a bit arbitrary. I'm wondering if this is a design choice with some thoughts behind it, or could this number be treated as a hyper parameter? Basically this number will decide the number of hierarchies in the structure.", "summary_of_the_paper": "This paper proposes Pyraformer, a low-complexity pyramidal attention model for long-range time-series modelling and forecasting. The proposed architecture is build upon a pyramidal attention module (PAM) in which the inter-scale tree structure summarizes features at different resolutions and the intra-scale neighbouring connections model the temporal dependencies of different ranges. The proposed framework harnesses the benefit of both transformer and RNN. Evaluation on Electricity, wind, App Flow, and ETT dataset against baseline models including Informer., LogTrans, Longformer, Reformer, ETC shows superior performance.", "summary_of_the_review": "Overall it is a solid paper. Please refer to the above session for the detailed discussion. I had a few concerns regarding evaluation setup and novelty. If the authors could reply accordingly, I'm willing to reevaluate the paper.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0rN6MM9aeo", "reviewer": "Reviewer_WMVh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n---\n1.\tThe architecture is well-motivated, tackles the important problem of LSTF, and improves both forecasting performance and computational efficiency of state-of-the-art baselines.\n2.\tPaper is well written and easy to follow – making motivations and contributions clear.\n\nWeaknesses\n---\nHowever, some key architectural details can be clarified further for full reproducibility and analysis. Specifically:\n1.\tHow are historical observations combined with inputs known over all time given differences in sequence lengths (L vs L+M)? The text mentions separate embedding and addition with positional encoding, but clarifications on how the embeddings are combined and fed into the CSCM are needed.\n2.\tCan each node attend to its own lower-level representation? From equation 2, it seems to be that only neighbouring nodes are attended to, based on the description of N_l^(s).\n3.\tDo the authors have any guidelines on how to select S/A/C (and consequently N) for a given receptive field L? \n\nIn addition, while the ablation analysis tests the impact of changing CSCM architectures, it would be good to evaluate the base performance without the PAM to determine the value added by attention. This would also provide a simple comparison vs dilated CNNs which have been used successfully in time series forecasting applications  (e.g. WaveNet). \n\nFinally, could I double check which dataset was used for the ablation analysis as well? I seem to be having some difficulty lining the numbers in Tables 4-6 up with Table 3.\n", "summary_of_the_paper": "The authors propose a new architecture to tackle the problem of long sequence temporal forecasting (LSTF) – which looks at capturing long-range dependencies in time-series data by providing more direct paths between the output and distant history. \n\nThe Pyraformer takes an interesting spin on the current state-of-the-art sparse transformers, consisting of 2 main components:\n1.\tA dilated CNN encoder to learn coarse-scale representations at multiple resolutions.\n2.\tA decoder with a pyramid structure that applies attentions masks to a limited subset of nearest neighbours (i.e. parents, adjacent nodes and children) – effectively sparsifying fully connected attention patterns by imposing a prior structure onto attention patterns.\n", "summary_of_the_review": "The paper makes a strong contribution to long sequence temporal forecasting, although there are some aspects that need to be verified before it is ready for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a multi-resolution pyramidal attention mechanism to capture long-range dependencies in time series forecasting, achieving linear time and space complexity. The authors conduced an extensive set of experiments and ablation studies demonstrating that  the proposed method consistently outperforms the state-of-the-art and provided evidence for the various components of the architecture. They also provided a proof guarantee the linear complexity of long sequence encoding and adequately addressed the concerns raised by the reviewers. The additional additional benchmarks conducted by the author further demonstrated the strong performance of the method. All reviewers agreed that this work makes a solid contribution to the field.
Decision: Accept (Oral)