achieved state-of-the-art performance on video classification [@nonlocal] and generative adversarial image modeling [@sagan; @biggan] and demonstrated significant improvements on object detection [@nonlocal], instance segmentation [@nonlocal], person re-identification [@video-reid], and image de-raining [@deraining], .

However, global dependency modeling on large inputs, long sequences, high-definition images, and large videos, remains an unsolved problem. The quadratic[^3] memory and computational complexities with respect to the input size of existing dot-product attention modules inhibit their application on such large inputs. For instance, a non-local module uses over 1 GB of GPU memory and over 50 GMACC[^4] of computation for a 64-channel $128 \times 128$ feature map or over 68 GB and over 3.2 TMACC for a 64-channel $64 \times 64 \times 32$ video feature volume. The high memory and computational costs constrain the application of dot-product attention to the low-resolution or short-temporal-span parts of models [@nonlocal; @sagan; @biggan] and prohibits its use for resolution-sensitive or resource-hungry tasks.

![**An illustration of the learned attention maps in a non-local module.** The first image identifies five query positions with colored dots. Each of the subsequent images illustrates the attention map for one of the positions. Adapted from [@sagan].[]{data-label="fig:factorizing"}](figures/factorizing.png){width="\linewidth"}

The need for global dependency modeling on large inputs greatly 