Scaling Attention to Very Long Sequences in Linear Time with Wavelet-Enhanced Random Spectral Attention (WERSA)

• URL: http://arxiv.org/abs/2507.08637v1
• Date: Fri, 11 Jul 2025 14:40:40 GMT
• Title: Scaling Attention to Very Long Sequences in Linear Time with Wavelet-Enhanced Random Spectral Attention (WERSA)
• Authors: Vincenzo Dentamaro,
• Abstract summary: Transformer models are computationally costly on long sequences since regular attention has quadratic $O(n2)$ time complexity.<n>We introduce Wavelet-Enhanced Random Spectral Attention (WERSA), a novel mechanism of linear $O(n)$ time complexity.<n>By significantly reducing computational loads without compromising accuracy, WERSA makes possible more practical, more affordable, long-context models.
• Score: 1.7622426179653563
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformer models are computationally costly on long sequences since regular attention has quadratic $O(n^2)$ time complexity. We introduce Wavelet-Enhanced Random Spectral Attention (WERSA), a novel mechanism of linear $O(n)$ time complexity that is pivotal to enable successful long-sequence processing without the performance trade-off. WERSA merges content-adaptive random spectral features together with multi-resolution Haar wavelets and learnable parameters to selectively attend to informative scales of data while preserving linear efficiency. Large-scale comparisons \textbf{on single GPU} and across various benchmarks (vision, NLP, hierarchical reasoning) and various attention mechanisms (like Multiheaded Attention, Flash-Attention-2, FNet, Linformer, Performer, Waveformer), reveal uniform advantages of WERSA. It achieves best accuracy in all tests. On ArXiv classification, WERSA improves accuracy over vanilla attention by 1.2\% (86.2\% vs 85.0\%) while cutting training time by 81\% (296s vs 1554s) and FLOPS by 73.4\% (26.2G vs 98.4G). Significantly, WERSA excels where vanilla and FlashAttention-2 fail: on ArXiv-128k's extremely lengthy sequences, it achieves best accuracy (79.1\%) and AUC (0.979) among viable methods, operating on data that gives Out-Of-Memory errors to quadratic methods while being \textbf{twice as fast} as Waveformer, its next-best competitor. By significantly reducing computational loads without compromising accuracy, WERSA makes possible more practical, more affordable, long-context models, in particular on low-resource hardware, for more sustainable and more scalable AI development.

Related papers

• DeltaLLM: A Training-Free Framework Exploiting Temporal Sparsity for Efficient Edge LLM Inference [19.987309147268586]
  We present DeltaLLM, a training-free framework that exploits temporal sparsity in attention patterns to enable efficient LLM inference on resource-constrained edge devices.<n>We evaluate our framework on the edge-device-friendly BitNet-b1.58-2B-4T model and Llama3.2-1B-Instruct model across diverse language tasks.
  arXiv  Detail & Related papers  (2025-07-25T18:23:18Z)
• $\texttt{SPECS}$: Faster Test-Time Scaling through Speculative Drafts [55.231201692232894]
  $textttSPECS$ is a latency-aware test-time scaling method inspired by speculative decoding.<n>Our results show that $textttSPECS$matches or surpasses beam search accuracy while reducing latency by up to $sim$19.1%.
  arXiv  Detail & Related papers  (2025-06-15T05:50:05Z)
• SageAttention: Accurate 8-Bit Attention for Plug-and-play Inference Acceleration [22.551095978580147]
  We propose SageAttention, a highly efficient and accurate quantization method for attention.<n>Our approach incurs almost no end-to-end metrics loss across diverse models.
  arXiv  Detail & Related papers  (2024-10-03T10:25:23Z)
• MixLinear: Extreme Low Resource Multivariate Time Series Forecasting with 0.1K Parameters [6.733646592789575]
  Long-term Time Series Forecasting (LTSF) involves predicting long-term values by analyzing a large amount of historical time-series data to identify patterns and trends. Transformer-based models offer high forecasting accuracy, but they are often too compute-intensive to be deployed on devices with hardware constraints. We propose MixLinear, an ultra-lightweight time series forecasting model specifically designed for resource-constrained devices.
  arXiv  Detail & Related papers  (2024-10-02T23:04:57Z)
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers [58.5711048151424]
  We introduce SPARSEK Attention, a novel sparse attention mechanism designed to overcome computational and memory obstacles. Our approach integrates a scoring network and a differentiable top-k mask operator, SPARSEK, to select a constant number of KV pairs for each query. Experimental results reveal that SPARSEK Attention outperforms previous sparse attention methods.
  arXiv  Detail & Related papers  (2024-06-24T15:55:59Z)
• Gated Linear Attention Transformers with Hardware-Efficient Training [60.670102007737476]
  This work describes a hardware-efficient algorithm for linear attention that trades off memory movement against parallelizability. We then generalize this algorithm to a more expressive variant of linear attention with data-dependent gates. When used as a replacement for the standard attention layer in Transformers, the resulting gated linear attention Transformer is found to perform competitively.
  arXiv  Detail & Related papers  (2023-12-11T18:51:59Z)
• Does Long-Term Series Forecasting Need Complex Attention and Extra Long Inputs? [21.15722677855935]
  Transformer-based models have achieved impressive performance on various time series tasks. Long-Term Series Forecasting (LTSF) tasks have also received extensive attention in recent years. Due to the inherent computational complexity and long sequences demanding of Transformer-based methods, its application on LTSF tasks still has two major issues.
  arXiv  Detail & Related papers  (2023-06-08T08:37:49Z)
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness [80.3586155104237]
  FlashAttention is an IO-aware exact attention algorithm for Transformers. It reduces the number of memory reads/writes between GPU high bandwidth memory (HBM) and GPU on-chip. FlashAttention and block-sparse FlashAttention enable longer context in Transformers.
  arXiv  Detail & Related papers  (2022-05-27T17:53:09Z)
• Triformer: Triangular, Variable-Specific Attentions for Long Sequence Multivariate Time Series Forecasting--Full Version [50.43914511877446]
  We propose a triangular, variable-specific attention to ensure high efficiency and accuracy. We show that Triformer outperforms state-of-the-art methods w.r.t. both accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-04-28T20:41:49Z)
• Taking ROCKET on an Efficiency Mission: Multivariate Time Series Classification with LightWaveS [3.5786621294068373]
  We present LightWaveS, a framework for accurate multivariate time series classification. It employs just 2.5% of the ROCKET features, while achieving accuracy comparable to recent deep learning models. We show that we achieve speedup ranging from 9x to 65x compared to ROCKET during inference on an edge device.
  arXiv  Detail & Related papers  (2022-04-04T10:52:20Z)
• Revisiting Multi-Scale Feature Fusion for Semantic Segmentation [90.32746095413447]
  In this paper, we demonstrate that neither high internal resolution nor atrous convolutions are necessary for accurate semantic segmentation. We develop a simplified segmentation model, named ESeg, which has neither high internal resolution nor expensive atrous convolutions. Our simple method can achieve better accuracy with faster speed than prior art across multiple datasets.
  arXiv  Detail & Related papers  (2022-03-23T19:14:11Z)

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.