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

Q: Large pre-trained models: What about other large pre-trained models? A: We chose Chronos as a recent foundation model (from 2024) for our experiments, as it is available in many sizes (from 20M-710M parameters). This way, we demonstrate that token merging scales well even to very large models. Timer only features 29M-67M parameters, which is relatively small in comparison to Chronos. Some of the models in Tab. 1 with 10 Layers have a similar amount of parameters as Timer. Other foundation models such as TimesFM [4] unfortunately did not publish sufficient code to be experimented with. Despite that, we already show 9 experiments on 7 models in 5 sizes and 6 datasets. However, we try to add Timer for the camera ready version.

Q: Small models: Regarding efficiency, why not compare with linear-based or CNN-based forecasters (e.g., DLinear)? A: We focus on transformers as almost all current time series foundation models are transformer based [4,5,6,7,8]. Further, transformers are a very universal architecture operating on a set of tokens. This universality allows us to merge tokens to accelerate the model. We evaluate token merging relatively to our baselines without token merging. Despite transformers, we propose first token merging for state space models, which are another promising architecture type. In our experiments we find token merging to be orthogonal to other efficiency methods such as sparse attention.

Q: Tab. 1: What about CARD (ICLR 2024) or Leddam (ICML 2024)? A: In Tab. 1 we focused on models, that are well acknowledged in the literature and have been used as baselines in many papers. We hoped to make more comparable statements about the effectiveness of token merging this way. Our baseline models feature different inductive biases for time series, which previous works on vision [1,2] did not take into account. Autoformer and FEDformer use transformations to the frequency domain. Informer and Autoformer already apply sparse attention. We show that token merging can accelerate even these specialized models, which was not evident before.

[1] Bolya Daniel, et al. "Token merging: Your vit but faster. In International Conference on Learning Representations", 2023.
[2] Bolya Daniel, et al. "Token merging for fast stable diffusion", CVPR Workshop on Efficient Deep Learning for Computer Vision, 2023.
[3] Tran, Hoai-Chau, et al. "Accelerating Transformers with Spectrum-Preserving Token Merging." arXiv preprint arXiv:2405.16148 (2024).
[4] Das, Abhimanyu, et al. "A decoder-only foundation model for time-series forecasting", arXiv:2310.10688, 2023.
[5] Ansari, Abdul Fatir, et al. "Chronos: Learning the language of timeseries", arXiv:2403.07815, 2024.
[6] Garza, Azul, et al. "Timegpt-1", arXiv:2310.03589, 2023.
[7] Rasul, Kashif, et al. "Lag-llama: Towards foundation models for probabilistic time series forecasting", arXiv:2310.08278, 2023.
[8] Woo, et al. "Unified training of universal time series forecasting transformers", arXiv:2402.02592, 2024.

Dear Reviewer P862,

Thank you for taking the time to read our paper and for your valuable comments and suggestions. We are happy to answer them in the following:

Q: Originality
A: Crossformer and CARD are both architectures that require training and the presented concepts can not be directly applied to pretrained models. We focus on applying token merging to accelerate already trained models. This is especially important for large foundation models such as Chronos. Therefore, token merging strongly differs from Crossformer, CARD or methods like sparse attention (please see L131-143). Following [1,2,3], we view token merging as an efficiency method which can be applied during inference without requiring any training, training data or fine-tuning. Therefore, we perform first investigations of such a token merging algorithm for time series. Additionally, we propose first token merging with variable complexity for subquadratic models, first token merging for state-space models and first causal token merging for transformer decoders. We thank the reviewer for this comment and will clarify this in the paper.

Q: Complexity
A: You are correct, that the linear complexity is the complexity of the token merging algorithm itself.

• We focus on applying token merging to accelerate already trained models. To achieve this we can not alter the model architecture itself such as when replacing attention with sparse attention, which would require a retraining of the model (please see L131-143). Therefore, we can not affect the model's complexity itself.
• Token merging has quadratic complexity by default. We specifically design local merging with linear complexity to accelerate models such as Hyena that feature subquadratic complexity. Introducing a global merging operation with quadratic complexity to such models would be harmful (please see Sec 5.9).
• For long sequences, global merging's quadratic complexity introduces a substantial overhead (please see Sec 5.9). Local merging with linear complexity outperforms global merging in both latency and accuracy.
• Despite the complexity of the model architecture itself, we can accelerate models up to 55x while preserving forecasting quality.
• Merging tokens throughout the transformer layers has a cumulative effect. This way token merging effectively reduces the complexity of the whole model and enables long sequence processing. We show this in Sec. 5.6 and Sec. 5.9. Models with local merging scale favorable to long sequences.

