Linear Complexity Attention for Sequence Modeling

1,690 concepts941 papers14 proposals

Standard Transformer architectures rely on softmax self-attention to capture dependencies across sequences. While highly expressive, this mechanism suffers from a fundamental computational bottleneck: it scales quadratically with the sequence length. As context windows expand to tens of thousands of tokens, the computational and memory costs become prohibitive.

To overcome this limitation, a prominent research direction focuses on Linear Complexity Attention. By mathematically restructuring how queries, keys, and values interact, these methods reduce the time and memory complexity from quadratic ($O(N^2)$) to linear ($O(N)$), enabling Transformers to scale efficiently to exceptionally long sequences.

The Softmax Bottleneck

To understand why linear attention works, we must first look at why standard attention fails to scale. Standard dot-product attention is computed as:

$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{QK^T}{\sqrt{d}}\right)V$$

where $Q$ (Queries), $K$ (Keys), and $V$ (Values) are matrices of size $N \times d$, with $N$ representing the sequence length and $d$ the feature dimension.

The core issue is the term $QK^T$. Multiplying an $N \times d$ matrix by a $d \times N$ matrix results in an $N \times N$ attention matrix that maps the pairwise relationship between every single token in the sequence. Because the non-linear $\text{softmax}$ function is applied directly to this intermediate $N \times N$ matrix, we are forced to materialize it completely. When $N$ grows from 1,000 to 100,000 tokens, the size of this matrix increases by a factor of 10,000.

Unlocking Associativity via Kernelization

The fundamental insight behind linear attention is that if we can eliminate or approximate the $\text{softmax}$ operation, we can exploit the associative property of matrix multiplication to change the order of operations.

Imagine replacing the $\text{softmax}$ function with a feature map $\phi(\cdot)$ applied row-wise to $Q$ and $K$. The attention equation can then be rewritten as:

$$\text{Attention}(Q, K, V) = \left(\phi(Q)\phi(K)^T\right)V$$

Because matrix multiplication is associative, we can choose which multiplication to perform first. Instead of grouping the operations as $(\phi(Q)\phi(K)^T)V$, we can group them as:

$$\text{Attention}(Q, K, V) = \phi(Q)\left(\phi(K)^TV\right)$$

Let's look at the matrix dimensions to see why this changes everything:

  1. $\phi(K)^T$ is a $d \times N$ matrix, and $V$ is an $N \times d$ matrix.
  2. Multiplying them first yields an intermediate matrix $\phi(K)^TV$ of size $d \times d$.
  3. Finally, we multiply $\phi(Q)$ ($N \times d$) by this $d \times d$ intermediate matrix, resulting in the final $N \times d$ output.

By changing the order of multiplication, the sequence length $N$ is no longer multiplied by itself. The computational complexity drops from $O(N^2d)$ to $O(Nd^2)$. Because the feature dimension $d$ is a small constant (typically fixed between 64 and 128 per head), the scaling becomes strictly linear with respect to sequence length.

Approximating Softmax

Simply dropping the softmax function degrades a model's capacity to focus sharply on specific tokens. To preserve performance, researchers use mathematical approximations that retain the linear-scaling property while mimicking softmax behavior.

One prominent approach is to use polynomial expansions. Simran Arora et al. utilize a second-order Taylor expansion to approximate the exponential function inherent in softmax. This allows the model to maintain a constant-sized recurrent state during generation while preserving the high-recall capabilities required for complex language tasks.

Alternatively, kernel functions can substitute for softmax entirely. Jiachen Lu et al. developed a softmax-free architecture (SOFT) that replaces traditional self-attention with a Gaussian kernel and a low-rank matrix approximation, proving that removing the softmax bottleneck does not inherently compromise accuracy on vision or language benchmarks.

The Dual View: Recurrence and Fast Weights

Linearizing attention reveals a deep conceptual bridge between Transformers and Recurrent Neural Networks (RNNs). When processing a sequence causally (where a token can only attend to past tokens), the intermediate matrix $\phi(K)^TV$ can be viewed as an accumulating memory state.

Instead of computing the entire sequence at once, the model can update this state step-by-step:

$$S_t = S_{t-1} + \phi(k_t)v_t^T$$

$$y_t = \phi(q_t)S_t$$

As explored by Kazuki Irie in Practical Computational Power of Linear Transformers, this formulation allows linear attention to act as a fast weight programmer. A "slow" network processes incoming tokens to generate context-dependent weight updates for a "fast" network storage matrix ($S_t$). This allows the model to maintain a fixed-size memory footprint during inference, bypassing the need for an ever-growing Key-Value (KV) cache. To further enhance this capability, Kazuki Irie et al. introduced explicit recurrence into these fast-weight systems, allowing the model to dynamically reprogram its own weights to track complex algorithmic states.

Overcoming Hardware Bottlenecks

While mathematically elegant, early linear attention models suffered from a practical flaw: the sequential nature of the cumulative state update ($S_t$) introduced a hardware bottleneck during parallel training on modern GPUs, which prefer highly parallelizable matrix operations over sequential loops.

To bridge this gap, Zhen Qin et al. developed Lightning Attention. They mathematically reformulated the attention mechanism to eliminate the slow cumulative summation bottleneck, replacing it with a "divide and conquer" tiling strategy. This hardware-aware optimization allows the model to achieve constant training and inference speeds regardless of sequence length, unlocking massive throughput gains on real-world hardware.

Alternative Paths to Linear Scaling

Beyond kernel and polynomial approximations, the broader field of linear attention encompasses several distinct structural strategies to compress token interactions:

  • Nested Projections: Instead of mapping queries directly to keys, architectures like Luna, introduced by Xuezhe Ma et al., decompose attention into two sequential linear operations using a fixed-length auxiliary sequence to bridge the query and context.
  • Sketching and Smoothing: Rather than computing the full attention matrix, Tian Zhou et al. utilize Fourier-based smoothing and matrix "skeleton sketching" to sample specific rows and columns, drastically slashing peak memory usage.
  • Vector Quantization: Lucas D. Lingle et al. designed Transformer-VQ, which applies vector quantization to keys alongside block-level recurrence, preserving the expressive power of dense attention within a linear-time framework.
  • Two-Pass Gating: To improve information retrieval, Wei Bi et al. proposed Gated Slot Attention, which uses an initial pass to determine what information to look for and a subsequent pass to retrieve it, matching standard Transformer recall without the quadratic cost.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_complexity_attention_e952a197,
  title = {linear complexity attention},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-complexity-attention/rdr_e952a197b39d4d08bececa01d0769398},
  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_linear_complexity_attention_e952a197_v1,
  title = {linear complexity attention},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-complexity-attention/rdr_e952a197b39d4d08bececa01d0769398/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