# Lightweight Structure-Aware Attention for Visual Understanding

Heeseung Kwon, Francisco M. Castro, Manuel J. Marin-Jimenez, Nicolas Guil, Karteek Alahari

► To cite this version:

Heeseung Kwon, Francisco M. Castro, Manuel J. Marin-Jimenez, Nicolas Guil, Karteek Alahari. Lightweight Structure-Aware Attention for Visual Understanding. 2022. hal-03916268

HAL Id: hal-03916268

https://hal.science/hal-03916268

Preprint submitted on 30 Dec 2022

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Lightweight Structure-Aware Attention for Visual Understanding

Heeseung Kwon, Francisco M. Castro, Manuel J. Marin-Jimenez, Nicolas Guil, Karteek Alahari

► To cite this version:

Heeseung Kwon, Francisco M. Castro, Manuel J. Marin-Jimenez, Nicolas Guil, Karteek Alahari. Lightweight Structure-Aware Attention for Visual Understanding. International Journal of Computer Vision, 2025, 133, pp.6129-6144. 10.1007/s11263-025-02475-7. http-03916268v2

HAL Id: hal-03916268

https://hal.science/hal-03916268v2

Submitted on 7 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Lightweight Structure-Aware Attention for Visual Understanding

Heeseung Kwon¹ Francisco M. Castro² Manuel J. Marin-Jimenez³ Nicolas Guil² Karteek Alahari¹

¹Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK

²Department of Computer Architecture, University of Málaga

³Department of Computing and Numerical Analysis, University of Córdoba

Abstract

Vision Transformers (ViTs) have become a dominant paradigm for visual representation learning with self-attention operators. Although these operators provide flexibility to the model with their adjustable attention kernels, they suffer from inherent limitations: (1) the attention kernel is not discriminative enough, resulting in high redundancy of the ViT layers, and (2) the complexity in computation and memory is quadratic in the sequence length. In this paper, we propose a novel attention operator, called lightweight structure-aware attention (LiSA), which has a better representation power with log-linear complexity. Our operator learns structural patterns by using a set of relative position embeddings (RPEs). To achieve log-linear complexity, the RPEs are approximated with fast Fourier transforms. Our experiments and ablation studies demonstrate that ViTs based on the proposed operator outperform self-attention and other existing operators, achieving state-of-the-art results on ImageNet, and competitive results on other visual understanding benchmarks such as COCO and Something-Something-V2. The source code of our approach will be released online.

1. Introduction

Since the emergence of the vision transformer (ViT) [12], transformers have become the dominant neural architecture for visual understanding, outperforming convolutional neural networks (CNNs). Self-attention, a core operator of ViT, has relative merits compared to convolution because of the adjustable attention kernel and its ability to capture long-range dependencies. However, self-attention has inherent limitations for visual recognition. First, the attention kernel has difficulty learning discriminative features due to the lack of desirable inductive biases, resulting in high redundancy of the ViT layers [27, 56]. Thus, it usually requires a large amount of data [12] and aggressive augmentations [45] to obtain good performance. Second, the complexity of self-attention is quadratic in the length of its input sequence,

<figure><img src="image_1.png" /><figcaption>Figure 1. **Self-attention vs. LiSA.** (a) Feature visualization of self-attention & LiSA: compared to self-attention, LiSA learns better discriminative features by capturing geometric structural patterns. (b) Computation (FLOPs) & memory cost: LiSA is significantly more efficient than self-attention when the sequence length increases, due to its log-linear complexity.</figcaption></figure>

making the operator impractical for high-resolution images and difficult to be adopted for hierarchical models.

Recent approaches have proposed new types of operators to address the limitations of self-attention. Some of them have attempted to learn better discriminative features with self-attention by including relative position embeddings (RPEs) [2, 10, 30, 37] or capturing geometric structures (e.g., image gradients, video motion) [23, 61]. However, these operators have high computational complexity, and thus it is hard to capture long-range dependencies on high resolutions [2, 10, 23, 30, 61]. Some other methods have proposed efficient attention operators to handle the complexity of self-attention [5, 7, 31, 33, 35, 50]. Although these operators have linear complexity with factorized softmax attention kernel, they often underperform on visual understanding, compared to the original attention-based models [33, 35].

In this paper, we propose an effective yet efficient operator, lightweight structure-aware attention (LiSA), which learns effective discriminative features while requiring only log-linear complexity. To improve the expressivity, we exploit a set of RPEs for learning both convolutional inductive biases (e.g., translation invariance) and geometric structural
Lightweight Structure-Aware Attention
for Visual Understanding

Heeseung Kwon¹, Francisco M. Castro², Manuel J. Marin-Jimenez³, Nicolas Guil²,
Karteek Alahari¹*

¹Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK.

²Department of Computer Architecture, University of Málaga.

³Department of Computing and Numerical Analysis, University of Córdoba.

*Corresponding author(s). E-mail(s): karteek.alahari@inria.fr;

Contributing authors: heeseung.kwon@inria.fr; fcastro@uma.es; mjmarin@uco.es; nguil@uma.es;

Abstract

Attention operator has been widely used as a basic brick in visual understanding since it provides some flexibility through its adjustable kernels. However, this operator suffers from inherent limitations: (1) the attention kernel is not discriminative enough, resulting in high redundancy, and (2) the complexity in computation and memory is quadratic in the sequence length. In this paper, we propose a novel attention operator, called Lightweight Structure-aware Attention (LiSA), which has a better representation power with log-linear complexity. Our operator transforms the attention kernels to be more discriminative by learning structural patterns. These structural patterns are encoded by exploiting a set of relative position embeddings (RPEs) as multiplicative weights, thereby improving the representation power of the attention kernels. Additionally, the RPEs are approximated to obtain log-linear complexity. Our experiments and analyses demonstrate that the proposed operator outperforms self-attention and other existing operators, achieving state-of-the-art results on ImageNet-1K and other downstream tasks such as video action recognition on Kinetics-400, object detection & instance segmentation on COCO, and semantic segmentation on ADE-20K.

**Keywords:** Visual Understanding, Vision Transformer, Self-Attention, Image Recognition

# 1 Introduction

Since the emergence of the vision transformer (ViT) [1], transformers have become the dominant neural architecture for visual understanding, out-performing convolutional neural networks (CNNs). Self-attention, a core operator of ViT, has relative merits compared to convolution because of the adjustable attention kernel and its ability to capture long-range dependencies. However,

self-attention has inherent limitations for visual
recognition. First, the attention kernel has diffi-
culty learning discriminative features due to the
lack of desirable inductive biases, resulting in high
redundancy of the ViT layers [2, 3]. Thus, it usually
requires a large amount of data [1] and aggressive
augmentations [4] to obtain good performance. Sec-
ond, the complexity of self-attention is quadratic in
patterns in the query-key correlation. Fig. 1a illustrates a few sample feature activations from the early layers of the same-scale models (DeiT-T [45] vs. LiSA-I-T). LiSA effectively captures geometric structures in the image, while self-attention feature activations are relatively weak and uninformative in the early layers due to the lack of desirable inductive biases. Although the use of the RPEs is effective for LiSA, it is infeasible to cover long-range dependencies due to their computation cost. Thus, we leverage them efficiently with fast Fourier transforms (FFTs), achieving log-linear complexity. We demonstrate this efficiency in Fig. 1b. While the complexity of self-attention increases exponentially with respect to the number of tokens, that of LiSA increases gracefully due to log-linear complexity.

Our main contributions are as follows: (1) to overcome the limitations of self-attention, we propose a new attention operator called LiSA, which learns both convolutional priors and structural patterns with log-linear complexity, and, (2) LiSANets, the models based on our LiSA operator, outperform other counterparts, achieving competitive results on visual understanding benchmarks, ImageNet [11], COCO [29], and Something-Something-V2 [15], respectively.

## 2. Related Work

**ViTs for visual understanding.** After the success of ViT [12], transformer architectures have been widely adopted in a variety of visual understanding tasks [1, 3, 43, 46, 54, 56]. Several approaches have proposed improvements to the original ViT [12], e.g., using a teacher-student scheme [45], a better tokenization scheme [56], or using small splits of the tokens to obtain richer local information [16]. Recently, several approaches try to combine transformers and CNNs to leverage the best of each world. Some of these incorporate convolutions into the attention block [13, 14, 27, 53] to increase the expressivity of self-attention. Others employ the hierarchical structure of CNNs to learn better discriminative features [10, 14, 27, 28, 30, 51, 53, 60]. To handle the complexity of hierarchical ViTs, these approaches use convolutions instead of self-attention operators in the early stages [10, 27], adopt local attention [30, 60], or downsampled attention [14, 28, 51, 53]. While these methods heavily depend on handcrafted designs, our proposed model purely based on LiSA achieves notable performance without such designs due to the high expressivity and efficiency of LiSA.

**Highly-expressive operators.** The new types of operators proposed recently, increase the representation power by developing self-attention [2, 10, 23, 30, 37, 61] or convolution [6, 21, 26, 34]. Attention-based operators have achieving this by adding convolutional priors [10, 30, 37] or capturing relational structures [2, 23, 61]. Convolution-based operators have dynamically adapted convolution kernels based on the input features [6, 21, 26, 34]. However, these highly-

expressive operators come with high computational complexity and are typically limited to local interactions [2, 23, 26, 61]. One example is the relational self-attention (RSA) [23], which is related to our work. RSA is one of the most expressive operators that captures structural patterns with relational components, but it is also limited to local interactions due to its high computational complexity. In contrast, our proposed LiSA shows the highest level of expressivity by capturing global structural patterns with log-linear complexity.

**Lightweight operators.** Some of the existing lightweight attention operators factorize the softmax attention kernel [7, 22, 41, 50]. While they have linear complexity, they usually perform worse than the original attention in terms of accuracy [33, 35]. Other approaches have attempted to linearize RPE-added attention operators [5, 31, 33], but they still underperform on visual recognition. Recently, a few approaches adopt FFTs for efficiently covering global receptive fields [25, 33, 39]. The Global Filter (GF) layer [39] is one such operator, which implements an efficient global circular convolution with FFTs. However, the expressivity of the GF layer is constrained due to static convolution kernels. Our LiSA also adopts this technique for efficiency but focuses on learning structural patterns with its dynamic attention kernels, leading to better performance.

## 3. Background

**Self-attention.** The self-attention operator [47] is a core component in transformer architectures that generates the query-key attention for updating the value. Let $N$ denote the sequence length (the number of tokens) and $C$ the number of input channels. Given an input feature $\mathbf{X} \in \mathbb{R}^{N \times C}$, query, key, value, $\mathbf{Q}, \mathbf{K}, \mathbf{V} \in \mathbb{R}^{N \times C}$, are firstly produced by independent linear projections, and each element of the output $\mathbf{Y} \in \mathbb{R}^{N \times C}$ of self-attention is expressed as

$$Y_{i,k} = \sum_{j}^{N} \sigma(A_{i,j}) V_{j,k}, \quad A_{i,j} = \frac{1}{\sqrt{C}} \sum_{k}^{C} Q_{i,k} K_{j,k}. \quad (1)$$

Note that $\sigma$ is the softmax function along $j$-axis. Two main characteristics of self-attention are that: (1) the operator represents a global interaction where the size of the attention kernel for each query is equal to $N$, and (2) the attention kernel dynamically changes according to the input feature. However, it is unable to encode the relative order of tokens due to the lack of convolutional inductive biases, resulting in performance degradation on visual recognition.

**Relative position embedding (RPE).** One of the popular schemes to handle the lack of convolutional inductive biases is adopting an RPE for the self-attention operator [10, 30, 37]. A common RPE has the shape of a Toeplitz matrix, and it
<figure><img src="image_2.png" /><figcaption>**Fig. 1: Self-attention vs. LiSA.** (a) Process of self-attention & LiSA: LiSA updates the attention to the structure-aware attention via RPEs. (b) Feature visualization of self-attention & LiSA: compared to self-attention, LiSA learns better features by capturing geometric structural patterns.</figcaption></figure>

the length of its input sequence, making the operator impractical for high-resolution images and difficult to adopt for hierarchical models.

Several approaches have proposed new types of operators to address the limitations of self-attention. Some of them have attempted to learn better discriminative features with self-attention by including relative position embeddings (RPEs) [5-7] or capturing geometric structures (e.g., image gradients, video motion) [8, 9]. However, these operators still have high computational complexity, which makes it challenging to capture long-range dependencies [6-9]. Some other methods have proposed efficient attention operators to handle the complexity of self-attention [10-15]. Although these operators have a linear complexity with a factorized attention kernel, they often underperform, compared to the original attention [12, 15]. Recent methods have proposed convolutional attention operators by integrating attention with convolution [2, 16-20]. While these operators are effective for capturing geometric structures with convolutions, their learnability is still limited since convolution kernels are local and static.

In this paper, we propose an effective yet efficient operator, lightweight structure-aware attention (LiSA). To address the limitations of self-attention, we focus on improving the attention kernel to be more discriminative. By leveraging the fact that the feature correlation contains rich structural information [9, 21-24], we devise a

new attention operator that learns structural patterns within the query-key correlation via RPEs. As illustrated in Fig. 1a, while existing methods adopt RPEs for additive interaction, we exploit RPEs as multiplicative weights. The RPEs extract structural patterns from the attention kernel and recompose the kernel in a structure-aware manner. Fig. 1b illustrates a few sample feature maps from the early layers of self-attention and LiSA. LiSA effectively captures geometric structures in the image, while self-attention features are relatively weak and uninformative due to the lack of desirable inductive biases. Finally, since the complexity of RPEs is quadratic in the sequence length, we compute them efficiently with fast Fourier transforms (FFTs), achieving log-linear complexity.

Our main contributions are as follows: (1) we overcome the limitations of self-attention by proposing a new attention operator called LiSA, which learns structural patterns with log-linear complexity, and, (2) LiSANets, the models based on our LiSA operator, outperform their counterparts, achieving state-of-the-art results on visual understanding benchmarks such as ImageNet-1K [25], Kinetics-400 [26], COCO [27], and ADE-20K [28].

## 2 Related Work

**ViTs for visual understanding.** After the success of ViT [1], transformer architectures have been widely adopted in a variety of visual understanding tasks [3, 29-33]. Several approaches have proposed improvements to the original ViT [1], e.g., using a teacher-student scheme [4], a better tokenization scheme [3], or using small splits of the tokens to obtain richer local information [34]. Recently, several approaches employ the hierarchical structure by adopting efficient local attention techniques [6, 35, 36]. However, their representation powers are still low due to the limitations of self-attention. In this paper, we propose a new hierarchical ViT model family, LiSANets, achieving state-of-the-art performance with less computation due to the high expressivity and efficiency of LiSA.

**Highly-expressive operators.** Recently proposed operators increase the representation power by developing self-attention [5-9, 37] or convolution [38-41]. Attention-based operators have achieved this by adding relative position embeddings [5, 6, 37] or capturing relational structures [7-
<figure><img src="image_2.png" /><figcaption>Figure 2. Computational graph of Structure-aware Attention (SA) for each query. After obtaining the query-key dot-product correlation (Ā), structural patterns in Ā are encoded by Rª, and utilized in two ways: 1) the patterns are used for generating a structure-aware attention kernel with Rᵇ, and 2) directly projected as a structural feature with Bᵇ. Note that N = H × W, C = 1 in this figure.</figcaption></figure>

consists of learnable weights which can be expressed as

$$ \mathcal{T}(e) = \begin{pmatrix} e_N & e_{N+1} & e_{N+2} & \cdots & e_{2N-1} \\ e_{N-1} & e_N & e_{N+1} & \cdots & e_{2N-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ e_1 & e_2 & e_3 & \cdots & e_N \end{pmatrix}, \quad (2) $$

where e = {e₁, e₂, ..., e₂N-1}. When RPE is added, the attention operator is formulated as

$$ Y_{i,k} = \sum_{j}^{N} \sigma(A_{i,j} + R_{i,j})V_{j,k}, \quad \mathbf{R} = \mathcal{T}(e) \in \mathbb{R}^{N \times N}. \quad (3) $$

By introducing relative positional information into attention, the self-attention operator obtains the ability to learn convolutional inductive biases.

**Limitations of self-attention with RPE.** Despite several approaches showing the effectiveness of RPE, the self-attention operator has inherent limitations. First, the expressivity of the operator is still insufficient; it is difficult to capture geometric structures (e.g., image gradients, video motion) since the softmax attention kernel may not be effective for encoding gradient information due to its non-negativity [23, 38]. Additionally, although the query-key correlation A suppresses photometric variations and reveals geometric structures [24, 40], the kernel is aggregated with the value V without considering structural patterns in A. Second, the operator suffers from quadratic complexity (O(N²)) since the non-linear softmax function and RPE are hard to be linearized. Although a few approaches [7, 33, 50] have attempted to approximate the softmax function with kernelized methods to make the operator more efficient, they do not improve over the original transformer in accuracy due to its training instability [33] or approximation errors [35].

# 4. Structure-aware Attention

## 4.1. Basic Form of Structure-aware Attention (SA)

**Learning convolutional inductive biases.** To handle the limitations of self-attention, we devise a new attention operator that leverages the advantages of convolution. Unlike the conventional usage of an RPE (Eq. 3), we employ it as multiplicative weights for learning convolutional priors as follows:

$$ Y_{i,k} = \sum_{j}^{N} \bar{A}_{i,j} R_{i,j} V_{j,k}, \quad \bar{A}_{i,j} = \sum_{k}^{C} \bar{Q}_{i,k} \bar{K}_{j,k}. \quad (4) $$

Note that $\bar{Q}$, $\bar{K}$ are L2-normalized query and key, respectively. In Eq. 4, the RPE R not only learns relative token orders, but also actively adjusts the dot-product attention values with its learnable weights. We remove the softmax function to allow the attention kernel to include negative values, which may be effective for encoding structural information. The query and key are L2-normalized to obtain the normalization effect of a softmax, which is helpful for stabilizing the training procedure [33]. Since matrix multiplication between the Toeplitz matrix R and the value V is equivalent to a global convolution [42] that applies the convolution kernel $e \in \mathbb{R}^{2N-1}$ for the value V, the operator can also be considered as a global dynamic convolution where the dynamic component of the convolution kernel is based on the query-key correlation. Thus, the proposed operator merges the characteristics of self-attention and convolution.

**Learning structural patterns.** Nevertheless, the above operator is (Eq. 4) still limited for capturing rich structural patterns in the dot-product attention Ā since the N-size attention kernel for each query is aggregated with the value V before the patterns are encoded. To effectively capture the structural patterns, we aggregate and recompose the attention values with multiple RPEs. The updated operator is
9]. Convolution-based operators have dynamically adapted convolution kernels based on the input features [38–41]. However, these highly-expressive operators require high computational complexity and are typically limited to local interactions [7–9, 39]. One example is the relational self-attention (RSA) [9], which is related to our work. RSA is one of the most expressive operators that captures structural patterns with relational components, but it is also limited to local interactions due to its high computational complexity. In contrast, our proposed LiSA shows the highest level of expressivity by capturing long-range structural patterns with log-linear complexity.

**Lightweight operators.** Some of the existing lightweight attention operators factorize the softmax attention kernel [10, 11, 42, 43]. While they have linear complexity, they usually perform worse than the original attention in terms of accuracy [12, 15]. Other approaches have attempted to linearize RPE-added attention operators [13–15], but they still underperform on visual recognition. Recently, a few approaches adopt FFTs for efficiently covering global receptive fields [15, 44, 45]. The Global Filter (GF) layer [44] is one such operator, which implements an efficient global circular convolution with FFTs. However, the representation power of the GF layer is constrained since its static kernels hinder adaptation to general visual concepts. Our LiSA also adopts FFTs to improve efficiency, but it focuses on learning structural patterns with its dynamic attention kernels, leading to better performance.

**Convolutional attention operators.** Recent approaches try to combine transformers and CNNs to leverage the best of each world. Some of them incorporate convolutions into the attention operators [2, 16, 17, 19, 20, 46] to increase the expressivity of self-attention. They often apply depthwise convolutions before computing attention to capture structural information. Inception Mixer [19] splits the input channels and processes convolution and attention in parallel to increase the representation power. While these operators are more expressive than the original attention, they highly depend on static convolution kernels for learning discriminative features. In contrast to these, our LiSA captures discriminative features by dynamic structure-aware attention kernels, which are beneficial for learning richer visual concepts.

# 3 Background

**Self-attention.** The self-attention operator [47] is a core component in transformer architectures that generates query-key attention for updating the value. Let $N$ denote the sequence length (the number of tokens) and $C$ the number of input channels. Given an input feature $\mathbf{X} \in \mathbb{R}^{N \times C}$, query, key, value, $\mathbf{Q}, \mathbf{K}, \mathbf{V} \in \mathbb{R}^{N \times C}$, are first produced by independent linear projections, and each element of the output $\mathbf{Y} \in \mathbb{R}^{N \times C}$ of self-attention is expressed as

