Scaling Attention to Very Long Sequences in Linear Time with Wavelet-Enhanced Random Spectral Attention ( WERSA )
Vincenzo Dentamaro · 2025
Read Scaling Attention to Very Long Sequences in Linear Time with Wavelet-Enhanced Random Spectral Attention ( WERSA ) by Vincenzo Dentamaro (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08637.txt.
Introduction
Vincenzo Dentamaro introduces WERSA, an attention method that reads very long sequences in linear time in a 2025 paper. Standard attention grows quadratically, choking on long inputs. WERSA blends random spectral features with multi-scale wavelets and learned weights to focus on informative scales without the quadratic cost.
Across vision, language, and reasoning benchmarks it topped rival methods in accuracy. On a text sorting task it beat plain attention while cutting training time by four fifths and compute by nearly three quarters. On extremely long sequences where quadratic methods ran out of memory, it stayed fastest among working rivals and most accurate. The design targets low-resource hardware.
Catalog record
| CREATOR | Vincenzo Dentamaro |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08637
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scaling Attention to Very Long Sequences in Linear Time with Wavelet-Enhanced Random Spectral Attention ( WERSA ) Vincenzo Dentamaro Abstract Transformer models are computationally costly on long sequences since regular attention has quadratic O ( n 2 ) O(n^{2}) time complexity. We introduce Wavelet-Enhanced Random Spectral Attention ( WERSA ), a novel mechanism of linear O ( n ) 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 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 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. 1 Introduction Transformer models ( Vaswani et al. 2017 ) have drastically changed machine learning field by providing better performance in a huge variety of applications, ranging from natural language processing ( Devlin et al. 2019 ; Brown et al. 2020 ) to computer vision ( Dosovitskiy et al. 2020 ; Liu et al. 2021 ) and multimodal learning ( Radford et al. 2021 ; Alayrac et al. 2022 ) . Underlying such success is the mechanism of attention, which allows long-range dependencies to be captured efficiently by calculating interactions between each pair of tokens in a sequence. The vanilla mechanism of self-attention, however, calculates a quadratically increasing computational cost in terms of sequence length, thereby limiting transformer applications in very long sequence environments. This computational burden has spurred a lot of work in designing effective attention mechanisms that capture the expressiveness of regular attention with much fewer computational resources. Recent techniques include sparse attention patterns ( Beltagy et al. 2020 ; Zaheer et al. 2020 ) , low-rank approximations ( Wang et al. 2020 ; Choromanski et al. 2020 ) , and kernel-based methods ( Katharopoulos et al. 2020 ; Peng et al. 2021 ) ( Lee-Thorp et al. 2021 ; Gu et al. 2022 ) . Transformers have also been constructed with Fast Fourier Transform (FFT) to calculate attention in the frequency domain to minimize computational complexity from \mathcal{O}(n^{2}) to \mathcal{O}(n\log n) . Such techniques do, however, rely on global sinusoidal bases, which do not capture the interaction between local and global patterns ( Lee-Thorp et al. 2021 ) . This work presents Wavelet-Enhanced Random Spectral Attention ( WERSA ), a novel attention mechanism incorporating wavelet transforms with random feature mappings to achieve a linear computational complexity of \mathcal{O}(n) without compromising representational power. Unlike FFT-based methods using static sinusoidal bases, WERSA uses the Haar wavelet transform to provide multi-resolution capabilities, thus supporting adaptive learning of both local and global interactions. Additionally, it uses content-adaptive filtering, where input-dependent coefficients control wavelet scales through learnable parameters, enabling the model to focus on relevant frequency components. WERSA ’s theoretical foundations include multi-resolution analysis allowing fine-grained attentional processing across scales, with proven exponentially decreasing approximation error as wavelet levels increase. The random feature approximation ensures \mathcal{O}(n) complexity with theoretical guarantees, while trainable bandwidth parameters optimize kernel approximation. The scale-specific processing is particularly useful for applications where signals contain important information at different frequencies, thus improving the model’s ability to capture detailed nuances and overall trends simultaneously. The major contributions are: 1. WERSA : A novel \mathcal{O}(n) attention mechanism maintaining performance comparable to standard quadratic attention 2. The application of multi-scale wavelet processing successfully captures both local and global dependencies. 3. Context-adaptive filtering reduces noise by applying input-dependent gating functions. 4. Empirical validation showing 73% FLOPS reduction and 81% faster computation while maintaining accuracy 5. Enabling the theoretical processing of very long sequences which are impractical with traditional attention mechanisms WERSA reduces the computational cost that comes with long sequence inputs, thus reducing energy consumption and promoting the next generation AI sustainable models. The paper is thought to be self-contained, i.e. all information required to understand the logic of WERSA are described here. Thus this work is organized as follows: a state-of-the-art review on efficient attention mechanisms for transformers is provided in Section 2. The WERSA method and the WERSA approximation theorem are presented in Section 3. The theorem proves asymptotic convergence to standard multi-headed attention but tackling very long sequences (millions of tokens of context) in linear time. Datasets used and experimental setups are shown in Section 4. Results and their discussion are provided in Section 5, while conclusions are provided in Section 6. Additionally, background information of attention mechanisms and Wavelet Transform are provided in Appendix A . Appendix B contains the proof of WERSA approximation theorem. Appendix C shows Haar Wavelet transform for generalized levels. The WERSA pseudo-algorithm is sketched in Appendix D while ablation studies are shown in Appendix E . 2 Literature Review The quadratic complexity of standard multi-headed attention (MHA) of the base transformer model has opened various ways to enhance it. Tay et al. 2022 provide a comprehensive overview of efficient transformer models and classify them into various different strategies. Sparse Attention techniques minimize computational overhead by constraining attention mechanisms to a specific subset of positions. Some notable examples include Sparse Transformer ( Child et al. 2019 ) , Longformer ( Beltagy et al. 2020 ) , and BigBird ( Zaheer et al. 2020 ) . These approaches typically achieve \mathcal{O}(n\sqrt{n}) or \mathcal{O}(n\log n) complexity. Low-Rank Approximations utilize low-rank factorizations to approximate the attention matrix. The Linformer ( Wang et al. 2020 ) truncates the length dimension to a fixed size, which results in \mathcal{O}(n) complexity. Performer ( Choromanski et al. 2020 ) and Linear Transformer ( Katharopoulos et al. 2020 ) utilize kernel approximations to approximate softmax attention and achieve linear complexity by avoiding the explicit computation of the quadratic-sized attention matrix. Recurrence-based Methods utilize recurrent models to efficiently capture long-term dependencies. Segment recurrence has been utilized by Transformer-XL ( Dai et al. 2019 ) and Compressive Transformer ( Rae et al. 2019 ) , while Linear Recurrent Units ( Orvieto et al. 2023 ) and RWKV ( Peng et al. 2023 ) use a combination of recurrent processing and parallel computation for efficient inference. Dao et al. 2022 presented FlashAttention, a method to reduce memory access patterns to enable exact attention with lower memory bandwidth overhead. FlashAttention-2 ( Dao 2023 ) , a variant, supported successful training and inference with long-length inputs. These methods, with asymptotic complexity being \mathcal{O}(n^{2}) , have a much lowered real-world computational cost. Xiong et al. 2021 introduced Nyström attention with computational complexity of \mathcal{O}(n\sqrt{n}) .