Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representation

Response to further questions on efficiency

We thank the reviewer for the in-depth comments on further clarifications of the efficiency analysis. Below, we address the raised two points in detail. ### R.1 Efficiency analysis on large-scale datasets **Experiment setups and results** For ImageNet-1K and WikiText-103, we provide the training memory and time on a single V100 GPU in Table 1.1 and Table 1.2 below. In the experiment, we adopt the architecture of "Primal.$+$Backbone", where the last attention layer of the Transformer is replaced by our Primal-Attention. As in large-scale data and complicated tasks, less information compression can be desired in the learning, especially in shallow layers, we thereby implement our KSVD-based Primal-Attention in the deep layer. Relevant explanations can refer to the 1st paragraph in Sec.5 in paper. + *ImageNet-1K:* While attaining the same accuracy and an enhanced low-rank property (Fig.1 in the paper), the efficiency gain of our Primal.$+$DeiT-Small/16 is limited, as we only replace the last layer of the 12-layer baseline with our Primal-Attention. Hence, it is reasonable that the efficiency improvement is less significant than that of UEA and LRA where we either implement both layers in the 2-layer baseline by Primal-Attention ("Primal."), or replace the 2nd layer ("Primal.$+$"). + *WikiText-103:* Our "Primal.$+$Trans." shows similar efficiency as the 6-layer baseline, but significantly reduces the perplexity by $2.0$. Compared to the fine-tuned SoTA Flowformer (see Table 2 in our rebuttal), our "Primal.$+$Trans" is slightly inferior in perplexity by a small margin of 0.2, however, Flowformer is significantly less efficient by requiring $28.8 $% more running time than ours. The current "Primal.$+$Trans." is simply with default setups, better perplexity can still be expected by further tuning. **Table 1.1:** Efficiency analysis on ImageNet-1K. |ImageNet-1K|Top-1|Memory(GB)|Time(s/1K-steps)| |:-:|:-:|:-:|:-:| |DeiT-Small/16|79.8|14.2|2425.5| |Primal.$+$DeiT-Small/16|79.8|14.0|2330.2| **Table 1.2:** Efficiency analysis on WikiText-103. |WikiText-103|Perplexity($\downarrow$)|Memory(GB)|Time(s/1K-steps)| |:-:|:-:|:-:|:-:| |Trans.(2017)|33.0|9.0|3108.4| |Flow.(2022)|30.8|10.5|3998.4| |Primal.$+$Trans.|31.0|8.9|3104.0| **Further remarks** In summary, the efficiency gain of Primal-Attention implemented networks over baselines is influenced by two main factors: *1)* number of Primal-Attention layers used in the architecture, the more the better; *2)* sequence length of the training data, the longer the more significant. + With deep architectures, the efficiency can be further improved by replacing more layers with our Primal-Attention. Yet, in very deep Transformers, Primal-Attention is not necessarily always superior in performance when being applied to all layers, as the learning in shallow layers may not enjoy the benefits from the low-rank property from KSVD as much as the higher layers do. It would be interesting to explore a more generic implementation setup for Primal-Attention in very deep Transformers, as briefly mentioned in the last paragraph of possible future work in the Supplementary Material. + The length of the data sequence, i.e., $N$, is also a key influencing the efficiency. By avoiding the computation of the $N\times N$ attention matrix, our Primal-Attention can gain better efficiency on longer-sequence datasets. Although ImageNet-1K is large-scale, currently Transformers treat each image as a sequence of length 197 (with $\tt cls$ token), which is actually not too long (even compared to some UEA datasets as shown in Table 3 in our rebuttal). Hence, this is also a reason why our Primal.$+$DeiT-Small/16 does not improve the efficiency significantly. Similarly in WikiText-103, the data sequence length is 512, which is also not really long, hence the efficiency of our "Primal.$+$Trans." is not always superior under the current setups. ### R.2 Efficiency gain of "Primal.$+$" in different tasks The efficiency gain of "Primal.$+$" over baseline is more significant on UEA and LRA, as the backbone has only 2 layers, hence replacing one layer makes a difference to the overall architecture. Moreover, UEA and LRA in general have longer training sequence length, which would signalize Primal-Attention's efficiency. In contrast, the backbones on D4RL, WikiText-103 and ImageNet-1K have more layers where canonical self-attention layers are the majority structures in "Primal.$+$" as shown in Table 2.1 below. Besides, the efficiency gain is less significant also due to the shorter training sequence lengths on these datasets. Explanations can refer to the response R.1 above. **Table 2.1:** Architecture of Primal.$+$. |Primal.$+$|canonical_layer+[primal_layer]|num_head|head_dim| |:-:|:-:|:-:|:-:| |UEA|1+[1]|8|64| |LRA|1+[1]|2|32| |D4RL|2+[1]|4|64| |WikiText-103|5+[1]|8|64| |ImageNet-1K|11+[1]|6|64|

Further response to the benefits of left singular vectors

