Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representation
Authors: Yingyi Chen
Qinghua Tao
Francesco Tonin
Johan Suykens
Venue: NeurIPS 2023 poster (2023)
Keywords: Self-attention
primal-dual representations
SVD
kernel method
asymmetry
transformer
TL;DR: We provide a primal-dual representation for the asymmetric self-attention in transformer that allows to avoid explicit computation of the kernel matrix.

Abstract: Recently, a new line of works has emerged to understand and improve self-attention in Transformers by treating it as a kernel machine. However, existing works apply the methods for symmetric kernels to the asymmetric self-attention, resulting in a nontrivial gap between the analytical understanding and numerical implementation. In this paper, we provide a new perspective to represent and optimize self-attention through asymmetric Kernel Singular Value Decomposition (KSVD), which is also motivated by the low-rank property of self-attention normally observed in deep layers. Through asymmetric KSVD, i) a primal-dual representation of self-attention is formulated, where the optimization objective is cast to maximize the projection variances in the attention outputs; ii) a novel attention mechanism, i.e., Primal-Attention, is proposed via the primal representation of KSVD, avoiding explicit computation of the kernel matrix in the dual; iii) with KKT conditions, we prove that the stationary solution to the KSVD optimization in Primal-Attention yields a zero-value objective. In this manner, KSVD optimization can be implemented by simply minimizing a regularization loss, so that low-rank property is promoted without extra decomposition. Numerical experiments show state-of-the-art performance of our Primal-Attention with improved efficiency. Moreover, we demonstrate that the deployed KSVD optimization regularizes Primal-Attention with a sharper singular value decay than that of the canonical self-attention, further verifying the great potential of our method. To the best of our knowledge, this is the first work that provides a primal-dual representation for the asymmetric kernel in self-attention and successfully applies it to modelling and optimization.

Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representation
Yingyi Chen ESAT-STADIUS
Qinghua Tao ESAT-STADIUS
KU Leuven, Belgium
KU Leuven, Belgium
yingyi. chen@esat .uu.eten..eeeeeeeeeee
tao@esat. gingeua.tao@esat kuleuven. be
Francesco Tonin
Johan A.K. Suykens
ESAT-STADIUS
ESAT-STADIUS
KU Leuven, Belgium
KU Leuven, Belgium
francesco. tonin@esat kul.uven. be
jo suykensesstt. wwt.ssatttuuleeue....a kuleuven. be
Abstract
Recently, line of works has emerged understand and improve self-attention in Transformers by treating it as a kernel machine. However, existing works apply the methods for symmetric kernels to the asymmetric self-attention, resulting a nontrivial gap between the analytical understanding and numerical implementation. In this paper, we provide new perspective represent and optimize self-attention through asymmetric Kernel Singular Value Decomposition (KSVD), which is also motivated by the low-rank property of self-attention normally observed deep layers. Through asymmetric KSVD, i) a primal-dual representation of self- attention formulated, where the optimization objective is cast to maximize the projection variances in the attention outputs; ii) novel attention mechanism, i.e., Primal-Attention, is proposed via the primal representation explicit computation of the kernel matrix in the dual; iii) with KKT conditions, we prove that the stationary solution to the KSVD optimization Primal-Attenn Attention yields zero-value objective. In this manner, KSVD optimization can be imple- mented by simply minimizing a regularization loss, so that low-rank property is promoted without extra decomposition. Numerical experiments show state-of-the- art performance of our Primal-Attention with improved efficiency. Moreover, we demonstrate that the deployed KSVD optimization regularizes with a sharper singular value decay than that of the canonical self-attention, further verifying the great potential of our method. To the best of knowledge, this is the first work that provides a primal-dual representation for the asymmetric kernel in self-attention and successfully applies it to modelling and optimization".
KSVD, avoiding
Introduction
Transformers [1] have become ubiquitous nowadays with state-of-the-art results in various tasks, such as natural language processing [2, 3, 4], computer vision [5, 7, 8J,, reinforcement learning [9, 10, 11], etc. In the remarkable success of Transformers, the self-attention blocks play a key role, where the complicated dependencies between the individuals in data sequences can be depicted by using the established queries, keys, and values. Despite the prevailing advantages, theoretical understandings towards Transformers seem yet lagged behind its unprecedented empirical performance.
"qqual contribution.
Our implementation is available at
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Overview layers [0.1,2.3]
Overview of layers [4,5,6.7] Overview layers (8.9.10.11]
DelT-Small/16
Normalized cumula-
tive singular valuee
1.0
1.0
-10
0.8
0.8
0.8
0.8
0.6
0.6
DeiT-S/16
Layer
0.4
0.4
0.4
DeiT-S/16, 1/11]
DeiT-5/16
0.2
DeiT-S/16
0.2
Primal.+
Primal++
Primal.+
Primal.+, L[13]
0
50
100
150
196
0
50
200
150
196
50
100
150 196
50 100 150 196
Singular value index
Singular value index
Singular value index
Singular value index
(a)
(b)
(c)
(d)
Figure/ I: Spectrum analysis of the self-attention matrix ImageNet- KK [23]. (a)-(c) plot the
cumulative explained variance regarding the singular values of the attention matrix with mean and standard deviation of the chosen layers in pre- pre-trained DeiT- Small/16 [7] and Primal. -mall/11 (ours): the attention matrix attains sharper singular value decays in deeper layers, also shown in (d). Note that also plot the cumulative explained variance curves of the self-attention matrix from the last layer, i.e., the 1 11tth layer denoted by "L[11]", of both models in (c). Our method shows an enhanced low-rank property of the attention matrix upon the baseline.
Recently, the kernel-bases based perspective has been proposed where the dot-product attention opera- tion shown as kernel matrix [12]. This finding quite encouraging by bridging kernels [13] with Transformers,
kernel methods have long been well studied with good interpretation ability. Following this spirit, different works have been proposed subsequently
improve self-attention, e.g., [14, 15, 16, 17, 18, 19]. However, in these works, the applied kernel techniques rely on Mercer kernels [20] requesting symmetry, which is inconsistent with the intrinsically asymmetric setups of self-attention. In [21]. it analytically characterizes the attention by asymmetric kernels based on Reproducing Kernel Banach Spaces (RKBS) [22]. Nonetheless, neither the asymmetry property nor the related optimization is utilized for improvements. In [19], self-attention is derived with a primal-die representation from the support vector regression, which still adopts the technique for Mercer kernels. Moreover, in the cast supervised task, the assumed ground-trutt outputs of self-attention are practically non-existent, making it difficult to be applied in the optimization.
In this work, we provide a novel perspective to interpret self self-attention with primal represen- tation based on asymmetric Kernel Singular Value Decomposition (KSVD), which fills the gap of dismissing the asymmetry between theory and implementation. Specifically, in this unsupervised setup, we propose to remodel self-attention the primal representation, namely, Frimal-Attention and to optimize it accordingly. Our method is driven by two major motivations. Firstly, we observe that attention matrices Transformers can low-rank, as shown in Figure I(d), and this property becomes more significant towards deeper network layers. Secondly, the self- self-attention matrix is intrin- sically an asymmetric kernel matrix [12, 21j. To this end, we propose KSVD for self-attention, which takes both low-rank and asymmetric properties into consideration. To the best of our knowledge, this is the first work that provides a primal-dual representation for the asymmetric self-attention and applies it to modelling and optimization. The contributions of this work summarized as follows:
We characterize self-attention by KSVD with asymmetric kernels. Different from existing works employing symmetric kernel-based methods, we take asymmetry into account as to be more consistent with the real setups in self-attention. (Section 2)
We derive a primal-duse representation for self-attention through KSVD, and propose a novel attention in the primal, named Primal-Attention avoiding the expensive kernel computation in the dual. With KSVD, the values are interpreted as the projection weights that yield maximal variances of features, and the low-rank property can be pursued by confining the projection numbers. (Section 3, Section 4)
We prove that the stationary solution to the derived KSVD leads to a zero-value objective of the unconstrained primal problem. Therefore, the optimization of KSVD in Primal-Attention can be efficiently implemented by minimizing a regularization term added to the loss, with need of extra decomposition operations. (Section 4)
In numerical experiments, Primal-Attention achieves sate-of-the-art performance on various datasets together with efficiency advantages over the canonical self-attention. Moreover, we demonstrate that our deployed optimization from KSVD can regularize the attention with

---

sharper singular value decay, hence promoting learning more low-rank features, which is shown in Figure 1. (Section 5)
2 Problem Statement: Self-attention with Asymmetric Kernel
Self-attention Let {æ; E ) be the input data sequence. In self-attention [1], the queries, keys and values output the linear projections of the input sequence, such that
(I) where W, E Rd,xd, W E Rddedd and W, E Rdlxdd commonly with the setup dg = dg- The attention scores are then given by a(z,, 2;,) (q(x;), h(x,))/ = (W Wxaz)) /dd.. In the canonical self-attention, the "softmax" activation is then applied bring non-linearity and positives, yielding the attention weights:
((xx)) W,s (xxx)) Wy v(xx,) W.
<(2;; 2T) = softmax (WWT. (aa,) dx
i,j= N.
Similar to [12], the attention matrix, i.e., K == [m(2; و,]] E N can be interpreted as a kernel matrix with entries k(z,,,)) where x(;,)): Rdd x Fd I serves as the kernel function. Notice that in general, (Wa Wa.z)) + (Waz), Wga,), leading to an asymmetric kernel where Kij & Kji.
Then, the attention output o; E dR in each head is attained as:
.V ش-ر
N Σ
( mm mi m.)
Ka) i= i=.,..., N.
In Transformers, multiple heads are commonly applied through the concatenation of all heads [l].
Asymmetric Attention Matrix In kernel methods, rigorous works have been presented with Mereer kernels that are symmetric and positive semi-definite [20] through the kernel trick from Reproducing Kerne Hilbert Spaces (RKHS) [13]. On the other hand in Transformer [1]. the attention kernel matrix asymmetric as shown (2). Existing works leverage the kernel interpretation for improving self-attention [14, 17, 18, 191, however, their deployed kernel-based techniques all rely on Mercer kernels, which is inconsistent with the asymmetric nature. Instead, asymmetry is allowed in kernel tricks from Reproducing Kernel Banach Spaces (RKBS) [22] as in the following Definition 2.1.
Definition 2.1 (Definition [21]; Theorem 2.1 [24]:[25]) For asymmetric kernels, the kernel trick from RKBS with the kernel function k(:,-): X 2 + R can be defined by the inner product of two real meusurable feature maps from Banach spaces Bx, Bz on X, 2, respectively:
k(xx 2) (2). Vx X, Oz E Bx, E 2, 0. Bz.
Based on Definition 2.1, the kernel matrix in self-attentin can be characterized by the kernel trick from RKBS [21], providing an analytical tool from the aspect of kernel representer theorem.
SVD and Shifted Eigenvalue Problem SVD factorizes given r-rank matrix A E N by two sets of orthonormal eigenbases: A = UEVT with [ .., o,) of positive singular values and the columns of U E Nxr and V E R Afxr as the left and right singular vectors, respectively [26]. U. V reflect the subspace projections in relation to the columns and rows, as shown (5), and contain different information residing in A due to the asymmetry. When A is squared and symmetric, SVD boils down to the eigendecomposition with U = V. [27]. a novel variational principle is proposed for SVD with Least Squares Support Vector Machines (LSSVM) [28], where the dual problem leads to a shifted eigenvalue problem in accordance to the decomposition thcorem from Lanczos [29] regarding SVD, i.c., Theorem 2.2. This theorem is also of special importance in our work to the kernel extension of SVD in self-attention under the framework of LSSVM.
Theorem 2.2 (Lanczos [29]). Any non-zero matrix A E R NxM can be written = Ü.VT,
where the matrices U, Σ, V are defined by the shifted eigenvalue problem:
AV UΣ, A Ā = VE. where t Nxr and V E Mr satisfy ÔTÜ I, and VTV= = Ir. and E. E R.xr a diagonal
(5)
matrix with positive numbers.
3

---

3 Primal-dual Representation of Self-attention based on Kernel SVD
In this section, we apply the kernel trick from RKBS to the asymmetric attention kernel, and derive self-attention with primal-dual representation based on Kernel SVD (KSVD). Under this Icarning scheme, new self-attention mechanism is proposed by remodelling the attention output in the primal representation, without explicit computation of the kernel matrix in the dual representation. With the stationarity conditions, flexibly implement the optimization of KSVD through additional loss term, which can regularize the model to improved low-rank properties without extra decomposition.
KSVD optimization problem in Primal and Dual By Definition 2.1 of RKBS, the kernel function in the dual for the asymmetric attention kernel K in self-attention can be formulated by K; = k(1;,, x.y) == (d)()))), di (xx)))), with two feature maps Qq. &% related to queries and keys. Recall the self-attention output in (3), the values {u(2,)), resemble the dual variables projecting the kernel matrix in the dual representation of kernel methods, whereas the kernel involved is asymmetric. In this regard, the nonlinear version of SVD under the framework of LSSVM [27] well fits the self-attention setup, hence is set as the basis for the following work with asymmetric kernels built upon RKBS. Differently, we extend the matrix SVD setups in [27] to the case of asymmetric attention matrix with two input data sources as queries and keys. Moreover, we consider that in self-attention, values are input data-dependent, and thus generalize [27] with data-dependent projection weights.
Given the sequence {æ; E IR. I. we start from the primal optimization with KSVD:
= 2 -i e, Ae, +
1
Σ 2== r. Ar, - Tr ( W.)
max W. W..
2
(6)
s.t.
e; (f(X) We) (x:), i i= I....,N. N.
rj (f(X) WW, (x(=)), j = I,,..,,
where we have the data- dependentt projection weights f(X) We =: Waix E Roxx ((() =: Wrix E _gxx relying on parameters We, Wr NR, the feature maps (,(+), oz Rd R", the projection scores e,, ry E IR,, and the regularization coefficient A E R which is a positive diagonal matrix. The objective J in the primal optimization maximizes the projection variances of x & (z:), WTTxx0 Φx (2z)) regarding queries and keys, and also involves a regularization term coupling the projections. The corresponding solution in the dual is characterized by the right and left singular vectors, which captures the directions with maximal projection variances, w.r.t. rows (queries) and columns (keys) of the attention kernel matrix. Thus, with the formulated primal optimization in (6), the learning in self-attention is interpreted as SVD problem the attention matrix.
For clarity, we elaborate our primal optimization problem in (6) as follows. i) The projection weights are data-depen,,nt, where fXX =: Fx E E. xp denotes transformation matrix containing the information of the sequence data X == [æ1..... ØN] E IR xdd, Notably, Fx is constant matrix once given X, and we let linearly depend on X in experiments. Moreover, when F'x is chosen the identity matrix, it reconciles to the common setups in kernel methods in primal. ii) The feature maps related queries and keys, respectively, are defined as (3(2),) =- Bg (g(x:)). (2;)) = g (kxx))) where (+) d - IP" and (+)-)) Fd - E. denote the mappings composited on the linear projections g(-) and kc(-) in (1) of queries and keys. Note that we leave the choice of 9g and 9a later explained in Remark 4.1. lii) By projecting dyy (xx), (x, E E2 with weights Walx, + E & we obtain the projection scores C;, ry E IR along the s directions, usually s < p. which corresponds to the number of singular values of the induced kernel matrix in the dual optimization (7).
Remark 3.1 (Variance maximization objective). In the formulated KSVD problem, the objective in (6) jointly maximizes the variances of the two projections es, r in the feature spaces determined by Dg &r along the directions Wexx, W, x- Within this context, e; Tÿ learn to capture maximal information mutually residing in 6g and de regarding the queries and keys.
the primal optimization
With Lagrangian duality and KKT conditions, we prove that the dual optimization problem to (6) leads to a shifted eigenvalue problem corresponding to the SVD on the asymmetric attention kernel K, given by Theorem 3.2. The proof is provided in the Supplementary Material.
Theorem 3.2 (Dual optimization problem of KSVD in self-attention). With Lagrangian duality and the KKT conditions, the dual optimization problem of (6) leads to the shifted eigenvalue problem:
K H HoW.,
KT H = H,Y.
4

---

Dual representation (canonical self-attention)
Primal representation (ours)
batsh dim
d(
batch dimi
O(Nps)
(000xx00)
N
83
83
Pxn N
I Nxd
N
83
X
83
(x)
Weix
Wrix
K [x))
vXX)
(x)
v(X)
4 (X)
(xxX)
An illustration of Primal-Attentins and canonical self-attention. Left: in canonical self- attention, the asymmetric attention matrix K can be induced by two feature maps dg. Øy through kemel trick from RKBS. The values (X) serve as the dual variables projecting the kernel matrix K to the attention output. The time and space complexity are O(N2d,) d.) and O + Nd.).. Right: in our
Figure 2:
we use the two feature maps Og. Ω% in the primal to present the attention outputs, which are projected through the primal variables W Wexx. W Wrix- The time and space complexity are ps) and (2Np + 2ps). To align with the output size in the canonical self-attention, we add a linear map mapping from 2s to dy with negligible memory increase after Primal-Attentie ' output.
where E E Raxa is a positive diagonal matrix, and He = [he....., hex] [ E RN Hr [hr....., Nyw]" E Nx are the dual variables serving as the left and right singular vec- tors, respectively. The kernel trick the asymmetric kernel matrix K is interpreted as Kij (xx))) (k())) (k(z;))) ((,( 0% (a;)).
As shown in Theorem 3.2, the solutions collect non-zero A in (6) such that Σ = A-1 Based on Lanczos' decomposition in Theorem 2.2, we can then associate Σ with the non-zero singular values of the attention kernel K in (7), and He, H, with the left and right singular vectors of K, such that K = H,DH,, Therefore, formulas (6) and (7) provide the optimization problems of performing KSVD with the attention kernel matrix K in the primal and in the dual, respectively.
Self-attention as KSVD dual representation Firstly, we provide the primal model represen- tation of the derived KSVD problem. Secondly, we show that the dual representation of the model corresponds to the canonical self-attention. The derivation details involving the KKT conditions are provided in the Supplementary Material.
Remark 3.3 (Primal-dual representations of KSVD in self-attention). In the KSVD formulations for the asymmetric kernel matrix in self-attention, with KKT conditions, the projection scores can be either represented in the primal using feature maps or in the dual using kernel functions:
{ e(x: = WT (x)) r(x) W r (x())
e(xx) = -x
1= hr, k(xx,
Primal:
Dual:
(8)
r(z)= ke x)).
Remark 3.4 (Correspondence of KSVD and canonical self-attention output). Recall the output og of canonical self-attention (3), it corresponds to the dual representation of the projection score e(xx) in (8), iee, & e(xx). When the values {u(x;)), f= in canonical self-attention chosen as the dual variables ( i.e. hr, v(xz), j L,...,,, the right singular vectors of K.
N, the values {u(x;))) play the role of
From the perspective in Remark 3.4, the optimization goal in self-attention is interpreted to jointly capture the maximal variances of e,, ry as in (6), where the projection scores can be denoted as e; = e(xx), ry = r(x,) through the representations (8). However, the canonical self-attention only outputs the e,-score (o, - e.). In this sense, the output of the canonical self-attention only considers the projection scores involving the right singular vectors of the asymmetric attention kernel K.
4 Primal-Attention
quite remarkable that the attention output can be equivalently represented without the kernel expressions, avoiding the heavy computation of the kernel matrix. Within the context of KSVD, we further observe that there exists another set of projections ry regarding the left singular vectors in leg in (8), providing extra information residing in the asymmetric kernel matrix K.
Modelling
5

---

We derive a novel attention mechanism by leveraging the primal representation of KSVD, namely, Primal-Attentions where two explicit feature maps og. Q: are adopted. To fully exploit the asymmetry in the kernel matrix of self-attention, Primal-Attention concatenates the two sets of projections using both left and right singular vectors, and thus formulates the attention outputs as follows:
O, = [e;;
Waxxx & (z,);; W x de (m:) [W] 1(X),, (q(2:)); W,, f(X)gx (M(2;)) (9)
In Attiatn,,t,niin,, the projection weights Waxx: W,ix in the primal play the role as the counterparts of the values in the dual. Given f(X) Fx an identity matrix, our KSVD problem in (6) boils down to the data-ima data-independent projection weight case as in [27], which can thereby be regarded as a special case of our derived KSVD in
In this case, the kernel trick in the asymmetric attention kernel becomes Ki- = (9.))()))) gl (k(z,))) = (xi,
Remark 4.1 (Choices of dg. or for non-linearity). The canonical self-attention adopts softmax for introducing non-linearity the attention score matrix; within our setups and kernel trick, it can be viewed as: k(2,, x3)) DD1 (3:() (xx)))) where (g(x)) = g(g(x))), @u(x) == z)...., exp(w, 2)), w; ~ NO, Ia,)) and dg = da [14], and D := diaglo, (X) (ox (X) 1x)). The projection scores then correspond to e(z) = D-1/2WT c|xx =| (x(x) and r(x) D 1-1/3
g(k((z)) with g(z) == 1xxp==1=11//)(xxpppppp
e)x__.,xp((1,,
r|x dn (x)). In this case, two exponential feature maps need
to be constructed and the normalization factor D all samples needs to be computed. In this paper, we consider feature maps related to the Cosine similarity kernel on queries and keys, such that 0g(x)= 0g(g(x)) == (<))/ ///l[=))))) (x) l/2 and (x(x=) gs (k(x)) == k(x)/ [[<(a) l2 in all experiments. It is easy to implement and able to bring both non-linearity and normalization to the feature maps.
Optimization The KSVD problem can either be optimized in the primal as a constrained opti- mization problem, or in the dual as a shifted eigenvalue problem (SVD on the kernel matrix K). In Primal-Attention, we perform the optimization in the primal. In the following Lemma 4.2, prove the zero-value property of the primal optimization objective J in (6) when it is evaluated at the stationary solution in (7). The proof is provided in the Supplementary Material.
Lemma 4.2 (A zero-value objective with stationary solutions). The solutions of He, Hy E to the shifted eigenvalue problem in the dual optimization (7) lead to the zero-value objective J in the primal optimization (6).
With the property in Lemma 4.2, rather than solving SVD problem on the kernel matrix K in the dual, the optimization of Primal-Attentinn is realized by minimizing the primal objective to zero:
min L+ Σ J..
(10)
where L is the task-oriented loss, e.g., the cross-entropy loss for classification tasks, the summation term over I denotes the additive objectives Ji of all attention blocks using the proposed Primal- Attention, where Jj is implemented as the mean over all heads, and 17 > 0 is the regularization coefficient. Specifically, for each head in the self-attentin using Primal- rimal-Attention. we have
J(W,, W A) = 1 EN e, Aet + Σ Ar Tr (W. W.) IKW 1BB Tr (T. W,),
(1I)
= -.
where A is automatically determined by the optimization. KSVD optimization of Primal-Attention is easy to implement by adding a regularization loss. Hence, Primal-Attention not only represents self- attention with KSVD formulation in the primal, but utilizes the optimization of KSVD by regularizing the attention, satisfying the stationarity conditions of KSVD when reaching a zero-value objective.
5 Numerical Experiments
In this section, we verify the effectiveness of our Primal-Attention applied in Transformers on five well-established benchmarks: time series, long sequence modelling, reinforcement learning, image classification and language modelling. Notably, we consider two types of Transformers applied with our Primal-Attention, i.e., PrimalFormer (Primal.) and Primal. i) In PrimalFormer, Primal- Attention (9) is applied to all attention layers, regularized with the KSVD loss (LI). This setup is

