attention mechanism quadratic complexity

Topics

• matrices
• attention mechanism

Standard attention mechanism has $O(N^2)$ complexity because:

1. Time Complexity: matrix multiplication $Q{K}^T$ (dot product between every query vector $Q_i$ and every key vector $K_j$) results in $N\times N$ matrix of similarity scores, which takes $O(N^2{d}_k)$ FLOPs. Multiplying $N\times N$ attention weight matrix by value matrix $V$ takes $O(N^2{d}_v)$ time. Overall time complexity is $O(N^2)$, assuming $d_k$​ and $d_v$​ are fixed dimensions independent of $N$

2. Memory Complexity: The $N\times N$ attention score matrix and attention weight matrix ($\text{softmax}(...)$) require $O(N^2)$ memory

This quadratic scaling severely restricts the maximum sequence length $N$ that can be practically processed. For instance, processing sequences longer than a few thousand tokens (as of writing) becomes prohibitively expensive in terms of both computation time and, often more critically, memory consumption.

Related

• linear attention math formulation (reduces complexity to $O(n)$)