# Poly-NL: Linear Complexity Non-local Layers with Polynomials

arXiv: https://arxiv.org/abs/2107.02859 · HTML: https://mlsanity.com/paper/2107.02859/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 43 of its 60 references that are in the map.
- First posted on arXiv 6 Jul 2021.

## Builds on (most cited first, 30 of 43)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [Mask R-CNN](https://mlsanity.com/paper/1703.06870/) (2017)
- [Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization](https://mlsanity.com/paper/1610.02391/) (2016)
- [Feature Pyramid Networks for Object Detection](https://mlsanity.com/paper/1612.03144/) (2016)
- [Squeeze-and-Excitation Networks](https://mlsanity.com/paper/1709.01507/) (2017)
- [CBAM: Convolutional Block Attention Module](https://mlsanity.com/paper/1807.06521/) (2018)
- [Non-local Neural Networks](https://mlsanity.com/paper/1711.07971/) (2017)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [MMDetection: Open MMLab Detection Toolbox and Benchmark](https://mlsanity.com/paper/1906.07155/) (2019)
- [Dual Attention Network for Scene Segmentation](https://mlsanity.com/paper/1809.02983/) (2018)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Focal Loss for Dense Object Detection](https://mlsanity.com/paper/1708.02002/) (2017)
- [Understanding the Effective Receptive Field in Deep Convolutional Neural Networks](https://mlsanity.com/paper/1701.04128/) (2017)
- [Stand-Alone Self-Attention in Vision Models](https://mlsanity.com/paper/1906.05909/) (2019)
- [EDVR: Video Restoration with Enhanced Deformable Convolutional Networks](https://mlsanity.com/paper/1905.02716/) (2019)
- [Distance-IoU Loss: Faster and Better Learning for Bounding Box Regression](https://mlsanity.com/paper/1911.08287/) (2019)
- [Residual Attention Network for Image Classification](https://mlsanity.com/paper/1704.06904/) (2017)
- [Efficient Attention: Attention with Linear Complexities](https://mlsanity.com/paper/1812.01243/) (2018)
- [Attention Augmented Convolutional Networks](https://mlsanity.com/paper/1904.09925/) (2019)
- [GCNet: Non-local Networks Meet Squeeze-Excitation Networks and Beyond](https://mlsanity.com/paper/1904.11492/) (2019)
- [Axial-DeepLab: Stand-Alone Axial-Attention for Panoptic Segmentation](https://mlsanity.com/paper/2003.07853/) (2020)
- [WIDER FACE: A Face Detection Benchmark](https://mlsanity.com/paper/1511.06523/) (2015)

## Built on by (most cited first, 5 of 5)

- [The Spectral Bias of Polynomial Neural Networks](https://mlsanity.com/paper/2202.13473/) (2022)
- [Improving Face-Based Age Estimation with Attention-Based Dynamic Patch Fusion](https://mlsanity.com/paper/2112.10167/) (2021)
- [Regularization of polynomial networks for image recognition](https://mlsanity.com/paper/2303.13896/) (2023)
- [Multilinear Operator Networks](https://mlsanity.com/paper/2401.17992/) (2024)
- [PolySAE: Modeling Feature Interactions in Sparse Autoencoders via Polynomial Decoding](https://mlsanity.com/paper/2602.01322/) (2026)

## Abstract (arXiv)

Spatial self-attention layers, in the form of Non-Local blocks, introduce long-range dependencies in Convolutional Neural Networks by computing pairwise similarities among all possible positions. Such pairwise functions underpin the effectiveness of non-local layers, but also determine a complexity that scales quadratically with respect to the input size both in space and time. This is a severely limiting factor that practically hinders the applicability of non-local blocks to even moderately sized inputs. Previous works focused on reducing the complexity by modifying the underlying matrix operations, however in this work we aim to retain full expressiveness of non-local layers while keeping complexity linear. We overcome the efficiency limitation of non-local blocks by framing them as special cases of 3rd order polynomial functions. This fact enables us to formulate novel fast Non-Local blocks, capable of reducing the complexity from quadratic to linear with no loss in performance, by replacing any direct computation of pairwise similarities with element-wise multiplications. The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks, while having considerably less computational overhead.