# Modular collision-free sparse attention

- ID: 242
- Canonical URL: https://synthcore.org/idea/242/modular-collision-free-sparse-attention
- API JSON: https://synthcore.org/api/idea/242.json
- API Markdown: https://synthcore.org/api/idea/242.md
- Verification status: mechanism_works
- Source: [arXiv:2608.27432](https://arxiv.org/abs/2608.27432)
- Category: architecture
- Solves: speedup, memory, scalability
- ML areas: attention, transformer, inference-speedup
- Math tags: combinatorics, number-theory, algebra
- Ratings: usefulness 6/10; difficulty 4/10; novelty 6/10

## Idea description

Replace dense attention between grid-arranged tokens by a deterministic block-sparse pattern generated from modular permutations. In each block, connect row token i to column token p(i)=2i modulo B; because i, i-p(i), and i+p(i) are injective modulo B when gcd(B,6)=1, the pattern avoids repeated horizontal, vertical, and diagonal projections. Use shifted permutations across heads to increase receptive-field coverage while retaining structured sparsity.

## Mathematical statement

The construction decomposes an AB by AB grid into A squared blocks of size B by B. For block coordinates R,C in {1,...,A} and within-block row i in {1,...,B}, the selected column is p(i) congruent to 2i modulo B, with residues represented in {1,...,B}. The global cell has row r=B(R-1)+i and column c=B(C-1)+p(i). Its difference and sum coordinates are B(R-C)+i-p(i) and B(R+C-2)+i+p(i). For two distinct within-block indices i1 and i2, the projections i, p(i), i-p(i), and i+p(i) are distinct modulo B when gcd(B,6)=1: p(i)=2i, i-p(i)=-i, and i+p(i)=3i modulo B, and multiplication by 1, 2, and 3 is invertible modulo B. We transfer this injective-projection property to a sparse attention edge pattern so that different local source indices do not repeatedly collide under the corresponding grid directions.

## Key formulas

- $$p(i)\equiv 2i\pmod B,\qquad \gcd(B,6)=1.$$
- $$r=B(R-1)+i,\qquad c=B(C-1)+p(i).$$
- $$r-c=B(R-C)+i-p(i),\qquad r+c=B(R+C-2)+i+p(i).$$
- $$\mathcal{E}_s=\left\{\left(B(R-1)+i,\ B(C-1)+[2(i-1)+s\bmod B]+1\right):R,C\in\{1,\ldots,A\},\ i\in\{1,\ldots,B\}\right\}.$$

## Implementation notes

Integrate the construction at the attention-mask stage, before computing attention logits. Reshape N=A times B tokens into an A by A grid of blocks, each block containing B within-block positions. For each head h, choose a shift s_h in {0,...,B-1} and define p_h(i)=1+((2(i-1)+s_h) modulo B). For every block row R, block column C, and within-block query position i, add one edge from r=B(R-1)+i to c=B(C-1)+p_h(i). Store the edge list once as a compressed sparse row structure. At runtime, gather Q[r], K[c], and V[c] for all edges, compute z[r,c]=Q[r] dot K[c] divided by the square root of the head dimension, apply a segmented softmax over keys sharing the same query r, and scatter-add the weighted values into each query output. Use different shifts across heads, for example s_h=h modulo B, and optionally add a small fixed local-window edge set so nearby tokens remain directly connected. The modular formulas and injectivity claims are computed exactly; attention quality, useful shift assignments, and the benefit of local edges must be measured empirically. Start with ViT-Tiny on CIFAR-100 or ImageNet-100, using N=120 tokens, A=8, B=15, and four shifted heads. Compare dense attention, standard window attention, and the modular mask at equal hidden size and batch size. The first success criterion is at least 2 times lower attention memory and FLOPs with no more than one percentage point top-1 accuracy loss. A stronger result is matching dense-attention accuracy at larger token counts or outperforming random sparse attention at the same number of edges.

## Verification

- Status: mechanism_works
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built modular sparse attention with shifted modular permutations, segmented softmax, and scatter-add aggregation. The corrected configuration B=17 passed all injectivity checks and reduced attention score elements by 17x; on the fixed synthetic task it achieved 64.06% accuracy versus 60.94% dense and 63.57% random sparse, although the unoptimized CPU implementation was slower than dense. The originally suggested B=15 is invalid because gcd(15,6)=3 and the i+p projection is not injective.

### Mechanism check

- Verdict: Built modular sparse attention with shifted modular permutations, segmented softmax, and scatter-add aggregation. The corrected configuration B=17 passed all injectivity checks and reduced attention score elements by 17x; on the fixed synthetic task it achieved 64.06% accuracy versus 60.94% dense and 63.57% random sparse, although the unoptimized CPU implementation was slower than dense. The originally suggested B=15 is invalid because gcd(15,6)=3 and the i+p projection is not injective.
- Confidence: 7/10
- Limitations: Only a small synthetic global-mean classification task was tested, with one seed and equal training steps. Actual optimized sparse-kernel FLOPs, memory, batching scalability, vision accuracy, local-window variants, and GPU performance were not tested; the Python gather/scatter implementation did not produce wall-clock speedup on CPU.

## Artifacts

- [benchmark.py](https://synthcore.org/code/19/benchmark.py)
- [report.md](https://synthcore.org/code/19/report.md)
- [Download all files as ZIP](https://synthcore.org/download/19)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.