Braid-word reversible mixer
Source paper: Fox $p$-Colorings as Fixed Points of Braid Representations arXiv:2608.29046 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace a dense token- or channel-mixing matrix with a product of local braid generators acting on adjacent coordinates. Each generator is an exactly invertible 2-by-2 transformation, while the braid and far-commutativity identities give multiple equivalent factorizations of the same global operator. This creates a sparse, reversible mixer with O(kn) cost for a braid word of length k, rather than O(n^2) cost for a dense matrix.
Formulas
Mathematical statement
Let B_n be the braid group generated by sigma_1,...,sigma_{n-1}. Over a field F_p, the paper maps each generator to the identity except on coordinates i and i+1, where M(sigma_i) has block G = [[0,1],[-1,2]]. Thus for a vector a in F_p^n, the local update is b_i = a_{i+1} and b_{i+1} = -a_i + 2a_{i+1}, with all other coordinates unchanged. The inverse generator uses G^{-1} = [[2,-1],[1,0]], so every crossing is reversible. The representation satisfies M(sigma_i)M(sigma_{i+1})M(sigma_i) = M(sigma_{i+1})M(sigma_i)M(sigma_{i+1}) and M(sigma_i)M(sigma_j) = M(sigma_j)M(sigma_i) whenever |i-j| >= 2. For a word beta = sigma_{i_1}...sigma_{i_k} read top-to-bottom, M(beta) = M(sigma_{i_k})...M(sigma_{i_1}). The all-ones vector 1 is fixed by every generator because G(1,1)^T = (1,1)^T. Adapt these matrices over the real numbers, with optional normalization, and apply them independently to token or feature dimensions.
Implementation notes
Integrate the mixer at the token-mixing or channel-mixing line of a small Transformer or MLP, immediately before the feed-forward block or in place of a dense linear projection. Let the input be X in R^(B x n x d). Choose a braid word w = ((i_1,s_1),...,(i_k,s_k)), where i_t is an adjacent pair in {1,...,n-1} and s_t in {+1,-1} selects the generator or inverse. For each batch and feature dimension, apply this pseudocode: Y = X; for (i,s) in word: if s == +1: (Y[...,i],Y[...,i+1]) = (Y[...,i+1], -Y[...,i] + 2*Y[...,i+1]); else: (Y[...,i],Y[...,i+1]) = (2*Y[...,i] - Y[...,i+1], Y[...,i]); Y = Y / sqrt(2). Use the same scale convention in every branch and optionally learn one scalar gate g_t per crossing, initialized at zero, with Y <- Y + g_t*(cross(Y)-Y). For exact reversibility, omit gates and use the explicit inverse word in reverse order. The paper supplies the local update, inverse, braid identities, and invariant constant direction; empirical choices are word length, index pattern, sign pattern, normalization, and gating. Log the ratio ||Y||_2/||X||_2 and compute singular values of the composed operator on a probe matrix. First run on CIFAR-10 with a 6-layer, width-256 MLP-Mixer or a 4-layer, 8-head Transformer. Compare against a fixed permutation, depthwise convolution, butterfly mixing, and a dense learned n-by-n mixer at matched FLOPs. Measure accuracy, loss at equal optimizer steps, wall-clock throughput, activation-norm drift, and parameter count. Success means comparable or better accuracy with at least 2x lower mixer FLOPs and bounded activation norms; failure means norm explosion, severe rank deficiency, or slower loss descent than the permutation baseline.
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.