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

Leon Götz1 Marcel Kollovieh2 Stephan Günnemann2 Leo Schwinn2
1Volkswagen AG 2Technical University of Munich & Munich Data Science Institute
Correspondence to<EMAIL_ADDRESS>

###### 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\text{\,}\mathrm{\char 37\relax}$
with only minor accuracy degradations.

##  1 Introduction

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.

Since their inception in NLP [1], transformers have extended their influence
into various domains, including computer vision with Vision Transformers
(ViTs) [2], graphs [3, 4], and time series processing [5]. 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 [6]. Consequently, recent foundational models in
time series, such as Chronos, exhibit impressive zero-shot generalization
capabilities but demand substantial computational resources [7].

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

Bolya et al. [10], 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 [5]. Most of them focus on
reducing complexity by modifying the attention mechanism. LogTrans uses
LogSparse attention [5] while Informer focuses only on the most relevant
queries using ProbSparse attention [11]. Additionally, many architectures
adopt decomposition techniques to model trend and seasonal patterns [12, 13,
14, 15]. Autoformer leverages autocorrelation as a sequence-based similarity
measure in the attention mechanism [13]. FEDformer uses the frequency domain
to model time series effectively [14]. Non-stationary Transformers further
mitigate the effect of the time series distribution changing over time [15].
PatchTST embeds subsequences as tokens to capture local semantic information
and reduce complexity [16]. Other works apply hierarchical attention [17, 18]
or leverage attention between the time series variates to better model
multivariate patterns [19, 20].
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 [21, 22, 23,
24]. 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 [7]. Besides,
other research branches focus on fine-tuning vision or NLP models for time
series [25] and on applying large language models directly on time series data
[26].

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
[27]. The S4 model reduces memory requirements by conditioning the state-space
matrix with a low-rank correction [28]. By using implicit convolutions and a
data-aware gating mechanism, Hyena [8] 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 [29].

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 [30, 31]. Marin et al. [32] merge tokens in ViT architectures to
reduce the loss of information associated with pruning. Bolya et al. [10]
enhance the token merging algorithm, which they successfully apply to already
trained models. Besides initial work on classification tasks [10], subsequent
work applies token merging to diffusion models [33]. Kim et al. [34] combine
merging and pruning, while other work investigates optimal merging and pruning
rates [35, 36].

Here, we propose a token-merging algorithm for the time series domain, which
extends beyond previous investigations of token-merging in ViTs [10, 33]. 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. [10] 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. [10]
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 [10, 33]. 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 [6, 37], and state-
space models featuring subquadratic complexity [8, 9].
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 [7]. 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 [1] 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$$ [7]. 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 [9] based on the Hyena architecture [8]. 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 [10]. 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 [38]. 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 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.

###  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
[39], computer vision [40], and time series processing [22]. 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 [7]. 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 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. 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.

###  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 [10].

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

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 [41, 42]. 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 6: Effect of different input lengths on forecasting quality (left) and
model execution time (right) for token merging in Chronos small models on
ETTh1.

###  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.

(a) Token redundancy

(b) Dynamic merging

Figure 7: (a) Relative number of redundant tokens for different similarity
thresholds on ETTh1 with and without added positional embedding. (b)
Comparison of dynamic merging based on a similarity threshold with fixed $r$
merging in single-sample settings for Chronos small on ETTh1.

###  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 [43, 44].

#### Disclaimer

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

