Two-Transitive Shuffle Mixer

(1) Integration point: replace dense token-mixing attention in a small Vision Transformer or graph network. Let X have shape B by N by d. Retain LayerNorm, residual connections, and a channel MLP, but insert a fixed token permutation before each lightweight mixing block. Choose k and n=N/k with n not a power of k; compare several factorizations of the same N. (2) Pseudocode: set X to LayerNorm(X). For layer ell, choose a short word g_ell over sigma, rho, sigma inverse, and rho inverse. Apply Y=P_{g_ell}X, where sigma sends index an+b to kb+a and rho sends it to ((a+1) mod k)n+b. Compute Z=MLP(Y), optionally with a depthwise local convolution or token gate, then update X <- X + alpha_ell Z. Initialize the learned residual gate alpha_ell to 0.1. (3) Compute exactly from the mathematics: the permutation indices and generator-word composition. Estimate empirically the coverage C_t of sampled words: C_t equals the number of distinct ordered pairs (g(x),g(y)) observed over sampled g and x not equal to y, divided by N(N-1). Select a deterministic schedule that maximizes coverage per layer, and compare it with random permutations and block-local mixing. (4) First experiment: train CIFAR-10 or Tiny-ImageNet ViTs with 196 patch tokens, comparing dense attention, shifted-window attention, random-permutation residual MLP, and this mixer at matched parameter count and FLOPs. Record accuracy, wall-clock throughput, peak memory, and C_t. Success means materially lower memory and faster inference with less than one percentage point validation-accuracy loss; failure is slow pair coverage or a large accuracy gap.