$$Y_{i,k} = \sum_{j}^{N} \sigma(A_{i,j}) V_{j,k}, \quad A_{i,j} = \frac{1}{\sqrt{C}} \sum_{k}^{C} Q_{i,k} K_{j,k}. \qquad (1)$$

Note that $\sigma$ is the softmax function along the $j$-axis. The two main characteristics of self-attention are that: (1) the operator represents a global interaction where the size of the attention kernel for each query is equal to $N$, and (2) the attention kernel dynamically changes according to the input feature. However, it is unable to encode the relative order of tokens due to the lack of convolutional inductive biases [37], resulting in performance degradation on visual recognition.

**Relative position embedding (RPE).** One of the popular schemes to handle the lack of convolutional inductive biases is adopting an RPE for the self-attention operator [5, 6, 37]. A common RPE has the shape of a Toeplitz matrix, and it consists of learnable weights which can be expressed as

$$\mathcal{T}(e) = \begin{pmatrix} e_N & e_{N+1} & e_{N+2} & \cdots & e_{2N-1} \\ e_{N-1} & e_N & e_{N+1} & \cdots & e_{2N-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ e_1 & e_2 & e_3 & \cdots & e_N \end{pmatrix}, \qquad (2)$$

where $e = \{e_1, e_2, \cdots e_{2N-1}\}$. When RPE is added, the attention operator is formulated as

$$Y_{i,k} = \sum_{j}^{N} \sigma(A_{i,j} + R_{i,j}) V_{j,k}, \quad \mathbf{R} = \mathcal{T}(e) \in \mathbb{R}^{N \times N}. \qquad (3)$$
formulated as:

$$
\begin{align}
Y_{i,k} &= \sum_{j}^{N} \sum_{d}^{D} \sum_{n}^{N} (\bar{A}_{i,n} R_{i,n,d}^{a}) (R_{i,j,d}^{b} V_{j,k} + B_{k,d}^{b}) \nonumber \\
&= \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} \sum_{j,n}^{N} (\bar{K}_{n,c} R_{i,n,d}^{a}) (R_{i,j,d}^{b} V_{j,k} + B_{k,d}^{b}), \tag{5}
\end{align}
$$

where $\mathbf{R}^a = \{\mathcal{T}(\mathbf{e}_1^a), \mathcal{T}(\mathbf{e}_2^a), \dots, \mathcal{T}(\mathbf{e}_D^a)\}$, $\mathbf{R}^b = \{\mathcal{T}(\mathbf{e}_1^b), \mathcal{T}(\mathbf{e}_2^b), \dots, \mathcal{T}(\mathbf{e}_D^b)\} \in \mathbb{R}^{N \times N \times D}$ are RPE tensors composed of sets of Toeplitz matrices and $\mathbf{B}^b \in \mathbb{R}^{C \times D}$ is a learnable projection matrix, respectively. Note that $D$ is the number of hidden channels. The computational graph of Eq. 5 is illustrated in Fig. 2. For each query, the learnable RPE tensor $\mathbf{R}^a$ captures structural patterns by encoding attention values as a $D$-size vector. We utilize this vector in two ways: first, for generating a new structure-aware attention kernel along the $j$-axis with the RPE tensor $\mathbf{R}^b$, and then also directly projected as a feature representation with the learnable matrix $\mathbf{B}^b$. The generated attention kernel with $\mathbf{R}^b$ updates $\mathbf{V}$ in a structure-aware manner like the relational kernel of RSA [23]. The feature representation with $\mathbf{B}^b$ directly encodes structural patterns, which is related to correlation-based representations [24, 48]. While these prior methods have focused on capturing local structures by convolutions, our operator captures global geometric structures through RPEs.

## 4.2. Improving the Expressivity of SA

We can further improve its expressivity by exploiting semantic information of the input channels. Here we describe the advanced form of structure-aware attention.

**Capturing channel-wise structural patterns.** To exploit the semantics of the input channels, we employ a different type of query-key correlation, the Hadamard-product correlation. A few approaches [23, 61] have demonstrated that Hadamard-product correlation is more effective than the dot-product one due to the use of richer query-key semantics. Considering the Hadamard correlation is a 3-dimensional tensor $\tilde{A}_{i,n,c} = \tilde{Q}_{i,c} \tilde{K}_{n,c} \in \mathbb{R}^{N \times N \times C}$, we expand the RPE tensor $\tilde{\mathbf{R}}^a$ by $C$ channels for encoding the Hadamard correlation. The modified operator is formulated as follows:

$$
Y_{i,k} = \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} \sum_{j,n}^{N} (\bar{K}_{n,c} \tilde{R}_{i,n,c,d}^{a}) (R_{i,j,d}^{b} V_{j,k} + B_{k,d}^{b}), \quad (6)
$$

where $\tilde{\mathbf{R}}^a \in \mathbb{R}^{N \times N \times C \times D}$ is the expanded RPE tensor, and learnable weights in the tensor increase from $\mathbf{E}^a = \{\mathbf{e}_1^a, \mathbf{e}_2^a, \dots, \mathbf{e}_D^a\} \in \mathbb{R}^{(2N-1) \times D}$ to $\tilde{\mathbf{E}}^a = \{\mathbf{e}_1^a, \mathbf{e}_2^a, \dots, \mathbf{e}_C^a\} \in \mathbb{R}^{(2N-1) \times C \times D}$. In Eq. 6, for each

<table><caption>Table 1. Comparison of complexity of the operators. $N, C, D$ denote the sequence length, the number of channels, and the number of latent channels respectively. Our operator has log-linear and linear complexity in computation and memory respectively.</caption><thead><tr><th>operator</th><th>computation</th><th>memory</th></tr></thead><tbody><tr><td>self-attention [47]</td><td>O(N<sup>2</sup>C)</td><td>O(N<sup>2</sup> + NC)</td></tr><tr><td>structure-aware attention (Eq. 4)</td><td>O(N<sup>2</sup>C)</td><td>O(N<sup>2</sup> + NC)</td></tr><tr><td>structure-aware attention (Eq. 5)</td><td>O(N<sup>2</sup>CD)</td><td>O(NCD)</td></tr><tr><td>LiSA (FFT approximation)</td><td>O(NCD log<sub>2</sub> N)</td><td>O(NCD)</td></tr></tbody></table>

query, the expanded tensor $\tilde{\mathbf{R}}^a$ captures channel-wise structural patterns by encoding a $(N \times C)$ Hadamard correlation matrix as a $D$-size vector. Since this process does not require additional computation, the operator can exploit rich semantics through the Hadamard correlation by only increasing the number of parameters.

**Combining features based on input semantics.** While the current form relies on query-key similarities for extracting features, we can also produce a different type of features that are fully based on input semantics, through a simple bias term. When we add a bias term $\mathbf{B}^a \in \mathbb{R}^{C \times D}$ to Eq 6,

$$
\begin{align}
Y_{i,k} &= \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} \sum_{j,n}^{N} (\bar{K}_{n,c} \tilde{R}_{i,n,c,d}^{a} + B_{c,d}^{a}) \tag{7} \\
&= \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} \sum_{j,n}^{N} (\bar{K}_{n,c} \tilde{R}_{i,n,c,d}^{a} R_{i,j,d}^{b} V_{j,k} \nonumber \\
&\phantom{= \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} \sum_{j,n}^{N} (\bar{K}_{n,c} \tilde{R}_{i,n,c,d}^{a} R_{i,j,d}^{b} V_{j,k} } + B_{c,d}^{a} R_{i,j,d}^{b} V_{j,k} + \bar{K}_{n,c} \tilde{R}_{i,n,c,d}^{a} B_{k,d}^{b} + B_{c,d}^{a} B_{k,d}^{b}). \tag{8}
\end{align}
$$

In Eq. 8, we obtain two additional terms. While the last term $(\sum_{c,d}^{C,D} \bar{Q}_{i,c} B_{c,d}^a B_{k,d}^b)$ is a common linear projection of the query feature, the second term $(\sum_{c,j,d}^{C,N,D} \bar{Q}_{i,c} B_{c,d}^a R_{i,j,d}^b)$ produces a different type of features. Considering the multiplication between Toeplitz matrices $\mathbf{R}^b$ and the value $\mathbf{V}$ is equivalent to a global convolution, the second term can be regarded as a global dynamic convolution, where the dynamic component is based on the query semantics. This is roughly equivalent to Lambda convolution or Involution operators [2, 26], which have shown the generated features are effective for learning spatial structures. Similarly, our operator gets the benefit of combining features based on input semantics through the additive bias term.

## 4.3. Lightweight Structure-aware Attention (LiSA)

Although our proposed operator (SA) is highly-expressive, it is impractical for neural architectures due to its huge computational complexity. Here we describe our final form, LiSA, which significantly reduces the complexity by efficiently processing the heavy RPE tensors through FFTs.

**Approximating RPEs with FFTs.** In Eq. 7, RPE tensor
<figure><img src="image_3.png" /><figcaption>Fig. 2: Computational graph of Structure-aware Attention (SA) for each query. After obtaining the query-key dot-product correlation (Ā), structural patterns in Ā are encoded by Rª, and utilized in two ways: 1) the patterns are used for generating a structure-aware attention kernel with Rᵇ, and 2) directly projected as a structural feature with B. Note that N = H × W, C = 1 in this figure.</figcaption></figure>

By introducing relative positional information into attention, the self-attention operator obtains the ability to learn convolutional inductive biases.

Limitations of self-attention with RPE.

Despite several approaches showing the effectiveness of RPE, the attention operator still has some limitations. First, the expressivity of the operator is insufficient; it is difficult to capture geometric structures (e.g., image gradients, video motion) since the softmax attention kernel may not be effective for encoding gradient information due to its non-negativity [9, 48]. Second, although the attention A suppresses photometric variations and reveals geometric structures [21, 23], the kernel is aggregated with the value V without leveraging structural patterns within A. Third, the operator suffers from quadratic complexity (O(N²)) since the non-linear softmax function and RPE are hard to linearize. Although a few approaches [10–12, 15] have attempted to approximate the softmax function with kernelized methods to make the operator more efficient, they do not improve over the original transformer in accuracy due to its training instability [15] or approximation errors [12].

# 4 Structure-aware Attention

## 4.1 Basic Form of Structure-aware Attention (SA)

Learning convolutional inductive biases. To handle the limitations of self-attention, we devise

a new attention operator that leverages the advantages of convolution. Unlike the conventional usage of an RPE (Eq. 3), we employ it as multiplicative weights for learning relative token orders as follows:

$$Y_{i,k} = \sum_{j}^{N} \bar{A}_{i,j} R_{i,j} V_{j,k}, \quad \bar{A}_{i,j} = \sum_{k}^{C} \bar{Q}_{i,k} \bar{K}_{j,k}. \qquad (4)$$

Note that $\bar{Q}$, $\bar{K}$ are L2-normalized query and key, respectively. In Eq. 4, the RPE R not only learns relative token orders, but also actively adjusts the attention values. We remove the softmax function to allow the attention kernel to include negative values, which may be effective for encoding structural information. Instead, the query and key are L2-normalized to stabilize the training procedure [15]. Since the matrix multiplication between the Toeplitz matrix R and the value V is equivalent to a global convolution [49] that applies the convolution kernel $e \in \mathbb{R}^{2N-1}$ for the value V, the operator can also be interpreted as a dynamic global convolution where the dynamic component of the convolution kernel is based on the attention Ā. Thus, the proposed operator merges the characteristics of self-attention and convolution.

Learning structural patterns. Nevertheless, the above operator (Eq. 4) is still limited for capturing rich structural patterns within the attention Ā. The RPE R is only element-wise multiplied with Ā, but it cannot extract meaningful features within the query-key correlation. To handle this,
<figure><img src="image_3.png" /><figcaption>Figure 3. Computational graph of LiSA and its block configuration. See text for details.</figcaption></figure>

multiplications can be considered as global convolutions:

$$Y_{i,k} = \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} (G_{i,c,d}^{a} + B_{c,d}^{a})(G_{i,k,d}^{b} + B_{k,d}^{b}), \quad (9)$$

$$\text{where } \mathbf{G}^a = \bar{\mathbf{K}} * \tilde{\mathbf{E}}^a, \mathbf{G}^b = \mathbf{V} * \mathbf{E}^b \in \mathbb{R}^{N \times C \times D}.$$

Note that $\mathbf{E}^b = \{e_1^b, e_2^b, \dots, e_D^b\} \in \mathbb{R}^{(2N-1) \times D}$ are learnable weights of the RPE tensor $\mathbf{R}^b$, and $*$ denotes convolution. $\mathbf{G}^b$ is a global convolution that applies the global kernels $\mathbf{E}^b \in \mathbb{R}^{(2N-1) \times D}$ for value $\mathbf{V} \in \mathbb{R}^{N \times C}$ by sharing the kernels across $C$ channels, and $\mathbf{G}^a$ is a depth-wise global convolution that applies the global kernels $\tilde{\mathbf{E}}^a \in \mathbb{R}^{(2N-1) \times C \times D}$ for the key $\bar{\mathbf{K}} \in \mathbb{R}^{N \times C}$. To reduce the complexity of these global convolutions, we approximate them as global circular convolutions, indicating that the RPEs are altered by circular position embeddings consisting of circulant matrices. These circular convolutions can be efficiently computed by FFTs [39] via the convolution theorem of Fourier transform: multiplication in the frequency domain is equal to circular convolution in the time domain. Thus, we can rewrite the convolutions as:

$$\begin{aligned} \mathbf{G}^a &\approx \bar{\mathbf{K}} \otimes \mathbf{W}^a = \mathcal{F}^{-1}(\mathcal{F}(\bar{\mathbf{K}}) \odot \mathcal{F}(\mathbf{W}^a)), \\ \mathbf{G}^b &\approx \mathbf{V} \otimes \mathbf{W}^b = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{V}) \odot \mathcal{F}(\mathbf{W}^b)), \end{aligned} \quad (10)$$

Note that $\mathbf{W}^a = \{\mathbf{w}_1^a, \dots, \mathbf{w}_D^a\} \in \mathbb{R}^{N \times C \times D}$, $\mathbf{W}^b = \{\mathbf{w}_1^b, \dots, \mathbf{w}_D^b\} \in \mathbb{R}^{N \times D}$ are learnable weights of the circular convolutions and $\otimes, \odot, \mathcal{F}, \mathcal{F}^{-1}$ denotes circular convolution, element-wise multiplication, FFT, and IFFT, respectively. The circular convolutions have the half size of parameters since the kernel size reduces from $(2N-1)$ to $N$. As shown in Tab. 1, we reduce the complexity in computation and memory on a linear scale by approximating heavy global interactions with FFTs. Moreover, since the input features and weights are real-valued, we can additionally reduce the complexity by half via RFFT and inverse RFFT. The computational graph of LiSA is illustrated in Fig. 3.

<table><caption>Table 2. Detailed configurations of different variants of LiSANet. For hierarchical models, we provide the number of channels and blocks in 4 stages. FLOPs are calculated with a 224 × 224 input.</caption><thead><tr><th>Model</th><th>#Blocks</th><th>#Channels (#heads)</th></tr></thead><tbody><tr><td>LiSANet-I-T</td><td>12</td><td>192 (12)</td></tr><tr><td>LiSANet-H-S</td><td>[1, 2, 11, 2]</td><td>[64 (4), 128 (8), 256 (16), 512 (32)]</td></tr><tr><td>LiSANet-H-B</td><td>[2, 3, 16, 3]</td><td>[96 (6), 192 (12), 384 (24), 768 (48)]</td></tr></tbody></table>

# 5. Experiments

We first describe the implementation details and then present extensive results. This includes a set of comprehensive ablation studies and a state-of-the-art comparison on ImageNet-1K [11]. Finally, we also verify the effectiveness of LiSA on object detection with COCO [29], and video action recognition with Something-Something-V2 (SSV2) [15].

## 5.1. Implementation details

**LiSA block.** Our proposed block follows the traditional transformers sequence of layers [1, 12, 45]: layer normalization (LN), attention operator, LN and MLP. Instead of using a traditional attention operator, we use LiSA. The latent channel size *D* is set to 16 as default. The overall block configuration is shown in Fig. 3.

**LiSANet.** To demonstrate the effectiveness of LiSA, we define two different style transformer architectures as shown in Tab. 2. The first style is an isotropic model (LiSANet-I-T) which has no downsampling layers and fixes the number of tokens (14 × 14) at all depths. The second style is hierarchical models (LiSANet-H-S, LiSANet-H-B) following the recent hierarchical ViT architectures [27, 30, 39]. Hierarchical models (LiSANet-H-S, LiSANet-H-B) are composed of 4 stages with a different number of blocks, and the number of tokens is downsampled in each stage. All the details of our variants are summarized in the Supplementary Material.

**Setup.** For ImageNet-1K, our isotropic model (LiSANet-I-T) is trained for 150 epochs, and hierarchical models
we directly extract structural patterns from $\tilde{A}$ and regenerate the attention kernel using multiple RPEs. The updated operator is formulated as:

$$Y_{i,k} = \sum_{j}^{N} \sum_{d}^{D} \sum_{n}^{N} (\bar{A}_{i,n} R_{i,n,d}^{a}) (R_{i,j,d}^{b} V_{j,k} + B_{k,d}) \quad (5)$$

where $R^a = \{\mathcal{T}(e_1^a), \mathcal{T}(e_2^a), \dots, \mathcal{T}(e_D^a)\}$, $R^b = \{\mathcal{T}(e_1^b), \mathcal{T}(e_2^b), \dots, \mathcal{T}(e_D^b)\} \in \mathbb{R}^{N \times N \times D}$ are RPE tensors composed of sets of Toeplitz matrices and $B \in \mathbb{R}^{C \times D}$ is a learnable projection matrix, respectively. Note that $D$ is the size of structural patterns. The computational graph of Eq. 5 is illustrated in Fig. 2. For each query, the learnable RPE tensor $R^a$ captures structural patterns by encoding the $N$-size attention kernel as a $D$-size vector. We utilize this vector in two ways: first, to generate a new structure-aware attention kernel along the $j$-axis using the RPE tensor $R^b$; second, to project it as a feature representation with the learnable matrix $B$. In summary, the generated attention kernel updates $V$ in a structure-aware manner, and the projected feature represents the encoded structural patterns.

Note that our method differs from convolutional attention operators [2, 16, 17, 19, 20] in the way of learning discriminative features. Convolutional attention operators process convolution and attention separately in a sequential [2, 16, 17, 20] or a parallel [19] way. These operators rely on convolution to obtain structural information from the input feature; however, their ability is limited because the convolution kernels are static and have restricted receptive fields. They cannot leverage rich structural patterns within the query-key correlation. In contrast to these operators, our structure-aware attention obtains structural information from the query-key correlation and has global receptive fields.

## 4.2 Improving the Expressivity of SA

We can further improve its expressivity by exploiting semantic information of the input channels. Here we describe the advanced form of our structure-aware attention.

**Capturing channel-wise structural patterns.** To exploit the semantics of the input

<table><caption>**Table 1: Comparison of complexity of the operators.** $N, C, D$ denote the sequence length, the number of channels, and the size of structural patterns, respectively. Our operator has log-linear and linear complexity in computation and memory, respectively.</caption><thead><tr><th>operator</th><th>computation</th><th>memory</th></tr></thead><tbody><tr><td>self-attention [47]</td><td>O(N<sup>2</sup>C)</td><td>O(N<sup>2</sup> + NC)</td></tr><tr><td>structure-aware attention (Eq. 4)</td><td>O(N<sup>2</sup>C)</td><td>O(N<sup>2</sup> + NC)</td></tr><tr><td>structure-aware attention (Eq. 5)</td><td>O(N<sup>2</sup>CD)</td><td>O(NCD)</td></tr><tr><td>LiSA (FFT approximation)</td><td>O(NCD log<sub>2</sub> N)</td><td>O(NCD)</td></tr></tbody></table>

channels, we employ a different type of query-key correlation, the Hadamard-product correlation. A few approaches [8, 9] have demonstrated that Hadamard-product correlation is more effective than the dot-product one due to the use of richer query-key semantics. Considering the Hadamard correlation is a 3-dimensional tensor $\tilde{A}_{i,n,c} = \tilde{Q}_{i,c} \tilde{K}_{n,c} \in \mathbb{R}^{N \times N \times C}$, we expand the RPE tensor $R^a$ by $C$ channels for encoding the Hadamard correlation. The modified operator is formulated as follows:

$$Y_{i,k} = \sum_{c}^{C} \sum_{d}^{D} \sum_{j,n}^{N} (\bar{A}_{i,n,c} \tilde{R}_{i,n,c,d}^{a}) (R_{i,j,d}^{b} V_{j,k} + B_{k,d}). \quad (6)$$

Note that $\tilde{R}^a \in \mathbb{R}^{N \times N \times C \times D}$ is the expanded RPE tensor and the number of learnable weights increases from $E^a = \{e_1^a, e_2^a, \dots, e_D^a\} \in \mathbb{R}^{(2N-1) \times D}$ to $\tilde{E}^a = \{e_1^a, e_2^a, \dots, e_D^a\} \in \mathbb{R}^{(2N-1) \times C \times D}$. In Eq. 6, for each query, the expanded tensor $\tilde{R}^a$ captures channel-wise structural patterns by encoding an $N \times C$ Hadamard correlation matrix as a $D$-size vector. Since this process does not require additional computation, the operator can exploit rich semantics through the Hadamard correlation by only increasing the number of parameters.

