Automorphism-corrected architecture MCMC
Implementation & benchmark of arXiv:2608.12430 — Metropolis-Hastings Sampling of Phylogenetic Networks: Correcting for Symmetries
Source paper: Metropolis-Hastings Sampling of Phylogenetic Networks: Correcting for Symmetries arXiv:2608.12430 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Run Metropolis-Hastings directly on neural architectures modulo permutations of structurally exchangeable hidden units, channels, or experts rather than treating every labelled representation as a distinct architecture. Correct the proposal ratio using representation-orbit sizes, so architectures with many internal symmetries receive the intended posterior mass.
Formulas
Mathematical statement
The paper uses the Bayesian posterior $\pi(N\mid\theta)=\frac{\prior(N)\likelihood(\theta\mid N)}{\mathbb{P}(\theta)}$, where $N$ is a network, $\theta$ is observed data, $\prior(N)$ is its prior, $\likelihood(\theta\mid N)$ is its likelihood, and $\mathbb{P}(\theta)$ is the evidence. Let a finite permutation group $G$ act on a fully labelled neural architecture $x$ by permuting exchangeable units or experts. The unlabelled architecture is the orbit $[x]=\{g\cdot x:g\in G\}$, and its stabilizer is $\mathrm{Aut}(x)=\{g\in G:g\cdot x=x\}$. Orbit-stabilizer gives $|[x]|=|G|/|\mathrm{Aut}(x)|$. If the intended target is a posterior $\bar\pi([x]\mid\theta)$ over unlabelled architectures but proposals operate on labelled states, the labelled target is $\pi_{\mathrm{lab}}(x\mid\theta)\propto\bar\pi([x]\mid\theta)/|[x]|=\bar\pi([x]\mid\theta)|\mathrm{Aut}(x)|/|G|$. Thus the Metropolis-Hastings acceptance probability includes the automorphism ratio $|\mathrm{Aut}(y)|/|\mathrm{Aut}(x)|$. Here $q(y\mid x)$ is the forward proposal probability and $q(x\mid y)$ is the reverse proposal probability. The correction is unnecessary when every architecture has a trivial automorphism group.
Implementation notes
Integrate this into a discrete Bayesian neural architecture sampler rather than ordinary SGD. Start with a small mixture-of-experts or MLP architecture represented as a coloured directed graph: vertices are hidden units or experts, vertex colours encode layer and activation, and edge labels encode connectivity or tensor shape. Define $G$ as the product of within-layer permutations, for example $S_{d_1}\times\cdots\times S_{d_L}$ for hidden widths $d_l$. Each MCMC state $x$ contains the labelled architecture and a validation-loss or trained-weight posterior proxy. At every step: (1) draw $y\sim q(\cdot\mid x)$ using an add/remove-expert, width-change, edge-rewire, or label-swap proposal; (2) canonicalize both graphs to identify their orbits $[x]$ and $[y]$; (3) compute $a_x=|\mathrm{Aut}(x)|$ and $a_y=|\mathrm{Aut}(y)|$ with exact coloured-graph automorphism software for the MVP, or partition refinement followed by backtracking; (4) evaluate $\bar\pi([x]\mid\theta)\propto\exp(-L_{\mathrm{val}}(x)/T)\,\prior(x)$; (5) accept using the displayed formula, including $a_y/a_x$ and the reverse/forward proposal ratio. Estimate automorphism sizes from architecture graph structure, not floating-point weights, unless weight symmetry is explicitly part of the state. First test on MNIST or CIFAR-10 with two-layer MLPs or four-expert MoEs and widths 2--8. Compare naive labelled MH, canonicalized MH without correction, and corrected MH under the same architecture-evaluation budget. Measure effective sample size, posterior mass over canonical architecture classes, frequency of repeated or exchangeable units, acceptance rate, and best validation accuracy. Success means reduced bias toward asymmetric encodings and higher effective sample size or better architecture discovery at equal evaluations.
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.