only generates $d_k$ global context vectors in $\mathbb{R}^{d_v}$. This change eliminates the $O(n^2)$ terms from both the memory and computational complexities of the module. Consequently, efficient attention has $O((d_k + d)n + d_kd)$ memory complexity and $O((d_kd + d^2)n)$ computational complexities, assuming the common setting of $d_v = d$. Table \[tab:complexity\] shows complexity formulae of the efficient attention module and the non-local module (using dot-product attention) in detail. In computer vision, this complexity difference is very significant. Firstly, $n$ itself is quadratic in image side length and often very large in practice. Secondly, $d_k$ is a parameter of the module, which the designer of a network can tune to meet different resource requirements. Section \[sec:channels\] shows that, within a reasonable range, this parameter has minimal impact on performance. This result means that an efficient attention module can typically have a small $d_k$, which further increases its efficiency advantage over dot-product attention. Table \[tab:complexity-res\] compares the complexities of the efficient attention module with the ResBlock. The table shows that the resource demands of the efficient attention module are on par with (less than in most cases) the ResBlock, which gives an intuitive idea on the level of efficiency of he module.

  