---

Table I: Test accuracy (%) on the UEA time series classification archive benchmark [31] with compar- isons to canonical Transformer (Trans.), Linear Transformer (Linear.), Reformer (Re.), Longformer (Long.), Performer (Per.), cosFormer (Cos.), Flowformer (Flow.), YOSO-E and SOFT.
Trans.
Linear.
Re.
Long.
Per.
YOSO-E E
Cos.
SOFT
Flow:
Ours
Dataset/ Model
[1]
[33]
[34]
[35]
[14]
[36]
[37]
[38]
[11]
Primal.
Primal + Trans.
EshanolConcenttatioo
32.7
31,9
31.9
32.3
31.2
31.2
32.3
33,5
33.8
33.1
35.4
FuceDetection
67.3
67.0
68.6
62.6
67.0
67.3
64.8
67.1
67.6
67.1
63.8
HandWrittng
32.0
34.7
27,4
39.6
32.1
30.9
28.9
34.7
33.8
29.6
28.7
HeartBeat
76.1
76.6
77.1
78.0
75.6
76.5
77.1
75.6
77.6
76.1
77.1
Japanese Vowels
98.7
99.2
97.8
98.9
98.6
98.3
99.2
98.9
98.4
98.9
PEMS-SH SF
82.1
82.1
82.7
83.8
80.9
85.2
83.2
80,9
83.8
89.6
90.2
SeIfRegulatioSSCP
92.2
92.5
90.4
90.1
91.5
91.1
91.1
91.8
92.5
92.5
92.5
SelfRegulationSCPP
53.9
56.7
56.7
55.6
56.7
53.9
55.0
55.6
56.1
57.2
56.1
SpokenAraaicliiits
98.4
98.0
97.0
94.4
98.4
98.9
98.4
98.8
98.8
100
100
LWvrrrestueLibbrryy
85.6
85.0
85.6
87.5
85.3
88.4
85.6
85.0
86.6
86.3
88.4
Average Accuracy
71.9
72.4
71.5
72.0
71.9
72.2
71.5
72.2
73.0
73.0
73.1
Table 2: Efficiency comparisons running time and memory consumption the UEA bench- mark [31] where running time (s/Epoch), the peak training memory usage (GB) are given. We report how much faster and how less memory each model uses than Transformer.
Dotect//
Ribandd.
Fasz.
Hard
Haar:
lap
PFMS-SF
SCP)
Arshic
UWne
Ang. Time
Memory (GB)
say kmngh
62
144
196
1152
83
(#Fpuch)
10.71x)
030x)
070g)
06:1x)
k7(1s)
25(0k)
(0.9
Aboc: [1]]
(..1)
03:00))
070.00)
06/08x)
0.70.9x
14113))
13(14))
44:08))
030.00)
22(11
Primal-- Trans
(.3)
033000)
020.0
(5(1.0))
0.7009x)
16011)
16
40:099)
03(.04)
19133)
65.17
Primal.
(13
(..6)
04/08X) B4018))
O.(L0X) 0.600.5))
14033)
130.4k)
45/08x)
(.4088%)
19(13%)
27140x)
preferred when data shows relatively strong low-rank structure or the model redundancy is quite substantial. ii) Primal.+ refers to the baselines from the Transformer family with the last layer replaced by our Primal-Attention,, which is in favour in large-scale data and complicated tasks where less information compression is desired in the learning, especially in shallower layers. To specify the Transformer backbone, we denote our method by "Primal. + herein. Primal.+ serves as a flexible variant combined with different Transformer backhones, and with KSVD optimization applied through an implicit low-rank regularization loss, advocating to learn more informative features, as in of our method are the coefficient 7) in (10) and the number of projection directions of KSVD in (6). In data-dependent cases with f(X), ) we take a subset of X by uniformly sampling n min( s 10, N) points from X for efficiency aspects, as the main patterns of a matrix can be retained with random linear projections shown by the Johnson Lindenstrauss lemma [30]. Details are given in the Supplementary Material.
Figure 1. The two main
UEA Time Series Classification UEA Time Series Classification Archive [31] the benchmark for the evaluation on temporal sequences. Following [1i]. we select 10 multivariate datasets with pre-processed data according to [32], and employ 2-layer Transformer as backbone with the hidden dimension 512 on 8 heads and the embedding dimension 64 for self-attention. The
search of our method is with 7) E {0.1, 0.2, 0.5). E {20, 30, 40). Experiments are run on one NVIDIA Tesla P100 SXM2 16GB GPU.
Table 1 reports the test accuracy of the compared recent methods, where the best result is in bold. Both our PrimalFormer and Primal. achieve comparable and better performance than the state-of-the-art results provided by Flowformer [11]. Notably, Primal.+ yields the best accuracy with 1.2% overall improvement upon the canonical Transformer [1], i.e., by replacing the softmax-based self-attention with our Primal-Attention in the last layer. This shows the promising potential of Primal-Attention in enhancing temporal modelling capacity upon the canonical softmax self- celf-attention. It is worth mentioning that our PrimalFormer applying the KSVD optimization with low-rank regularization to all layers also obtains good performance. This could be due to the fact that these datasets are relatively simple where model redundancy can exist, so that appropriately imposing the low-rank regularization in KSVD does not harm the model expressiveness for the data. We also compare the running time and memory consumption with the canonical Transformer and Flowformer, which is proposed recently with sfate-of-the-arr performances and efficiency. Both our Primal. and Primal.+Trren consistently lead to improved efficiency than the canonical Transformer. In Primal., all attention layers are implemented with the proposed Primal-Attentin while + Trans. applies the
7

