Course contentsShow
← Machine Learning and Deep Learning
Lesson 1355 of 3,53830. Vision TransformersFree lesson

Window Partitioning and Computational Efficiency

How restricting attention to local windows reduces complexity from quadratic to linear in image size.

Window Partitioning and Computational Efficiency

You'll learn: How restricting self-attention to local windows dramatically reduces the computational cost of Vision Transformers from quadratic to linear complexity.

The Quadratic Problem

In a vanilla Vision Transformer, every patch attends to every other patch in the image. If you have N patches, each patch computes attention with all N patches, resulting in N² operations. For high-resolution images with thousands of patches, this becomes prohibitively expensive—both in memory and compute time.

Window Partitioning: The Solution

Window partitioning divides the image into non-overlapping local windows, and attention is computed only within each window. Think of it like organizing a large conference: instead of everyone talking to everyone (chaos!), you split people into small discussion groups where conversations happen independently.

If each window contains M patches (say, 7×7 = 49 patches per window), and you have N total patches divided into windows:

  • Old complexity: N² operations (global attention)
  • New complexity: N × M operations (windowed attention)

Since M is a fixed, small constant (typically 49 or 64), the complexity becomes linear in the number of patches! This means doubling the image resolution only doubles the computation, not quadruples it.

Why This Works

Images have strong local structure—nearby pixels are highly correlated. Most visual patterns (edges, textures) are local. By focusing attention within windows, you capture the most important relationships efficiently. The Swin Transformer's shifted window mechanism later adds cross-window connections without sacrificing this efficiency.

Key Takeaway: Window partitioning reduces Vision Transformer complexity from O(N²) to O(N) by restricting self-attention to fixed-size local regions, making high-resolution image processing computationally feasible.