Q: Method: The method section seems too brief A: We kindly refer to our general comment.

Q: The naive token merging method merges $k$ neighboring tokens. Why not compare it with the proposed method? A: We split all tokens into two disjoint sets before computing merging correspondences. This way, we can find all merges without having to iteratively resolve merging conflicts. Merging $k$ neighboring tokens naively would result in merging conflicts. Resolving these conflicts iteratively introduces additional overhead, mitigating the acceleration due to token merging. Therefore, this naive baseline would not be very strong. To challenge local merging in our evaluation, we compare it to sophisticated global merging as a tough baseline and outperform it. We are happy to further discuss your question in case we misinterpreted "naive token merging".

Q: Token merging during training: other compression methods such as tokenizers
A: You are right, that there is a broad spectrum of efficiency methods when training is involved. However, we mainly focus on applying token merging to accelerate already trained models, which is of great importance for emerging foundation models. We experiment with token merging during training only as an ablation to show its potential. Nevertheless, token merging has some advantages compared to other methods such as tokenizer + transformer:

• Most importantly, there is no such tokenizer (comparable to NLP etc.) for time series in literature yet. Such a tokenizer would be a different study. We find the idea of tokenizing time series very intriguing.
• A tokenizer is an extra model, which needs to be fit to the specific dataset. The generalization capability of tokenizers in the time series domain has not been shown. This is of high importance for foundation models during zero-shot inference. We show that token merging generalizes well to unseen data in our Chronos experiments. Further, no extra tokenizer model needs to be trained.
• A tokenizer requires adjustments to the training pipeline and possibly the model architecture (regression loss -> classification loss). Therefore, a tokenizer is only applicable to some architectures, whereas token merging can accelerate almost all architectures in our experiments. Token merging requires negligible changes to the training pipeline. As an example: Autoformer and FEDformer utilize frequency based tokens. A frequency transformation on more complex tokens from a tokenizer is not well defined. Therefore, a tokenizer is not applicable to these architectures whereas token merging accelerates architectures with various inductive biases.
• Similarly to a tokenizer, token merging accelerates the training process itself by reducing its complexity.
• We find token merging to perform orthogonal to other efficiency methods like sparse attention (L131-143). We think that token merging might further accelerate a model, which already employs a tokenizer for input compression.
• In contrast to a tokenizer, which compresses the input, token merging can accelerate every transformer layer with different merging rates (Sec. 5.8). This way it can adaptively reduce complexity throughout the whole transformer and is more flexible than a tokenizer that only works on input data. As an example, for the classification task, only one class token needs to remain after merging in the last layer.
• Please also see above: Token merging not only relies on redundancy of the input data, but exploits redundancy that the attention mechanism generates.
• ElasticTok [2] was published in October 2024 after the ICLR paper submission deadline. However, we will add it to our related work section for the camera-ready version.
• Finally, as we already show 9 experiments on 7 models in 5 sizes and 6 datasets. Therefore, we consider comparing to other vision / NLP methods, that have not yet been shown for time series, out of scope of this work.

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

Dear Reviewer ps2u,

Thank you for taking the time to read our paper and for your valuable comments and intriguing ideas. We are happy to answer them in the following:

Q: Token merging during inference - are there properties of the target dataset/domain that are particularly amenable or hostile to local token merging?
A: We conducted new experiments showcasing properties of the target dataset and properties of the target model that are amenable to local merging. Please see our general comment.
Further, we ablate token merging in many different settings to understand its behavior and when it works best. In most of our experiments, token merging finds Pareto optimal points. Ablations already in our paper:

• Models: We test 5 transformer models with different inductive biases for time series. Autoformer and FEDformer use transformations to the frequency domain. Informer and Autoformer already apply sparse attention. Token merging can accelerate even these specialized models. Besides that, we show token merging in the foundation model Chronos, which leverages discrete tokens. Further, we present first token merging for state space models.
• Model sizes: We show local merging on 5 different model sizes ranging from 2 to 24 layers and from ~2M to 710M parameters.
• Tasks: Local merging performs well on both forecasting and classification (Sec. 5.9)
• Settings: Local merging can be applied to speed up model training and to make the trained model more robust. However, we focus on applying token merging on already trained models during inference and in zero shot settings.
• We explain 3 distinctive merging patterns:
  • Trivial case: Local merging is a tradeoff between acceleration and quality
  • High cosine similarities inside the transformer lead to constant merging patterns. Here, local merging accelerates the model while preserving quality. (See [1] below: attention generates redundancy throughout the transformer)
  • Token merging improves quality and accelerates the model at the same time. Here, we show that token merging behaves like a low pass filter.
