Evolutionary Architecture Search through Grammar-Based Sequence Alignment

AI summary

Overview

Research area: Neural Architecture Search (NAS) — specifically evolutionary search methods and distance metrics for grammar-based (context-free grammar) architecture search spaces. The paper sits at the intersection of evolutionary computation, program/grammar representations, and bioinformatics-inspired sequence alignment.

Technical level: Advanced. The paper assumes familiarity with context-free grammars, derivation trees, dynamic-programming sequence alignment (Smith-Waterman, Needleman-Wunsch), graph edit distance, and standard NAS terminology (search space, search strategy, performance estimator).

Scope: The paper introduces two variants of the Smith-Waterman local sequence alignment algorithm — CSWX and RCSWX — as a fast crossover operator and distance metric for architectures encoded in the einspace probabilistic context-free grammar, showing orders-of-magnitude speed-ups over the prior SEPX method, competitive search performance across seven datasets, and a large-scale analysis of architectural loss-landscape smoothness.

What This Paper Is About

Expressive, grammar-based NAS search spaces (such as einspace) can encode far more varied architectures than traditional cell-based spaces like NAS-Bench-101 or NAS-Bench-201, but existing crossover operators do not scale to them. The prior state of the art, shortest edit path crossover (SEPX), requires solving an NP-hard graph edit distance problem, so it becomes computationally intractable as architecture size grows. The paper's goal is a crossover operator and distance metric that is fast enough to use on large grammar-defined architectures while remaining syntactically valid and, in its recursive form, invariant to functionally irrelevant permutations of branches.

Key Contributions

1. A grammar-based sequence-alignment algorithm for computing edit paths and edit distances between neural architectures in expressive search spaces, with a constrained scoring scheme that guarantees the produced offspring is syntactically valid under the grammar. The authors show this reduces computation time by orders of magnitude compared to previous methods.
2. Two method variants: constrained Smith-Waterman crossover (CSWX) for sequentialised encodings, and recursive constrained Smith-Waterman crossover (RCSWX), which collapses permutation submatrices to achieve invariance to branch ordering while reusing pre-computed alignment information.
3. New applications enabled by the algorithm: (a) crossover along the shortest edit path in grammar-based NAS, and (b) use of the resulting distance as a metric for measuring population diversity and analysing the architectural loss landscape.
4. Demonstration in one of the most expressive search spaces to date (einspace), establishing new tools for search and interpretability, and revealing the loss landscape at what the authors describe as unprecedented scale, quantifying its smoothness and clustered structure.

Main Findings

• Formal metric properties: The authors prove that the CSWX edit distance satisfies non-negativity, identity of indiscernibles, symmetry, and the triangle inequality, making it a metric on the syntactic space of grammar representations. RCSWX additionally satisfies identity of indiscernibles in the semantic space, where architectures are considered identical if they are functionally equivalent (e.g., differing only by branch permutations).

• Complexity improvements: SEPX scales as O(n₁^n₂) because it requires solving graph edit distance. CSWX scales as O(n₁n₂). Brute-force permutation-invariant CSWX scales as O(n₁n₂ 2^b), with a worst case of O(n₁n₂ 2^((n₁+n₂)/4)). RCSWX reduces the exponential factor to 2^(d_ij) per cell, where d_ij is the number of simultaneously open branches, giving a worst case of O(m·2^(2m)) for m = n₁/4 − 1 (assuming n₁ = n₂). The authors state RCSWX is faster than both SEPX and brute-force CSWX in all cases.

• Runtime measurements: In the scalability experiment, SEPX becomes intractable at around 20 nodes, while CSWX and RCSWX can be computed in less than a second for many architecture pairs. RCSWX reaches 71 nodes before any computation takes longer than one second. SEPX and RCSWX produce identical edit paths on the tested graphs, which the authors confirmed empirically. CSWX was sometimes slower than RCSWX, which the authors attribute partly to implementation overhead and partly to RCSWX's constraints reducing the number of valid paths.

• Search performance (test accuracy of best models found on validation, mean ± std over five seeds):

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

• Dataset-dependent strategy: Some datasets benefit from the information sharing enabled by crossover (CSWX on AddNIST; STX on Chesseract), while others benefit from less constrained exploration (mutation-only searches on Isabella). In some cases RCSWX's permutation-invariant interpolation underperformed CSWX, which the authors suggest injects useful noise in the form of unnecessary mutation operations. All methods behaved similarly on validation on average, but mutation-based approaches showed higher overfitting, with the lowest test scores.

• Loss landscape smoothness (CIFAR10 and Isabella): Using a 1000 × 1000 matrix of pairwise RCSWX distances over the 1000 architectures of a single seeded search run, UMAP projections show highly fragmented spaces — architectures cluster into a small number of well-separated islands with local continuity but limited cross-cluster continuity. For CIFAR10, semivariance is very low for h ≤ 5, rises steadily, and plateaus around h ≈ 15; a spherical fit gives a small nugget, a sill matching the maximal performance variance, and a range of roughly 25 edits. For Isabella, the semivariogram indicates that distance between two architectures does not appear to affect how their fitness correlates, suggesting a much flatter space. The authors characterise CIFAR10 as locally smooth but globally rugged and fragmented, and Isabella as flatter with little performance difference among clusters.

