QT-ViT: Improving Linear Attention in ViT with Quadratic Taylor Expansion
Authors: Yixing Xu
Chao Li
Dong Li
Xiao Sheng
Fan Jiang
Lu Tian
Emad Barsoum
Venue: NeurIPS 2024 poster (2024)
Keywords: Vision Transformer
linear attention
quadratic Taylor expansion
Primary area: deep_learning_architectures

Abstract: Vision transformer model (ViT) is widely used and performs well in vision tasks due to its ability to capture long-range dependencies. However, the time complexity and memory consumption increase quadratically with the number of input patches which limits the usage of ViT in real-world applications. Previous methods have employed linear attention to mitigate the complexity of the original self-attention mechanism at the expense of effectiveness. In this paper, we propose QT-ViT models that improve the previous linear self-attention using quadratic Taylor expansion. Specifically, we substitute the softmax-based attention with second-order Taylor expansion, and then accelerate the quadratic expansion by reducing the time complexity with a fast approximation algorithm. The proposed method capitalizes on the property of quadratic expansion to achieve superior performance while employing linear approximation for fast inference. Compared to previous studies of linear attention, our approach does not necessitate knowledge distillation or high-order attention residuals to facilitate the training process. Extensive experiments demonstrate the efficiency and effectiveness of the proposed QT-ViTs, showcasing the state-of-the-art results. Particularly, the proposed QT-ViTs consistently surpass the previous SOTA EfficientViTs under different model sizes, and achieve a new Pareto-front in terms of accuracy and speed.

