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

Dear Reviewer 6Amp,

Thank you for taking the time to read our paper and for your valuable questions. We are happy to answer them in the following. To this end, we conducted 5 new experiments. Please find anonymous results here: https://figshare.com/s/679d2c1d825228385b2d

Q: Gap between token merging in CV and time series.
A: Prior work in CV only used quadratic token merging in non-causal transformer encoders. We design token merging for time series:

• Long sequences: Time series often consist of very long sequences, as opposed to CV (L122). Here, quadratic global merging introduces a significant computational burden. We propose local merging with linear complexity. (tab. 5, 16k long sequences).
• Decoders: In CV, token merging is applied to non-causal encoders. However, for time series, endoder-decoder or decoder-only models are common. Local merging is the first causal merging scheme for decoders. Further, causality is a good inductive bias for time series (tab. 5, L417-426), improving MSE. In contrast to images, real-world time series are generated by causal processes.
• Forecasting: In CV, most works focus on classification where only 1 cls token needs to be preserved. We use forecasting as a dense task where reducing tokens might be more difficult. To this end, we propose causal unmerging to restore a required number of output tokens.
• SSM: Prior work focuses on transformers. We are the first to merge tokens in ssm.
• We propose dynamic merging to mitigate the issue of dissimilar tokens being merged. Prior work utilized fixed merging rates per layer.
• Besides these technical aspects, our detailed analysis of local merging, such as why it improves MSE, is way beyond literature.

We will highlight these differences in our paper

Q: Dynamic merging in batch settings.
A: Thank you for this nice suggestion. We conducted new experiments for dynamic merging in batched settings. To retain rectangular tensors, we average the number of tokens to be merged among the elements in a batch. For batch size 10 dynamic merging is still better than fixed r merging. Variable token counts per batch element do not hinder practical usage.

Q: Would results hold on the full ETTh1 test set?
A: We subsample 7000 time series for chronos experiments. We have made additional efforts to compare results of the subsampled test set to the full ETTh1 test set. Results also hold for the full set.

Q: Section B.1 upper bound for speed up ignores overhead.
A: You are correct. As the overhead varies between models and implementation, we derive this upper bound theoretically. For our experiments, however, we report the execution time rather than the FLOPs as it includes all overheads.

Q: Fig. 9 uses only Autoformer.
A: This is a good point. For this ablation, we only borrow the trained position embedding from Autoformer. It is quite similar to the one Transformer, Informer, FEDformer and Non-stationary use. The actual model has no effect. We therefore hope to make broad statements.

Q: Merging and pruning.
A: This is a great addition. We conducted new experiments to compare merging and pruning, which is used by DynamicViT. Merging results in better MSE, as it retains more information, and comparable speed up. Further, as opposed to DynamicViT, our pruning does not require any training and is zero-shot-applicable.

Q: Tokenization and token merging
A: In our experiments, the models use 3 different types of tokenization:

• Models in tab. 1 use multivariate tokens
• Chronos uses a discrete vocabulary
• Hyena builds tokens from nucleotides

Autoformer and FEDformer further use the frequency domain. Local merging works on top of all token types. We argue that the tokenization method is of minor importance. We conduct new experiments to include PatchTST. Preliminary results show, that local merging also works on patches.
Technical differences: Patching compresses only the input data and requires model training (architectural change). Token merging is a general method that accelerates a variety of models in zero-shot setting. It exploits redundancy in every layer (L807-809, transformers generate redundancy). Thanks for pointing us to this missing detail.

Q: Mamba as SSM
A: Thank you for this suggestion. We added Mamba for this rebuttal. Local merging achieves over 4x acceleration with only 1.6% drop in accuracy.

Q: Lack of details for SSM merging
A: We are happy to include more details. Do you have specific aspects in mind? We already analyzed the wall-clock time in more detail: The similarity computation of local merging adds 14% of additional wall-clock time to each hyena block, while global merging takes additional 68%. This highlights the value of linear complexity.

Thank you also for pointing us to sec. 5.4 spectral analysis. We will clarify "signal entropy" and "noise". We are happy to further discuss any open questions.

Dear Reviewer mSjb,

Thank you for your valuable feedback and effort.

