The self-attention mechanism is the core engine of the Transformer architecture, responsible for its remarkable ability to model long-range dependencies in text, audio, and images. However, this power comes with a severe mathematical penalty: its computational and memory complexity scales quadratically ($O(N^2)$) with the input sequence length $N$.
To understand why, consider how standard self-attention works. Every token in a sequence generates a Query vector, a Key vector, and a Value vector. To compute the attention weights, every single Query must undergo a dot-product operation with every single Key. For a sequence of 1,000 tokens, this requires 1,000,000 pairwise comparisons. If the sequence expands to 100,000 tokens—the length of a short novel or a complex codebase—the system must compute and store 10,000,000,000 interactions.
As highlighted by Wang et al. in their survey, Beyond the Limits: A Survey of Techniques to Extend the Context Length in Large Language Models, this quadratic wall severely constrains Transformers across diverse domains. It restricts long-document classification (Khandve et al.), limits real-time 3D facial animation from audio streams (Fan et al.), makes tabular in-context learning slow as the number of examples grows (Küken), and prevents standard models from scaling to millions of data points in single-cell genomics (Fan et al.).
To bypass this bottleneck, researchers have developed a spectrum of techniques designed to break the quadratic wall. These approaches can be grouped into three primary strategies: sparsifying the attention matrix, compressing the token sequence, and replacing global attention with linear recurrent state updates.
Sparsifying the Attention Landscape
The most direct way to avoid computing an $N \times N$ matrix is to simply leave most of its entries blank. In many applications, a token does not need to attend to every other token in the entire document; it primarily relies on local context or specific target terms.
Local and Query-Directed Windows
One intuitive approach is to restrict each token's view to a small, localized window. Hofstätter et al. utilize this in Local Self-Attention over Long Text for Efficient Document Retrieval, demonstrating that local windows allow models to ingest thousands of tokens without experiencing a computational blowup.
In information retrieval, this can be taken a step further by aligning the attention pattern with the task's underlying logic. For instance, Jiang et al. introduce the Long Document Ranking with Query-Directed Sparse Transformer, which enforces sparsity by only allowing document tokens to attend to text within the proximity of query terms. This reduces the number of calculated dot products from $N^2$ to a fraction proportional to the query's footprint.
Global-Local Hybrids
Completely isolating tokens into local windows prevents the model from sharing information across long distances. To fix this, Ainslie et al. propose Extended Transformer Construction in ETC: Encoding Long and Structured Data in Transformers. They introduce a small set of "global tokens" that can attend to all tokens, while the standard tokens remain restricted to local attention. The global tokens act as a high-speed communication bus, routing information across distant parts of the sequence in linear time.
Standard Attention (Quadratic):
Token 1 <---> Token 2 <---> Token 3 <---> Token 4 (All-to-All)
Global-Local Attention (Linear):
Token 1 <---> [ Global Token ] <---> Token 4
| ^ |
v v v
Local Window Local Window Local Window
The Hardware Realities of Sparsity
While sparse attention patterns are mathematically elegant, they often suffer from a frustrating paradox: they can run slower than dense attention on modern hardware. Graphics Processing Units (GPUs) are optimized for massive, contiguous matrix multiplications. Irregular, sparse memory accesses break this efficiency.
To bridge this gap, Pagliardini introduces Fast Attention Over Long Sequences With Dynamic Sparse Flash Attention. By co-designing the sparse attention pattern to fit the block-based memory layout of GPU hardware (building on the principles of FlashAttention), this approach achieves genuine wall-clock speedups over dense attention, proving that algorithmic sparsity must respect hardware architecture to be viable.
Token Reduction and Context Compression
Because the cost of attention scales with the square of the sequence length, reducing the number of tokens $N$ before they enter the attention layers yields a disproportionate dividend. If you can compress or prune the sequence length by half, you reduce the attention workload by 75%.
Dynamic Token Dropping
Not all words or tokens contribute equally to the meaning of a text. In TR-BERT: Dynamic Token Reduction for Accelerating BERT Inference, Ye et al. demonstrate that a model can dynamically "drop" unimportant tokens as they pass upward through successive layers. A token that is deemed irrelevant for the final prediction is pruned early, shrinking the sequence length for the remaining, deeper layers of the network. Similarly, Liu et al. show in Only 5% Attention Is All You Need: Efficient Long-range Document-level Neural Machine Translation that document-level translation models can maintain high quality while computing attention over a tiny fraction of highly informative tokens.
Hourglass Architectures and Context Autoencoders
Instead of discarding tokens entirely, information can be condensed into a more compact representation. Zhai et al. implement this via an "hourglass" architecture in Fast-StrucTexT: An Efficient Hourglass Transformer with Modality-guided Dynamic Token Merge for Document Understanding. The model uses cross-modal cues to merge redundant tokens in the middle layers where attention is heaviest, and then expands them back to the original resolution for final processing.
Taking this concept to its logical conclusion, Ge et al. develop the In-context Autoencoder for Context Compression in a Large Language Model. This system acts as a neural zip-file, compressing thousands of words of document context into a handful of dense "memory slots." The large language model then attends only to these condensed slots, bypassing the need to compute attention across the original, sprawling text.
Recurrence and Linear State-Space Models
The most radical solution to the quadratic bottleneck is to abandon global self-attention entirely in favor of mechanisms that scale linearly ($O(N)$) with sequence length.
Segment-Level Recurrence
Traditional Recurrent Neural Networks (RNNs) process text token-by-token, maintaining a fixed-size hidden state that summarizes everything seen so far. This keeps computational costs constant per token, but RNNs historically struggled with long-range memory compared to Transformers.
To combine the best of both worlds, Bulatov et al. introduce the Recurrent Memory Transformer in Beyond Attention: Breaking the Limits of Transformer Context Length with Recurrent Memory. Instead of performing attention across an entire multi-million token document at once, RMT breaks the input into smaller segments. It processes each segment with standard, highly expressive self-attention, but passes a small set of dedicated "memory tokens" from one segment to the next, achieving linear scaling across massive context windows.
[ Segment 1 + Memory ] ---> Local Attention ---> Updated Memory
|
v
[ Segment 2 + Memory ] ---> Local Attention ---> Updated Memory
Hybrid State-Space Models
Modern State-Space Models (SSMs), such as Mamba, offer a mathematically rigorous alternative to attention, updating a continuous hidden state via linear state equations. However, pure SSMs sometimes lack the sharp, precise recall capabilities of attention layers.
To strike an optimal balance, Lenz et al. present Jamba: Hybrid Transformer-Mamba Language Models. Jamba interleaves standard Transformer attention layers with Mamba SSM layers. By doing so, it retains the high-quality reasoning and retrieval capabilities of attention while drastically reducing the size of the Key-Value (KV) cache.
Complementing this direction, Liu et al. frame these recurrent state updates through the lens of optimization theory in Longhorn: State Space Models are Amortized Online Learners. They show that the hidden state updates in SSMs can be viewed as an online regression problem, providing a principled explanation for why these linear-time models can successfully extrapolate to contexts many times longer than those seen during training.
Low-Level Numerical Acceleration
Even when maintaining dense or semi-sparse attention patterns, the quadratic bottleneck can be mitigated by optimizing how numbers are represented and manipulated at the hardware level.
Because attention matrices often contain low-precision or redundant information, quantization strategies can compress the numerical precision of the calculations. Zhu demonstrates this low-level optimization in SageAttention2++: A More Efficient Implementation of SageAttention2. By carefully managing FP8-to-FP16 hardware instructions and narrowing quantization ranges to prevent numerical overflow, this implementation accelerates the underlying matrix math by up to 3.9x over standard FlashAttention. This demonstrates that even within the constraints of quadratic scaling, hardware-aware numerical engineering can significantly push back the practical boundaries of the quadratic wall.