Bridging the Divide: Reconsidering Softmax and Linear Attention
Authors: Dongchen Han
Yifan Pu
Zhuofan Xia
Yizeng Han
Xuran Pan
Xiu Li
Jiwen Lu
Shiji Song
Gao Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: Softmax attention
linear attention
Primary area: deep_learning_architectures

Abstract: Widely adopted in modern Vision Transformer designs, Softmax attention can effectively capture long-range visual information; however, it incurs excessive computational cost when dealing with high-resolution inputs. In contrast, linear attention naturally enjoys linear complexity and has great potential to scale up to higher-resolution images. Nonetheless, the unsatisfactory performance of linear attention greatly limits its practical application in various scenarios. In this paper, we take a step forward to close the gap between the linear and Softmax attention with novel theoretical analyses, which demystify the core factors behind the performance deviations. Specifically, we present two key perspectives to understand and alleviate the limitations of linear attention: the injective property and the local modeling ability. Firstly, we prove that linear attention is not injective, which is prone to assign identical attention weights to different query vectors, thus adding to severe semantic confusion since different queries correspond to the same outputs. Secondly, we confirm that effective local modeling is essential for the success of Softmax attention, in which linear attention falls short. The aforementioned two fundamental differences significantly contribute to the disparities between these two attention paradigms, which is demonstrated by our substantial empirical validation in the paper. In addition, more experiment results indicate that linear attention, as long as endowed with these two properties, can outperform Softmax attention across various tasks while maintaining lower computation complexity. Code is available at https://github.com/LeapLabTHU/InLine.