• Diversity dynamics: Plots of average pairwise distance across search iterations show significant fluctuations in population diversity, with alternating phases of exploration (broadening the search, increasing diversity) and exploitation (converging on promising regions).

• Scope of evidence: The authors note their results span around 140 000 architecture evaluations across seven datasets and five seeds, and describe this as only an initial assessment, not a state-of-the-art benchmark claim.

Methodology in Plain English

The researchers start from einspace, a probabilistic context-free grammar that describes neural networks as derivation trees. Any architecture in this grammar can be serialised into a flat sequence of tokens, with special separator tokens marking where branching and routing blocks begin and end.

They then reuse a classic bioinformatics tool: Smith-Waterman local sequence alignment, originally designed to find similar subsequences in DNA or protein sequences. Placing the two parent architecture sequences on perpendicular axes of a matrix, they fill the matrix with the cost of transforming one parent into the other using three operations — addition, deletion, and substitution — computed by dynamic programming. The key adaptation is a validity check applied at every cell: substitution is only allowed between nodes of the same type, and any separator token operation must be matched by the corresponding operation on its branching or routing node, with branches properly closed. This constraint is what keeps the resulting offspring syntactically valid under the grammar, and it turns the method from a general sequence aligner into an ordered-architecture aligner. Once the alignment is traced back into a list of operations, only a sampled subset is applied, producing a hybrid offspring rather than simply the second parent.

The recursive variant, RCSWX, addresses the fact that the order of branches in an encoding does not change what the network computes. Rather than recomputing the whole alignment matrix for every possible branch ordering (which grows exponentially), RCSWX splits the matrix into submatrices around branching nodes, computes the 2^d permutations within each, and collapses them at separator tokens by keeping the minimum-cost path to each cell. This reuses computation and yields the same operations as the brute-force approach.

To test the method, the authors run evolutionary searches on a subset of the Unseen NAS benchmark datasets: AddNIST, Chesseract, GeoClassing, Gutenberg, Isabella, Language, and MultNIST. Each run starts from 100 randomly sampled architectures, then performs 900 further iterations for 1000 total architecture evaluations, in steady-state fashion (a new offspring is generated and the oldest individual is removed), with parents chosen by tournament selection, crossover and mutation probabilities both set to 1.0, and five random seeds. They also measure runtime against the number of nodes for SEPX, CSWX, and RCSWX, and use the RCSWX distance to build distance matrices over the 1000 architectures of a single seeded run on CIFAR10 and Isabella, which they visualise with UMAP projections and analyse with semivariograms. Large-scale experiments ran on JUWELS.

Why This Matters

Impact on research. The work removes a practical bottleneck in grammar-based NAS. Prior principled crossover (SEPX) was limited to small graphs such as NAS-Bench-101's 7-node cells because of NP-hard graph edit distance; this paper provides a fast alternative that also doubles as a metric, enabling diversity control, loss-landscape analysis, and shortest-path computation between architectures in large expressive spaces. The authors frame the result explicitly as a tool for further research rather than an attempt to set a state-of-the-art benchmark.

Real-world applications (as plausible directions the method enables — the paper does not report deployed systems):

• Automated neural network design for mixed or tabular/sequence data, which is what the seven Unseen NAS benchmark datasets exercise.
• Discovery and reuse of performant architectural blocks, which the authors identify as a promising strategy for transferring components across model designs.
• Design-space analysis for teams choosing between architectures, using the RCSWX distance to quantify how smooth or fragmented a search space is before committing compute.
• Medical and scientific imaging pipelines, given the affiliations with a health research institute and medical imaging groups, and the paper's use of an image dataset (CIFAR10) for its landscape analysis.

Industry relevance. Companies that tune neural architectures at scale benefit from a crossover operator that runs in under a second on architectures up to 71 nodes, where the previous method fails at around 20 nodes. The distance metric also lets practitioners monitor population diversity and detect whether a search is exploring or prematurely converging, which is directly useful for allocating compute budgets.

Future Directions

• Explicit control of the exploration–exploitation trade-off using the distance metric, including implementing and analysing the methods described in the paper's Appendix F.
• Component-level merit assignment using the shortest paths produced by the crossover, aiming toward discovering and reusing performant architectural blocks.
• Preserving and injecting high-performing sequences into offspring generation, or even adding them to the grammar for subsequent mutation steps, based on the element-wise addition, deletion, and substitution costs in the alignment matrices.
• Studying how these crossover mechanisms interact with more sophisticated optimisation strategies, and broadening applications beyond NAS, since the method applies to any search space representable as a sequential set of tokens.

Target Audience

Researchers and practitioners in neural architecture search who work with expressive or grammar-defined search spaces, evolutionary computation specialists interested in recombination operators for tree- and graph-structured encodings, and machine-learning engineers who need a tractable distance metric between neural architectures. Readers with a background in bioinformatics sequence alignment will find the transfer of Smith-Waterman to architecture search especially familiar. Some familiarity with context-free grammars and dynamic programming is needed to follow the complexity analysis and the metric proofs in full.

Authors’ 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.