criss-cross attention

Criss-Cross Attention is a sparse attention mechanism that computes self-attention along horizontal and vertical directions (criss-cross paths) — requiring only O(H + W) computation per position instead of O(H × W) for full attention.

How Does Criss-Cross Attention Work?

• Attention Scope: Each position attends only to its row and column (forming a "+" pattern).
• Two Iterations: Apply criss-cross attention twice — after two iterations, each position has effectively attended to all positions (through transitive connections).
• Recurrence: The second pass propagates information from the first pass's cross paths.
• Paper: Huang et al. (2019).

Why It Matters

• Efficiency: O(sqrt(N)) sparse attention approximates O(N) full attention after two passes.
• Segmentation: Designed for semantic segmentation where global context is critical.
• Memory: Much lower memory than full self-attention for high-resolution feature maps.

Criss-Cross Attention is full attention via two sparse passes — attending along rows and columns twice to efficiently capture all pairwise relationships.