Neighborhood attentionreduces the cost of self attention by restricting each token’s attention span
to its nearest neighbors.
This restriction, parameterized by a window size and dilation factor, draws a spectrum of possible attention patterns between
linear projection and self attention.
Neighborhood attention, and more generally sliding window attention patterns, have long been bounded by infrastructure,
particularly in higher-rank spaces (2-D and 3-D) ,
calling for the development of custom kernels, which have been limited in either functionality, or performance, if not both.
In this work, we aim to massively improve upon existing infrastructure by providing two new methods for implementing
neighborhood attention.
We first show that neighborhood attention can be represented as a batched GEMM problem, similar to standard attention,
and implement it for 1-D and 2-D neighborhood attention.
These kernels on average provide 895% and 272% improvement in full precision latency compared to existing naive CUDA kernels
for 1-D and 2-D neighborhood attention respectively.
We find certain inherent inefficiencies in all unfused implementations of neighborhood attention that bound their performance
and hinder their lower-precision scalability.
Motivated by the progress made into fused dot-product attention kernels, we developed fused neighborhood attention;
an adaptation of fused dot-product attention kernels that allow fine-grained control over attention across different
spatial axes.
Known for reducing the quadratic time complexity of self attention to a linear complexity, neighborhood attention can now enjoy
a reduced and constant memory footprint, and record-breaking half precision latency.
We observe that our fused implementation successfully circumvents some of the unavoidable inefficiencies in unfused
implementations.
While our unfused GEMM-based kernels only improve half precision performance compared to naive kernels by an average of 496% and 113% in
1-D and 2-D problems respectively,
our fused kernels improve naive kernels by an average of 1607% and 581% in 1-D and 2-D problems respectively.
These translate into up to 97% improvement in inference speed in existing models based on neighborhood attention,
and additionally extend its applicability in vision (image and video)  as well as other modalities.
We will open source our kernels atgithub.com/SHI-Labs/NATTEN.