---

Table Test accuracy (%) on the LRA benchmark [39] with comparisons canonical Transformer (Trans.), Reformer (Re.), Performer (Per.), Linformer (Lin.), Nyströmformer (Nyström.), Longformer
(Long.) and YOSO-E.
Dataset (seq. length)
Trans.
Re.
Per.
Lin.
Nystrüm.
Long.
YOSO-F
Ours
[1]
[34]
[14]
[46]
[45]
[35]
[36]
Primal.
Primal. + Trans.
ListOps (2K)
37.1
18.8
37.3
37.2
37.2
37.3
37.3
37.3
Text (4K)
65.0
64.9
63.8
55.9
65.5
64.6
64.7
61.2
65.4
Retrieval (4K)
79.4
78.6
78.6
79.4
79.6
81.0
81.2
77.8
81.0
Image (IK)
38.2
43.3
37.1
37.8
41.6
39.1
39.8
43.0
43.9
Pathfinder (IK)
74.2
69.4
69.9
67.6
70.9
73.0
72.9
68.3
74.3
Average Accurney
58.8
55.1
53.6
55.6
59.0
59.0
59.2
57.5
60.4
Table 4: Efficiency comparisons on running time and memory consumption on LRA [39].
Model
Time (s/KK steps)
Memory (GB)
LeuOps
Text
Retrieval
Image
Pathinder
ListOps
Test
Retrival
Image
Pathinder
Trans [1]
(13)5
60433 (1x)
1333.7 (1x)
333,5(13)
(1x)
(350(11))
[1x)
(1x)
(188(xx)
(1))
Nystnim. [45]
(2.8x)
120.9 (5.7x)
255.)(57%)
(1.90
22..20..3)
0.89(6.2x)
1.69
3.29 (5.7x)
1995
1993 (3.0x)
[46]
63.413.1x)
136.5 (6.0x)
(5..2
(2.152
22.00
1.73 (3.2%)
3.51662k)
6.33 (3.0x)
3..5
14450
Per. [14]
(2.3x2
157.5 (4.4))
211411.6x)
278.1 (15xg)
1.57 (3.30)
33416.4x)
6.28 (3.0x)
(.84
17.012.2xx)
108.5 (4.1x)
339.9(3.9x)
(1.5%)
256.7 (1.4x)
(.34
(.29
6.09 (3.1x)
(.89
(189
Primal.- Trans,
(1.7x)
(245) 967.611.--)
212.1 (1,x2)
5.200.100
20.7(1.)))
(8.59(10x))
(35(111)
(1.
Primal. 56.3 (3.4x))
98.67744)
(8..3
142.9 (2.3x)
180.0/2.3x))
0.09 (7.9k)
(1588)
(6.x))
1,39 (4.2%)
(.90))
in the last layer, making Primal. more efficient model. We note that our Primal. further surpasses Flowformer in most cases regarding both running time and memory.
Long-Range Arena Benchmark Long-Rane Range Arena (LRA) [39] is a benchmark for the long- sequence scenarios, including equation calculation (ListOps) [40], review classification (Text) [41], document retrieval (Retrieval) [42], image classification (Image) [43] and image spatial dependencies (Pathfinder) [44]. We follow the settings in [45] with PyTorch. The Transformer backbone is set with 2 layers, hidden dimension 128 with 2 heads and embedding dimension 64 with mean pooling, where Reformer (Re.) uses 2 hashes, Performer (Per.) has 256 random feature dimensions and Linformer (Lin.) uses a projection dimension of 256. Our hyper-parameter set from vj E {0.05, 0.1), E 300,30). Experiments are conducted on single NVIDIA Tesla V100 SXM2 32GB GPU.
From the reported top-1 test accuracy in Table 3, our PrimalFormer shows better accuracy while achieves top efficiency (see Table 4) than several efficient self-attention counterparts including Reformer, Performer and Linformer. Notably, our model + achieves the state-of- the-art accuracy of 60.4%, which is 1.6% higher than Transformer, and 1.2% higher than the currently best YOSO-E, showing that the deployed Primal-Attentinn upon canonical Transformer distinctively. On top of it. Primal.+Trans. has distinctively higher efficiency and require much less memory than the canonical Transformer as in Table 4, and our Primal. outperforms all compared variants of efficient Transformer. Compared to Table I with simpler data, Primal.+ Trans. further achieves performance gain over PrimalFormer. The reason can be that the shallower (the first) layer needs more model capacity for depicting the data patterns in the learning, while the deep (the second) layer captures less detailed features and is regularized with more informative feature learning through our Primal-Attenien The efficiency of our Primal-Attentin are further pronounced with longer sequences than that of the UEA benchmark in Table 2.
is able to boost the performance
Reinforcement I Learning We consider the offline reinforcement learning (RL. performance of our methods on D4RL benchmark [47] designed for continuous control tasks. We choose three different environments controlling the robot movement: HalfCheetah, Hopper and Walker. Our experiments are conducted on three datasets pre-collected under different policies: Medium-Expert, Medium and Sediumm-Replay We follow the experimental settings in Flowformer [11], and also compare to Decision Transformer (DT) [10] which is commonly considered as the baseline with state-of-the performances based on the canonical attention. Note that offline RL is an nugo-regressive task and our Primal-Attention is adapted to its causal version, as described in the Supplementary Material. We adopt the architecture of 3 layers, hidden dimension 256 with 4 heads, and the embedding dimension 64. Our hyper-parae ppper-paraeetess are set as 1) = 0.05, 8 E (32, 64, 96). Each experiment run with different seeds one NVIDIA Tesla P100 SXM2 16GB GPU.
8

