Efficient Time Series Processing for Transformers and State-Space Models through Token Merging

## Abstract

Abstract Transformer architectures have shown promising results in time series processing. However, despite recent advances in subquadratic attention mechanisms or state-space models, processing very long sequences still imposes significant computational requirements. Token merging, which involves replacing multiple tokens with a single one calculated as their linear combination, has shown to considerably improve the throughput of vision transformer architectures while maintaining accuracy. In this work, we go beyond computer vision and perform the first investigations of token merging in time series analysis on both time series transformers and state-space models. To effectively scale token merging to long sequences, we introduce local merging , a domain-specific token merging algorithm that selectively combines tokens within a local neighborhood, adjusting the computational complexity from linear to quadratic based on the neighborhood size. Our comprehensive empirical evaluation demonstrates that token merging offers substantial computational benefits with minimal impact on accuracy across various models and datasets. On the recently proposed Chronos foundation model, we achieve accelerations up to 5400 % times 5400 percent 5400\text{\,}\mathrm{\char 37\relax} start_ARG 5400 end_ARG start_ARG times end_ARG start_ARG % end_ARG with only minor accuracy degradations.

## 1 Introduction

Figure: Figure 1: Local token merging: Computing token similarity on a subset $\mathbf{S}_{loc}$ under locality constraint $k$ reduces token merging’s quadratic complexity to linear.
Refer to caption: x1.png

Since their inception in NLP [], transformers have extended their influence into various domains, including computer vision with Vision Transformers (ViTs) [], graphs [, ], and time series processing [].
However, the computational complexity of the standard attention mechanism used in transformer architectures scales quadratically with the number of input tokens, resulting in high memory requirements. This scalability issue becomes especially pronounced in time series processing, where sequences frequently comprise thousands of tokens []. Consequently, recent foundational models in time series, such as Chronos, exhibit impressive zero-shot generalization capabilities but demand substantial computational resources [].

Recently, state-space models have emerged as a solution to mitigate the computational burden of transformers. Their complexity scales subquadratically with the sequence length [], which allows them to process millions of tokens []. However, even in state-space models, very long sequences will impose considerable memory and computational demands.

Bolya et al. [], have shown that the efficiency of ViTs can be substantially improved by merging tokens throughout the transformer architecture. Specifically, they compute similarity scores between tokens and combine them into single tokens through a convex combination. However, they only explore token merging for ViT architectures.

In this empirical study, we for the first time explore token merging within the time series domain. We introduce a novel local token merging algorithm whose computational complexity varies from linear to quadratic, based on the neighborhood considered for each token merge. This allows token merging to scale to long sequences. The algorithm is illustrated in figure 1. Through comprehensive empirical evaluations, we analyze the impact of token merging on various time series transformer models and state-space models. Our key contributions are as follows:

- -
Token merging in time series   We present first studies on token merging in time series analysis, exploring its application beyond transformer architectures to include state-space models. For this purpose, we propose a domain-specific token merging algorithm that combines tokens within a local neighborhood around each token. Adjusting the size of the neighborhood allows the complexity of the algorithm to range from linear to quadratic. We show that this adaptability improves upon classical token merging for long-sequence modeling tasks.
- -
Model acceleration   Our findings from both pretrained models and those trained with token merging reveal substantial computational savings with only slight reductions in accuracy across five time series transformer architectures and datasets. We also assess five different model sizes per architecture, noting greater relative accelerations in larger models.
- -
Token merging in foundation models   Specifically, token merging enhances the throughput of the time series foundation model Chronos by up to $54.76\times$, with a marginal quality drop of $3\text{\,}\mathrm{\char 37\relax}$ in relative MSE. Across four out of five datasets, we identify Pareto optimal points where token merging simultaneously boosts throughput and increases accuracy. For example, on the ETTh1 dataset, token merging achieves a $14.17\times$ acceleration while the MSE improves by $6\text{\,}\mathrm{\char 37\relax}$.
- -
Token merging patterns   Our analysis of token merging’s effects identifies three distinct patterns: 1) a consistent decline in performance with an increasing number of merged tokens, 2) initial improvements in accuracy with few merged tokens followed by a drop as merging increases, and 3) scenarios where accuracy remains unchanged regardless of the token merging rate. We investigate all patterns and find different explanations for all behaviors.

## 2 Related work

Time series transformers   In recent years, many transformer architectures with inductive biases for time series have been proposed, successfully outperforming classical and other deep-learning-based methods in time series forecasting quality like recurrent neural networks  []. Most of them focus on reducing complexity by modifying the attention mechanism. LogTrans uses LogSparse attention [] while Informer focuses only on the most relevant queries using ProbSparse attention []. Additionally, many architectures adopt decomposition techniques to model trend and seasonal patterns [, , , ]. Autoformer leverages autocorrelation as a sequence-based similarity measure in the attention mechanism []. FEDformer uses the frequency domain to model time series effectively []. Non-stationary Transformers further mitigate the effect of the time series distribution changing over time []. PatchTST embeds subsequences as tokens to capture local semantic information and reduce complexity []. Other works apply hierarchical attention [, ] or leverage attention between the time series variates to better model multivariate patterns [, ].
Due to their success in the vision and NLP domain, transformer-based foundation models have recently emerged for time series, often used in zero-shot settings. Many works focus on training transformers directly on large and diverse time series datasets, usually with billions of tokens [, , , ]. Inspired by the success of foundation models in NLP, the recently proposed Chronos model converts continuous time series data into a fixed vocabulary and is trained on both real-world and synthetic data []. Besides, other research branches focus on fine-tuning vision or NLP models for time series [] and on applying large language models directly on time series data [].

State-space models   Due to the quadratic scaling of the attention mechanism, transformer architectures suffer from significant computational cost when processing very long input sequences. Recently, state-space models have shown promising results in overcoming the quadratic complexity of transformers with respect to input length. Linear state-space layers solve the sequential processing requirement of RNNs through linear state-space representations []. The S4 model reduces memory requirements by conditioning the state-space matrix with a low-rank correction []. By using implicit convolutions and a data-aware gating mechanism, Hyena [] became one of the first state-space model architectures to match transformers on NLP tasks. Later work uses hardware-aware algorithms to improve the performance of state-space models on modern accelerators [].

Reducing tokens   Many works reduce the number of processed tokens to increase the efficiency of transformer architectures in computer vision and NLP, often by pruning [, ]. Marin et al. [] merge tokens in ViT architectures to reduce the loss of information associated with pruning. Bolya et al. [] enhance the token merging algorithm, which they successfully apply to already trained models.
Besides initial work on classification tasks [], subsequent work applies token merging to diffusion models []. Kim et al. [] combine merging and pruning, while other work investigates optimal merging and pruning rates [, ].

