Overcoming the Quadratic Scaling Bottleneck of Self Attention

45 concepts45 papers1 proposal

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quadratic_attention_complexity_sequence__08f0cce9,
  title = {quadratic attention complexity (sequence length scaling bottleneck)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-attention-complexity-sequence-length-scaling-bottleneck/rdr_08f0cce9b24043eeb506c418f32e81f9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_quadratic_attention_complexity_sequence__08f0cce9_v1,
  title = {quadratic attention complexity (sequence length scaling bottleneck)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quadratic-attention-complexity-sequence-length-scaling-bottleneck/rdr_08f0cce9b24043eeb506c418f32e81f9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake