# Uniform Species Architecture Sampler

- ID: 3094
- Canonical URL: https://synthcore.org/idea/3094/uniform-species-architecture-sampler
- API JSON: https://synthcore.org/api/idea/3094.json
- API Markdown: https://synthcore.org/api/idea/3094.md
- Verification status: unverified
- Source: [arXiv:2609.02932](https://arxiv.org/abs/2609.02932)
- Category: architecture
- Solves: sample-efficiency, scalability, accuracy
- ML areas: graph-nn, cnn
- Math tags: combinatorics, graph-theory, group-theory, generating-functions
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Translate a recursive neural architecture grammar into a combinatorial specification and use its generating function to sample architectures uniformly conditional on size. This removes the severe shape and branching biases of naive random tree generation, producing a better-covered architecture-search population at the same evaluation budget.

## Mathematical statement

The paper defines a combinatorial class \(\mathcal{C}\), its size-\(n\) subset \(\mathcal{C}_n=\{c\in\mathcal{C}:|c|=n\}\), and the generating function \(C(z)=\sum_{c\in\mathcal{C}}z^{|c|}=\sum_{n\ge0}c_nz^n\), where \(c_n=|\mathcal{C}_n|\) and \([z^n]C(z)=c_n\). Its acyclic-structure specification has the recursive form \(\mathcal{A}=\mathsf{Z}+\mathsf{Z}\times\mathcal{A}+\mathsf{Z}\times\mathcal{A}\times\mathcal{A}+\mathsf{Z}\times\mathrm{CYC}_3(\mathcal{A})\), where \(\mathsf{Z}\) contributes one node and \(\mathrm{CYC}_3\) identifies ordered triples under cyclic permutation. Adapt this as a grammar for rooted neural computation graphs: a node is either a leaf, a unary composition, a binary merge, or a three-branch permutation-invariant merge. Dynamic programming computes \(a_n\), the number of valid architectures of size \(n\), and recursive completion-weighted decomposition samples a structure uniformly within a fixed size. For an unlabeled 3-cycle constructor, use the cycle-index generating function \(\mathrm{CYC}_3(A)(z)=(A(z)^3+2A(z^3))/3\).

## Key formulas

- $$\mathcal{C}_n=\{c\in\mathcal{C}\mid |c|=n\},\qquad c_n=|\mathcal{C}_n|$$
- $$C(z)=\sum_{c\in\mathcal{C}}z^{|c|}=\sum_{n=0}^{\infty}c_nz^n,\qquad [z^n]C(z)=c_n$$
- $$\mathcal{A}=\mathsf{Z}+\mathsf{Z}\times\mathcal{A}+\mathsf{Z}\times\mathcal{A}\times\mathcal{A}+\mathsf{Z}\times\mathrm{CYC}_3(\mathcal{A})$$
- $$\mathrm{CYC}_3(A)(z)=\frac{A(z)^3+2A(z^3)}{3}$$

## Implementation notes

Integrate this at the neural architecture-search population generator, before model training. Define an architecture grammar with leaf L, unary node U(X) such as a residual or graph-convolution block, binary node B(X,Y) such as concatenation followed by projection, and a three-way invariant node T(X,Y,Z) such as sum aggregation. Let size count trainable blocks, and let a[n] be the number of canonical architecture trees of size n. Compute all counts up to budget N by dynamic programming. For each constructor r with child sizes n1,...,nk, compute its completion count w_r as the product of the child counts. For a requested total size n, enumerate feasible constructor and child-size tuples and choose each tuple with probability proportional to its number of completions. Recurse until leaves, then assign operation labels from a finite set and canonicalize commutative children by sorting their serialized hashes. For the symmetric three-way merge, enumerate unordered triples directly or use the cycle-index correction (A(z)^3+2A(z^3))/3. Cache sampled subtrees and reject only tensor-shape-invalid combinations, or include shape and type as additional DP states. The exact mathematical components are the coefficient recursion, symmetry quotient, and completion-weighted sampling; operation validity and downstream accuracy are empirical. First compare 1,000 architectures on CIFAR-10 using a small GraphNAS-style GNN or eight-block image model against uniform random mutation and ordered random trees at equal training FLOPs. Measure distinct canonical structures, validation accuracy after a fixed budget, and best accuracy versus evaluated architectures. Success is higher best and median accuracy with lower variance at small search budgets.

## Disclaimer

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