---

Table Rewards on D4RL [47] datasets. We report mean and variance for seeds. A higher reward and lower deviation indicates better performance. We consider Decision Transformer (DT), Linear Transformer (Linear.), Reformer (Re.), Performer (Per.), cosFormer (Cos.) and Flowformer (Flow.).
DT
Linear. [33]
Re.
Per.
Cos.
Flow. [11]
Ours
Dataset
Environment
[10]
[34]
[14]
[37]
Primal++
HalfChoctah
83.8=3.3
78.2+3.2
815+1.6
85.1+2.11
85.5+2.9
90.8=0.4
77.8=22.1
Medium
-Expert
Hopper
104.0:2.55
107.2400.9
104.249.8
93.5+13.9
98.147,4
109.9=1.0
111.540.2
Walker
107.740..6
67.2+:7..3
714418
72.642.4
100.5=14.5
108.0:0.44
108.9:0..
HalfCheetah
42.4=0.1
42.3++02
42.2+0.11
42.1+-0.2
42.1+0033
42.2+0.2
43.0+0.0
Medium
Hopper
64.2=111
58.740.4
59.9=0.7
59.747.5
59.843.8
66.942.5
74,5400.6
Walker
70.6=3.2
57.9+10..6
65.8+4999
63.3+10.7
71.4+122
71.7+2.5
77.97788
HallCheetah
34.6++0.6
32.1+1.5
33.6+0.7
31.7++0.9
32.8+3.6
34.7++1.5
38.+0.4
Medium
Hopper
79.7=7.4
74.3+7.0
66.1=2.6
64.6+24.2
59.3+16.55
15.5++1..5
88.5=12.5
-Replay
Walker
62.9+5.0
62.1+7.4
50.1+3.5
61.3++6.77
60.5+99.
62.0++311
76.8+10.3
Average Reward
72.2::266
64.416.55
63.9-1.99
63.817.66
67.817.6
73,51:2.9
77.51.6.0
Table 6: Efficiency comparisons on running time (s/IK~steps) and memory (GB) on D4RL [47].
Medium Medium-Expert
Medium
Medium Mcdium-Replay
Model
Time
Memory
Time
Memory
Time
Memory
DT (average reward: 72.2)
20.8
0.3
20.8
0.3
20.8
0.3
Flow. (average reward: 73.5)
54.4
1.5
54.4
1.5
54.3
1.5
Primal. DDT (average reward: 77.5)
23,5
0.3
23.4
0.3
23.3
0.3
Results in Table 5 demonstrate that our Primal.+ outperforms all compared methods with a distinctly higher average reward. Specifically, our Primal.+DD7 reaches 4.0 points higher than the otate-of- the-art Flowformer [11]. Compared to the baseline Decision Transformer (DT), our Primal.+ only replaces the self-attention in the top layer and keeps other structures the same and manages to improve the average reward by 5.3 points. This verifies the effectiveness of our Primal-Attention and the benefits of our low-rank regularization of KSVD for the generality of DT in offline reinforcement learning. We evaluate the efficiency with comparisons to DT and Flowformer in Table 6, which give distinctively better results than other baselines in Table 5. Our Primal.-DTT achieves comparable time and memory efficiency as the most efficient baseline DT, while Flowformer shows significantly lower efficiency in both aspects. Recall that our Primal. DT achieves an average reward of 77.5, which is 5.3 points higher than DT and 4.0 points higher than Flowformer.
Large-scale Experiments We evaluate the capability of our Primal.+ model with DeiT-Small/16 [7] as backbone on ImageNet-100 [48] and ImageNet- IK [23] for image classification task. We also experiment with the language modelling task on VikiText-103 [49]. On ImageNet, we train DeiT-
Small/16 and our Primal. Meial.--DiT--SSS Deil-Small/16 from scratch following the same training protocols in [7] with 4 NVIDIA Tesla V100 SXM2 32GB GPUs Our hyper-parameters are chosen 17 = 0.05, s E (32, 64, 96). On WikiText- 103, we follow the setting in [50] where the sequence length is set as 5 22, the model consists of decoder layers with 8 heads. We implement the causal version of Primal-Attention in the last layer, i.e., Primal.+ Trans with v = 0.1, = 30. Models are trained from scratch on 4 NVIDIA Tesla V100 SXM2 32GB GPUs for 150K updates after 6K-steps warm-up.
Table 7(a) provides the test accuracy, training time and memory on a single V100 GPU with batch size 256 on both ImageNet- 100 and ImageNet-IKK 1K datasets. There is only one set of time and memory since models follow the same training protocols on both datasets. Our Primal.+ achieves better accuracy than DeiT-Small/16 less training time and memory on ImageNet-
ImageNet- 100. It also achieves the same accuracy as baseline with 1 IK On WikiText- 103 in Table 7(b), our method with default setups significantly reduces the perplexity by 2.0 points than Transformer, and achieves comparable performances with the well-tuned Flowformer, a latest SoTA model, with enhanced efficiency. Results show that using Primal-Attentic in the last layer helps the overall performance.
Ablation Study on Using Two Projections e(x), r(w) We conduct an ablation study with (w/) and without (w/o) projection scores, i.e., r-scores, involving the left singular vectors, on LRA [39]. Table shows that using both projections (w/ r-scores) helps boost performances, verifying the effectiveness of learning with the two sides of singular vectors on an asymmetric attention kernel.

---

