Orthogonal anti-Latin hash routing
Source paper: Mutually orthogonal anti-Latin squares arXiv:2608.30082 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace random or learned routing hashes for tokens arranged on a d by d grid with a fixed family of mutually orthogonal anti-Latin squares. Each channel assigns exactly d of the d squared tokens to every bucket, while any two channels jointly distinguish every grid position. The resulting router has deterministic load balance and multi-view positional diversity.
Formulas
Mathematical statement
An anti-Latin square A of order d is a d by d matrix with entries in the alphabet [d] = {0, ..., d - 1}, such that every symbol occurs exactly d times in the whole matrix and at least one symbol repeats in every row and every column. Two anti-Latin squares A^(r) and A^(s) are orthogonal when the map from cell position (i,j) to the ordered pair (A^(r)_(i,j), A^(s)_(i,j)) is one-to-one. Since both the set of cells and the set of ordered pairs have size d squared, every ordered pair appears exactly once. The paper proves N_L(d) + 1 <= N_A(d) <= N_L(d) + 2, and N_A(d) = N_L(d) + 2 for d >= 4, where N_A and N_L are the maximum sizes of mutually orthogonal anti-Latin and Latin-square families. The transferable facts are exact marginal balance, pairwise collision-freedom, and the existence of several deterministic channels.
Implementation notes
Integrate the construction at the routing decision in an MoE layer whose tokens correspond to a d by d image-patch grid or a sequence reshaped into that grid. Prepare K mutually orthogonal anti-Latin squares offline and store them as an integer tensor A with shape [K,d,d]. For token position (i,j), select a channel r and compute q = A[r,i,j]. In a fixed top-1 router, map q directly to expert q when the number of experts is d. For two-channel routing, compute q1 = A[r,i,j] and q2 = A[s,i,j], then use the pair as a structured code; with d squared experts use expert index q1 times d plus q2, while with fewer experts hash the pair but retain both labels as auxiliary features. Rotate r and s across layers or batches. A practical hybrid is score_e = alpha times fixed_score_e plus (1-alpha) times learned_gate_e(x), with alpha initially near one and decayed if learned routing improves accuracy. The exact load count is computed from the identity sum over i,j of indicator[A[r,i,j] = q] = d, so no stochastic estimate or load-balancing loss is needed for the fixed component. Measure expert counts, overflow, token dropping, pairwise co-routing collisions, router entropy, and training variance. First test a Switch-style Transformer or ViT-Tiny on CIFAR-100 with d = 8, 64 tokens, and 8 experts. Compare anti-Latin routing against random balanced hashing and learned top-1 routing with an auxiliary load loss at equal FLOPs. Success is zero or near-zero overflow, lower batch-to-batch expert-load variance, and equal or better validation accuracy without the auxiliary balancing term.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.