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 imes 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.