window partition

Window Partition is a technique that divides a feature map or image into non-overlapping local windows for efficient self-attention — computing attention independently within each window to reduce complexity from $O(N^2)$ to $O(w^2 \cdot N/w^2) = O(N \cdot w^2)$.

How Does Window Partition Work?

• Partition: Divide $H \times W$ feature map into $\frac{H}{M} \times \frac{W}{M}$ windows of size $M \times M$.
• Reshape: Each window becomes a $M^2 \times C$ tensor (sequence of $M^2$ tokens).
• Attention: Compute multi-head self-attention within each window independently.
• Unpartition: Reshape back to $H \times W \times C$.

Why It Matters

• Linear Complexity: Attention cost scales linearly with image size (fixed $M^2$ attention per window).
• Local Inductive Bias: Introduces locality similar to CNNs, which is beneficial for vision tasks.
• Foundation: The base operation for Swin Transformer, Focal Transformer, and other window-based ViTs.

Window Partition is dividing the image into attention neighborhoods — the fundamental operation that makes high-resolution Vision Transformers computationally practical.