Here, we propose a token-merging algorithm for the time series domain, which extends beyond previous investigations of token-merging in ViTs [, ]. We systematically evaluate the potential to reduce computational effort in time-series-specific transformer architectures and state-space models.

## 3 Token merging

Despite recent advances in efficient transformers, processing long input sequences still induces considerable memory requirements and computational effort. In the following, we first outline the token merging algorithm introduced by Bolya et al. [] for ViT architectures. We then propose local merging enabling efficient token merging for state-space models and long sequence processing.

#### (Global) Token merging in computer vision

Let a neural network $\mathbf{f}(\mathbf{x})=\mathbf{\Phi}_{L}\circ\mathbf{\Phi}_{L-1}\circ\cdots
\circ\mathbf{\Phi}_{1}(\mathbf{x})$ consist of $L$ layers denoted as $\mathbf{\Phi}_{l}$, where each layer takes the output of the previous layer as input. We assume that the input $\mathbf{x}_{l}\in\mathbb{R}^{t_{l}\times d}$ consists of $t_{l}$ tokens with dimension $d$. Thereby, the input tokens are generated by a tokenizer $\mathbf{g}:\mathbb{R}^{z}\rightarrow\mathbb{R}^{t\times d}$ out of $z$-dimensional input data $\mathbf{u}$. In the computer vision domain, $\mathbf{u}$ usually takes the form $\mathbf{u}\in\mathbb{R}^{w\times h\times c}$, where $w,h,c$ are the width, height, and channels of the input image, respectively, and $w\cdot h\cdot c=z$.
To improve the computational efficiency of a given model, Bolya et al. [] combine the $r$ most similar tokens in each layer, reducing the tokens to be processed in layer $l\!+\!1$ to $t_{l+1}=t_{l}-r$. Therefore, they split the set of all tokens into two disjoint subsets $\mathcal{A,B}$ in alternation to avoid merging conflicts and allow for a parallelized computation of merging correspondences. Here $\mathcal{A}$ and $\mathcal{B}$ contain $t_{l}/2$ elements each, denoted as $\mathbf{a}_{i}$ and $\mathbf{b}_{j}$ respectively. The authors compute the cosine similarity between all tokens in both subsets $\mathbf{S}=(s_{ij})$ and merge the $\mathop{\mathrm{top\,}}r$ most similar correspondences by averaging the tokens accordingly. This results in a global token merging algorithm with quadratic complexity. Lastly, the authors use a fixed $r$ to enable batch processing without needing to pad individual batch elements to the same shape after token reduction.

#### (Local) Token merging for time series

In this work, we design token merging mechanisms for time series architectures and demonstrate run-time and even performance improvements over various datasets and models. We assume that the input $\mathbf{u}$ consists of $m$ time stamps with $n$ variates.

Previous work on token merging in image processing explored global merging schemes, where every token of each subset $\mathcal{A}$ and $\mathcal{B}$ could be merged with each other [, ].
However, computing the similarity $\mathbf{S}\in\mathbb{R}^{t_{l}/2\,\times\,t_{l}/2}$ between both sets of tokens has a complexity of $O(t_{l}^{2}/4)$, which is suboptimal for sequential data often consisting of long token sequences [, ], and state-space models featuring subquadratic complexity [, ].
Therefore, we propose local merging - a superset of token merging - by introducing $k\in\mathbb{N},1\,\leqslant\,k\,\leqslant\,t_{l}/2$ as a locality constraint where we compute the similarity only on a local subset of tokens $\mathbf{S}_{loc}=\{s_{ij}\,|\,1\leqslant i,j\leqslant t_{l}/2,\,|i-j|<k\}$. Figure 1 illustrates the proposed merging algorithm. The locality constraint reduces the complexity to $O(t_{l}/2+(k-1)(t_{l}-k))$. Varying the locality, we achieve linear complexity by considering only neighboring tokens for merging up to quadratic complexity by considering a global merging pool, possibly exploiting more redundancy.
For efficient computation, we refactor $\mathbf{S}_{loc}$ into a rectangular tensor. An upper bound for the resulting speed up can be given by $\mathrm{speed\;up}\,\leqslant 3\,L\,4^{L-1}\cdot(4^{L}-1)^{-1}$. The acceleration of deeper models is expected to increase as more subsequent layers can profit from already merged tokens.
Local merging additionally preserves order and locality as an inductive bias for sequence processing.
Some time series transformers use processing mechanisms that require a minimum number of tokens in the forward pass. To universally enable token merging in these architectures, we further introduce $q$ as the minimum number of remaining tokens. When encountering odd numbers of tokens $t_{l}$ we exclude the most recent token from merging as we expect it to contain the most relevant information.
We derive the complexity of the token merging procedures in section A.1.

