The standard Transformer architecture owes its remarkable expressivity to the softmax self-attention mechanism. By allowing every token in a sequence to look at every other token, the model builds a comprehensive, non-local representation of context. However, this global view comes at a steep price: computational and memory requirements scale quadratically ($O(N^2)$) with the input sequence length $N$.
As models are deployed on increasingly long contexts—such as entire books, long video streams, or full-length biological sequences—this quadratic scaling becomes a hard hardware barrier. To bypass this bottleneck, researchers are redesigning the core mechanics of attention.
The Root of the Problem: The Softmax Coupling
To understand why standard attention scales quadratically, we look at its fundamental equation:
$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d}}\right)V$$
Here, $Q$ (Queries) and $K$ (Keys) are matrices of shape $(N \times d)$, where $d$ is the hidden dimension. Multiplying $Q$ by $K^T$ produces an intermediate matrix of shape $(N \times N)$. This matrix represents the pairwise attention scores between every single token combination.
Standard Attention:
[Q: N x d] x [K^T: d x N] ---> [Attention Matrix: N x N] (Quadratic Bottleneck!)
[Attention Matrix: N x N] x [V: N x d] ---> [Output: N x d]
Because the nonlinear $\text{softmax}$ function is applied row-wise across this $N \times N$ matrix, the Queries and Keys are inextricably coupled before they interact with the Values ($V$). We are forced to materialize this massive $N \times N$ matrix in memory. During inference, this manifests as an ever-expanding Key-Value (KV) cache that quickly exhausts GPU memory.
Linearization: Changing the Order of Operations
The most direct way to eliminate the $N \times N$ matrix is to decouple the Queries and Keys so that we can exploit the associative property of matrix multiplication. If we can replace the softmax operation with a localized feature map $\phi(\cdot)$, the attention equation transforms:
$$\text{LinearAttention}(Q, K, V) = \left(\phi(Q)\phi(K)^T\right)V = \phi(Q)\left(\phi(K)^TV\right)$$
By computing $\phi(K)^TV$ first, we multiply a $(d \times N)$ matrix by an $(N \times d)$ matrix. This yields a tiny $(d \times d)$ matrix that captures the global context of the sequence. We then multiply $\phi(Q)$ by this $(d \times d)$ matrix. The computational complexity drops from $O(N^2)$ to $O(Nd)$, which scales linearly with sequence length.
Linear Attention:
[\phi(K)^T: d x N] x [V: N x d] ---> [Global Context: d x d] (Constant size!)
[\phi(Q): N x d] x [Global Context: d x d] ---> [Output: N x d]
Valerii Likhosherstov et al. advanced this approach in Chefs’ Random Tables: Non-Trigonometric Random Features by introducing unbiased, bounded kernel estimators that approximate the softmax function without materializing the full matrix, stabilizing the training of linearized models. To avoid training these models from scratch, researchers have designed post-training conversion methods. For instance, Michael Zhang developed LoLCATs: On Low-Rank Linearizing of Large Language Models, which projects pretrained quadratic attention layers into low-rank linear approximations. Similarly, Ning Wang et al. proposed MVA: Linear Attention with High-order Query-Keys Integration and Multi-level Vocabulary Decomposition to recover original model performance through recursive error compression, while Yeonju Ro et al. introduced On-the-Fly Adaptive Distillation of Transformer to Dual-State Linear Attention for Long-Context LLM Serving to dynamically linearize layers during inference to mitigate KV cache expansion.
To prevent the gradient vanishing issues common in recurrent formulations of linear attention, Peng Lu introduced ReGLA: Refining Gated Linear Attention, which incorporates a stable exponential feature map and a refining gate to preserve long-range dependencies.
Sparsification and Token Eviction: Pruning the Context
An alternative perspective argues that full global attention is mathematically redundant. Not every token needs to attend to every other token; instead, a model can maintain high performance by focusing only on a sparse subset of critical interactions.
In SparseBERT: Rethinking the Importance Analysis in Self-attention, Han Shi et al. demonstrated that even the diagonal elements of an attention matrix—where tokens attend to themselves—can be safely removed using a differentiable mask without degrading accuracy. Rather than relying on static sparse patterns, modern architectures dynamically prune irrelevant history. Yaniv Leviathan et al. proposed Selective Attention Improves Transformer, a parameter-free modification that allows tokens to actively mask out past entries they deem irrelevant, drastically reducing the inference memory footprint.
This concept extends naturally to KV cache management through intelligent token eviction. Instead of storing every historical token, models can compress or drop redundant information:
- Core Token Compression: Yaofo Chen et al. developed Core Context Aware Transformers for Long Context Language Modeling, which dynamically compresses global context into a compact set of "core tokens" while maintaining local precision.
- Informative Selection: Xinting Huang et al. introduced the Long-Range Language Modeling with Selective Cache, which scores and preserves only the most informative key-value pairs rather than relying on a naive recency bias.
- Learnable Eviction: To counteract the inherent "forgetfulness" of pure linear attention, Mutian He et al. proposed Alleviating Forgetfulness of Linear Attention by Hybrid Sparse Attention and Contextualized Learnable Token Eviction, utilizing a lightweight convolutional network to decide which tokens deserve a spot in a small, high-fidelity cache.
This spatial routing is also highly effective in multi-dimensional domains. For instance, in Mixture of Contexts for Long Video Generation, Shengqu Cai et al. framed long-context video synthesis as an internal information retrieval problem, routing queries exclusively to relevant historical video chunks to sidestep dense $O(N^2)$ frame-to-frame computations.
Hybrid Architectures: Balancing Efficiency and Expressivity
While pure linear attention and state-space models (SSMs) achieve $O(N)$ scaling, they compress an infinite history into a fixed-size hidden state. This compression creates a fundamental retrieval bottleneck, making it difficult for the model to recall exact, fine-grained details from the distant past (the "needle in a haystack" problem).
Hybrid architectures solve this by interleaving linear-scaling recurrent or SSM layers with localized or sliding-window softmax attention layers. The linear layers compress broad, global context over hundreds of thousands of tokens, while the local attention layers maintain sharp, high-resolution focus on immediate neighbors.
Hybrid Layer Stacking:
Layer 3: [ Sliding Window Softmax Attention ] --> High-resolution local recall
Layer 2: [ Linear Attention / SSM Layer ] --> Compresses infinite global history
Layer 1: [ Sliding Window Softmax Attention ] --> High-resolution local recall
In Samba: Simple Hybrid State Space Models for Efficient Unlimited Context Language Modeling, Liliang Ren et al. combined the selective state-space mechanics of Mamba with Sliding Window Attention (SWA), achieving perfect memory recall up to 256K tokens. Similarly, Bowen Yang et al. explored positional dynamics in Rope to Nope and Back Again: A New Hybrid Attention Strategy, discovering that interleaving global layers without positional embeddings (NoPE) with local, sliding-window RoPE layers optimizes long-range retrieval speed and accuracy.
Other hybrid paradigms treat memory as an active, test-time optimization process. Ali Behrouz et al. introduced Titans: Learning to Memorize at Test Time, which pairs short-term attention with a dynamic neural network acting as long-term memory, updating its internal weights via gradient descent at test time based on a "surprise" metric.
These subquadratic hybrid designs have expanded beyond text into biological sequence modeling, where whole genomes or full-length transcripts span thousands of elements. Philipp Seidl developed Bio-xLSTM: Generative modeling, representation and in-context learning of biological and chemical sequences to scale chemical and genomic modeling using matrix-memory recurrent blocks. For transcriptomics, Guipeng Li et al. designed HydraRNA: a hybrid architecture based full-length RNA language model, blending bidirectional SSMs with multi-head attention to process full-length mRNA sequences that are computationally intractable under standard Transformer constraints.
Alternative Structural Formulations
Beyond kernelization and sparsification, some approaches bypass the quadratic bottleneck by restructuring the geometry of the sequence itself or treating the layers as continuous physical evolutions.
Attention Tensorization
Instead of treating an input as a flat 1D sequence of length $N$, Aosong Feng et al. proposed Long Sequence Modeling with Attention Tensorization: From Sequence to Tensor Learning. By reshaping the 1D sequence into a multi-dimensional tensor, the model replaces a single $O(N^2)$ attention operation with a series of smaller, hierarchical, dimension-wise attention steps, reducing the computational footprint.
Dynamical Systems and Continuous Evolution
Rather than recomputing attention patterns from scratch at every single layer, Subhabrata Dutta et al. introduced Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems. Their framework, TransEvolve, views neural network layers as time-steps in a physical system of interacting particles. It uses Ordinary Differential Equations (ODEs) to mathematically "evolve" attention patterns from the previous layer, cutting parameter costs and training time.
By replacing dense, global softmax coupling with linear kernels, dynamic token eviction, and hybrid recurrent structures, these diverse methodologies collectively transform the Transformer from a model bounded by sequence length into an architecture capable of processing virtually unlimited context.
Key Foundational Work
Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems (2021) — contributed 1 concept elements to this direction.
SparseBERT: Rethinking the Importance Analysis in Self-attention (2021) — contributed 1 concept elements to this direction.
Pay attention and you won't lose it: a deep learning approach to sequence imputation (2019) — contributed 1 concept elements to this direction.