## 4.3 Lightweight Structure-aware Attention (LiSA)

Although our operator (SA) is highly-expressive, it is not easy to apply in neural architectures due to its high computational complexity. Here, we describe its final form, LiSA, which significantly reduces the complexity by efficiently processing the heavy RPE tensors through FFTs.
<table><caption>(a) Comparison with other basic operators.</caption><thead><tr><th>operator</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>Self-attn [47]</td><td>1.25 G</td><td>5.72 M</td><td>71.0</td><td>90.0</td></tr><tr><td>Self-attn w/ RPE [37]</td><td>1.25 G</td><td>5.72 M</td><td>72.2</td><td>90.9</td></tr><tr><td>Self-attn w/ RPE (C↑) [37]</td><td>1.40 G</td><td>6.44 M</td><td>73.4</td><td>91.6</td></tr><tr><td>Depthwise conv (7 × 7) [19]</td><td>0.84 G</td><td>4.49 M</td><td>69.0</td><td>89.2</td></tr><tr><td>GF layer [39]</td><td>0.82 G</td><td>4.90 M</td><td>69.5</td><td>89.4</td></tr><tr><td>GF layer (C↑) [39]</td><td>1.27 G</td><td>7.37 M</td><td>72.4</td><td>91.0</td></tr><tr><td>Lambda convolution [2]</td><td>2.41 G</td><td>5.41 M</td><td>72.6</td><td>91.0</td></tr><tr><td>RSA [23]</td><td>5.34 G</td><td>8.23 M</td><td>74.5</td><td>92.2</td></tr><tr><td>LiSA (ours)</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

<table><caption>(c) Impact of global interactions.</caption><thead><tr><th>kernel size</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>Local - 3 × 3</td><td>1.22 G</td><td>5.75 M</td><td>71.9</td><td>90.7</td></tr><tr><td>Local - 5 × 5</td><td>1.45 G</td><td>5.80 M</td><td>73.8</td><td>91.7</td></tr><tr><td>Local - 7 × 7</td><td>1.80 G</td><td>5.88 M</td><td>73.8</td><td>91.8</td></tr><tr><td>Global (ours)</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

<table><caption>(b) Effectiveness of LiSA components.</caption><thead><tr><th>operator</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>Self-attn</td><td>1.25 G</td><td>5.72 M</td><td>71.0</td><td>90.0</td></tr><tr><td>Self-attn w/ RPE</td><td>1.25 G</td><td>5.72 M</td><td>72.2</td><td>90.9</td></tr><tr><td>Self-attn w/ h RPEs</td><td>1.25 G</td><td>5.81 M</td><td>72.7</td><td>91.3</td></tr><tr><td>SA (Eq. 4)</td><td>1.25 G</td><td>5.72 M</td><td>72.4</td><td>91.2</td></tr><tr><td>SA (Eq. 4 w/ h RPEs)</td><td>1.25 G</td><td>5.81 M</td><td>73.6</td><td>91.7</td></tr><tr><td>SA (Eq. 5)</td><td>3.92 G</td><td>5.99 M</td><td>73.9</td><td>92.0</td></tr><tr><td>+ bias term B<sup>a</sup></td><td>3.92 G</td><td>5.99 M</td><td>74.2</td><td>92.1</td></tr><tr><td>+ Hadamard corr</td><td>3.92 G</td><td>8.09 M</td><td>74.9</td><td>92.3</td></tr><tr><td>LiSA (ours)</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

<table><caption>(d) Influence of the number of latent channels D.</caption><thead><tr><th>D</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>1</td><td>1.11 G</td><td>5.76 M</td><td>71.3</td><td>90.5</td></tr><tr><td>4</td><td>1.13 G</td><td>5.88 M</td><td>73.6</td><td>91.6</td></tr><tr><td>8</td><td>1.17 G</td><td>6.04 M</td><td>74.4</td><td>92.2</td></tr><tr><td>16 (ours)</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>Figure 4. Comparisons among LiSA & efficient attention blocks in (a) FLOPs, (b) latency, and (c) memory. Dotted lines denote estimated values due to the limited GPU memory. The latency and memory is measured by an RTX A5000 GPU with batch size 16.</figcaption></figure>

(LiSANet-H-S, LiSANet-H-B) are trained for 300 epochs. We follow the rest of the training recipes suggested in [30,45] for a fair comparison. For COCO, we adopt standard Mask R-CNN [17] detection frameworks, which employ ImageNet-1K pre-trained weights for fine-tuning. We use a 1× schedule (12 epochs), and follow the same recipe as in [30]. For SS-V2, the isotropic model (LiSANet-I-T) is trained for 60 epochs from scratch, and we adopt the uniform sampling strategy [49] for training and a single crop inference for testing. Other recipes are in the Supplementary Material.

## 5.2. Ablation studies

We use the isotropic model (LiSANet-I-T) for ablations since the operators with quadratic complexity are hard to be adopted for hierarchical models due to their extreme memory consumption shown in Fig. 4c. Unless specified otherwise, we use 224 × 224 resolution for input.

**Comparison with other operators.** In Tab. 3a, we compare our LiSA operator with several others, including self-attention [37,47], convolution [19,39], and highly-expressive operators [2,23]. For a fair comparison, we only replace our operator with others in the LiSA blocks, and all the recep-

tive fields are set as global, except for the 7 × 7 depthwise convolution [19]. As expected, self-attention with RPE [37] outperforms vanilla self-attention [47] in accuracy, showing the impact of convolutional inductive biases. GF layer [39], an FFT-based global convolution, outperforms local depthwise convolution [19], and the accuracy becomes comparable to the self-attention when increasing FLOPs (6th row). However, the accuracy of the GF layer is lower than Lambda convolution or RSA due to the limited expressivity. RSA [23] shows the effectiveness of learning structural patterns with high accuracy, but it requires a huge computation budget. LiSA shows the best trade-off between accuracy and FLOPs, achieving the best accuracy among the operators with lower FLOPs. The accuracy of LiSA is even 1.5% higher than the self-attention with increased parameters (3rd row), indicating that the accuracy gain of LiSA does not come from the increased parameters.

**Effectiveness of LiSA components.** In Tab. 3b, we demonstrate the effectiveness of each component of LiSA. We first compare the way of learning convolutional inductive biases between self-attention and ours (Eq. 4). With the same FLOPs and the number of parameters, our approach that uses
<figure><img src="image_4.png" /><figcaption>Fig. 3: Computational graph of LiSA and its block configuration. See text for details.</figcaption></figure>

**Approximating RPEs with FFTs.** Unlike the original attention (Eq. 3), the multiplicative RPEs ($\tilde{R}^a, \tilde{R}^b$) and the absence of softmax enable the permutation of the computation order, and thus, the rearranged equation is expressed as:

$$ 
\begin{aligned}
Y_{i,k} &= \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} \sum_{j,n}^{N} \bar{K}_{n,c} \tilde{R}_{i,n,c,d}^{a} (R_{i,j,d}^{b} V_{j,k} + B_{k,d}), \\
&= \sum_{c}^{C} \bar{Q}_{i,c} \sum_{d}^{D} G_{i,c,d}^{a} (G_{i,k,d}^{b} + B_{k,d}),
\end{aligned}
\quad (7) $$

$$ \text{where } \mathbf{G}^a = \bar{\mathbf{K}} * \tilde{\mathbf{E}}^a, \mathbf{G}^b = \mathbf{V} * \mathbf{E}^b \in \mathbb{R}^{N \times C \times D}. $$

Note that $\mathbf{E}^b = \{e_1^b, e_2^b, \dots, e_D^b\} \in \mathbb{R}^{(2N-1) \times D}$ are learnable weights of $\mathbf{R}^b$, and $*$ denotes convolution. $\mathbf{G}^b$ is a global convolution that applies the global kernels $\mathbf{E}^b \in \mathbb{R}^{(2N-1) \times D}$ to the value $\mathbf{V}$ by sharing the kernels across $C$ channels, and $\mathbf{G}^a$ is a depth-wise global convolution that applies the global kernels $\tilde{\mathbf{E}}^a \in \mathbb{R}^{(2N-1) \times C \times D}$ to the key $\bar{\mathbf{K}}$. In Eq. 8, improving the efficiency of SA has shifted to efficiently processing global convolutions.

To reduce the complexity of global convolutions, we approximate them as global circular convolutions [44], indicating that the RPEs are replaced by circular position embeddings consisting of circular matrices. These circular convolutions can be efficiently computed by FFTs via the convolution theorem of Fourier transform: multiplication in the frequency domain is equal to circular convolution in the time domain. Thus, we can rewrite the equation as follows:

$$ \mathbf{G}^a \approx \bar{\mathbf{K}} \circledast \mathbf{W}^a = \mathcal{F}^{-1}(\mathcal{F}(\bar{\mathbf{K}}) \odot \mathcal{F}(\mathbf{W}^a)), \quad (8) $$

$$ \mathbf{G}^b \approx \mathbf{V} \circledast \mathbf{W}^b = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{V}) \odot \mathcal{F}(\mathbf{W}^b)). \quad (9) $$

Note that $\mathbf{W}^a = \{\mathbf{w}_1^a, \dots, \mathbf{w}_{CD}^a\} \in \mathbb{R}^{N \times C \times D}$, $\mathbf{W}^b = \{\mathbf{w}_1^b, \dots, \mathbf{w}_D^b\} \in \mathbb{R}^{N \times D}$ are learnable weights of the circular convolutions and $\circledast, \odot, \mathcal{F}, \mathcal{F}^{-1}$ denote circular convolution, element-wise multiplication, FFT, and IFFT, respectively. The circular convolutions have half the size of parameters since the kernel size reduces from $2N-1$ to $N$. As shown in Tab. 1, we reduce the complexity in computation and memory on a log-linear scale by approximating heavy global interactions with FFTs. The computational graph of LiSA is illustrated in Fig. 3. Moreover, we further reduce the complexity by half using RFFT and inverse RFFT. Implementing Eq. 9 using standard GPU libraries has an IO bottleneck in throughput since it reads and writes the intermediate results repeatedly. We adopt the kernel fusion strategy [50] to overcome this by fusing the entire computation of Eq. 9 into a single kernel and computing it in SRAM.

# 5 Experiments

We first describe the implementation details and then present extensive results. This includes a set of comprehensive analyses and a state-of-the-art comparison on ImageNet-1K [25] and ImageNet-21k [51]. Finally, we also verify the effectiveness of LiSA on video action recognition with Kinetics-400 [26], object detection with COCO [27], and semantic segmentation with ADE-20K [28].

## 5.1 Implementation details

**LiSA block.** Our proposed block follows the traditional transformers sequence of layers [1, 4, 31]: layer normalization (LN), attention operator, LN
an RPE as multiplicative weights ("SA (Eq. 4)"), 4th row in the table) is better than standard self-attention with RPE (2nd row) in accuracy. The accuracy gap between self-attention and ours becomes more clear when we use an independent RPE for each head (3rd row vs. 5th row), indicating our RPEs defined in Eq. 4 are more beneficial than those of standard self-attention. This indicates that our attention containing negative values is potentially more effective for learning spatial features such as gradient information compared to softmax attention. Next, we demonstrate our structure-aware attention variants in the third part of the table. Comparing Eq. 4 with Eq. 5 (4th row vs. 6th row), we validate the effectiveness of learning structural patterns, which improves by 1.5% in top-1 accuracy. The next two rows in the table show the impact of exploiting semantic information of input channels. With the bias term $B^a$ and the Hadamard correlation, our operator improves the top-1 accuracy by 1.0% with negligible additional cost. Lastly, LiSA with FFT approximation dramatically reduces the computational cost (3×) without compromising accuracy.

**Effect of global interactions.** Tab. 3c studies the influence of local and global interactions. Focusing on the local kernels (first three rows in the table), the larger the kernel, the larger the number of parameters, FLOPs, and accuracies. This shows that a big kernel with more trainable parameters produces better results but at an increased computational cost. However, our global version (last row) allows a larger number of parameters with smaller FLOPs due to FFT, resulting in the best performance among all the variants.

**Effect of the number of latent channels D.** Tab. 3d summarizes this study using four different values of D. Since D represents the size of the encoded vector that learns structural patterns from the query-key correlation, it is expected that larger values result in better performances. As shown in Tab. 3d, the accuracy is indeed improved with larger values of D, being 16 the best one. We use this value in our attention kernel. Note that the cases over $D = 16$ are not reported since the accuracy becomes saturated.

**Efficiency of the LiSA block.** In Fig. 4, we demonstrate the efficiency of LiSA in terms of FLOPs, latency, and GPU memory consumption. We measure the performance of a single block ($C = 96$) by varying the number of tokens. For a fair comparison, we replace our LiSA block with other attention blocks [14, 30]. Window attention block [30] efficiently computes local attention with shifted windows, and pooling attention block [14] downsamples the key and value before computing attention for reducing complexity. We set the window size as $N/4$ and the pooling stride as $2 \times 2$. Window and pooling attention are more efficient than the standard one in all cases, but their values increase exponentially since their computational complexities are still quadratic in the number of tokens. In comparison, the values of LiSA increase gracefully due to the log-linear complexity, and thus

<table><caption>Table 4. Comparison to the state-of-the-art models on ImageNet. We compare our models with several state-of-the-art architectures. FLOPs (G), the number of parameters (M), top-1, top-5 accuracy (%) on ImageNet validation set are shown. All the models use 224 × 224 resolution images for training and testing.</caption><thead><tr><th>model</th><th>attn+conv</th><th>FLOPs</th><th>#params</th><th>top-1</th></tr></thead><tbody><tr><td>ResNet-50 [18]</td><td></td><td>4.1 G</td><td>26 M</td><td>76.1</td></tr><tr><td>PVT-S [51]</td><td></td><td>3.8 G</td><td>25 M</td><td>79.8</td></tr><tr><td>Deit-S [45]</td><td></td><td>4.6 G</td><td>22 M</td><td>79.9</td></tr><tr><td>RegNetY-4.0GF [36]</td><td></td><td>4.0 G</td><td>21 M</td><td>80.0</td></tr><tr><td>Swin-Ti [30]</td><td></td><td>4.5 G</td><td>29 M</td><td>81.2</td></tr><tr><td>T2T-ViT-14 [56]</td><td></td><td>4.8 G</td><td>22 M</td><td>81.5</td></tr><tr><td>GFNet-H-S [39]</td><td></td><td>4.6 G</td><td>32 M</td><td>81.5</td></tr><tr><td>CvT-13 [53]</td><td>✓</td><td>4.5 G</td><td>20 M</td><td>81.6</td></tr><tr><td>CoAtNet-0 [10]</td><td>✓</td><td>4.2 G</td><td>25 M</td><td>81.6</td></tr><tr><td>MViTv2-T [28]</td><td>✓</td><td>4.7 G</td><td>24 M</td><td>82.3</td></tr><tr><td>LiSANet-H-S (ours)</td><td></td><td>2.9 G</td><td>19 M</td><td><strong>82.5</strong></td></tr><tr><td>ResNet-101 [18]</td><td></td><td>7.9 G</td><td>45 M</td><td>77.4</td></tr><tr><td>RegNetY-8.0GF [36]</td><td></td><td>8.0 G</td><td>39 M</td><td>81.7</td></tr><tr><td>PVT-L [51]</td><td></td><td>9.8 G</td><td>61 M</td><td>81.7</td></tr><tr><td>Deit-B [45]</td><td></td><td>17.5 G</td><td>86 M</td><td>81.8</td></tr><tr><td>T2T-ViT-24 [56]</td><td></td><td>13.8 G</td><td>64 M</td><td>82.3</td></tr><tr><td>CvT-21 [53]</td><td>✓</td><td>7.1 G</td><td>32 M</td><td>82.5</td></tr><tr><td>GFNet-H-B [39]</td><td></td><td>8.6 G</td><td>54 M</td><td>82.9</td></tr><tr><td>Swin-S [30]</td><td></td><td>8.7 G</td><td>50 M</td><td>83.1</td></tr><tr><td>Swin-B [30]</td><td></td><td>15.4 G</td><td>88 M</td><td>83.4</td></tr><tr><td>CoAtNet-1 [10]</td><td>✓</td><td>8.4 G</td><td>42 M</td><td>83.3</td></tr><tr><td>CoAtNet-2 [10]</td><td>✓</td><td>15.7 G</td><td>75 M</td><td>84.1</td></tr><tr><td>MViTv2-B [28]</td><td>✓</td><td>10.2 G</td><td>52 M</td><td><strong>84.4</strong></td></tr><tr><td>LiSANet-H-B (ours)</td><td></td><td>9.6 G</td><td>59 M</td><td><strong>84.4</strong></td></tr></tbody></table>

<table><caption>Table 5. Comparison with other models on COCO object detection. FLOPs (G), the number of parameters (M), box mAP (AP<sup>b</sup>) and mask mAP (AP<sup>m</sup>) are shown. Note that FLOPs are measured at resolution 800 × 1280.</caption><thead><tr><th rowspan="2">model</th><th rowspan="2">FLOPs</th><th rowspan="2">#params</th><th colspan="5">Mask R-CNN 1 × schedule</th></tr><tr><th>AP<sup>b</sup></th><th>AP<sup>b</sup><sub>50</sub></th><th>AP<sup>b</sup><sub>75</sub></th><th>AP<sup>m</sup></th><th>AP<sup>m</sup><sub>50</sub></th><th>AP<sup>m</sup><sub>75</sub></th></tr></thead><tbody><tr><td>Res-50 [18]</td><td>260 G</td><td>44 M</td><td>38.0</td><td>58.6</td><td>41.4</td><td>34.4</td><td>55.1</td><td>36.7</td></tr><tr><td>PVT-S [51]</td><td>245 G</td><td>44 M</td><td>42.9</td><td>65.8</td><td>47.1</td><td>40.0</td><td>62.7</td><td>42.9</td></tr><tr><td>Twins-S [8]</td><td>238 G</td><td>44 M</td><td>24.0</td><td>50.0</td><td>41.4</td><td>34.4</td><td>55.1</td><td>36.7</td></tr><tr><td>Swin-T [30]</td><td>264 G</td><td>48 M</td><td>42.2</td><td>64.6</td><td>46.2</td><td>39.1</td><td>61.6</td><td>42.0</td></tr><tr><td>ViL-S [59]</td><td>218 G</td><td>45 M</td><td>44.9</td><td>67.1</td><td>49.3</td><td>41.0</td><td>64.2</td><td>44.1</td></tr><tr><td>Focal-T [55]</td><td>291 G</td><td>49 M</td><td>44.8</td><td>67.7</td><td>49.2</td><td>41.0</td><td>64.7</td><td>44.2</td></tr><tr><td>LiSANet-H-S</td><td>232 G</td><td>38 M</td><td><strong>46.1</strong></td><td><strong>67.9</strong></td><td><strong>50.5</strong></td><td><strong>41.6</strong></td><td><strong>64.8</strong></td><td><strong>44.9</strong></td></tr></tbody></table>

LiSA achieves the best efficiency in all cases. Additional details are presented in the Supplementary Material.

## 5.3. State-of-the-art Results on ImageNet-1K

In Tab. 4, we compare our two hierarchical models with state-of-the-art approaches including CNNs [18, 36], ViTs [30, 39, 45, 51, 56], and the models containing both convolution and self-attention [10, 28, 53] (marked with ✓ in ‘attn+conv’ column). In the top half of the table, we present the results of small models that have comparable FLOPs
<table><caption>**Table 2:** Detailed configurations of different variants of LiSANet. For hierarchical models, we provide the number of channels and blocks in 4 stages.</caption><thead><tr><th>Model</th><th>#Blocks</th><th>#Channels (#heads)</th></tr></thead><tbody><tr><td>LiSANet-I</td><td>12</td><td>192 (12)</td></tr><tr><td>LiSANet-S</td><td>[2, 4, 12, 4]</td><td>[64 (4), 128 (8), 320 (20), 384 (24)]</td></tr><tr><td>LiSANet-B</td><td>[4, 8, 18, 3]</td><td>[96 (6), 192 (12), 384 (24), 576 (36)]</td></tr><tr><td>HyLiSANet-S</td><td>[3, 6, 12, 4]</td><td>[64, 128, 320 (20), 384 (24)]</td></tr><tr><td>HyLiSANet-B</td><td>[3, 12, 18, 3]</td><td>[96, 192, 384 (24), 576 (36)]</td></tr></tbody></table>

and MLP. Instead of using a traditional attention operator, we use LiSA. The overall block configuration is shown in Fig. 3.