Bridging the Divide: Reconsidering Softmax and Linear Attention
Dongchen Han"
Yifan Pu"
Zhuofan Xia*
Yizeng Han
Xuran Pan
Xiu Li Jiwen Lu
Shiji Song
Gao Huang
Tsinghua University
Abstract
Widely adopted in modern Vision Transformer designs, Softmax attention effectively capture long-range visual information; however, incurs excessive computational cost when dealing with high-resolution inputs. In contrast, linear attention naturally enjoys linear complexity and has great potential to scale up to higher-resolutin images. Nonetheless, the unsatisfactory performance of linear attention greatly limits its practical application in various scenarios. In this paper, take step forward close the gap between the linear and Softmax attention with novel theoretical analyses, which demystify the core factors behind the per- formance deviations. Specifically, and alleviate the limitations of linear attention: the injective property and the local modeling ability. Firstly, prove that linear attention is not injective, which is prone to assign identical attention weights to different query vectors, thus adding to severe semantic confusion since different queries correspond to the same outputs. Secondly, we confirm that effective local modeling is essential for the success of Softmax attention, in which linear attention falls short. The aforementioned two fundamental differences significantly contribute to the disparities between these two attention paradigms, which demonstrated by our substantial empirical validation in the paper. In addition, more experiment results indicate that linear attention, as long as endowed with these two properties, can outperform Softmax attention across various tasks while maintaining lower computation complexity. Code available at https://github.com www.taubb.oomeaaaaaaeeeeaeeee www.aaap.aaaaaaae...
present two key perspectives understand
Introduction
Recent years have witnessed the unprecedented success of Transformer and attention [32] in the field of computer vision [7]. Softmax attention, also known as dot- product attention, has demonstrated remarkable expressive power, leading state-of-the-ar performance across various vision tasks [30, 2, 23, 35]. However, applying Softmax attention in vision also faces challenges. The quadratic complexity of Softmax attention results prohibitively high computational cost when applied with global receptive field. Previous works [33, 19, 36, 6, 45] have strived to reduce the computation complexity by restricting receptive fields introducing sparsity. Although effective, these approaches inevitably compromise Softmax attention's 's ability for long-range modeling and scalability.
The nature of Sofumax attention forces compute the dot-products between queries and keys QK N first, and then aggregates values e NxC by the normalized score Softmax(QRK /Vd). which accounts for the quadratic ((N2) complexity w.E.. the sequence length N. On the contrary. linear attention relaxes the similarity score between Q and K from Softmax to other functions
Equal Contribution.
1 Corresponding Author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

which can be decomposed into kernels, i.e., the linear attention replaces the original score func- tion Sim Q, K)= = Softmax(QK" /vd) with Sim(Q, (Q)))(()()) where o(.) is the kernel function. This substitution enables a change in the computation order from (Φ(Q))(K) V to (()) (Ø ()) based on the associative law of matrix multiplication, reducing the complexity from O(N2) to ((N) w.E.. the sequence length N. Nevertheless, every coin has two sides. Linear attention proves to be less effective than Softmax attention [3, 27, 40], whose poor expressive power limits its practical application. Although many pieces of research [27, 28, 22, 9, 40] have attempted to alleviate this issue in different ways, we still do not have a complete understanding of the key factors that contribute to the gap between linear and Softmax attention.
In this paper, we delve into the fundamental differences between linear and Softmax attention, offering two insightful perspectives to demystify the topic: the injective property and local modeling capability. Firstly, we consider attention as a function that maps a query to an attention score. We find that the injectivity of this attention function greatly affects the performance of the model. Specifically, the attention function is not injective, different queries will induce identical attention distributions, leading to severe semantic confusion within the feature space. Our rigorous analysis has demonstrated that the Softmax attention function is an injective function, whereas the linear attention function is not. Therefore, linear attention is vulnerable to the semantic confusion problem, which largely leads to its insufficient expressiveness. Secondly, our analysis of the attention weight distribution has confirmed that the success of Softmax attention is not solely dependent on its strong long-range modeling capabilities. Effective local modeling is also crucial to achieving optimal outcomes.
To validate our analyses, we present two simple yet effective methods to endow linear attention with the injective property and the local modeling ability, respectively. The widely employed Swin Transformer [19] architecture is used to validate our findings. The results highlight the importance of both properties in the gap between linear and Softmax attention. Moreover, comprehensive experiments demonstrate that linear attention, endowed with these two properties, outperforms the widely used Softmax attention across diverse tasks.
Our main contributions and takeaways are summarized as follows: (1) Injectivity is a key disparity between linear and Softmax attention. While Softmax attention is injective, the non-injective nature of linear attention causes semantic confusion and severely impairs model performance. To the best of our knowledge, our work is the first to conceptualize attention as a mapping function and prove the vital importance of its injective property. (2) Local modeling is still essential to the effectiveness of the attention mechanism, even though it is renowned for its large receptive field and outstanding long-range modeling ability. (3) We challenge the viewpoint that linear attention is inferior to Softmax
attention and demonstrate that with the above two properties, linear attention can outperform Softmax attention while maintaining lower computation complexity.
2 Related Works
Vision Transformer and Softmax Attention. Vision Transformer [7] the pioneer work that introduces self-attention to vision. Since then, attention has found success in various vision tasks [7, 2, 24]. The widely used attention mechanism is Softmax attention [32], also known as dot-producc attention, which computes the similarity between all query-key pairs. Although effective, its quadratic computation complexity leads to unmanageable cost when processing global feature maps. Therefore, various approaches [19, 34, 36, 14, 45, 12] have been proposed to reduce the computational overhead of Softmax attention. PVT [33] employs downsampling of keys and values to reduce computational complexity. Swin Transformer [19] restricts the receptive field by introducing window attention pattern. NAT [14] mimics convolution and calculates attention within the neighborhood of each feature, and DAT [36] presents input-dependent sparse attention pattern.
Linear Attention. As opposed Softmax attention, Linear attention is another attention paradigm with natural linear complexity of O(N). Linear attention replaces Softmax with kernel functions, thereby reducing computational complexity to linear through a change in computation order. Nonethe- less, prior studies [27, 3, 29, 40, 11] have demonstrated that linear attention performs markedly worse than Softmax attention. CosFormer attributed this discrepancy to the efficient re-weighting mechanism of Softmax attention and proposed cosine re-weighting to enhance linear attention. Nys- trömformer [38] and SOFT [22] use matrix decomposition to further approximate Softmax operation. Efficient Attention [28] applies Softmax function to queries and keys. Tormer [26] identifies
2

---

Attn(@1)
Attm(
Atta((s)
Attm
(C) ReAU()
0.25
0.22
0,1
0.20
0.44
Softmax
Attention
2.
0.25
0.20
0.25
0.57
0.24
0.15
0.25
0.15
15-
0.32
0.23
0.32
0.23
0.32
0.25
0.32
0.23
Legend
Linear ttention
10-
3.0
Inl.ine Attention (0 (urs)
0.0
0.5
1.0
1.5
2.0
(a)
0.25
0.20
0.26
0.17
0.26
0.14
0.26
0.12
(C) ReLU(A +b)
A itention
2.0
0.1
0.18
0.22
0.17
0.24
0.16
0.25
0.14
0.4
0.51
0.24
0.31
0.54
0.31
0.24
0.31
0.34
Linear Attention
0.0
0.5
2.0
1.5
2.0
A ttention
(b)
0.24
0.18
0.24
0.16
0.24
0.15
0.24
0.30
Figure 1: An illustration of injective property and confusion problem. Non-injectivity leads to various semantic confusions in linear attention when different kernel functions are employed. (a) With o(-) ReLU(-), linear attention assigns the same attention values to collinear queries of varying lengths. (b) Using (--) = ReLU(A +6), linear attention faces severe confusion problem, producing identical attention distribution for certain queries with different directions and lengths.
that unbounded gradients and attention dilution harm linear attention. FLatten Transformer [9] introduces focused function address the smoothin issue. MLLA [10] draws inspiration from Mamba [8] to improve linear attention.
Despite their elegant outcomes, the fundamental reason for the disparity between linear attention and Softmax attention remains unclear. In this work, we perform an in-depth analysis of the disparities between linear and Softmax attention, identifying crucial properties higghperformance Softmax attention: injectivity and local modeling ability, We present both theoretical proofs and experimental verification validate our findings.
3 Preliminaries
Attention Formulation. Let r E IR NCC be an input of N tokens. In each self-attention head, is transformed into Q = xWQ. = xW k, V= xWv through projection matrices W Wo/k/v RCxd where C' and d are the channel dimension of module and each head. Therefore, we have Q, K, V e N and Q., K;, V, E Rd. Based on this, Softmax attention [32] computes the attention weights and calculates the output the weighted sum of value:
S; exp(Q, Ki)
exp(Q, Σ Q K2)
O =S.
(1)
J==1 Q,
For simplicity, we omit Vd exinnexp(]] (Q_ Kj/Väl since we can equivalently renormalize Q and K. This attention paradigm has been highly successful in modern vision Transformers. However, it should compute the similarity between all query-key pairs, resulting O(N2) complexity. Consequently, employing Softmax attention with global receptive field results in overwhelming computation cost.

---

Linear attention [15] was proposed to efficiently handle the computation challenge with linear complexity of (NN). Specifically, exp(Q; K2) is replaced by (Qi) ((Q)))((K))) where & is kernel function. In this way, linear attentions reformulate eq. (1) as:
(QQ)) ((KN) 1" ((2.) ((K,)
(QQ)T(K)) En ((Q.)T((K))))
L
(2)
((2)) k(K))
VJ ((Q)) (E/= ((K))) ((Q)) (E o(K)))
0f - = = j=1 (Qi)) (((K)
The form of O. suggests that explicitly computing attention weights L, unnecessary. Instead, we can change the computation order from (o(Q))(K) TV to ((K)) T V) based on the associative property of matrix multiplication. By doing so, the computation complexity is reduced to (NV).
Injective Property Let f A + B be mapping function. We call injective function if and only if Vo, A, # it holds that f(xx) + f(v)-
Analysing the Gap between Linear and Softmax Attention
Due its linear computation complexity, linear attention is considered a promising solution to address the computational challenges of Softmax attention in high-resolution scenarios. However, previous works [27, 3, 40] have shown that linear attention's 's expressive power is significantly lower than that of Softmax attention, rendering it impractical for real-world applications. In this section, we conducted in-depth analysis of the gap between linear and softmax attention from two perspectives: injective mapping and local modeling capability, and offer both theoretical proofs and experimental verification to enhance understanding of the key disparities between these two attention types.
4.1 Injectivity of Attention Function
We first define the function of Softmax and linear attention as follows:
SK, Lg IR + R.N, Sk(Q.) S., Lk(Q.)= Li,
where Q: denotes the query, and St, L, are the attention scores in eq. (1) and eq. (2). Given keys K Nxxx Sk, LK can be viewed as the function of query q. mapping each q to corresponding Softmax and linear attention scores, Sk(g) and (g). Then the final outputs of Softmax and linear attention corresponding to 9 can be formulated as O (g) and O Lx(g) V.
Injective property. In this work, we identify that the injective property of the attention function significantly impacts model performance, which may largely contribute to the gap between linear prove that under mild assumptions, the Softmax attention
and Softmax attention. Specifically, function SK is injective, whereas linear attention function Lg is not (Proposition and Please refer Appendix for complete proof). As consequent, for two different queries p and q (p q). Softmax attention should produce different attention distributions Sk(p) * Sk(4), while linear attention may yield the same linear attention values Tx(p) Tux (q). Since different queries p # q typically represent distinct semantics, the non-injective property of linear attention actually leads to semantic confusion, i.c. (k(p) Lk(g) and Of (p) Lk((g) to distinguish certain semantics.
Of, making the model unable
Proposition 1 (Softmax attention is injective) Given K Nxd with rank(K) d and rank([K, 1 Ixx1)) = d + 1. Vp. Rd & 4, we have Sk(p) # Sk(g).
Proposition (Linear attention not injective) Let Φ Rdd + Rd be a continuous function. 3 p. Rd .p * q, s.t. (p(p) = Lx(g).
We provide an example to better understand the injective property and confusion problem. As shown in Fig. ((a), there are four collinear vectors with different lengths. Benefiting from injectivity, Softmax attention ensures that each of these four queries obtains distinct attention scores, producing more focused attention distributions for longer queries. Nevertheless, with kernel function ob.) ReL.U(-), linear attention fails to distinguish the same semantics with different intensities, i.e. collinear queries with varying lengths, resulting in identical attention scores for all these four queries. Consequently,

---

linear attention is unable to yield more focused attention scores for stronger semantics, which may explain the lack of focus ability discussed in [9]. When using kernel functions with stronger nonlinearity, linear attention encounters more pronounced confusion issues. For instance, in Fig. 1(b), employing kernel function o(-) = ReLU(A +b), linear attention assigns exactly the same attention scores to four queries with different directions and lengths. This serious semantic confusion can directly impair model's performance.
Confusion problem in real models. While Fig. 1 illustrates the concept of confusion, it also crucial to verify if this issue occurs in real models. Therefore, we conduct statistical analy- sis based on Deit-T. We count the occurrences of confusion for each image (i.e., P # q but (p) = Sk(g) or (p(p) = =L during inference on the ImageNet [5] validation set. As is rare for two vectors to be strictly equal in floating-point representation, we consider them approximately equal if the L2 norm of their difference is less than lc-3. The results are provided in Fig. 2. Almost all samples did not encounter confusion model employing Softmax attention, whereas large number of samples encountered confusion more than 2 times on linear attention model. This proves the existence of confusion problem with linear attention in real models.
Softmax
0.8
Linear
percentage
InLine (Ours)
0.4
0.0
2 2 2 222222222 2"2"" Confusion Occurs
Figure 2: The distribution of the number of times each image encoun- ters confusion during inference.
The importance of injectivity. We further verify the importance of injec- tivity by inducing confusion in Soft- max attention. To achieve this, we apply additional non-injective map- ping functions to each query before the Softmax attention calculation, i.e., introducing Q:= (Qi)
Table I: Introducing confusion Softmax attention.
Confusion None fi( = |ReLU()) f2(4)=
ReLU(g)
ReLUU(A9+)) [[geLU(A++bi]
Acc. 72.2
70.6
69.9
prior to eq. (1), where is non-injective function. Specifically, we use f1) [|ReLUU to
()LU(g)
simulate the confusion observed linear attention using the kernel function Φ(-) ReLUU-)), as
depicted in Fig. ((a), and employ f2(2)= = [[EeLU[Aq+b]]]]
(e++b() to replicate the confusion in Fig. 1(b). As
shown in Tab. 1, introducing confusion leads to an obvious decrease in performance, underscoring the crucial role of the attention function's 's injective property. Therefore, the non-injectivity of linear attention is likely key factor leading to its limited expressive capacity.
Make linear attention injective. We propose simple yet effective solution make linear attention an injective function. The proof of Proposition 2 (see Appendix) demonstrates that Va & 0, ap(p) obtains identical scores in linear attention due to the omission of a in division, resulting in non- injectivity. Hence, we simply transform the normalization of linear attention from division to subtraction, presenting our injective linear attention (InLine) follows:
(Q.) [ .(1.)) To(N) T_
Σ (QQ)T((K)) +
1 N'
(4)
N
and the attention output corresponding Q, can be written O (Q.)((.))) TV. This modification ensures that the attention weights still sum up to I, while transforming the attention function into an injective one (see Proposition 3). Thus, injective linear attention can distinguish different queries, akin to Softmax attention, and it no longer suffers from confusion problem.
Proposition 3 (InLine attention is injective) Let ó Rd + Rd be injective map. Given K Nxd with rank @ (K)) =) and rank( K), 1nxx])====i Vp, q E Rd, * g. = lnLK(p) # InLk(q).
Additionally, similar to linear attention, InLine attention can be calculated with O(N) complexity by changing the computation order:
Of ( Σ ((QI)T(K))
1 N
Σ (Q.)) (K,)((
Vi
(5)
N
N
1 N
= =(())
Σ
((2)) Σ o(K,) -
Σ Vj.
N
3=1
j=1
5

---

Imtge
Softmax
Linear
InLine Atta
Image
InLine
Figure 4: Visualizations of attention distributions. Softmax attention exhibits strong local bias. The other two attention types yield meaningful attention distributions, but focus more on global modeling.
Table 2: Model performances ImageNet-1K KK when masking out tokens from different positions.
Loc. & x means masking out tokens in local x windows for each query. Rand n represents randomly masking out tokens out of local 3 x windows for each query. The attention scores of each query still sum up to These models are tested directly without retraining.
Mask Out Position
None
Loc. 3x3
Loc. 5x5
Loc. 7x7
Rand 9 Rand 25
Rand 49
Softmax Attn
72.2
51.6
24.3
9.0
71.7
71.5
71.1
InLine Atin
70.0
58.0
20.0
70.0
69.9
69.5
Since we can compute Σ)= o(K)) and 1. ΣØ=1 Vy once and reuse them for every query, the overall complexity InLine attention 2Nd Nd ((NF). Accounting for multi-head, the complexity becomes (NCd),, where C and d are the channel dimension of the model and each head.
4.2 Local Modeling Capability
Attention mechanism famous for its large receptive field and outstanding long-range modeling capability. However, find that effective local modeling is crucial for the effectiveness of attention.
In Fig. we compute the sum attention values assigned to local 3 neighborhoods for each query using De With a total of 14x14+1 197 tokens in each attention layer of DeiT-T, if attention scores are randomly assigned, the expected sum of attention for 3 neighborhood would be 197. The result shows that all three attention paradigms tend to pay more attention to the neighborhoods of each query, revealing local bias, especially shallow layers. Notably, Softmax attention allocates substantial amount of attention to local windows, suggesting stronger local modeling ability compared to the other two attention paradigms. Visualizations are provided in Fig. 4 to further confirm this finding.
0.6
Local Alli Score
Softmax Attn
Linear Attn InLine Attn (Ours) 9/197
0.4
g
0.2
0.0
Layer
Figure 3: The sum of attention scores in the
local 3x3 windows of each query from DeiT-T.
We speculate that Softmax attention's 's superior performance stems from robust local priors and strong local modeling capabilities. To validate this hypothesis, we employ attention masks to mask out tokens from various positions and assess their effect model performance. The results presented Tab. 2. Two key observations emerge: 1. Masking out local tokens significantly decreases model performance, while randomly masking out the same number of tokens has minor impact results. Softmax attention's performance suffers more severely than InLine attention when local tokens are masked out. These findings demonstrate the significance of local modeling for both attention types and prove that Softmax attention's 's advantage over InLine attention primarily attributes to its stronger local modeling ability.
Based on our analysis, increasing local bias may enhance the expressive power of InLine attention. In light of this, employ MLP to predict additional local attention residual for InLine attention.

---

Table 3: Ablation on the impact of injective property using Swin-T.
Kernel Function (6-)
(-I.U(-)
ReI.U(A +b)
LeakyRel.U()) Identity())
Linear Attn
77.3
70.2
1.5
0.2
InLine Attn
79.8
80.0
79.8
80.2
Table 4: Ablation on local modeling ability based on Swin-T. Identity() (-) kernel function is used.
Window
FLOPs
#PParam
Acc.
Window
FLOPs
#Param
Acc.
7
4.5G
30M
80.3
7
4.5G
30M
81.6
InLine-Swin-1
142
4.5G
30M
80.4
Inl-ine-Swin-T
142
4.5G
30M
82.1
w/o res.
28a
4.5G
30M
80.2
res.
28
4.5G
30M
82.3
56
4.5G
30M
80.2
56
4.5G
30M
82.4
Specifically, the output corresponding to Q; is defined as:
9
O, = (n.)
+ Σ V r MLP(T,
(6)
J=1
where InLK(-) denotes InLine attention function, is the average of input tokens, r is the predicted local attention residual, and V,)(() represents the value in the 3 neighborhood of Qú In this way, we explicitly enhance InLine attention's local bias by introducing local attention residual term. We refer to InLine attention with local attention residual, i.c. eq. (6), as InLine attention module. As the local residual term introduces little computational cost Nd + 9Nd, the InLine attention module still maintains linear complexity of ((N).
5 Empirical Study
In Sec. 4, we analyzed two core factors behind the performance gap between Softmax and linear attention, proposing possible remedies. In this section, conduct empirical verification to fully validate the importance of these two properties and the effectiveness our methods.
5.1 Implementation
We utilize the popular Swin Transformer architecture [19] to investigate the effects of injectivity and local modeling capability. Specifically, we substitute the original Softmax attention in Swin- T with linear attention to establish the baseline model. Subsequently, we introduce the injective property and local bias in turn assess their respective impacts. To fully verify the effectiveness of inl attention module, we further apply it to four advanced and representative Transformer models including DeiT [30], PVT [33], Swin [19], CSwin [6] and offer broad comparisons with various state-of-the-art methods using Softmax attention.
5.2 Datasets and Experiment Details
ImageNet classification. The ImageNet- IK [5] recognition dataset contains 1.28M training images and 50K validation images with total of 1,000 classes. For a fair comparison, we train our model using identical settings the corresponding baseline model. We Adam [21] optimizer train all our models from scratch for 300 epochs, employing cosine learning rate decay with 20 epochs of linear warm-up. The initial learning rate is 10-3 and the weight decay is 0.05. Augmentation and regularization strategies consist of Rand AundAugment [4], Mixup [42], CutMix [41], and random erasing [43]. Following CSwin [6], EMA [25] is used the training of InLine-CSwin models.
COCO object detection. COCO [18] object detection and instance segmentation dataset has 118K training and 5K validation images. We follow the training and testing strategies of the corresponding baseline model and employ pretrained InLine backbones to conduct experiments.
ADE20K semantic segmentation. ADE20K [44] is well-established benchmark for semantic segmentation which encompasses 20K training images, 2K validation images and 150 semantic categories. The same setting as bascline model is adopted.

---

Table Comparison with baseline models on ImageNet-IK. See full comparison table in Appendix.
Method
Reso
#Params FLOPs
Top-1
Method
Reso
#Params
FLOPs
Top-1
DeïT-T [30]
224
5.7M
1.2G
72.2
Swin-T [19]
2212
29M
4.5G
81.3
InLine-DeiT-T
224
6.5M
1.1G
(+2.)
InLine-Swin-I
224
30M
4.5G
(-.4
DeïT-B
224
86.6M
17.6G
81.8
Swin-S
224
50M
8.7G
83.0
InLine-DeiT-B
448"
23.8M
17.2G
82.3 (10.5)
InLinn-Swin-S
2212
50M
8.7G
83.6
PVT-S
224"
24.5M
3.8G
79.8
Swin-B
224
88M
15.4G
83.5
InLine-PVT-S
224"
21.6M
3,9G
(+22)
InLine-Swin-B
224
88M
15.4G
(+0.6)
PVT-L
224
61.4M
9.8G
81.7
Swin-B
3842
88M
47.0G
84.5
InLine-PVTI
224
50.2M
10.2G
(416)
Inl.ineSSwin-B
384
88M
45.2G
(-..))
Table 6: Comparison with SOTA methods on ImageNet-IK.
Method
Reso #Params FLOPs
Top-1
Method
Reso #Params FLOPSs Top-1
PVTv2-B2 [34]
224
25M
4.0G
82.0
Swin-B [19]
224"
88M
15.4G
83.5
ConvNeXt-T [20]
224
29M
4.5G
82.1
PVTv2-B5 [34]
224
82M
11.8G
83.8
Focal-T [39]
2242
29M
4.9G
82.2
ConvNeXt-B [20]
224
89M
15.4G
83.8
MViTv2-T [17]
224
24M
4.7G
82.3
Focal-B [39]
224
90M
16.4G
84.0
CSwin-T [6]
2242
23M
4.3G
82.7
CSwin-B
2242
78M
15.0G
84.2
DINAT-T [13]
2242
28M
4.3G
82.7
NAT-B [14]
224
90M
13.7G
84.3
InL.in-CSSin-TT
22/12
21M
4.3G
83.2
InLine-CSwing
2212
73M
14.9G
84.5
ConvNcXt-S [20]
224
50M
8.7G
83.1
Swin-B [19]
384
88M
47.0G
84.5
PVTv2-B3 [34]
2242
45M
7.9G
83.2
CaiT-S36 [31]
384²
68M
48.0G
85.0
C [6]
2242
35M
6.9G
83.6
ConvNeXI-B [20]
384
89M
45.0G
85.1
Focal-T [39]
224
51M
9.4G
83.6
MViTv2-B B [17]
3842
52M
36.7G
85.2
MV [17]
224
35M
7.0G
83.6
CSwin-B
384
78M
47.0G
85.4
InLine S
224
33M
6.8G
83.8
InLine- Linne-CSwinBB
3842
73M
46.3G
85.7
5.3 Empirical Analysis of Injectivity and Local Modeling
Injective property. As shown in Tab. 3, we adopt four different kernel function o(-) to validate the effect of injectivity. As discussed in Sec. 4.1, with kernel function e(-) ReLU(.), linear attention fails to distinguish the same semantics with different intensities. Addressing this issue with InLine attention leads to a 2.5 increase accuracy. When using d(-) ReLU(A- (b), linear attention faces more severe semantic confusion, and introducing injective property results in a significant accuracy boost of 9.8, from 70.2 80.0. These obvious improvements fully prove the significance of injectivity and validate the effectiveness of our injective linear attention. We also employ two kernel functions that do not ensure non negativvii Consistent with the findings in [27], linear attention fails to converge without non-negativity assurance. We attribute this to extreme semantic confusion. For example, with Φ(-) Identity(-), linear attention is unable to distinguish completely opposite semantics, assigning identical attention scores to and -q.
Local modeling capability. Tab. 4 highlights the importance of local modeling capability. In the left table, we apply pure Inl.ne attention to Swin-T and gradually increase the window size from 72 to 562. Due to the linear complexity of InLine attention, we can adopt different window sizes while preserving identical computational cost. Larger window sizes lead to larger receptive fields, typically associated with improved performance. However, the results show that the model performance does not improve with increasing window sizes. We believe this can be attributed to the insufficient local modeling capability: 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. To validate this, we apply InLine attention with local residual and present the results in the right table. Significant improvements can be observed upon the introduction of the local residual term. Additionally, the increase in window size leads to steady performance improvement after introducing local residual, which strongly supports analysis.
8

---

1000
Accuracy (89
83
10a
1.9x
62
3.7x
600
81
InLine PVT (ours)
10a
Swin
Swin-T
Innene InLine-Swin Swin (ours)
Swin-T
InLine-DeiTF
1.0
1.5
2.0
200
14
56
224
384
640
1024
(a)
Runtime (ms)
(b) Window Size
(C)
Resolution
Figure 5: Speed measurements. Runtime and FPS is tested on RTX3090 GPU. (a) Accuracy- Runtime curve on ImageNet. (b) Increasing window size. (c) High-resolution scenarios.
Table 7: Results on COCO dataset. The FLOPs are computed with an input resolution of 1280x800.
(a) Mask R-CNN Object Detection on COCO
Method
FLOPs
Sch.
AP"
AP
AP%
APm
AP
AP
PVT-T
240G
1x
36.7
59.2
39.3
35.1
56.7
37.3
InLine-PVTr PVT-T
211G
40.2
62.7
43.8
37.7
59.7
40.4
PVT-S
305G
1x
40.4
62.9
43.8
37,8
60.1
40.3
InLine-PVTSS
250G
43.4
66.4
47.1
40.1
63.1
43.3
PVT-M
392G
1x
42.0
64.4
45.6
39.0
61.6
42.1
AnLine-PVT-N
310G
44.0
66.4
48.0
40.3
63.4
43.5
PVT-
494G
1x
42.9
65.0
46.6
39.5
61.9
42.5
InL-IL-PVT-L
377G
45.4
67.6
49.7
41.4
64.7
44.6
(b) Cascade Mask
R-CNN Object Detection
COCO
Method
FL.OPs
Sch.
Ap
AP
AP
Apm
AP
AP
Swin-S
837G
3x
51.9
70.7
56.3
45.0
68.2
48.8
InLine-Swin
835G
3x
52.4
71.0
56.9
45.4
68.8
49.6
Swin-B
981G
3x
51.9
70.5
56.4
45.0
68.1
48.9
InLine-Swin
978G
3x
52.6
71.0
57.0
45.4
68.5
49.3
5.4 Main Results and Broad Comparisons
As shown in Tab, 4, InLine-Swin-T with local residual achieves better results than the Swin-T baseline, increasing from 81.3 82.4. Therefore. wonder whether InLine attention module can perform better than the widely adopted Softmax attention in various scenarios. To validate this, we further apply several representative Transformers and conduct comprehensive comparisons on image classification, object detection, and semantic segmentation.
ImageNet classification. Firstly, We apply our InLine attention module DeiT [30], PVT [33], and Swin Transformer [19], presenting the results in Tab. 5. It can be seen that substituting Softmax attention with our method results in notable improvements. For example, InLine-PVTT-S outperforms PVT-L. with 30% of the parameters and 40% the FLOPs. Subsequently, We apply our module to the advanced Transformer design, CSwin Transformer [6], and offer a broad comparison with various state-of-the-art models on ImageNet-IK. K. As depicted in Tab. 6, our InLine-CSwin model not only yields better results than CSwin, but also surpasses various SOTA CNN and Transformer designs. These results demonstrate that our InLine attention module tends to be superior alternative to the widely used Softmax attention.
Inference throughput analysis. We offer real speed measurements in Fig. 5. As shown in Fig. 5(a), InLine models achieve obviously better trade-off between accuracy and latency. In Fig. 5(b), increase the window size from 72 to 562. Due to the quadratic complexity of Softmax attention, Swin-T's speed drops sharply window goes larger. On the contrary, InLine-Swin-T with linear complexity even exhibits higher speed with larger windows. This may be due to the reduction in the latency caused by the window partition. With global receptive field, InLine benefits from both high performance (see Tab, 4) and fast speed. Furthermore, Fig. 5(c) shows the significant computational advantage of InLine in reshuresolt scenarios.

---

COCO object detection. Tab. 7 shows that In- Line attention consistently improves the results in object detection tasks. For instance, InI Line- PVT-$ outperforms PVT-T with 6.7 box AP un- der similar FLOPs, and InL.ne-PPVTA surpasses PVT-M by 3.4 box AP with fewer FLOPs, show- ing the advantage of InLine attention's 's linear complexity in high-resolution scenarios.
Table 8: Results semantic segmentation. The FLOPs are computed over encoders and decoders with an input image at the resolution of x12x2048.
S-FPN is short for SemanticFPN [ [16] model.
Semantic Segmentation ADE20K
Backbone
Method FLOPs
#Params
mloU mAcc
PVT-T
S-FPN
158G
17M
36.57 46.72
Inl.ine-PVT-T
S-FPN
127G
16M
39.16 50.63
ADE20K semantic segmentation. We employ our model on two representative segmentation models, SemanticFPN [16] and UperNet [37]. As depicted Tab. 8, benefited from injectivity and effective local modeling ability, Our Inl achieves better results under all settings with obviously lower computational cost.
PVT-S
S-FPN
225G
28M
41.95
53.02
MiLine-PVTSS
S-FPN
168G
25M
42.93
54.58
PVT-L
S-FPN
420G
65M
43.49
54.62
InLine-PVT-L
S-FPN
298G
55M
44.71
57.17
Swin-T
UperNet 945G
60M
44.51
55.61
InLine Swin--
UperNet 941G
61M
45.57 57.60
Comparison with SOTA linear attention de- signs. As shown in Tab. 9, our simple InLine attention design outperforms various linear at- tention methods without bells and whistles. Ad- ditionally, our Inline attention can possibly in- tegrate with previous designs to achieve better results, which we leave for future work. For instance, the advanced focused function in FLat- ten [9] can also be employed InLine attention.
Table 9: Comparison of different linear attention designs using DeiT-T.
Method
#Params
FLOPs
Acc.
Hydra Attn [1]
5.7M
1.1G
68.3
Efficient Attn [28]
5.7M
1.1G
70.2
Linear Angular Atin [40]
5.7M
1.IG
70.8
FLatten [9]
6.1M
1.1G
74.1
InLine (Ours)
6.5M
1.1G
74.5
5.5 Ablation Study
The effectiveness of two key designs has been verified and detailed analyzed in Sec. 5.3. In Tab. 10, we offer additional results to validate the impact of different kernel functions. It is shown that our InLine attention can effectively work with different kernel functions, further validating the effectiveness of our method. The ReLU and Exponential functions achieve slightly better results. In this paper, use Identity(-) as default for simplicity.
Table 10: Ablation the impact of different kernel functions based on maLine-Swin--
Kernel Function (6-) Identity(()
ReLU() LeakyReLU(-) Exponential(-)
Acc.
82.4
82.5
82.3
82.5
Conclusion
In this paper, shed some light the core factors leading to the performance gap between linear and Softmax attention. We identify and validate two fundamental disparities between these two attention paradigms: injective property and local modeling capability. Injectivity implies that the attention function assigns distinct attention scores to queries with varying semantics, reflecting the ability distinguish different semantics. Using different kernel functions, linear attention's ''s non-injectivity results in various semantic confusions. Furthermore, despite being recognized for their robust long-range modeling capability, attention mechanisms heavily depend on effective local modeling for impressive results. Thorough empirical validation unequivocally supports our analyses. Our findings also demonstrate that with the above two properties, linear attention can outperform Softmax attention with lower computation complexity.
Acknowledgement
This work is supported in part by the National Key R&D Program of China (0222))114903),
10

---

References
[1] Daniel Bolya, Cheng- Yang Fu, Xiaoliang Dai, Peizhao Zhang, and Judy Hoffman. Hydra attention: Efficient attention with many heads. In ECCVW, 2022. 10
[2] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In ECCV, 2020. 1,
[3] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreca Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. ICLR, 2021. 2,
[4] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In CVPRW, 2020. 7
[5] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. CVPR, 2009. 5,
[6] Xiaoyi Dong. Jianmin Bao, Dongdong Chen, Weiming Zhang, Nenghai Yu, Lu Yuan, Dong Chen, and Baining Guo. Cswin transformer: general vision transformer backbone with cross-shaped windows. In CVPR, 2022. 1, 7, 8
[7] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021.
1.2
[8] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:23/2.00752 2023. 3
[9] Dongchen Han, Xuran Pan, Yizeng Han, Shiji Song, and Gao Huang. Flatten transformer: Vision transformer using focused linear attention. In ICCV, 2023. 2,5,5, 10
[10] Dongchen Han, Ziyi Wang. Zhuofan Xia, Yizeng Han, Yifan Pu, Chunjiang Ge, Jun Song, Shiji Song, Bo Zheng, and Gao Huang. Demystify mamba in vision: A linear attention perspective. In NeurIPS, 2024.
[11] Dongchen Han, Tianzhu Ye, Yizeng Han, Zhuofan Xia, Shiji Song, and Gao Huang. Agent attention: On the integration of softmax and linear attention. In ECCV, 2024. 2
[12] Yizeng Han, Dongchen Han, Zeyu Liu, Yulin Wang, Xuran Pan, Yifan Pu, Chao Deng, Junlan Feng, Shiji Song, and Gao Huang. Dynamic perceiver for efficient visual recognition. In ICCV, 2023.
[13] Ali Hassani and Humphrey Shi. Dilated neighborhood attention transformer. arXiv preprint arXiv:2209.1500 15001, 2022.
[14] Ali Hassani, Steven Walton, Jiachen Li, Shen Li, and Humphrey Shi. Neighborhood attention transformer. CVPR, 2023. 2,
[15] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers mns: Fast autoregressive transformers with linear attention. In ICMI., 2020. 4
[16] Alexander Kirillov, Ross Girshick, Kaiming He, and Piotr Dollár. Panoptic feature pyramid networks. In CVPR, 2019. 10, 17
[17] Yanghao Li, Chao- Yuan Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer. Mvitv2: Improved multiscale vision transformers for classification and detection. In CVPR, 2022. 8
[18] Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. ECCV, 2014. 7, 15
11

---

[19] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows, In ICCV, 2021.
2, 8, 9, 14, 16
[20] Zhuang Liu, Hanzi Mao, Chao- Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In CVPR, 2022. 8
[21] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In ICLR, 2018. 7
[22] Jiachen Lu, Jinghan Yao, Junge Zhang, Xiatian Zhu, Hang Xu, Weiguo Gao, Chunjing Xu, Tao Xiang, and Li Zhang. Soft: Softmax-free transformer with linear complexity. In NeurIPS, 2021.
2
[23] Zanlin Ni, Yulin Wang, Renping Zhou, Jiayi Guo, Jinyi Hu, Zhiyuan Liu, Shiji Song, Yuan Yao, and Gao Huang. Revisiting von-autoregressive transformers for efficient image synthesis. In CVPR, 2024.
[24] Zanlin Ni, Yulin Wang, Renping Zhou, Rui Lu, Jiayi Guo, Jinyi Hu, Zhiyuan Liu, Yuan Yao, and Gao Huang. Adanat: Exploring adaptive policy for ECCV, 2024.
image generation. In
[25] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 1992. 7
[26] Zhen Qin, Xiaodong Han, Weixuan Sun, Dongxu Li, Lingpeng Kong, Nick Barnes, and Yiran Zhong. The devil in linear transformer. arXiv preprint arXiv:2210. 100400000, 2022. 2
[27] Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong, cosformer: Rethinking softmax in attention. In ICLR, 2022.
2, 4,
[28] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention:
Attention with linear complexities. WACV, 2021. 2, 10
[29]
Weixuan Sun, Zhen Qin, Hui Deng, Jianyuan Wang. Yi Zhang, Kaihao Zhang, Nick Barnes, Stan Birchfield, Lingpeng Kong, and Yiran Zhong. Vicinity vision transformer. TPAMI, 2023.
[30] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In ICML, 2021. 1, 9,
[31] Hugo Touvron, Matthieu Cord, Alexandre Sablayrolles, Gabriel Synnaeve, and Hervé Jégou. Going deeper with image transformers. In ICCV, 2021. 8
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NewrIPS, 2017. 1, 1,
[33] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pyramid vision transformer: A versatile backbone for dense prediction without convolutions. In ICCV, 2021. 1, 9, 16
[34] Wenhai Wang, Enze Xic, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pvt v2: Improved baselines with pyramid vision transformer. Computational Visual Media, 2022. 2,
[35] Zhuofan Xia, Dongchen Han, Yizeng Han, Xuran Pan, Shiji Song, and Gao Huang. Gsva: Generalized segmentation via multimodal large language models. In CVPR, 2024.
[36] Zhuofan Xia, Xuran Pan, Shiji Song. Li Erran Li, and Gao Huang. Vision transformer with deformable attention. In CVPR, 2022. 1,2
[37] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun, Unified perceptual parsing for scene understanding. In ECCV, 2018. 10
12

---

[38] Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty. Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer. A nyström-baser algorithm for approximating self-attention.
In AAAI, 2021. 2
[39] Jianwei Yang, Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao. Focal self-attention for local-global interactions in vision transformers. In NewrIPS, 2021.
8
[40] Haoran You, Yunyang Xiong, Xiaoliang Dai, Bichen Wu, Peizhao Zhang, Haoqi Fan, Peter Vajda, and Yingyan Celine Lin. Castling-vit: Compressing self-attention via switching towards linear-angular attention vision transformer inference. In CVPR, 2023. 4, 10
[41] Sangdoo Yun, Dongyoon Han, Scong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In ICCV, 2019.
[42] Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In ICLR, 2018.
[43] Zhum Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang. Random erasing data augmentation. In AAAI, 2020. 7
[44] Bolei Zhou, Hang Zhao, Xavier Puig, Tete Xiao, Sanja Fidler, Adela Barriuso, and Antonio Torralba. Semantic understanding of scenes through the ade20k dataset. IJCV, 2019. 7, 15
[45] Lei Zhu, Xinjiang Wang, Zhanghan Ke. Wayne Zhang, and Rynson WH Lau, Biformer: Vision transformer with bi-level routing attention. In CVPR, 2023. 1.2
13

---

Appendix
A
Mathematical Proof
This section offers mathematical proofs for the three propositions outlined in the main paper.
A.1 Proof of Proposition
Proposition 1 (Softmax attention is injective) Given K E RNxd with rank(K) = d and rank([K, INxil) = d + p.q R p # q, we have Sk(p) # Sk(g).
Proof. To arrive at a contradiction, assume p.q E R . q, s.t. Sk(p) = Sk(g). Then we have:
exp(g T Kj)
[exp(p) T Ki),".. .. ,xp(pp' T KN)]]
[exp(1 K1), .. , exp(a Kx)] T
(7)
exp(p T Kj)
j= exp(2 Kj)
+ KI .p p_KN]+ +c= Ki .q KN cc In
(8)
Σラ= exp(p
Consider the following two cases:
1. c= O. Then eq. (8) + p K Kj + K(p - 9) 00. As rank(K) = d. we have p = which contradicts the assumption that p +
2. c A O. Then eq. (8) = Kj
K c= Kj + -
1) INXI, which contradicts the fact that rank([K, xx)) = d + and equation Kr 1Nx1 does not have a solution.
Therefore, we have KJ (p -g//-//c->>>>> K(p
Both cases arrive at a contradiction, which proves the original proposition.
Notably, the two assumptions rank(K) d and rank (K, 1,x I]) d + 1 are easy to satisfy in real models. In practice, the number of tokens N is usually much larger than head dimension d. For instance, in the first stage of Swin Transformer [19], N = 562 = 3136 and d 32. Therefore, have E Nxd N > d. If raak(K) K) < d, indicates that the N key tokens lie in a low-dimension subspace of TRd. If rank( [K, xxl)
+ 1, it means that the N key tokens are in a hyperplane of IRd Given that N is much greater than d, it is highly likely that the N key tokens have various directions in Rd instead of locating in low- di-dimension subspace or hyperplane. In this case, it holds that rank K) d and rank([K, 1 1xx1)) d 1.
A.2 Proof of Proposition 2
Lemma 1 (Existence of collinear features in linear attention) Let Φ Rdd + Rdd be a continuous injective function. 3p. 9 E Rd p # q, 3a E RR, + 0, s.t. x(g) = ad(p).
|o( U = f d(x) + 0, E (R) S s= fo ||||| 1, E Rd). d is a continuous function, so f is continuous on U. & is an injective function, so it has no more than one zero point. Therefore, U Fd or {2 # ro, E Ed is an open subset of Rd. where xp is the zero point of 6. f(U) E 5 is not open set, every point of f(U) is not interior point.
U Proof. Let U 5, fzx = o(z)
Assume f is injective. Then f + S is a continuous injective map. According to Brouwer Invariance of Domain Theorem, U is an open set + S(U) is also open, which contradicts the fact that f(U) is not an open set.
Therefore, f is not injective.
3p, Rd . g. s.t. f(p) f(g)-
p(g) = |((
(()) e a = ||ő(g)] [[(pp]
[](()] #0.
(9)
14

---

Proposition 2 (Linear attention is not injective) Let Ø Rd + R be continuous function. p Rd P & q, s.t. Lx(p) Lg).).
Proof. Consider the following two cases:
1. é is not injective. 3p, E R p + q, s.t. x(p) Q(4) Lk(p) -L<(1)
2. @ is injective. Lemma = 3p, q E Rd p + q, 3a E R, + 0, s.t. x(9) aá(p))
axp(p) T ((1)
ed(p) (((p)(((K)) ((KN)
= Lk(g))
E==ı ap(p)) o0 Kÿ)
Σ ap(p) (T((KK))))
(10)
<(p) T ((K))
<()) 00 (KN)
Lk(p).
Σ <(p) [((()())))))))))))){{)))
Σ d()) T (K₁,)
A.3 Proof of Proposition 3
Proposition (InLine attention is injective) Ler R + R be an injective map. Given K Rxd with rank (b( (K) =d and rank([((K), 1 (xxx))===-1... Vp, E Rd 4 = lnLk(p) # InLk(g).
Proof. Assume p Rd , # q. s.t. InLK (p) = lnLK(q)) p q <p) + Q(g).
+ [ (K)), ... Ap)) (lP)))))K))) d(KN)] cc= [d(g] (K1). ... (l) T [(K)]]
(lg) ((K))
(()) ((1)) Σ N
1
N
(11)
The subsequent proof mirrors Proposition 1.
Similar to the analysis in Sec. A.I, rank(o(K)) d and rank([p(K), 1xx1)) d+ 1 are easy to satisfy.
B Complete Experimental Results
We provide complete experimental results on ImageNet- 1K classification [5], COCO object de-
tection [18], ADE20K semantic segmentation [44] in Tab. 11, Tab. 12 and Tab. 13. The results demonstrate that InLine attention module consistently outperforms Softmax counterparts across all settings, strongly supporting our analyses and fully validating its effectiveness.
C Model Architectures
We summarize the detailed architectures of four Transformer models used in the main paper, including InLine-DeiT, InLine-PVT, InLine-Swin and InLine-CSwin in 18.1.4
D Limitations
In this paper, we shed some light on the core factors leading to the performance gap between linear and Softmax attention. We identify and validate two fundamental and essential disparities between these two attention paradigms: injective property and local modeling capability. Firstly, we prove that linear attention is not injective, which is prone to assign identical attention weights to different query vectors, thus adding to severe semantic confusion problem. Secondly, we confirm that effective local modeling is important for the success of Softmax attention, in which linear attention falls short. The aforementioned two essential differences significantly contribute to the disparities between these two attention paradigms, which is unequivocally proved by our thorough empirical validation in the paper. However, there may be other differences between Softmax and linear attention, and this paper not exhaustive.
15

