\in \mathbb{R}^{n\times d_v}$, respectively, the output of dot-product attention is $$\label{eq:ca}
    \bm{D}(\bm{Q}, \bm{K}, \bm{V}) = \rho\left(\bm{Q}\bm{K}^\mathrm{T}\right)\bm{V}.$$ The normalization function has two common choices: $$\begin{aligned}
\begin{split}
\label{eq:ca-norm}
    \text{Scaling: } & \rho(\bm{Y}) = \frac{\bm{Y}}{n}, \\
    \text{Softmax: } & \rho(\bm{Y}) = \sigma_\text{row}(\bm{Y}),
\end{split}\end{aligned}$$ where $\sigma_\text{row}$ denotes applying the softmax function along each row of matrix $\bm{Y}$. An illustration of the dot-product attention module is in Figure \[fig:ca-ea\] (left).

The critical drawback of this mechanism is its resource demands. Since it computes a similarity between each pair of positions, there are $n^2$ such similarities, which results in $O(n^2)$ memory complexity and $O(d_kn^2)$ computational complexity. Therefore, dot-product attention’s resource demands get prohibitively high on large inputs. In practice, application of the mechanism is only possible on low-resolution features.

Efficient Attention {#sec:ea}
-------------------

Observing the critical drawback of dot-product attention, this paper proposes the efficient attention mechanism, which is mathematically equivalent to dot-product attention but much faster and more memory efficient. In efficient attention, the individual feature vectors $\bm{X} \in \mathbb{R}^{n \times d}$ still pass through three linear layers to form the query features $\bm{Q} \in \mathbb{R}^{n \times d_k}$, key features $\bm{K} \in \mathbb{R}^{n \times d_k}$, and value features $\bm{V} \in \mathbb{R}^{n \times d_v}$. However, instead 