We thank the reviewer for the reply. We provide the following 3 aspects to address your concerns and eliminate possible confusions. ### 1. Projection scores involving left singular vectors are beneficial to the performance. For clarity, in Table R.1 we summarize the setups and architectures of Table 2pAx-1. We use the 2-layer backbone baseline commonly used on LRA. To make the ablation more comprehensive, we **respectively** conduct this study on the two main architectures in this work, i.e., Primal. and Primal.$+$Trans. (see the 1st paragraph of Sec.5 in the paper for details). **Table R.1:** Ablation setups on LRA. |Primal.|w/o $r$-scores|w/ $r$-scores| |:-:|:-:|:-:| |Layer 1|[right]|[right;left]| |Layer 2|[right]|[right;left]| |Avg. Acc.|45.6|**57.5**| |Primal.$+$Trans.|w/o $r$-scores|w/ $r$-scores| |:-:|:-:|:-:| |Layer 1|canonical attention|canonical attention| |Layer 2|[right]|[right;left]| |Avg. Acc.|59.4|**60.4**| The two subtables in Table 2pAx-1 are the ablation study of using the left singular vectors on **two different network architectures respectively**, so that their results are not directly comparable under the setups in this ablation. Therefore, it is not the left singular vectors that bring bad influence on the performance, and such evaluations should be considered separately in these two subtables. More specifically, 1. Using the projections of left singular vectors, i.e., (w/ $r$-scores), is helpful to the performance, when Primal-Attention is applied to all layers (Primal.) and also when it is applied only to deep layer (Primal.$+$Trans.). The role of the left singular vectors is more influential in Primal. for boosting the performance, where all canonical attention is replaced with the KSVD-based Primal-Attention. 2. As mentioned by the reviewer, Primal.(w/ $r$-scores) has inferior performance than Primal.$+$Trans.(w/o $r$-scores). This is due to: Primal.(w/ $r$-scores) applies low-rank KSVD to the first layer, where the learning in this shallow layer does not always desire for the low-rank property from KSVD as much as the deep layer does on LRA. ### 2. Performance gain is substantial. From the results of Primal.$+$Trans. in Table 2pAx-1, the mentioned performance improvement is substantial on LRA. 1. *We obtain 1% gain (59.4% $\to$ 60.4%) in average accuracy:* In Table 2 in paper, recent SoTA method YOSO-E has only 0.4\% gain compared to the baseline. Hence, 1% gain can be regarded as substantial on LRA. 2. *LRA benchmark should be evaluated as a whole:* Since there are five different tasks in this benchmark, the average accuracy is the most conclusive measure, which is also attached great importance by almost all SoTA methods. In Table 2 in paper, YOSO-E even has inferior performance on Pathfinder dataset than baseline. However, this cannot diminish its overall better performance on this benchmark. 3. *In each individual task, using both projection scores consistently brings improvement*: As in Table R.2, the accuracy gain is significant on at least 3 tasks: Retrieval, Image and Pathfinder; besides, using both projection scores consistently improves performances in all tasks, which is substaintial for the LRA benchmark. **Table R.2:** Acc.(%) gain of Primal.$+$Trans.(w/ $r$-scores) over Primal.$+$Trans.(w/o $r$-scores). |Primal.$+$Trans.|ListOps|Text|Retrieval|Image|Pathfinder|Avg.Acc.| |:-:|:-:|:--:|:-:|:-:|:-:|:-:| |Acc.$\uparrow$|0.2|0.3|1.8|1.1|1.5|1.0| ### 3. Necessity remarks 1. **Theoretically,** the derived KSVD can be regarded as a low-rank approximation to the self-attention kernel matrix where utilizing both left and right singular vectors leads to the optimal approximation. 2. **Experimentally,** using both projection scores brings substantial performance gain than using only one. 3. **Intuitively,** using both projection scores can be treated as considering both directions in a directed graph. Section 2 in the paper presents the asymmetric attention weight $K_{ij}=\kappa(\boldsymbol x_i, \boldsymbol x_j)=\text{softmax}(a(\boldsymbol x_i, \boldsymbol x_j))$ with $a(\boldsymbol x_i, \boldsymbol x_j)=\left<q(\boldsymbol x_i), k(\boldsymbol x_j)\right>/\sqrt{d_k}$. This shows that the attention kernel $K$ can be interpreted as message passing in a directed graph in relation to queries and keys, with asymmetric similarity measures $\kappa(\boldsymbol x_i, \boldsymbol x_j)\neq\kappa(\boldsymbol x_j, \boldsymbol x_i)$. Using only the right singular vectors means considering only one directionality, where additional information might reside in another directionality to enhance the learning on such an asymmetric kernel matrix. Useful references can be checked on page 128-129 in [1] for graph theory. In the asymmetric case, it is natural to consider directed information, i.e., both right and left singular vectors as in our case, for enhancing performance. [1] Estrada, E. "The structure of complex networks: theory and applications." Oxford University Press, 2012.