Bridging the Divide: Reconsidering Softmax and Linear Attention

Summary

The paper addresses the computational inefficiency of Softmax attention in Vision Transformers, particularly when handling high-resolution inputs. The authors provide a theoretical analysis showing that the injectivity and local modeling capabilities of attention mechanisms significantly impact performance. They demonstrate that linear attention, which has linear complexity, is not injective and thus performs poorly compared to Softmax attention. To address this, the authors propose modifications to make linear attention injective, resulting in InLine Attention, which improves performance in vision tasks while maintaining computational efficiency. Experiments on high-resolution vision tasks show that InLine attention exhibits comparable performance to Softmax attention.

Strengths

- The paper presents a solid theoretical analysis explaining the performance gap between linear and Softmax attention, focusing on injectivity and local modeling capabilities. - The proposed modifications to linear attention are simple yet improve the performance and computational efficiency of Vision Transformers.

Weaknesses

- The only novelty in the paper is the analysis of the injective property of Softmax and linear attention. The overall novelty and contribution of the paper are limited. - The analysis of the local modeling capability of Softmax and linear attention was originally presented by [1]. The authors do not mention this work in their manuscript. - The authors do not mention or provide any ablation study of the different embedding functions that can be used with InLine attention. Some works suggest that the exponential function is more beneficial than ReLU [2]. If the authors can show that InLine attention has similar performance for both ReLU and exponential functions, it could justify the strength of the method. - There is a lack of experiments on language models. Generally, language models are much harder to train with linear attention than Vision Transformers. Vision tasks mostly require learning local interactions where language exhibits more long-range dependencies between tokens. If the authors can show their method works on language models, it could improve the soundness of this work.

Questions

Normalizing linear attention by its mean (centering) as suggested in eq. 4 should result in negative attention scores. To be strictly positive, it requires all numbers to be greater than $-1/N$. Can the authors provide some analysis or ablation study showing the effect of negative values on the attention on performance? [1] The Devil in Linear Transformer [2] Linear Log-Normal Attention with Unbiased Concentration

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

This paper invetigate the linear attention in the Vision task

Strengths

1. The paper is well written, the motivation is clear. 2. The findings is this work is 1) inear attention is not injective, which is prone to assign identical attention weights to different query vector. 2) effective local modeling is essential for the success of Softmax attention, which linear attention deos not have. Thoses findings may be improtant for design efficient linear transformer. 3. The experimental results are good.

Weaknesses

1. The source code is not avaliable, the reproductability is unclear at this time. 2. how this linear attetnion compare with Vision Mamba since Mamba is efficient. 3. The experimental results are mainly on CV domain, is this algorithm adaptive to NLP or time series domain?

Questions

1. The source code is not avaliable, the reproductability is unclear at this time. 2. how this linear attetnion compare with Vision Mamba since Mamba is efficient. 3. The experimental results are mainly on CV domain, is this algorithm adaptive to NLP or time series domain?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The experimental results are mainly on CV domain, is this algorithm adaptive to NLP or time series domain?

Summary

This paper aims to solve the computational challenges of Softmax attention in vision tasks due to its quadratic complexity with respect to sequence length. Linear attention as an alternative, reduces complexity to linear time by altering the similarity function from Softmax to kernel functions. However, the authors argue linear attention’s poor expressive power and non-injective nature can lead to semantic confusion. The authors propose two methods to enhance linear attention: enforcing injective properties and improving local modeling capabilities. Using the Swin Transformer architecture, they validate these methods, showing that linear attention can match or exceed Softmax attention’s performance while maintaining lower computational costs. The main contributions are highlighting the importance of injectivity and local modeling in attention mechanisms and demonstrating that linear attention, with these enhancements, can outperform traditional Softmax attention.

Strengths

1. This paper thoroughly analyzes the shortcomings of linear attention in vision tasks compared to Softmax attention, identifying non-injective properties and attention confusion as potential root causes. The authors validate these issues through quantitative and qualitative experiments, demonstrating that they contribute to performance drops. The claims seem well-founded, and the verification process appears robust. 2. To address these issues, the authors propose a simple yet effective modification: using subtraction in the normalization of linear attention instead of division, creating a method they call injective linear attention (InLine). 3. The proposed InLine method achieves competitive performance on ImageNet 1k classification and various downstream tasks.

Weaknesses

1. Although the authors' hypothesis and claims seem reasonable, the performance of the proposed method is not remarkable. This paper also lacks the comparison to some related works. For example, another linear attention based method VVT [A] achieves the Top-1 Acc(%) of 84.1 on ImageNet1k with 61.8M Param and 10.8 GFLOPs. The proposed method, InLine-CSwin-B has a Top-1 Acc(%) of 84.5 on ImageNet1k with 73M Param and 14.9G FLOPs. Although InLine-CSwin-B is higher regarding accuracy by 0.4%, it uses 20% more Params and 40% more GFLOPs. This largely weakens the authors' claims. 2. The analysis of local modeling capability (L264-L275) indicates correlation rather than causation. The authors gradually increase the window size and find it does not lead to better performance. Based on this observation, they claim “the insufficient local modeling capability: a small window size restricts the receptive field but introduces strong local bias, enhancing local modeling, while a large window size enlarges the receptive field but further diminishes local modeling ability”. They find that adding a residual connection can solve the problem and thus claim that the local modeling capability of linear attention is problematic. However, as a common practice, a larger receptive field usually requires a different learning rate to ensure the network converges sufficiently. The effect of the residual connection here may not be as the authors claim, but rather just stabilizing the gradient. [A] Sun, W., Qin, Z., Deng, H., Wang, J., Zhang, Y., Zhang, K., Barnes, N., Birchfield, S., Kong, L. and Zhong, Y., 2023. Vicinity vision transformer. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(10), pp.12635-12649.

Questions

Overall the reviewer is quite concerned about the performance of the proposed method, especially given the fact it loses the direct comparison to a very related and comparable linear attention model.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

Summary

While linear attention reduces the quadratic complexity of softmax attention, it often suffers from inferior performance. The authors analysed the reason behind it and identified two crucial properties which linear attention lacks: 1) injectivity where different queries in linear attention may have the same attention scores, increasing semantic confusion; 2) local modeling where linear attention can’t capture local patterns well. To bridge the gap, the authors proposed injective linear attention (InLine) with local enhancement, which achieves comparable and even better performance than softmax attention across several models and benchmarks.

Strengths

1) The analysis of injectivity and locality includes both theoretical understanding and empirical evidence; 2) InLine achieves competitive performance to softmax attention, and performs better than several previous linear models.

Weaknesses

1) The locality issue of linear attention has been discussed in-depth before; 2) The motivation and formulation of InLine are very similar to FLatten, and doesn’t show substantial quality gain to FLatten; 3) It would be great to have language modeling experiments;

Questions

1) This is not the first paper discussing the locality problem of linear attention. Check [1] for more details. 2) The intuition of InLine is very similar to FLatten. For example, FLatten removes the division operation so it satisfies the injectivity and Flatten adopts depthwise convolution, enhancing locality modeling. Based on Table 9, InLine doesn’t outperform FlAtten significantly. The authors should give a more comprehensive analysis on the similarity and differences compared to Flatten and why InLine is preferred. [1] Qin et al., 2022; The Devil in Linear Transformer.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors discussed the limitations of their work.