Evolutionary Architecture Search through Grammar-Based Sequence Alignment

Adri Gómez Martín; Felix Möller; Steven McDonagh; Monica Abella; Manuel Desco; Elliot J. Crowley; Aaron Klein; Linus Ericsson

cs.NEDec 4, 2025

Evolutionary Architecture Search through Grammar-Based Sequence Alignment

Authors: Adri Gómez Martín, Felix Möller, Steven McDonagh, Monica Abella, Manuel Desco, Elliot J. Crowley, Aaron Klein, Linus Ericsson

Organizations: Carlos III University of Madrid · Instituto de Investigación Sanitaria Gregorio Marañón · Helmholtz-Zentrum Berlin für Materialien und Energie · University of Edinburgh ·

Abstract

Neural architecture search (NAS) in expressive search spaces is a computationally hard problem, but it also holds the potential to automatically discover completely novel and performant architectures. To achieve this we need effective search algorithms that can identify powerful components and reuse them in new candidate architectures. In this paper, we introduce two adapted variants of the Smith-Waterman algorithm for local sequence alignment and use them to compute the edit distance in a grammar-based evolutionary architecture search. These algorithms enable us to efficiently calculate a distance metric for neural architectures and to generate a set of hybrid offspring from two parent models. This facilitates the deployment of crossover-based search heuristics, allows us to perform a thorough analysis on the architectural loss landscape, and track population diversity during search. We highlight how our method vastly improves computational complexity over previous work and enables us to efficiently compute shortest paths between architectures. When instantiating the crossover in evolutionary searches, we achieve competitive results, outperforming competing methods. Future work can build upon this new tool, discovering novel components that can be used more broadly across neural architecture design, and broadening its applications beyond NAS.

Figures & tables

Panel of Figure 1 — Figure 1: Example $dists$ and $paths$ matrices overlaid. Lighter coloured cells denote a higher distance from the first parent model, shown on top. Moving towards the right entails deleting a node from the first model, moving downwards represents the addition of a node from the second model, and moving diagonally corresponds to a node substitution. Dashed lines signal the closure of branching and routing nodes. The optimal mutation path is traced back in thicker lines, whose brightness reflects the weight of each operation, being brightest intensities a cost of 1, and darker ones reaching a cost of 0.

Dataset	AddNIST	Chesseract	GeoClassing	Gutenberg	Isabella	Language	MultNIST	Avg.
No Crossover	82.13 ± 11.46	60.10 ± 0.78	79.05 ± 2.44	43.35 ± 1.49	48.79 ± 2.25	93.59 ± 1.06	87.99 ± 3.29	70.71 ± 1.79
STX	97.07 ± 0.30	60.91 ± 0.49	86.27 ± 2.03	42.77 ± 1.07	49.94 ± 3.81	96.16 ± 0.61	91.68 ± 2.41	74.97 ± 0.73
CSWX	90.64 ± 4.12	58.80 ± 0.82	82.80 ± 3.29	45.75 ± 1.37	53.25 ± 1.83	95.95 ± 0.41	88.94 ± 2.89	73.73 ± 0.93
RCSWX	95.82 ± 0.36	59.94 ± 0.52	85.90 ± 2.58	44.84 ± 0.41	47.27 ± 3.48	95.41 ± 0.55	91.87 ± 1.22	74.44 ± 0.66

Table 1: Test performances of the best models found on the validation set during search, reporting mean and standard deviation across five seeds. Significance testing can be found in Appendix G .

Figure 2: Search results comparing STX, CSWX and RCSWX-based evolutionary search with mutation-only searches. The plots show the mean validation accuracy across five seeds and the standard error of the mean. To assess the average performance, we normalise the results based on the lowest and highest attained performance within each dataset and combine them into a single plot by averaging (bottom right).

Figure 3: Runtime versus node count (top; logarithmic runtime axis) and node-count distribution encountered during search (bottom). Points show recorded timings, including exception timings and resource-limit lower bounds for Rust. Curves are empirical least-squares fits in log-runtime: exponential for SEPX and offset power-law

t_{0}+an^{b}

for CSWX and both RCSWX implementations. Curves extrapolate beyond observed sizes to 200 nodes. RCSWX † denotes the serial Rust reimplementation, measured in aggregate process CPU seconds. The campaigns are not matched-hardware or common-clock comparisons.

Panel of Figure 4 — Figure 4: Architecture-landscape and population-diversity analyses for CIFAR10 (a–c) and Isabella (d–f). Panels (a,d) show two-dimensional UMAP projections based on the RCSWX edit-distance matrices. Panels (b,e) show empirical semivariograms and their fitted spherical models. Panels (c,f) show population diversity over the course of search, measured as the arithmetic mean of the RCSWX distance over all unordered architecture pairs; point colour denotes mean population fitness.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 5 — Figure 5: From left to right, top to down: original model 1 (a), and offspring models resulting from the deletion of the leftmost Computation node (b), the addition of a Routing node (c), the substitution of a positional encoding into a ReLU terminal node (d), the addition of a Branching(4) node (e) and substitution of a positional encoding into a linear terminal node (f), resulting in original model 2.

Panel of Figure 6 — Figure 6: Illustration of STX. Parent architectures $\bm{P_{1}}$ and $\bm{P_{2}}$ swap selected subtrees (highlighted), generating two offspring architectures $\bm{C_{1}}$ and $\bm{C_{2}}$ .

Method	Distance Metric	Crossover Operator	Permutation-aware crossover	Encoding	Spaces	Scaling
WL kernel (Weisfeiler–Lehman)	✗	✗	–	Graph	Any	$O(h(n_{1}+m_{1}+n_{2}+m_{2}))$
NWNAS (Needleman–Wunsch)	✓	✗	–	Sequence	Chain-based	$O(n_{1}n_{2})$
GED/SEPX (Graph Edit Distance)	✓	✓	✓	Graph	Cell-based / general DAGs	$O(n_{1}^{n_{2}})$
CSWX	✓	✓	✗	Ordered Tree	Grammar-based	$O(n_{1}n_{2})$
RCSWX	✓	✓	✓	Semi-ordered Tree	Grammar-based	$O\!\left(\sum_{i=1}^{n_{1}}\sum_{j=1}^{n_{2}}2^{d_{ij}}\right)$

Appendix

Table 2: Comparison with other methods for computing architecture distances and performing crossover. A dash indicates that permutation-aware crossover is not applicable because the method does not define a crossover operator.

Name	Addition/deletion cost	Mutation cost
Scoring matrix 0	Always 1	0 if nodes are the same, 0.25 if nodes’ children’s hyperparameters differ, 0.5 if nodes’ children’s type of node differ and $\infty$ if parents type of node differ
S. M. 1	Always 1	0 if nodes’ children’s are exactly the same, 0.5 if not, $\infty$ if parent’s type of node differ
S. M. 2	Always 1	$\infty$ if parent’s type of node differ, 0.5 otherwise
S. M. 3	Number of branches for branching nodes, 1 otherwise	Difference in number of branches for branching nodes, same as default scoring matrix otherwise

Appendix

Table 3: Default and alternative scoring schemes used to assess the robustness of the RCSWX distance calculation.

Figure 7: Distance calculated for randomly sampled pairs of models employing scoring matrices 0 (x axis) and 1 through 3 (y axis) with RCSWX, along with their linear fits and R 2 .

Architectures	Nodes	Original	Rust	Distance
ResNet18, MLP-Mixer d8	267, 264	39.054 s	0.728 s	60.38
ResNet18, MLP-Mixer d12	267, 392	342.383 s	5.529 s	95.38
ResNet34, MLP-Mixer d8	499, 264	86.633 s	1.113 s	119.62
ResNet34, MLP-Mixer d12	499, 392	741.57 min	97.136 s	115.62

Appendix

Table 4: RCSWX results on predefined architectures. Rust v0.3 times are medians of three serial alignment wall-time measurements with corner collapsing enabled.