**LiSANet.** To demonstrate the effectiveness of LiSA, we define three different variant architectures as shown in Tab. 2. The first variant is an *isotropic model* (LiSANet-I), which has no downsampling layers and fixes the number of tokens (14 × 14) at all depths. The second is *hierarchical ViTs* (LiSANet-S, LiSANet-B) consisting of LiSA blocks. All of the hierarchical ViTs are composed of 4 stages with a different number of blocks, and the number of tokens is downsampled in each stage. And, the third is *hybrid ViTs* (HyLiSANet-S, HyLiSANet-B) following the strategy of recent hybrid models [2, 19, 37]. We adopt depthwise convolutions for the early two stages, which allows for constructing deeper layers for high-resolution stages. The structural pattern size *D* is set to 16 for LiSANet-I and 8 for the other models. Like many previous backbones [16, 18, 52–55], we adopt convolutional position embedding [56] and convolutional MLP [18] for our models. All the details of our variants are summarized in Sec.A.1. of the supplementary material.

## 5.2 LiSA Analysis

**Setup.** We use the isotropic model (LiSANet-I) for analyses since the operators with quadratic complexity are hard to be adopted for hierarchical models due to their extreme memory consumption. LiSANet-I is trained for 150 epochs on ImageNet1K, and we follow the rest of the training recipes suggested in [4, 6] for a fair comparison. Unless specified otherwise, we use 224 × 224 resolution for input.

**Comparison with other operators.** In Tab. 3a, we compare our LiSA operator with

several others, including self-attention [5, 47], convolution [44, 57], and the other expressive operators [7, 9, 16, 19]. For a fair comparison, we only replace our operator with those others in the LiSA blocks, and all the receptive fields are set as global, except for the 7 × 7 depthwise convolution [57]. LiSA substantially outperforms self-attention with and without RPE [5] (first two rows) in accuracy, showing the impact of learning structural patterns. The accuracy of LiSA is even 1.5% higher than the self-attention with larger channels (3rd row), indicating that the gain does not come from the increased parameters. LiSA also performs better than the GF layer [44] (5, 6th rows), which is equal to a global circular convolution. This implies that the adjustable attention kernel of LiSA is a better fit for learning various visual concepts rather than the static convolution kernel.

For the convolutional attention operator (8, 9th rows), we adopt multi-scale attention [16], one of the advanced operators. The operator applies a 3 × 3 depthwise convolutions for the input features before computing attention, and the stride is set to 1 × 1. Inception mixer [19] splits input channels and processes convolution and attention in parallel for learning both high and low-frequency features, and the stride is set to 1 × 1. To demonstrate fair comparisons between these advanced attention operators with ours, we match the number of parameters and FLOPs in a similar scale by increasing the number of channels (9, 10th rows). Convolutional attention and Inception mixer perform better than self-attention in accuracy, but their accuracies are lower than that of LiSA, even with larger FLOPs and number of parameters. We conjecture that LiSA learns better discriminative features by capturing structural patterns inside the attention. RSA [9] shows high accuracy by learning structural patterns via its relational components, but it requires a significantly large computation budget due to the larger correlation. In contrast, LiSA shows the best trade-off between accuracy and FLOPs, achieving the best accuracy among the operators with lower FLOPs.

**Effectiveness of LiSA components.** In Tab. 3b, we provide a detailed analyses of the components of LiSA. We first compare how convolutional inductive biases are learned in self-attention by our (Eq. 4) parameters. For the same FLOPs and the number of parameters, our approach
<table><caption>Table 6. Comparison with other basic operators on SS-V2. Top-1, top-5 accuracy (%), FLOPs (G) and the number of parameters (M) are shown.</caption><thead><tr><th>operator</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>Self-attention [47]</td><td>7.36 G</td><td>5.82 M</td><td>18.0</td><td>40.9</td></tr><tr><td>Self-attention w/ RPE [37]</td><td>7.36 G</td><td>5.87 M</td><td>24.0</td><td>50.0</td></tr><tr><td>Depthwise conv (3 × 7 × 7) [19]</td><td>3.75 G</td><td>4.82 M</td><td>33.0</td><td>60.9</td></tr><tr><td>GF layer [39]</td><td>3.53 G</td><td>6.54 M</td><td>28.7</td><td>40.0</td></tr><tr><td>Lambda convolution [2]</td><td>26.87 G</td><td>6.34 M</td><td>34.5</td><td>63.1</td></tr><tr><td>RSA [23]</td><td>72.58 G</td><td>23.45 M</td><td>34.1</td><td>62.7</td></tr><tr><td>LiSA (ours)</td><td>5.16 G</td><td>8.37 M</td><td><b>38.1</b></td><td><b>67.1</b></td></tr></tbody></table>

and the number of parameters. Models that incorporate convolutions into ViTs [10, 53] perform better than the others on the accuracy measure. Our proposed model, LiSANet-H-S, clearly outperforms all the other models in terms of both accuracy and FLOPs. In the case of larger models, grouped in the bottom half of the table, many of the methods show comparable performance. Swin-S & -B [30] shows the effectiveness of hierarchical ViT based on its efficient window attention technique. CoAtNet-1 & -2 [10] obtains an effective result by adopting depthwise convolutions in the early stages and self-attentions in the latter stages. MViTv2-B [28], which shows the highest accuracy, adopts depthwise convolutions and additional residual connections inside the attention blocks for the performance boost. While these models rely on elaborated architecture designs, our proposed model, LiSANet-H-B, is a pure transformer architecture without any complicated modification, achieving state-of-the-art accuracy with less computation.

## 5.4. Object Detection & Video Action Recognition

**Object detection on COCO.** To show the generalization ability of LiSA, we conduct object detection experiments on the COCO dataset using the standard Mask R-CNN [17] detection framework with ImageNet-1K pre-trained weights and following the experimental setup in [30] (1× schedule of 12 epochs). In Tab. 5, we compare the results of small models that have comparable FLOPs and parameters. As expected, LiSANet-H-S shows the best performance among CNN [18] and ViT [30, 51, 55, 59] backbones in AP<sup>b</sup> and AP<sup>m</sup>, while maintaining its efficiency. Since object detection is a high-resolution computer vision task (e.g., 800 × 1280), these results demonstrate that LiSA is a better fit for processing a large number of tokens compared to other attention methods [30, 51, 55].

**Video action recognition on SS-V2.** We perform experiments on video data to show the wide applicability of LiSA. We compare LiSA with other attention operators trained from scratch on SS-V2 [15] in Tab. 6. We sample 8 frames per video, and the rest of the details are the same as in Sec. 5.2. Since structural patterns of videos, i.e., motion patterns, are important cues for recognizing video actions,

<figure><img src="image_5.png" /><figcaption>Figure 5. Attention kernels of self-attention & LiSA. Attention kernels from different layers and heads are visualized. For each sample, the top row is self-attention and the bottom is LiSA. Note that the red box in the center of each subfigure is the query pixel.</figcaption></figure>

the operators that learn convolutional priors [2, 19, 39, 61] or geometric structures [23] are more effective than their self-attention counterparts [37, 47]. LiSA shows even better performance on video than image, in terms of both accuracy and complexity. While FLOPs of the attention [47, 61] and highly-expressive [2, 23] operators significantly grow due to the increased number of tokens (T × H × W), LiSA remains efficient due to its log-linear complexity.

## 5.5. Visualization

In Fig. 5, we visualize both self-attention and LiSA kernels of different layers and heads from isotropic models. As expected, LiSA kernels contain much more diverse patterns compared to self-attention kernels. Self-attention kernels in the early layers often fail to capture relevant context, and those in the latter layers are effective but they usually capture redundant information. Unlike self-attention, LiSA kernels in the early layers focus on encoding local features. Some of these look similar to Sobel filters or Laplacian filters, which are beneficial for learning local structural information. Considering that modern hybrid models [10, 27, 54], which replace self-attention with convolution in early layers obtain an extra accuracy gain, the behavior of LiSA kernels in early layers seems reasonable. Meanwhile, LiSA kernels in the latter layers concentrate on the context relevant to the target object like self-attention does. LiSA, however, generates more diverse shapes of kernels than self-attention, which implies that they aggregate the relevant context and further consider structural patterns inside the context at the aggregation. Therefore, this visualization demonstrates that our structure-aware attention kernel can be more expressive and flexible compared to the self-attention kernel.
<table><thead><tr><th>index</th><th>operator</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>1</td><td>Self-attn [47]</td><td>1.25 G</td><td>5.72 M</td><td>71.0</td><td>90.0</td></tr><tr><td>2</td><td>Self-attn w/ RPE [5]</td><td>1.25 G</td><td>5.72 M</td><td>72.2</td><td>90.9</td></tr><tr><td>3</td><td>Self-attn w/ RPE (C↑) [5]</td><td>1.40 G</td><td>6.44 M</td><td>73.4</td><td>91.6</td></tr><tr><td>4</td><td>Depthwise conv (7×7) [57]</td><td>0.84 G</td><td>4.49 M</td><td>69.0</td><td>89.2</td></tr><tr><td>5</td><td>GF layer [44]</td><td>0.82 G</td><td>4.90 M</td><td>69.5</td><td>89.4</td></tr><tr><td>6</td><td>GF layer (C↑) [44]</td><td>1.27 G</td><td>7.37 M</td><td>72.4</td><td>91.0</td></tr><tr><td>7</td><td>Lambda convolution [7]</td><td>2.41 G</td><td>5.41 M</td><td>72.6</td><td>91.0</td></tr><tr><td>8</td><td>Convolutional attn [16]</td><td>1.26 G</td><td>5.78 M</td><td>73.3</td><td>91.7</td></tr><tr><td>9</td><td>Convolutional attn (C↑) [16]</td><td>1.41 G</td><td>6.49 M</td><td>74.1</td><td>92.1</td></tr><tr><td>10</td><td>Inception mixer (C↑) [19]</td><td>1.28 G</td><td>6.36 M</td><td>74.4</td><td>92.1</td></tr><tr><td>11</td><td>RSA [9]</td><td>5.34 G</td><td>8.23 M</td><td>74.5</td><td>92.2</td></tr><tr><td>12</td><td>LiSA (ours)</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

(a) Comparison with other operators.

<table><thead><tr><th>index</th><th>D</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>1</td><td>1</td><td>1.11 G</td><td>5.76 M</td><td>71.3</td><td>90.5</td></tr><tr><td>2</td><td>4</td><td>1.13 G</td><td>5.88 M</td><td>73.6</td><td>91.6</td></tr><tr><td>3</td><td>8</td><td>1.17 G</td><td>6.04 M</td><td>74.4</td><td>92.2</td></tr><tr><td>4</td><td>16</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

(c) Effect of the structural patterns (D).

<table><thead><tr><th>index</th><th>operator</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>1</td><td>Self-attn</td><td>1.25 G</td><td>5.72 M</td><td>71.0</td><td>90.0</td></tr><tr><td>2</td><td>Self-attn w/ RPE</td><td>1.25 G</td><td>5.72 M</td><td>72.2</td><td>90.9</td></tr><tr><td>3</td><td>Self-attn w/ h RPEs</td><td>1.25 G</td><td>5.81 M</td><td>72.7</td><td>91.3</td></tr><tr><td>4</td><td>SA (Eq. 4)</td><td>1.25 G</td><td>5.72 M</td><td>72.4</td><td>91.2</td></tr><tr><td>5</td><td>SA (Eq. 4 w/ h RPEs)</td><td>1.25 G</td><td>5.81 M</td><td>73.6</td><td>91.7</td></tr><tr><td>6</td><td>SA (Eq. 5)</td><td>3.92 G</td><td>5.99 M</td><td>74.2</td><td>92.1</td></tr><tr><td>7</td><td>+ Hadamard corr</td><td>3.92 G</td><td>8.09 M</td><td>74.9</td><td>92.3</td></tr><tr><td>8</td><td>LiSA (ours)</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

(b) Effectiveness of LiSA components.

<table><thead><tr><th>index</th><th>kernel size</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>1</td><td>Local - 3 × 3</td><td>1.22 G</td><td>5.75 M</td><td>71.9</td><td>90.7</td></tr><tr><td>2</td><td>Local - 5 × 5</td><td>1.45 G</td><td>5.80 M</td><td>73.8</td><td>91.7</td></tr><tr><td>3</td><td>Local - 7 × 7</td><td>1.80 G</td><td>5.88 M</td><td>73.8</td><td>91.8</td></tr><tr><td>4</td><td>Global (ours)</td><td>1.21 G</td><td>6.36 M</td><td><strong>74.9</strong></td><td><strong>92.4</strong></td></tr></tbody></table>

(d) Effect of global interactions.

<table><caption>Table 3: LiSA analysis on ImageNet-1K. Top-1, top-5 accuracy (%), FLOPs (G) and the number of parameters (M) are shown.</caption><thead><tr><th rowspan="2">block</th><th colspan="3">(H,W) = (7,7)</th><th colspan="3">(H,W) = (14,14)</th><th colspan="3">(H,W) = (28,28)</th><th colspan="3">(H,W) = (56,56)</th><th colspan="3">(H,W) = (84,84)</th></tr><tr><th>FLOPs</th><th>mem</th><th>latency</th><th>FLOPs</th><th>mem</th><th>latency</th><th>FLOPs</th><th>mem</th><th>latency</th><th>FLOPs</th><th>mem</th><th>latency</th><th>FLOPs</th><th>mem</th><th>latency</th></tr><tr><th></th><th>(M)↓</th><th>(M)↓</th><th>(ms)↓</th><th>(M)↓</th><th>(M)↓</th><th>(ms)↓</th><th>(M)↓</th><th>(M)↓</th><th>(ms)↓</th><th>(G)↓</th><th>(G)↓</th><th>(ms)↓</th><th>(G)↓</th><th>(G)↓</th><th>(ms)↓</th></tr></thead><tbody><tr><td>Self-attn [47]</td><td>22.7</td><td><strong>18.1</strong></td><td><strong>0.9</strong></td><td>102.0</td><td>21.7</td><td>1.6</td><td>584.0</td><td>282.4</td><td>13.0</td><td>5.2</td><td>14.7</td><td>174.7</td><td>22.2</td><td>OOM</td><td>OOM</td></tr><tr><td>Convolutional attn [16]</td><td>23.1</td><td><strong>18.1</strong></td><td>1.7</td><td>104.0</td><td>23.9</td><td>2.7</td><td>413.0</td><td>135.4</td><td>8.5</td><td>1.6</td><td>2.6</td><td>30.5</td><td>3.7</td><td>3.4</td><td>68.0</td></tr><tr><td>LiSA (ours)</td><td><strong>21.8</strong></td><td>18.3</td><td>1.2</td><td><strong>87.3</strong></td><td><strong>20.3</strong></td><td><strong>1.3</strong></td><td><strong>349.0</strong></td><td><strong>87.4</strong></td><td><strong>4.6</strong></td><td><strong>1.4</strong></td><td><strong>0.8</strong></td><td><strong>19.8</strong></td><td><strong>3.1</strong></td><td><strong>1.7</strong></td><td><strong>45.0</strong></td></tr></tbody></table>

<caption>Table 4: Comparisons among LiSA & attention operators in FLOPs, memory, and latency. The memory & latency is measured by an RTX A5000 (batch=32, channels=192). OOM is an abbreviation of out-of-memory.</caption>

that uses an RPE as multiplicative weights ("SA (Eq. 4)", 4th row in the table) is better than standard self-attention with RPE (2nd row) in accuracy. The accuracy gap between self-attention and ours becomes more clear when we use independent learnable weights (RPE) for each attention head (3rd vs. 5th row), thus showing that our RPEs defined in Eq. 4 are more beneficial than those of standard self-attention. This indicates that our attention containing negative values is potentially more effective for learning spatial features such as gradient information compared to softmax attention. Next, we demonstrate our structure-aware attention variants in the third part of the table. Comparing Eq. 4 with Eq. 5 (4th vs. 6th row), we validate the effectiveness of learning structural patterns, which improves by 1.8% in top-1 accuracy. With the Hadamard correlation, our operator improves

the top-1 accuracy by 1.0% without any additional FLOPs. Lastly, LiSA with FFT approximation dramatically reduces the computational cost (3×) without compromising accuracy.

Effect of the structural patterns *D*. Our *D* parameter represents the size of the encoded vector that learns structural patterns from the query-key correlation. Thus, larger values are expected to result in better performances. Tab. 3c shows the impact of the structural patterns by varying the values of *D*. As shown in Tab. 3c, the size of *D* significantly impacts the accuracy, which implies the importance of structural patterns. The accuracy is indeed improved with larger values of *D*, 16 being the best one. Compared to the results of Tab. 3a, the case of *D* = 8 already surpasses all the other operators in accuracy except for RSA. Note that
# 6. Conclusion

In this paper, we have presented LiSA, a novel expressive, yet efficient, attention operator that learns rich structural patterns with log-linear complexity. Our comprehensive ablation studies have shown that the ViTs based on LiSA, LiSANets, outperform their counterparts in accuracy and computational complexity. Our LiSANet, which is purely based on LiSA for spatial modeling, has achieved competitive performance on various kinds of visual understanding tasks. We believe that LiSA can be further extended for diverse understanding tasks, including machine translation.

# Acknowledgments

This work has been supported in part by the ANR grant AVENUE (ANR-18-CE23-0011), the Junta de Andalucía of Spain (P18-FR-3130 and P20_00430, including European Union funds) and the Ministry of Education of Spain (PID2019-105396RB-I00). We also thank the EuroHPC JU for the GPU computing hours.

# References

[1] Anurag Arnab, Mostafa Dehghani, Georg Heigold, Chen Sun, Mario Lučić, and Cordelia Schmid. Vivit: A video vision transformer. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021. 2, 5, 12

[2] Irwan Bello. Lambdanetworks: Modeling long-range interactions without attention. In Proc. International Conference on Learning Representations (ICLR), 2021. 1, 2, 4, 6, 8

[3] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Proc. European Conference on Computer Vision (ECCV), 2020. 2

[4] Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, et al. Mmdetection: Open mmlab detection toolbox and benchmark. arXiv preprint arXiv:1906.07155, 2019. 12

[5] Peng Chen. Permuteformer: Efficient relative position encoding for long sequences. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing (EMNLP), 2021. 1, 2

[6] Yinpeng Chen, Xiyang Dai, Mengchen Liu, Dongdong Chen, Lu Yuan, and Zicheng Liu. Dynamic convolution: Attention over convolution kernels. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020. 2

[7] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. In Proc. International Conference on Learning Representations (ICLR), 2021. 1, 2, 3

[8] Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen. Twins: Revisiting the design of spatial attention in vision transformers. Proc. Neural Information Processing Systems (NeurIPS), 2021. 7

[9] Ekin Dogus Cubuk, Barret Zoph, Jon Shlens, and Quoc Le. Randaugment: Practical automated data augmentation with a reduced search space. Proc. Neural Information Processing Systems (NeurIPS), 33:18613–18624, 2020. 12

[10] Zihang Dai, Hanxiao Liu, Quoc V Le, and Mingxing Tan. Coatnet: Marrying convolution and attention for all data sizes. In Proc. Neural Information Processing Systems (NeurIPS), 2021. 1, 2, 7, 8

[11] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009. 2, 5

[12] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In Proc. International Conference on Learning Representations (ICLR), 2021. 1, 2, 5

[13] Stéphane d'Ascoli, Hugo Touvron, Matthew L Leavitt, Ari S Morcos, Giulio Biroli, and Levent Sagun. Convit: Improving vision transformers with soft convolutional inductive biases. In Proc. International Conference on Machine Learning (ICML), 2021. 2

[14] Haoqi Fan, Bo Xiong, Karttikeya Mangalam, Yanghao Li, Zhicheng Yan, Jitendra Malik, and Christoph Feichtenhofer. Multiscale vision transformers. In Proc. IEEE International Conference on Computer Vision (ICCV), 2021. 2, 7

[15] Raghav Goyal, Samira Ebrahimi Kahou, Vincent Michal- ski, Joanna Materzynska, Susanne Westphal, Heuna Kim, Valentin Haenel, Ingo Fruend, Peter Yianilos, Moritz Mueller- Freitag, et al. The" something something" video database for learning and evaluating visual common sense. In Proc. IEEE International Conference on Computer Vision (ICCV), 2017. 2, 5, 8

[16] Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. Proc. Neural Information Processing Systems (NeurIPS), 34, 2021. 2

[17] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Gir- shick. Mask R-CNN. In Proc. IEEE International Conference on Computer Vision (ICCV), 2017. 6, 8, 12

