✗ Failed on benchmark 2026

Orthogonal Latin Sparse Attention

Implementation & benchmark of arXiv:2607.10890 — Generalizations of nets and Latin squares

Usefulness7/10

Difficulty5/10

Novelty7/10

Architecture Speedup Memory Accuracy Attention Transformer Inference speedup Memory Combinatorics Graph theory Algebra

Source paper: Generalizations of nets and Latin squares arXiv:2607.10890 ⓘ · analyzed Aug 30, 2026

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

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.

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

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.

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

Failed on benchmark

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not reproduced ✗

Stage 2 · Practical benchmark result: Inconclusive

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

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.

Agent confidence: 9/10

Baseline: Dense attention: 707281 score pairs, median 0.05285 s at T=841,d=32.
Idea: 4-head Latin/row/column sparse attention: 97556 score pairs, 7.25x fewer, median 0.03025 s, 1.75x dense-over-sparse speed ratio. Latin group size was exactly n and joint collision maximum exactly 1 for every tested n; random joint maximum averaged 1.99, 2.63, 3.18, 3.81, 4.01 for n=3,5,7,11,13.

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.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2607.10890) Sep 2, 2026

Ahead of the baseline (−11.3%) but not statistically significant (p=0.0816, wins 6 / 8 paired seeds).

Benchmark: Sequence modeling
Model: transformer_tiny
Paired seeds: 8
Baseline mean: 0.5692
Idea mean: 0.5046
Effect (Δ): -0.0646 (−11.3%; negative = idea better)
Wins: 6 / 8 paired seeds
p-value: 0.0816 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±13.2%
Mechanism: Not confirmed ✗
Practical effect: Inconclusive
Baseline tuning: swept over 3 configs

Limitations:

Only the registered synthetic sequence forecast track was tested. WikiText, copy accuracy, optimized sparse GPU kernels, peak activation memory, and wall-clock speed were not tested. The 32-token sequence only partially fills the 6x6 grid, so the ideal balanced-grid pair-reduction claim was not confirmed at neural-network scale.

How to run: python3 bench_experiment.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 9/10

Built and evaluated deterministic row/column Latin sparse attention against the standard dense transformer_tiny on the registered sequence forecast track. Mean test MSE was lower for the idea (0.504599 vs 0.569158), but the paired permutation test was not significant (p=0.0816), so there was no qualifying win. The trained-model mechanism signature was not confirmed because the partially filled grid yielded 356 observed sparse pairs versus 72 predicted ideal pairs.

Baseline: Best lr=0.0015; 8-seed mean MSE 0.569158, std 0.069141.
Comparison: delta_mean=-0.064559, idea_wins=6/8, p_value=0.0816, verdict=no significant win.
Idea: Best lr=0.0015; 8-seed mean MSE 0.504599, std 0.074627.
Mechanism signature: predicted_pair_reduction=14.2222, observed_pair_reduction=2.8764, confirmed=false.

Benchmark result