**Table 1: Token merging speeds up (Accel.) various pretrained transformer architectures of different sizes on several multivariate time series datasets. Merging induces minimal change in quality (MSEΔ) compared to the reference without token merging (MSE).**
| Dataset | Layers $L$ | Transformer | Autoformer | FEDformer | Informer | Non-stationary |  |  |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| MSE | Accel. | MSEΔ | MSE | Accel. | MSEΔ | MSE | Accel. | MSEΔ | MSE | Accel. | MSEΔ | MSE | Accel. | MSEΔ |  |  |
| ETTh1 | 2 | $0.75$ | $1.30$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.42$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.38$ | $1.27$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.87$ | $1.27$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.55$ | $1.32$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ |
| 4 | $0.71$ | $1.76$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.40$ | $1.39$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.39$ | $1.77$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.92$ | $1.32$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.47$ | $1.84$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ |  |
| 6 | $0.66$ | $2.35$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.44$ | $2.15$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.38$ | $2.24$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.93$ | $2.29$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.46$ | $2.39$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ |  |
| 8 | $0.84$ | $2.98$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.41$ | $2.67$$\times$ | $-5\text{\,}\mathrm{\char 37\relax}$ | $0.39$ | $2.95$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $1.23$ | $2.24$$\times$ | $8\text{\,}\mathrm{\char 37\relax}$ | $0.48$ | $2.99$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| 10 | $0.69$ | $3.51$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.39$ | $3.10$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.38$ | $3.45$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $1.16$ | $2.35$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ | $0.57$ | $3.63$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| ETTm1 | 2 | $0.52$ | $1.31$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.44$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.36$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.65$ | $1.28$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.42$ | $1.32$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |
| 4 | $0.58$ | $1.73$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ | $0.43$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.37$ | $1.74$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ | $0.60$ | $1.66$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.48$ | $1.72$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| 6 | $0.62$ | $1.99$$\times$ | $4\text{\,}\mathrm{\char 37\relax}$ | $0.45$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.38$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.59$ | $2.03$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.38$ | $2.37$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| 8 | $0.60$ | $2.91$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.58$ | $2.65$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.33$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.61$ | $1.53$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.46$ | $2.04$$\times$ | $-2\text{\,}\mathrm{\char 37\relax}$ |  |
| 10 | $0.62$ | $3.48$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.54$ | $1.67$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.36$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.57$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.41$ | $3.60$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ |  |
| Weather | 2 | $0.25$ | $1.31$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.28$ | $1.11$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.27$ | $1.26$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.35$ | $1.28$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.19$ | $1.34$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ |
| 4 | $0.28$ | $1.80$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.24$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.26$ | $1.78$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.24$ | $1.75$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ | $0.19$ | $1.81$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| 6 | $0.28$ | $2.04$$\times$ | $9\text{\,}\mathrm{\char 37\relax}$ | $0.26$ | $2.09$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ | $0.27$ | $2.33$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.21$ | $2.06$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ | $0.20$ | $2.36$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| 8 | $0.32$ | $2.11$$\times$ | $5\text{\,}\mathrm{\char 37\relax}$ | $0.26$ | $1.59$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ | $0.27$ | $2.92$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.30$ | $1.50$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.20$ | $2.97$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| 10 | $0.35$ | $2.41$$\times$ | $8\text{\,}\mathrm{\char 37\relax}$ | $0.26$ | $1.74$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ | $0.24$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.31$ | $1.63$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.19$ | $3.56$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ |  |
| Electricity | 2 | $0.25$ | $1.27$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.18$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.20$ | $1.27$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.30$ | $1.26$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ | $0.17$ | $1.32$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |
| 4 | $0.26$ | $1.73$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.19$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.19$ | $1.74$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.30$ | $1.62$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ | $0.17$ | $1.75$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ |  |
| 6 | $0.25$ | $2.28$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.19$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.20$ | $2.23$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.29$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.17$ | $2.27$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ |  |
| 8 | $0.25$ | $2.80$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.19$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.20$ | $2.82$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.31$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.17$ | $2.86$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |
| 10 | $0.25$ | $3.39$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.18$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.20$ | $3.35$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.30$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.18$ | $2.54$$\times$ | $7\text{\,}\mathrm{\char 37\relax}$ |  |
| Traffic | 2 | $0.66$ | $1.28$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.63$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.59$ | $1.25$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.68$ | $1.20$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ | $0.60$ | $1.25$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ |
| 4 | $0.66$ | $1.57$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ | $0.60$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.58$ | $1.67$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.68$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.59$ | $1.68$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ |  |
| 6 | $0.64$ | $2.11$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ | $0.61$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.57$ | $2.15$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.69$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.62$ | $1.58$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ |  |
| 8 | $0.68$ | $2.67$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.60$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.59$ | $2.65$$\times$ | $-0\text{\,}\mathrm{\char 37\relax}$ | $0.71$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.59$ | $2.66$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ |  |
| 10 | $0.67$ | $3.26$$\times$ | $-1\text{\,}\mathrm{\char 37\relax}$ | $0.59$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.58$ | $3.13$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.69$ | $1.00$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $0.59$ | $3.18$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ |  |

## 4 Experiments

We systematically explore token merging in diverse settings on $5$ time series datasets and $5$ model architectures in $5$ different sizes each. Additionally, we investigate token merging in large foundation models using Chronos in a zero-shot setting []. Finally, we demonstrate that token merging can be applied to state-space models for long sequence processing by using a novel local merging algorithm featuring subquadratic complexity.

Datasets   We use time series forecasting datasets including ETTh1, ETTm1, Weather, Electricity and Traffic for our transformer experiments. For state-space models, we use the long-range Dummy Mouse Enhancers Ensembl dataset. See section A.2 for more details.

Model architectures   For our main experiments, we use $5$ architectures, including Autoformer, FEDformer, Informer, Non-stationary Transformer, and the vanilla Transformer [] as reference. For each model, we evaluate token merging for different model sizes with $L\in\{2,4,6,8,10\}$ encoder layers, which we train doing hyperparameter optimization (see section A.2). We use an input length of $m=$192$$ and prediction horizon $p=$96$$ samples.
For experiments on Chronos, we use the default input length of $m=$512$$ and prediction horizon $p=$64$$ []. We compute the median from Chronos probabilistic forecasts and report the MSE.
For our experiments on state-space models, we use HyenaDNA medium, a genomic foundation model [] based on the Hyena architecture []. We use a large input length of $m=$16\,000$$ nucleotides utilizing Hyenas subquadratic complexity.

Applying token merging   We apply token merging between the attention and MLP block in all transformer architectures as in []. Additionally, we only merge in the encoder and not in the decoder, as many architectures do not allow for a unified merging scheme. In architectures utilizing additional tensors like attention masks or positional biases, we merge them using the same correspondences.
Many transformers exhibit quadratic attention, imposing considerable computational cost. As a result, we do not find the token merging algorithm to introduce a substantially additional overhead. Thus, we choose $k=t_{l}/2$ to profit from a global merging pool for transformer models. In state-space models, we merge tokens after the Hyena operator and choose $k=1$ to not introduce an operation with quadratic complexity into the architecture.

Reproducibility of measurements   We report all results on the same Nvidia A6000 GPU. For training, we utilize Nvidia V100 and A100 GPUs (see section A.2). We measure the end-to-end execution time of the models using $2$ warm-ups and $2$ measurement runs per batch. The standard deviation of the execution time is generally $<$2\text{\,}\mathrm{\char 37\relax}$$ in our experiments. Besides the execution time as practically most relevant quantity, we report FLOPs as a more hardware independent measure using the thop library []. We always choose the maximum possible batch size and standardize the results.

## 5 Results

We first present our main results for token merging on pretrained models and models trained with token merging and subsequently conduct several ablation studies.

### 5.1 Token merging in pretrained models

We investigate token merging on diverse time series transformer models with different inductive biases. All models are specifically trained on the target dataset and token merging is applied only during inference time, as accelerating already trained models is of high practical relevance. We choose token merging hyperparameters as described in section A.2, selecting the fastest token merging trial on the validation set that is within a $0.01$ increase in MSE compared to the reference without token merging.
If we do not find a trial with token merging satisfying these tight criteria, we report results without token merging, mimicking how token merging might be applied in practice. We perform all selections on the validation set and report all results on the test set.
The vanilla and Non-stationary Transformers have quadratic attention mechanisms, while the remaining architectures feature subquadratic attention complexities of $O(t_{l}\cdot\log(t_{l}))$ for Autoformer and Informer and $O(t_{l})$ for FEDformer.
Regardless, token merging substantially increases the throughput of most models, up to $$3.63$\times$, often with no change in forecasting quality as table 1 shows. In some experiments, token merging even improves the MSE. In line with the formal analysis of potential speed up from token merging conducted in section 3, we generally observe higher accelerations for larger models, as more subsequent layers can profit from already merged tokens.
In some cases, we do not find a model with decent forecasting quality satisfying our criteria. Here, token merging during test only has a larger impact on model accuracy, such as for Autoformer on the Traffic dataset. We address this issue when training with token merging in section 5.2.