• Input length: Models with local merging scale favorable to long sequences. A shorter input length can not replace token merging.
• Redundancy of input tokens in the dataset:
  • For different input length and different similarity thresholds, the redundancy scales linearly.
  • Time position embedding has minimal effect on the redundancy of tokens.
• Layer-dependent merging strategies: Dynamic merging strategies are superior to a fixed $r$ in single sample settings.
• Datasets: We evaluate local merging on 5 time series datasets and 1 genomic dataset. Local merging finds Pareto optimal points on all datasets.

Besides, [1] show, that the attention of the transformer acts as a low pass filter, effectively generating more redundancy throughout the transformer layers. Therefore, token merging not only relies on redundancy of the input data but exploits redundancy that is generated natively by the transformer itself, making it more efficient. We already added this crucial information to our updated paper.

[1] D. Marin, et al. Token pooling in vision transformers. arXiv:2110.03860.

Dear Reviewer ZtFY,

Thank you for taking the time to read our paper and for your valuable comments and suggestions. We are happy to answer them in the following:

Q: Operation to merge tokens
A: We kindly refer to our general comment.

Q: Operation to unmerge tokens
A: We kindly refer to our general comment.

Q: Temporal issues and handling time-position embedding during token merging
A: We carefully design local merging with $k=1$ to preserve the casuality of the time series for proper handling of the temporal relationship. In Sec. 5.9 we demonstrate that this locality bias is advantageous over global merging strategies.
The additive time-position embedding gets incorporated into the token throughout the transformer layers. The token simultaneously represents its value and position. Therefore, token merging selectively combines tokens based on their value and position (e.g. in periodic series). Further, we ablate in Sec. 5.7 and Fig. 7a whether the temporal position embedding prevents merging and find it has only minor influence.

Q: Ablate $k$
A: In Sec. 5.9 we compare local merging with $k=1$ to global merging with $k=t_l/2$. Causal local merging outperforms global merging in terms of latency due to its linear complexity. Due to its locality bias preserving causality, local merging is also superior in terms of accuracy. In preliminary experiments we find that either $k=1$ (preserving causality, linear complexity) or $k=t_l/2$ (global merging pool) is best. Other values for $k$ were suboptimal. This is why we choose either $k=1$ or $k=t_l/2$ based on token mergings application.

Q: Dynamic merging time measurements
A: We explore the single sample setting in dynamic merging for real-time applications where one can not wait to gather a batch of samples to be processed. As we use batch size 1, the CUDA overhead, which is included in runtime measurements, is strongly GPU dependent. Therefore, we report FLOPs as a more hardware independent measure. However, in preliminary experiments, token merging also improved latency in dynamic merging settings (runtime measurements were just more noisy than FLOPs in this single sample setting).

Q: Learning $k$ during training
A: You are right that $k$ can be learned during training. However, as mentioned above, we find that either $k=t_l/2$ or $k=1$ lead to optimal results in our preliminary experiments. This is why we choose $k$ as a hyperparameter based on which token merging properties we want to achieve: either causality and linear complexity or utilizing a global merging pool. Further, we focus on applying local merging to already trained models as this is very important for large foundation models, which are expensive to train. We only show token merging during traiing as an ablation to highlight its potential.

Q: Question 1: Token merging speedup in training Autoformer is this a general trend for all architectures
A: Yes, you are correct. We experience training speedup when applying token merging during training for all architectures we experiment with in Tab. 1. We also observe less performance degredations (better MSE) from token merging when token merging has already been applied during training.

Q: Question 2: We conducted new experiments investigating the token distance measure. Please see above.

Q: Question 3: Why we suggest that local merging is domain specific
A: We suggest, that local merging is domain specific as it is designed to preserve casuality, which is a very important property of time series. But you are right that local merging might be valuable in other domains. Locality and the linear merging complexity might especially be relevant for high resolution images. We included this in our future work of our updated paper.

