Cyclic Non-Backtracking Mixer
Implementation & benchmark of arXiv:2607.05807 — Long Directed Cycles in Vertex-Transitive Digraphs
Source paper: Long Directed Cycles in Vertex-Transitive Digraphs arXiv:2607.05807 ⓘ · analyzed Aug 30, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Replace a dense token or channel mixing matrix by a fixed sparse directed graph whose states are ordered pairs of symbols and whose transitions advance through a cyclic phase. Each state has exactly two allowed successors, obtained by appending a symbol different from the previous two, producing a strongly connected, vertex-transitive sparse mixer with shared local dynamics. The prescribed phase structure prevents arbitrary short-cycle routing and can act as an anti-collapse inductive bias in recurrent, graph, or mixture-of-experts modules.
Formulas
Mathematical statement
The construction uses the vertex set V=X×Z_m, where X={(a,b):a,b∈{1,2,3,4}, a≠b}, so |X|=12 and |V|=12m. Here Z_m is the cyclic set of phases modulo m. Directed edges are exactly (a,b,t)→(b,c,t+1 mod m) for c∉{a,b}; each vertex has two outgoing and two incoming edges. Because every edge advances the phase by one, every directed cycle has length divisible by m. The paper proves that the resulting digraph is strongly connected and vertex-transitive, but has no Hamiltonian cycle: a cycle visiting all 12m states would induce a forbidden global parity pattern in the local transitions. The neural adaptation treats each graph vertex as a d-dimensional hidden vector h_{a,b,t}; the sparse graph adjacency supplies a fixed linear mixing operator, while a pointwise learned map supplies nonlinear computation. The transferable properties are constant degree, translation symmetry in t, local non-backtracking transitions c∉{a,b}, strong connectivity, and the explicit absence of a single cycle covering all states.
Implementation notes
Integrate this as a sparse mixer inside a graph neural network, recurrent state-space block, or router over a fixed bank of latent slots. Use m phases and 12 pair states per phase, each holding a d-dimensional vector h[t,a,b]. At every mixer step, for each t,b,c with b≠c, gather the two predecessors h[t-1,a,b] for a∈{1,2,3,4}\{b,c}, sum their projected values, add a residual or gated self term, and apply normalization followed by a pointwise MLP. Pseudocode is: for t in range(m): for b in 1..4: for c in 1..4, c!=b: pred = sum(W[a,b,c] @ h[(t-1)%m,a,b] for a not in {b,c}); z[t,b,c] = RMSNorm(h[t,b,c] + alpha*pred); h_new[t,b,c] = z[t,b,c] + MLP(z[t,b,c]). The edge mask and phase increment come directly from the paper; the matrices W, residual gate alpha, and MLP are learned. For parameter efficiency, tie W across t and optionally across symbol permutations, retaining only one or two matrices per transition type. Use the 12m latent states as a compact recurrent memory, or partition an input sequence into m phase groups and aggregate each group into its corresponding state. The first experiment should use m∈{8,16,32}, d=128, and compare this mixer with a dense MLP mixer, a random 2-in/2-out directed graph, and a standard diagonal SSM at matched parameter count and FLOPs on WikiText-2 language modeling or CIFAR-100 sequence classification. Measure validation loss, gradient norm variance, wall-clock throughput, activation memory, and performance degradation as m increases. Success means comparable accuracy with lower mixer memory and FLOPs than dense mixing, and more stable long-horizon behavior than a random sparse graph; failure is slower loss descent or poor information propagation across phases.
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.