Every Token Looks Everywhere: The Quadratic Bill Behind Attention
TL;DR for operators Long context becomes expensive for a specific architectural reason: standard self-attention allows every position to interact with every other position. In the usual formulation, that means $O(n^2 d)$ computation and $O(n^2)$ storage for attention-related matrices as sequence length $n$ grows. Hasi Hays’s mathematical monograph on attention1 is useful because it connects that deployment constraint directly to the mechanism that makes attention powerful in the first place. ...