Table Results on large-scale experiments including image classification and language modelling.
(b) Reslls on WikTTess-108 [40]
(9) Test aceuney (%) and efficiency on ImageNet- 100 [45] and ImageNet-IK IK [3]
ImageNet-100
ImageNes-IK (Top-1 Acc.)
Time (5/K-sstpp))
Memory (GBB)
Model
Perplexity ())
Time (v/K--steps)
Memory (GB)
Model
(Top-1 Acc.)
DeiT-Small/16
74.2
79.8
2425.5
14.2
Trans. [1]
3108.4
9.0
Flow. [11]
30.8
3998.4 4
10.5
Diimll-Dei--Sallli
75.7
2330.2
14.0
Prinul Thnnll-Taaass Trans.
31.0
3104.0
8,9
Table 8: Ablation on r-scores involving left singular vectors on LRA [39] with test accuracy (%)
Model
r-scores
ListOps
Text
Retrieval
Image
Pathfinder
Avg. Ace
w/o
36.8
52.4
58.2
30.5
50.2
45.6
Primal.
w/
37,3
61.2
77.8
43.0
68.3
57.5
w/o
37.1
65.1
79.2
42.8
72.8
59.4
Primal. TTans.
37.3
65.4
81.0
43,9
74.3
60.4
6
Related work
Since the pioncering work [12], the kernel-based approaches have become popular in Transformers, in which the kernel interpretation the attention matrix has been shed light on. FourierFormer [17]
treats the canonical self-attention as non- -onraammttiic regression with methodologics for symmetric kernels. [18] considers relative positional embedding with conditional positive definite kemnl.. [19] treats self-attention operation as support vector regression without considering the asymmetry in the deployed kernel methods, and the supervised regression is not applied in optimzing the attention either. [S1] addresses the issue of asymmetry, however, it resorts to symmetrization by replacing the softmax attention with approximated symmetric one, thereby still dismissing the asymmetry. These prior works deploy kernel-based techniques that are originally designed for symmetric kernels and request to suffice Mercer conditions, which is inconsistent with the asymmetric nature in self-attention. resulting in a nontrivial gap between the analytical understanding and numerical implementation towards revealing the rationale in Transformers. In [2 leverages the kernel tricks from RKBS [22] that allows asymmetry and formulates attention as a binary kernel learning problem via empirical risk minimization. However, it is hard find an explicit optimization accordingly in implementing Transformers. Nevertheless, [21] provides an analytical tool from the aspect of kernel representer theorem upon RKBS that allows asymmetry.
Much literature has also devoted to improving the efficiency of the attention computation through different approximation techniques. In the related works addressing the attention mechanism, Re- former [34] uses locally-sensitie hashing for sparse approximation. Performer [14] approximates self-attention matrix with random features. Linformer [46] considers low-rank approximation with the help of random projections. Nyströmformer [45] utilizes the Nyström method by down sampling the queries and keys in the attention matrix. [52] incorporates sparsity prior on attention. These works pose the focus on reducing the computation of the attention kernel matrix from the canonical self-attention. Hence, these works all address how to solve the problem the dual form involving the kernel matrix, while we work in a significantly different way, that is. in the primal form.
7 Conclusion
In this paper, we interpret the self-attention in Transformers with asymmetric kernels and construct a learning framework with SVD on asymmetric kernels (KSVD) under the setups of LSSVM. Within the context of KSVD, a primal-dual model representation is formulated for self-attention and a novel attention mechanism PPrimal-Attention is proposed accordingly by leveraging the primal representation. It is quite significant that with Primal-Attention attention kernel matrix in the dual can be avoided, but also the cast unsupervised KSVD optimization can be efficiently incorporated into the training through an additional regularization loss for more informative low-rank property. The analytical derivations and numerical evaluations demonstrate our great potentials in bridging explicit model interpretability and oftte-of-the-at performances. Future works can include developing different variants with the low-rank property, e.g., robust Transformers, investigating more general applications of Primal-Attentec to wide range of architectures and tasks.
not only the computation of the
10

---

Acknowledgements
This work is jointly supported by the European Research Council under the European Union's Horizon 2020 research and innovation program/ERC Advanced Grant E-DUALITY (787960), iBOF project Tensor Tools for Taming the Curse (3E22142) 1427), Research Council KU Leuven: Optimization framework for deep kernel machines C14/18/068, KU Leuven Grant CoE PFV/10/002, The Research Foundation Flanders Flaaddrs (FWO) projects: GOA4917N (Deep Restricted kemel Machines: Methods and Foundations), Ph.D./Poo Poosddoctorr grant, the Flemish Government (AI Research Program), EU H2020 ICT-48 Network TAILOR (Foundations of Trustworthy Al- Al-Integrating Reasoning, Learning and Optimization), Leuven.AI Institute.
References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[2] Jacob Devlin Ming- Wei Chang Kenton and Lee Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-IILT, pages 4171-4186, 2019.
[3] Tom Brown, Benjamin Mann, Nick Ryder, Mclanic Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
[4] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21()):548--551, 2020.
[5] Haogi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li, Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer. Multiscale vision transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 683246635.. 2021.
[6] 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.
[7] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In Proceedings of the International conference on machine learning, pages 10347-10357. PMLR, 2021.
[8] Yingyi Chen, Xi Shen, Yahui Liu, Qinghua Tao, and Johan A.K. Suykens. Jigsaw-vit: Learning jigsaw puzzles in vision transformer. Pattern Recognition Letters, 166:53-60, 2023.
[9] Michael Janner, Qiyang Li, and Sergey Levine. Offline reinforcement learning as one big sequence modeling problem. Advances in neural information processing systems, 34:1273- 1286, 2021.
[10] Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Picter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems, 14:15084-15097, 2021.
[11] Haixu Wu, Jialong Wu, Jiehui Xu, Jianmin Wang, and Mingsheng Long. Flowformer: Lineariz- ing transformers with conservation flows. In International Conference on Machine Learning. pages 24226-24242. 2022.
[12] Yao- Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis Phuis-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: An unified understanding for transformer's attention via the lens of kernel. In Proceedings of the Conference on Empirical Methods in Natural Lan- guage Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), 2019.

---

[13] Vladimir N Vapnik. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5):988-999) 1999.
[14] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song. Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
[15] Alaaeldin Ali, Hugo Touvron, Mathilde Caron, Piotr Bojanowski, Matthijs Douze, Armand Joulin, Ivan Laptev, Natalia Neverova, Gabriel Synnaeve, Jakob Verbeek, et al. XCIT: Cross- covariance image transformers. Advances in neural information processing systems, 34:20014- 20027. 2021.
[16] Tam Minh Nguyen, Tan Minh Nguyen, Dung DD Le, Duy Khuong Nguyen, Viet-Anh Tran, Richard Baraniuk, Nhat Ho, and Stanley Osher. Improving transformers with probabilistic attention keys. In Proceedings of the International Conference on Machine Learning, pages 16595-16621. PMLR, 2022.
[17] Tan Nguyen, Minh Pham, Tam Nguyen, Khai Nguyen, Stanley Osher, and Nhat Ho. Fourier- former: Transformer meets generalized fourier integral theorem. Advances in Neural Informa- tion Processing Systems, 35:29319-2999 2022.
[18] Ta-Chung Chi, Ting-Hau Man Fan, Peter Ramadge, and Alexander Rudnicky. Kerple: Kemel- ized relative positional embedding for length extrapolation. Advances in Neural Information Processing Systems, 35:8386-888 119966839,,222 2022.
[19] Tan Minh Nguyen, Tam Minh Nguyen, Nhat Ho, Andrea L. Bertozzi, Richard Baraniuk, and Stanley Osher. A primal-dual framework for transformers and neural networks. International Conference Learning Representations, 2023.
[20] James Mercer. Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society A, (4944444558))41554444 January 1909.
[21] Matthew A Wright and Joseph Gonzalez. Transformers are deep aafinite-dimensione non- Mereer binary kernel machines. arXiv preprint arXiv:2106.01506. 2021.
[22] Haizhang Zhang, Yuesheng Xu, and Jun Zhang. Reproducing kernel banach spaces for machine learning. Journal of Machine Learning Research, 10(12), 2009.
[23] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE conference on computer vision and pattern recognition, pages 248-255, 2009.
[24] Rong Rong Lin, Hai Zhang Zhang, and Jun Zhang. On reproducing kernel banach spaces: Generic definitions and unified framework of constructions. Acta Mathematica Sinica, English Series, 38(8): 1459-148,, 2022.
[25] Pando G Georgiev, Luis Sánchez-González, and Panos M Pardalos. Construction of pairs of reproducing kernel banach spaces. In Constructive Nonsmooth Analysis and Related Topics, pages 39-57. Springer, 2013.
[26] Gilbert Strang. Linear algebra and its applications. Belmont, CA: Thomson, Brooks/Cole, 2006.
[27] Johan A.K. Suykens. SVD revisited: A new variational principle, compatible feature maps and nonlinear extensions. Applied and Computational Harmonic Analysis, 40(3):600-666 609, 2016.
[28] Johan A.K. Suykens, Tony Van Gestel, Joseph De Brabanter, Bart De Moor, and Joos PL. Vandewalle. Least Squares Support Vector Machines. World scientific, 2002.
[29] Cornelius Lanezos. Linear systems self-adjoint form. The American Mahematical Monthly, (5(9):6656679) 1958.
12

---