The "Rough Transformers" paper is very interesting and we will further discuss it in our related work section. Thank you for pointing us to that. We would like to emphasize that we see local merging as a method to accelerate a variety of models without needing to retrain or finetune them. Local merging is not only applicable to transformers but also to state space models. "Rough Transformers" on the other hand is a specifically designed model architecture.

Q: Do the authors feel that similar techniques could be used in language?
A: This is a great point. We do think that local merging might help to boost the efficiency of language models. Our causal merging and causal unmerging is the first token merging technique applicable to decoders, making it very valuable for decoder or encoder-decoder language models. Previous work in vision breaks causality and is not applicable to decoder models as used in NLP. For long contexts, local mergings linear complexity is particularly helpful.

Further, we have made several improvements to our work and present new results in our comments to review 6Amp. We are happy to further discuss any open questions.

Dear Reviewer eLzT,

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

Q: Local merging is a minimal contribution.
A: We see our main contribution in investigating token merging for time series in great detail. Additionally, we propose new mechanisms to extend token merging to causal decoders, state-space models and long sequences. (Please see our Rebuttal on Review 6Amp for a full list of novelties)

Q: Does linear complexity translate to wall-clock time?
A: We think this is a great point. We compare global merging with local merging in sec. 5.8 and tab. 5. Using subquadratic ssm and a very long context of 16k tokens, we showcase the advantage of linear complexity. Computing the cosine similarity of all tokens in global merging has a significant overhead, resulting in only 2.92x speed up while local merging achieves greater acceleration of 3.62x. For this rebuttal, we investigate the wall-clock time in more detail. The similarity computation of local merging adds 14% of additional wall-clock time to each hyena block. For global merging, however, this is an additional 68% of wall-clock time. Thank you for pointing us to this missing detail, we will clarify that in our paper.

Q: Is preserving causality important for time series?
A: Thanks for bringing this up, you understood it correctly, and we will explain it more explicitly. Preserving causality has two important aspects: First, it enables token merging in decoder models, which are commonly used in time series processing. Previous work only focused on encoders. Second, causality and order seems to be a good inductive bias for time series, as we show in tab. 5. Here, it is better to rely on a smaller merging pool while preserving causality (74% vs. 69% accuracy, L417-418, L424-432). Intuitively, real-world time series are generated by causal processes.

Q: Gaussian filtering does not demonstrate that this is what token merging does.
A: Gaussian filtering smoothes the time series acting, as a low pass filter. We argue that averaging two tokens also reduces noise, but in an adaptive manner as only similar tokens are merged. To validate our intuition, we compare local merging to gaussian filtering on 5 datasets. On datasets where gaussian filtering improves forecasting quality, local merging also improves quality. On Electricity, both gaussian filtering and local merging are not effective (fig. 4, 15). We further validate the low-pass-filtering hypothesis by correlating local mergings MSE improvements to dataset properties related to noise (see Dataset properties in sec. 5.4). Please note that we try to show that local merging acts as an adaptive filtering algorithm. Not that it is the same as gaussian filtering. We agree that our comparison is not absolute, but we gather lots of evidence that local merging can be compared to gaussian filtering.

Q: Table 1, Autoformer and Informer have rows with no speed up.
A: In these experiments, we apply token merging only during inference. This disturbs some models too much. Thus, we report the results without merging (see L228-233, L251-255). However, in sec. 5.2 we show that we can accelerate these models when applying token merging during training. This way the models can adapt to token merging.

Q: The gaussian + merging line missing from Figure 4 b.
A: This is intentional, as you correctly guessed, the gaussian + merging line was exactly following the gaussian line.

Q: Acceleration measure?
A: Thank you for pointing this out. We base our acceleration on the wall-clock time (see L703) as we think it is the practically most relevant measure. However, not reported in the paper, we notice even larger accelerations in FLOPs in all experiments as they do not measure GPU overhead.

Q: Important plots in the appendix.
A: Due to the page limit we moved many results to the appendix. We will restructure the final paper.

Q: Ablate neighborhood size k.
A: In our preliminary experiments we find that either k=1 (linear complexity, causality, locality bias) or k=tl/2 (global merging pool) leads to best results. In many transformer encoders that already exhibit large computational cost, we utilize k=tl/2 to profit from a global merging pool (L679-683). In decoders, ssm, and for long sequence processing we find local merging with k=1 to work best (sec. 5.8). Other values for k were suboptimal. We will add this crucial information to the paper.

