Linear attention: Definition & Examples

Linear attention is a family of attention mechanisms that factor query–key similarities through finite feature vectors, allowing keys and values to be aggregated before each query reads them. For a quant model processing long news histories or market-event sequences, this can reduce the attention operation's growth with sequence length. The word linear describes that computational scaling; it does not make the whole neural network a linear function.

Aggregate first, query second

Let queries and keys be column vectors, values $v_j\in\mathbb{R}^{d_v}$ , and the feature map $\phi$ have width $r$ . Choose similarities $s_{ij}=\phi(q_i)^\top\phi(k_j)$ that are nonnegative, with a strictly positive sum for each query. Componentwise nonnegative features are a sufficient way to obtain nonnegative similarities, but an all-zero query or incompatible feature supports can still give a zero denominator.

Define the shared summaries

S=\sum_{j=1}^{N}\phi(k_j)v_j^\top, \qquad z=\sum_{j=1}^{N}\phi(k_j).

Then the output is

y_i^\top =\frac{\sum_{j=1}^{N}s_{ij}v_j^\top}{\sum_{j=1}^{N}s_{ij}} =\frac{\phi(q_i)^\top S}{\phi(q_i)^\top z}.

This is the associative computation developed by Katharopoulos et al.. The summaries have shapes

r\times d_v

and

r

, independent of the number of keys. For

N

queries and keys, aggregation and reading cost

O(Nrd_v)

, apart from feature construction and projections. Calling this linear in

N

holds

r

and

d_v

fixed. It avoids explicitly constructing an

N\times N

attention matrix; it does not remove all sequence activations or training memory.

An equality within one kernel

Take dimensionless toy vectors $q=(2,1)^\top$ , $k_1=(1,0)^\top$ , $k_2=(0,1)^\top$ , and scalar values $v_1=2$ , $v_2=4$ . Use the identity feature map on these nonnegative vectors. Similarities are $2$ and $1$ , so normalised weights are $2/3$ and $1/3$ :

y=\frac{2\cdot2+1\cdot4}{2+1}=\frac83\approx2.6667.

Alternatively, aggregate $S=(2,4)^\top$ and $z=(1,1)^\top$ first. The query produces numerator $q^\top S=8$ and denominator $q^\top z=3$ , giving the same result. Signed raw embeddings would not generally permit this identity-map construction with nonnegative weights.

Dimensionless toy attention: query (2, 1), keys (1, 0) and (0, 1), values 2 and 4. Direct linear-kernel weights (2/3, 1/3) and aggregate state S=(2, 4), z=(1, 1) both yield 8/3. Softmax of logits (2, 1) instead yields 2.5379.

Original toy calculation. Reordering the products preserves the chosen feature-kernel attention exactly; changing the kernel changes the output.

Applying softmax to logits

(2,1)

instead gives

y_{\mathrm{softmax}}=\frac{2e^2+4e}{e^2+e}\approx2.5379.

Here the logit scale is explicitly one; no dimension-based scaling is applied. The different answer comes from exponentiating the dot products. Associativity alone cannot move the rowwise softmax through the matrix products.

One approach chooses a different kernel, such as the positive feature construction in the original linear Transformer. Another approximates the softmax kernel using kernel feature approximation. Performer uses positive orthogonal random features for that second approach. Finite random features introduce approximation error; an unbiased estimate of a kernel entry does not automatically make the normalised ratio unbiased. These distinctions matter when replacing a trained softmax attention layer. Choromanski et al.

A running state must respect the forecast clock

For causal attention including the current position, maintain prefix summaries:

S_i=S_{i-1}+\phi(k_i)v_i^\top, \qquad z_i=z_{i-1}+\phi(k_i), \qquad y_i^\top=\frac{\phi(q_i)^\top S_i}{\phi(q_i)^\top z_i}.

Start with zero summaries. If the task permits only strictly earlier positions, read the previous state before adding the current key and value. A full-sequence summary would let future events affect earlier forecasts. The prefix mask also cannot repair embeddings built from information unavailable at the forecast time.

The attention state needs $O(rd_v+r)$ storage per head during sequential inference. Check finite values and positive denominators: small denominators and accumulated floating-point error can make the ratio fragile. A denominator floor changes the formula and should be treated as part of the implemented model.

For financial evaluation, compare forecast quality and actual latency on the same dated information set. A smaller attention state can make a longer history feasible, but it does not establish that older events improve a forecast. The fixed-width state also does not retain a separately addressable value vector for every past event.

The SelfMadeQuant QKV lesson develops the underlying weighted-context mechanism and query/key/value roles. Its public page is a preview; the full lesson requires membership.

Sources

Katharopoulos et al. (2020), Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention, §§3.1–3.3: kernel factorisation, computational cost and causal summaries.
Choromanski et al., Rethinking Attention with Performers, §§2.2–2.4: kernel approximation and positive orthogonal random features.

Aggregate first, query second

An equality within one kernel

A running state must respect the forecast clock

Sources

Related terms

Nyström approximation and random Fourier features

Softmax and log-sum-exp