[30] Joram Lindenstrauss and William B. Johnson. Extensions of lipschitz maps into a Hilbert space. Contemporary Mathematics, 26(18-220): 1984.
[31] Anthony Bagnall, Hoang Anh Dau, Jason Lines, Michael Flynn, James Large, Aaron Bostrom, Paul Southam, and Eamonn Keogh. The uea multivariate time series classification archive, 2018.
arXiv preprint 18/100005, 2018.
[32] George Zerveas, Srideepika Jayaraman, Dhaval Patel, Anuradha Bhamidipaty, and Carsten Eickhoff. A transformer- based framework for multivariate time series representation learning- In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 21 14 2124, 2021.
[33] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnss: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pages 5156-5165, 2020.
[34] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
[35] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long- document transformer. arXiv preprint 2000::00000005500, 2020.
[36] Zhanpeng Zeng, Yunyang Xiong, Sathya Ravi, Shailesh Acharya, Glenn M Fung, and Vikas Singh. You only sample (almost) once: Linear cost self-attention via bernoulli sampling. In International conference on machine learning, pages 12321 12321-12332, 2021.
[37] Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. In International Conference on Learning Representations, 2022.
[38] Jiachen Lu, Jinghan Yao, Junge Zhang, Xiatian Zhu, Hang Xu, Weiguo Gao, Chunjing Xu, Tao Xiang, and Li Zhang. Soft: Softmax-free transformer with linear complexity. Advances in Neural Information Processing Systems, 34:21297-21309 2021.
[39] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang. Sebastian Ruder, and Donald Metzler. Long range arena: benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
[40] Nikita Nangia and Samuel Bowman. Listops: A diagnostic dataset for latent tree learning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pages 92-99. 2018
[41] Andrew Maas, Raymond E Daly, Peter T Pham, Dan Huang, Andrew Y Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th annual meeting of the association for computational linguistics: Human language technologies, pages 142-150, 2011.
[42] Dragomir R Radev, Pradeep Muthukrishnan, Vahed Qazvinian, and Amjad Abu-Jbara. The acl anthology network corpus. Language Resources and Evaluation, 47:919 17:919-944, 2013.
[43] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[44] Drew Linsley, Junkyung Kim, Vijay Veerabadran, Charles Windolf, and Thomas Serre. Learning long-range spatial dependencies with horizontal gated recurrent units. Advances neural information processing systems, 31, 2018.
[45] Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: A nyström- based algorithm for approximating self-attention. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 14138-14148, 2021.
[46] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.0477 047668 2020.
13

---

[47] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.
[48] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 11:21112553 2015.
[49] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. In International Conference on Learning Representations, 2016.
[50] Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong. Random feature attention. In International Conference on Learning Representations, 2021.
[51] Yifan Chen, Qi Zeng, Heng Ji, and Yun Yang. Skyformer: Remodel self-attention with gaussian kernel and nyström method. In A. Beygelzimer, Y. Dauphin, Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[52] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904 10509, 2019.
14


