# Canonical orbit search for symmetric pruning masks

- ID: 454
- Canonical URL: https://synthcore.org/idea/454/canonical-orbit-search-for-symmetric-pruning-masks
- API JSON: https://synthcore.org/api/idea/454.json
- API Markdown: https://synthcore.org/api/idea/454.md
- Verification status: failed_benchmark
- Source: [arXiv:2607.05967](https://arxiv.org/abs/2607.05967)
- Category: architecture
- Solves: speedup, scalability
- ML areas: pruning, architecture
- Math tags: combinatorics, group-theory
- Ratings: usefulness 6/10; difficulty 5/10; novelty 8/10

## Idea description

Enumerate structured pruning masks only up to exact permutations of exchangeable channels, hidden units, or experts. Replace exhaustive mask search with canonical augmentation: retain a subset only when it is lexicographically smallest among all masks obtained by the model's symmetry group, while recursively generating only canonical predecessors.

## Mathematical statement

The paper defines lexicographic order for equal-cardinality subsets S,R contained in [n] by S <_{lex} R if and only if min(S triangle R) belongs to S, where S triangle R is the symmetric difference and min(emptyset) is infinity. A finite permutation group G contained in the symmetric group on n elements acts on subsets by g(S) = {g(i): i in S}; the canonical representative is C(S) = lex-min {g(S): g in G}. Lemma 2 states that if S = C(S) and S is nonempty, then S-minus = S minus {max S} also satisfies S-minus = C(S-minus). Here [n] indexes candidate channels or experts and k = |S| is the number retained. This predecessor-closure property means depth-first backtracking that expands only canonical subsets still reaches every orbit exactly once. For an ML mask, G must be an exact network symmetry: permuting equivalent hidden channels requires applying the inverse permutation to adjacent weight dimensions, and permuting identical MoE experts requires permuting both expert parameters and router-output columns.

## Key formulas

- $$S<_{\mathrm{lex}}R\iff\min(S\mathbin{\triangle}R)\in S,$$
- $$C(S):=\operatorname{lex\text{-}min}\{g(S):g\in\mathfrak G\},\qquad S^{-}:=S\setminus\{\max S\},$$
- $$C(S)=S\ \Longrightarrow\ C(S^{-})=S^{-},$$
- $$\operatorname{keep}(S)=\mathbf 1\!\left[S=\min_{g\in\mathfrak G}^{\mathrm{lex}}g(S)\right],\qquad \mathcal M_k/\mathfrak G=\{S\subseteq[n]:|S|=k,\ \operatorname{keep}(S)=1\}.$$

## Implementation notes

Integrate this into a discrete structured-pruning or architecture-search evaluator before expensive fine-tuning. Let indices 1 through n denote exchangeable channels in one hidden layer, or exchangeable experts in one MoE layer. First construct the exact symmetry group: for a simple MVP, use all permutations of channels within one homogeneous layer; for several groups of equivalent components, use the product of their permutation groups. Represent a candidate retained set S as a sorted integer tuple. Implement is_canonical(S) by applying every g in G, sorting the resulting tuple, and comparing it with S using the first differing element; retain S only if it is lexicographically smallest. Enumerate recursively from the empty set by appending an index larger than the current maximum, and call is_canonical on every child before recursing. Pseudocode: `dfs(S): evaluate(S) if len(S)==k; for i in range(max(S)+1,n): T=sort(S+[i]); if is_canonical(T): dfs(T)`. The predecessor formula guarantees that canonical children have canonical parents, so this does not discard an orbit's only representative. Estimate the group size and orbit count empirically; the canonicality test is exact for the supplied permutations. For larger groups, use a stabilizer-chain or graph-canonical-labeling implementation, validated against exhaustive enumeration for small n. The first experiment should use a width-12 MLP on MNIST or CIFAR-10, enumerate all masks retaining k=6 channels, and compare exhaustive mask evaluation against canonical search using channel permutations. Measure evaluated masks, wall-clock search time, and best validation accuracy after identical one-shot-supernet scoring. Success is a reduction near the number of symmetry orbits with unchanged best accuracy; for a fully exchangeable layer, the 924 masks can collapse to one representative.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: harms
- Verdict: Built an exact permutation-group canonicalizer, canonical DFS, orbit coverage checks, and a two-block symmetry experiment. The math checks passed: canonical representatives covered every mask orbit, DFS matched the canonical set, predecessor closure held, and the lexicographic order check passed. Under full exchangeability, 70 masks collapsed to 1; under two exchangeable blocks, 70 masks collapsed to 5 with identical best score and 14x fewer evaluated candidates. The reduction is real, but naive factorial canonicality testing was slower in wall-clock time than exhaustive scanning at this tiny size.

### Mechanism check

- Verdict: Built an exact permutation-group canonicalizer, canonical DFS, orbit coverage checks, and a two-block symmetry experiment. The math checks passed: canonical representatives covered every mask orbit, DFS matched the canonical set, predecessor closure held, and the lexicographic order check passed. Under full exchangeability, 70 masks collapsed to 1; under two exchangeable blocks, 70 masks collapsed to 5 with identical best score and 14x fewer evaluated candidates. The reduction is real, but naive factorial canonicality testing was slower in wall-clock time than exhaustive scanning at this tiny size.
- Confidence: 9/10
- Limitations: No neural-network training or real pruning accuracy experiment was run. The implementation enumerates explicit permutation groups, so factorial group construction and canonicality scans do not scale; a stabilizer-chain or graph-canonical-labeling backend is needed for larger channel counts.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 0/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_experiment.py](https://synthcore.org/code/1307/bench_experiment.py)
- [bench_report.json](https://synthcore.org/code/1307/bench_report.json)
- [canonical_orbit.py](https://synthcore.org/code/1307/canonical_orbit.py)
- [experiment.py](https://synthcore.org/code/1307/experiment.py)
- [report.md](https://synthcore.org/code/1307/report.md)
- [report_bench_2026-09-04T145218.md](https://synthcore.org/code/1307/report_bench_2026-09-04T145218.md)
- [Download all files as ZIP](https://synthcore.org/download/1307)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.