## References

  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Dosovitskiy et al. [2021] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.
  * Yun et al. [2019] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, and Hyunwoo J Kim.  Graph transformer networks.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Geisler et al. [2023] Simon Geisler, Yujia Li, Daniel J Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru.  Transformers meet directed graphs.  In _International Conference on Machine Learning_ , 2023.
  * Li et al. [2019] 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.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Godahewa et al. [2021] Rakshitha Wathsadini Godahewa, Christoph Bergmeir, Geoffrey I. Webb, Rob Hyndman, and Pablo Montero-Manso.  Monash time series forecasting archive.  In _Neural Information Processing Systems Datasets and Benchmarks Track_ , 2021.
  * Ansari et al. [2024] Abdul Fatir Ansari, Lorenzo Stella, Caner Turkmen, Xiyuan Zhang, Pedro Mercado, Huibin Shen, Oleksandr Shchur, Syama Sundar Rangapuram, Sebastian Pineda Arango, Shubham Kapoor, Jasper Zschiegner, Danielle C. Maddix, Hao Wang, Michael W. Mahoney, Kari Torkkola, Andrew Gordon Wilson, Michael Bohlke-Schneider, and Yuyang Wang.  Chronos: Learning the language of time series.  _arXiv:2403.07815_ , 2024.
  * Poli et al. [2023] Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Re.  Hyena hierarchy: Towards larger convolutional language models.  In _International Conference on Machine Learning_ , 2023.
  * Nguyen et al. [2023] Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Michael Wornow, Callum Birch-Sykes, Stefano Massaroli, Aman Patel, Clayton Rabideau, Yoshua Bengio, Stefano Ermon, Christopher Ré, and Stephen Baccus.  Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Bolya et al. [2023] Daniel Bolya, Cheng-Yang Fu, Xiaoliang Dai, Peizhao Zhang, Christoph Feichtenhofer, and Judy Hoffman.  Token merging: Your vit but faster.  In _International Conference on Learning Representations_ , 2023.
  * Zhou et al. [2021] 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 _AAAI Conference on Artificial Intelligence_ , 2021.
  * Woo et al. [2022] Gerald Woo, Chenghao Liu, Doyen Sahoo, Akshat Kumar, and Steven Hoi.  Etsformer: Exponential smoothing transformers for time-series forecasting.  _arXiv:2202.01381_ , 2022.
  * Wu et al. [2021] Haixu Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long.  Autoformer: Decomposition transformers with auto-correlation for long-term series forecasting.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Zhou et al. [2022] Tian Zhou, Ziqing Ma, Qingsong Wen, Xue Wang, Liang Sun, and Rong Jin.  Fedformer: Frequency enhanced decomposed transformer for long-term series forecasting.  In _International Conference on Machine Learning_ , 2022.
  * Liu et al. [2022a] Yong Liu, Haixu Wu, Jianmin Wang, and Mingsheng Long.  Non-stationary transformers: Exploring the stationarity in time series forecasting.  In _Advances in Neural Information Processing Systems_ , 2022a.
  * Nie et al. [2023] Yuqi Nie, Nam H Nguyen, Phanwadee Sinthong, and Jayant Kalagnanam.  A time series is worth 64 words: Long-term forecasting with transformers.  In _International Conference on Learning Representations_ , 2023.
  * Liu et al. [2022b] Shizhan Liu, Hang Yu, Cong Liao, Jianguo Li, Weiyao Lin, Alex X. Liu, and Schahram Dustdar.  Pyraformer: Low-complexity pyramidal attention for long-range time series modeling and forecasting.  In _International Conference on Learning Representations_ , 2022b.
  * Cirstea et al. [2022] Razvan-Gabriel Cirstea, Chenjuan Guo, Bin Yang, Tung Kieu, Xuanyi Dong, and Shirui Pan.  Triformer: Triangular, variable-specific attentions for long sequence multivariate time series forecasting–full version.  _arXiv:2204.13767_ , 2022.
  * Zhang and Yan [2023] Yunhao Zhang and Junchi Yan.  Crossformer: Transformer utilizing cross-dimension dependency for multivariate time series forecasting.  In _International Conference on Learning Representations_ , 2023.
  * Liu et al. [2023] Yong Liu, Tengge Hu, Haoran Zhang, Haixu Wu, Shiyu Wang, Lintao Ma, and Mingsheng Long.  Itransformer: Inverted transformers are effective for time series forecasting.  _arXiv:2310.06625_ , 2023.
  * Garza and Mergenthaler-Canseco [2023] Azul Garza and Max Mergenthaler-Canseco.  Timegpt-1.  _arXiv:2310.03589_ , 2023.
  * Das et al. [2023] Abhimanyu Das, Weihao Kong, Rajat Sen, and Yichen Zhou.  A decoder-only foundation model for time-series forecasting.  _arXiv:2310.10688_ , 2023.
  * Rasul et al. [2023] Kashif Rasul, Arjun Ashok, Andrew Robert Williams, Hena Ghonia, Rishika Bhagwatkar, Arian Khorasani, Mohammad Javad Darvishi Bayazi, George Adamopoulos, Roland Riachi, Nadhir Hassen, Marin Biloš, Sahil Garg, Anderson Schneider, Nicolas Chapados, Alexandre Drouin, Valentina Zantedeschi, Yuriy Nevmyvaka, and Irina Rish.  Lag-llama: Towards foundation models for probabilistic time series forecasting.  _arXiv:2310.08278_ , 2023.
  * Woo et al. [2024] Gerald Woo, Chenghao Liu, Akshat Kumar, Caiming Xiong, Silvio Savarese, and Doyen Sahoo.  Unified training of universal time series forecasting transformers.  _arXiv:2402.02592_ , 2024.
  * Zhou et al. [2023] Tian Zhou, Peisong Niu, xue wang, Liang Sun, and Rong Jin.  One fits all: Power general time series analysis by pretrained lm.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Gruver et al. [2023] Nate Gruver, Marc Finzi, Shikai Qiu, and Andrew G Wilson.  Large language models are zero-shot time series forecasters.  In _Advances in Neural Information Processing Systems_ , 2023.
  * Gu et al. [2021] Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré.  Combining recurrent, convolutional, and continuous-time models with linear state space layers.  In _Advances in Neural Information Processing Systems_ , 2021.
  * Gu et al. [2022] Albert Gu, Karan Goel, and Christopher Re.  Efficiently modeling long sequences with structured state spaces.  In _International Conference on Learning Representations_ , 2022.
  * Gu and Dao [2023] Albert Gu and Tri Dao.  Mamba: Linear-time sequence modeling with selective state spaces.  _arXiv:2312.00752_ , 2023.
  * Meng et al. [2022] Lingchen Meng, Hengduo Li, Bor-Chun Chen, Shiyi Lan, Zuxuan Wu, Yu-Gang Jiang, and Ser-Nam Lim.  Adavit: Adaptive vision transformers for efficient image recognition.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2022.
  * Goyal et al. [2020] Saurabh Goyal, Anamitra Roy Choudhury, Saurabh Raje, Venkatesan Chakaravarthy, Yogish Sabharwal, and Ashish Verma.  Power-bert: Accelerating bert inference via progressive word-vector elimination.  In _International Conference on Machine Learning_ , 2020.
  * Marin et al. [2021] Dmitrii Marin, Jen-Hao Rick Chang, Anurag Ranjan, Anish Prabhu, Mohammad Rastegari, and Oncel Tuzel.  Token pooling in vision transformers.  _arXiv:2110.03860_ , 2021.
  * Bolya and Hoffman [2023] Daniel Bolya and Judy Hoffman.  Token merging for fast stable diffusion.  _CVPR Workshop on Efficient Deep Learning for Computer Vision_ , 2023.
  * Kim et al. [2024] Minchul Kim, Shangqian Gao, Yen-Chang Hsu, Yilin Shen, and Hongxia Jin.  Token fusion: Bridging the gap between token pruning and token merging.  In _IEEE Winter Conference on Applications of Computer Vision_ , 2024.
  * Bonnaerens and Dambre [2023] Maxim Bonnaerens and Joni Dambre.  Learned thresholds token merging and pruning for vision transformers.  _Transactions on Machine Learning Research_ , 2023.
  * Chen et al. [2023] Mengzhao Chen, Wenqi Shao, Peng Xu, Mingbao Lin, Kaipeng Zhang, Fei Chao, Rongrong Ji, Yu Qiao, and Ping Luo.  Diffrate: Differentiable compression rate for efficient vision transformers.  In _IEEE International Conference on Computer Vision_ , 2023.
  * Grešová et al. [2023] Katarína Grešová, Vlastimil Martinek, David Čechák, Petr Šimeček, and Panagiotis Alexiou.  Genomic benchmarks: a collection of datasets for genomic sequence classification.  In _BMC Genomic Data_ , 2023.
  * Zhu [2022] Ligeng Zhu.  Thop: Pytorch-opcounter.  https://github.com/Lyken17/pytorch-OpCounter, 2022.
  * Touvron et al. [2023] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample.  Llama: Open and efficient foundation language models.  _arXiv:2302.13971_ , 2023.
  * Kirillov et al. [2023] Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan-Yen Lo, Piotr Dollar, and Ross Girshick.  Segment anything.  In _IEEE International Conference on Computer Vision_ , 2023.
  * Zeng et al. [2023] Ailing Zeng, Muxi Chen, Lei Zhang, and Qiang Xu.  Are transformers effective for time series forecasting?  In _AAAI Conference on Artificial Intelligence_ , 2023.
  * Li et al. [2023] Zhe Li, Shiyi Qi, Yiduo Li, and Zenglin Xu.  Revisiting long-term time series forecasting: An investigation on linear mapping.  _arXiv:2305.10721_ , 2023.
  * Schwinn et al. [2021] Leo Schwinn, An Nguyen, René Raab, Leon Bungert, Daniel Tenbrinck, Dario Zanca, Martin Burger, and Bjoern Eskofier.  Identifying untrustworthy predictions in neural networks by geometric gradient analysis.  In _Uncertainty in Artificial Intelligence_ , 2021.
  * Schwinn et al. [2022] Leo Schwinn, Leon Bungert, An Nguyen, René Raab, Falk Pulsmeyer, Doina Precup, Björn Eskofier, and Dario Zanca.  Improving robustness against real-world and worst-case distribution shifts through decision region quantification.  In _International Conference on Machine Learning_ , 2022.
  * Cowen-Rivers et al. [2022] Alexander Cowen-Rivers, Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan-Rhys Griffiths, Alexandre Maravel, Jianye Hao, Jun Wang, Jan Peters, and Haitham Bou Ammar.  Hebo: Pushing the limits of sample-efficient hyperparameter optimisation.  In _Journal of Artificial Intelligence Research_ , 2022.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy L. Ba.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations_ , 2015.

##  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 [11]. Weather consists
of $21$ meteorological quantities such as air temperature and is recorded
every $10$ minutes in $2020$.111https://www.bgc-jena.mpg.de/wetter/
Electricity measures the energy demand of $321$ consumers every hour [6].
Traffic consists of $862$ sensors in the San Francisco Bay Area measuring the
road occupancy hourly [6]. We use the same data splits for training,
validation and test as [13] 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 [37] 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 [45]. 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 [9] and for testing Chronos [7] we used their default
hyperparameters.

Table 4: Hyperparameters for training the transformer models. Hyperparameter | Value
---|---
Training |
Seed | 2024
Optimizer |  Adam [46]
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 8: Token merging in different Chronos models on ETTh1 Figure 9: Token
merging in different Chronos models on ETTm1 Figure 10: Token merging in
different Chronos models on Weather Figure 11: Token merging in different
Chronos models on Electricity Figure 12: Token merging in different Chronos
models on Traffic

###  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 13: Comparing token merging to smoothing the input time series of
Chronos small on different datasets.

###  A.5 Dependencies on input length

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

Figure 14: Varying the input length of Chronos small on ETTh1.