Reviews:
[{"review_id": "UMxHw6Ggre", "reviewer": "Reviewer_2pAx", "summary": "This paper proposes a Primal-Attention method to realize self-attention blocks in Transformer with a kernel matrix. It firstly explains the relationships between self-attention and asymmetric kernel matrix. Secondly it formulates self-attention in the form of kernel SVD and derive its primal and dual representations. And eventually it proposes Primal-Attention, which uses not only the projection scores involving the right singular vectors of the asymmetric attention kernel K, but also the ones involving the left singular vectors of the asymmetric attention kernel K. Besides, it conducts several experiments on several tasks.", "questions": "1. Why are the projection scores involving the left singular vectors of the asymmetric attention kernel K so important? What does it mean physically by doing so?\n2. Why do you conduct experiments of efficiency only on LRA benchmark? And why does Primal+ have less efficiency than Primal+Trans?\n", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The motivation to formulate a neural network structure into a kernel one is quite interesting and meaningful. \n2. The primal-dual representations are derivable.\n", "weaknesses": "1. The explanation of why the projection scores involving the left singular vectors of the asymmetric attention kernel K are used is not adequate. It lacks enough analyses to prove their importance.\n2. The results of experiments show little improvements compared with baseline methods. And only LRA benchmark has efficiency analyses.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments. Below, we address the raised two main concerns in detail.\n\n***R.1 Incorporating projection scores involving left singular vectors of the asymmetric attention kernel matrix $K$.***\n\nWe provide detailed explanations and empirical evidences below. Relevant context can refer to line 164-182 on page 5 in paper. \n+ In Section 2 in paper, we present the self-attention weights $K_{ij}=\\kappa(x_i, x_j)=\\text{softmax}(\\left< q( x_i),k(x_j) \\right>/\\sqrt{d_k})$, where $K$ can be regarded as a kernel in relation to queries and keys via asymmetric measures $\\kappa(x_i, x_j)\\neq\\kappa(x_j,x_i)$.  Given an asymmetric matrix $K$, there naturally exists information from two ways w.r.t. row space and column space [1]. This is in contrast to symmetric cases, e.g., Kernel PCA that only explores row data with a symmetric kernel [2]. Moreover, from the low-rank approximation perspective of KSVD to the self-attention kernel, utilizing both left and right singular vectors leads to the optimal approximation [3]. Hence, incorporating both sides of singular vectors could provide more possibilities to exploit comprehensive information, so as to benefit the learning of asymmetric kernels for boosted performances. \n+ Empirically, we conduct an ablation study with (w/) and without (w/o) projection scores, i.e., $r$-scores, involving the left singular vectors.  Table 2pAx-1 shows that using both projections (w/ $r$-scores) helps boost performances, verifying our effectiveness in learning with asymmetric self-attention kernels. \n \n**Table 2pAx-1:** Ablation on the projection scores, i.e.,$r$-scores, involving left singular vectors on LRA with Top-1 test accuracy (%).\n|Primal.|ListOps|Text|Retrieval|Image|Pathfinder|Avg.Acc.|\n|:-:|:-:|:--:|:-:|:-:|:-:|:-:|\n|w/o $r$-scores|36.8|52.4|58.2|30.5|50.2|45.6|\n|w/ $r$-scores|37.3|61.2|77.8|43.0|68.3|**57.5**|\n\n|Primal.$+$Trans.|ListOps|Text|Retrieval|Image|Pathfinder|Avg.Acc.|\n|:-:|:-:|:--:|:-:|:-:|:-:|:-:|\n|w/o $r$-scores|37.1|65.1|79.2|42.8|72.8|59.4|\n|w/ $r$-scores|37.3|65.4|81.0|43.9|74.3|**60.4**|\n\n***R.2.1 Performance improvement***\n\nIn Tables 1, 2, 4 and 5  in paper, our method beats all compared methods including the very recent Transformers. In Table 1 on UEA Time Series, our method significantly improves over the baseline Transformer and also better than most other Transformers with a clear margin. Although our improvement is less distinctive than the very latest Flowformer (Flow.), it is reasonable to have comparable results on this simple benchmark with small-scale and short-sequence data. On LRA, D4RL and ImageNet-100 in Tables 2, 4 and 5 with more complex datasets, ours shows more substantial improvements. Notably, in reinforcement learning, our method has distinctively better performance than Flow. by a large margin (4.0%) in Table 4. \n\n***R.2.2 Efficiency analyses***\n + Long-range Arena (LRA) is a popular benchmark for evaluating efficiency in Transformers due to its long data sequence, which is a key element determining the kernel size and computation efficiency. Hence, we test on LRA in paper. \n + In Table 3, \"Primal.\" indicates that our Primal-Attention is applied to all attention layers, while in \"Primal.$+$Trans.\" only the last layer in Transformers is replaced by Primal-Attention, as explained in line 219-229 on page 6. Thus, \"Primal.\" shows to be more efficient than \"Primal.$+$Trans.\".\n + We also present efficiency analyses on other datasets with comparisons to the baseline Transformer, and the most recent state-of-the-art Flowformer.\n\n **UEA Times Series**: Our methods show the best efficiency among all compared methods. “Primal.$+$Trans.” improves over baseline Transformers (Trans.) by decreasing peak memory from 10.9GB to 6.5GB, while our “Primal.” even reduces it to 2.7GB and becomes more efficient with longer sequences, e.g., EthanolConcentration and SelfRegulationSCP2.  \n \n **D4RL Reinforcement Learning**: Our \"Primal.$+$DT\" achieves comparable time and memory efficiency as the baseline Decision Transformer (DT), while Flowformer (Flow.) shows significantly lower efficiency. Recall that in Table 4  in paper, our method achieves a much better average reward of 77.5 than DT (72.2) and Flow. (73.5). \n\n**Table 2pAx-2:** Comparisons on running time (s/Epoch) and memory consumption (GB) on UEA Time Series. \n|UEA benchmark (sequence length)|Trans.|Flow.|Primal.+Trans.|Primal.|\n|:-:|:-:|:-:|:-:|:-:|\n|EthanolConcentration (1751)|4.3|2.4|3.3|2.3|\n|FaceDetection (62)|10.7|9.8|5.7|6.9|\n|HandWriting (152)|0.3|0.3|0.3|0.4|\n|HeartBeat (405)|0.7|0.7|0.7|0.4|\n|JapaneseVowels (26)|0.5|0.6|0.5|0.5|\n|PEMS-SF (144)|0.6|0.7|0.7|0.8|\n|SelfRegulationSCP1 (896)|1.8|1.4|1.6|1.4|\n|SelfRegulationSCP2 (1152)|1.8|1.3|1.6|1.3|\n|SpokenArabicDigits (83)|3.7|4.4|4.0|4.5|\n|UWaveGestureLibrary (315)|0.3|0.3|0.3|0.4|\n|**Avg. Time (s/Epoch)**|2.5|2.2|**1.9**|**1.9**|\n\n|UEA benchmark|Trans.|Flow.|Primal.+Trans.|Primal.|\n|:-:|:-:|:-:|:-:|:-:|\n|**Memory (GB)**|10.9|2.8|6.5|**2.7**|\n\n**Table 2pAx-3:** Comparisons on running time (s/1K-steps) and memory consumption (GB) on D4RL.\n|Time |Medium-Expert|Medium|Medium-Replay|\n|:-:|:-:|:-:|:-:|\n|DT (reward: 72.2)|20.8|20.8|20.8|\n|Flow. (reward: 73.5)|54.4|54.4|54.3|\n|Primal.+DT (**reward:77.5**)|23.5|23.4|23.3|\n\n|Memory|Medium-Expert|Medium|Medium-Replay|\n|:-:|:-:|:-:|:-:|\n|DT|0.3|0.3|0.3|\n|Flow.|1.5|1.5|1.5|\n|Primal.+DT|0.3|0.3|0.3|\n\n[1] Suykens, J.A.K. \"SVD revisited: A new variational principle, compatible feature maps and nonlinear extensions.\" Applied and Computational Harmonic Analysis, 2016.\n\n[2] Schölkopf, B., Alexander S., and Klaus-Robert M. \"Nonlinear component analysis as a kernel eigenvalue problem.\" Neural computation, 1998.\n\n[3] Eckart, C., and Gale Y. \"The approximation of one matrix by another of lower rank.\" Psychometrika, 1936."}, {"review_id": "VqAPoEmSyu", "reviewer": "Reviewer_8hph", "summary": "This paper proposes a new understanding of self-attention in transformers via asymmetric Kernel Singular Value Decomposition (KSVD). In particular, the authors formulate a primal-dual representation of self-attention for maximizing the projection variances in the attention outputs and then derive a new attention mechanism, namely the Primal-Attention, to avoid direct computation of the kernel matrix. Using KKT conditions, they prove the Primal-Attention can obtain a zero-value objective. Experimental results are provided to justify the advantage of the Primal-Attention. ", "questions": "1. Can the proposed KSVD framework be used to explain other components in a self-attention unit, such as the residual connection, the layer normalization, and the feedforward network?", "limitations": "The authors have not clearly addressed the limitations of their work.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The idea of formulating self-attention as solving an KSVD problem is novel and of potentially high-impact.\n\n2. The derivation of self-attention from KSVD given in the paper is elegant and correct.\n\n3. The paper is well-written, easy to follow, and enjoyable to read.", "weaknesses": "1.  More large-scale experiments, e.g., on full ImageNet or WikiText103 language modeling, should be conducted.\n\n2. Empirical analysis, such as the efficiency analysis of the Primal-Attention vs. the baselines, should be provided to help provide better understanding of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer's high appreciation of our work and the insightful comments, which will be addressed point-wisely below.\n\n**R.1 More large-scale experiments**\n\nAs suggested, we test on ImageNet-1K and WikiText-103, both showing our promising potentials. Ours achieves the same accuracy as baseline with less memory; recall that our model also shows enhanced low-rank property as in Fig.1 in paper. On WikiText-103, our method with default setups achieves comparable performances with the well-tuned Flowformer, a latest SoTA model. \n\n**Table 1:** Test Acc. (%) on ImageNet-1K. \n|Model|Top-1 |Memory(GB)|\n|:-:|:-:|:-:|\n|DeiT-Small/16|79.8|14.2|\n|Primal.$+$DeiT-Small/16(ours)|79.8|14.0|\n\n**Table 2:** Perplexity on WikiText-103. \n|Model|Perplexity($\\downarrow$)|\n|:-:|:-:|\n|Trans.(2017)|33.0|\n|Re.(2020)|33.6|\n|Per.(2021)|37.5|\n|Cos.(2022)|34.1|\n|Flow. w/o competition(2022)|31.2|\n|Flow. w/o allocation(2022)|32.2|\n|Flow.(2022)|30.8|\n|Primal.$+$Trans.(ours)|31.0|\n\n**R.2 More empirical analyses**\n\n**R.2.1 Efficiency**\n\nLRA is a popular benchmark in evaluating efficiency due to long data sequences. We test on LRA where ours shows better efficiency in running time and memory as in Table 3 in paper. \n\nBelow, we provide more efficiency evaluations.\n+ *UEA Times Series:* Ours show the best efficiency especially in memory where ours are more efficient with longer sequences, e.g., EthanolConcentration and SelfRegulationSCP2. \n+ *D4RL Reinforcement Learning:* Our \"Primal.$+$DT\" achieves comparable time and memory efficiency as Decision Transformer (DT), while Flowformer is significantly less efficient. Recall that in Table 4 in paper, ours attains a much higher average reward of 77.5 than DT (72.2) and FlowFormer (73.5).\n\n**Table 3:** Running time and memory (GB) on UEA Time Series. \n|UEA benchmark (sequence length)|Trans.|Flow.|Primal.+Trans.|Primal.|\n|:-:|:-:|:-:|:-:|:-:|\n|EthanolConcentration (1751)|4.3|2.4|3.3|2.3|\n|FaceDetection (62)|10.7|9.8|5.7|6.9|\n|HandWriting (152)|0.3|0.3|0.3|0.4|\n|HeartBeat (405)|0.7|0.7|0.7|0.4|\n|JapaneseVowels (26)|0.5|0.6|0.5|0.5|\n|PEMS-SF (144)|0.6|0.7|0.7|0.8|\n|SelfRegulationSCP1 (896)|1.8|1.4|1.6|1.4|\n|SelfRegulationSCP2 (1152)|1.8|1.3|1.6|1.3|\n|SpokenArabicDigits (83)|3.7|4.4|4.0|4.5|\n|UWaveGestureLibrary (315)|0.3|0.3|0.3|0.4|\n|**Avg. Time(s/Epoch)**|2.5|2.2|**1.9**|**1.9**|\n\n||Trans.|Flow.|Primal.+Trans.|Primal.|\n|:-:|:-:|:-:|:-:|:-:|\n|**Memory**|10.9|2.8|6.5|**2.7**|\n\n**Table 4:** Running time(s/1K-steps) and memory(GB) on D4RL.\n|Time|Medium-Expert|Medium|Medium-Replay|\n|:-:|:-:|:-:|:-:|\n|DT(reward: 72.2)|20.8|20.8|20.8|\n|Flow.(reward: 73.5)|54.4|54.4|54.3|\n|Primal.+DT(**reward:77.5**)|23.5|23.4|23.3|\n\n|Memory|Medium-Expert|Medium|Medium-Replay|\n|:-:|:-:|:-:|:-:|\n|DT|0.3|0.3|0.3|\n|Flow.|1.5|1.5|1.5|\n|Primal.+DT|0.3|0.3|0.3|\n \n**R.2.2 Other empirical analyses**\n+ *Spectrum of self-attention kernels:* We plot cumulative explained variances of self-attention kernels on ImageNet-1K in Figure 1 in paper. Our method shows enhanced low-rank property, where more information can be captured within less components than the baseline.\n+ *Ablation on $\\eta$ and $s$:* Through the KSVD regularization coefficient $\\eta$ in eq.(10) and the number of components $s$, we verify the effectiveness of our KSVD optimization in Tables 1, 2 in Sec.B.2 in Supplementary Material. \n+ *Ablation on the projection weights:* We also compare the data-dependent and data-independent projections in Tables 3 and 4 in Sec.B.2 in Supplementary Material. \n+ *Ablation on projection scores from left singular vectors:* We evaluate the results of using with (w/) and without (w/o) the projection scores ($r$-scores) involving left singular vectors. It shows that using both sets of projections (w/ $r$-scores) helps boost performance in learning asymmetric self-attention kernels.\n \n**Table 5:** Ablation on projection scores, i.e., $r$-scores, involving left singular vectors on LRA.\n|Primal.|ListOps|Text|Retrieval|Image|Pathfinder|Avg. Acc.|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|w/o $r$-scores|36.8|52.4|58.2|30.5|50.2|45.6|\n|w/ $r$-scores|37.3|61.2|77.8|43.0|68.3|**57.5**|\n\n|Primal.$+$Trans.|ListOps|Text|Retrieval|Image|Pathfinder|Avg. Acc.|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|w/o $r$-scores|37.1|65.1|79.2|42.8|72.8|59.4|\n|w/ $r$-scores|37.3|65.4|81.0|43.9|74.3|**60.4**|\n\n**R.3 Possible work on other components**\n\nThanks for mentioning these interesting perspectives, which we would like to regard as possible future work. For instance, layer normalization might be in relation to orthonormality of singular vectors; the feedforward network and residual connection could be inspiring to connect with deep kernel machines[1,2]. Nevertheless, the authenticity requires rigorous analyses and experiments before arriving at a conclusion.\n\n**R.4 Limitations**\n\nThe limitations can refer to the last paragraph in Supplementary Material.\n+ In efficiency evaluations, e.g., on UEA time-series, we can note that our time efficiency gain is less distinctive on shorter-length sequence data than on longer ones. Further promoting the efficiency even on shorter-length sequence data can be an interesting future work.\n+ Our Primal-Attention uses feature maps in primal, avoiding kernel computations in dual. However, it is not always easy to obtain or approximate feature maps of the kernel function, e.g., Gaussian kernel[3]. We applied feature maps of Cosine similarity kernels (see Remark 4.1 in paper). Although we achieved good performances in many datasets, more variants of feature maps can benefit wider applications. \n\nThanks for this suggestion. We will elaborate it in the possible final version.\n\n[1] Allen-Zhu, Z., and Li, Y. \"Backward feature correction: How deep learning performs deep learning.\" arXiv, 2020.\n\n[2] Tonin, F., Tao, Q., Patrinos, P., and Suykens, J.A.K. \"Deep Kernel Principal Component Analysis for Multi-level Feature Learning.\" arXiv, 2023.\n\n[3] Rahimi, A., and Recht, B. \"Random features for large-scale kernel machines.\" NeurIPS, 2007."}, {"review_id": "678SNb9kCB", "reviewer": "Reviewer_aphr", "summary": "Self-attention mechanisms serve as pivotal components in the domains of natural language processing and computer vision. Previous kernel function based self-attention variants, which are predicated on Mercer kernels, tend to overlook the inherent asymmetry of the attention matrix in the vanilla self-attention. In response to this oversight, this study introduces a novel approach, termed Primal-Attention. This approach leverages asymmetric Kernel Singular Value Decomposition (KSVD) to facilitate a low-rank approximation of the attention matrix, thereby incorporating an asymmetric kernel attention matrix. The empirical findings substantiate that Primal-Attention functions as a low-rank attention mechanism, exhibiting superior performance while maintaining low time complexity.", "questions": "1. Why should the primal optimization function, as depicted in Equation 6, be considered? On what basis is this function proposed? Furthermore, why should this function be maximized rather than minimized?\n2. Why is the formula for Primal-Attention in each head represented by Equation 11? The process of derivation appears to be missing.\n3. How do the authors handle the positive diagonal matrix $\\mathbf{\\Lambda}$? Given that $\\mathbf{\\Lambda}$ is a key component in Equations 6 and 11, can the authors provide a detailed explanation of the process?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper introduces a novel perspective that interprets the self-attention mechanism as a KSVD optimization problem.", "weaknesses": "1. The exposition of methodologies in this paper lacks sufficient clarity. For instance, the crucial concept of primal optimization in self-attention with KSVD, as proposed in Equation 6, is introduced abruptly without a detailed discussion of the connection between KSVD and self-attention.\n2. Algorithm 1, outlined in Appendix B.1, details the entire process of Primal-Attention and employs random projection. However, the omission of a citation for the Johnson–Lindenstrauss lemma in the paper is inappropriate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments and the appreciation on the novelty of our work. We address your concerns point-wisely below.\n\n***R.1 Concept of primal optimization with KSVD in eq.(6) and connections with self-attention.***\n\nThe modeling and optimization of KSVD on self-attention are under the LSSVM setup [1]. We extend its linear version (SVD) to the nonlinear one (KSVD), by starting from the primal optimization eq.(6) till deriving the dual problem  eq.(7) for the primal-dual representation of self-attention in eq.(8). As presented in eq.(3), the attention outputs $o_i=\\sum\\nolimits_{j=1}^N v(x_j)K_{ij}$ are consistent with the dual representation of KSVD $e_i=\\sum\\nolimits_{j=1}^N h_{r_j}K_{ij}$, derived in eq.(8). We agree with the reviewer and will add more explanations in an early place before eq.(6). More explanations can also refer to line 115-122 on page 4, and Remarks 3.3-3.4 in paper. \n\n***R.2 Citation of the Johnson–Lindenstrauss lemma in Algorithm 1.***\n\nIn Algorithm 1 with data-dependent projection weights, transformation matrix $f(X)$ is used for projection directions, as explained in line 128-132 on page 4. In experiments, we set $f(X):=X'$ with $X'$ a subset uniformly sampled from the rows of $X$. Indeed, the Johnson–Lindenstrauss Lemma [2] shows the main patterns of a matrix can be retained with the random linear projections. We appreciate the helpful referene and will cite it in paper. Other projection parameters are all optimized by SGD. \n\n***R.3 Why and on what basis is eq.(6) proposed? Why maximization in eq.(6) but minimization in eq.(10)?***\n\nEq.(6) is based on the variational principle on SVD under the LSSVM framework [1], but extends the original linear SVD in [1] to the nonlinear KSVD with asymmetric kernels in dual, induced by two feature maps $\\phi_q(x),\\phi_k(x)$ in primal. The primal objective in eq.(6) maximizes the projection variances of $W_{e|X}^\\top\\phi_q(x),W_{r|X}^\\top\\phi_k(x)$ regarding queries and keys. This follows the idea of KSVD, because in dual,the corresponding right and left singular vectors learn the directions with the maximal projection variances, w.r.t. row and column data of the asymmetric kernel matrix $K:=[\\left<\\phi_q(x_i),\\phi_k(x_j)\\right>]$. The trace term in eq.(6) regularizes the primal variables $W_e,W_r$ and helps deriving the Lagrange function and the dual optimization eq.(7) via KKT conditions. This is the basis of eq.(6). Details can also refer to Remark 3.1, Theorem 3.2 and its proof in Appendix A.1.\n\nWe derived that the primal optimization in eq.(6) can be solved through KKT conditions with stationary solutions in the dual optimization derived in eq.(7). As proved in Lemma 4.2, stationary solutions yield a zero-value objective $J$ in eq.(6), thus we do not need to solve the expensive SVD on the asymmetric kernel matrix $K$ in dual but intead we choose to optimize the objective $J$ in primal, i.e., eq.(6), to a zero value. In implementation of such an optimization, this zero-value objective can be flexibly realized by $\\min J^2$ with efficient SGD-based algorithms. Therefore, in training, we adopt $\\min L+\\eta \\sum_{l}J_l^2$, i.e., optimizing the loss $L$ with regularization loss terms $J_l^2$ promoting KSVD optimization. Relevant context can be referred in Theorem 3.2 and Lemma 4.2 in paper and their proofs in Appendix A.\n\n***R.4 Why is the formula for Primal-Attention in each head represented by eq.(11)?***\n\nIn the primal optimization of KSVD for each head in eq.(6), the projection scores $e_i, r_j$ are given in the equality constraints. By replacing $e_i, r_j$ in the objective $J$ of eq.(6), we derive the unconstrained optimization with the objective as in eq.(11), which can be referred to line 124-127 on page 6. \n\n***R.5 How to handle the positive diagonal matrix $\\Lambda$ crucial in eq.(6) and (11)? Detailed explanation of the process?***\n\n+ Diagonal matrix $\\Lambda$ serves as the inverse of the positive singular values $\\Sigma$ of the attention kernel matrix $K$, i.e.,$\\Sigma=\\Lambda^{-1}$, shown in line 152-156 on page 5. Details can be found in Proof of Theorem 3.2, and Comments on Lemma 4.2 in Appendix. \n+ In modeling, as attention outputs are formulated as projection scores along directions corresponding to those singular values (vectors), $\\Lambda:= \\Sigma^{-1}$ is indeed a key component reflecting the importance of each projection direction, exploring low-rank explanations. \n+ In experiments, we assure the positivity of $\\Lambda$ by defining a squared value of a diagonal matrix $\\Lambda:=C^2$ and set it as learnable parameter in $J$ of eq.(11) for each head: \n$J=\\frac{1}{2}\\sum\\_{i=1}^N \\||( W\\_{e|X}\\Lambda^{\\frac{1}{2}})^\\top\\phi_q(x_i)\\||_2^2+\\frac{1}{2}\\sum\\_{j=1}^N \\||( W\\_{r|X}\\Lambda^{\\frac{1}{2}})^\\top\\phi_k(x_j)\\||_2^2-\\text{Tr}(W_e^\\top W_r).$\n\nNote that given $\\phi_q, \\phi_k$, projection weights $W_{e|X},W_{r|X}\\in\\mathbb R^{p\\times s}$ for the $s$ directions and $\\Lambda\\in \\mathbb R^{s\\times s}$ are optimized together by SGD to approach an zero-valued $J$. Here, $\\Lambda$ imposes different importance on the $s$ projection directions. Due to the production between $W_{e|X},W_{r|X}$ and $\\Lambda$, the optimized results only reflect the final results of $W_{e|X}\\Lambda^{\\frac{1}{2}},W_{{r|X}}\\Lambda^{\\frac{1}{2}}$, so the $\\Lambda$ optimized by SGD is not necessarily the original inversed singular values. However, in empirical low-rank analysis, we can always compute the exact singular values of the self-attention kernel matrix $K$, as shown in Figure 1 in paper, where our Primal-Attention captures more information with less components than the canonical self-attention. \n\n[1] Suykens, J.A.K. “SVD revisited: A new variational principle, compatible feature maps and nonlinear extensions.” Applied and Computational Harmonic Analysis, 2016.\n\n[2] Lindenstrauss, W., and Johnson J. “Extensions of Lipschitz maps into a Hilbert space.” Contemp. Math, 1984."}]

