Global Sub-Sampled Attention

Global Sub-Sampled Attention, or GSA, is a local attention mechanism used in the Twins-SVT architecture.

A single representative is used to summarize the key information for each of m ×n subwindows and the representative is used to communicate with other sub-windows (serving as the key in self-attention), which can reduce the cost to 𝒪(m n H W d)=𝒪((H² W² d)/(k₁ k₂)). This is essentially equivalent to using the sub-sampled feature maps as the key in attention operations, and thus it is termed global sub-sampled attention (GSA).

If we alternatively use the LSA and GSA like separable convolutions (depth-wise + point-wise). The total computation cost is 𝒪((H² W² d)/(k₁ k₂)+k₁ k₂ H W d) . We have:

(H² W² d)/(k₁ k₂)+k₁ k₂ H W d ≥2 H W d √(H W)

The minimum is obtained when k₁ ·k₂=√(H W). Note that H=W=224 is popular in classification. Without loss of generality, square sub-windows are used, i.e., k₁=k₂. Therefore, k₁=k₂=15 is close to the global minimum for H=W=224. However, the network is designed to include several stages with variable resolutions. Stage 1 has feature maps of 56 ×56, the minimum is obtained when k₁=k₂=√(56) ≈7. Theoretically, we can calibrate optimal k₁ and k₂ for each of the stages. For simplicity, k₁=k₂=7 is used everywhere. As for stages with lower resolutions, the summarizing window-size of GSA is controlled to avoid too small amount of generated keys. Specifically, the sizes of 4,2 and 1 are used for the last three stages respectively.