Figure: Figure 2: (Left) Training with different token merging $r_{train}$ fractions compared to applying token merging only during inference. Even if token merging is not applied during testing (no merging), models trained with token merging achieve better MSE. (Right) Additionally, models that showed high MSE degradation with token merging without training show high accelerations while maintaining MSE (increases up to $6\%$) when enabling token merging during training.
Refer to caption: x2.png

### 5.2 Token merging during training

Here, we apply token merging during training to reduce the model’s sensitivity to the algorithm at inference time. As shown in figure 2, models trained with token merging often outperform those trained without it, even if token merging is not applied during testing. This approach enables us to accelerate models such as Autoformer on the Traffic dataset without sacrificing accuracy, which was previously not feasible when applying token merging only during inference. Additionally, token merging accelerates the training process itself by up to $$2.27$\times$ for Autoformer on the Traffic dataset.

**Table 2: Token merging acceleration (Accel.) for all Chronos foundation models from tiny to large, measured for zero-shot forecasting of different univariate time series. Applying token merging, we aim for two objectives: the best MSE and the fastest acceleration. Among all Chronos models, we choose the best without token merging as reference (MSE). As token merging improves MSE (negative MSEΔ) while speeding up the model, we are able to choose small Chronos models while surpassing forecasting quality of larger models.**
| Dataset | MSE | Best | Fastest |  |  |
| --- | --- | --- | --- | --- | --- |
| Accel. | MSEΔ | Accel. | MSEΔ |  |  |
| ETTh1 | $0.45$ | $14.17$$\times$ | $-6\text{\,}\mathrm{\char 37\relax}$ | $32.76$$\times$ | $2\text{\,}\mathrm{\char 37\relax}$ |
| ETTm1 | $0.41$ | $1.23$$\times$ | $-4\text{\,}\mathrm{\char 37\relax}$ | $6.47$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ |
| Weather | $0.17$ | $1.16$$\times$ | $-1\text{\,}\mathrm{\char 37\relax}$ | $54.76$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ |
| Electricity | $0.14$ | $1.02$$\times$ | $0\text{\,}\mathrm{\char 37\relax}$ | $2.91$$\times$ | $3\text{\,}\mathrm{\char 37\relax}$ |
| Traffic | $0.61$ | $1.16$$\times$ | $-9\text{\,}\mathrm{\char 37\relax}$ | $2.91$$\times$ | $1\text{\,}\mathrm{\char 37\relax}$ |

### 5.3 Scaling to large models

Foundation models are getting more relevant across domains, including NLP [], computer vision [], and time series processing [].
However, these models have high computational requirements. Thus, we investigate token merging for foundation models on Chronos, a univariate probabilistic model, in zero-shot forecasting setting []. We apply token merging during inference only, as training Chronos from scratch is not within the scope of this work.
In all our experiments, we find Pareto optimal points with token merging. For four out of five datasets token merging improves both accuracy and throughput simultaneously (see section A.3). Our results demonstrate that it is often beneficial to choose a larger Chronos model with token merging over a smaller one without as in figure 3.
We report our results in table 2, choosing the best Chronos model without token merging as reference. We illustrate two cases: 1) Selecting the token merging setting that provides the best MSE, 2) selecting the setting with the fastest throughput. For 2), we constrain the MSE of token merging trials to be lower than the second-best model without token merging. In addition, we allow a maximum increase in MSE of $3\text{\,}\mathrm{\char 37\relax}$ compared to the reference. In our experiments we can improve Chronos MSE by up to $9\text{\,}\mathrm{\char 37\relax}$ and speed up inference by $$54.76$\times$.

Figure: Figure 3: MSE for different token merging in Chronos models during zero-shot testing on two datasets. Choosing larger models with token merging is beneficial compared to smaller ones without.
Refer to caption: x3.png

Figure: Figure 4: Comparison of the effects of low-pass filtering the input time series with a Gaussian filter and token merging for Chronos small. The Gaussian filter has a similar effect on MSE as token merging, supporting our hypothesis that token merging selectively low-pass filters data. Besides improving MSE token merging accelerates the model unlike the Gaussian filter.
Refer to caption: x4.png

### 5.4 Merging patterns

We observe three distinct merging patterns when combining tokens in transformer architectures.

Increasing MSE   As the number of merged token increases the MSE increases almost monotonically (see figure 3). This behavior can be explained due to a loss of information when combining multiple tokens and also occurs in the vision domain [].

Figure: Figure 5: Transformer models on ETTh1 show constant MSE, independent of the amount of token merging $r$.
Refer to caption: x5.png

Constant MSE   For the vanilla Transformer on ETTh1 and for FEDformer on ETTh1, Weather, Electricity, and Traffic, we observe a constant MSE when applying token merging as shown in figure 5. For the Transformer model, we find all tokens to be similar after the first attention block. Thus, token merging does not affect the model performance. Nevertheless, we find that in most cases, these models still provide reasonable forecasts. In our experiments, transformer models trained on larger or more complex datasets containing more variates do not show this behavior. We argue that this might be a limitation of transformers on small time series datasets [, ]. Still, token merging successfully improves the throughput while maintaining accuracy for these models.

Decreasing MSE   Token merging increases forecasting quality, most prominently in Chronos models as in figure 3. We explain this behavior in section 5.5.

### 5.5 When does token merging improve model performance

In our experiment, applying token merging sometimes improves MSE. Our hypothesis is that averaging similar tokens smoothes the time series, reducing noise and acting as a low-pass filer. To validate our hypothesis, we low-pass filter the input time series using Gaussian kernels without token merging in figure 4. On ETTh1 and Traffic, both token merging and Gaussian filtering improve the MSE. On the Electricity dataset, token merging and Gaussian filtering do not positively impact the MSE. All of these observations are in line with our hypotheses.
Applying token merging together with the Gaussian kernel leads to the best results. Other averaging kernels were significantly worse. We show additional results on ETTm1 and Weather in section A.4.

### 5.6 Dependencies on input length