QT-ViT: Improving Linear Attention in ViT with Quadratic Taylor Expansion
Yixing Xu, Chao Li, Dong Li, Xiao Sheng, Fan Jiang, Lu Tian, Emad Barsoum Advanced Micro Devices, Inc., Beijing, China
(yixing.xx xu, chao. 11, d. d.li, xsheng, f. f.jiang lu. tian, emad. barsoum) Camdd com
Abstract
Vision transformer model (ViT) is widely used and performs well in vision tasks due its ability to capture long-range dependencies. However, the time complexity and memory consumption increase quadratically with the number of input patches which limits the usage of ViT in real-world applications. Previous methods have employed linear attention to mitigate the complexity of the original self-attention mechanism the expense of effectiveness. In this paper, propose QT-ViT models that improve the previous linear self-attention using quadratic Taylor ex- pansion. Specifically, we substitute the softmax-based attention with second-order Taylor expansion, and then accelerate the quadratic expansion by reducing the time complexity with fast approximation algorithm. The proposed method capitalizes on the property of quadratic expansion to achieve superior performance while employing linear approximation for fast inference. Compared to previous studies of linear attention, our approach does not necessitate knowledge distillation or high- order attention residuals facilitate the training process. Extensive experiments demonstrate the efficiency and effectiveness of the proposed QT-ViTs. showcasing the state-of-the-aa results. Particularly, the proposed QT- consistently surpass the previous SOTA EfficientViTs under different model sizes, and achieve a new Pareto-front terms of accuracy and speed.
Introduction
Compared to convolutional neural networks (CNNs), vision transformers (ViT's are getting more and more attention due to their strong performance across various computer vision tasks, such as
image classification [33 16
37
38
21 object detection 43, semantic segmentation [36] [5]
The effectiveness of VIT comes from the multi-head self- attention (MHSA) operation that allows the model to capture long-range information by calculating the attention score between each pair of patches. However, this mechanism necessitates quadratic time and storage complexity O(n²) related to the number of input patches n, and the original ViTs require significant computational and storage resources when applied to real-world applications.
and low-level vision 20 32
31
30
To overcome the aforementioned problem, previous researches focus on improving the original self- attention mechanism by using local attention such as window attention 23 dilated attention [TO and random attention (27). Another family of methods is to utilize linear attention [1] 5
that decomposes the original softmax function into two non-linear kernels so that the order of matrix multiplications attention score calculation changed to reduce the quadratic computational complexity into linear one. Many papers focus on designing non-linear kernels and novel linear- attention architectures for better approximation, e.g., Hydra-attention 2 uses the hydra trick their
multi-head attention by setting many heads features. Performer [ uses fast attention via positive orthogonal random features approach to approximate the softmax attention. EfficientViT B replaces softmax with ReLU non-linear activation and applies depthwise and group convolution to
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

86
85
ImageNet Top-1 Accuracy (%)
84
QTVIT (ours)
EfficientViT
82
EfficientNet
CMT
Swin
81
FasterVIT
ConvNext
EfficientNetV2
SwinV2
CSwin
79
Hydra
2
4
10
12
14
Latency (ms)
Figure 1: The accuracy-speed trade-off's of the proposed QT-ViTs and other state-of-the-art trans- former models on the ImageNet dataset. Latencies are evaluated on the AMD Instinct MI250 GPU.
improve its performance. Flatten transformer utilizes focused attention based on ReLU force the attention operation to focus on more informative regions.
Previous linear attention methods reduce the complexity of the attention mechanism from O(n2d) to ((dd)) at the expense of the performance on visual tasks, where d is the patch dimensionality. Some of them necessitate the knowledge distillation method 7 or high-order attention residuals (39 to make up for the performance gap. However, the GPU memory consumption will severely increase which makes these methods unsuitable for training large transformer models.
In this paper, we explore the utilization of second-order (quadratic) Taylor expansion to approximate the original softmax attention. We theoretically show that this approximation can be decomposed
into two non-linear kernels through the utilization of the Kronecker product [34] By employing this approach, the computational complexity can be changed from O(n2d) d) O(nd). We then propose fast approximation algorithm to accelerate the computation of the Kronecker product, thereby reducing the complexity to Ondd). In contrast the first-order (linear) Taylor expansion (7) and other linear attention methods, we can utilize the high-order information within the softmax function achieve superior performance while at the same time preserving the efficiency of linear attention. Experimental results on the ImageNet dataset show that the proposed VITs can achieve superior accuracy-speed trade-off when compared other state-of-the-as art methods, as shown in Fig. Additionally, we conduct experiments on object detection and semantic segmentation tasks to further validate the effectiveness of our approach.
2 Preliminaries
In this section, we first introduce the preliminaries of softmax attention and linear attention. Then, we provide an overview of various instantiations of the original linear attention method used VIT and analyze their advantages and disadvantages.

---

2.1 Softmax Self-Attention
Softmax self-attention operation is the key component in the transformer model. Given an input matrix X E R where N is the number of patches and d is the dimension of each patch, we first map the input matrix to the query, key and value embeddings by using the matrix multiplications:
Q = QWQ XWW,
V= V
where We. Wx k and Wv E Ixdd are learnable matrices. Then, the attention score is computed on each pair of patches to capture the global information as shown below:
Sim Q2 K.)
exp K /V) 1 exp QU /Vd)
V
(2)
Sim Q Kj)
where Sim Q+. K;) expl x /Vd) the similarity measurement function in the softmax attention, Q+ K; (K2), V O₂ are the corresponding k-th, i-th (i-th,, i-th, k-th row vectors of the query, key, value and output matrices, respectively. The inner product of the query-key pair is first computed to calculate the similarity between the pair, then a scale is applied for stability and a softmax function is used to transfer the similarity into probability. This probability applied to the value matrix to get the final attention score output. The softmax attention computes the inner products of all the query-key pairs and results in a ( time complexity.
2.2 Linear Self-Attention
The overhead of the computation of Eq. mainly comes from the matrix multiplication. By decompos- ing the similarity function into two separate kernel embeddings, ie., Sim (Q., K;) ( (K;) and the original softmax attention function can be changed into linear attention by exchanging the order of matrix multiplication:
V ó(Qs) (EN ((K,) TV.). j-1 (QU)(K))
N
oe (Q))(K,)
O₂
Σ Σ N
(3)
( (E ((K))T)
where the complexity is changed from ((V2d) to O(Nd)) Since the patch dimension d is always smaller than the number of patches N in the popular ViT architectures, the computation overhead can thus be reduced.
However, in order to losslessly decompose the similarity function in the softmax attention Sim(Qu: Qu, K;) into the product of two kernel embeddings Φi (Qss) and @(K,), the dimensionality of the kernel function needs to be infinite which is unable to apply to real-world applications. Thus, a series of instantiations are proposed trying to compute (--) efficiently while preserving as much information of the original similarity function possible.
In the following, we use q è Q₁ and k A Ki to represent row vectors in query matrix Q and key matrix K that not belong to any specific row
2.3 Instantiations of the Kernel Function
Linear transformer was first proposed in 19 and ((x) elu(x) was used the kernel function. EfficientViT (3 used @(x) = (x)U(() as the instantiation. Both methods ensure that á(q)o(k) 2 0 which is consistent with the property of the similarity measurement function Sim(-). Flatten Transformer [4]] argued that previous approximations smooth the distribution of linear attention which failed to focus on more informative regions, and proposed a focused function
(x) ||ReLU(x]"""]]
ReLL(x)]] ReLU(x)*** ** where ||-|| represents the Euclidean norm and (-)"*p is element-
wise power p of the input. Hydra attention 2 used cosine similarity as the kernel d(x) s/||x||2.
PolyNL ① used mean kernel d(x) = x/vN, and AFT-Simple [4 proposed different functions for query p(q) = sigmoid((g) and key (kk) (offmaxx(k). respectively. These methods suffered from the performance drop since they lacked sufficient expression ability to replicate the original sofumax attention mechanism.
3

---

Besides the aforementioned methods, some studies approximated the similarity function with kernel expansions such as angular kernel expansion 39 with Sim k) 1/2 + 1/ (qk") + H, or first order Taylor expansion 7 with Sim q. k) I+ qk /vV+ Hr where H, represents the high-order residuals. These methods necessitated the masked output of original softmax attention H,, and applied the knowledge distillation (KD) method to further enhance the performance which severely increased the GPU memory consumption and were unsuitable for training large transformer models.
3 Methods
In this section, we propose use second-order (quadratic) Taylor expansion to approximate the similarity measurement function Sim(.: i) Eq. [2] Compared to the first-order (linear) Taylor expan- sion [7]. quadratic approximation contains less information in the high-order residuals. Therefore, we can directly ignore them and derive good performance without utilizing masked softmax attention output or the KD method.
However, is non-trivial to decompose the quadratic Taylor expansion into separate kernel embed- dings with linear time complexity. Thus, in the following we first give a theoretical derivation by using the Kronecker product to decompose the quadratic expansion. Then, a fast approximation algorithm is applied accelerate the computation of the Kronecker product.
3.1 Decompose Quadratic Taylor Expansion
The quadratic Taylor expansion of the similarity measurement function is expressed as:
< q. k
>
q. k
>
q.
k
>
Sim(q, k) = exp
~ 1+
+
Vd
Vd
2d
<9 Vd
+1
+1
2
< (()): ((k) >ا +1
(4)
where < <',,'> >>
is the dot product and o(x) = va is used for vectors q and k. However, since the quadratic term exists in Eq. f it is challenging to decompose the equation into two separate kernel embeddings. In the following, we show that this problem can be solved by using the Kronecker product.
Given two vectors = Ma and b {br]d-n we can easily derive:
a b ba=
asbi
Σ
2 2
agb:azby-
1=1+1
This is equal to first computing the Kronecker product of each vector and then applying dot product, i.e., given Kx(x) = vec(x&x) where & represents the Kronecker product and vee(-) ) is the vectorized output, we have:
(a), >= =aaaa asa) [b,b,
babj
=(a10 ... aidd, a201, a2dd, ... adal, adae
[bib], biba, b2b1, baba. babi, ... babba
d-1
Σ 26
a.b,a,b,
ii+1 < a b x
(6)

---

Then, we can apply Eq. to Eq. 4 and decompose the similarity function into two separate kernel embeddings:
Φ((g). ((k) >
Sim(q, k)
2 ()()(g), Kr (r(((k)) > +1
2 =< (<g))) +(k)),((k)>> >,
(7)
where
(x) = Lv2 K, (o(x),
v2 vec(o(x) @ oxx)),
(8)
/2
V2
the kernel function applied the query and key vectors. Note that given a vector x E Rd Kronecker product gives an output vector with quadratic length (x) E R.. Thus, the time complexity of linear attention using the decomposed quadratic Taylor expansion is ((Nd²). Compared to the original softmax attention with O(N2d) time complexity, the proposed method does not yield an advantage.
3.2 Reduce the Time Complexity
Recall that the computational burden primarily arises from the Kronecker product that quadratically expands the input dimension. Thus, there are several simple ways to reduce the dimension. For example, pooling function can be applied the input vector y pool(x) (x) E I2d/p where p the dimensionality reduction factor. The output dimension of the Kronecker product can be reduced to (y) E TR /v² and the corresponding time complexity of the linear attention is O(Nd /p²). Another way to divide the input vector into chunks x .x.,,..., x*) and compute the Kronecker product within each chunk (x"x) E /ed and finally concatenate them together to derive the output concat (x,(x'), )............... (xx)) d /c. The time complexity of the linear attention using this method is O(Nd3/c).
Although methods mentioned above can decrease the computational load, they do not actually reduce the time complexity. In the following, we propose a fast approximation algorithm to accelerate the computation of the Kronecker product, and reduce the computational complexity from O to O(Nd)..
By rewriting the definition of (,()()) in Eq. 8 in its element-wise form, can get:
X
K,({(x)) = K,((
1])
1},
Fd
1},
Vd 11
Vd
4/d
Vd
Va
F1
Fi
31
Td Vd
Fg
Fd Vd
31
Fd Va
(9)
Vd
Vd
Vd
Vd
Note that the order of the elements in the above equation does not influence the result of the inner product < (ő(g), (ě(k)) > in Eq. 7 as long as (,((())) and (,(o(k) change the order of their elements the same manner. Thus, Eq. Cean written as:
(m,,,,) (x
(x.)1_1 4d 1
(x((())) concat
(10)
Vd
Vd
which is divided into four terms. The first is the quadratic term that contains d² components representing the multiplication of each pair of elements in (including ceff-muliipiication)) the second and third terms are the linear term with length each, and the fourth term is the constant term. Since the computational load of the inner product in Eq. mainly comes from the quadratic term, it is important to reduce the number of elements in this term. Randomly preserving d items from d2 elements is an efficient approach but leads to poor results. Employing grouping techniques help selecting the most representative items at the cost of increasing the computational complexity
5

---

compared to random selection. We empirically find that using the self multiplication terms {aī) can effectively represent all quadratic terms, while the same time maintaining high efficiency.
Therefore, the Kronecker product in Eq. 10 can be replaced with a compact version:
x ji=1
{
(x()()) concat
3.
V2
?
vd
vd
concat
a
(11)
in which we merge items of the same kind and multiply them by the square root of the number of the same items so as not to affect the inner-product result in Eq. 2 Learnable scalar parameters a, B and y are used as the trade-off parameters. Note that given a vector x E R", this compact version of the Kronecker product gives an output of length 2d + 1. Therefore, the time complexity of linear attention using the decomposed quadratic Taylor expansion is reduced from O(Nd²) to O ((Nd). We further found that the linear term can be discarded without hurting the classification performance, thus we set
the following experiments.
4 Experiments
In this section, we apply our linear attention with quadratic Taylor expansion to vision transformers and propose a series of QT-ViT models. We empirically investigate the effectiveness and efficiency of the proposed models on the ImageNet-1k classification dataset. Additional results regarding the performance on object detection and semantic segmentation tasks are provided in the appendices.
4.1 Image Classification
Datasets and model architectures. The ImageNet- Ik classification dataset is used for training and evaluation, which contains 1.28M training images and 50K validation images from 1000 different classes We utilize the model architecture proposed in EfficientViT (3) and replace the kernel function with our proposed compact quadratic Taylor expansion kernel. An absolute positional embedding is added to the key matrix before applying linear attention, and non-linear shortcut 0=0+ GELU (BV) is added to the output of the linear attention where is the value matrix. Different exponential moving average (EMA) decay parameters are used, and all the other training settings and hyper-panee parameerssmeters remain the same
Compared methods and evaluation metrics. To verify the effectiveness of the proposed QT-s,Ts, compare our method with series of competitors including (1) Vision transformers with lin- ear attention such as ViTALiTy 77]. Castling-Vis ViT (39]. Efficient ViT 3.. FLatten Transformer [14]
and Hydra Attention ViT 2 : (2) Other vision transformers with sparse attention hierarchical
architectures such as Swin 233 S2 [22), FasterViT (17), PoolFormer [40], Mobile (25).
Mobile ViTV2 [26] and CSwin [ (3) State-of-the-an CNN models and CNN-Transformer com-
bined model architectures such as CoAtNet (6) CMT 12). ConvNeXt (24). EfficientNet (28 and
EfficientNe122 29
The proposed QiT''T' ViT's and other baseline models are evaluated based on the accuracy-speed trade- measure the classification performance with top- 1/top/
offs shown in Fig, Furthermore, accuracy. The efficiency of the model is represented by the FLOPs and parameters. Finally, we
evaluate the inference speed of the models the AMD Instinct MI250 GPU in Fig. D
Experimental results. The effectiveness and efficiency of the proposed QT-ViTs are evaluated on the ImageNet- 1K dataset by comparing them to other state-of state-of-the-art bascline methods mentioned above. The results are shown in Tab, D and all methods are gathered by their FLOPs into five groups including: <1G, I~3G, 3~5G, 1~1 and > >0G.
As shown in the table, the proposed QT-VITs achieve new SOTA accuracy-efficiency trade-off across different FLOPs range. For example, we outperform ViTALiTy who uses the first-order Taylor expansion by large margin without using knowledge distillation or high-order residuals that severely increase the GPU memory consumption during training. Compared to vision transformer with sparse attention such as CSWin, our QT-ViT-4 achieves 84.7% top-1 accuracy with only 5.26G FLOPs while CSwin-B has 84.2% top-1 accuracy with 15,00G FLOPs, which means that we have 0.5% higher top-1

---

Table 1: Image classification results ImageNet- 1k dataset. QT-VI's compared with SOTA baselines. Methods are grouped based on FLOPs.
FLOPs range
Model Architecture
Parameters (M)
FLOPs (G)
Top-1 | Acc (%)
Top-5 Acc
(%)
<IG
ViTALiTy-DeiT-T
0.33
71.9
EfficientNet-11
28
7.8
0.70
79.1
94.4
PoolFormer-5y
11.9
1.82
77.2
Efficient ViT-BB
9.1
0.52
79.4
94.3
CMT
12
9.5
0.60
79.1
94.5
MobileViT-XS
25
2.3
0.70
74.8
92.3
MobileViTVV2-0.5 26
0.50
70.2
QT-ViT-1 (ours)
9.4
0.52
79.6
94.7
I~3G
Castlig--eiTT-
39
5.6
1.18
76.0
92.5
EfficientNet-B3 28
12.0
1.80
81.6
95.7
EfficientVVT-BB2
24.3
1.60
82.1
95.8
FLatten-PVT-- [14
12.2
2.00
77.8
QT-ViT-2 (ours)
24.9
1.60
82.5
95.9
3~5G
PoolFormer-S24
40
21.4
3.40
80.3
EfficientNet-BB B4
28
19.0
4.20
82.9
96.4
Swin T 23
29.0
4.50
81.3
95.5
EfficientViT-B3
49.0
4.00
83.5
96.4
FasterViT-1 17
53.4
5.30
83.2
96.5
ConvNeXt-T 24
29.0
4.50
82.1
QT-V (ours)
49.7
3.97
83.9
96.7
5~10G
PoolFormer-M33
56.2
8.78
82.1
EfficientNet-B5
28
30.0
9.90
83.6
96.7
EfficiemtNetV2-S
22.0
8.40
83.9
SwinV2-T 22
28.0
6.60
82.8
EfficientVVT--L.1
53.0
5.30
84.5
96.9
EfficientVVT--1.2
3
64.0
6.96
85.1
97.0
Casting-MWViTV2-B
51.9
9.82
85.0
97.2
FasterViT-2 [17
75,9
8.70
84.2
96.8
QT-V (ours)
53.0
5.26
84.7
96.7
QT- (ours)
64.1
6.96
85.2
97.0
>00G
PoolFormer-Mas
73.5
11.56
82.5
CSWin-B 9
78.0
15.00
84.2
EfficientViT-L.3
246.0
28.00
85.8
97.2
Castling-DeiT-B 139
87.2
17.28
84.2
Hydra-DeiT-B 2
17.46
80.6
FLatten-CSwin-1 14
75.0
15,00
84.5
SwinV2-B [2
88.0
21.80
84.6
CoAtNet-3 6
168.0
35.00
84.5
FasterViT-4 [7]
424.6
36.60
85.4
97.3
QT-V (ours)
246.8
27.60
86.0
97.3
accuracy with 64.9% less FLOPs. For CNN competitors, the QT-ViT-3 outperforms ConvNeXt-T by 1.8% top-1 accuracy with 11.8% less FLOPs. Finally, compared to the current sfate-of-the-arr vision transformer model, the proposed QT-ViT-1~6 outperforms SfficientViT-BII-BB & LI~L3 by 0.2%, 0.4%, 0.4%, 0.2%, 0.1 % 0.2% respectively with roughly the same FLOPSs and parameters. The accuracy-speed trade-off's of the proposed QT-ViTs and other models are shown in Fig.

---

Table 2: Results of using different kernels. The baseline method uses the original self-attention operation with dd computational complexity and is used as the strong baseline. Other methods use different linear attentions.
Method
Kernel
((q)
o(k)
Top-1 Acc (%)
baseline
79.8
EfficientViI 3
ReLU non- con-lincarity
(e)U(()
79.4
Hydra 2
cosine similarity
x/ //||>/||
79.1
PolyNL
mean sigmoid & softmax angular kernel
x/ e//V
78.8
AFT-Simple 41
aax)
k) 1 softmaxx(x)
78.9
Castling- VIT ViT
Sim
(qk
79.1
ViTALiTy
1st order Taylor expansion
[2/ Vd 1
78.5
QT-ViT (ours)
2nd order Taylor expansion
(o(xx)) v2
79.6
v2
4.2 Ablation Study
In this section, we conduct several ablation studies to further verify the superiority of our proposed quadratic Taylor expansion kernel.
We compare the results of using quadratic Taylor expansion kernel with other kernels used in various linear attention vision transformers including EfficientViT 3 which uses ReL.U kernel, Hydra attention
Results of using different kernels.
2 that utilizes cosine kernel, PolyNI. 1 with the mean kernel, AFT-Simple [4I] that proposes different kernels for query and key, angular kernel expansion [39] and first order Taylor expansion 77). All methods use the same training settings and network architecture except the kernel used for computing the linear self-attention. The baseline method uses the original self-attention operation with O(Ndd) computational complexity and is used as a strong baseline for comparison.
As the results shown in Tab. the proposed quadratic (2nd order) Taylor expansion outperforms all other competitors which demonstrates the effectiveness of the proposed method. For example, we achieve a 1.1% % better top-1 accuracy compared to the linear (1st order) Taylor expansion kernel, 0.2% better than ReLU, 0.5% better than cosine, 0.8% better than mean, 0.7% better than sigmoid & softmax and 0.5% better than the angular kernel.
Ablation reducing the time complexity of the Kronecker product. In Sec. 3.2 we mentioned
several ways of reducing the computational burden of the Kronecker product including:
Method 1: applying pooling function the input vector y= pool(x) Rd/p;
Table Ablation on reducing the time complexity the Kronecker product. The experiments are conducted using the QT-ViT-1 model on the ImageNet- k dataset.
Method
Hyper-param
Time Comp.
Params (M)
FLOPs (G)
Top-1 1 Acc (%)
baseline
O(Nd3)
9.4
0.65
79.7
p=2
0.55
79.3
O(N
p=4
9.4
0.52
79.1
0.58
79.4
O(Nd%/c
9.4
0.55
79.3
c=8
9.4
0.53
79.1
O(Nd))
9.4
0.52
61.8
(ours)
O(Nd+)
9.4
0.52
79.6
8

---

Method 2: dividing the input vector into chunks, compute the Kronecker product within each chunk and concatenate them together derive the final output;
Method 3: randomly preserving d items from de quadratic elements in (Ø(x)) (Eq. 10
Method 4: using the self-multiplication terms to represent all quadratic terms to derive the compact version of the original Kronecker product (d)x)) (Eq.
The classification results of using different methods mentioned above are shown in Tab. in which the baseline method computes the original Kronecker product and is used compare with other efficient methods. We can see that reducing input dimension with the pooling function (method 1) or dividing it into chunks (method 2) are efficient enough since p and are small compared the dimension d of the vector and has a higher time complexity. Besides, the classification performances are not satisfying because too much information lost. Randomly selecting quadratic items (method 3) is computationally friendly but has sub-optimal performance. The proposed compact version of original Kronecker product (method 4) performs best among the methods which indicates that using the seff-multplication terms to represent quadratic terms is enough to preserve the information in the output of the Kronecker product.
4.3 Visualization
1st order Taylor
2nd order Taylor
Query
ReLU
We plot the results of the self- attention maps from the last block given specific query (column 1, marked as red on the original images) using dif- ferent attention methods in- cluding first-order Taylor ex- pansion (7) (column 2). ReLU non-linearity function [ (col- umn 3) and the quadratic Tay- lor expansion used in the pro- posed QT-VIT VIT (column 4). We can see that the proposed QT- VIT can exhibit more focused and sharper response on atten- tion feature maps. Further- more, given query vector, QT-ViT captures reasonable features on the feature map more accurately compared to the competitors. For exam- ple, Qi- concentrates on both ears of the dog given the query on the left ear of the dog. We can intuitively ob- serve the advantages of QT-
Ball
Bird
Dog
Taxi
Figure Attention maps from different linear attention methods including the first-order Taylor expansion, ReLU non- non-linearity func- tion and the second-order Taylor expansion (ours).
ViT from Fig. 2
5 Conclusion
In this paper, we propose a new linear attention method approximate the usage of softmax self- attention in the original vision transformer models. By conducting quadratic Taylor expansion of the similarity measurement function with the help of the Kronecker product, we can successfully decompose the similarity function into the product of two kernel embeddings while reserving high- order information and maintaining the effectiveness of the original self-attention. Furthermore, we propose fast approximation algorithm accelerate the computation of the Kronecker product and reduce the time complexity from O (NN3) (Nd?) without much loss of information. We conduct experiments the proposed QT-ViT models using the benchmark dataset ImageNet- Ik.

---

and the results show that we can achieve a better accuracy-efficiency trade-off compared to other state-of-the-art transformers and CNNs.
References
[1] Francesca Babiloni, Ioannis Marras, Filippos Kokkinos, Jiankang Deng, Grigorios Chrysos, and Stefanos Zafeiriou. Poly-nl: Linear complexity non-local layers with 3rd order polynomials. In Proceedings of the IEEE/CVF international conference on computer vision, pages 10518 10528, 2021.
[2] Daniel Bolya, Cheng-Yane Yang Fu, Xiaoliang Dai, Peizhao Zhang, and Judy Hoffman. Hydra attention: Efficient attention with many heads. In Luropean Conference Computer Vision, pages 35-49. Springer, 2022.
[3] Han Cai, Chuang Gan, and Song Han. Efficientvit: Enhanced linear attention for high-resolution low- computation visual recognition. arXiv preprint arXiv:2205. 14756, 2022.
[4] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European conference on computer vision, pages 213 219. Springer, 2020.
[5] Krzysztof Choromanski. Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009 14794, 2020.
[6] Zihang Dai, Hanxiao Liu, Quoc Le, and Mingxing Tan. Coatnet: Marrying convolution and attention for all data sizes. Advances in neural information processing systems, 11:3965-39777 2021.
[7] Jyotikrishna Dass, Shang Wu, Huihong Shi, Chaojian Zhifan Ye, Zhongfeng Wang, and Yingyan Lin. Vitality: Unifying low-rank and sparse approximation for vision transformer acceleration with a linear taylor attention. In 2023 IEEE International Symposium on High-Perfornn Performance Computer Architecture (HPCA), pages 415-428. IEEE, 2023.
[8] Ning Ding, Ychui Tang, Kai Han, Chao Xu, and Yunhe Wang. Network expansion for practical training acceleration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 20269-20279, 2023.
[9] 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 Proceedings of the IEFF/CVE conference on computer vision and pattern recognition, pages 12124-12134, 2022.
[10] Dan Guo, Kun Li, Zheng-Jun Zha, and Meng Wang. Dadnet: Dilatd--tttanion-efffomaae convnet for crowd counting. In Proceedings of the 27th ACM international conference on multimedia, pages 1823-1832 2019.
[11] Jialong Guo, Xinghao Chen, Yehui Tang, and Yunhe Wang. Slab: Efficient transformers with simplified linear attention and progressive re re-parameterized batch normalization. arXiv preprint arXiv:2405. 71044055.1888. 1582, 2024.
[12] Jianyuan Guo, Kai Han, Han Wu, Yehui Tang, Xinghao Chen, Yunhe Wang. and Chang Xu. Cmt: Convolutional neural networks meet vision transformers. In Proceedingy the IEEE/CVE conference on computer vision and pattemn recognition, pages 12175-12185, 2022.
[13] Jianyuan Guo, Zhiwei Hao, Chengcheng Wang, Yehui Tang, Han Wu, Han Hu, Kai Han, and Chang Xu. Data-efficient large vision models through sequential autoregression. arXiv preprint arXiv:2402.048. 2024.
[14] Dongchen Han, Xuran Pan, Yizeng Han, Shiji Song, and Gao Huang. Flatten transformer: Vision transformer using focused lincar attention. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 5961 1971, 2023.
[15] Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey on vision transformer. IEEE transactions on pattern analysis and machine intelligence, 45(1 4501):87-110, 2022.
[16] Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. Advances in neural information processing systems, 34:15908-115 15919, 2021.
10

---

[17] Ali Hatamizadeh, Greg Heinrich, Hongxu Yin. Andrew Tao, Jose M Alvarez, Jan Kautz, and Pavlo Molchanov. Fastervit: Fast vision transformers with hierarchical attention. arXiv preprint arXiv:2306. 06199, 2023.
[18] Kaiming He, Georgia Ckioxari, Piotr Dollár, and Ross Girshick. Mask r-cnn. In Proceedings of the IEEE international conference on computer vision, pages 2961-2969. 2017.
[19] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers mns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pages 5156 5165. PMLR, 2020.
[20] Wenbo Li, Xin Lu, Shengju Qian, Jiangbo Lu, Xiangyu Zhang, and Jiaya Jia. On efficient transformer-basedt image pre-training for low-level vision, arXiv preprint arXiv:21 10175, 2021.
[21] Wenshuo Li, Xinghao Chen, Han Shu, Yehui Tang, and Yunhe Wang. Exep: Extreme Ilm checkpoint compression via weight-momentum joint shrinking. arXiv preprint arXiv:2406. 1257, 2024.
[22] Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie, Yixuan Wei, Jia Ning, Yue Cao, Zheng Zhang, Li Dong, et al. Swin transformer v2: Scaling up capacity and resolution. In Proceedings of the IEEE/CVF conference on computer vision and pattern recogmition, pages 12009-12019, 2022. 2022.
[23] 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 Proceedings of the IEEE/CVF international conference computer vision, pages 10012-10022, 2021.
[24] Zhuang Liu, Hanzi Mao, Chao Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11976- 1976-11986, 2022.
[25] Sachin Mehta and Mohammad Rastegari. Mobilevit: light-weight, general-purpose, and friilll vision transformer. arXiv preprint arXIv:2110.02178, 2021.
[26] Sachin Mehta and Mohammad Rastegari. Separable self-attention for mobile vision transformers. arXiv preprint arXiv:2206. 02680, 2022.
[27] Hao Peng. Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. Random feature attention. arXiv preprint arXiv:2103.02143, 2021.
[28] Mingxing Tan and Quoc Lc. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference machine learming, pages 6105-6111111 611.6 PMLR, 2019.
[29] Mingxing Tan and Quoc Le. Efficientnetv2: Smaller models and faster training. In International conference machine learning, pages 10096-10106. PMLR, 2021.
[30] Yuchuan Tian, Hanting Chen, Chao Xu, and Yunhe Wang. Image processing gnn: Breaking rigidity in super-resolution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition. pages 24108-24117, 2024.
[31] Yuchuan Tian, Jianhong Han, Hanting Chen, Yuanyuan Xi, Guoyang Zhang, Jie Hu, Chao Xu, and Yunhe Wang. Instruct-ipt: All-in-one image processing transformer via weight modulation. arXiv preprint arXiv:2407.000 00676, 2024.
[32] Yuchuan Tian, Zhijun Tu, Hanting Chen, Jie Hu, Chao Xu, and Yunhe Wang. U-dits: Downsample tokens in uhspaped diffusion transformers. arXiv preprint arXiv:2405.0221 2024.
[33] Hugo Touvron, Matthieu Cord, Mathhijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. International conference on machine learning, pages 10347-10351 PMLR, 2021.
[34] Charles F Van Loan. The ubiquitous kronecker product. Journal of computational and applied mathematics. 123(1-2):55-100, 2000.
[35] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and Jian Sun. Unified perceptual parsing for scene understanding. In Proceedings of the European conference on computer vision (ECCV), pages 418-434, 2018.
[36] Enze Xie, Wenhai Wang, Zhiding Yu, Anima Anandkumar, Jose M Alvarez, and Ping Luo. Segformer: Simple and efficient design for semantic segmentation with transformers. Advances in neural information processing systems, 34:17777-120 12090, 2021.

---

[37] Yixing Xu, Chao Li. Dong Li, Xiao Sheng, Fan Jiang, Lu Tian, and Ashish Sirasao. Fdvit: Improve the hierarchical architecture of vision transformer. In Proceedings of the IEEE/CVF International Conference on Computer Vixion, pages 5950-5960, 2023.
[38] Yixing Xu, Chao Li. Dong Li, Xiao Sheng, Fan Jiang, Lu Tian, Ashish Sirasao, and Emad Barsoum. Enhancing vision transformer: Amplifying non-linearity feedforward network module. Forty-first International Conference on Machine Learning.
[39] 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 at vision transformer inference. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14431 14442, 2023.
[40] Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng, and Shuicheng Yan. Metaformer is actually what you need for vision. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10819-1082)) 2022.
[41] Shuangfei Zhai, Walter Talbott, Nitish Srivastava, Chen Huang, Hanlin Goh, Ruixiang Zhang, and Josh Susskind. An attention free transfomerr. arXiv preprint arXiv:2105 14103, 2021.
12

---

A Object Detection on COCO 2017 Dataset
We conduct experiments on the COCO 2017 dataset to further validate the effectiveness of the proposed QT- ViT models. The COCO 2017 dataset has 118K training images, 5K validation images and 20K test-dev images. We use the mask R-CNN [8] as the object detection framework, Efficient [3] and the proposed QT-ViTs as the backbone models. The experimental results are shown in the following table. We can see that the proposed QT-ViT has better mAP than the state-of-the-ar model EfficientViT under the same training setting.
Table 4: Experimental results on COCO 2017 dataset using different backbones.
Backbone
AP
AP50
AP75
Params (M)
EfficientViT-BI
39.1
58.0
41.8
57.6
QT-ViT-1
39.3
58.2
42.1
57.9
EfficientViT-B2
40.8
59.5
44.3
68.0
QT-ViT-2
41.1
59.7
44.7
68.5
EfficientViT-B3
42.3
60.6
45.5
92.1
QT-ViT-3
42.6
60.9
45.9
93.1
In the following table, we show the results of using absolute positional embedding (APH) on object detection. Note that APE has little impact on the latency, FL.OPs, and top-1 accuracy for image classification tasks thus we do not show the corresponding results in the main section.
Table 5: Experimental results on COCO 2017 dataset using different backbones.
Backbone
AP
AP50
AP75
QI-V w/ APE
39.3
58.2
42.1
QT-ViT-I w/o APE
39.2
58.2
42.0
QT-ViT-2 w/ APE
41.1
59.7
44.7
QT-ViT-2 w/o APE
41.0
59.7
44.6
QT-ViT-3 w/ APE
42.6
60.9
45.9
QT-ViT-3 w/ APE
42.5
60.8
45.8
Semantic Segmentation on ADE20K dataset
further verify the effectiveness of the proposed QT-VIT on semantic segmentation task using the ADE20K dataset, which contains 20K training images from 150 semantic categories, 2K validation images and test-dev images. UperNet (55 is used as the framework for the experiments. As shown in the table below, using QT-VTTs as the backbone models achieve better mloU on the ADE20K dataset than using the Efficient ViTs as backbones. The results show that the proposed ViT performs well on the semantic segmentation task.
C Memory Footprint
The masked output of the original softmax attention has been shown to useful in previous studies such as Vitality 77] and Castling- ViT 39.. It is also shown to be useful in our method and the experiments using QTViT-1 on the ImageNet dataset are shown below. However, requires more GPU memory during training, which is not suitable for training large models. Thus, we do not use this strategy our method. For the integrity of the paper, we still list the results of using original softmax in the following table, the experiments are conducted with QT-ViT-L 1 on ImageNet dataset.
13

---

Table 6: The effectiveness of APE.
Backbone
mloU
mAcc
Params (M)
EfficientViT-BI
32.8
45.3
32.5
QT-ViT-1
33,2
45,6
32.8
EfficientViT-B2 QT-ViT-2
35.8
49.0
43.7
36.3
49.4
44.3
EfficientViT-B3
38.0
51.0
68.8
QT-ViT-3
38.5
51.5
69.7
Table The impact using original softmax attention during training.
Method
GPU memory required per GPU during Training (GB)
Top-1 Ace (%)
w/o original softmax w/ original softmax
13.9
79.6
15.8 (+13.7%)
79.8
D
Broader Impact
This paper presents work whose goal is advance the field of Machine Learning. There many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
14

---

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 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 are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: takes lots of computational resources for training the models from scratch.
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: [NA]
15

---

Justification:
No theoretical results.
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 the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix 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:
Contents the main paper has all the information needed to reproduce the
results.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, 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 to 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 is a specific model and empirical evaluation, it may be necessary to either make 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 are appropriate to the research performed.
While NeurIPS 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) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer:
[No]
Justification:
We do not include code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for 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
/ ctpppp..cppulli//guiii wwwticccguie//eeeeeeeeiii CoodeSubeiiieeee ssi wswinnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We show all the experimental details in the main section.
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 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: It is time consuming to conduct experiments several times.
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, statistical significance tests, at least for the experiments that support 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, 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.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
17

---

It 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 enrors 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 error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See the experiment section.
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, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: htap:::///uripps/ http//uuurss.ccppuiipi/e httppp/ssccppp..t.ttttttttteeeea
Answer: [Yes]
Justification:
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: [Yes]
Justification: is research about fundamental vision transformer model.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or 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.
The conference expects that many papers will be foundational research and not tied to 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 improvement in the quality of generative models could be used to
18

---

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 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.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a 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:
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 to 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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?
Question:
Answer: [Yes]
Justification:
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 is used and, if possible, include URL.
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.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whw.ree.wthhhe....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
19

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll 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. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification:
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 much detail as possible should be included the main paper.
According to 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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on 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 expect authors to adhere 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.
20


Reviews:
[{"review_id": "sti61xrazs", "reviewer": "Reviewer_5zgq", "summary": "This paper proposed a new linear complexity sequence modeling strategy for image modeling. To achieve this, the authors first replace the softmax attention with second-order Taylor expansion, then accelerate its computation with a fast approximation algorithm. The effectiveness of the proposed method is validated on the image classification task.", "questions": "As above.", "limitations": "N/A", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "Its performance on ImageNet-1K is good.", "weaknesses": "1. It is unclear why directly using the first-order Taylor expansion is worse than using the second-order Taylor expansion with linear approximation. The author should provide a section to discuss this.\n\n2. Experiment details are missing. For example, different image resolutions can largely impact image classification performance. The author fails to provide the image resolution in the experiment section. \n\n3. Some mathematical derivation can be moved to the supplemental section. For example, there are some redundant equations in Eq. 4, 6, 7, 9. \n\n4. There is no actual training/inference speed comparison. Counting flops can be misleading in some cases. I would like to know the actual speed instead of flops.\n\n5. Missing linear attention vision backbone. For example, VVT (TPAMI 23).\n\n6. For image modeling, object detection, and semantic segmentation are also important. I do not know why the author decided to move these two tasks into the supplemental section. However, the semantic segmentation results are extremely low when compared with other linear image backbones. The author do not provide any comments on this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: It is unclear why directly using the first-order Taylor expansion is worse than using the second-order Taylor expansion with linear approximation. The author should provide a section to discuss this.**\n\nA1: In fact, the disadvantages of first-order Taylor attention are mentioned in the sections introduction (lines 42-44), preliminaries (lines 102-105), and experiments (lines 198-200), and our main idea is trying to resolve the disadvantages. \nGenerally speaking, first-order Taylor expansion discards too much information from the original attention and needs to necessitate the KD or high-order attention residuals during training to make up for the performance gap. However, the GPU memory consumption will severely increase which makes these methods unsuitable for training large transformer models. The second-order Taylor expansion utilizes more information in the original attention and can alleviate this problem. The above explanation is shown in lines 108-112.\n\n**Q2: Experiment details are missing. For example, different image resolutions can largely impact image classification performance. The author fails to provide the image resolution in the experiment section.**\n\nA2: We use image resolution of 224x224 by default in our experiments. The experimental results of using other image resolutions such as 256 and 228 are shown below, we can see that our QTViT can achieve a consistent improvement over the state-of-the-art method EfficientViT. Experiments on other models and the corresponding discussions will be added in the final version of the paper.\n|resolution|model|Top-1 Acc (%)|\n|-|-|-|\n|224|QTViT-1|**79.6**|\n|224|EfficientViT-B1|79.4|\n|256|QTViT-1|**80.1**|\n|256|EfficientViT-B1|79.9|\n|288|QTViT-1|**80.6**|\n|288|EfficientViT-B1|80.4|\n\n**Q3: Some mathematical derivation can be moved to the supplemental section. For example, there are some redundant equations in Eq. 4, 6, 7, 9.**\n\nA3: In fact, Eq. 4, 6, 7, 9 are not redundant equations. Eq.4 shows an initial way of decomposing the $exp(\\cdot)$ function with second-order Taylor expansion. Eq.6 gives theoretical proof that the square of a dot product can be converted into two Kronecker products followed by a dot product, which is also the core analysis of our method. Eq.7 combines the results of Eq.4 and 6 to prove that we can decompose the similarity function into separate kernel embeddings. Finally, Eq.9 changes the order of the elements in the Kronecker product, which does not influence the result of Eq.7 and can help us generate the approximation algorithm that can reduce the computational cost.\n\nThese equations illustrate the main idea of our method and may not be moved to the supplemental section. Otherwise, it will be hard for the readers to understand our method.\n\n**Q4: There is no actual training/inference speed comparison. Counting flops can be misleading in some cases. I would like to know the actual speed instead of flops.**\n\nA4: Figure 1 already shows the inference speed comparison among different methods. We provide inference speed of the models on the AMD Instinct MI250 GPU, which is also shown in Line 192 in the original paper.\n\n**Q5: Missing linear attention vision backbone. For example, VVT (TPAMI 23).**\n\nA5: Thanks for your suggestion. We will add VVT in our final version. We show the comparison between our method and VVT in the following table. We can see that we achieve similar results compared to VVT-small and medium but with much fewer FLOPs. For VVT-tiny and large, we can outperform them by a large margin with much fewer FLOPs and parameters.\n\n|models|parameters|FLOPs|Top-1 Acc (%)|\n|-|-|-|-|\n|QTViT-1|**9.4**|**0.52**|**79.6**|\n|VVT-tiny|12.9|3.0|79.2|\n|-|-|-|-|\n|QTViT-2|24.9|**1.60**|82.5|\n|VVT-small|25.5|5.6|82.6|\n|-|-|-|-|\n|QTV-T-3|49.7|**3.97**|83.9|\n|VVT-medium|47.9|9.4|83.8|\n|-|-|-|-|\n|QTViT-4|**53.0**|**5.26**|**84.7**|\n|VVT-large|61.8|10.8|84.1|\n\n**Q6: For image modeling, object detection, and semantic segmentation are also important. I do not know why the author decided to move these two tasks into the supplemental section. However, the semantic segmentation results are extremely low when compared with other linear image backbones. The author do not provide any comments on this.**\n\nA6: This is a good question. Due to space limitations, we move the results of object detection and semantic segmentation into the supplemental section. We will put them into the experimental section in the final version of the paper.\n\nFor the results of semantic segmentation, since EfficientViT did not provide their training details either in their GitHub code or in their paper by the time we submitted our NeurIPS paper, we conducted segmentation experiments based on mmsegmentation and used the same training strategy as Upernet-resnet50. Note that we use exactly the same training strategy to derive the results of the proposed QTViT and EfficientViT, we can surpass them by a margin which shows the priority of the proposed method. It is easy to improve the absolute mIoU value of both EfficientViT and QTViT by adjusting the training strategy, such as increasing the training steps.\n\nAs shown in the following table, by merely increasing the training steps, the mIoU results can be largely increased and approach the result of official EfficientViT-B1. In all of the settings, our QTViT can outperform EfficientViT.\n\n|model |training steps|mIoU|\n|-|-|-|\n|QTViT-1|160k|**33.2**|\n|EfficientViT-B1|-|32.8|\n|QTViT-1|320k|**37.6**|\n|EfficientViT-B1|-|37.2|\n|QTViT-1|640k|**41.2**|\n|EfficientViT-B1|-|40.9|", "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": "Q423U9mf3a", "reviewer": "Reviewer_QZCU", "summary": "This paper introduces QT-ViT models, which enhance linear self-attention using quadratic Taylor expansion. The similarity function is decomposed into the product of two kernel embeddings via the Kronecker product. By employing a fast approximation algorithm, the computational cost is reduced while maintaining overall performance. Experiments on ImageNet Classification with various model sizes show consistent improvement over the baseline EfficientViT method. Additionally, visualizations demonstrate that the QT-ViT model has a more focused attention feature map.", "questions": "- The author should provide more implementation details about the network, experimental setting, and comparison with other methods.", "limitations": "- The latency is tested on an AMD GPU, and I'm not sure if there is any difference on the implementation side. Will the performance gain be consistent on other type of devices?", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- S1. The paper is well-organized and easy to follow.\n- S2. The overall idea of improving linear attention with quadratic Taylor expansion and Kronecker product is sound.\n- S3. An extensive ablation study is conducted to show the performance of different variants of the Kronecker product.", "weaknesses": "- W1. The overall improvement is incremental. Compared to the EfficientViT baseline, the performance is almost the same under the same computation budget across different model sizes and tasks. For ImageNet classification, it would be helpful to include results on ImageNet-v2 and ImageNet-real to demonstrate the robustness and consistency of the improvement.\n\n- W2. The image resolution is not listed in the experiment section. Performance on different image resolutions should also be reported and compared with other methods. When using a much larger image resolution (and more patch tokens), how are the computation cost and latency affected?\n\n- W3. It would be better to include the detection and segmentation results in the main text to support the effectiveness of the proposed QT-ViT across different tasks.\n\n- W4. The network architecture should be detailed, and additional components like absolute positional embedding should be ablated.\n\n- W5. The mIoU performance of EfficientViT-B3 is reported as 49.0 on the ADE20k dataset in the original paper, which is inconsistent with the 38.0 reported in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: Overall improvement is incremental. Add results on ImageNetv2 and real.**\n\nA1: EfficientViT is currently the state-of-the-art method according to the accuracy-efficiency trade-off. Also, note that the difficulty of increasing the classification accuracy from a baseline of 79% is different from that of 85%. The better the baseline method is, the more difficult to further improve its performance. We achieve a new SOTA accuracy-efficiency trade-off under different model sizes.\n\nNote that our QTViTs 1$\\sim$3 and 4$\\sim$6 follow the architectures of EfficientViT B and L series which use different architectures as their baseline models, and QTViTs 1$\\sim$3 have more obvious improvements than QTViTs 4$\\sim$6. One of the reasons is mentioned above. Another reason is that the ratios of FLOPs of attention blocks in QTViTs 4$\\sim$6 are much smaller than those in 1$\\sim$3. Thus, the proposed method will have a smaller impact on QTViTs 4$\\sim$6, since we only modify the attention operation in the model. The proportions of the attention operation are shown in the following table.\n\n|model |ratio of FLOPs of attention blocks|\n|-|-|\n|QTViT-1|59.2%|\n|QTViT-2|62.1%|\n|QTViT-3|65.6%|\n|QTViT-4|25.4%|\n|QTViT-5|25.7%|\n|QTViT-6|25.6%|\n\nFor the robustness and consistency of the improvement, we directly use the pre-trained QTViTs and EfficientViTs checkpoints and conduct inference on ImageNet-V2 and ImageNet-ReaL. The results are shown below, and we can see that the proposed QTViTs can consistently outperform EfficientViTs, which shows the robustness and consistency of our method.\n|models|ImageNet|ImageNet-V2 |ImageNet-ReaL|\n|-|-|-|-|\n|QTViT-1|**79.57**|**75.37**|**85.61**|\n|EfficientViT-B1|79.38|75.04|85.32|\n|QTViT-2|**82.46**|**78.21**|**87.32**|\n|EfficientViT-B2|82.09|77.92|86.98|\n|QTViT-3|**83.93**|**80.04**|**88.31**|\n|EfficientViT-B3|83.47|79.01|88.11|\n\n**Q2: Larger image resolution, and the computation cost and latency.**\n\nA2: We use image resolution of 224 by default. The experimental results of using other image resolutions such as 256 and 228 are shown below, we can see that our QTViT can achieve a consistent improvement over the state-of-the-art method EfficientViT, and the FLOPs and latencies are roughly the same. Experiments on other models and the corresponding discussions will be added in the final version of the paper.\n|resolution|model|FLOPs (G)|latency (ms)|Top-1 Acc (%)|\n|-|-|-|-|-|\n|224|QTViT-1|0.52|1.74|**79.6**|\n|224|EfficientViT-B1|0.52|1.76|79.4|\n|256|QTViT-1|0.68|2.16|**80.1**|\n|256|EfficientViT-B1|0.68|2.13|79.9|\n|288|QTViT-1|0.86|2.28|**80.6**|\n|288|EfficientViT-B1|0.86|2.26|80.4|\n\n**Q3: Move det and seg results in the main text.**\n\nA3: Thanks for your suggestion, the experiments are currently in the supplemental section due to the limited pages of the main text. We will move the detection and segmentation results to the main text in the final version.\n\n**Q4: The network architecture should be detailed, and absolute positional embedding should be ablated.**\n\nA4: As shown in lines 176~180, we use exactly the same architecture as EfficientViT, except for changing the kernel function to our quadratic Taylor expansion kernel and adding the absolute positional embedding. In fact, the absolute positional embedding has little impact on the latency, FLOPs, and top-1 accuracy for image classification tasks (with almost the same latency and FLOPs, and <0.05 top-1 accuracy gap on different models). We actually see the difference in object detection, and the results of using absolute positional embedding or not are shown in the following table (APE stands for absolute positional embedding). \n\n|Backbone|AP|AP$_{50}$|AP$_{75}$|\n|-|-|-|-|\n|QTViT-1 w/ APE|39.3|58.2|42.1|\n|QTViT-1 w/o APE|39.2|58.2|42.0|\n|QTViT-2 w/ APE|41.1|59.7|44.7|\n|QTViT-2 w/o APE|41.0|59.7|44.6|\n|QTViT-3 w/ APE|42.6|60.9|45.9|\n|QTViT-3 w/o APE|42.5|60.8|45.8|\n\nThe above results will be added to the final version of the paper.\n\n**Q5: Inconsistent mIoU results.**\n\nA5: For the results of semantic segmentation, since EfficientViT did not provide their training details either in their GitHub code or in their paper by the time we submitted our NeurIPS paper, we conducted segmentation experiments based on mmsegmentation and used the same training strategy as Upernet-resnet50. Note that we use exactly the same training strategy to derive the results of the proposed QTViT and EfficientViT, we can surpass them by a margin which shows the priority of the proposed method. It is easy to improve the absolute mIoU value of both EfficientViT and QTViT by adjusting the training strategy, such as increasing the training steps.\n\nAs shown in the following table, by merely increasing the training steps, the mIoU results can be largely increased and approach the result of official EfficientViT-B1. In all of the settings, our QTViT can outperform EfficientViT.\n\n|model |training steps|mIoU|\n|-|-|-|\n|QTViT-1|160k|*33.2*|\n|EfficientViT-B1|-|32.8|\n|QTViT-1|320k|**37.6**|\n|EfficientViT-B1|-|37.2|\n|QTViT-1|640k|**41.2**|\n|EfficientViT-B1|-|40.9|\n\n\n**Q6: Provide more implementation details, experimental setting, and comparison with other methods.**\n\nA6: Thanks for your suggestions. The implementation details are already provided in lines 176-180, the experimental settings are shown in the experimental section and we will add the default image resolution in the main text. The experimental results mentioned above will be added to the final version of our paper.\n\n**Q7: The latency on other type of devices.**\n\nA7: We follow the standard procedure to test the latency on AMD GPU, by first converting the .pth pytorch checkpoint file into .onnx file, then conducting a latency test on our device. \n\nWe also test the latencies on NVIDIA V100 GPU, and the latency results are shown in **Figure 1 in the rebuttal PDF**. The conclusion is consistent with that of AMD GPU.", "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": "Au54SrZurf", "reviewer": "Reviewer_dQG7", "summary": "This paper proposes a novel method to compute the kernel function in linear attention. They decompose the softmax attention with Tayler expansion and utilize the first two items to approximate the exponential function. The Kronecker product is used to decompose the quadratic Taylor expansion into two kernel functions, and the self-multiplication terms in the output of the kernel are used to replace the quadratic terms for fast inference. The experimental results on multiple CV tasks show the effectiveness and efficiency of the proposed method.", "questions": "- You have mentioned that you do not necessitate the masked output of the original softmax attention during training as the previous methods do. I wonder if this can be added back to get further performance gain on QTViT?\n\n- You mentioned that QTViT can exhibit a more focused and sharper response around Fig.2. Is there any insight about this phenomenon?\n\n- In Tab.1, the performance gains of QT-ViT 4$\\sim$6 to the SOTA are more marginal compared to QT-ViT 1$\\sim$3 to the SOTA. Are there any explanations for this phenomenon?\n\nOverall, I would like to see the accuracy and speed trade of the other 3 models to make sure that the proposed method can surpass EfficientViT on all different model sizes.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The use of Kronecker product to realize the second-order Taylor expansion is smart and enlightening.\n\n- The fast approximation algorithm is effective in reducing the time complexity.\n\n- The QTViTs achieve a new Parato-front based on the accuracy and speed trade-off.\n\n- The paper is well-written and easy to understand.", "weaknesses": "- What is the dimension of $\\alpha$, $\\beta$ and $\\gamma$ used in Eq.11? Are there any ablation studies using different parameters?\n\n- I notice that you replace $K_r(\\phi(x))$ in Eq.8 with Eq.11, and you use $\\gamma$ to represent the constant term. Then, could the constant term $1/\\sqrt{2}$ in Eq.11 be merged with $\\gamma$? What about the scaling factor $1/\\sqrt{2}$ in Eq.8?\n\n- There are 6 models with different model sizes in Tab.1. Why do you plot only 3 models in Fig.1?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: What is the dimension of $\\alpha$, $\\beta$ and $\\gamma$ used in Eq.11? Are there any ablation studies using different parameters?**\n\nA1: $\\alpha$, $\\beta$, and $\\gamma$ are all scalars as shown in Line 164 in the original paper. All of them are learnable parameters and are initially set to 1s in the experiments. We further conduct some ablation studies by setting one of them to 0 initially and learning the three parameters normally. The results are shown below (conducted on QTViT-1 on ImageNet dataset).\n\n|$\\alpha$|$\\beta$|$\\gamma$|Top1 Acc (%)|\n|-|-|-|-|\n|1|1|1|79.6|\n|0|1|1|79.3|\n|1|0|1|79.4|\n|1|1|0|79.0|\n\nWe can see that the lack of each part in the initialization will influence the performance, and the constant term is the most important term among them. This is reasonable since the constant term is the most important basis for the Fourier series and a proper value can guarantee the approximation to always be greater than 0 which is one of the properties of softmax function.\n\n**Q2: I notice that you replace $K_r(\\phi(x))$ in Eq.8 with Eq.11, and you use $\\gamma$ to represent the constant term. Then, could the constant term $1/\\sqrt{2}$ in Eq.11 be merged with $\\gamma$? What about the scaling factor $1/\\sqrt{2}$ in Eq.8?**\n\nA2: This is a really good question. Yes, we merge the scaling factor and constant term in Eq.8 with $\\alpha$ and $\\gamma$ in Eq.11. Thus, the real initialization of $\\alpha$, $\\beta$, and $\\gamma$ after merging are $1/\\sqrt 2$, $1/\\sqrt 2$ and $\\sqrt 2$.\n\n**Q3: There are 6 models with different model sizes in Tab.1. Why do you plot only 3 models in Fig.1?**\n\nA3: Note that the baseline of our method is the EfficientViT, and they plot only EfficientViT L1$\\sim$L3 in their paper. We are following the same rule.\n\nSpecifically, QTViT 1$\\sim$3 corresponds to EfficientViT B1$\\sim$B3 and QTViT 4$\\sim$6 corresponds to EfficientViT L1$\\sim$L3. For the B series and L series in EfficientViT, they use different backbones and thus achieve different Parato-fronts. The L series has a better Parato-front than the B series. We have a similar result that our QTViT 4$\\sim$6 has a better Parato-front than QTViT 1$\\sim$3. Thus, we only plot QTViT 4$\\sim$6 in our original paper.\n\nTo better illustrate this, we show all 6 different models in **Figure 2 in the rebuttal PDF**. Note that although QTViT 4$\\sim$6 is better than 1$\\sim$3, all six models have better accuracy-speed trade-offs than the EfficientViT series.\n\nIf you feel it is necessary, we can add QTViT 1$\\sim$3 back to Fig.1 in the final version of the paper.\n\n**Q4: You have mentioned that you do not necessitate the masked output of the original softmax attention during training as the previous methods do. I wonder if this can be added back to get further performance gain on QTViT?**\n\nA4: This is a good question. The masked output of the original softmax attention has been shown to be useful in previous studies such as [1] and [2]. It is also shown to be useful in our method and the experiments using QTViT-1 on the ImageNet dataset are shown below. However, it requires more GPU memory during training, which is not suitable for training large models. Thus, we do not use this strategy in our paper.\n\n|Method|GPU memory required per GPU during training|Top1 Acc (%)|\n|-|-|-|\n|w/o original softmax|13.9 GB|79.6|\n|w/ original softmax| 15.8 GB (+13.7%)| 79.8|\n\n\n[1] Vitality: Unifying low-rank and sparse approximation for vision transformer acceleration with a linear Taylor attention. HPCA, 2023.\n\n[2] Castling-vit: Compressing self-attention via switching towards linear-angular attention at vision transformer inference. CVPR, 2023.\n\n**Q5: You mentioned that QTViT can exhibit a more focused and sharper response around Fig.2. Is there any insight about this phenomenon?**\n\nA5: Compared to linear Taylor attention and ReLU attention, our proposed method has a quadratic term, and thus can have a sharper response on input features with larger values, which means that QTViT concentrates more on important input features.\n\n**Q6: In Tab.1, the performance gains of QT-ViT 4$\\sim$6 to the SOTA are more marginal compared to QT-ViT 1$\\sim$3 to the SOTA. Are there any explanations for this phenomenon?**\n\nA6: First of all, the difficulty of increasing the classification accuracy from a baseline of 79% is different from that of 85%. The better the baseline method is, the more difficult to further improve its performance.\n\nSecondly, similar to EfficientViT B series and L series, QTViT 1$\\sim$3 and 4$\\sim$6 use different architectures as their baseline models. Thus, the proportion of attention operation is different in these two settings. Specifically, the ratios of FLOPs of attention blocks in QTViTs are shown below and we can see that the ratios in QTViT 4$\\sim$6 are much smaller than those in 1$\\sim$3. Thus, the proposed method will have a smaller impact on QTViT 4$\\sim$6, since we only modify the attention operation in the model.\n\n|model |ratio of FLOPs of attention blocks|\n|-|-|\n|QTViT-1|59.2%|\n|QTViT-2|62.1%|\n|QTViT-3|65.6%|\n|QTViT-4|25.4%|\n|QTViT-5|25.7%|\n|QTViT-6|25.6%|", "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": "O4UU5hjGob", "reviewer": "Reviewer_LZeB", "summary": "In this paper, the authors propose QT-ViT models, which improve the traditional linear self-attention methods by using a second-order (quadratic) Taylor expansion to approximate the original softmax attention and then accelerate this process using a fast approximation algorithm reducing computational complexity from $O(n^2d)$ to $O(nd^3)$ and further to $O(nd^2)$. This method leverages the properties of quadratic expansion for better performance while maintaining the speed of linear approximation. Extensive experiments on image classification, as well as object detection and semantic segmentation tasks, demonstrate that QT-ViT models achieve state-of-the-art accuracy-speed trade-offs, surpassing previous methods across various model sizes.", "questions": "Please see the weakness. The instability of accuracy is my major concern of this method.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "+ The paper introduces a novel method as it combines the benefits of quadratic expansion with a fast approximation algorithm, offering a fresh perspective on improving attention mechanisms without relying on knowledge distillation or high-order attention residuals.\n\n+ The paper provides a clear theoretical foundation for their method, explaining how the quadratic Taylor expansion and Kronecker product are utilized to reduce computational complexity. The theoretical analysis is solid and sound.\n\n+ The experiments on image classification, detection, and segmentation both show the effectiveness of the proposed method.\n\n+ The paper is well-written and structured.", "weaknesses": "+ In Table 1, the top 1 acc of the proposed QT-ViT models over EfficientViT appears to diminish. This trend raises concerns about the scalability and robustness of QT-ViT models as they are scaled up. The paper should include a detailed analysis of this trend.\n\n+ While Figure 1 effectively visualizes the latency of the models, the paper does not include this crucial metric in Table 1, The paper should include latency metrics in Table 1 to provide a comprehensive comparison of the models.\n\n+ Table 2 presents the results of using different kernels, but it is unclear whether all these kernels have the same time complexity. The paper should clearly state whether the time complexities of each kernel in Table 2 are the same. If not, the time complexity of each method should be added in Table 2.\n\n+ In Eq.11. the authors state that using the self-multiplication terms can effectively represent all quadratic terms. Could the authors provide more details for this finding?\n\n+ It seems that the improvement in segmentation is larger than in image classification and object detection. It is better to provide some analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1: In Table 1, the top 1 acc of the proposed QT-ViT models over EfficientViT appears to diminish. This trend raises concerns about the scalability and robustness of QT-ViT models as they are scaled up. The paper should include a detailed analysis of this trend.**\n\nA1: First of all, the difficulty of increasing the classification accuracy from a baseline of 79% is different from that of 85%. The better the baseline method is, the more difficult to further improve its performance.\n\nSecondly, similar to EfficientViT B series and L series, QTViT 1$\\sim$3 and 4$\\sim$6 use different architectures as their baseline models. Thus, the proportion of attention operation is different in these two settings. Specifically, the ratios of FLOPs of attention blocks in QTViTs are shown below and we can see that the ratios in QTViT 4$\\sim$6 are much smaller than those in 1$\\sim$3. Thus, the proposed method will have a smaller impact on QTViT 4$\\sim$6, since we only modify the attention operation in the model. This is the main reason that QTViT 1$\\sim$3 has a better performance over the baseline method than QTViT 4$\\sim$6 over the baseline method.\n\n|model |ratio of FLOPs of attention blocks|\n|-|-|\n|QTViT-1|59.2%|\n|QTViT-2|62.1%|\n|QTViT-3|65.6%|\n|QTViT-4|25.4%|\n|QTViT-5|25.7%|\n|QTViT-6|25.6%|\n\n**Q2: While Figure 1 effectively visualizes the latency of the models, the paper does not include this crucial metric in Table 1, The paper should include latency metrics in Table 1 to provide a comprehensive comparison of the models.**\n\nA2: Thank you for your advice. We will include the latency metrics in Table 1.\n\n**Q3: Table 2 presents the results of using different kernels, but it is unclear whether all these kernels have the same time complexity. The paper should clearly state whether the time complexities of each kernel in Table 2 are the same. If not, the time complexity of each method should be added in Table 2.**\n\nA3: Sorry for the unclarity. We have mentioned that we compare our method with other kernels used in various linear attention vision transformers in Line 212. These kernels are the kernel functions introduced in Section 2.3. Since they are all used for linear attention, the time complexity of each kernel in Table 2 is all the same and is O(Nd^2). We will further illustrate this in the final version of the paper.\n\n**Q4: In Eq.11. the authors state that using the self-multiplication terms can effectively represent all quadratic terms. Could the authors provide more details for this finding?**\n\nA4: In fact, as Table 3 shows, we have tried several different methods to reduce the number of quadratic terms, and using the self-multiplication terms yields the best result among all of the methods. Generally speaking, the quadratic terms can be viewed as a square matrix $\\bf M$ in which each element ${\\bf M}_{ij}$ represents the multiplication result of $x_i$ and $x_j$. Thus, the self-multiplication terms can be viewed as the elements on the diagonal of the matrix which can represent the whole matrix to some extent. Besides, we expand the self-multiplication results with respect to the number of quadratic terms and use a learnable parameter $\\alpha$ to further adjust the ratio. Thus, the overall method can represent all quadratic terms.\n\n**Q5: It seems that the improvement in segmentation is larger than in image classification and object detection. It is better to provide some analysis.**\n\nA5: In our research, we introduce a novel linear self-attention using quadratic Taylor expansion. Our experimental results on image classification tasks using the ImageNet 1K dataset show the efficacy of our method.\n\nWhile image classification focuses on assigning a single label to an entire image, segmentation is the classification task on the pixel level. Due to the similarity between these tasks, our method also has a good performance on segmentation.\n\nFor the object detection task, treating QT-ViT-1 as an example, although achieving a modest performance improvement compared to the semantic segmentation task, there is a smaller ratio of parameter (57.6M->57.9M, +0.5%) increase compared to the semantic segmentation task with parameters from 32.5M to 32.8M (+0.9%), which is reasonable.\n\nThe explanation above will be added in the final version of the paper.", "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:
The PDF contains the answer to Q7 of Reviewer QZCU that adds the latencies of different models on NVIDIA-V100 GPU, and the answer to Q3 of Reviewer dQG7 that adds the results of QTViT 1-3 and EfficientViT-L series into the figure.

Meta-review: This paper presents a method for improving the prior art of linear self-attention using quadratic Taylor expansion with a fast approximation algorithm. It has been reviewed by several knowledgable reviewers. The majority consensus from the reviewers (dQG7, LZeB and QZCU) was that the proposed fast approximation algorithm is novel and effective. The clarifications and new results presented during the reviewer-author discussion addressed their concerns raised in the initial comments. This meta-reviewer concurs, and recommends **acceptance**. 

The reviewer 5zgq had concerns mainly regarding the difference between the proposed method and some related work pointed out during the reviewer-author discussion. The authors and the reviewer 5zgq had very informative discussions. Although the authors did not finally convince the reviewer 5zgq, s/he did mentioned that the proposed concatenation of self-multiplication terms in the fast approximation algorithm is somewhat new. So, this meta-review leans towards looking at the positive aspects of the proposed method. 

The authors are encouraged to carefully revise their paper by,
- incorporating the clarifications, discussions, new results and new references; 
- providing comparisons on memory footprints that are missing in the submission and the discussions;
- providing more detailed analyses on effects between w/ APE and w/o APE in both image classification tasks and downstream tasks.
Decision: Accept (poster)