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. )

Hover or focus to explore. Click or tap to pin; select again, press Escape, or clear to unpin.

Select an operation or a branch boundary in any view.

Clear selection

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 introduce separator tokens that delimit branches and routing modules, preserving the information needed to interpret the sequence.

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.

Alignment matrix

Inspect a cell to read its accumulated cost. Use arrow keys to move between cells, Home or End to reach the start or end of a row, and Escape to dismiss the cost label. Inspecting cells does not change the selected edit.

Select an edit

↓ InsertRetained: lowest total ↘ SubstituteRetained: lowest total → DeleteRetained: lowest total

Delete Dropout from A; the corresponding position in B is a gap. The selected move advances right in A, not B.

Accounting for branch order

The alignment still depends on the order in which we write the branches. Suppose two branches produce outputs $a$ and $b$, which are then added. Swapping their order changes the serialization, but not their sum:

$a+b=b+a.$

Their token sequences nevertheless differ, so CSWX can assign a positive edit distance to two descriptions of the same computation.

Trying every possible branch ordering would address this, but repeating the entire alignment for each combination would quickly become expensive. Our recursive extension, RCSWX, instead reuses the unaffected parts of the matrix and computes the alternatives in submatrices delimited by branching nodes.

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. )

a and b abbreviate whole branches; purple tracks the same branch a.

When a separator closes a branching block, we merge these alternatives by retaining the cheapest paths to each cell. This does not mean choosing one winning submatrix: different cells can retain paths from different alternatives. 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 one branch of a larger block. While aligning the inner block, we must account for its possible orderings as well as the still-open alternatives of the outer block. Once the inner block closes, its alternatives can be collapsed within each enclosing case. We then continue the outer alignment until its own closing separator allows those alternatives to be combined too. This is where the recursion enters: the same procedure handles a branching structure whether it appears at the top level or inside another one.

With these correspondences established, we can return to the opening explorer and choose which of the recovered edits an offspring should inherit.

Choosing the edits

Recovering an alignment tells us how to transform one parent into the other, but leaves us free to choose which changes an offspring should inherit. Rather than always applying the first few edits, we can sample different combinations from the recovered set. 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.

Among the valid combinations, we assign sampling probabilities according to their total edit cost, using a truncated Gaussian distribution. Its optional skewness parameter lets us favour combinations that produce offspring closer to one parent, rather than requiring every offspring to inherit the same number of edits.

Even combinations with the same total cost can produce different architectures. The opening slider’s single progression therefore shows only some of the available offspring; sampling reveals other ways to combine the changes without having to solve the alignment again.

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

1. • start

   1 combination

2. Open A

   • A: 1
   • A: 2

   2 combinations

3. Close A

   • continue

   1 combination

4. Open B

   • B: 1
   • B: 2

   2 combinations

5. Close B

   • continue

   1 combination

Nested blocks

1. • start

   1 combination

2. Open A

   • A: 1
   • A: 2

   2 combinations

3. Open B

   • A: 1B: 1
   • A: 1B: 2
   • A: 2B: 1
   • A: 2B: 2

   4 combinations

4. Close B

   • A: 1
   • A: 2

   2 combinations

5. Close A

   • continue

   1 combination

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

To examine how the methods behave on actual architectures, we compared their runtimes on models collected during evolutionary searches. Under the benchmark’s representation and edit costs, the edit paths returned by SEPX matched those found by RCSWX for all tested comparisons where SEPX completed. The runtime comparison therefore concerns different ways of obtaining the same transformations in that setting.

At around 15 nodes, the SEPX measurements already reach minutes or hours, while RCSWX handles much larger comparisons in a fraction of that time.

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 architectures in these examples use the grammar-based representation introduced with einspace. In our paper, we combine the alignment and offspring-generation procedures with evolutionary search, then use the resulting distance to study population diversity and the relationship between architectural differences and performance. Those applications build on the operator, but are not required to compare two parent architectures or construct offspring from their edits.

Our reimplementation is available at flxai/rcswx.