---

Table 11: Comparison with baseline models on ImageNet- K.
Method
Reso
#Params
FLOPs
Top-1
DeïT-T [30]
224"
5.7M
1.2G
72.2
InLine-DeiT-T
224"
6.5M
1.1G
74.5 (+2.3)
DeïT-S
224"
22.1M
4.6G
79.8
InLine-DeiT-S
224"
16.7M
5.0G
80.2 (+0.44
DeïT-B
224
86.6M
17.6G
81.8
InLine-DeiT-B
4482
23.8M
17.2G
82.3 (+0.5)
PVT-T [33]
224
13.2M
1.9G
75.1
InLine-PVT-T
224"
12.0M
2.0G
78.2 (+3.1)
PVT-S
224
24.5M
3.8G
79.8
InLine-PVT-S
224
21.6M
3.9G
82.0 (+2.2)
PVT-M
224
44.2M
6.7G
81.2
InLine-PVT-M
224
37.6M
6.9G
83.2 (+2.0)
PVT-L
224
61.4M
9.8G
81.7
InLine-PVT-L
224
50.2M
10.2G
83.6
Swin-T [19]
2242
29M
4.5G
81.3
InLine-Swin-T
224
30M
4.5G
82.4 (+1.1)
Swin-S
224"
50M
8.7G
83.0
InLine-Swin-S
224
50M
8.7G
83.6 (+0.6)
Swin-B
224
88M
15.4G
83.5
InLine-Swin-B
224
88M
15.4G
84.1 (+0.6)
Swin-B
3842
88M
47.0G
84.5
InLine-Swin-B
3842
88M
45.2G
85.0 (+0.5)
Table 12: Results COCO dataset. The FLOPs are computed with an input resolution of 1280x800.
(a) Mask R-CNN Object Detection on COCO
Method
FLOPs
Sch.
AP
AP
AP
ApM
APm
APM
75
PęT-T
240G
1x
36.7
59.2
39.3
35.1
56.7
37.3
InLine-PVT-T
211G
1x
40.2
62.7
43.8
37.7
59.7
40.4
PVT-S
305G
1x
40.4
62.9
43.8
37.8
60.1
40.3
inLine-PVT-S
250G
1x
43.4
66.4
47.1
40.1
63.1
43.3
PVT-M
392G
1x
42.0
64.4
45.6
39.0
61.6
42.1
InLine-PVT-M.
310G
1x
44.0
66.4
48.0
40.3
63.4
43.5
PVT-L
494G
1x
42.9
65.0
46.6
39.5
61.9
42.5
InLine-PVT:
377G
1x
45.4
67.6
49.7
41.4
64.7
44.6
(b) Cascade Mask R-CNN Object Detection COCO
Method
FLOPs
Sch.
APb
AP
30
AP
Apm
APm
APM
Swin-S
837G
3x
51.9
70.7
56.3
45.0
68.2
48.8
InL-in-Swin-S
835G
3x
52.4
71.0
56.9
45.4
68.8
49.6
Swin-B
981G
3x
51.9
70.5
56.4
45.0
68.1
48.9
Liine-Swin- B
978G
3x
52.6
71.0
57.0
45.4
68.5
49.3
16

---

Table 13: Results of semantic segmentation. The FLOPs are computed over encoders and decoders with input image at the resolution of 512x2048. S-FPN is short for SemanticFPN [16] model.
Semantic Segmentation on ADE20K
Backbone
Method
FLOPs
#Params
mIoU
mAcc
PVT-T
S-FPN
158G
17M
36.57
46.72
InLine-PVTTT
S-FPN
127G
16M
39.16
50.63
PVT-S
S-FPN
225G
28M
41.95
53.02
InLine-PVT-S
S-FPN
168G
25M
42.93
54.58
PVT-M
S-FPN
315G
48M
42.91
53.80
InLine-PVT-M
S-FPN
229G
41M
44.59
57.20
PVT-L
S-FPN
420G
65M
43.49
54.62
InLine-PVT-L
S-FPN
298G
55M
44.71
57.17
Swin-T
UperNet
945G
60M
44.51
55.61
InLine-Swin-T
UperNet
941G
61M
45.57
57.60
Swin-S
UperNet
1038G
81M
47.64
58.78
MaLine-Swin-
UperNet
1035G
81M
48.59
60.73
Swin-B
UperNet
1188G
121M
48.13
59.13
Inl.ne-SSwn-B
UperNet
1183G
122M
49.10
60.57
Table 14: Architectures of InLine-Deit models.
Inl Dee-i
Ini-in--eiT-B
InLine Block
DefT Block
InLine Block
DeiT Block
InLine Block
DeiT Block
18 18
28 28
dim
x 12
None
dim 320
12
None
dim 384
12
None
head 6
head 10
head 12
Table 15: Architectures InLine-PVT models (Partl).
PVT-T
Inl-ine-PVT.S
stage
output
InLine Block
PVT Block
InLine Block
Block
Conv4x4, stridem4, 64,
56 56
res1
56 56
dim 61
x
None
dim
X3
Nonc
head
head
Conv2x2, stride=2, 128, LN
win 28 x 28
win 28 28
res2
28
dim 128
x
None
dit 128
x3
None
head
head 2
Cony2x2, stridl==2, 320,
win 14 320 head
win 14 14 dim
x
None
None
head
Conv2x2, stridew2, 512, LN
win 7
win 7 7 None
res4
7
dim 512
x2
dim 512
x3
Nonc
head
head 8
17

---

Table 16: Architectures InLine-PVT models (Part2).
InLine-PVT-M
InLine-PVT-L.
stage
output
InLine Block
PVT
InLine Block
PVT Block
Conv4x4, stride=4, LN
win 56 x
win 56 x 56
resl
56 x 56
dim 64
x3
None
dim 64
X
None
head 1
head
Conv2x2, stride=2, 128, LN
win 28 x
win 28 x
dim
dim 128
head 2
head
Conv2x2, stride=2,
win 141 14
win 14
1083
14 x 14
dim 320
18
None
dim 320
x27
None
head
head 5
Conv2x2, stride22, 512, LN
win X
win 7x7
rew4
7 X
dim 512
x3
None
dim 512
x3
None
head 8
head
Table 17: Architectures of InLine-Swii models.
InLine-Swin-T
InLine-Swin-S
InLine-Swin-B
stage
outpuu
InLine Block
Swin Block
InLine Block
Swin Block
InLine Block
Swin Block
LN
LN
concat
LN
win 56 56
win 56 56
win 56 56
resl
56 56
dim 96
x
None
dim head 3
x
None
dim 128 x
None
head
head
2, 192, LN
2, 192, LN
256, LN
win 28
win 28
win 28 28
res2
28 x 28
dim 192
x
None
dim 192
x
None
dim 256
x
None
head
head 6
head
concat 2, 384, I.N
2, 384, LN
concat 512, LN
win 7x
win 7x
win 14x
win 7x
res3
14 14
None
dim 384
X
None
dim 384
x18
dim 512
x dim 512
x16
head 12
head 12
head 12
head 12
concat 2, 768. LN
concat 2. 768, LN
concat 2,
1024, LN
win 7x 7
win 7x
win 7
res4
x
None
dim 768
x2
None
dim 768
x2
None
dim 1024
x2
head 24
head 24
head 24
18

---

Table 18: Architectures of InLine-CSwin models.
InLine CSwin-S
InLine CSwin-B
stage output
InLine Block
CSwin Block
InLine Block
CSwin Block
InLine Block
CSwin Block
Conv7x7, stride=,, 64,
Conv7x7, stride=4, 64, LN
Conv7x7, stride=4, 96, LN
56
win
resl 56 56
dim
None
x
None
dim
x3
None
head
head
head
Conv3x3, stride=2, 128, LN
Conv3x3, stride=2, 128, LN
Conv3x3, stride=2,
win 28 28
win 28
win 28
res2. 28 28
dim 128
x4
None
din 128
x
None
dim 192 head
x
None
head
head
Conv3x3, stride=2, 256, LN
Conv3x3, stride=2, 256, LN
Conv3x3, stride=2. 384, LN
win 7 14
win 7x 14
win 7x 14
res3 14 14
None
dim 256
x88
None
dim 256
29
None
din 384
x
head
head 8
head 16
Conv3x3, stride=2, 512, LN
Conv3x3, stride=2, 512, LN
Conv3x3, stride=2, 768, LN
win 7
win 7x
win 7 7
None
dim 512
dim 512
None
dim 768
16
head
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in Sec. D.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

Justification:
The paper provides full set of assumptions and complete, correct proof for the theoretical results, i.e., the propositions, in Sec. A of the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper fully discloses the information needed to reproduce the main experimental results of the paper in Sec. 5.2.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
21

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is available https///gghhab..oommm//ppoooo//h
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines pettps://niiee cc/
publ / guides/ CodeSulom s. onPoli ccy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. cc/
ctaaps.ccpublic..oc pttpppullcccccc heabbiccggiids CooeeeeeeSSeeeeee Sumeeuubmmii.. cessooPolllo ooyicyyyyyy....cc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies all the training and test details in Sec. 5 and Sec. 5.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not reported because it would be too computationally expensive.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
22

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide information on the computer resources in Sec. 5.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttp://////uis.eeeeeee
Answer: [Yes]
Justification: The research conducted in the paper conform with the NeurIPS Code of Ethics, in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work focuses attention mechanism and has direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
23

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks it is foundational research focusing attention paradigm.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use all assets properly according to their licenses, and give credits the creators in Sec. 5.2.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use package should be provided. For popular datasets, papers rswi thoode. com / da sets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
24

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "IVts7Q1tYW", "reviewer": "Reviewer_TKLm", "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.", "questions": "1) This is not the first paper discussing the locality problem of linear attention. Check [1] for more details. \n2) 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.\n\n[1] Qin et al., 2022; The Devil in Linear Transformer.", "limitations": "The authors discussed the limitations of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The analysis of injectivity and locality includes both theoretical understanding and empirical evidence;\n2) 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;\n2) The motivation and formulation of InLine are very similar to FLatten, and doesn’t show substantial quality gain to FLatten;\n3) It would be great to have language modeling experiments;", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would first like to express our appreciation for your time and insightful comments. Please find our response to your concerns in the following:\n\n---\n\n**1. The locality problem and related work.**\n\nThanks for pointing out this important related work [1]. Here, we offer clarification on the relationship between this study and our work.\n\n***Firstly**, our work verifies the vital importance of the injective property of attention mechanism.* This unique and valuable perspective helps us develop the extremely simple yet effective injective linear attention.\n\n***Secondly**, while our work shares some similar analyses on the locality problem with [1], it has fundamental distinctions:*\n\n- ***We thoroughly validate the crucial role of local modeling in attention mechanism, while [1] mainly focuses on identifying differences.*** There could be many different behaviors between Softmax and linear attention, but a large number of them may not be the key disparities. Therefore, our study conducts a series of experiments in Fig. 3, 4 and Table. 2, 4 to fully validate that: (1) Softmax attention's effectiveness depends significantly on robust local modeling. (2) Varied local priors contribute substantially to the performance gap between Softmax and linear attention. In contrast, [1] observes that Softmax attention is more concentrated locally than linear attention (see its Fig. 2), but it does not verify whether this is a key factor leading to the performance gap between the two.\n\n- ***The design proposed in our paper is more effective than [1].*** To enhance locality, [1] proposes DiagAttention, which restricts each token's receptive field to its local block. This approach resembles the window attention in Table 4 (left), which shows little improvement (window=$14^2$, acc=80.4) compared to vanilla global linear attention (acc=80.2). In contrast, our design boosts accuracy significantly from 80.2 to 82.4, fully unleashing the power of global linear attention. Additionally, we offer a comparison between our InLine model and TransNormer proposed in [1] under Swin-T structure. Our InLine model achieves better results.\n\n  |   Method    | #Params | FLOPs | Acc. |\n  | :---------: | :-----: | :---: | :--: |\n  | TransNormer |   30M   | 4.5G  | 79.9 |\n  |   InLine    |   30M   | 4.5G  | 82.4 |\n\n- Thanks for pointing this out again. ***We will include discussion and give more credits to this work in the revised manuscript.***\n\n[1] Qin et al., 2022; The Devil in Linear Transformer.\n\n---\n\n**2. The similarities and differences compared to FLatten.**\n\nThanks for your valuable comment.\n\n***Firstly**, removing the division operation can make FLatten injective but hinders performance.* Without the division operation, FLatten can not ensure the attention weights sum up to 1, which is important for stabilizing the model. Therefore, when the division operation is removed from FLatten-Swin-T, the model experiences an accuracy drop of 0.2.\n\n***Secondly**, we offer a detailed analysis of the similarities and differences with FLatten.*\n\n- ***Our work and FLatten are largely orthogonal.*** Our work analyzes the injectivity and locality of Softmax and linear attention, while FLatten discusses the focus ability and feature diversity of linear attention. Furthermore, we present subtraction normalization to make linear attention injective, \n  $$\n  \\rm{InL_K}(Q_i)=\\left[\\phi(Q_i)^\\top \\phi(K_1), \\cdots, \\phi(Q_i)^\\top \\phi(K_N)\\right]^\\top-\\frac{1}{N} \\sum_{s=1}^N \\phi(Q_i)^\\top \\phi(K_s)+\\frac{1}{N},\n  $$\n  while FLatten introduces a specific mapping function $\\phi=\\frac{||x||}{||x^{**p}||}x^{**p}$ to sharpen attention distribution. These methods are orthogonal and can be employed together.\n\n- ***The findings of our paper are more fundamental***, and could be more beneficial for the community in designing effective linear attention patterns. As discussed in our paper (L145-L152), the focus ability identified in FLatten can be viewed as a special case of non-injectivity and confusion problem. And our studies on locality can also explain why dwconv improves FLatten.\n\n- ***Our InLine attention is more effective and efficient than FLatten.*** The proposed InLine attention is extremely simple yet effective, yielding both faster speed and higher accuracy compared to FLatten. For example, a single InLine attention block is 1.8x faster than a FLatten block, and InLine-PVT-T achieves 0.4 accuracy gain with 1.2x speed up than FLatten-PVT-T. These results are tested on a single RTX3090 GPU.\n\n---\n\n**3. Language modeling experiments.**\n\nPlease refer to our general response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t3M8za2gM5", "reviewer": "Reviewer_My8Q", "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.", "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.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThis 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.\n\n2.\tTo 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).\n\n3.\tThe 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. \n\n2. 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.\n\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would first like to express our appreciation for your time and insightful comments. Please find our response to your concerns in the following:\n\n---\n\n**1. The performance of InLine models and comparison with related works.**\n\nThanks for the valuable comment. \n\n***Firstly, under fair comparison, the improvement of our method is significant and consistent.***\n\n- We propose injective linear attention and local attention residual to address two core limitations of linear attention. The effectiveness of these two designs is validated in Table 3 and Table 4 of our paper. Table 3 shows that injective linear attention achieves significant ***accuracy gains of 2.5 and 9.8*** compared to vanilla linear attention. Table 4 shows that local attention residual further improves model performance ***from 80.2 to 82.4.*** We kindly argue that these improvements are significant and remarkable.\n- Our InLine attention module ***significantly improves performance*** across four representative architectures: ***DeiT, PVT, Swin and CSwin***. As shown in Table 5 and Table 6 of our paper, simply applying our InLine attention module to these four models leads to obvious accuracy gains. For example, InLine-Swin-S outperforms Swin-B with 57% of the Params and 56% of the FLOPs. These results demonstrate the superiority of InLine attention as an effective alternative to the widely used Softmax attention.\n\n***Secondly, we offer additional comparison with more competitive related works like VVT.***\n\n- The primary focus of our paper is to demystify the limitations of linear attention, rather than achieving SOTA results. Therefore, we mainly focus on building our InLine models under the four simple baseline models. In contrast, VVT utilizes advance macro designs like ConvFFN to achieve more competitive results. For a fair comparison with VVT, we employ similar advance designs and provide the results below. \n\n  | Model  | #Params | FLOPs | Acc. |\n  | :----: | :-----: | :---: | :--: |\n  | VVT-L  |  61.8M  | 10.8G | 84.1 |\n  | InLine |  51.1M  | 6.8G  | 84.2 |\n\n  It is shown that ***our InLine model outperforms VVT with 20% fewer Params and 40% fewer FLOPs.***\n\n- Additionally, since our InLine model is extremely simple and effective, it delivers much better speed-accuracy trade-off than other competitive works. For example, as depicted in Fig. 1 of ***the PDF in general response***, our simple ***InLine-Swin model shows 1.8x-2.5x faster inference speed than VVT***, while achieving comparable accuracy. Speed is tested on a single RTX3090 GPU.\n\n- ***We will give more credits to these related works and include comparison in the revised manuscript.***\n\n---\n\n**2. The analysis of local modeling capability.**\n\nThanks for your insightful question. We offer clarification on the analysis of local modeling capability.\n\n- As shown in Eq. 6 of our paper, the local attention residual proposed in our paper is $\\sum_{j=1}^9 r_j V_j^{N(i)}$, where $N(i)$ is the 3×3 neighborhood of $V_i$ and $V_j^{N(i)}$ represents the value token in this neighborhood, $j=1,\\cdots,9$. Therefore, the attention local attention residual is not a simply residual $rV_i$ since it contains local property. ***The local property of the attention residual is beneficial for InLine attention, rather than the residual property.*** We offer additional experiments to further validate this.\n\n- ***Firstly, we replace the local residual with vanilla residual $rV_i$ and provide the results below.*** The window size is fixed as global, i.e. $56^2$.\n\n  |          Method           | Window | #Params | FLOPs | Acc. |\n  | :-----------------------: | :----: | :-----: | :---: | :--: |\n  |    InLine w/o residual    | $56^2$ |   30M   | 4.5G  | 80.2 |\n  | InLine + vanilla residual | $56^2$ |   30M   | 4.5G  | 80.2 |\n  |  InLine + local residual  | $56^2$ |   30M   | 4.5G  | 82.4 |\n\n  It can be seen that adding vanilla residual can not benefit InLine model and it achieves the same result as no residual. This indicates that the residual property is not the core of the proposed attention residual.\n\n- ***Secondly, we provide further ablation studies on $N(i)$.*** In our original design,  $N(i)$ is the 3×3 neighborhood of $V_i$. Here, we define $D_kN(i)$ as the dilated 3×3 neighborhood of $V_i$ with dilation $k$, where the concept \"dilation\" is the same as in dilated convolution. Thus we have $D_1N(i)=N(i)$. As $k$ enlarges, the local property of $\\sum_{j=1}^9 r_j V_j^{D_kN(i)}$ is weakened. \n\n  |     Model     | $k$  | #Params | FLOPs | Acc. |\n  | :-----------: | :--: | :-----: | :---: | :--: |\n  | InLine-Swin-T |  1   |   30M   | 4.5G  | 82.4 |\n  | InLine-Swin-T |  2   |   30M   | 4.5G  | 81.7 |\n  | InLine-Swin-T |  3   |   30M   | 4.5G  | 80.8 |\n  | InLine-Swin-T |  4   |   30M   | 4.5G  | 80.6 |\n\n  As depicted in the above table, the model performance decreases significantly as $k$ enlarges, proving that local property is the real factor benefiting InLine model.\n\n- These results will be included in the revised version to make the analysis of local modeling capability more solid. Thanks again for your valuable question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MJwfxuSNER", "reviewer": "Reviewer_3cj2", "summary": "This paper invetigate the linear attention in the Vision task", "questions": "1. The source code is not avaliable, the reproductability is unclear at this time.\n\n2. how this linear attetnion compare with Vision Mamba since Mamba is efficient.\n\n3. The experimental results are mainly on CV domain, is this algorithm adaptive to NLP or time series domain?", "limitations": "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, "strengths": "1. The paper is well written, the motivation is clear.\n\n2. 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.\n\n3. The experimental results are good.", "weaknesses": "1. The source code is not avaliable, the reproductability is unclear at this time.\n\n2. how this linear attetnion compare with Vision Mamba since Mamba is efficient.\n\n3. The experimental results are mainly on CV domain, is this algorithm adaptive to NLP or time series domain?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would first like to express our appreciation for your time and insightful comments. Please find our response to your concerns in the following:\n\n---\n\n**1. The source code.**\n\n- ***Firstly, we provide the Pytorch-style pseudo code of our InLine attention module below.*** It can be seen that the proposed method is very simple and easy to implement.\n\n  ```python\n  # b: batch size;  n: sequence length;  d: head dimension\n  \n  # q: query,\t\tshape: (b, num_heads, n, d)\n  # k: key,\t\tshape: (b, num_heads, n, d)\n  # v: value,\t\tshape: (b, num_heads, n, d)\n  \n  # Eq. 5 of our paper\n  o = q @ (k.transpose(2, 3) @ v) - (q @ k.transpose(2, 3).sum(dim=2) - 1) * v.mean(dim=2)\n  # Eq. 6 of our paper\n  o = o + local_residual_aggre(v)\n  \n  # o: output,\tshape: (b, num_heads, n, d)\n  ```\n\n- ***Secondly, we will provide the full source code to promote reproducibility if this manuscript is accepted.***\n\n---\n\n**2. Comparison with vision Mamba models.**\n\nThanks for your valuable comment. Here, we provide additional comparison with vision Mamba models.\n\n- ***We offer comparison in terms of params, FLOPs and accuracy in the table below.***\n\n  |       Model        | #Params |   FLOPs   |   Acc.   |\n  | :----------------: | :-----: | :-------: | :------: |\n  |       Vim-S        |   26M   |   5.1G    |   80.3   |\n  |     LocalVim-S     |   28M   |   4.8G    |   81.2   |\n  |   PlainMamba-L2    |   25M   |   8.1G    |   81.6   |\n  | EfficientVMamba-B  |   33M   |   4.0G    |   81.8   |\n  |      VMamba-T      |   31M   |   4.9G    |   82.5   |\n  |   LocalVMamba-T    |   26M   |   5.7G    |   82.7   |\n  | **InLine-CSwin-T** | **21M** | **4.3G**  | **83.2** |\n  |                    |         |           |          |\n  |     Mamba2D-B      |   94M   |     -     |   83.0   |\n  |      VMamba-B      |   89M   |   15.4G   |   83.9   |\n  | **InLine-CSwin-B** | **73M** | **14.9G** | **84.5** |\n\n  As depicted in the above table, our InLine model surpasses various vision Mamba designs without bells and whistles.\n\n- ***Furthermore, as our InLine attention is extremely simple, it achieves much faster inference speed than vision Mamba models.*** Accuracy-runtime comparison is provided ***in the PDF in general response***. The results demonstrate that our InLine model is ***4.6x, 6.3x faster*** than LocalVMamba and PlainMamba models respectively, while achieving comparable performance. Compared to the highly optimized VMamba model, our model also achieves 1.4x speedup and 0.2 accuracy gain.\n\n---\n\n**3. Is this algorithm adaptive to NLP or time series domain?**\n\nOur method can be applied to NLP and time series domain. Please refer to our general response for the detailed discussion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "InnEihEBiA", "reviewer": "Reviewer_yvdC", "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.", "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?\n\n[1] The Devil in Linear Transformer\n\n[2] Linear Log-Normal Attention with Unbiased Concentration", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a solid theoretical analysis explaining the performance gap between linear and Softmax attention, focusing on injectivity and local modeling capabilities.\n- 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.\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would first like to express our appreciation for your time and insightful comments. Please find our response to your concerns in the following:\n\n---\n\n**1. Novelty and contribution.**\n\nThanks for your valuable comment. The novelty and contribution of our work can be summarized as follows:\n\n- We identify an important property of attention mechanism, ***injectivity***, which has not been explored in literature. With both theoretical proof and experimental verification, we show that injectivity significantly contributes to the performance gap between Softmax and linear attention.\n- We thoroughly validate the crucial role of ***local modeling*** in attention mechanism through a series of experiments.\n- We propose a novel ***subtraction normalization*** method to achieve injectivity in linear attention, significantly improving performance with no extra FLOPs.\n- We present ***InLine attention module***, a simple, effective and efficient alternative to the commonly adopted Softmax attention. Extensive experiments fully validate the superiority of our design over Softmax attention.\n\n---\n\n**2. The locality problem and related work.**\n\nThanks for highlighting this important related work [1]. While our work shares some similar analyses with [1], it has fundamental distinctions:\n\n- ***We thoroughly validate the crucial role of local modeling in attention mechanism, while [1] mainly focuses on identifying differences.*** There could be many different behaviors between Softmax and linear attention, but a large number of them may not be the key disparities. Therefore, our study conducts a series of experiments in Fig. 3, 4 and Table. 2, 4 to fully validate that: (1) Softmax attention's effectiveness depends significantly on robust local modeling. (2) Varied local priors contribute substantially to the performance gap between Softmax and linear attention. In contrast, [1] observes that Softmax attention is more concentrated locally than linear attention (see its Fig. 2), but it does not verify whether this is a key factor leading to the performance gap between the two.\n\n- ***The design proposed in our paper is more effective than [1].*** To enhance locality, [1] proposes DiagAttention, which restricts each token's receptive field to its local block. This approach resembles the window attention in Table 4 (left), which shows little improvement (window=$14^2$, acc=80.4) compared to vanilla global linear attention (acc=80.2). In contrast, our design boosts accuracy significantly from 80.2 to 82.4, fully unleashing the power of global linear attention. Additionally, we offer a comparison between our InLine model and TransNormer proposed in [1] under Swin-T structure. Our InLine model achieves better results.\n\n  |   Method    | #Params | FLOPs | Acc. |\n  | :---------: | :-----: | :---: | :--: |\n  | TransNormer |   30M   | 4.5G  | 79.9 |\n  |   InLine    |   30M   | 4.5G  | 82.4 |\n\n- Thanks for pointing this out again. ***We will include discussion and give more credits to this work in the revised manuscript.***\n\n[1] The Devil in Linear Transformer.\n\n---\n\n**3. Ablation on different kernel functions.**\n\nThanks for the insightful comment. We conduct additional ablation studies on different kernel functions $\\phi$ using InLine-Swin-T.\n\n| Kernel Function $\\phi$ | #Params | FLOPs | Acc. |\n| :--------------------: | :-----: | :---: | :--: |\n|        Identity        |   30M   | 4.5G  | 82.4 |\n|          ReLu          |   30M   | 4.5G  | 82.5 |\n|       LeakyReLu        |   30M   | 4.5G  | 82.3 |\n|      Exponential       |   30M   | 4.5G  | 82.5 |\n\nIt is shown that our InLine attention can effectively work with different kernel functions, further validating the effectiveness of our method. The ReLU and Exponential functions achieve similar results, slightly outperforming the Identity function. In our paper, we use Identity kernel function as default. Additionally, we will give more credits to [2] in the revised version.\n\n[2] Linear Log-Normal Attention with Unbiased Concentration\n\n---\n\n**4. Experiments on language models.**\n\nPlease refer to our general response.\n\n---\n\n**5. Negative attention scores.**\n\nThanks for the insightful question. We already provide a brief discussion on the non-negativity assurance in L260-L263 of our paper. Here, we offer detailed analyses and additional experiments to further clarify this interesting issue.\n\n- ***InLine attention does not ensure non-negative attention scores.*** As you pointed out, the subtraction normalization could possibly produce negative values, and we practically find that there do exist many negative attention scores in our InLine models.\n\n- ***These negative values do not impair the performance of InLine attention.*** We directly verify this with an ablation experiment, where we ensure all attention values to be non-negative by introducing additional normalization on $Q,K$. The results are provided below. \n\n  |           Method           | #Params | FLOPs | Acc. |\n  | :------------------------: | :-----: | :---: | :--: |\n  |       InLine-Swin-T        |   30M   | 4.5G  | 82.4 |\n  | InLine-Swin-T non-negative |   30M   | 4.5G  | 81.7 |\n\n  It can be seen that the additional non-negative assurance actually leads to notable performance drop. This suggests that negative values in InLine attention do not hinder performance and might even enhance the model.\n\n- ***Non-negativity is crucial for vanilla linear attention.*** As depicted in Table. 3 of our paper, unlike our InLine attention, vanilla linear attention fails to converge without non-negativity assurance. We attribute this to extreme non-injectivity and semantic confusion problem. For example, with Identity kernel function, vanilla linear attention is unable to distinguish completely opposite semantics, assigning identical attention scores to $q$ and $−q$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their insightful and valuable comments. 

We have carefully considered the reviewers' comments and provided additional clarification to address each concern. Here, we offer general responses to all reviewers on two key issues.

---

**1. Discussion with related works.**

We appreciate the reviewers for highlighting several important related works that we have overlooked. Detailed discussions with these studies are provided in separate responses to each reviewer. We will give more credits to these works and include the discussions in the revised manuscript.

---

**2. Applying InLine attention to language models.**

- The proposed injective linear attention can be applied to language models. Currently, our work mainly focuses on vision tasks since we follow the line of linear attention studies in vision [1,2,3,4]. However, we fully agree with the reviewers' comments that applying our method to language models can greatly improve its impact. Here, we provide detailed discussion on how to apply injective linear attention to language models.

- When applied to auto-regressive language models, our injective linear attention can naturally achieve parallel training and $\mathcal{O}(1)$ complexity (per token) inference. 

- ***Parallel training.***

  The Eq. 4 of our paper can be written in a two-step form as follows: 
  $$
  A=\phi(Q)\phi(K)^\top,\ \ \mathrm{InL}=A-(A\cdot1)\odot l+l,
  $$
  where $Q,K\in\mathbb{R}^{N\times d}$ are query and key, $A\in\mathbb{R}^{N\times N}$ represents the raw attention scores, and $1,l\in\mathbb{R}^{N\times 1}$ are vectors with all 1 elements and all $1/N$ elements, respectively. We could see that $(A\cdot1)\odot l\in\mathbb{R}^{N\times 1}$ denotes the row mean of $A$ and the above formulation is equivalent to Eq. 4. To apply InLine attention to language models, the only modification we need to make is applying the causal mask. To achieve this, the above equation is rewritten as:

  $$
  A=\phi(Q)\phi(K)^\top,\ \ \mathrm{InL}=(A-((A\odot M)\cdot1)\odot l+l)\odot M,
  $$
  where $M\in\mathbb{R}^{N\times N}$ is the casual mask, and $l\in\mathbb{R}^{N\times 1}$ is a vector whose $i$-th element is $1/i$. Similarly, $((A\odot M)\cdot1)\odot l\in\mathbb{R}^{N\times 1}$ is the row mean of the causal attention matrix $A\odot M$. In this way, the InLine attention map with causal relationship is obtained, and the output is $O=\mathrm{InL}\cdot V$.

- ***Recurrent inference.***

  The causal InLine attention can be written in a recurrent mode, supporting $\mathcal{O}(1)$ complexity inference. This recurrent form is formulated as follows: 
  $$
  S_i=S_{i-1}+\phi(K_i)V_i^\top,\ \ W_i=W_{i-1}+\phi(K_i),\ \ Z_i=Z_{i-1}+V_i,\ \ O_i=\phi(Q_i)^\top S_i-\phi(Q_i)^\top W_i/i+Z_i/i
  $$

  where $Q_i,K_i,V_i\in\mathbb{R}^{d}$. This recurrent form is ***strictly equivalent to*** the parallel form.

- The above analyses show that our injective linear attention can apply to auto-regressive language models, enjoying both parallel training and $\mathcal{O}(1)$ complexity (per token) inference. In addition, chunk-wise parallel training like [5] can also be used, which is a mix of the parallel and recurrent modes.

- Due to time and computation resource constraints, we are still working on building InLine language model and are unable to offer the results here. Hopefully, we could possibly provide the results in the revised manuscript.

[1] Hydra attention: Efficient attention with many heads. In ECCVW, 2022.

[2] Efficient attention: Attention with linear complexities. In WACV, 2021.

[3] Soft: Softmax-free transformer with linear complexity. In NeurIPS, 2021.

[4] Flatten transformer: Vision transformer using focused linear attention. In ICCV, 2023.

[5] Retentive network: A successor to transformer for large language models. ArXiv, 2307.08621.

---

**For detailed responses to individual reviewer comments, please refer to our separate responses to each reviewer.**

Lastly, we would like to thank the reviewers for their time and we are welcome for any further discussion.

Meta-review: The paper received 5/5/5/6 ratings. Reviewers had initial concerns regarding the novelty of the paper, the similarity between the paper and related works, missing comparison with Mamba and other related works, lack of ablation study, etc. The authors provided a rebuttal which successfully addressed those concerns. After checking paper, reviews and rebuttal, AC recommends to accept the paper.
Decision: Accept (poster)