linear attention

Standard attention compares every query with every key, costing time and memory quadratic in sequence length. Linear attention removes the quadratic blow-up by replacing the softmax similarity with a kernel that factorizes. The trick: if the similarity between query q and key k can be written as a dot product of feature maps phi(q) and phi(k), then by associativity you can sum over keys first, computing the running sum of phi(k) times v transpose once, and reuse it for every query, turning quadratic cost into linear.

Concretely, the output for query i becomes phi(q_i) transpose times the sum over j up to i of phi(k_j) times v_j transpose, divided by phi(q_i) transpose times the sum over j up to i of phi(k_j). The bracketed quantities are a matrix and a vector that you accumulate left to right, so causal linear attention has a recurrent form: a fixed-size state S updated by S becomes S plus phi(k_t) times v_t transpose at each step and read out by phi(q_t). This gives constant memory per step and linear total time, and it reveals attention and RNNs as two faces of the same computation.

The catch is quality: a fixed-size state cannot store an unbounded history with the fidelity of full softmax attention, so naive linear attention underperforms on tasks needing sharp recall. Modern variants with gated or decayed states, delta-rule updates, and selective state-space models substantially close this gap and revive linear attention as a serious alternative for long sequences.