Walk me through how linear attention eliminates the qua...

Standard softmax attention suffers from quadratic complexity because it requires computing an N x N attention matrix. Linear attention eliminates this by replacing the softmax kernel exp(q⊤k) with a kernelized feature map ϕ(q)⊤ϕ(k). By applying the associative property of matrix multiplication, the model can pull the query projection outside the sum over the sequence length. The resulting inner state Si = ∑j≤i ϕ(kj )v⊤j updates as a rank-1 outer-product addition at each step. This makes the state size fixed and independent of the sequence length, allowing for efficient training via a parallel scan over the recurrence.