# Orthogonal Latin Sparse Attention

- ID: 713
- Canonical URL: https://synthcore.org/idea/713/orthogonal-latin-sparse-attention
- API JSON: https://synthcore.org/api/idea/713.json
- API Markdown: https://synthcore.org/api/idea/713.md
- Verification status: failed_benchmark
- Source: [arXiv:2607.10890](https://arxiv.org/abs/2607.10890)
- Category: architecture
- Solves: speedup, memory, accuracy
- ML areas: attention, transformer, inference-speedup, memory
- Math tags: combinatorics, graph-theory, algebra
- Ratings: usefulness 7/10; difficulty 5/10; novelty 7/10

## Idea description

Partition tokens into a rectangular grid and use Latin-square labels to define several sparse attention heads. Each head attends only to tokens sharing a row, column, or Latin label, while orthogonality guarantees that every pair of labels occurs at most once, reducing systematic blind spots and repeated collisions. The resulting masks are deterministic, reusable across examples, and can be generated without learned routing scores.

## Mathematical statement

The paper defines a Latin square L of order n as an n by n array in which every symbol in [n] appears exactly once in each row and each column. Two Latin squares L1 and L2 are orthogonal when the ordered pairs (L1(i,j),L2(i,j)) are distinct for all i,j in [n]. Thus the map from (i,j) to (L1(i,j),L2(i,j)) is injective, and for order n it is a bijection onto [n] squared. Use r(i,j)=i, c(i,j)=j, and h_s(i,j)=L_s(i,j) as several balanced token partitions. A mask based on equality of one label gives groups of exactly n tokens, while the joint condition L_a(i,j)=u and L_b(i,j)=v selects at most one token because of orthogonality. The construction therefore supplies balanced neighborhoods and an exact anti-collision guarantee, unlike independent random hashes.

## Key formulas

- $$\forall i\in[n],\quad \{L(i,1),\ldots,L(i,n)\}=[n],\qquad \forall j\in[n],\quad \{L(1,j),\ldots,L(n,j)\}=[n].$$
- $$L_1\perp L_2\quad\Longleftrightarrow\quad \big(L_1(i,j),L_2(i,j)\big)\neq\big(L_1(i',j'),L_2(i',j')\big)\ \text{whenever }(i,j)\neq(i',j').$$
- $$\mathcal{N}_{s,u}=\{(i,j):L_s(i,j)=u\},\qquad \left|\mathcal{N}_{s,u}\right|=n,$$
- $$M_{a,b,u,v}(i,j)=\mathbf{1}\{L_a(i,j)=u\ \land\ L_b(i,j)=v\},\qquad \sum_{i,j}M_{a,b,u,v}(i,j)\le 1.$$

## Implementation notes

Integrate this into the attention-mask construction, before the softmax and preferably without changing the dense QKV projections. Let the sequence length be T=n squared, pad or truncate to a square, and reshape token index t into grid coordinates (i,j). Precompute one or more orthogonal Latin squares L_s; for prime n, a simple family is L_a(i,j)=((i-1)+a(j-1)) modulo n plus 1, using distinct slopes a modulo n. For attention head s, assign each token to a group by g_s(i,j)=L_s(i,j), and construct block-sparse edges t to t' whenever g_s(t)=g_s(t'). Add optional row and column heads using g_0=i and g_minus1=j. Pseudocode: reshape tokens to an n by n grid; for each head s, compute labels L_s, sort token indices by label, pack Q, K, and V by groups, compute grouped softmax of QK transpose divided by square root of d, multiply by grouped V, and unpack outputs. Compute the Latin tables analytically rather than learning them initially. Compare against dense attention and random equal-size hash attention on a small language model, such as a 6-layer Transformer on WikiText-2 or synthetic long-range copy tasks, at the same number of attended pairs. Measure validation perplexity, copy accuracy, wall-clock attention time, and peak activation memory. The expected signal is lower variance across groups and better long-range or copy accuracy than random hashing at the same sparsity, with memory and runtime approximately proportional to T times n rather than T squared.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: inconclusive
- Verdict: Built deterministic orthogonal Latin sparse attention masks with row, column, and two Latin-label partitions. Across n=3,5,7,11,13, every group had exactly n tokens and every orthogonal joint label bin had exactly one token, while randomized partitions had increasing collisions (mean maximum 1.99 to 4.01) and fewer occupied bins. For n=29, four sparse heads reduced score pairs 7.25x and ran 1.75x faster than dense NumPy attention, so the claimed mechanism manifested; this is not evidence of downstream modeling accuracy.

### Mechanism check

- Verdict: Built deterministic orthogonal Latin sparse attention masks with row, column, and two Latin-label partitions. Across n=3,5,7,11,13, every group had exactly n tokens and every orthogonal joint label bin had exactly one token, while randomized partitions had increasing collisions (mean maximum 1.99 to 4.01) and fewer occupied bins. For n=29, four sparse heads reduced score pairs 7.25x and ran 1.75x faster than dense NumPy attention, so the claimed mechanism manifested; this is not evidence of downstream modeling accuracy.
- Confidence: 9/10
- Limitations: The benchmark uses a simple NumPy grouped implementation rather than an optimized GPU kernel, and the dense and sparse outputs are intentionally not equivalent because they use different attention neighborhoods. No Transformer training, validation perplexity, copy-task accuracy, peak GPU memory, composite-prime orders, or end-to-end FLOP-matched language-model comparison was tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0816
- Paired wins: 6/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/304/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/304/bench_report.json)
- [experiment.py](https://synthcore.org/code/304/experiment.py)
- [report.md](https://synthcore.org/code/304/report.md)
- [report_bench_2026-08-31T003702.md](https://synthcore.org/code/304/report_bench_2026-08-31T003702.md)
- [results.json](https://synthcore.org/code/304/results.json)
- [Download all files as ZIP](https://synthcore.org/download/304)

## Disclaimer

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