  Transformer architectures are now central to sequence modeling tasks. At its
heart is the attention mechanism, which enables effective modeling of long-term
dependencies in a sequence. Recently, transformers have been successfully
applied in the computer vision domain, where 2D images are first segmented into
patches and then treated as 1D sequences. Such linearization, however, impairs
the notion of spatial locality in images, which bears important visual clues.
To bridge the gap, we propose ripple attention, a sub-quadratic attention
mechanism for vision transformers. Built upon the recent kernel-based efficient
attention mechanisms, we design a novel dynamic programming algorithm that
weights contributions of different tokens to a query with respect to their
relative spatial distances in the 2D space in linear observed time. Extensive
experiments and analyses demonstrate the effectiveness of ripple attention on
various visual tasks.