[18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016. 7, 8

[19] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv:1704.04861, 2017. 6, 8

[20] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. Deep networks with stochastic depth. In Proc. European Conference on Computer Vision (ECCV), 2016. 12

[21] Xu Jia, Bert De Brabandere, Tinne Tuytelaars, and Luc Van Gool. Dynamic filter networks. In Proc. Neural Information Processing Systems (NeurIPS), 2016. 2

[22] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are rnns: Fast autoregressive
<table><caption>**Table 5: Comparison to the state-of-the-art models on ImageNet-1K.** FLOPs (G), the number of parameters (M), top-1 accuracy (%) on the ImageNet validation set are shown. All the models use 224 × 224 resolution images.</caption><thead><tr><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td></td><td>type</td><td>model</td><td>FLOPs</td><td>#params</td><td>top-1</td></tr><tr><td rowspan="5">CNN</td><td rowspan="5">ViT</td><td>ResNet-50 [58]</td><td>4.1 G</td><td>26 M</td><td>76.1</td></tr><tr><td>RegNetY-4.0GF [59]</td><td>4.0 G</td><td>21 M</td><td>80.0</td></tr><tr><td>GFNet-H-S [44]</td><td>4.6 G</td><td>32 M</td><td>81.5</td></tr><tr><td>ConvNext-T [60]</td><td>4.5 G</td><td>29 M</td><td>82.1</td></tr><tr><td>InternImage-T [54]</td><td>5.0 G</td><td>30 M</td><td>83.5</td></tr><tr><td rowspan="5">Hybrid</td><td rowspan="5">ViT</td><td>PVT-S [61]</td><td>3.8 G</td><td>25 M</td><td>79.8</td></tr><tr><td>Deit-S [4]</td><td>4.6 G</td><td>22 M</td><td>79.9</td></tr><tr><td>Swin-Ti [6]</td><td>4.5 G</td><td>29 M</td><td>81.2</td></tr><tr><td>T2T-ViT-14 [3]</td><td>4.8 G</td><td>22 M</td><td>81.5</td></tr><tr><td>CSwin-T [36]</td><td>4.3 G</td><td>23 M</td><td>82.7</td></tr><tr><td></td><td></td><td>LiSANet-S (ours)</td><td>3.9 G</td><td>25 M</td><td><strong>83.4</strong></td></tr><tr><td rowspan="7">CNN</td><td rowspan="7">Hybrid</td><td>CvT-13 [17]</td><td>4.5 G</td><td>20 M</td><td>81.6</td></tr><tr><td>CoAtNet-0 [37]</td><td>4.2 G</td><td>25 M</td><td>81.6</td></tr><tr><td>MViTv2-T [16]</td><td>4.7 G</td><td>24 M</td><td>82.3</td></tr><tr><td>iFormer-S [19]</td><td>4.8 G</td><td>20 M</td><td>83.4</td></tr><tr><td>Slide-PVTv2-B2 [55]</td><td>4.2 G</td><td>23 M</td><td>82.7</td></tr><tr><td>UniFormer-S [53]</td><td>3.6 G</td><td>22 M</td><td>82.9</td></tr><tr><td>SMT-S [52]</td><td>4.7 G</td><td>21 M</td><td><strong>83.7</strong></td></tr><tr><td></td><td></td><td>HyLiSANet-S (ours)</td><td>4.5 G</td><td>24 M</td><td><strong>83.7</strong></td></tr><tr><td rowspan="5">CNN</td><td rowspan="5">ViT</td><td>ResNet-101 [58]</td><td>7.9 G</td><td>45 M</td><td>77.4</td></tr><tr><td>RegNetY-8.0GF [59]</td><td>8.0 G</td><td>39 M</td><td>81.7</td></tr><tr><td>GFNet-H-B [44]</td><td>8.6 G</td><td>54 M</td><td>82.9</td></tr><tr><td>ConvNext-B [60]</td><td>15.4 G</td><td>89 M</td><td>83.8</td></tr><tr><td>InternImage-S [54]</td><td>8.0 G</td><td>50 M</td><td>84.2</td></tr><tr><td rowspan="6">Hybrid</td><td rowspan="6">ViT</td><td>PVT-L [61]</td><td>9.8 G</td><td>61 M</td><td>81.7</td></tr><tr><td>Deit-B [4]</td><td>17.5 G</td><td>86 M</td><td>81.8</td></tr><tr><td>T2T-ViT-24 [3]</td><td>13.8 G</td><td>64 M</td><td>82.3</td></tr><tr><td>Swin-B [6]</td><td>15.4 G</td><td>88 M</td><td>83.5</td></tr><tr><td>CSwin-B [36]</td><td>15.0 G</td><td>78 M</td><td>84.2</td></tr><tr><td>LiSANet-B (ours)</td><td>10.4 G</td><td>51 M</td><td><strong>84.6</strong></td></tr><tr><td rowspan="11">Hybrid</td><td rowspan="11">ViT</td><td>UniFormer-B [53]</td><td>8.3 G</td><td>50 M</td><td>83.9</td></tr><tr><td>CoAtNet-2 [37]</td><td>15.7 G</td><td>75 M</td><td>84.1</td></tr><tr><td>VAN-B4 [62]</td><td>12.2 G</td><td>60 M</td><td>84.2</td></tr><tr><td>Slide-Swin-B [55]</td><td>15.5 G</td><td>89 M</td><td>84.2</td></tr><tr><td>MViTv2-B [16]</td><td>10.2 G</td><td>52 M</td><td>84.4</td></tr><tr><td>MaxViT-S [20]</td><td>11.7 G</td><td>69 M</td><td>84.5</td></tr><tr><td>iFormer-B [19]</td><td>9.4 G</td><td>48 M</td><td>84.6</td></tr><tr><td>SMT-L [52]</td><td>17.7 G</td><td>81 M</td><td>84.6</td></tr><tr><td>Slide-CSwin-B [55]</td><td>15.0 G</td><td>78 M</td><td>84.7</td></tr><tr><td>iFormer-L [19]</td><td>14.0 G</td><td>87 M</td><td>84.8</td></tr><tr><td>HyLiSANet-B (ours)</td><td>11.7 G</td><td>50 M</td><td><strong>85.0</strong></td></tr></tbody></table>

the cases over $D = 16$ are not reported since the accuracy becomes saturated.

**Effect of global interactions.** Tab. 3d studies the influence of local and global LiSA kernels. Focusing on the local LiSA kernels (first three rows in the table), the larger the kernel, the larger the number of parameters, FLOPs, and accuracies. This shows that a big kernel with more trainable parameters produces better results but at an increased computational cost. However, our global version (last row) allows a larger number of parameters with smaller FLOPs due to FFT, resulting in the best performance among all the variants.

**Efficiency of the LiSA block.** In Tab. 4, we demonstrate the efficiency of LiSA in terms of FLOPs, memory consumption, and latency. We

compare our LiSA block with a standard attention block and measure the performance of a single block ($C = 192$) by varying the number of tokens. We also compare the LiSA block with a convolutional attention block [16], which downsamples the query and key to 14 × 14 before computing attention by depthwise convolutions with multiple strides. This attention block is more efficient than the standard one on high-resolutions (e.g., 28 × 28, 56 × 56), but it becomes less efficient on low-resolutions due to added depthwise convolutions. In comparison, the efficiency values of LiSA increase gracefully due to the log-linear complexity, and thus LiSA achieves the best computational performance except for 7 × 7, where LiSA is slightly slower due to a higher number of sequential operations. Additional details are presented in the supplementary material.

## 5.3 Image classification

**ImageNet-1K.** We train our hierarchical models (LiSANet-S, LiSANet-B, HyLiSANet-S, HyLiSANet-B) for 300 epochs, and follow the rest of the training recipes suggested in [4, 6] for a fair comparison. In Tab. 5, we compare our hierarchical models with state-of-the-art approaches on ImageNet-1K, including CNNs [44, 58, 59], ViTs [3, 4, 6, 36, 61], and hybrid models containing both convolution and self-attention [16, 17, 19, 20, 37, 52–55]. In the top half of the table, we present the results of small models with comparable FLOPs and number of parameters. Our pure ViT model, LiSANet-S, clearly outperforms all the other ViTs in terms of accuracy and FLOPs, demonstrating the effectiveness of LiSA. Compared with other hybrid models, our HyLiSANet-S achieves better or similar results than other approaches with comparable FLOPs and number of parameters.

In the case of larger models, grouped in the bottom half of the table, again our pure ViT model, LiSANet-B, obtains the best accuracy with the lowest FLOPs and number of parameters, showing the benefits of our LiSA operator. Focusing on the hybrid models, our proposed HyLiSANet achieves the best accuracy (85.0%) with much lower FLOPS and number of parameters than other approaches. Thus, our proposed models achieve state-of-the-art results, especially for large models, improving traditional ViTs and more complex models that rely on additional techniques such as
transformers with linear attention. In Proc. International Conference on Learning Representations (ICLR), 2020. 2

[23] Manjin Kim, Heeseung Kwon, Chunyu Wang, Suha Kwak, and Minsu Cho. Relational self-attention: What's missing in attention for video understanding. In Proc. Neural Information Processing Systems (NeurIPS), 2021. 1, 2, 3, 4, 6, 8

[24] Heeseung Kwon, Manjin Kim, Suha Kwak, and Minsu Cho. Learning self-similarity in space and time as generalized motion for video action recognition. In Proc. IEEE International Conference on Computer Vision (ICCV), 2021. 3, 4

[25] James Lee-Thorp, Joshua Ainslie, Ilya Eckstein, and Santiago Ontanon. Fnet: Mixing tokens with fourier transforms. arXiv preprint arXiv:2105.03824, 2021. 2

[26] Duo Li, Jie Hu, Changhu Wang, Xiangtai Li, Qi She, Lei Zhu, Tong Zhang, and Qifeng Chen. Involution: Inverting the inherence of convolution for visual recognition. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021. 2, 4

[27] Kunchang Li, Yali Wang, Peng Gao, Guanglu Song, Yu Liu, Hongsheng Li, and Yu Qiao. Uniformer: Unified transformer for efficient spatiotemporal representation learning. In Proc. International Conference on Learning Representations (ICLR), 2022. 1, 2, 5, 8, 12, 13

[28] Yanghao Li, Chao-Yuan Wu, Haoqi Fan, Karttikeya Mangalam, Bo Xiong, Jitendra Malik, and Christoph Feichtenhofer. Mvitv2: Improved multiscale vision transformers for classification and detection. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2022. 2, 7, 8, 12, 13

[29] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft COCO: Common objects in context. In Proc. European Conference on Computer Vision (ECCV), 2014. 2, 5

[30] 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 Proc. IEEE International Conference on Computer Vision (ICCV), 2021. 1, 2, 5, 6, 7, 8, 12

[31] Antoine Liutkus, Ondrej Cifka, Shih-Lun Wu, Umut Simsekli, Yi-Hsuan Yang, and Gael Richard. Relative positional encoding for transformers with linear complexity. In Proc. International Conference on Machine Learning (ICML), 2021. 1, 2

[32] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proc. International Conference on Learning Representations (ICLR), 2018. 12

[33] Shengjie Luo, Shanda Li, Tianle Cai, Di He, Dinglan Peng, Shuxin Zheng, Guolin Ke, Liwei Wang, and Tie-Yan Liu. Stable, fast and accurate: Kernelized attention with relative positional encoding. In Proc. Neural Information Processing Systems (NeurIPS), 2021. 1, 2, 3

[34] Ningning Ma, Xiangyu Zhang, Jiawei Huang, and Jian Sun. Weightnet: Revisiting the design space of weight networks. In Proc. European Conference on Computer Vision (ECCV), 2020. 2

[35] Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. arXiv preprint arXiv:2202.08791, 2022. 1, 2, 3

[36] Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Designing network design spaces. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020. 7

[37] 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. arXiv preprint arXiv:1910.10683, 2019. 1, 2, 6, 8

[38] Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan Bello, Anselm Levskaya, and Jonathon Shlens. Stand-alone self-attention in vision models. In Proc. Neural Information Processing Systems (NeurIPS), 2019. 3

[39] Yongming Rao, Wenliang Zhao, Zheng Zhu, Jiwen Lu, and Jie Zhou. Global filter networks for image classification. In Proc. Neural Information Processing Systems (NeurIPS), 2021. 2, 5, 6, 7, 8, 12, 14

[40] Eli Shechtman and Michal Irani. Matching local self-similarities across images and videos. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007. 3

[41] Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention: Attention with linear complexities. In Proc. Winter Conference on Applications of Computer Vision (WACV), 2021. 2

[42] Gilbert Strang. A proposal for toeplitz matrix calculations. Studies in Applied Mathematics, 74(2):171–176, 1986. 3

[43] Robin Strudel, Ricardo Garcia, Ivan Laptev, and Cordelia Schmid. Segmenter: Transformer for semantic segmentation. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021. 2

[44] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proc. IEEE conference on computer vision and pattern recognition, 2016. 12

[45] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In Proc. International Conference on Machine Learning (ICML), 2021. 1, 2, 5, 6, 7, 12

[46] Ashish Vaswani, Prajit Ramachandran, Aravind Srinivas, Niki Parmar, Blake Hechtman, and Jonathon Shlens. Scaling local self-attention for parameter efficient visual backbones. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021. 2

[47] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proc. Neural Information Processing Systems (NeurIPS), 2017. 2, 4, 6, 8

[48] Heng Wang, Du Tran, Lorenzo Torresani, and Matt Feiszli. Video modeling with correlation networks. In Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020. 4
<table><caption>**Table 6:** Comparison with other models pre-trained on ImageNet-21K and fine-tuned on ImageNet-1K. Top-1 accuracy (%), FLOPs (G), and the number of parameters (M) are shown.</caption><thead><tr><th>model</th><th>img size</th><th>FLOPs</th><th>#params</th><th>top-1</th></tr></thead><tbody><tr><td>ConvNext-T [60]</td><td>224×224</td><td>4.5 G</td><td>29 M</td><td>82.9</td></tr><tr><td>ViT-B/16 [1]</td><td>384×384</td><td>55.4 G</td><td>88 M</td><td>84.0</td></tr><tr><td>ConvNext-S [60]</td><td>224×224</td><td>8.7 G</td><td>50 M</td><td>84.6</td></tr><tr><td>Swin-B [6]</td><td>224×224</td><td>15.4 G</td><td>88 M</td><td>85.2</td></tr><tr><td>ConvNext-B [60]</td><td>224×224</td><td>15.4 G</td><td>89 M</td><td>85.8</td></tr><tr><td>CSwin-B [36]</td><td>224×224</td><td>15.0 G</td><td>78 M</td><td>85.9</td></tr><tr><td>HyLiSANet-S</td><td>224×224</td><td>4.5 G</td><td>24 M</td><td>84.3</td></tr><tr><td>HyLiSANet-B</td><td>224×224</td><td>11.7 G</td><td>50 M</td><td><strong>86.2</strong></td></tr></tbody></table>

window attention (Swin [6]), depthwise convolutions plus self-attention (MViTv2 [16], SMT [52]) or processing convolution and attention in parallel (iFormer [19]). This indicates an essential difference between convolution and LiSA. Convolution-based models converge fast and are data-efficient by their strong inductive biases such as 2D locality, but their performance is restricted when the models are scaled up since convolution may hinder adaptation to general visual concepts due to its static kernels. Whereas, our model achieves great performance even with a larger scale since LiSA can adaptively aggregate spatial information by its structure-aware attention kernels.

**ImageNet-21K.** We have demonstrated the results with HyLiSNets fine-tuned from ImageNet-21k pre-training in Table 6 to check the behavior of our models in the large-scale data regime. We train 90 epochs for ImageNet-21K pre-training, and fine-tune 30 epochs on ImageNet-1K. We follow the setup of ConvNext [60] models for a fair comparison, and all the other details are summarized in Sec.A.2 of the supplementary material. When our models are pre-trained on ImageNet-21K, the accuracies are improved substantially. HyLiSANet-S & -B obtain 0.9% & 1.4% accuracy gains compared to the previous ImageNet-1K results, respectively. Considering iFormer [19] could not be trained on ImageNet-21K due to the manually defined channel ratio [19], these results demonstrate our models can learn general visual concepts when they can access a larger amount of training data. Both HyLiSANet-S and HyLiSANet-B outperform the other models with lower computation, showing the superior scalability of HyLiSNets.

**Throughput.** In Tab. 7, we compare our models with other low-latency ViTs [6, 60, 63] in terms of throughput to show the efficiency of FFTs in

<table><caption>**Table 7:** Throughput comparison among modern ViT models on ImageNet-1K. For the images per second (ims/s) metric, higher is better.</caption><thead><tr><th>model</th><th>img size</th><th>FLOPs</th><th>#params</th><th>mem</th><th>ims/s</th><th>top-1</th></tr></thead><tbody><tr><td>Swin-B [6]</td><td>224×224</td><td>15.4 G</td><td>88 M</td><td>1.8 G</td><td>306.7</td><td>83.5</td></tr><tr><td>Swin-B [6]</td><td>384×384</td><td>47.1 G</td><td>88 M</td><td>2.9 G</td><td>96.5</td><td>84.5</td></tr><tr><td>ConvNext-B [60]</td><td>224×224</td><td>15.4 G</td><td>89 M</td><td>1.8 G</td><td>312.5</td><td>83.8</td></tr><tr><td>ConvNext-L [60]</td><td>224×224</td><td>34.4 G</td><td>198 M</td><td>3.1 G</td><td>171.2</td><td>84.3</td></tr><tr><td>FastViT-SA36 [63]</td><td>384×384</td><td>12.6 G</td><td>30 M</td><td>4.2 G</td><td>194.6</td><td>84.5</td></tr><tr><td>FastViT-MA36 [63]</td><td>384×384</td><td>17.7 G</td><td>43 M</td><td>5.0 G</td><td>168.4</td><td>84.9</td></tr><tr><td>LiSANet-B</td><td>224×224</td><td>10.4 G</td><td>51 M</td><td>2.0 G</td><td>347.2</td><td>84.4</td></tr><tr><td>HyLiSANet-B</td><td>224×224</td><td>11.7 G</td><td>50 M</td><td>1.8 G</td><td>299.4</td><td>85.0</td></tr></tbody></table>

<table><caption>**Table 8:** Comparison to the other models on Kinetics-400. Pre-trained weights, FLOPs (G), and top-1 accuracy (%) on Kinetics-400 validation set are shown. All the models use 16 input frames except for Swin [68].</caption><thead><tr><th>type</th><th>model</th><th>pretrain</th><th>frame×<br>crops×clips</th><th>FLOPs</th><th>top-1</th></tr></thead><tbody><tr><td rowspan="2">CNN</td><td>X3D-XL [64]</td><td>-</td><td>16×3×10</td><td>1452 G</td><td>79.1</td></tr><tr><td>SlowFast+NL [65]</td><td>-</td><td>16×3×10</td><td>7020 G</td><td>79.8</td></tr><tr><td rowspan="5">ViT</td><td>X-ViT [66]</td><td>IN-21K</td><td>16×3×1</td><td>850 G</td><td>80.2</td></tr><tr><td>MFormer-L [67]</td><td>IN-21K</td><td>16×3×10</td><td>35553 G</td><td>80.2</td></tr><tr><td>ViViT-L [31]</td><td>IN-21K</td><td>16×3×4</td><td>17352 G</td><td>80.6</td></tr><tr><td>Swin-B [68]</td><td>IN-1K</td><td>32×3×4</td><td>3384 G</td><td>80.6</td></tr><tr><td>TimeSformer-L [69]</td><td>IN-21K</td><td>16×3×1</td><td>7140 G</td><td>80.7</td></tr><tr><td rowspan="5">Hybrid</td><td>MViT-B [70]</td><td>-</td><td>16×1×5</td><td>353 G</td><td>78.4</td></tr><tr><td>UniFormer-S [53]</td><td>IN-1K</td><td>16×1×4</td><td>167 G</td><td>80.8</td></tr><tr><td>MViTv2-S [16]</td><td>-</td><td>16×1×5</td><td>320 G</td><td>81.0</td></tr><tr><td>UniFormer-B [53]</td><td>IN-1K</td><td>16×1×4</td><td>389 G</td><td>82.0</td></tr><tr><td>HyLiSANet-S</td><td>IN-1K</td><td>16×1×4</td><td>165 G</td><td>81.1</td></tr><tr><td></td><td>HyLiSANet-B</td><td>IN-1K</td><td>16×1×4</td><td>428 G</td><td><strong>82.5</strong></td></tr></tbody></table>

LiSA. We measure the model throughputs with their respective official source codes by using an RTX6000 with batch size of 32. With 224 × 224 input, LiSANet-B outperforms both Swin-B [6] and ConvNext models (ConvNext-B, -L) [60] with higher accuracy. In addition, HyLiSANet-B outperforms much larger models (Swin-B with 384 × 384 input, ConvNext-L) in all metrics. FastViT [63] aims to improve the runtime of conventional ViTs by removing skip connections and applying the reparameterization technique. Regarding FastViT [63], our models are better in throughput with higher accuracies (e.g., 6th vs 8th rows), and HyLiSANet-B outperforms FastViT-MA36 in both metrics. Note that FastViT did not report the results on the 224 × 224 resolution.
[49] Limin Wang, Yuanjun Xiong, Zhe Wang, Yu Qiao, Dahua Lin, Xiaoou Tang, and Luc Van Gool. Temporal segment networks: Towards good practices for deep action recognition. In Proc. *European Conference on Computer Vision (ECCV)*, 2016. 6, 12
[50] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. *arXiv preprint arXiv:2006.04768*, 2020. 1, 2, 3
[51] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pyramidal vision transformer: A versatile backbone for dense prediction without convolutions. In Proc. *IEEE International Conference on Computer Vision (ICCV)*, 2021. 2, 7, 8
[52] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pvt v2: Improved baselines with pyramid vision transformer. *Computational Visual Media*, 8(3):415-424, 2022. 12
[53] Haiping Wu, Bin Xiao, Noel Codella, Mengchen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang. Cvt: Introducing convolutions to vision transformers. In Proc. *IEEE International Conference on Computer Vision (ICCV)*, 2021. 2, 7, 8
[54] Tete Xiao, Mannat Singh, Eric Mintun, Trevor Darrell, Piotr Dollár, and Ross Girshick. Early convolutions help transformers see better. In Proc. *Neural Information Processing Systems (NeurIPS)*, 2021. 2, 8
[55] Jianwei Yang, Chunyuan Li, Pengchuan Zhang, Xiyang Dai, Bin Xiao, Lu Yuan, and Jianfeng Gao. Focal attention for long-range interactions in vision transformers. Proc. *Neural Information Processing Systems (NeurIPS)*, 2021. 7, 8
[56] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zi-Hang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan. Tokens-to-token vit: Training vision transformers from scratch on imagenet. In Proc. *IEEE International Conference on Computer Vision (ICCV)*, 2021. 1, 2, 7
[57] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proc. *IEEE International Conference on Computer Vision (ICCV)*, pages 6023-6032, 2019. 12
[58] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In Proc. *International Conference on Learning Representations (ICLR)*, 2018. 12
[59] Pengchuan Zhang, Xiyang Dai, Jianwei Yang, Bin Xiao, Lu Yuan, Lei Zhang, and Jianfeng Gao. Multi-scale vision longformer: A new vision transformer for high-resolution image encoding. In Proc. *IEEE International Conference on Computer Vision (ICCV)*, 2021. 7, 8
[60] Zizhao Zhang, Han Zhang, Long Zhao, Ting Chen, and Tomas Pfister. Aggregating nested transformers. *arXiv preprint arXiv:2105.12723*, 2021. 2
[61] Hengshuang Zhao, Jiaya Jia, and Vladlen Koltun. Exploring self-attention for image recognition. In Proc. *IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, 2020. 1, 2, 4, 8
[62] Zhun Zhong, Liang Zheng, Guoliang Kang, Shaozi Li, and Yi Yang. Random erasing data augmentation. In Proc. *AAAI Conference on Artificial Intelligence (AAAI)*, 2020. 12
<table><caption>**Table 9: Comparison with other models on COCO validation set.** FLOPs (G), the number of parameters (M), box mAP (AP<sup>b</sup>) and mask mAP (AP<sup>m</sup>) are shown. Note that FLOPs are measured at resolution 800 × 1280.</caption><thead><tr><th rowspan="2">model</th><th rowspan="2">FLOPs</th><th rowspan="2">#params</th><th colspan="2">Mask</th><th colspan="2">R-CNN</th><th colspan="2">1× schedule</th><th colspan="2">mIOU (%)</th></tr><tr><th>AP<sup>b</sup></th><th>AP<sub>50</sub><sup>b</sup></th><th>AP<sub>75</sub><sup>b</sup></th><th>AP<sup>m</sup></th><th>AP<sub>50</sub><sup>m</sup></th><th>AP<sub>75</sub><sup>m</sup></th></tr></thead><tbody><tr><td>Res-50 [58]</td><td>260 G</td><td>44 M</td><td>38.0</td><td>58.6</td><td>41.4</td><td>34.4</td><td>55.1</td><td>36.7</td><td></td><td></td></tr><tr><td>PVT-S [61]</td><td>245 G</td><td>44 M</td><td>42.9</td><td>65.8</td><td>47.1</td><td>40.0</td><td>62.7</td><td>42.9</td><td></td><td></td></tr><tr><td>Twins-S [71]</td><td>238 G</td><td>44 M</td><td>24.0</td><td>50.0</td><td>41.4</td><td>34.4</td><td>55.1</td><td>36.7</td><td></td><td></td></tr><tr><td>Swin-T [6]</td><td>264 G</td><td>48 M</td><td>42.2</td><td>64.6</td><td>46.2</td><td>39.1</td><td>61.6</td><td>42.0</td><td></td><td></td></tr><tr><td>Vil-S [72]</td><td>218 G</td><td>45 M</td><td>44.9</td><td>67.1</td><td>49.3</td><td>41.0</td><td>64.2</td><td>44.1</td><td></td><td></td></tr><tr><td>Focal-T [73]</td><td>291 G</td><td>49 M</td><td>44.8</td><td>67.7</td><td>49.2</td><td>41.0</td><td>64.7</td><td>44.2</td><td></td><td></td></tr><tr><td>iFormer-S [19]</td><td>263 G</td><td>40 M</td><td>46.2</td><td>68.5</td><td>50.6</td><td>41.9</td><td>65.3</td><td>45.0</td><td></td><td></td></tr><tr><td>CSwin-T [36]</td><td>279 G</td><td>42 M</td><td>46.7</td><td>68.6</td><td>51.3</td><td>42.2</td><td>65.6</td><td>45.4</td><td></td><td></td></tr><tr><td>LiSANet-S</td><td>258 G</td><td>43 M</td><td>47.2</td><td>68.3</td><td>52.0</td><td>42.2</td><td>65.7</td><td>45.2</td><td></td><td></td></tr><tr><td>HyLiSANet-S</td><td>265 G</td><td>42 M</td><td>47.7</td><td>69.0</td><td>52.5</td><td>42.6</td><td>65.9</td><td>45.9</td><td></td><td></td></tr></tbody></table>

## 5.4 Downstream tasks on other domains

**Video action recognition.** We conduct experiments on Kinetics-400 by adjusting HyLiSANet-S & -B for video representation learning. Depth-wise convolutions in the models are transformed from 2D to 3D, and LiSA takes (T × H × W) tokens for spatio-temporal modeling. We temporarily downsample at the first patch embedding layer, and keep the temporal dimension for the rest of the models. For training, we fine-tune the ImageNet-1K trained weights by inflating 2D convolution kernels and LiSA weights. We follow the training recipe of Uniformer [53] and all the experimental details are in Sec.A.2 of the supplementary material. Table 8 demonstrates the state-of-the-art results on Kinetics-400 including 3D CNNs [64, 65], video transformers [31, 66–69], and hybrid models [16, 53, 70]. For a fair comparison, we compare the models taking the same number of input frames (16 frames). Our small model, HyLiSANet-S, outperforms CNN-based models [64, 65] and ViT models [31, 66–69] in accuracy while consuming much fewer FLOPs. Our base model, HyLiSANet-B, outperforms all the other models including hybrid ViTs [16, 53, 70] in accuracy with comparable FLOPs. The results demonstrate the transferability of our models, and further verify that LiSA is highly beneficial for spatio-temporal modeling.

**Object detection & instance segmentation.** To show the generalization ability of LiSA, we conduct object detection experiments on the

<table><caption>**Table 10: Comparison with other models on ADE-20K.** mIOU (%), FLOPs (G) and the number of parameters (M) are shown. Note that FLOPs are measured at resolution 512×2048.</caption><thead><tr><th>model</th><th>FLOPs</th><th>#params</th><th>mIOU (%)</th></tr></thead><tbody><tr><td>ResNet-50 [58]</td><td>183 G</td><td>29 M</td><td>36.7</td></tr><tr><td>PVT-S [18]</td><td>161 G</td><td>28 M</td><td>39.8</td></tr><tr><td>Twins-S [71]</td><td>144 G</td><td>28 M</td><td>43.2</td></tr><tr><td>Swin-T [6]</td><td>182 G</td><td>32 M</td><td>41.5</td></tr><tr><td>UniFormer-S<sub>h32</sub> [53]</td><td>199 G</td><td>25 M</td><td>46.2</td></tr><tr><td>UniFormer-S [53]</td><td>147 G</td><td>25 M</td><td>46.6</td></tr><tr><td>CSwin-T [36]</td><td>202 G</td><td>26 M</td><td>48.2</td></tr><tr><td>LiSANet-S</td><td>176 G</td><td>27 M</td><td>49.2</td></tr><tr><td>HyLiSANet-S</td><td>184 G</td><td>26 M</td><td>49.3</td></tr></tbody></table>

COCO dataset. We adopt standard Mask R-CNN [74] detection frameworks, which employ ImageNet-1K pre-trained weights for fine-tuning. We use a 1× schedule (12 epochs) and follow the same recipe as in [6]. In Tab. 9, we show the results of object detection and instance segmentation tasks. Our HyLiSANet-S shows the best performances among CNN [58], ViT [6, 61, 72, 73], and Hybrid ViT [19] backbones in AP<sup>b</sup> and AP<sup>m</sup>, while maintaining its efficiency. Since these are high-resolution computer vision tasks (e.g., 800 × 1280), the results demonstrate that LiSA is a proper fit for processing a large number of tokens compared to other attention methods [6, 61, 73].

**Semantic segmentation.** We also evaluate our model on ADE-20K dataset [28]. We adopt the popular Semantic FPN [75] as a basic framework and the model is trained for 80k iterations. The stochastic depth rate is set as 0.15, and we follow the same setting of PVT [18] for a fair comparison. Table 10 summarizes the results on ADE-20K. HyLiSANet-S achieves the best mIOU among different models while requiring fewer FLOPs and the number of parameters, indicating that LiSA is beneficial for processing high-resolutions.

## 5.5 Visualization

In Fig. 4, we visualize both self-attention and LiSA kernels of different layers and heads from isotropic models. As expected, LiSA kernels contain much more diverse patterns compared to self-attention kernels. Self-attention kernels in the early layers often fail to capture relevant context, and those in the latter layers are effective, but they usually capture redundant information. Unlike self-attention, LiSA kernels in the early layers focus on encoding local features. Some of these look similar to
# A. Implementation details

## A.1. Architecture Details

**LiSA.** In addition to the details included in the main paper, we provide pseudo-code of structure-aware attention (Eq. 4 & Eq. 5 in the main paper) and LiSA in Fig. 6 and Fig. 7, respectively. The notation of multi-head is omitted for clarity and simplicity. As shown in the pseudo-code, we effectively reduce the computational complexity with the FFT approximation. In actual implementation, we employ 2D RFFT/IRFFT for images and 3D variant for videos.

**LiSANet.** A detailed overview of our proposed architectures is shown in Tab. 7. LiSANet-I-T is composed of a single stage following the traditional ViT guidelines [1,45]. The number of tokens is constant in this model: $14 \times 14$. Focusing on the blocks, we have an initial patch embedding layer with a stride of 16 pixels and then, 12 LiSA blocks with an embedding size of 192. On the other hand, our hierarchical models follow the guidelines proposed in [27, 30, 39]. Both models (LiSANet-H-S and LiSANet-H-B) are composed of the same four stages with different token sizes and numbers of tokens. In the earlier stages, the token size is larger producing a smaller number of tokens. We adopt the overlapping patch embedding strategy [52] for hierarchical models. The number of LiSA blocks differs in both models, with LiSANet-H-B the larger model employing a larger number of blocks (16 vs. 24 blocks).

## A.2. Experimental Setup

**Image classification.** Our models are trained with AdamW [32] with a weight decay of 0.05 and a learning rate of $0.0005/512$. *batch_size* with a cosine decay scheduler and 20 warm-up epochs. Our isotropic model (LiSANet-I-T) is trained for 150 epochs and hierarchical models are trained for 300 epochs. Following the training recipe proposed in [30], we apply several regularization techniques such as Mixup [58], Cutmix [57], label smoothing [44] and stochastic depth [20]. The stochastic depth strategy is applied only to the hierarchical models with a probability of 0.1 and 0.4 for the LiSANet-H-S and LiSANet-H-B models, respectively. In addition, we also apply several data augmentation techniques like Rand-Augment [9], random erasing [62], and repeated augmentation. Note that all these hyperparameter values and data-augmentation techniques are selected following the training recipes of the previous works [30, 45].

**Object detection.** We adopt standard Mask R-CNN [17] detection frameworks, and ImageNet-1K pre-trained model (LiSANet-H-S) are utilized as backbones. weights for fine-tuning. We use a 1× schedule (12 epochs) with total batch size 16, and follow the same recipe as in [30]. The code is mainly based on mmdetection [4]. For training, the shorter side of the image is resized to 800 pixels while keeping the

```c
# B: batches, N: tokens, C: channels, D: latent_channels
def structure_aware_attn_Eq4(input, e):
    # input shape: [B,N,C], e shape: [2N-1]
    qkv = linear proj(input, channels=3C) # shape: [B,N,3C]
    query,key,value = split(qkv, [C,C,C], dim=-1)
    # query,key,value shape: [B,N,C]
    query = L2norm(query) # shape: [B,N,C]
    key = L2norm(key) # shape: [B,N,C]

    R = Toeplitz(e) # shape: [N,N]
    attn = einsum(query,key, 'BNC,BMC->BNM') # shape: [B,N,N]
    attn_R = attn * R # shape: [B,N,N]

    out = einsum(attn_R,value,'BNM,BMC->BNM') # shape: [B,N,C]
    out = linear proj(out, channels=C) # shape: [B,N,C]
    return out

def structure_aware_attn_Eq5(input, Ea, Eb, Bb):
    # input shape: [B,N,C], Ea,Eb shape: [2N-1,D], Bb shape: [C,D]
    qkv = linear proj(input, channels=3C) # shape: [B,N,3C]
    query,key,value = split(qkv, [C,C,C], dim=-1)
    # query,key,value shape: [B,N,C]
    query = L2norm(query) # shape: [B,N,C]
    key = L2norm(key) # shape: [B,N,C]

    Ra = Toeplitz(Ea) # shape: [N,N,D]
    Rb = Toeplitz(Eb) # shape: [N,N,D]
    K_Ra = einsum(key,Ra,'BMC,NMD->BNCD') # shape: [B,N,C,D]
    Rb_V = einsum(Rb,value,'NMD,BMV->BNVD') # shape: [B,N,C,D]
    Rb_V_Bb = Rb_V + Bb # shape: [B,N,C,D]

    out = einsum(query,K_Ra,Rb_v_Bb,'BNC,BNCD,BNVD->BNV') # shape: [B,N,C]
    out = linear proj(out, channels=C) # shape: [B,N,C]
    return out
```

<caption>Figure 6. **Pseudo-code for structure-aware attention.** We describe the way of learning convolutional inductive biases in structure-aware attention (Eq. 4) and its basic form (Eq. 5) presented in Sec. 4.1 of the main paper.</caption>

longer side no more than 1333 pixels. AdamW [32] with a weight decay of 0.05 is adopted as an optimizer, and the initial learning rate is set as 0.0001. Stochastic depth rate is set as 0.1.

**Video action recognition.** Our video models are trained with AdamW [32] with a weight decay of 0.05 and $0.0002/32$. *batch_size* with a cosine decay scheduler and 5 warm-up epochs. Total epoch is set as 60 epochs, and we apply several regularization techniques following [1, 27, 28]. We adopt the uniform sampling strategy [49] for training and a single crop inference for testing.

**Code.** Our source code is included for reproducibility.

# B. Additional Ablations

**Comparison between LiSANet & (conv+attn) models.** In this ablation study, we provide a new comparison between the state-of-the-art (conv+attn) models [27, 28] and LiSANet with hierarchical architecture. Both models [27, 28] incorporate self-attention with convolution operators in each block to increase expressivity. Since self-attention requires a large amount of memory in higher reso-
<figure><img src="image_5.png" /><figcaption>Fig. 4: Attention kernels of self-attention & LiSA. Attention kernels from different layers and heads are visualized. For each sample, the top row is self-attention, and the bottom is LiSA. Note that the red box in the center of each subfigure is the query pixel.</figcaption></figure>

Sobel or Laplacian filters, which are beneficial for learning local structural information. Considering that modern hybrid models [2, 19, 33, 37], which replace self-attention with convolution in early layers obtain an extra accuracy gain, the behavior of LiSA kernels in early layers seems reasonable. Meanwhile, LiSA kernels in the latter layers concentrate on the context relevant to the target object like self-attention does. LiSA, however, generates more diverse shapes of kernels than self-attention, which implies that they aggregate the relevant context and further consider structural patterns inside the context at the aggregation. Therefore, this visualization demonstrates that our structure-aware attention kernel can be more expressive and flexible compared to the self-attention kernel.

## 6 Conclusion

In this paper, we have presented LiSA, a novel expressive, yet efficient, attention operator that learns rich structural patterns with log-linear complexity. Our comprehensive analyses have shown that the ViTs based on LiSA, LiSANets, outperform their counterparts in accuracy and computational complexity. LiSANet & HyLiSANet have achieved competitive performance on various kinds

of visual understanding tasks such as image classification, video classification, object detection, and semantic segmentation. While LiSA is effective yet efficient for understanding visual concepts, it still leaves room for improvement in several aspects. First, LiSA encodes structural patterns as a fixed size of the vector, which is set as a parameter *D*, but we can further investigate a method to dynamically change the size of structural patterns depending on the visual context. Second, although LiSA is much more efficient than the other attention methods due to the log-linear complexity, it is still heavy to construct multiple layers for processing high resolutions. It would be interesting to examine the effect of LiSA with the local or sparse attention techniques. We believe that LiSA can be a guideline for designing a better basic brick for visual understanding, and we further expect our structure-aware attention could be applied for cross-attention mechanisms, which are widely used for handling multiple modalities such as image-text or video-text.

## Acknowledgments

This work has been supported in part by the ANR grant AVENUE (ANR-18-CE23-0011), the Junta de Andalucía of Spain (P18-FR-3130 and P20_00430, including European Union funds) and the Ministry of Education of Spain (PID2019-105396RB-I00). We also thank the EuroHPC JU for the GPU computing hours.

## References

[1] Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al.: An image is worth 16x16 words: Transformers for image recognition at scale. *Proc. International Conference on Learning Representations (ICLR)* (2020)

[2] Li, K., Wang, Y., Gao, P., Song, G., Liu, Y., Li, H., Qiao, Y.: Uniformer: Unified transformer for efficient spatiotemporal representation learning. *Proc. International Conference on Learning Representations (ICLR)* (2022)

[3] Yuan, L., Chen, Y., Wang, T., Yu, W., Shi, Y., Jiang, Z.-H., Tay, F.E., Feng, J., Yan,
<table><caption>Table 7. **Details of LiSANet variants.** Patch Embed↓n denotes a patch embedding layer that downsamples features with a stride n.</caption><thead><tr><th></th><th>Output Size</th><th>LiSANet-I-T</th><th>LiSANet-H-S</th><th>LiSANet-H-B</th></tr></thead><tbody><tr><td>Stage1</td><td><sup>H</sup>&frasl;<sub>4</sub> &times; <sup>W</sup>&frasl;<sub>4</sub></td><td>-</td><td>Overlap Patch Embed↓4<br>LiSA Block (64) &times; 1</td><td>Overlap Patch Embed↓4<br>LiSA Block (96) &times; 2</td></tr><tr><td>Stage2</td><td><sup>H</sup>&frasl;<sub>8</sub> &times; <sup>W</sup>&frasl;<sub>8</sub></td><td>-</td><td>Overlap Patch Embed↓2<br>LiSA Block (128) &times; 2</td><td>Overlap Patch Embed↓2<br>LiSA Block (192) &times; 3</td></tr><tr><td>Stage3</td><td><sup>H</sup>&frasl;<sub>16</sub> &times; <sup>W</sup>&frasl;<sub>16</sub></td><td>Patch Embed↓16<br>LiSA Block (192) &times; 12</td><td>Overlap Patch Embed↓2<br>LiSA Block (256) &times; 11</td><td>Overlap Patch Embed↓2<br>LiSA Block (384) &times; 16</td></tr><tr><td>Stage4</td><td><sup>H</sup>&frasl;<sub>32</sub> &times; <sup>W</sup>&frasl;<sub>32</sub></td><td>-</td><td>Overlap Patch Embed↓2<br>LiSA Block (512) &times; 2</td><td>Overlap Patch Embed↓2<br>LiSA Block (768) &times; 3</td></tr><tr><td>Classifier</td><td></td><td></td><td>Global Average Pooling, Linear</td><td></td></tr></tbody></table>

```python
# B: batches, N: tokens, C: channels, D: latent bidirectional
# input shape: [B,N,C], Wa shape: [N,C,D], Wb shape: [N,D],
# Ba,Bb shape: [C,D]
qkv = linearproj(input, channels=3C) # shape: [B,N,3C]
query,key,value = split(qkv, [C,C,C], dim=-1)
# query,key,value shape: [B,N,C]
query = L2norm(query) # shape: [B,N,C]
key = L2norm(key) # shape: [B,N,C]

K_ftt = rfft(key, dim=1) # shape: [B,N//2+1,C]
Wa_ftt = rfft(Wa, dim=0) # shape: [N//2+1,C,D]
K_Wa = einsum(K_ftt, Wa_ftt, 'BMK,MKD->BMKD') # shape:
    [B,N//2+1,C,D]
K_Wa = irfft(K_Wa, dim=1) # shape: [B,N,C,D]
K_Wa_Ba = K_Wa + Ba # shape: [B,N,C,D]

V_ftt = rfft(value, dim=1) # shape: [B,N//2+1,C]
Wb_ftt = rfft(Wb, dim=0) # shape: [N//2+1,D]
V_Wb = einsum(V_ftt, Wb_ftt, 'BMV,MD->BMVD') # shape:
    [B,N//2+1,C,D]
V_Wb = irfft(V_Wb, dim=1) # shape: [B,N,C,D]
V_Wb_Bb = V_Wb + Bb # shape: [B,N,C,D]

out = einsum(query, K_Wa_Ba, V_Wb_Bb, 'BNK,BNKD,BNVD->BNV')
    # shape: [B,N,C]
out = linearproj(out, channels=C) # shape: [B,N,C]
return out
```

<caption>Figure 7. **Pseudo-code for LiSA.** We describe the final form of LiSA described in Sec. 4.3 of the main paper.</caption>

lutions, Uniformer [27] only uses depthwise convolutions in earlier layers and MViTv2 [28] downsamples features with convolutions before applying attention. For a fair comparison, we use the same configuration (shown in Tab 8a) for all the models. Tab. 8b summarizes the results on ImageNet, which show that the accuracy of LiSANet-H-T is higher than the state-of-the-art (conv+attn) models with comparable FLOPs and params. This is impressive since we do not apply any modification for our block while other models rely on elaborated architecture designs and handcrafted schemes.

<table><thead><tr><th>Model</th><th>#Blocks</th><th>#Channels (#heads)</th></tr></thead><tbody><tr><td>MViTv2-H-T</td><td>[1, 2, 5, 2]</td><td>[64 (4), 128 (8), 256 (16), 512 (32)]</td></tr><tr><td>Uniformer-H-T</td><td>[1, 2, 5, 2]</td><td>[64 (4), 128 (8), 256 (16), 512 (32)]</td></tr><tr><td>LiSANet-H-T</td><td>[1, 2, 5, 2]</td><td>[64 (4), 128 (8), 256 (16), 512 (32)]</td></tr></tbody></table><p>(a) Model configuration of hierarchical-tiny models.</p><table><thead><tr><th>model</th><th>FLOPs</th><th>#params</th><th>top-1</th></tr></thead><tbody><tr><td>MViTv2-H-T</td><td>2.1 G</td><td>12.0 M</td><td>79.3</td></tr><tr><td>Uniformer-H-T</td><td>1.7 G</td><td>11.9 M</td><td>79.7</td></tr><tr><td>LiSANet-H-T (D=8)</td><td>1.8 G</td><td>12.7 M</td><td>80.4</td></tr><tr><td>LiSANet-H-T (D=8) w/ conv</td><td>1.8 G</td><td>12.7 M</td><td>80.9</td></tr></tbody></table>

(b) Performance comparison among hierarchical-tiny models. Note that D is the number of latent channels of LiSA. Top-1, accuracy (%), FLOPs (G), and the number of parameters (M) are shown.

<caption>Table 8. Comparison between (conv+attn) models & ours.</caption>

For example, LiSANet-H-T obtains an additional gain by using the depthwise convolution scheme of [27]. These results show that the models based on LiSA outperform the (conv+attn) models with hierarchical architecture. We use the official source code of Uniformer [27] and MViTv2 [28] for implementing their blocks. For Uniformer, we only apply depthwise convolutions for the early 2 stages, following their paper. For MViTv2, we downsample features with stride 2 for the early 2 stages, and do not downsample for the other stages.

**Fine-tuning on higher resolutions.** We have verified that fine-tuning LiSANet on higher resolutions can boost image recognition accuracy. Tab. 9 summarizes the results of LiSANet-I-T on ImageNet. LiSANet obtains a 2.5% gain when we use 384 × 384 resolution. While MLP-mixer models are hard to adapt to higher resolutions since they process a fixed number of tokens, LiSANet can be easily
S.: Tokens-to-token vit: Training vision transformers from scratch on imagenet. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 558-567 (2021)

[4] Touvron, H., Cord, M., Douze, M., Massa, F., Sablayrolles, A., Jégou, H.: Training data-efficient image transformers & distillation through attention. In: Proc. International Conference on Machine Learning (ICML), pp. 10347-10357 (2021). PMLR

[5] Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., Liu, P.J.: Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.10683 (2019)

[6] Liu, Z., Lin, Y., Cao, Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., Guo, B.: Swin transformer: Hierarchical vision transformer using shifted windows. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 10012-10022 (2021)

[7] Bello, I.: Lambdanetworks: Modeling long-range interactions without attention. In: Proc. International Conference on Learning Representations (ICLR) (2020)

[8] Zhao, H., Jia, J., Koltun, V.: Exploring self-attention for image recognition. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10076-10085 (2020)

[9] Kim, M., Kwon, H., Wang, C., Kwak, S., Cho, M.: Relational self-attention: What's missing in attention for video understanding. Proc. Neural Information Processing Systems (NeurIPS) 34, 8046-8059 (2021)

[10] Wang, S., Li, B., Khabsa, M., Fang, H., Ma, H.: Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768 (2020)

[11] Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L., et al.: Rethinking attention with performers. In: Proc. International Conference on Learning Representations (ICLR) (2021)

[12] Qin, Z., Sun, W., Deng, H., Li, D., Wei, Y., Lv, B., Yan, J., Kong, L., Zhong, Y.: cosformer: Rethinking softmax in attention. arXiv preprint arXiv:2202.08791 (2022)

[13] Liutkus, A., Cifka, O., Wu, S.-L., Simsekli, U., Yang, Y.-H., Richard, G.: Relative positional encoding for transformers with linear complexity. In: Proc. International Conference on Machine Learning (ICML), pp. 7067-7079 (2021). PMLR

[14] Chen, P.: Permuteformer: Efficient relative position encoding for long sequences. In: Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 10606-10618 (2021)

[15] Luo, S., Li, S., Cai, T., He, D., Peng, D., Zheng, S., Ke, G., Wang, L., Liu, T.-Y.: Stable, fast and accurate: Kernelized attention with relative positional encoding. Proc. Neural Information Processing Systems (NeurIPS) 34, 22795-22807 (2021)

[16] Li, Y., Wu, C.-Y., Fan, H., Mangalam, K., Xiong, B., Malik, J., Feichtenhofer, C.: Mvitv2: Improved multiscale vision transformers for classification and detection. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4804-4814 (2022)

[17] Wu, H., Xiao, B., Codella, N., Liu, M., Dai, X., Yuan, L., Zhang, L.: Cvt: Introducing convolutions to vision transformers. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 22-31 (2021)

[18] Wang, W., Xie, E., Li, X., Fan, D.-P., Song, K., Liang, D., Lu, T., Luo, P., Shao, L.: Pvt v2: Improved baselines with pyramid vision transformer. Computational Visual Media 8(3), 415-424 (2022)

[19] Si, C., Yu, W., Zhou, P., Zhou, Y., Wang, X., Yan, S.: Inception transformer. Proc. Neural Information Processing Systems (NeurIPS) 35, 23495-23509 (2022)
<table><caption>Table 9. Fine-tuning to higher resolutions on ImageNet. Image size, Top-1, accuracy (%), FLOPs (G) and the number of parameters (M) are shown.</caption><thead><tr><th>model</th><th>Image size</th><th>FLOPs</th><th>#params</th><th>top-1</th></tr></thead><tbody><tr><td>LiSANet-I-T</td><td>224 × 224</td><td>1.21 G</td><td>6.36 M</td><td>74.9</td></tr><tr><td>LiSANet-I-T</td><td>384 × 384</td><td>3.62 G</td><td>7.82 M</td><td>77.4</td></tr></tbody></table>

interpolated to higher resolutions due to the property of Discrete Fourier transform, where each element of the time (i.e. spatial) domain is a sampling of a continuous spectrum in the frequency domain. Since the circular embeddings $W^a$, $W^b$ can be considered as samplings of continuous spectrums, changing the resolution is equal to changing the sampling interval of spectrums [39]. Thus, LiSA can be adapted to higher resolutions by simple interpolation.

## C. Visualization

In Fig. 8, we additionally visualize both self-attention and LiSA kernels of different layers and heads from isotropic models.
[20] Tu, Z., Talebi, H., Zhang, H., Yang, F., Milanfar, P., Bovik, A., Li, Y.: Maxvit: Multi-axis vision transformer. In: *Proc. European Conference on Computer Vision (ECCV)*, pp. 459–479 (2022). Springer

[21] Shechtman, E., Irani, M.: Matching local self-similarities across images and videos. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 1–8 (2007). IEEE

[22] Wang, H., Tran, D., Torresani, L., Feiszli, M.: Video modeling with correlation networks. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 352–361 (2020)

[23] Kwon, H., Kim, M., Kwak, S., Cho, M.: Learning self-similarity in space and time as generalized motion for video action recognition. In: *Proc. IEEE International Conference on Computer Vision (ICCV)*, pp. 13065–13075 (2021)

[24] Sun, D., Yang, X., Liu, M.-Y., Kautz, J.: Pwc-net: Cnns for optical flow using pyramid, warping, and cost volume. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 8934–8943 (2018)

[25] Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., Fei-Fei, L.: Imagenet: A large-scale hierarchical image database. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 248–255 (2009). IEEE

[26] Kay, W., Carreira, J., Simonyan, K., Zhang, B., Hillier, C., Vijayanarasimhan, S., Viola, F., Green, T., Back, T., Natsev, P., et al.: The kinetics human action video dataset. *arXiv preprint arXiv:1705.06950* (2017)

[27] Lin, T.-Y., Maire, M., Belongie, S., Hays, J., Perona, P., Ramanan, D., Dollár, P., Zitnick, C.L.: Microsoft coco: Common objects in context. In: *Proc. European Conference on Computer Vision (ECCV)*, pp. 740–755 (2014). Springer

[28] Zhou, B., Zhao, H., Puig, X., Fidler, S., Barriuso, A., Torralba, A.: Scene parsing through ade20k dataset. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 633–641 (2017)

[29] Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A., Zagoruyko, S.: End-to-end object detection with transformers. In: *Proc. European Conference on Computer Vision (ECCV)*, pp. 213–229 (2020). Springer

[30] Strudel, R., Garcia, R., Laptev, I., Schmid, C.: Segmenter: Transformer for semantic segmentation. In: *Proc. IEEE International Conference on Computer Vision (ICCV)*, pp. 7262–7272 (2021)

[31] Arnab, A., Dehghani, M., Heigold, G., Sun, C., Lučić, M., Schmid, C.: Vivit: A video vision transformer. In: *Proc. IEEE International Conference on Computer Vision (ICCV)*, pp. 6836–6846 (2021)

[32] Vaswani, A., Ramachandran, P., Srinivas, A., Parmar, N., Hechtman, B., Shlens, J.: Scaling local self-attention for parameter efficient visual backbones. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 12894–12904 (2021)

[33] Xiao, T., Singh, M., Mintun, E., Darrell, T., Dollár, P., Girshick, R.: Early convolutions help transformers see better. *Proc. Neural Information Processing Systems (NeurIPS)* 34, 30392–30400 (2021)

[34] Han, K., Xiao, A., Wu, E., Guo, J., Xu, C., Wang, Y.: Transformer in transformer. *Proc. Neural Information Processing Systems (NeurIPS)* 34, 15908–15919 (2021)

[35] Zhang, Z., Zhang, H., Zhao, L., Chen, T., Arik, S.Ö., Pfister, T.: Nested hierarchical transformer: Towards accurate, data-efficient and interpretable visual understanding. In: *Proc. AAAI Conference on Artificial Intelligence (AAAI)*, vol. 36, pp. 3417–3425 (2022)

[36] Dong, X., Bao, J., Chen, D., Zhang, W., Yu, N., Yuan, L., Chen, D., Guo, B.: Cswin transformer: A general vision transformer backbone
<figure><img src="image_6.png" /><figcaption>Figure 8. Attention kernels of self-attention & LiSA. Attention kernels from different layers and heads are visualized. For each sample, the top row is self-attention and the bottom is LiSA. Note that the red box in the center of each subfigure is the query pixel.</figcaption></figure>
with cross-shaped windows. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 12124-12134 (2022)

[37] Dai, Z., Liu, H., Le, Q.V., Tan, M.: Coatznet: Marrying convolution and attention for all data sizes. Proc. Neural Information Processing Systems (NeurIPS) 34, 3965-3977 (2021)

[38] Jia, X., De Brabandere, B., Tuytelaars, T., Gool, L.V.: Dynamic filter networks. Proc. Neural Information Processing Systems (NeurIPS) 29 (2016)

[39] Li, D., Hu, J., Wang, C., Li, X., She, Q., Zhu, L., Zhang, T., Chen, Q.: Involution: Inverting the inherence of convolution for visual recognition. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 12321-12330 (2021)

[40] Chen, Y., Dai, X., Liu, M., Chen, D., Yuan, L., Liu, Z.: Dynamic convolution: Attention over convolution kernels. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11030-11039 (2020)

[41] Ma, N., Zhang, X., Huang, J., Sun, J.: Weight-net: Revisiting the design space of weight networks. In: Proc. European Conference on Computer Vision (ECCV), pp. 776-792 (2020). Springer

[42] Shen, Z., Zhang, M., Zhao, H., Yi, S., Li, H.: Efficient attention: Attention with linear complexities. In: Proc. Winter Conference on Applications of Computer Vision (WACV), pp. 3531-3539 (2021)

[43] Katharopoulos, A., Vyas, A., Pappas, N., Fleuret, F.: Transformers are rnns: Fast autoregressive transformers with linear attention. In: Proc. International Conference on Machine Learning (ICML), pp. 5156-5165 (2020). PMLR

[44] Rao, Y., Zhao, W., Zhu, Z., Lu, J., Zhou, J.: Global filter networks for image classification. Proc. Neural Information Processing Systems (NeurIPS) 34, 980-993 (2021)

[45] Lee-Thorp, J., Ainslie, J., Eckstein, I., Ontanon, S.: Fnet: Mixing tokens with fourier transforms. arXiv preprint arXiv:2105.03824 (2021)

[46] d'Ascoli, S., Touvron, H., Leavitt, M.L., Morcos, A.S., Biroli, G., Sagun, L.: Convit: Improving vision transformers with soft convolutional inductive biases. In: Proc. International Conference on Machine Learning (ICML), pp. 2286-2296 (2021). PMLR

[47] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. Proc. Neural Information Processing Systems (NeurIPS) 30 (2017)

[48] Ramachandran, P., Parmar, N., Vaswani, A., Bello, I., Levskaya, A., Shlens, J.: Stand-alone self-attention in vision models. Proc. Neural Information Processing Systems (NeurIPS) 32 (2019)

[49] Strang, G.: A proposal for toeplitz matrix calculations. Applied Mathematics 74(2), 171-176 (1986)

[50] Fu, D.Y., Dao, T., Saab, K.K., Thomas, A.W., Rudra, A., Re, C.: Hungry hungry hippos: Towards language modeling with state space models. In: Proc. International Conference on Learning Representations (ICLR) (2022)

[51] Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A.C., Fei-Fei, L.: ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV) 115(3), 211-252 (2015) https://doi.org/10.1007/s11263-015-0816-y

