Linear Attention

Attention is one of the most important building blocks in modern artificial intelligence. It lets a model compare different parts of a sequence and decide which elements matter most. The standard attention mechanism used in Transformer models is powerful, but it comes with a cost.

The classic formulation computes attention as:

Attention(Q, K, V) = softmax(QK^T / sqrt(d)) V

The matrices Q, K, and V are usually shaped as N by d, where N is the sequence length. The product QK^T creates an N by N attention matrix. That means both computation and memory grow quadratically with sequence length. When N is small, this is not a problem. When N becomes very large, the approach becomes expensive.

Linear attention is a set of ideas designed to reduce this burden while trying to keep the core intuition of attention.

Why Standard Attention Is Expensive

In standard attention, every query can attend to every key. The softmax operation creates weights based on similarity. Then the output is a weighted sum of values.

Because the full attention matrix must be computed, the time complexity is O(N^2) and the memory complexity is also O(N^2). For long sequences, this becomes a bottleneck.

Linear attention aims to change the computation so that the sequence-level cost moves closer to linear. The goal is not simply to throw away attention. The goal is to reformulate it.

The Kernel-Based Insight

Linear attention relies heavily on a mathematical idea: a similarity function can sometimes be expressed as an inner product between feature representations.

Instead of using a direct similarity measure, linear attention maps queries and keys into a new space using a function phi. Then similarity can be written as:

sim(q, k) = phi(q)^T phi(k)

This means the attention weight is based on a dot product in the feature space. The original query and key are transformed before comparison.

Once this reformulation is made, the attention output can be computed using accumulated state. The full attention matrix is no longer needed. This is the key reason why linear attention can achieve better scaling.

From Quadratic to Linear Complexity

In ordinary attention, the output for each query involves a sum over all keys. Linear attention reorganizes this sum into a global state.

For example, the state might be defined as:

S = sum_j phi(k_j) v_j^T
z = sum_j phi(k_j)

Then the output can be computed as:

y_i = phi(q_i)^T S / (phi(q_i)^T z)

This structure avoids explicitly building an N by N matrix. The computational cost can drop from quadratic to roughly linear in sequence length, depending on the feature dimension.

When the feature map has a dimension similar to the original model dimension, the overall complexity can become close to O(N).

Choosing the Right Kernel

The feature map phi plays a central role. Different choices lead to different behaviors.

Some common approaches include:

• Identity mapping: phi(x) = x, which is simple but may not be numerically stable.
• Nonnegative mappings: phi(x) = ELU(x) + 1, ReLU(x) + 1, or Softplus(x), which can keep attention weights nonnegative.
• Random Fourier features: used in Performer to approximate a softmax kernel.
• Improved kernels: such as CosFormer or other variants for long-range modeling.

The choice of kernel can affect accuracy, stability, and capacity.

Causality and Streaming Inference

In autoregressive models, a token can only attend to previous tokens. Linear attention can handle this by using prefix states.

At each step, the state can be updated:

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

Then the output is:

y_t = phi(q_t)^T S_t / (phi(q_t)^T z_t + epsilon)

During training, cumulative sums can support parallel computation. During inference, the recurrence allows fixed-size state vectors to be updated step by step.

This makes linear attention suitable for streaming generation and low-latency applications.

Practical Considerations

Linear attention is not a free lunch. Approximate kernels may reduce precision. The feature mapping can be sensitive. Long-range dependency modeling may still be weaker than full softmax attention. The denominator may require numerical stabilization.

Still, the potential benefits are significant. Linear attention can reduce compute and memory costs, support longer sequences, and enable efficient streaming inference.

Summary

Linear attention reframes attention through kernel-based aggregation. By expressing similarity as a feature inner product, it avoids explicit quadratic attention matrices. The result is a method that can scale more gracefully and support long-sequence modeling. The field is still evolving, but the core promise remains attractive: keep the useful parts of attention while removing its quadratic bottleneck.