linear attention

Standard attention forms a full table comparing every query with every key, and that table is what makes cost grow with the square of the sequence length. Linear attention avoids ever building the table. By replacing the softmax with a simpler similarity that factors apart, it can reorder the math so each new token just updates a fixed-size running summary of all past keys and values, much like a state-space model keeping notes.

The trick is associativity: with a kernel feature map, you can multiply keys by values first and accumulate them into a single matrix, then apply each query to that accumulator, turning quadratic cost into linear. The result reads and generates in time proportional to length with bounded memory. The honest tradeoff is accuracy: dropping the sharp softmax usually blunts the model's ability to focus precisely on one token, so linear attention often trails full attention on recall-heavy tasks unless carefully designed or hybridized.