arXiv:2607.18499 2026 Architecture 1 ideas extracted · analyzed Aug 30, 2026
The paper gives a combinatorial construction for balanced sparse interaction patterns. Its central incidence identity, $MM^T=(r-\lambda)I+\lambda J$, guarantees that every token is covered by the same number of blocks and that every token pair co-occurs in the same number of blocks. This structure can replace dense self-attention with overlapping block attention, preserving uniform pair coverage while reducing the quadratic interaction count. The most direct experiment is to compare design-based masks against contiguous windows and random sparse masks at equal attention FLOPs on long-range language modeling and copy tasks.
Construct overlapping attention windows from a block design instead of using one dense sequence-by-sequence attention matrix. Every token appears in exactly $r$ windows and every token pair co-occurs in exactly $\lambda$ windows, giving uniform coverage and avoiding the uneven connectivity of arbitrary sparse masks.