[Paper] Evolutionary Architecture Search through Grammar-Based Sequence Alignment

Source: arXiv - 2512.04992v1

Overview

The paper presents a fresh take on Neural Architecture Search (NAS) by borrowing ideas from bio‑informatics: it adapts the Smith‑Waterman local sequence‑alignment algorithm to measure similarity between neural network “genomes.” This grammar‑based distance makes crossover‑style evolution cheap and scalable, opening the door to faster, more diverse architecture discovery.

Key Contributions

• Grammar‑based edit distance: Introduces two variants of the Smith‑Waterman algorithm to compute a lightweight, meaningful distance between neural architectures expressed as grammar strings.
• Crossover operator for NAS: Uses the alignment to splice together sub‑structures from two parent models, generating hybrid offspring without expensive retraining.
• Complexity reduction: Shows that the new distance metric is orders of magnitude faster than prior graph‑matching approaches, enabling real‑time diversity tracking and shortest‑path queries in the search space.
• Empirical validation: Demonstrates that evolutionary runs equipped with the new crossover outperform several state‑of‑the‑art NAS methods on standard benchmarks.
• Analysis tools: Provides a framework for visualising the architectural loss landscape and monitoring population diversity during evolution.

Methodology

1. Grammar representation: Each neural architecture is encoded as a string of production rules (e.g., “Conv‑3×3 → ReLU → MaxPool”). This turns a network graph into a linear sequence that can be aligned.
2. Smith‑Waterman adaptation:
   • Local alignment finds the best‑matching subsequences between two architectures, rewarding identical modules and penalising mismatches or gaps.
   • Two variants are explored: one that favours structural similarity, another that emphasises functional similarity (e.g., matching filter sizes).
3. Edit distance computation: The alignment score is transformed into an edit distance, quantifying how many insertions, deletions, or substitutions are needed to turn one architecture into another.
4. Crossover generation: Given two parents, the algorithm extracts the aligned subsequences and swaps them, producing offspring that inherit well‑performing “building blocks.”
5. Evolutionary loop: Standard mutation operators (e.g., adding/removing layers) are combined with the new crossover. The population’s diversity is measured via the grammar‑based distance, and the shortest‑path distance to the current best model is tracked to guide exploration.

All steps are implemented with simple dynamic‑programming tables, keeping the overhead low enough for large‑scale NAS experiments.

Results & Findings

• Speed: Computing the distance between two architectures drops from O(|V|³) (graph isomorphism methods) to O(L²), where L is the grammar string length—typically a 10‑100× speed‑up.
• Search performance: On CIFAR‑10 and ImageNet‑subsets, the evolutionary algorithm with the new crossover reaches +1.2% top‑1 accuracy over baselines that rely on mutation‑only or expensive graph‑based crossover.
• Diversity preservation: The distance metric reveals that populations using the new crossover maintain higher structural diversity throughout the run, correlating with better final performance.
• Loss landscape insight: By mapping distances to validation loss, the authors show that promising architectures cluster in “valleys” that can be traversed efficiently via aligned crossover.

Practical Implications

• Faster NAS pipelines: Developers can plug the grammar‑based distance and crossover into existing evolutionary NAS frameworks and expect dramatically lower compute costs, making NAS feasible on modest GPU clusters.
• Modular architecture design: The alignment highlights reusable sub‑networks (e.g., efficient bottleneck blocks) that can be extracted and shared across projects, accelerating manual model engineering.
• Automated model diversification: The distance metric can serve as a regulariser in multi‑objective NAS, ensuring that ensembles or AutoML services produce genuinely different models rather than near‑duplicates.
• Cross‑domain applicability: Because the method works on any grammar‑defined search space, it can be extended to transformer architectures, graph neural networks, or even hardware‑aware NAS where latency constraints are encoded as grammar tokens.

Limitations & Future Work

• Grammar dependence: The quality of the distance hinges on the chosen grammar; poorly designed production rules may hide important structural nuances.
• Local alignment bias: Smith‑Waterman focuses on the best local match, which can overlook global architectural incompatibilities, potentially leading to sub‑optimal offspring.
• Scalability to very deep nets: While faster than graph methods, alignment cost still grows quadratically with sequence length, so extremely deep or highly branched models may need additional pruning or hierarchical alignment.
• Future directions: The authors suggest learning grammar encodings automatically, integrating the distance into gradient‑based NAS, and applying the technique to hardware‑constrained or multi‑task search spaces.

Bottom line: By turning neural networks into alignable strings, this work gives practitioners a practical, low‑overhead tool for evolutionary NAS that not only speeds up search but also provides new lenses for understanding and reusing model components.

Authors

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

Paper Information

• arXiv ID: 2512.04992v1
• Categories: cs.NE, cs.AI, cs.LG
• Published: December 4, 2025
• PDF: Download PDF