Q: How we chose hyperparameter r.
A: We do 185 hyperparameter optimization trials to find the best r (see L692-694) satisfying our tolerated MSE drop (see L227-230) for every model. In fig. 2,3,4,5,7 r is plotted as the color bar and the different points in the diagram.

Thank you for also finding a typo. We are happy to further discuss any open questions. We present new results in our comment to review 6Amp.

Dear Reviewer HVPc,

Thank you for taking the time to read our paper. We would like to address your concerns in the following:

Q: Write-up of the paper
A: We are sorry, that you were confused by the write-up. We will rework the writeup of our Methods and Introduction section to point out our contributions more clearly.

Q: Contributions
A: Previous work in CV only used quadratic token merging in non-causal transformer encoders. We design token merging for time series:

• Long sequences: Time series often consist of very long sequences, as opposed to CV (L122). Here, quadratic global merging introduces a significant computational overhead. We propose local merging with linear complexity. (see tab. 5, 16k long sequences).
• Decoders: In CV, token merging is applied to non-causal encoders. However, for time series, endoder-decoder or decoder-only models are commonly used. Local merging is the first causal merging scheme for decoders. Further, causality is a good inductive bias for time series (tab. 5, L417-426), improving MSE. In contrast to images, real-world time series are generated by causal processes.
• Forecasting: In CV, most works focus on classification where only 1 cls token needs to be preserved. We, however, use forecasting as a dense task where reducing tokens might be more difficult. To this end, we propose causal unmerging to restore a required number of output tokens.
• SSM: Previous work only focuses on transformers. We are the first to merge tokens in ssm.
• We propose dynamic merging to mitigate the issue of dissimilar tokens being merged. Previous work utilized fixed merging rates per layer.
• Besides these technical aspects, our detailed analysis of local merging, such as why it improves MSE, is way beyond literature.

Due to the page limit and the large amount of experiments, we had to move some aspects to the appendix. However, that seems to cause confusion. We will list our contributions more clearly in the Method and Introduction section.

Q: No experiments regarding causality
A: Preserving causality has two advantages. First, it enables token merging in transformer decoders. Our main experiment in tab. 1 therefore demonstrates causal merging implicitly as we merge tokens in the encoder and the decoder. Second, causality is a good inductive bias for time series. We show that when comparing local merging with k=1 to global merging in sec. 5.8 and tab. 5. Global merging can exploit a larger merging pool with more similar tokens. However, local merging is still better due to its causal locality bias (74% vs. 69% accuracy, L417-418, L424-432). Reviewers mSjb and 6Amp find our causality claim well supported. Thank you for pointing us to that. We will mention the link to causality more explicitly in these experiments.

Q: The paper seems to be having difficulty taking a single stance on their claims. Lines 243~246, in both columns, seem to claim the proposed local merging improves both accuracy and efficiency. But Lines 354 ~356, some results in Table 1 imply reducing tokens would decrease accuracy.
A: We investigate token merging from different points of view. Sometimes token merging improves MSE while accelerating the model at the same time. This is mostly true for chronos models in sec. 5.3 and L82-89. In other settings, token merging accelerates the model at some cost of MSE. This is mostly true for the models in tab 1. We find empirical and theoretical explanations for these different behaviors in sec. 5.4 and 5.5. We think that an evaluation from both points of view (finding the best MSE and finding the fastest model at some MSE cost) is very valuable. Both settings relate to different practical applications, i.e., finding the best or the fastest model. We argue that our objective evaluation is therefore especially valuable, rather than focussing on a single setting. We try to disentangle both settings in the write-up of the final paper.

Q: Colors in figure 1
A: Thank you for pointing us to this figure. The colors illustrate how different merging distances correspond to entries in the similarity matrix and to different values of k, i.e., which merging correspondences are valid for a given k and which reduced similarity set has to be computed. To avoid further confusion, we will reduce the matrix in fig. 1 to 3x3 (tokens 1 to 6).

We hope we could address your concerns and we are happy to answer any follow-up questions. Further, we have made several improvements to our work and present new results in our comments to review 6Amp.