Interpolating between neural architectures

When searching for new neural architectures, we’d like to build on promising designs rather than start from scratch each time. We could build new architectures from parts of existing networks, provided we can work out how those parts fit together. In Evolutionary Architecture Search through Grammar-Based Sequence Alignment, we use sequence alignment to identify the edits connecting two architectures, then draw on those edits to construct offspring that combine elements of both.

Here, we’ll explore that idea interactively, beginning with two architectures and the designs we can build between them.

1. From one architecture to another
2. From a network to a sequence
3. Finding an alignment
4. Accounting for branch order
5. Choosing the edits
6. What the computation costs
   1. Measured runtimes
7. Beyond the operator

From one architecture to another

The slider below follows one route between the two parents, showing the intermediate designs as more of the transformation is carried out.

Carrying out every edit would reproduce the second architecture, whereas stopping along the way leaves us with a combination of the two. The slider presents these changes in a fixed progression, but crossover allows other combinations too, provided the selected edits fit together. Some changes depend on others, so we cannot simply choose each edit independently.

Before choosing which changes to make, though, we need to establish which parts of the parents correspond. An extra layer shifts the positions of everything that follows it, even when those later layers are unchanged. Comparing the networks position by position would obscure that relationship; aligning them with a gap for the insertion lets the unchanged layers line up again.

For networks with branches, we also need to preserve which operations belong together and how they connect. Our starting point is therefore a representation that records how the architecture is assembled: its derivation tree.

From a network to a sequence

While the computational graph describes the network’s operations and how data flows between them, the derivation tree records how the architecture is assembled. In the grammar used here, a module can contain smaller modules arranged in sequence or in parallel branches whose outputs are combined. Those modules can be expanded in the same way, allowing a small set of rules to describe architectures with nested structures.

Computational graph

Derivation tree

Token sequence

1. Add
2. (
3. Conv3x3
4. ReLU
5. )
6. (
7. Conv1x1
8. BatchNorm
9. )

To align two architectures, we serialize their trees into sequences of tokens. Some nodes can be omitted because their role is already implied by the structure, but flattening the tree would lose information unless we also recorded its boundaries. We therefore use separator tokens to preserve the boundaries of branches and routing modules. A routing module wraps an inner module with transformations applied to its input and output.

These separators become important when we start editing. A change to a branching node has to agree with the changes made to its corresponding separators; otherwise, the resulting sequence could describe an incomplete or inconsistent structure. Our alignment therefore considers both the cost of a proposed edit and whether it is compatible with the structural decisions made along the path so far.

Finding an alignment

With the first parent’s sequence across the columns of a matrix and the second’s down its rows, each position marks how far we have progressed through both sequences. Moving right deletes a token from the first parent, moving down inserts one from the second, and moving diagonally matches or substitutes the two. Different routes through this matrix therefore describe different ways of transforming the first parent into the second.

Rather than enumerate every route, we build the alignment incrementally. At each cell, we consider extending paths from the left, above, and upper left, adding the cost of each move to the corresponding path’s accumulated cost. We discard extensions that violate the structural constraints and retain the cheapest remaining paths. When several paths are equally cheap, we keep them because their earlier edits can affect which later moves are valid. The cell therefore records the cost of reaching that position, not merely the cost of comparing its two tokens. This is the dynamic-programming procedure underlying our Constrained Smith-Waterman crossover, or CSWX. Not every change needs to count equally. Adjusting a layer’s settings can cost less than replacing it, while changes that violate the grammar are ruled out altogether.

By the bottom-right corner, both sequences have been accounted for. Following the recorded choices backwards recovers the edits connecting the parents, while the accumulated cost gives their edit distance. We can then map those edits back onto the architectures to see which components correspond and where changes are needed.

Accounting for branch order

The alignment still depends on the order in which we write the branches. When their outputs are added, swapping the branches leaves the computation unchanged. CSWX can nevertheless assign a positive edit distance because the token sequences differ.

Ordered derivation trees

S₁

↔same sum

S₂

Different token sequences

S₁

1. Add
2. (
3. a
4. )
5. (
6. b
7. )

S₂

1. Add
2. (
3. b
4. )
5. (
6. a
7. )

