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

• URL: http://arxiv.org/abs/2405.17951v1
• Date: Tue, 28 May 2024 08:28:18 GMT
• Title: Efficient Time Series Processing for Transformers and State-Space Models through Token Merging
• Authors: Leon Götz, Marcel Kollovieh, Stephan Günnemann, Leo Schwinn,
• Abstract summary: Token merging has shown to considerably improve the throughput of vision transformer architectures. We introduce local merging, a domain-specific token merging algorithm that selectively combines tokens within a local neighborhood. On the recently proposed Chronos foundation model, we achieve accelerations up to 5400% with only minor accuracy degradations.
• Score: 44.27818172708914
• License: http://creativecommons.org/licenses/by/4.0/
• 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% with only minor accuracy degradations.

Related papers

• Rough Transformers: Lightweight Continuous-Time Sequence Modelling with Path Signatures [46.58170057001437]
  We introduce the Rough Transformer, a variation of the Transformer model that operates on continuous-time representations of input sequences. We find that, on a variety of time-series-related tasks, Rough Transformers consistently outperform their vanilla attention counterparts.
  arXiv  Detail & Related papers  (2024-05-31T14:00:44Z)
• Leveraging 2D Information for Long-term Time Series Forecasting with Vanilla Transformers [55.475142494272724]
  Time series prediction is crucial for understanding and forecasting complex dynamics in various domains. We introduce GridTST, a model that combines the benefits of two approaches using innovative multi-directional attentions. The model consistently delivers state-of-the-art performance across various real-world datasets.
  arXiv  Detail & Related papers  (2024-05-22T16:41:21Z)
• Token Fusion: Bridging the Gap between Token Pruning and Token Merging [71.84591084401458]
  Vision Transformers (ViTs) have emerged as powerful backbones in computer vision, outperforming many traditional CNNs. computational overhead, largely attributed to the self-attention mechanism, makes deployment on resource-constrained edge devices challenging. We introduce "Token Fusion" (ToFu), a method that amalgamates the benefits of both token pruning and token merging.
  arXiv  Detail & Related papers  (2023-12-02T04:29:19Z)
• Sparse Binary Transformers for Multivariate Time Series Modeling [1.3965477771846404]
  We show that lightweight Compressed Neural Networks can achieve accuracy comparable to dense floating-point Transformers. Our model achieves favorable results across three time series learning tasks: classification, anomaly detection, and single-step forecasting. We measure the computational savings of our approach over a range of metrics including parameter count, bit size, and floating point operation (FLOPs) count.
  arXiv  Detail & Related papers  (2023-08-09T00:23:04Z)
• Toeplitz Neural Network for Sequence Modeling [46.04964190407727]
  We show that a Toeplitz matrix-vector production trick can reduce the space-time complexity of the sequence modeling to log linear. A lightweight sub-network called relative position encoder is proposed to generate relative position coefficients with a fixed budget of parameters. Despite being trained on 512-token sequences, our model can extrapolate input sequence length up to 14K tokens in inference with consistent performance.
  arXiv  Detail & Related papers  (2023-05-08T14:49:01Z)
• Robust representations of oil wells' intervals via sparse attention mechanism [2.604557228169423]
  We introduce the class of efficient Transformers named Regularized Transformers (Reguformers) The focus in our experiments is on oil&gas data, namely, well logs. To evaluate our models for such problems, we work with an industry-scale open dataset consisting of well logs of more than 20 wells.
  arXiv  Detail & Related papers  (2022-12-29T09:56:33Z)
• ClusTR: Exploring Efficient Self-attention via Clustering for Vision Transformers [70.76313507550684]
  We propose a content-based sparse attention method, as an alternative to dense self-attention. Specifically, we cluster and then aggregate key and value tokens, as a content-based method of reducing the total token count. The resulting clustered-token sequence retains the semantic diversity of the original signal, but can be processed at a lower computational cost.
  arXiv  Detail & Related papers  (2022-08-28T04:18:27Z)
• CloudAttention: Efficient Multi-Scale Attention Scheme For 3D Point Cloud Learning [81.85951026033787]
  We set transformers in this work and incorporate them into a hierarchical framework for shape classification and part and scene segmentation. We also compute efficient and dynamic global cross attentions by leveraging sampling and grouping at each iteration. The proposed hierarchical model achieves state-of-the-art shape classification in mean accuracy and yields results on par with the previous segmentation methods.
  arXiv  Detail & Related papers  (2022-07-31T21:39:15Z)
• Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
  Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. We propose Linformer and Informer to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention.
  arXiv  Detail & Related papers  (2021-12-10T06:58:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.