[52] Lin, W., Wu, Z., Chen, J., Huang, J., Jin, L.: Scale-aware modulation meet transformer. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 6015-6026 (2023)

[53] Li, K., Wang, Y., Zhang, J., Gao, P., Song, G., Liu, Y., Li, H., Qiao, Y.: Uniformer: Unifying convolution and self-attention for visual recognition. IEEE Transactions on Pattern
*Analysis and Machine Intelligence (TPAMI)* **45**(10), 12581-12600 (2023)

[54] Wang, W., Dai, J., Chen, Z., Huang, Z., Li, Z., Zhu, X., Hu, X., Lu, T., Lu, L., Li, H., et al.: Internimage: Exploring large-scale vision foundation models with deformable convolutions. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 14408-14419 (2023)

[55] Pan, X., Ye, T., Xia, Z., Song, S., Huang, G.: Slide-transformer: Hierarchical vision transformer with local self-attention. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 2082-2091 (2023)

[56] Chu, X., Tian, Z., Zhang, B., Wang, X., Shen, C.: Conditional positional encodings for vision transformers. In: *Proc. International Conference on Learning Representations (ICLR)* (2023)

[57] Howard, A.G., Zhu, M., Chen, B., Kalenichenko, D., Wang, W., Weyand, T., Andreetto, M., Adam, H.: Mobilenets: Efficient convolutional neural networks for mobile vision applications. *arXiv preprint arXiv:1704.04861* (2017)

