Quadratic Cost of Self-Attention in Sequence Length

The Quadratic Wall: The Algorithmic Race to Beat O(n²) Attention

In computational complexity theory applied to sequence modeling, the "quadratic wall" describes the asymptotic lower bound where standard self-attention mechanisms incur arithmetic and memory costs s…