any specific position. Instead, each of them corresponds to a semantic aspect of the entire input. For example, one such attention map might cover the persons in the input. Another might correspond to the background. Section \[sec:vis\] gives several concrete examples. Efficient attention uses each $\bm{k}_j^\mathrm{T}$ to aggregate the value features $\bm{V}$ and produce a global context vector $\bm{g}_j$. Since $\bm{k}^\mathrm{T}_j$ describes a global, semantic aspect of the input, $\bm{g}_j$ also summarizes a global, semantic aspect of the input. Then, position $i$ uses $\bm{q}_i$ as a set of coefficients over $\bm{g}_0, \bm{g}_1, \ldots, \bm{g}_{d_k - 1}$. Using the previous example, a person pixel might place a large weight on the global context vector for persons to refine its representation. A pixel at the boundary of an object might have large weights on the global context vectors for both the object and the background to enhance the contrast.

Efficiency Advantage {#sec:efficiency}
--------------------

This section analyzes the efficiency advantage of efficient attention over dot-product attention in memory and computation. The reason behind the efficiency advantage is that efficient attention does not compute a similarity between each pair of positions, which would occupy $O(n^2)$ memory and require $O(d_kn^2)$ computation to generate. Instead, it 