[58] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 770-778 (2016)

[59] Radosavovic, I., Kosaraju, R.P., Girshick, R., He, K., Dollár, P.: Designing network design spaces. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 10428-10436 (2020)

[60] Liu, Z., Mao, H., Wu, C.-Y., Feichtenhofer, C., Darrell, T., Xie, S.: A convnet for the 2020s. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)*, pp. 11976-11986 (2022)

[61] Wang, W., Xie, E., Li, X., Fan, D.-P., Song, K., Liang, D., Lu, T., Luo, P., Shao, L.: Pyramidal vision transformer: A versatile backbone for dense prediction without convolutions. In: *Proc. IEEE International Conference on Computer Vision (ICCV)*, pp. 568-578 (2021)

[62] Guo, M.-H., Lu, C.-Z., Liu, Z.-N., Cheng, M.-M., Hu, S.-M.: Visual attention network. *arXiv preprint arXiv:2202.09741* (2022)

[63] Vasu, P.K.A., Gabriel, J., Zhu, J., Tuzel, O., Ranjan, A.: Fastvit: A fast hybrid vision transformer using structural reparameterization. In: *Proc. IEEE International Conference on Computer Vision (ICCV)*, pp. 5785-5795 (2023)

[64] Feichtenhofer, C.: X3d: Expanding architectures for efficient video recognition. In: *Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)* (2020)

[65] Feichtenhofer, C., Fan, H., Malik, J., He, K.: Slowfast networks for video recognition. In: *Proc. IEEE International Conference on Computer Vision (ICCV)* (2019)

[66] Bulat, A., Perez Rua, J.M., Sudhakaran, S., Martinez, B., Tzimiropoulos, G.: Space-time mixing attention for video transformer. *Proc. Neural Information Processing Systems (NeurIPS) 34*, 19594-19607 (2021)

[67] Patrick, M., Campbell, D., Asano, Y., Misra, I., Metze, F., Feichtenhofer, C., Vedaldi, A., Henriques, J.F.: Keeping your eye on the ball: Trajectory attention in video transformers. *Proc. Neural Information Processing Systems (NeurIPS) 34*, 12493-12506 (2021)

[68] Liu, Z., Ning, J., Cao, Y., Wei, Y., Zhang, Z., Lin, S., Hu, H.: Video swin transformer. In: *Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition*, pp. 3202-3211 (2022)

[69] Bertasius, G., Wang, H., Torresani, L.: Is space-time attention all you need for video understanding? In: *Proc. International Conference on Machine Learning (ICML)*, vol. 2, p. 4 (2021)

[70] Fan, H., Xiong, B., Mangalam, K., Li, Y.,
Yan, Z., Malik, J., Feichtenhofer, C.: Multiscale vision transformers. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 6824–6835 (2021)

[71] Chu, X., Tian, Z., Wang, Y., Zhang, B., Ren, H., Wei, X., Xia, H., Shen, C.: Revisiting the design of spatial attention in vision transformers. Proc. Neural Information Processing Systems (NeurIPS) 34, 9355–9366 (2021)

[72] Zhang, P., Dai, X., Yang, J., Xiao, B., Yuan, L., Zhang, L., Gao, J.: Multi-scale vision longformer: A new vision transformer for high-resolution image encoding. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 2998–3008 (2021)

[73] Yang, J., Li, C., Zhang, P., Dai, X., Xiao, B., Yuan, L., Gao, J.: Focal attention for long-range interactions in vision transformers. Proc. Neural Information Processing Systems (NeurIPS) 34, 30008–30022 (2021)

[74] He, K., Gkioxari, G., Dollár, P., Girshick, R.: Mask r-cnn. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 2961–2969 (2017)

[75] Kirillov, A., Girshick, R., He, K., Dollár, P.: Panoptic feature pyramid networks. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 6399–6408 (2019)

[76] Loshchilov, I., Hutter, F.: Decoupled weight decay regularization. In: Proc. International Conference on Learning Representations (ICLR) (2018)

[77] Zhang, H., Cisse, M., Dauphin, Y.N., Lopez-Paz, D.: mixup: Beyond empirical risk minimization. In: Proc. International Conference on Learning Representations (ICLR) (2018)

[78] Yun, S., Han, D., Oh, S.J., Chun, S., Choe, J., Yoo, Y.: Cutmix: Regularization strategy to train strong classifiers with localizable features. In: Proc. IEEE International Conference on Computer Vision (ICCV), pp. 6023–6032 (2019)

