Metric                       Efficient attention module                         Non-local module
  -------------------------- ---------------------------- ----------------------------------------
  Memory (floats)                   $(2d_k + 3d)n + d_kd$                     $(2d_k + 3d)n + n^2$
  Computation (MACC)                $(8d_kd + 2d^2 + d)n$   $(4d_kd + 2d^2 + d)n + (2d_k + 2d)n^2$
  Memory complexity                $O((d_k + d)n + d_kd)$                    $O((d_k + d)n + n^2)$
  Computational complexity             $O((d_kd + d^2)n)$         $O((d_kd + d^2)n + (d_k +d)n^2)$

  Module                         ResBlock               EA module
  -------------------- ------------------ -----------------------
  Memory (floats)                   $5dn$   $4dn + \frac{d^2}{2}$
  Computation (MACC)     $(36d^2 + 11d)n$           $(6d^2 + d)n$
  Mem. complexity                 $O(dn)$           $O(dn + d^2)$
  Comp. complexity              $O(d^2n)$               $O(d^2n)$

  : **Comparison of resource usage of the efficient attention module and the ResBlock.** Since the ResBlock does not have parameters $d_k, d_v$, this table sets $d_v = d, d_k = \frac{d}{2}$, the typical values for these parameters.[]{data-label="tab:complexity-res"}

![**Resource requirements under different input sizes.** The blue and orange bars depict the resource requirements of the efficient attention and non-local modules, respectively. The calculation assumes $d = d_v = 2d_k = 64$. The figure is in log scale.[]{data-label="fig:complexity"}](figures/complexity.png){width="3.25in"}

The rest of this section will give several concrete examples comparing the resource demands of the efficient attention and non-local modules. Figure \[fig:complexity\] compares their resource consumption for image features with different sizes. 