Token merging effectively reduces the number of tokens in a transformer layer. Here, we explore if we can achieve similar accelerations while maintaining the same prediction quality by varying the number of input samples $m$. For better comparison, we keep the predicted time series snippet fixed and only vary the input sequence.
Our results demonstrate that varying the input length cannot replace token merging (see also section A.5). In figure 6, we investigate input length dependence for two objectives in more detail: First, we explore the token merging setup that leads to the best MSE and compare the results to the model without merging. Here, token merging yields considerable throughput increases while improving predictive quality at the same time. Secondly, we compare the fastest model with token merging, which shows no quality decreases, to a standard model. We find models with token merging to scale favorable to long sequences compared to models without merging.

Figure: Figure 6: Effect of different input lengths on forecasting quality (left) and model execution time (right) for token merging in Chronos small models on ETTh1.
Refer to caption: x6.png

### 5.7 Redundancy of input tokens

Token merging exploits similarities in data. Intuitively, the number of tokens that can be merged without affecting predictive performance should depend on the redundancy of the tokens. We explore factors influencing the redundancy of input tokens, including their number and positional embeddings. In the following, we use Autoformer’s time stamp positional embedding for our ablation.
First, we investigate whether scaling the number of input tokens increases average redundancy on the ETTh1 dataset. As demonstrated in figure 7(a), the same relative number of tokens are merged for a given merging threshold, independent of input length. Therefore, we suggest scaling the number of merged tokens in each layer $r$ linearly with the input length.
Positional embeddings add information about the location of a token within a sequence. As a result, two identical tokens without positional embeddings may show considerable differences when positional embeddings are included, potentially preventing merging. However, figure 7(a) shows that this effect on token merging is only marginal.

Figure: (a) Token redundancy
Refer to caption: x7.png

### 5.8 Dynamic merging

A fixed merging objective allows for batch processing without needing to pad individual time series to the same length. However, it enforces a fixed $r$ among independent batch elements, which might not always be optimal. Determining the number of tokens to be merged dynamically using a similarity threshold might increase quality as no dissimilar tokens are combined. Here, we leverage the single-sample case to explore dynamic merging in optimal conditions. From a practical perspective, this case might be relevant for on-device applications like smartphones or automated driving.
In figure 7(b), we compare token merging utilizing a fixed $r$ to dynamic merging varying the cosine similarity threshold. Dynamic merging improves quality slightly in most settings. Therefore, we suggest using a fixed merging schedule for batch applications and dynamic merging just for the single-sample case. There is no equivalent $r$ to dynamic merging schedules as they are similarity-based and strongly layer-dependent. We report FLOPs as we observe substantial execution overhead in time measurements.

### 5.9 Token merging in state-space models

**Table 3: Comparison of global and local token merging for HyenaDNA on the long sequence Dummy Mouse Enhancers Ensembl dataset. Best, second.**
| Token merging | Accel. | Accuracy |
| --- | --- | --- |
| No merging | 1.00$\times$ | 78.9 % |
| Local merging | $\bm{3.62\times}$ | 74.0 % |
| Global merging | 2.93$\times$ | 69.4 % |

State-space models can process very long sequences with millions of tokens due to their subquadratic complexity. Our proposed local merging algorithm is specifically designed to match this subquadratic complexity, enabling effective token merging in state-space models. Additionally, it preserves locality and order as inductive bias for sequence processing.
We explore token merging in HyenaDNA. We use a classification task for the experiment, where the data consists of long genomic sequences with $16\,000$ nucleotides each. Our local merging with $k=1$ featuring linear complexity and locality bias outperforms global merging with $k=t_{l}/2$ and quadratic complexity. Table 3 illustrates that local merging achieves substantially larger speed up and better accuracy than global merging. This experiment indicates that architecture and domain-specific biases are important when applying token merging to a task.
Local merging accelerates HyenaDNA $$3.62$\times$ with a $4.9\text{\,}\mathrm{\char 37\relax}$ decrease in accuracy. To the best of our knowledge, this is the first study that investigates merging individual states in state-space models to improve their sequence modeling performance.

## 6 Conclusion

In this work, we explore token merging in the time series domain for the first time. We conduct an extensive empirical study on transformer architectures and state-space models in diverse settings using various models and datasets. We demonstrate that token merging can successfully accelerate pretrained models and sometimes even improve their prediction quality. We further introduce a domain-specific local merging algorithm with variable complexity and illustrate its effectiveness on the Hyena model. On the long-range Dummy Mouse Enhancers Ensembl dataset, this method outperforms traditional token merging approaches in terms of throughput and accuracy.
Finally, we conduct several ablation studies to investigate when token merging is most effective, including sequence length, positional embedding, and single-sample inference settings.
We hope that token merging will have a positive effect on reducing the resource consumption and environmental impact of time series models.

#### Limitations

In our work, we restrict the merging algorithm to the encoder part of all transformer architectures. Moreover, we divide all tokens into two sets and restrict merging to occur only between tokens from different sets. Future work can explore more flexible merging schemes for time series-specific architectures. Moreover, we do not conduct ablations on all possible hyperparameters due to the large number of architectures and datasets evaluated in this work. Lastly, we focus primarily on common metrics like MSE and accuracy and do not explore the impact of token merging on other factors, such as robustness to distribution shifts or adversarial attacks [, ].

#### Disclaimer

The results, opinions and conclusions expressed in this publication are not necessarily those of
Volkswagen Aktiengesellschaft.

## Appendix A Appendix

Supplementary material such as derivations, further details and additional results are listed below.

### A.1 Derivations

In the following we derive our theoretical results in section 3.

#### Complexity of local merging

To compute $\mathbf{S}_{loc}$ for local merging we need to compute the main diagonal of $\mathbf{S}\in\mathbb{R}^{t_{l}/2\,\times\,t_{l}/2}$ and depending on $k$ also secondary diagonals which are symmetrical but shorter than the main diagonal for $k>1$. We derive the complexity of local merging depending on $k$ in the following:

$$ $\displaystyle\mathrm{complexity}\;\mathbf{S}_{loc}$ $\displaystyle={\color[rgb]{0,0.88,0}\frac{t_{l}}{2}}+{\color[rgb]{1,0.49,0}2}{ \color[rgb]{0,0.44,0.57}\sum_{p={\color[rgb]{1,0,0}2}}^{k}\frac{t_{l}}{2}{ \color[rgb]{1,0,0.87}-(p-1)}}$ $\displaystyle=\frac{t_{l}}{2}+2\sum_{p=1}^{k-1}\frac{t_{l}}{2}-p$ $\displaystyle=\frac{t_{l}}{2}+2\left(\frac{(k-1)\,t_{l}}{2}-\sum_{p=1}^{k-1}p\right)$ $\displaystyle=\frac{t_{l}}{2}+2\left(\frac{(k-1)\,t_{l}}{2}-(k-1)\frac{k}{2}\right)$ $\displaystyle=\frac{t_{l}}{2}+(k-1)(t_{l}-k)$ $$