Figure 8: Alignment matrix for ResNet34 and MLP-Mixer d12

Figure 9: Alignment matrix for ResNet18 and MLP-Mixer d8

Figure 10: Alignment matrix for ResNet18 and MLP-Mixer d12

Figure 11: Alignment matrix for ResNet34 and MLP-Mixer d8

Figure 12: Alignment matrix for two sequences with a differing number of input nodes (addition/deletion cost of 1; substitution cost of 0 if nodes are the same, 0.5 if they are interchangeable). Each matrix cell is subdivided into substitution, deletion, addition and selected costs. Selected operations are shown in a light colour, and deprecated operations are shown in grey. The shortest edit path is shown in green.

Figure 13: Critical difference (CD) diagram comparing the average ranks of the four algorithms across all datasets. The Friedman test did not reveal a statistically significant difference among the methods (p = 0.0997), and none of the Wilcoxon–Holm post-hoc comparisons reached significance. All algorithms fall within a single cluster—indicated by the horizontal connection—showing that their rank differences do not exceed the critical threshold.

Evolutionary NAS

See all 8 papers

Structuring Open-Ended NAS: Semi-Automated Design Knowledge Structuring with LLMs for Efficient Neural Architecture Search
May 19, 2026Yuiko Sakuma, Masakazu Yoshimura, Marcel Gröpl +4Large Language Model-Guided NAS Large Language Model-Guided Optimization
Sony Group Corporation, Tokyo, Japan · ETH Zurich, Switzerland
EvoTreeNAD: Genealogy-Guided Evolution for LLM-Driven Neural Architecture Discovery
Sep 24, 2026Lishan Yu, Derek Jiu, Qizhen Lan +1Large Language Model-Guided NAS Evolutionary Optimization
Department of Health Data Science and AI McWilliams School of Biomedical Informatics University of Texas Health Science Center at Houston
Transferrable Surrogates in Expressive Neural Architecture Search Spaces
Apr 17, 2025Shiwen Qin, Gabriela Kadlecová, Martin Pilát +5Neural Architecture Search Neural Surrogate Modeling
University of Edinburgh · Charles University, Faculty of Mathematics and Physics · The Czech Academy of Sciences, Institute of Computer Science +1

May 19, 2026J/K move · Enter open · S save

Structuring Open-Ended NAS: Semi-Automated Design Knowledge Structuring with LLMs for Efficient Neural Architecture Search

Yuiko Sakuma, Masakazu Yoshimura, Marcel Gröpl, Zitang Sun+3

Sony Group Corporation, Tokyo, Japan · ETH Zurich, Switzerland

Large Language Model-Guided NAS Large Language Model-Guided Optimization Neural Architecture Search

Open paper AskPDF arXiv

Current neural architecture search (NAS) methods are often limited by their predefined, restrictive search spaces. While recent large language model (LLM)-assisted NAS methods enable open-ended search spaces, they often suffer from inefficient exploration due to biased or low-quality design ideas. To address these issues, we propose to semi-automatically structure model design knowledge to guide the search process. Our approach first defines a high-level structural template of architectural attributes. An LLM then populates this template by analyzing papers, creating a rich and diverse search space that embodies this structured design knowledge. To efficiently explore this vast space, we introduce FairNAD, using a multi-type mutation that enables broad exploration through mutation with fair idea sampling, Pareto-aware mutation, LLM-driven iterative mutation, and a fine-grained feedback loop. We demonstrate the effectiveness of FairNAD in discovering high-performing architectures that yield 0.84, 2.17, and 2.35 points improvement on CIFAR-10, CIFAR-100, and ImageNet16-120, respectively, compared to current state-of-the-art methods.

Abstract

Evolutionary NAS

Explore similar work

Structuring Open-Ended NAS: Semi-Automated Design Knowledge Structuring with LLMs for Efficient Neural Architecture Search

EvoTreeNAD: Genealogy-Guided Evolution for LLM-Driven Neural Architecture Discovery

Transferrable Surrogates in Expressive Neural Architecture Search Spaces