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

Authors: Leon Götz, Marcel Kollovieh, Stephan Günnemann, Leo Schwinn
Primary area: learning on time series and dynamical systems
Keywords: Token Merging, Efficient Time Series Processing, Transformers, State-Space Models

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. We further introduce local merging, a domain-specific token merging algorithm that selectively combines tokens within a local neighborhood, achieving two major benefits:  a) Local merging can adjust its the computational complexity from quadratic to linear based on the neighborhood size to effectively scale token merging to long sequences; b) Local merging is the first causal merging scheme enabling token merging in transformer decoders. 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% with only minor accuracy degradations.

Decision: reject
Reviewer scores: 5, 6, 3, 5

Reviews and discussion:
<thread>
creation date:
1729741678729

thread_type:
official_review

<thread_object>
creator: reviewer_p862

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

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.

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)?

questions:
Please see weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730582094187

thread_type:
official_review

<thread_object>
creator: reviewer_ps2u

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

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.

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.

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730681773073

thread_type:
official_review

<thread_object>
creator: reviewer_ztfy

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

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730688758827

thread_type:
official_review

<thread_object>
creator: reviewer_gi8b

<content>
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).

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.

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

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].
</content>
</thread_object>

</thread>
<thread>
creation date:
1732111010485

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Comment - Question to the Reviewers

comment:
### Question to the Reviewers
**We included our new ablations and findings in the appendix on pages 22-25. We kindly ask the Reviewers for their opinion on which new experiments to include in the main text of our paper.** Besides our experiments, we already included many of the Reviewers comments in our paper (marked in red). For the camera-ready version we will shorten our paper again to 10 pages.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732111046173

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Comment - Additional Experiments

comment:
### Additional experiments:

**Other similarity measures / metrics** \
We explore different metrics to determine token similarity during token merging. In our paper we follow Bolya et al at ICLR 2023 using the cosine similarity. In our new experiment, we also include the L1/L2 norm as magnitude aware metrics. We use Chronos small on ETTh1 as base model. Our experiment shows that the cosine similarity outperforms both, the L1 and L2 norm. For further ablation, we kindly refer to the vision token merging paper by Bolya et al at ICLR 2023 (Tab. 1b). Please see page 22 for the results in our updated paper.

**Properties of the target dataset that are particularly amenable or hostile to local token merging** \
In this analysis, we correlate the quality gains due to token merging with properties of the target dataset. This way we can predict how well token merging will work on a new dataset and gain more insights in the behavior of token merging itself. We find that gains in forecasting quality due to token merging (see Tab. 2, Best) correlate with the spectral entropy of the dataset. Specifically, local merging achieves higher quality gains on high entropy datasets, such as ETTh1, ETTm1 and Traffic. We argue that local merging removes unnecessary information from complex signals with high entropy using its selective smoothing ability (Sec. 5.5). This allows the model to focus on only the relevant patterns of a signal and to achieve better prediction quality. Besides the spectral entropy, the same correlation is evident in the total harmonic distortion. Local merging adaptively low-pass-filters noisy distorted signals to condense the most relevant patterns and effectively improves the signal-to-noise-ratio. This greater noise in ETTh1, ETTm1 and Traffic compared to Weather and Electricity can also be visually inspected in the respective frequency spectrum. Therefore, we expect larger prediction quality gains when applying local merging on high entropy signals with a low signal-to-noise ratio. The results are summarized in the following table. Please also see pages 23, 24 in our updated paper.



| Dataset     | MSE$_{\Delta}$ (negative is better) | Spectral Entropy | Total Harmonic Distortion |
| ----------- | ----------------------------------- | ---------------- | ------------------------- |
| ETTh1       | -6%                                 | 4.55             | 54.93                     |
| ETTm1       | -4%                                 | 4.64             | 70.23                     |
| Weather     | -1%                                 | 1.64             | 13.15                     |
| Electricity | 0%                                  | 2.24             | 15.77                     |
| Traffic     | -9%                                 | 2.96             | 19.78                     |

\
**Properties of the target model that are particularly amenable or hostile to local token merging** \
Besides properties of the dataset, we find properties of the model that are amenable to local merging. We analyze the average cosine similarity of tokens in the models (Tab. 1) after the first transformer layer. We find that local merging accelerates model such as the Nonstationary Transformer, which learn more similar token representations, without quality degradations. Models that show quality degradations when applying local merging like the Informer have learned a dissimilar token representation. Therefore, local merging favors models that learn similar token representations.



| Model                          | Quality degradation (see Tab. 1)                          | Token similarity |
| ------------------------------ | -------------------------------------------------------- | ---------------- |
| Informer 2 Layers Traffic      | 6%                                                       | 0.10             |
| Informer 4 Layers  Electricity | 7%                                                       | 0.22             |
| Informer 8 Layers  ETTh1       | 9%                                                       | 0.28             |
| Informer 6 Layers  Weather     | 2%                                                       | 0.35             |
| Informer 6 Layers ETTm1        | -1%                                                      | 0.40             |
| Nonstationary 10 Layers ETTh1  | 0%                                                       | 0.77             |
| Nonstationary 8 Layers  ETTh1  | 0%                                                       | 0.82             |
| Nonstationary 6 Layers Weather | 0%                                                       | 0.87             |
| Transformer 10 Layers ETTm1    | 0%                                                       | 0.99             |
</content>
</thread_object>

</thread>
<thread>
creation date:
1732111070093

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Comment

comment:
Dear Reviewers,

Thank you for your valuable feedback and effort. We've made several improvements to our work and incorporated them in the updated version of our paper. We are happy to discuss any open questions. In this general comment, we would like to further elaborate the exact operation to merge and to unmerge tokens.

**Q:** Operation to merge tokens \
**A:** You are correct, we merge tokens by averaging them. Due to the computational cost of the performed experiments we had to prioritize, which design decisions are most important to ablate. In this case, we rely on previous results from Bolya et al at ICLR 2023, who ablate stacking / concatenation, averaging and keeping one token / max-pooling in their Tab. 1c,d and find that averaging is most effective. We focus our ablations on time series specific details of token merging.

**Q:** Operation to unmerge tokens \
**A:** Coherent with our merging operation (averaging) of two tokens, we unmerge them. We clone / copy a previously merged token $t$ to two neighboring tokens $t_1 \leftarrow t$ and $t_2 \leftarrow t$. This way we preserve causality. Additionally, we unmerge the tokens after the last transformer layer to utilize the cumulative effect of reducing tokens for long sequence processing. In contrast, Bolya and Hoffman do not preserve causality and unmerge immediately after every merge, which would introduce a large computational overhead in long sequence processing.

**Q:** What is meant by "the most recent token"?
**A:** Thanks for pointing this out. You are correct, we exclude the token with the latest positional encoding / the most recent time series sample / measurement from merging when encountering odd numbers of tokens. It in also an intriguing idea to merge tokens based on a priority, i.e., forcing to merge older tokens first. We think that this also depends on the time series itself. In some cases, past events might be more relevant than more recent data (such as for periodic data).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732539668012

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Friendly Reminder

comment:
We are writing to kindly check if you've had the chance to review our rebuttal response. We believe we could adress most of the raised concerns. If you have any remaining questions or concerns, we'd be happy to address them.

Thank you for your time and consideration.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.