Q: Question 4: A: In our general comment we conduct new experiments investigating properties of the datasets that are particularly amenable to token merging. You are correct that ETTh1, ETTm1 and Traffic have considerable noise.

Q: Question 5: What is meant by "the most recent token"? A: We kindly refer to our general comment. Thank you for this interesting idea of prioritizing the merges, we already included this in our future work of our updated paper.

Q: Question 6: How is "split a merged token into two neighboring identical ones" done? A: We kindly refer to our general comment.

Thank you also for mentioning paragraph L228-238. We will make our explanation more coherent in the camera-ready version.

Dear Reviewer gi8b,

Thank you for taking the time to read our paper and for your valuable comments and questions. We are happy to answer them in the following:

Q: Weaknesses 1: Token merging is a tradeoff between quality and acceleration
A: We highlight cases in the Chronos foundation model and in Tab. 1 where token merging simultaneously accelerates the model and boosts quality. For Chronos that is often the case (see Fig. 8-10). Moreover, token merging generally leads to Pareto optimal models, where it can be beneficial to choose a lager model with token merging over a smaller one without. In the majority of our experiments token merging leads to models with faster inference speeds and higher prediction quality. We will clarify this in the paper.

Q: Weaknesses 2: Token merging in local neighborhood to preserve causality
A: We show in Sec. 5.9 that exactly this locality bias is not harmful but beneficial for long sequence processing. Here, causal local merging with $k=1$ outperforms global merging in accuracy. Additionally, local merging with linear complexity is superior to global merging with quadratic complexity in terms of latency. For long sequences, the merging overhead of quadratic global merging is substantial. Besides that, we choose the token merging neighborhood size based on its application: for long sequences or in causal decoders, we restrict the neighborhood to also profit from the mentioned locality bias (Sec. 5.9). In transformer encoders, we do not restrict the merging neighborhood and utilize a global merging pool.

Q: Weaknesses 3 and Question 2: Other similarity measures / metrics
A: We kindly refer to our general comment, where we conducted new experiments regarding quantitatively informed token similarity measure.

Q: Weaknesses 4: Video datasets
A: We restrict our analysis to the time series domain, as images and videos are out of the scope of our paper. However, Bolya et al at ICLR 2023 already ablate their global token merging for videos. We see this as a very interesting extension of our work to apply local merging also to other domains. When transferring local merging to the image domain, 2-d image based locality measured would be required.

Q: Weaknesses 5: Other token merging approaches
A: We focus on applying token merging to accelerate already trained models. This is especially important for large foundation models such as Chronos, which are expensive to train. SegFormer [1], however, needs to be trained from scratch and is not applicable to pretrained models. Further, [1,2] are methods designed for ViT encoders and do not preserve causality, which makes them inapplicable to transformer decoders. We specifically design our local merging to preserve the causal properties of time series and present first token merging for decoders. Additionally, [2] builds a fully connected graph between the tokens to find the ones to merge. This leads to quadratic complexity of their merging algorithm, which the authors list as a limitation. Quadratic complexity merging is unsuitable for long sequence processing or models like Hyena with subquadratic complexity (see Sec. 5.9, where local merging with linear complexity outperforms global merging with quadratic complexity). This is why we design our local merging with varying complexity from quadratic too linear to process long time series and to accelerate models with subquadratic complexity. We already included this discussion in our related work section in our updated paper.

Thanks for answering my questions. For the most part, things are clearer to me and I am satisfied with the answers. Thanks for Fig 15, and thanks for pointing out the experiments in Bolya's work. The reason for pointing out Weakness 5 was to get a broad picture of comparison, but I quite agree that current methods are either for other domains or don't fall within this work's scope to compare with.

As for Weakness 4, the reason I wondered how local merging would do on videos ties to the well-articulated Weakness 1 by Reviewer ps2u, particularly about the breadth of domains to which it can be applied. For my part, Sec. A.7 and the general rebuttal broadly answer this; however, if the gains as pronounced as in the new experiments are to be attributed to the information contained in the target dataset (high entropy) and merging is removing unnecessary information (assuming that information is thanks to a low signal-to-noise ratio), this is hinging upon the fact that there is sufficient noise to remove--a plus for local merging. But then, at the same time, my question is, wouldn't local merging negatively impact by losing supposedly-useless information if the entropy as well as the signal-to-noise ratio were high (a richer and less-noisier target)?