Trying every permitted branch ordering would address this, but repeating the entire alignment for each combination would redo much of the same work. Our recursive extension, RCSWX, instead reuses the unaffected parts of the matrix and computes alternative orderings within submatrices delimited by branching nodes.

When a separator closes a branching block, we merge these alternatives by retaining the cheapest paths to each cell. Different cells can retain paths from different branch orderings. The corresponding path information is retained alongside the costs, so we can still recover the decisions that produced the final alignment.

Consider a branching block nested inside another. For each ordering of the outer block, we compare the inner block’s possible orderings. When the inner block closes, we merge its alternatives separately for each outer ordering. We then continue the outer alignment and merge its alternatives when it closes. The same procedure applies at every level of nesting.

Choosing the edits

Rather than following the slider’s fixed progression, we can sample compatible combinations of recovered edits. This is also the idea behind Shortest Edit Path Crossover (SEPX), which randomly selects roughly half the edits from a shortest path between the parent graphs.

In our grammar-based representation, some of these choices depend on one another. Deleting all operations inside a routing module, for instance, would leave it empty unless another edit adds content or removes the enclosing module as well. We record these dependencies when recovering the edits, then use them to exclude incompatible combinations before sampling.

We sample compatible edit combinations according to their total edit cost, using a truncated skew-normal distribution. At zero skewness, this reduces to a truncated Gaussian. Adjusting the skewness lets us favour offspring closer to either parent.

Even combinations with the same total cost can produce different architectures.

What the computation costs

Reusing the unaffected parts of an alignment avoids a great deal of repeated work, but it does not make every comparison equally easy. Longer token sequences enlarge the matrix, while nested branching structures increase the number of alternatives that must be considered within parts of it. For binary branch-order choices, we describe the following scaling of the alignment computation in our paper.

Alignment strategy	Scaling
CSWX: compute one ordered alignment	$O(n_1n_2)$
Enumerate all branch orderings and repeat the complete alignment	$O(n_1n_2\,2^b)$
RCSWX: compute and collapse alternatives locally	$O\!\left(\displaystyle\sum_{i=1}^{n_1}\sum_{j=1}^{n_2}2^{d_{ij}}\right)$

Here, $n_1$ and $n_2$ are the sequence lengths, $b$ counts the binary branching choices across both parents, and $d_{ij}$ counts those simultaneously open at a particular matrix position. Repeating CSWX recalculates the whole matrix for every combination of branch orderings. RCSWX instead reuses unaffected regions and evaluates the alternatives locally.

Separate blocks

At most 2 alternatives

Nested blocks

At most 4 alternatives

Alignment progress →↓

Several branching blocks arranged in sequence can be resolved one after another. Nesting them keeps more alternatives open at the same time, multiplying the work within the affected regions. RCSWX consequently retains an exponential worst case for deeply nested architectures, even though it avoids the global enumeration of every branch-order combination.

These expressions describe the alignment, not every part of producing an offspring. The sampling procedure also has to consider compatible combinations of recovered edits, so its work can grow with the number of edits available. Where similar parents yield fewer edits, this stage may become cheaper without a corresponding reduction in the size of the alignment matrix.

Measured runtimes

We timed SEPX and RCSWX on architectures collected during evolutionary searches. Using the same representation and edit costs, both methods found the same edit paths in every comparison that SEPX completed.

SEPX becomes expensive while the architectures are still small: at around 15 nodes, comparisons already take hours. RCSWX extends the same edit-path approach to substantially larger architectures.

To complement the measurements on search-generated architectures, we also compared ResNets with MLP-Mixers. Here, some pairs with larger edit distances were faster to align than pairs with smaller distances, so similarity alone cannot explain the timings. Finding a transformation involves considering alternatives, and the way we retain and check those paths contributes to the computational cost.

Beyond the operator

The same alignment that lets us construct offspring also gives us a distance between architectures. That lets us ask broader questions: how diverse is a search population, and how closely do changes in architecture track changes in performance? Our paper explores these questions alongside evolutionary search in the grammar-based space introduced by einspace.

For the full method and experimental results, see our paper on arXiv. Our reimplementation is available on GitHub.