## 3 Proposed Method
### Complexity Analysis  
The computation complexity of local-global self-attention in LGViT is analyzed as follows:  
For vanilla self-attention [5] with input feature maps \(x\in R^{H\times W\times C}\), the computational complexity is shown as Equation (2):  
\[\Omega(SA)=4 HWC^{2}+2(HW)^{2}C \tag{2}\]  
where \(H,W,C\) are the height, width, and channel dimensions of feature maps, respectively.  
A window-based self-attention [23] partitions the feature map into \(\frac{H}{M}\times\frac{W}{M}\) non-overlapping windows \(x_{w}\in R^{M\times M\times C}\), and the complexity is Equation (3):  
\[\Omega(WSA)=4 HWC^{2}+2M^{2}HWC \tag{3}\]  
where M is the fixed window size.  
In our local self-attention (LSA) module, the key set and value set are expanded by overlapping windows. For each window, the total number of queries is \(N_{1}=M\times M\), while the total number of keys and value are both \(N_{2}=(M+E)^{2}\), thus the complexity is Equation (4):  
\[\Omega(LSA)=4 HWC^{2}+2N_{2}HWC \tag{4}\]  
where \(M\) is the local window size, and \(E\) is the expanded size of the current layer.  
In the global self-attention module, the key set and value set are expanded by multi-scaled pooling. The total number of keys and values in Equation (4) should be as Equation (5):  
\[N_{2}=N_{1}+\Sigma_{i=1}^{n}O_{i}^{2} \tag{5}\]  
where \(N_{1}\) is the number of queries, and \(O_{i}\) means the output size of i-th scaled pooling. A detailed complexity comparison of vision transformers can be seen in Table 2.  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & **Layer Name** & **Imagenet-1K** & **COCO2017** & **ADE20K** \\ \cline{2-5}  & **InputSize** & **224 \(\times\) 244** & **1280 \(\times\) 800** & **512 \(\times\) 512** \\ \cline{2-5}  & **Window Size** & **7** & **8** & **8** \\ \hline \multirow{3}{*}{Stage1} & Patch & Conv2d (in = 3, out = 96, kernel = 4, padding = 0, stride = 4) \\  & Embedding & & & \\ \cline{2-5}  & LSA & expand\_size = 3 & expand\_size = 4 & expand\_size = 4 \\  & GSA & pooling = [(7,1,7), (3, 3, 6)] & pooling = [(32,1,32), (16, 2,31)] & pooling = [(16,1,16), (8, 2,15)] \\ \hline \multirow{3}{*}{Stage2} & Conv Merging & Conv2d (in = 96, out = 192, kernel = 3, padding = 1, stride = 2) \\ \cline{2-5}  & LSA & expand\_size = 2 & expand\_size = 3 & expand\_size = 3 \\  & GSA & pooling = [(7,1,7), (3, 3, 5)] & pooling = [(8,1,8), (8, 2,15)] & pooling = [(8,1,8), (4, 2,7)] \\ \hline \multirow{3}{*}{Stage3} & Conv Merging & Conv2d (in = 192, out = 384, kernel = 3, padding = 1, stride = 2) \\ \cline{2-5}  & LSA & expand\_size = 1 & expand\_size = 2 & expand\_size = 2 \\ \cline{2-5}  & GSA & pooling = [(7,1,7), (3, 3, 4)] & pooling = [(8,1,8), (4, 2,7)] & pooling = [(8,1,8), (4, 2,6)] \\ \hline \multirow{3}{*}{Stage4} & Conv Merging & Conv2d (in = 384, out = 768, kernel = 3, padding = 1, stride = 2) \\ \cline{2-5}  & LSA & expand\_size = 0 & expand\_size = 1 & expand\_size = 1 \\ \cline{2-5}  & GSA & — & pooling = [(8,1,8), (4, 2,6)] & pooling = [(8,1,8), (4, 2,5)] \\ \hline \hline \end{tabular}
\end{table}
Table 1: The three configurations for different visual tasks, i.e., image classification, object detection, and semantic segmentation, on three corresponding benchmark datasets, i.e., Imagenet-1K, COCO2017, and ADE20K, respectively.