The standard self-attention mechanism fundamentally relies on global pairwise comparisons. For an input sequence of length $L$, every single token must compute an attention score with every other token. This operation yields an $L \times L$ matrix, resulting in a computational and memory complexity that scales quadratically ($O(L^2)$).
While highly effective for short contexts, this quadratic scaling creates a severe "memory wall" when dealing with long sequences, such as high-frequency sensor streams, multi-year patient medical records, or extended user interaction histories. To process these long horizons without exhausting hardware resources, researchers have developed several distinct architectural paradigms that bypass or restructure the dense $O(L^2)$ matrix.
Sparsity and Quantization: Selecting Vital Signals
The first core insight in mitigating quadratic complexity is that dense, all-to-all communication is often redundant. In many long-sequence tasks, a token's true dependencies are concentrated on a small subset of the context rather than distributed evenly across the entire history.
In Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting, Zhou et al. demonstrate that the self-attention matrix typically exhibits a long-tail distribution, where only a few "active" queries drive the majority of the attention weights. By introducing a "ProbSparse" attention mechanism, the authors use a Kullback-Leibler divergence measurement to identify and select these dominant queries. Instead of computing the full matrix, the model only calculates attention for the top-performing queries, effectively dropping the computational complexity to $O(L \log L)$.
Another way to exploit this redundancy is through discrete latent spaces. In VQ-TR: Vector Quantized Attention for Time Series Forecasting, Rasul leverages vector quantization to map long historical sequences into a compact, discrete set of latent representations. By attending to these quantized prototypes rather than individual raw tokens, the model compresses the context window and achieves linear complexity relative to the historical input length.
Patching and Segmentation: Shifting from Points to Shapes
Standard Transformers treat every individual timestamp or data point as an independent token. However, in continuous domains like time-series or trajectory modeling, isolated points carry very little semantic meaning; information is instead encoded in localized shapes, trends, and variations. Grouping adjacent points into "patches" or "segments" fundamentally alters the scaling math.
If a sequence of length $L$ is divided into non-overlapping patches of size $P$, the effective sequence length drops from $L$ to $L/P$. Consequently, computing attention across these patches reduces the matrix size from $L^2$ to $(L/P)^2$, yielding a massive reduction in computational overhead.
In SVP-T: A Shape-Level Variable-Position Transformer for Multivariate Time Series Classification, Zuo et al. implement this shift by replacing timestamp-level inputs with shape-level subsequences, allowing the model to scale efficiently to high-frequency data. Similarly, Du et al. introduce the Preformer: Predictive Transformer with Multi-Scale Segment-wise Correlations for Long-Term Time Series Forecasting architecture, which swaps out point-wise attention for multi-scale segment-wise correlations.
By stacking these observations at multiple granularities, as seen in the multi-scale slicing framework proposed by HE et al. in Long sequence time-series forecasting method based on multi-scale segmentation, models can capture both fine-grained local fluctuations and long-term seasonal trends without ever instantiating a massive point-to-point attention matrix.
Linear Recurrence and State Space Models: Constant-Memory History
A more radical departure from the Transformer paradigm involves replacing the global attention matrix entirely with a rolling hidden state. Traditional Recurrent Neural Networks (RNNs) maintained a constant-sized memory, scaling linearly ($O(L)$) with sequence length. However, they fell out of favor because their sequential step-by-step execution prevented parallelization during training.
Modern linear recurrent architectures and State Space Models (SSMs) solve this dilemma. By removing non-linearities from the hidden-to-hidden transitions, these models can be formulated as a parallel scan during training (allowing fast GPU acceleration) while retaining the $O(1)$ incremental inference and $O(L)$ memory scaling of traditional recurrences.
For production real-time environments like recommendation engines, Yue introduces Linear Recurrent Units for Sequential Recommendation, replacing self-attention with parallel linear recurrences to eliminate the need to re-compute a user's entire interaction history for each new action.
In healthcare and longitudinal modeling, where sequences are exceptionally long, Song et al. combine linear attention variants with convolutional modules in Timelygpt: extrapolatable transformer pre-training for long-term time-series forecasting in healthcare to process continuous physiological biosignals efficiently. Furthermore, Wang et al. demonstrate in Effective and Efficient Time-Varying Counterfactual Prediction with State-Space Models that leveraging selective state-space models (such as Mamba) allows networks to maintain a coherent long-term memory of history without encountering the quadratic computational barriers that limit standard attention-based decoders.
Frequency-Domain Filtering: Bypassing Attention Entirely
The final paradigm shifts the problem from the time domain to the frequency domain. Instead of calculating how every token relates to every other token chronologically, the sequence is mapped into its constituent frequencies using the Fast Fourier Transform (FFT). Because the FFT operates in $O(L \log L)$ time, applying learnable filters in the frequency domain bypasses the need for pairwise token comparisons entirely.
In TSLANet: Rethinking Transformers for Time Series Representation Learning, Eldele et al. introduce a lightweight architecture that replaces heavy attention layers with adaptive frequency-domain filtering. This approach inherently captures global periodicities and seasonal patterns—which are often smeared or obscured in point-wise time-domain attention—while remaining highly compute-efficient.
To maximize both local and global modeling capabilities, Wu et al. combine this concept with linear-time state-space models in Affirm: Interactive Mamba with Adaptive Fourier Filters for Long-term Time Series Forecasting. By utilizing learnable Fourier filters alongside linear scans, these architectures achieve robust, noise-resistant long-horizon modeling at a fraction of the computational footprint of standard Transformers.
Key Foundational Work
Scene Memory Transformer for Embodied Agents in Long-Horizon Tasks. (2019) — contributed 1 concept elements to this direction.