# Evolutionary Architecture Search through Grammar-Based Sequence Alignment

arXiv: https://arxiv.org/abs/2512.04992 · HTML: https://mlsanity.com/paper/2512.04992/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 27 references that are in the map.
- First posted on arXiv 4 Dec 2025.

## Builds on (most cited first, 15 of 15)

- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search](https://mlsanity.com/paper/2001.00326/) (2020)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [Efficient Multi-objective Neural Architecture Search via Lamarckian Evolution](https://mlsanity.com/paper/1804.09081/) (2018)
- [A Survey on Evolutionary Neural Architecture Search](https://mlsanity.com/paper/2008.10937/) (2020)
- [Graph2Seq: Graph to Sequence Learning with Attention-based Neural Networks](https://mlsanity.com/paper/1804.00823/) (2018)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [JUWELS Booster -- A Supercomputer for Large-Scale AI Research](https://mlsanity.com/paper/2108.11976/) (2021)
- [Construction of Hierarchical Neural Architecture Search Spaces based on Context-free Grammars](https://mlsanity.com/paper/2211.01842/) (2022)
- [Approximate Neural Architecture Search via Operation Distribution Learning](https://mlsanity.com/paper/2111.04670/) (2021)
- [Insights from the Use of Previously Unseen Neural Architecture Search Datasets](https://mlsanity.com/paper/2404.02189/) (2024)
- [Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences](https://mlsanity.com/paper/2202.03341/) (2022)
- [Shortest Edit Path Crossover: A Theory-driven Solution to the Permutation Problem in Evolutionary Neural Architecture Search](https://mlsanity.com/paper/2210.14016/) (2022)
- [Neural Architecture Search using Particle Swarm and Ant Colony Optimization](https://mlsanity.com/paper/2403.03781/) (2024)

## Abstract (arXiv)

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.