[79] Szegedy, C., Vanhoucke, V., Ioffe, S., Shlens, J., Wojna, Z.: Rethinking the inception architecture for computer vision. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2818–2826 (2016)
[80] Huang, G., Sun, Y., Liu, Z., Sedra, D., Weinberger, K.Q.: Deep networks with stochastic depth. In: Proc. European Conference on Computer Vision (ECCV), pp. 646–661 (2016). Springer
[81] Cubuk, E.D., Zoph, B., Shlens, J., Le, Q.: Randoaugment: Practical automated data augmentation with a reduced search space. Proc. Neural Information Processing Systems (NeurIPS) 33, 18613–18624 (2020)
[82] Zhong, Z., Zheng, L., Kang, G., Li, S., Yang, Y.: Random erasing data augmentation. In: Proc. AAAI Conference on Artificial Intelligence (AAAI), vol. 34, pp. 13001–13008 (2020)
[83] Wang, X., Girshick, R., Gupta, A., He, K.: Non-local neural networks. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7794–7803 (2018)
[84] Wang, L., Xiong, Y., Wang, Z., Qiao, Y., Lin, D., Tang, X., Van Gool, L.: Temporal segment networks: Towards good practices for deep action recognition. In: Proc. European Conference on Computer Vision (ECCV), pp. 20–36 (2016). Springer
[85] Fu, D.Y., Kumbong, H., Nguyen, E., Ré, C.: Flashftconv: Efficient convolutions for long sequences with tensor cores. arXiv preprint arXiv:2311.05908 (2023)
# Supplementary Material of "Lightweight Structure-Aware Attention for Visual Understanding"

## A Implementation details

### A.1 Architecture Details

**LiSA.** In addition to the details included in the main paper, we provide pseudo-code of structure-aware attention (Eq. 4 & Eq. 5 in the main paper) and LiSA in Fig. 6 and Fig. 7, respectively. The notation of multi-head is omitted for clarity and simplicity. As shown in the pseudo-code, we effectively reduce the computational complexity with the FFT approximation.

**LiSANet.** A detailed overview of our proposed architectures is shown in Tab. 11. LiSANet-I is composed of a single stage following the traditional ViT guidelines [4, 31]. The number of tokens is constant in this model: 14 × 14. Focusing on the blocks, we have an initial patch embedding layer with a stride of 16 pixels and then, 12 LiSA blocks with an embedding size of 192. On the other hand, our hierarchical ViTs follow the guidelines proposed in [6, 36, 44]. Both models (LiSANet-S and LiSANet-B) are composed of the same four stages with different token sizes and numbers of tokens. For hybrid models (HyLiSANet-S and HyLiSANet-B), we follow the strategies proposed in [2, 37]. We adopt convolutional blocks for the early two stages and employ LiSA blocks for the other stages. Each convolutional block consists of two pointwise convolutions and one depthwise convolution as illustrated in Fig. 5. We adopt the overlapping patch embedding strategy [18] for hierarchical models. MLP ratios are set to 4 for the early two stages and 3 for the last two stages. We adopt convolutional position embedding [56] and convolutional MLP [18] for our hierarchical models.

### A.2 Experimental Setup

**Image classification (ImageNet-1K).** Our models are trained with AdamW [76] with a weight decay of 0.05 and a learning rate of $0.0005 \cdot \text{batch\_size}$ with a cosine decay scheduler and 20 warm-up epochs. Our isotropic model (LiSANet-I) is trained for 150 epochs and hierarchical models are trained for 300 epochs. Following the training recipe proposed in [6], we apply several regularization techniques such as Mixup [77], Cutmix [78], label smoothing [79] and stochastic depth [80]. The stochastic depth strategy is applied only for the hierarchical models with a probability of 0.1 and 0.4 for the LiSANet-S and LiSANet-B models, respectively. In addition, we also apply several data augmentation techniques like Rand-Augment [81], random erasing [82], and repeated augmentation. Note that all these hyperparameter values and data-augmentation techniques are selected following the training recipes of the previous works [4, 6].

**Image classification (ImageNet-21K).** For ImageNet-21K pre-training, models are trained with AdamW [76] with a weight decay of 0.05 and a base learning rate of 4e-3 & batch size 4096 with a cosine decay scheduler and 5 warm-up epochs. The total number of epochs are set to 90, and the stochastic depth rate is set to 0.1 & 0.2 for HyLiSANet-S & -B models, respectively. For the other details, we follow the training setup proposed in [60]. For ImageNet-1K fine-tuning, models are trained with AdamW [76] with a weight decay of 1e-8 and a base learning rate of 5e-5 & batch size 512 with a cosine decay scheduler. The total number of epochs are set to 30, and the stochastic depth rate is set to 0.1 & 0.2 for HyLiSANet-S & -B models, respectively. For the other details, we follow the training setup proposed in [60].

**Video action recognition (Kinetics-400).** ImageNet-1K pre-trained models (HyLiSANet-S, HyLiSANet-B) are adapted to video models and utilized as backbones, and the models are trained with AdamW [76] using a weight decay of 0.05 and $0.0001/32 \cdot \text{batch\_size}$ with a cosine decay scheduler and 10 warm-up epochs. The total number of epochs are set to 110, and the stochastic depth rate is set to 0.15 & 0.3 for HyLiSANet-S & -B models, respectively. For the other regularization or data-augmentation details, we follow the training setup proposed in [53]. Number of input frames is set to 16, and we adopt the dense sampling strategy [83] for training and multi-clip (16×1×4) inference for testing. All scores are averaged for the final result.
<figure><img src="image_6.png" /><figcaption>**Fig. 5: Convolutional block in hybrid models.** 'PW conv' denotes a pointwise convolution and 'DW conv' denotes a depthwise convolution.</figcaption></figure>

<table><caption>**Table 11: Details of LiSANet variants.** Patch Embed↓n denotes a patch embedding layer that downsamples features with a stride n.</caption><thead><tr><th></th><th>Output Size</th><th>LiSANet-I</th><th>LiSANet-S</th><th>LiSANet-B</th><th>HyLiSANet-S</th><th>HyLiSANet-B</th></tr></thead><tbody><tr><td>Stage1</td><td><sup>H</sup>&frasl;<sub>4</sub> &times; <sup>W</sup>&frasl;<sub>4</sub></td><td>-</td><td>Overlap Patch Embed↓4<br>LiSA Block (64) &times; 2</td><td>Overlap Patch Embed↓4<br>LiSA Block (96) &times; 4</td><td>Overlap Patch Embed↓4<br>Conv Block (64) &times; 3</td><td>Overlap Patch Embed↓4<br>Conv Block (96) &times; 3</td></tr><tr><td>Stage2</td><td><sup>H</sup>&frasl;<sub>8</sub> &times; <sup>W</sup>&frasl;<sub>8</sub></td><td>-</td><td>Overlap Patch Embed↓2<br>LiSA Block (128) &times; 4</td><td>Overlap Patch Embed↓2<br>LiSA Block (192) &times; 8</td><td>Overlap Patch Embed↓2<br>Conv Block (128) &times; 6</td><td>Overlap Patch Embed↓2<br>Conv Block (192) &times; 12</td></tr><tr><td>Stage3</td><td><sup>H</sup>&frasl;<sub>16</sub> &times; <sup>W</sup>&frasl;<sub>16</sub><br>LiSA Block (192) &times; 12</td><td>Patch Embed↓16</td><td>Overlap Patch Embed↓2<br>LiSA Block (320) &times; 12</td><td>Overlap Patch Embed↓2<br>LiSA Block (384) &times; 18</td><td>Overlap Patch Embed↓2<br>LiSA Block (320) &times; 12</td><td>Overlap Patch Embed↓2<br>LiSA Block (384) &times; 18</td></tr><tr><td>Stage4</td><td><sup>H</sup>&frasl;<sub>32</sub> &times; <sup>W</sup>&frasl;<sub>32</sub></td><td>-</td><td>Overlap Patch Embed↓2<br>LiSA Block (384) &times; 4</td><td>Overlap Patch Embed↓2<br>LiSA Block (576) &times; 3</td><td>Overlap Patch Embed↓2<br>LiSA Block (384) &times; 4</td><td>Overlap Patch Embed↓2<br>LiSA Block (576) &times; 3</td></tr><tr><td>Classifier</td><td></td><td></td><td colspan="4">Global Average Pooling, Linear</td></tr></tbody></table>

**Video action recognition (Something-V2).** Video models are trained with AdamW [76] using a weight decay of 0.05 and 0.0002 / 32 · batch_size with a cosine decay scheduler and 5 warm-up epochs. The total number of epochs is set to 60, and we apply several regularization or data-augmentation techniques following [2, 16, 31]. We adopt the uniform sampling strategy [84] for training and a single crop inference for testing.

**Object detection (COCO).** We adopt standard Mask R-CNN [74] detection frameworks, and ImageNet-1K pre-trained models (LiSANet-S, HyLiSANet-S) are utilized as backbones. We use a 1× schedule (12 epochs) with total batch size 16, and follow the same recipe as in [6]. For training, the shorter side of the image is resized to 800 pixels while keeping the longer side no more than 1333 pixels. AdamW [76] with a weight decay of 0.05 is adopted as an optimizer, and the initial learning rate is set to 0.0001. The stochastic depth rate is set to 0.1 and we follow the other details proposed in [6].

**Semantic segmentation (ADE-20K).** We adopt Semantic FPN [75] as a basic framework. ImageNet-1K pre-trained models (LiSANet-S, HyLiSANet-S) are utilized as backbones. The framework is trained for 80k iterations with a cosine decay scheduler. The stochastic depth rate is set to 0.15 and we follow the other details proposed in [18] for a fair comparison.

## B Additional Analyses

**Latency.** We demonstrate both inference and training latency in Table 12. As shown in the table, the training latency follows the tendency of the inference ones. LiSA becomes much faster than self-attention as the number of tokens increases due to its log-linear complexity. We observed that training and inference latency values vary according to the FLOP size except for 7 × 7, where LiSA is slightly slower due to a
```python
# B: batches, N: tokens, C: channels, D: latent_channels
def structure_aware_attn_Eq4(input, e):
    # input shape: [B,N,C], e shape: [2N-1]
    qkv = linear proj(input, channels=3C) # shape: [B,N,3C]
    query,key,value = split(qkv, [C,C,C], dim=-1)
    # query,key,value shape: [B,N,C]
    query = L2norm(query) # shape: [B,N,C]
    key = L2norm(key) # shape: [B,N,C]

    R = Toeplitz(e) # shape: [N,N]
    attn = einsum(query,key, 'BNC,BMC->BNM') # shape: [B,N,N]
    attn_R = attn * R # shape: [B,N,N]

    out = einsum(attn_R,value,'BNM,BMC->BNC') # shape: [B,N,C]
    out = linear proj2(out, channels=C) # shape: [B,N,C]
    return out

def structure_aware_attn_Eq5(input, Ea, Eb, B):
    # input shape: [B,N,C], Ea,Eb shape: [2N-1,D], Bb shape: [C,D]
    qkv = linear proj(input, channels=3C) # shape: [B,N,3C]
    query,key,value = split(qkv, [C,C,C], dim=-1)
    # query,key,value shape: [B,N,C]
    query = L2norm(query) # shape: [B,N,C]
    key = L2norm(key) # shape: [B,N,C]

    Ra = Toeplitz(Ea) # shape: [N,N,D]
    Rb = Toeplitz(Eb) # shape: [N,N,D]
    K_Ra = einsum(key,Ra,'BMC,NMD->BNCD') # shape: [B,N,C,D]
    Rb_V = einsum(Rb,value, 'NMD,BMV->BNVD') # shape: [B,N,C,D]
    Rb_V_B = Rb_V + B # shape: [B,N,C,D]

    out = einsum(query,K_Ra,Rb_v_B,'BNC,BNCD,BNVD->BNV') # shape: [B,N,C]
    out = linear proj2(out, channels=C) # shape: [B,N,C]
    return out
```

<caption>**Fig. 6: Pseudo-code for structure-aware attention.** We describe the way of learning convolutional inductive biases in structure-aware attention (Eq. 4) and its basic form (Eq. 5) presented in Sec. 4.1 of the main paper.</caption>

higher number of sequential operations. We employ FlashConv [50, 85] for FFT acceleration and adapt it to our implementation. The kernel fusion in FlashConv addresses the I/O bottleneck by fusing the entire calculation into a single kernel and computing it in GPU SRAM.

<table><caption>**Table 12: Comparisons among LiSA & attention operators in FLOPs, inference latency, and training latency.** The latency is measured by an RTX A6000 (batch=32, channels=192). OOM is an abbreviation of out-of-memory.</caption><thead><tr><th rowspan="3">block</th><th colspan="2">(H, W) = (7, 7)</th><th colspan="2">(H, W) = (14, 14)</th><th colspan="2">(H, W) = (28, 28)</th><th colspan="2">(H, W) = (56, 56)</th><th colspan="2">(H, W) = (84, 84)</th></tr><tr><th>FLOPs</th><th>infer</th><th>train</th><th>FLOPs</th><th>infer</th><th>train</th><th>FLOPs</th><th>infer</th><th>train</th><th>FLOPs</th><th>infer</th><th>train</th></tr><tr><th>(M)↓</th><th>(ms)↓</th><th>(ms)↓</th><th>(M)↓</th><th>(ms)↓</th><th>(ms)↓</th><th>(M)↓</th><th>(ms)↓</th><th>(ms)↓</th><th>(G)↓</th><th>(ms)↓</th><th>(ms)↓</th></tr></thead><tbody><tr><td>Self-attn [47]</td><td>22.7</td><td><b>0.9</b></td><td><b>2.6</b></td><td>102.0</td><td>1.6</td><td>4.9</td><td>584.0</td><td>13.0</td><td>39.6</td><td>5.2</td><td>174.7</td><td>531.8</td><td>22.2</td><td>OOM</td><td>OOM</td></tr><tr><td>Convolutional attn [16]</td><td>23.1</td><td>1.7</td><td>4.6</td><td>104.0</td><td>2.7</td><td>11.0</td><td>413.0</td><td>8.5</td><td>32.1</td><td>1.6</td><td>30.5</td><td>120.8</td><td>3.7</td><td>68.0</td><td>266.5</td></tr><tr><td>LiSA (ours)</td><td><b>21.8</b></td><td>1.2</td><td>3.2</td><td><b>87.3</b></td><td>1.3</td><td><b>4.3</b></td><td><b>349.0</b></td><td>4.6</td><td>13.6</td><td>1.4</td><td><b>19.8</b></td><td><b>59.2</b></td><td><b>3.1</b></td><td><b>45.0</b></td><td><b>139.5</b></td></tr></tbody></table>

**Fine-tuning on higher resolutions.** We have verified that fine-tuning LiSANet on higher resolutions can boost image recognition accuracy. Tab. 13 summarizes the results of LiSANet-I on ImageNet. LiSANet obtains a 2.5% gain when we use 384 × 384 resolution. While MLP-mixer models are hard to adapt to higher resolutions since they process a fixed number of tokens, LiSANet can be easily interpolated to higher resolutions due to the property of Discrete Fourier transform, where each element of the time (i.e. spatial) domain is a sampling of a continuous spectrum in the frequency domain. Since the circular embeddings $W^a, W^b$ can be considered as samplings of continuous spectrums, changing the resolution is
```python
# B: batches, N: tokens, C: channels, D: latent bidirectional
# LiSA(input, Wa, Wb, B):
# input shape: [B,N,C], Wa shape: [N,C,D], Wb shape: [N,D], B shape: [C,D]
    qkv = linearproj(input, channels=3C) # shape: [B,N,3C]
    query,key,value = split(qkv, [C,C,C], dim=-1)
    # query,key,value shape: [B,N,C]
    query = L2norm(query) # shape: [B,N,C]
    key = L2norm(key) # shape: [B,N,C]

    K_ftt = rfft(key, dim=1) # shape: [B,N//2+1,C]
    Wa_ftt = rfft(Wa, dim=0) # shape: [N//2+1,C,D]
    K_Wa = einsum(K_ftt, Wa_ftt, 'BMK,MKD->BMKD') # shape: [B,N//2+1,C,D]
    K_Wa = irfft(K_Wa, dim=1) # shape: [B,N,C,D]

    V_ftt = rfft(value, dim=1) # shape: [B,N//2+1,C]
    Wb_ftt = rfft(Wb, dim=0) # shape: [N//2+1,D]
    V_Wb = einsum(V_ftt, Wb_ftt, 'BMV,MD->BMVD') # shape: [B,N//2+1,C,D]
    V_Wb = irfft(V_Wb, dim=1) # shape: [B,N,C,D]
    V_Wb_B = V_Wb + B # shape: [B,N,C,D]

out = einsum(query, K_Wa, V_Wb_B, 'BNK,BNKD,BNVD->BNV') # shape: [B,N,C]
out = layer_norm(out)
out = linearproj2(out, channels=C) # shape: [B,N,C]
return out
```

<table><caption>**Fig. 7: Pseudo-code for LiSA.** We describe the final form of LiSA described in Sec. 4.3 of the main paper.</caption><thead><tr><th>index</th><th>model</th><th>Image size</th><th>FLOPs</th><th>#params</th><th>top-1</th></tr></thead><tbody><tr><td>1</td><td>LiSANet-I</td><td>224 × 224</td><td>1.21 G</td><td>6.36 M</td><td>74.9</td></tr><tr><td>2</td><td>LiSANet-I</td><td>384 × 384</td><td>3.62 G</td><td>7.82 M</td><td>77.4</td></tr></tbody></table>

<table><caption>**Table 13: Fine-tuning to higher resolutions on ImageNet.** Image size, Top-1, accuracy (%), FLOPs (G) and the number of parameters (M) are shown.</caption><thead><tr><th>operator</th><th>FLOPs</th><th>#params</th><th>top-1</th><th>top-5</th></tr></thead><tbody><tr><td>Self-attention [47]</td><td>7.36 G</td><td>5.82 M</td><td>18.0</td><td>40.9</td></tr><tr><td>Self-attention w/ RPE [5]</td><td>7.36 G</td><td>5.87 M</td><td>24.0</td><td>50.0</td></tr><tr><td>Depthwise conv (3 × 7 × 7) [57]</td><td>3.75 G</td><td>4.82 M</td><td>33.0</td><td>60.9</td></tr><tr><td>GF layer [44]</td><td>3.53 G</td><td>6.54 M</td><td>28.7</td><td>40.0</td></tr><tr><td>Lambda convolution [7]</td><td>26.87 G</td><td>6.34 M</td><td>34.5</td><td>63.1</td></tr><tr><td>RSA [9]</td><td>72.58 G</td><td>23.45 M</td><td>34.1</td><td>62.7</td></tr><tr><td>LiSA (ours)</td><td>5.16 G</td><td>8.37 M</td><td><strong>38.1</strong></td><td><strong>67.1</strong></td></tr></tbody></table>

<caption>**Table 14: Comparison with other basic operators on SS-V2.** Top-1, top-5 accuracy (%), FLOPs (G) and the number of parameters (M) are shown.</caption>

equal to changing the sampling interval of spectrums [44]. Thus, LiSA can be adapted to higher resolutions by simple interpolation.

**LiSA analysis on videos (Something-V2).** In Tab. 14, we compare different types of operators to check the feasibility of LiSA on videos, as done in Tab. 3a for images. The isotropic model (LiSANet-I) is trained for 60 epochs from scratch, and we adopt the uniform sampling strategy [84] for training and a single crop inference for testing. We sample 8 frames per video, and the rest of the details are the same as in Sec. 5.2. Since structural patterns of videos, i.e., motion patterns, are important cues for recognizing video actions, the operators that learn convolutional inductive biases [7, 8, 44, 57] or geometric structures [9] are more effective than their self-attention counterparts [5, 47]. LiSA shows even better performance on video than image, in terms of both accuracy and complexity. While FLOPs of the attention [8, 47] and highly-expressive [7, 9] operators significantly grow due to the increased number of tokens ($T \times H \times W$), LiSA remains efficient due to its log-linear complexity.
C Visualization

In Fig. 8, we additionally visualize both self-attention and LiSA kernels of different layers and heads from
isotropic models. In the early layers, while self-attention kernels often fail to capture relevant context,
LiSA kernels focus on encoding local features. In the latter layers, both self-attention kernels and LiSA
kernels are concentrating on the context relevant to the target object. Therefore, LiSA kernels are much
more flexible than self-attention kernels due to their ability to capture structural patterns.

In Fig. 9, we visualize both self-attention and LiSA feature maps of different layers from isotropic
models. We use the L2-norm of features for each layer. Compared to self-attention, we observed that
LiSA captures the geometric layout and positions of the main objects more effectively as the feature map
progresses through the layers, verifying the effectiveness of capturing structural patterns.
<figure><img src="image_7.png" /><figcaption>**Fig. 8: Attention kernels of self-attention & LiSA.** Attention kernels from different layers and heads are visualized. For each sample, the top row is self-attention and the bottom is LiSA. Note that the red box in the center of each subfigure is the query pixel.</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Fig. 9: L2-norms of self-attention & LiSA feature maps. L2-norms of different intermediate feature maps are visualized. For each sample, the top row is self-attention and the bottom is LiSA.</figcaption></figure>