Efficient Attention: Attention with Linear Complexities

[5g4s]

Efficient Attention: Attention with Linear Complexities

[5g4s]

Since matrix multiplication is associative, switching the order from $\left(Q K^{\top}\right) V$ to $Q\left(K^{\top}T\right)$ has no impact on the effect but changes the complexities from $O\left(n^2\right)$ to $O\left(d_k d_v\right)$, for n the input size and $d_k$, $d_v$, the dimensionalities of the keys and the values, respectively.
This change removes the $O \left(n^2 \right)$ terms in the complexities of the module, making it linear in complexities.

[5g4s]

Dot-product attention equals efficient attention.