#### Merging speed up bound

We roughly estimate the upper bound of the speed up we can achieve by merging tokens in a $L$-layer transformer model. Therefore, we only consider attention due to its quadratic scaling with $t_{l}$. We disregard additional effects reducing speed up such as merging overhead to estimate the upper bound. Further, we assume merging half of the tokens each layer. The attention in the first layer is unaffected by merging as we apply token merging between the attention and MLP.

$$ $\displaystyle\mathrm{speed\;up}\;$ $\displaystyle\leqslant\frac{L\,t{\color[rgb]{0,0.88,0}{}^{2}}}{{\color[rgb]{ 0,0.44,0.57}t}{\color[rgb]{0,0.88,0}{}^{2}}+\left(\frac{t}{{\color[rgb]{ 1,0.49,0}2}}\right){\color[rgb]{0,0.88,0}{}^{2}}+\left(\frac{t}{{\color[rgb]{ 1,0.49,0}4}}\right){\color[rgb]{0,0.88,0}{}^{2}}+\cdots+\left(\frac{t}{{\color [rgb]{1,0.49,0}2^{L-2}}}\right){\color[rgb]{0,0.88,0}{}^{2}}+\left(\frac{t}{{ \color[rgb]{1,0.49,0}2^{L-1}}}\right){\color[rgb]{0,0.88,0}{}^{2}}}$ $\displaystyle=\frac{L}{\sum_{p=0}^{L-1}\left(\frac{1}{2^{p}}\right)^{2}}$ $\displaystyle=\frac{L}{\sum_{p=0}^{L-1}\left(\frac{1}{4}\right)^{p}}\hskip 18. 00003pt\mathrm{using\;geometric\;series}\;\sum_{s=0}^{S}v^{s}=\frac{1-v^{S+1}} {1-v}\mathrm{\;for\;}v\neq 1$ $\displaystyle\Rightarrow\frac{L\left(1-\frac{1}{4}\right)}{1-\left(\frac{1}{4} \right)^{L}}$ $\displaystyle=3\,L\,4^{L-1}\cdot(4^{L}-1)^{-1}$ $$

### A.2 Experiments

Here we list additional information concerning our experimental settings and resources.

