PADRe: A Unifying Polynomial Attention Drop-in Replacement for Efficient Vision Transformer
Efficient Vision Transformer;Attention Approximation;Computer Vision;Deep Learning
Yes
No ethics review needed.
See weakness.
The unified formulation proposed in this paper is intriguing, as it establishes mathematical connections across different attention variants. I believe this polynomial-based approach has great potential for impact, offering a foundation for designing more efficient attention mechanisms in the future.
The paper proposes a novel approach to replace full-attention with a unified polynomial formulation that achieves linear complexity. The authors show that various efficient attention mechanisms can be seen as special cases within the PADRe framework. They also implement a specific instance of PADRe and observe a favorable trade-off between efficiency and accuracy, even with a polynomial degree as low as 3.
1): Figure 1 illustrates a specific design within the PADRe framework, but a straightforward baseline is missing. For example, for degree-
$d$ approximation, directly ensembling $d$ MLP-Mixers can be a strong baseline, and this approach can also be efficiently parallelized.

2): While the paper introduces a unified formulation, it remains unclear how readers can directly leverage it to enhance existing linear attention mechanisms. In Eq. (8), the coefficients $\pi_k$ are noted to have a complex dependency on parameters, specifically on the properties of the transformation matrices $A_i$, $B_i$, $C_i$ and $D_i$.  For example, in Eq. (82), a practical approximation formulation for the softmax operation can be more concrete. 

3): The experimental results demonstrate comparable performance with previous methods, but the paper defines the transformation matrices as pointwise and 2D convolutions to mix channels and tokens, respectively. However, it is well-established that adding locality can boost ViT performance (e.g., LocalViT). To fully evaluate the PADRe's effectiveness, testing on NLP benchmarks and models—without adding any locality inductive bias—would provide a more compelling validation.
Yes
No ethics review needed.
See the weakness.
1. Good insight and strong theoretical proofs. Approximating self-attention with polynomial approximants sounds interesting. The authors have provided solid proofs that the proposed PADRe can cover other special cases in recent works.

2. Experiments have well demonstrated the effectiveness of their approach, especially considering the FLOPs reduction in Table 3 and Table 4.

3. The paper is in a good structure. Figures are clear as well.
This paper introduces Polynomial Attention Drop-in Replacement (PADRe), a new method which aims to replace the conventional self-attention in Transformers. Specifically, PADRe replaces self-attention with polynomial approximants. Furthermore, it adopts mobile-friendly operations such as  Hadamard products to achieve a good balance between efficiency and performance.  The authors have provided rigorous proofs that the proposed PADRe is a general approach that covers previous Hyena, Mamba, SimA, etc. Extensive experiments have also demonstrated the effectiveness of their approach.
1. The paper acknowledges that model performance begins to saturate (Lines 462-463) when the polynomial degree exceeds 3, suggesting potential numerical stability issues with higher-degree polynomials. Investigating more stable polynomial bases could be beneficial.

2. As the author already states, this paper lacks experiments on LLMs. It would be great if we can know the performance of PADRe on LLMs. This could be more attractive to the community than experimenting on ViTs.

3. In Table 1, the improvement over DeiT-Base is minor. Could it be that PADRe works more effectively for smaller Transformers?
Yes
No ethics review needed.
Please see the weaknesses above.
1. This paper addresses an important problem in vision transformer design.

2. This paper provides a theory-driven solution with a thorough mathematical justification.
This paper proposes PADRe, a unifying framework for replacing the attention mechanism based on
polynomial approximants to provide an efficient, linear-complexity alternative to the
standard self-attention without sacrificing accuracy.
1. How would the method work for large language models (LLMs), with much longer sequence lengths?

2. How to decide the optimal degree of PARDe?
Yes
No ethics review needed.
- How does replacing self-attention with PADRe change the number of model parameters? Is there any increase or decrease? This will be helpful in understanding PADRe's impact on mobile devices since parameter count is directly correlated to storage, DRAM usage etc.
- Framework that helps building alternative self-attention based transformer architecture
- advantageous over Flash attention
This paper proposes a framework for drop in self attention replacement. This framework allows for building any polynomial time self-attention module, relies on polynomial approximates at the input, uses Hadamard product to introduce non-linearities. The framework at its current stage does not look into cross-attention and/or multi-modal attention although in principal it can be extended to cross-attention
- The authors evaluated PADRe on DeiT. It might be a good idea to evaluate PADRe on ViT (Dosovitskiy et al.). This will demonstrate the impact of PADRe even more since ViT is widely used as an image encoder for many other models such as CLIP, Vision LLMs etc.
- Since you are evaluating on device, it would be good to show peak memory consumption, anything that shows energy efficiency improvement when running PADRe over standard self-attention
Polynomial-based replacement of standard self-attention for efficient vision transformer that is hardware friendly and preserves accuracy
@inproceedings{
anonymous2024padre,
title={{PADR}e: A Unifying Polynomial Attention Drop-in Replacement for Efficient Vision Transformer},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=YFxfcQMLWX},
note={under review}
}
We present Polynomial Attention Drop-in Replacement (PADRe), a novel and unifying framework designed to replace the conventional self-attention mechanism in transformer models. Notably, several recent alternative attention mechanisms, including Hyena, Mamba, SimA, Conv2Former, and Castling-ViT, can be viewed as specific instances of our PADRe framework.  PADRe leverages polynomial functions and draws upon established results from approximation theory, enhancing computational efficiency without compromising accuracy.  PADRe's key components include multiplicative nonlinearities, which we implement using straightforward, hardware-friendly operations such as Hadamard products, incurring only linear computational and memory costs. PADRe further avoids the need for using complex functions such as Softmax, yet it maintains comparable or superior accuracy compared to traditional self-attention. We assess the effectiveness of PADRe as a drop-in replacement for self-attention across diverse computer vision tasks. These tasks include image classification, image-based 2D object detection, and 3D point cloud object detection. Empirical results demonstrate that PADRe runs significantly faster than the conventional self-attention (11x~43x faster on server GPU and mobile NPU) while maintaining similar accuracy when substituting self-attention in the transformer models.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Efficient Vision Transformer Attention Approximation Computer Vision Deep Learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/ae367ef3b7d46dc448a4c260df7e853c5573b081.pdf
other topics in machine learning (i.e., none of the above)
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
PADRe: A Unifying Polynomial Attention Drop-in Replacement for Efficient Vision Transformer
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission