# Trace-Canonical Modular Blocks

- ID: 597
- Canonical URL: https://synthcore.org/idea/597/trace-canonical-modular-blocks
- API JSON: https://synthcore.org/api/idea/597.json
- API Markdown: https://synthcore.org/api/idea/597.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2607.08841](https://arxiv.org/abs/2607.08841)
- Category: architecture
- Solves: scalability, generalization
- ML areas: transformer, mlp, architecture
- Math tags: algebra, combinatorics, graph-theory
- Ratings: usefulness 6/10; difficulty 4/10; novelty 6/10

## Idea description

Represent a modular neural block as a word over primitive operators and identify operators that commute because they act on disjoint tensor supports. Canonicalize every equivalent word into one representative, allowing architecture search, caching, and parameter sharing to operate on equivalence classes rather than redundant layer orderings.

## Mathematical statement

The paper starts with the free monoid \(\mathcal W=\langle X\rangle\), whose elements are words \(w=x_{i_1}\cdots x_{i_k}\) over an alphabet \(X\) of operators; multiplication is concatenation and \(|w|\) is word length. A commutation graph \(\mathcal G=(X,E)\) specifies which distinct letters commute: if \((x,y)\in E\), impose \(xy=yx\). The partially-commutative monoid is the quotient \(\mathcal W_{\mathcal G}=\mathcal W/\sim\), where \(u\sim v\) when one can transform \(u\) into \(v\) by swapping adjacent commuting letters. The equivalence class is \([w]=\{v:v\sim w\}\), and all representatives have the same multiset of letters and degree. For neural operators \(f_x\), define support \(S_x\) as the tensor coordinates, channels, heads, or feature groups read and written by \(f_x\). Declare \((x,y)\in E\) only when \(S_x\cap S_y=\varnothing\), or when an analytically verified identity \(f_x\circ f_y=f_y\circ f_x\) holds. Then swapping adjacent commuting operators preserves the network function exactly, whereas noncommuting pairs retain their order.

## Key formulas

- $$\mathcal W=\langle X\rangle,\qquad w=x_{i_1}x_{i_2}\cdots x_{i_k},\qquad |w|=k.$$
- $$\mathcal W_{\mathcal G}=\mathcal W/\sim,\qquad u\sim v\ \Longleftrightarrow\ u\text{ can be transformed into }v\text{ by swaps }xy\leftrightarrow yx\text{ for }(x,y)\in E.$$
- $$[w]=\{v\in\mathcal W:v\sim w\},\qquad f_{x_1}\circ f_{x_2}=f_{x_2}\circ f_{x_1}\ \text{whenever }(x_1,x_2)\in E.$$
- $$\operatorname{canon}(w)=\min_{\prec}\{v:v\in[w]\},$$

## Implementation notes

Integrate this at the architecture-search and module-caching level for a small library of operators such as grouped linear maps, per-head attention, independent feature mixers, residual scalings, and channelwise nonlinearities. Give every primitive operator \(x\) a support set \(S_x\), for example a set of channel groups or attention heads. Build the commutation graph with an edge \((x,y)\) when the supports are disjoint; do not infer commutation merely from similar tensor shapes. For a candidate sequence \(w=[x_1,\ldots,x_k]\), repeatedly scan adjacent pairs and swap \(x_i,x_{i+1}\) if \((x_i,x_{i+1})\in E\) and the pair is inverted under a fixed total operator order \(\prec\). Stop when no swap is possible; this produces a deterministic canonical representative \(\operatorname{canon}(w)\). Use the canonical string as the key for weight sharing, memoized forward graphs, and NAS deduplication. During validation, compare outputs of every proposed swap numerically on random tensors; only allow exact or tolerance-certified swaps. The mathematical part is the equivalence relation and its correctness under verified commuting supports; the empirical part is measuring whether deduplication changes search coverage. First test on a 12-layer grouped-MLP or multi-head toy Transformer on CIFAR-100 or WikiText-2, comparing random architecture search with and without canonicalization at the same evaluation budget. Success means substantially fewer unique candidates, lower search wall-clock, and equal or better validation loss at fixed evaluations.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: no_effect
- Verdict: Built a support-aware trace canonicalizer with deterministic adjacent commuting swaps, exact swap validation, and memoized forward evaluation. Commuting swaps had maximum output error 0.0, while noncommuting swaps changed outputs with median maximum difference 0.1464. On 500 deliberately redundant proposals, canonicalization reduced 500 strings to 50 classes with identical losses and a measured 3.79x forward-evaluation speedup.

### Mechanism check

- Verdict: Built a support-aware trace canonicalizer with deterministic adjacent commuting swaps, exact swap validation, and memoized forward evaluation. Commuting swaps had maximum output error 0.0, while noncommuting swaps changed outputs with median maximum difference 0.1464. On 500 deliberately redundant proposals, canonicalization reduced 500 strings to 50 classes with identical losses and a measured 3.79x forward-evaluation speedup.
- Confidence: 9/10
- Limitations: This is a small synthetic grouped-vector experiment, not CIFAR-100, WikiText-2, a Transformer, or a full NAS loop. Redundant proposals were intentionally generated from shared traces to test the claimed caching phenomenon; speed measurements are single-run timings and do not separately report canonicalization overhead.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 1
- Paired wins: 0/8
- Benchmark verdict: no measurable effect

## Artifacts

- [bench_report.json](https://synthcore.org/code/1404/bench_report.json)
- [experiment.py](https://synthcore.org/code/1404/experiment.py)
- [report.md](https://synthcore.org/code/1404/report.md)
- [report_bench_2026-09-04T202654.md](https://synthcore.org/code/1404/report_bench_2026-09-04T202654.md)
- [stage2_bench.py](https://synthcore.org/code/1404/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/1404)

## Disclaimer

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