Spatio-Spectral Sequence Processing

Long-sequence data have become ubiquitous in the last decade. Transformers, being the de facto standard for processing sequences, suffer from quadratic complexity in both memory and running time, which makes them prohibitively expensive for long sequences. To augment recurrent models with efficient global information exchange, we follow the recent developments in usage of spectral information for graph neural networks (GNNs). This paper introduces Spatio-Spectral Sequence (S2Seq) models, which augment arbitrary sequence architectures with a learnable spectral branch to capture global geometric structure. Using Long-Range Arena classification benchmark, we demonstrate that our approach can yield meaningful improvements, sometimes bridging the gap to the state-of-the-art performance. We also show that truncated and even approximated spectra can provide enough information to match the performance of a full FFT calculation. Furthermore, we propose a proof-of-concept extension of S2Seq for autoregressive prediction using recurrent window updates in subquadratic time.