Author rebuttal:
Dear Program Chairs, Area Chairs, and Reviewers,

First of all, we would like to thank you for your time and valuable comments, which help improving our work. 

In this work, we provide a new framework to interpret self-attention in Transformers via asymmetric Kernel Singular Value Decomposition (KSVD). Our work addresses the intrinsic asymmetry residing in self-attention and fills the gap of most of existing works on Transformers resorting to the classic techniques using symmetric Mercer kernels. With KSVD, a primal-dual representation of self-attention is formulated and its corresponding primal and dual optimization problems are also cast by maximizing the projection variances in the attention outputs. Based on the derived analytical results, a new attention mechanism is proposed with improved efficiency and performances, namely the Primal-Attention, and its optimization is also incorporated through a regularization term with enhanced low-rank properties.

We are grateful that the reviewers unanimously regard our work as novel and interesting towards understanding self-attention and of potentially high-impact. The review comments mainly raise to present more empirical evaluations and to elaborate some technical details. In the rebuttal, we have addressed the comments from all reviewers point-wisely. To be more specific, *i)* we present more experimental results that all support the superiority of our method, including efficiency analyses, large-scale datasets, ablation on the incorporation of projection score involving the left singular vectors (to **Reviewer 2pAx, Reviewer 8hph**); *ii)* we provide further explanations to better introduce the primal and dual optimization in Eq.(6)-(7) and the objective of Primal-Attention in Eq.(10)-(11) based on the property from stationary conditions in Lemma 4.2 (to **Reviewer aphr**). 

We hope that our detailed responses could well address the comments and be assessed by Chairs and Reviewers. We sincerely look forward to further discussions with the reviewers.

Best wishes,

Anonymous author(s) of Paper3761

Meta-review: Growing body of work aims to improve self-attention by treating it as a kernel machine. However, they utilize symmetric kernels. While the symmetry issue might be perceived as a minor concern, canonical self-attention is inherently asymmetric through distinct key-query embeddings. The main contribution of this paper is representing self-attention through asymmetric Kernel Singular Value Decomposition (KSVD). Building on this, the authors provide a primal-dual representation of self-attention and introduce the so-called Primal-Attention through the primal representation of KSVD. 

The reviewers and I found the paper to be a solid contribution with strong in its theoretical underpinnings. The authors also demonstrate the empirical value of the proposed Primal-Attention. There are some notable shortcomings, primarily related to insufficient explanations and empirical analyses. The reviewers collectively pointed to the need for greater clarity in outlining methodologies and for more comprehensive experimental evaluations. The authors have addressed many of these shortcomings during the response period, for instance, they have provided more thorough experiments. Overall, despite some concerns, the contributions and theoretical strengths of the paper warrant an "Accept" decision. I recommend reviewers to address any remaining weaknesses to enhance the paper's impact and rigor. Specifically, the authors should 

* provide clear explanations for the critical methodologies and concepts that reviewers found lacking.
* carefully incorporate new empirical findings and 
* address the omitted citation and any other relevant literature that strengthens the theoretical basis of the paper.
Decision: Accept (poster)