Datasets   We base our experiments on $5$ commonly used multivariate time series datasets covering different forecasting applications: ETTh1 and ETTm1 consist of $7$ variates measuring the power load and temperature of electric transformers in hourly and quarter-hourly granularity [].
Weather consists of $21$ meteorological quantities such as air temperature and is recorded every $10$ minutes in $2020$.(^1^11[https://www.bgc-jena.mpg.de/wetter/](https://www.bgc-jena.mpg.de/wetter/))
Electricity measures the energy demand of $321$ consumers every hour [].
Traffic consists of $862$ sensors in the San Francisco Bay Area measuring the road occupancy hourly [].
We use the same data splits for training, validation and test as [] for consistency.
Since the Chronos foundation model operates univariately and requires considerable computational resources, we randomly sample the same $7000$ time series from the test set for all Chronos evaluations. For the ETTh1 dataset we do not observe relevant differences when comparing the results to the full test set.
To explore token merging in an additional sequence-based domain and on a second task, we use the Dummy Mouse Enhancers Ensembl dataset [] for classifying genomic data. It contains very long sequences of nucleotides from a mouse.

Hyperparameter optimization   For each transformer architecture, model size, and dataset we train $32$ models without token merging doing hyperparameter tuning of learning rate and dropout using HEBO []. Here we apply token merging during inference-time only. We choose the best model based on its validation MSE. We train $17$ models with the found hyperparameters, the minimum possible $q_{train}$, and different uniformly spaced $r_{train}$ until all tokens are merged. We again choose the best model based on the MSE for further evaluation. We do $180$ hyperparameter optimization trials of both chosen models, trained with and without token merging, using HEBO to find token merging inference hyperparameters $r_{test}$ and $q_{test}$ on the validation set. Finally, we evaluate once on the test set to report our results.

Hyperparameters   In table 4 we list the most relevant hyperparameters we used for training the transformer models including the vanilla Transformer, Autoformer, FEDformer, Informer and Non-stationary Transformer. For training and testing HyenaDNA [] and for testing Chronos [] we used their default hyperparameters.

**Table 4: Hyperparameters for training the transformer models.**
| Hyperparameter | Value |
| --- | --- |
| Training |  |
| Seed | 2024 |
| Optimizer | Adam [] |
| Learning rate | Search space loguniform[$10^{-6}$, $10^{-2}$] |
| Learning rate decay | Exponential, $\gamma=0.97$ |
| Dropout | Search space uniform[0.0, 0.25] |
| Batch size | 32 |
| Epochs | 100 |
| Early stopping patience | 7 |
| Loss | MSE |
| Model |  |
| Input length | $m=192$ |
| Prediction horizon | $p=96$ |
| Token dimension | $d=512$ |
| Encoder layers | $L\in\{2,4,6,8,10\}$ |
| Decoder layers | 1 |
| Attention heads | 8 |
| MLP hidden dimension | 2048 |
| Activation | GELU |

Computational effort   We estimate the computational effort for reproducing our experiments in table 5. Please note that we base some of our experiments on model checkpoints acquired in previous experiments.

**Table 5: Computational effort to reproduce our experiments.**
| Experiment | Accelerator | GPU hours |
| --- | --- | --- |
| Token merging in pretrained models | A6000 | 80 |
| V100 | 6720 |  |
| Token merging during training | A6000 | 50 |
| V100 | 3840 |  |
| Scaling to large models | A6000 | 500 |
| Token merging improves model performance | A6000 | 30 |
| Dependencies on input length | A6000 | 80 |
| Redundancy of input tokens | A6000 | 5 |
| Dynamic merging | A6000 | 140 |
| Token merging in state-space models | A6000 | 40 |
| A100 | 6 |  |

### A.3 Scaling to large models

In this section we show complete results on applying token merging to Chronos, a time series foundation model.

Figure: Figure 8: Token merging in different Chronos models on ETTh1
Refer to caption: x9.png

Figure: Figure 9: Token merging in different Chronos models on ETTm1
Refer to caption: x10.png

Figure: Figure 10: Token merging in different Chronos models on Weather
Refer to caption: x11.png

Figure: Figure 11: Token merging in different Chronos models on Electricity
Refer to caption: x12.png

Figure: Figure 12: Token merging in different Chronos models on Traffic
Refer to caption: x13.png

### A.4 When does token merging improve model performance

We find token merging to have a smoothing effect improving MSE and show our results on all datasets here.

Figure: Figure 13: Comparing token merging to smoothing the input time series of Chronos small on different datasets.
Refer to caption: x14.png

### A.5 Dependencies on input length

Here we show an additional evaluation on applying token merging in Chronos models with different input lengths.

Figure: Figure 14: Varying the input length of Chronos small on ETTh1.
Refer to caption: x16.png

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 4
questions: 1. Piggybacking on Strength 3, L305 shows speedup in training Autoformer. Is
   this a general trend for all architectures (that have been experimented
   with)?
2. Have other measures of similarity been experimented with (L1, L2, etc)?
3. L021: What is the reason behind suggesting that the local token merging is
   domain-specific? Wouldn't allowing 1 < k < l/2 and relaxing the requirement
   that the tokens must be subsequent make the local ToMe still relevant to
   other domains?
4. Would it be fair to say that Sec 5.5 and Fig 5 support the suggested
   hypothesis provided the datasets (ETTh1, etc) are ridden with considerable
   noise? If this question is invalid, L402/403 that applying token merging plus
   Gaussian leading to the best result is confusing: if on the one hand the
   filter seems to exacerbate the results, and on the other ToMe improves it,
   how come a combination yields the best result?
5. L190: What is meant by "the most recent token"? The token corresponding to
   the latest positional encoding? If that assumption is true, wouldn't it be
   profitable to merge based on a priority, where older tokens are forced to
   merge first?
6. L199: I might have missed this, but if unlike Bolya and Hoffman, how is
   "split a merged token into two neighbouring identical ones" done?

### General comments

* I quite like the separation of the meat of local merging away from the
  experiments. But I found the paragraph from 228-238 somewhat disorganised.
  Starting with "We utilise different merging strategies in transformer encoders
  and decoders" would have make the paragraph clearer to read further. It might
  make a coherent writeup for this paragraph to have generic statements
  (L233-236) in the beginning and specific details afterwards. [This is merely a
  suggestion and not part of any review assessment].
soundness: 3
strengths: 1. Firstly, this work addresses a problem relevant to the field in general: attempting to reduce computational complexity of the widespread transform-based and SSM models. Though similar efforts to this end have been made earlier, this work presents some interesting findings, such as choosing larger models with token merging are preferable to smaller ones without (Fig 3) and those trained with token merging scale better to longer observations (Fig 6).
2. The ability of this method to enable its application on models at inference time without having to retrain them with local token merging makes it very applicable. The improved output quality on some smaller models (Tab. 2) is an added strength.
3. This method shows speedup in training while performing comparably to a counterpart trained without token merging (L305). In addition, performance of models so trained without the token merging during inference not sacrificing accuracy is an added incentive to generally consider using this technique.
summary: This work presents a form of token merging to speed up transformers (and state-space models), particularly large and foundational models trained in the time-series domain. It generalises the token merging technique presented by Bolya et al at ICLR 2023 by allowing specifying the number of tokens to be merged (Fig 1, Sec 3), referred to in this work as "local" token merging.

Much of the work is dedicated to studying and analysing the method and presents insightful findings (Figs 2-7; 8-13). The experiments include five architectures on five datasets (many-to-many experiments). The method is shown to speed up inference, which increases with larger models and model architectures, with little to no deterioration in output quality (Tab. 1).
weaknesses: 1. Obviously, as with the original token merging and its subsequent forms, this method inherits the one same major downside: that of somewhat degraded performance. The more tokens that are merged, the faster the model performs, but the quality of the also tends to decline, and this seems to be a tradeoff (Tab. 2)
2. Another weakness is induced by the nature of the problem: time-series. In order to ensure that tokens are merged while causal relationship between observations is maintaining, setting $k = 1$ in the decoder restricts it from merging a wider set of tokens.
3. Converse to Strength 1, while the relevance of this work is broad, little analysis is done with the representations learnt: namely, the possible use of other measures of similarity measures for merging and unmerging, and the resulting impact on downstream tasks.
    
    * For instance, if my understanding is correct (see Question 5), it would make more sense to use a quantitatively informed measure to choose tokens to further merge/retain as is, such as measuring the informativeness of tokens or using better heuristics for merging [4]

4. How would this technique translate to video such as human gait analysis or datasets like EPIC Kitchens [3], for example, all time-series? Is there a reason for not experimenting on videos which still offer the causal, time-series essence? Because, such datasets are sufficiently long temporally, offering to provide more insights into Fig 4. (A recent, relevant work [5] might be of interest).
5. Another serious weakness I find is lack of comparison to other token merging algorithms. Have the authors applied current merging algorithms ([1, 2]) to time series just for comparison?

### References

1. Xie, Enze, et al. "SegFormer: Simple and efficient design for semantic segmentation with transformers." Advances in neural information processing systems 34 (2021): 12077-12090.
2. Tran, Hoai-Chau, et al. "Accelerating Transformers with Spectrum-Preserving Token Merging." arXiv preprint arXiv:2405.16148 (2024).
3. Damen, Dima, et al. "Scaling egocentric vision: The epic-kitchens dataset." Proceedings of the European conference on computer vision (ECCV). 2018.
4. Choi, Joonmyung, et al. "vid-TLDR: Training Free Token merging for Light-weight Video Transformer." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.
5. Lee, Seon Ho, et al. "Video token merging for long-form video understanding." (2024).

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. See the weakness.
2. I like the dynamic merging results it indeed can improves the FLOPS but I wonder whether it can improve throughputs or latency? The authors should validate it. Besides, it should be able to combine with merging during training setting since the k even can be learned during training.
soundness: 3
strengths: The method is simple, efficient, and effective. Experimental results demonstrate its superior acceleration across datasets and its applicability to both small-scale and large-scale models. Additionally, I appreciate the ablation study, which effectively illustrates the merging patterns and highlights where the proposed method succeeds or falls short.
summary: The authors propose an efficient, customized token-merging strategy tailored for time-series processing in transformer and state-space models. Unlike the "global" token-merging methods used in image domains, the proposed "local" token-merging approach is more efficient and better preserves the causality crucial to time-series tasks. Experimental results demonstrate the efficiency of the proposed method with minimal performance drop across various datasets. Additionally, the method shows the applicability in practical experiments for both transformer-based and state-space model (SSM) approaches.
weaknesses: My main concerns lie with the clarity of the writing. It is unclear how the authors merge the tokens—are they using averaging, max-pooling, or another method? I believe this should be explained and ablated, especially in relation to temporal issues and handling time-position embedding during token merging. These aspects are not sufficiently clear. Additionally, the authors mention an "unmerging" technique, but it is also unclear how this process is conducted

Furthermore, it is essential to conduct an ablation study on the parameter k to demonstrate the robustness of the proposed method.

---

confidence: 3
contribution: 1
initial_rating: 3
presentation: 3
questions: Following the discussion from the the "weaknesses" section:

(1) How can we understand when local token merging will perform well or not? Are there properties of the target dataset/domain that are particularly amenable or hostile to local token merging? Does this change when it is applied only during inference vs also during training?

(2) When training is in scope, how does local token merging compare against other model architectures (e.g. tokenizer + Transformer) that similarly reduce the effective input dimensionality? Depending on the results, what is the broader significance/utility of token merging?
soundness: 3
strengths: The presentation of the motivation, proposed method, and experiments is clear and easy to understand. The experiments are thorough for the presented scope, evaluating the proposed method across a variety of model architectures/sizes, and datasets/domains. I appreciate the investigation into why local token merging sometimes improves model performance, as this may seem surprising from a first glance.
summary: The paper introduces local token merging, a dimensionality-reduction method for very long sequences that can be used to lower the computational cost of training and/or inference in such domains.
Compared to prior work in token merging, the proposed method can be constrained to a local radius (which allows fine-grained control over the computational complexity of the merging process itself), and can be performed in causal manner to support autogressive decoding.
The experiments apply the proposed local token merging to a variety of Transformer and non-Transformer models across a variety of time-series datasets (long sequences but low feature dimensionality), and show that substantial speedup can be achieved at little-to-no detriment to the model accuracy, even when local token merging is only applied during inference.
weaknesses: The proposed method does not feel like a significant contribution towards the broader goal of more efficient modeling of very long timeseries data. The paper demonstrates the effectiveness of local token merging compared to global token merging, but the experiments/discussion do not effectively place it into the broader context.

I contextualize the proposed method with prior work into two ways:

(1) Methods that can be applied to existing models with no additional training. In this category, I can see the appeal of local token merging, as the experiments show a substantial reduction in computational cost at similar prediction accuracy. However, it seems to me that if applying local token merging is effective in this fashion, then that is an indication that the underlying signal does not contain very much "useful" information (could be either low entropy or low signal-to-noise ratio). This calls into question how broadly applicable this technique can be, if it can only be applied to certain types of data (even within a particular category like "timeseries data"). The comparison between local token merging and gaussian smoothing (Section 5.2; When does token merging improve model performance) exemplifies this point, as local token merging can be viewed as an "adaptive smoothing filter", whereas the gaussian filter requires a fixed window size. Even if it has limited applicability, local token merging could still have be a useful contribution, but then some insight into when/why it is applicable would be helpful to understand its impact.

(2) Methods that are incorporated during training. From this lens, local token merging can be viewed as a particular type of adaptive pooling layer. However, once the model architecture is in scope, then the set of alternatives to local token merging becomes very larger, and the experiments conducted in the paper are not sufficient to evaluate learned token merging in this context. I am particularly curious about more expressive/universal methods like learned tokenizers (continuous VAE for diffusion models [1], discrete autoencoders for multimodal LLMs [2, 3]), which offer significant compression with near-lossless reconstructions. There even exist tokenizers where the degree of compression/dimensionality reduction can be adaptive [4, 5]. One could imagine training a tokenizer (either continuous or discrete) on the timeseries datasets evaluated in this paper, and such a tokenizer could learn a compression algorithm tailored to the timeseries domain, and could employ domain-specific reconstruction metrics analogous to the perceptual losses [6] typically used for images/video. This could potentially outperform local token merging, and the cost of tokenizer training & inference is typically much less than that of the base model.

[1] R. Rombach, et al. High-Resolution Image Synthesis with Latent Diffusion Models. CVPR 2022.

[2] L. Yu, et al. MAGVIT: Masked Generative Video Transformer. CVPR 2023.

[3] D. Kondratyuk, et al. VideoPoet: A Large Language Model for Zero-Shot Video Generation. ICML 2024.

[4] Q. Yu, et al. An Image is Worth 32 Tokens for Reconstruction and Generation. arxiv: 2406.07550.

[5] W. Yan, et al. ElasticTok: Adaptive Tokenization for Image and Video. arXiv:2410.08368.

[6] R. Zhang, et al. The Unreasonable Effectiveness of Deep Features as a Perceptual Metric. CVPR 2018.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Please see weaknesses.
soundness: 2
strengths: The paper proposes a token merging scheme for time series analysis and uses extensive experiments to demonstrate the efficiency improvements. Overall, the structure of the paper is clear, and the writing is well-done.
summary: This paper proposes a token merging technique for time series analysis aimed at improving efficiency. Compared to the global token merging technique (e.g., ToMe), the proposed method reduces merging complexity from quadratic to linear.
weaknesses: 1.	Originality: The proposed token merging method is straightforward, and similar techniques have been explored in previous works, such as Crossformer (https://openreview.net/forum?id=elZoduqPe8) and CARD (https://openreview.net/forum?id=MJksrOhurE). The claim in the abstract that this paper "performs the first investigations of token merging in time series analysis" seems inaccurate.
2.	Complexity: The linear complexity regarding tokens applies only to the token merging process (which is also the case for existing token merging schemes), rather than to the entire model. This limits the contribution of the paper.
3.	Method: The method section seems too brief and lacks sufficient details, such as how the tokens are merged—are they concatenated or summed?
4.	Experiments:
(1) The naïve token merging method merges k neighboring tokens. Why not compare it with the proposed method?
(2) Large pre-trained models: The proposed method is primarily tested on Chronos. What about other large pre-trained models, such as Timer? 
(3) Small models: Regarding efficiency, why not compare with linear-based or CNN-based forecasters (e.g., DLinear)?
(4) Table 1: The base models presented do not seem to include the latest models. What about CARD (ICLR 2024) or Leddam (ICML 2024)?

Meta-review: The paper proposes a local token merging method aimed at improving computational efficiency in time-series analysis for transformer and state-space models. The key advantage is that comparing to global merging whose complexity is quadratic, local merging reduces the merge complexity to linear, enabling efficient processing of long time-series data. The merging process respects the causality inherent in time-series tasks, making it applicable for autoregressive decoding. The method can also be applied during inference without retraining the model. On the negative side, the reviewers are concerned how broadly applicable this technique can be and whether it can only be applied to certain types of data. The reviewers appreciate that local token merging improves MSE when applied to noisy timeseries, but they are worried that the quality will degrade whenever the learned representations vary significantly throughout the feature sequence, both of which are hard to tell before testing. There has been extensive message exchange among the expert reviewers and the authors. However, after thorough discussion, the reviewers still find the cons outweigh the pros. The ACs agree. The authors are encouraged to take into account the feedbacks and re-submit to a future venue.

Decision: Reject