QT-ViT: Improving Linear Attention in ViT with Quadratic Taylor Expansion

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.

A1: 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.

Secondly, 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.

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.

A2: Thank you for your advice. We will include the latency metrics in Table 1.

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.

A3: 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.

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?

A4: 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.

Q5: It seems that the improvement in segmentation is larger than in image classification and object detection. It is better to provide some analysis.

A5: 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.

While 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.

For 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.

The explanation above will be added in the final version of the paper.

Q1: What is the dimension of $\alpha$, $\beta$ and $\gamma$ used in Eq.11? Are there any ablation studies using different parameters?

A1: $\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).

We 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.

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?

A2: 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$.

Q3: There are 6 models with different model sizes in Tab.1. Why do you plot only 3 models in Fig.1?

A3: 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.

Specifically, 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.

To 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.

If you feel it is necessary, we can add QTViT 1$\sim$3 back to Fig.1 in the final version of the paper.

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?

A4: 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.

[1] Vitality: Unifying low-rank and sparse approximation for vision transformer acceleration with a linear Taylor attention. HPCA, 2023.

[2] Castling-vit: Compressing self-attention via switching towards linear-angular attention at vision transformer inference. CVPR, 2023.

Q5: You mentioned that QTViT can exhibit a more focused and sharper response around Fig.2. Is there any insight about this phenomenon?

A5: 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.

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?

A6: 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.

Secondly, 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.

Q1: Overall improvement is incremental. Add results on ImageNetv2 and real.

A1: 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.

Note 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.

For 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.

Q2: Larger image resolution, and the computation cost and latency.

A2: 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.

Q3: Move det and seg results in the main text.

A3: 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.

Q4: The network architecture should be detailed, and absolute positional embedding should be ablated.

A4: 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).

The above results will be added to the final version of the paper.

Q5: Inconsistent mIoU results.

A5: 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.

As 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.

Q6: Provide more implementation details, experimental setting, and comparison with other methods.

A6: 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.

Q7: The latency on other type of devices.

A7: 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.

We 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.

Dear reviewer QZCU,

We appreciate your comments and suggestions in the review. All of your concerns in your original review have been addressed, including the overall improvement and results on ImageNetv2 and real, experiments on different image resolutions, ablations on positional embedding, experiments on semantic segmentation, and inference speed comparison on different devices.

We hope you can read the rebuttal and let us know if you have further questions. Thanks for your time.

Best,

Authors of paper 275

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.

A1: 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. Generally 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.

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.

A2: 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.

Q3: Some mathematical derivation can be moved to the supplemental section. For example, there are some redundant equations in Eq. 4, 6, 7, 9.

A3: 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.

These 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.

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.

A4: 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.

Q5: Missing linear attention vision backbone. For example, VVT (TPAMI 23).

A5: 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.

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.

A6: 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.

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.

As 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.

Dear reviewer 5zgq,

We appreciate your comments and suggestions in the review. All of your concerns in your original review have been addressed, including the clarity of second-order Taylor expansion, experiments on different image resolutions, mathematical derivation, inference speed, comparison with VVT and experiments on semantic segmentation.

We hope you can read the rebuttal and let us know if you have further questions. Thanks for your time.

Best,

Authors of paper 275

First of all, this paper directly used the conclusion of 2nd Taylor expansion from paper [a1] at the start of page 7. However, the conclusion in paper [a1] has some problems. For example, in page 6 in paper [a1], they have $d'=1+d+d^2$. However, the dimension of $\varphi(x)$ should be $(d+1)^2+1=2+2d+d^2$ which can be rigorously derived from Eq.8 in our paper. Besides, paper [a1] does not have any theoretical analysis and derivations to explain the dimension $d'$. Thus, we believe that our conclusion is correct.

Secondly, the acceleration of this paper is to utilize the hardware-efficient algorithm based on CUDA, which limits the utilization of its method and can only be accelerated on NVIDIA GPUs and is not able to be accelerated with other devices. The time complexity of their method is still $O(Nd^3)$, and mapping the input to lower dimensions as they used will yield bad results (see method 1 and 2 in Table 3 in our paper). Our method provides a fast approximation algorithm to reduce the time complexity to $O(Nd^2)$ and can be used without limitation.

Thirdly, this paper was published on Arxiv only two months before the deadline of NeurIPS 2024, thus we do not cite this paper or discuss it. We will add these discussions in our final version.

Thank you very much.

[a1] The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry. ArXiv, 2024.

Thanks for your comments.

1. If I understand it correctly, you are asking why using our fast approximation algorithm can well represent the second-order Taylor expansion. 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 ${\bf x}_i$ and ${\bf 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 to further adjust the ratio. Thus, the overall method can represent all quadratic terms.

2. The training speeds of EfficientViT and QTViT are shown below, in which we use a batch size of 1024. The inference speeds of different models on NVIDIA V100 GPU are shown in Figure 1 in the rebuttal pdf which is also used to answer Q7 from reviewer QZCU.

Hope these answers can address your concerns.

Dear reviewer 5zgq,

We appreciate you taking the time to review this paper. Since it is less than 10 hours before the deadline for the discussion phase, we hope that we have addressed all your concerns.

If you still have any questions, we are happy to discuss them with you. Thank you very much.

Best,

Authors of paper 275

The paper [a2] you mentioned does not solve any of the problems in [a1] that I mentioned above. In fact, they do not even cite the paper [a1]. This paper simplifies the second-order Taylor expansion to $\phi(x)=x^2$ as shown on page 5, and uses a linear transformation before applying the kernel function. Thus, their implementation is much simpler than the second-order Taylor expansion since they discard all other terms except for the quadratic term. There is no theoretical analysis to show the relationship between this method and the second-order Taylor expansion.

Thus, compared to this paper [a2], our contributions are concluded in the following:

1. We improve the linear self-attention using the correct quadratic Taylor expansion through rigorous theoretical analysis and derivations, while there is no such analysis in [1, a1, a2] and the conclusions they derive are either incorrect [1, a1] (see the dimension $d’$ I mentioned above) or has little connection to second-order Taylor expansion [a2].

2. We propose a fast approximation algorithm to reduce the time complexity of our method from $O(Nd^3)$ to $O(Nd^2)$, while they use methods such as reducing the dimension of input through the linear layer or using hardware-efficient algorithm based on CUDA, which have their own drawbacks as we analyzed previously.

3. These three papers [a1, a2, 1] are all published within 2-3 months before the submission deadline of NeurIPS 2024. Thus it is unfair to judge our novelty based on them according to the policy of the NeurIPS conference.

Besides, the contribution of the hardware implementation of different platforms is about the paper [1] you mentioned above rather than ours.

Hope the above analysis can address your concern.

[a2] Linear Transformers with Learnable Kernel Functions are Better In-Context Models. ArXiv, 2024.