# Neural Architecture Search using Property Guided Synthesis

Charles Jin  CSAILMITCambridgeMAUS<EMAIL_ADDRESS>,  Phitchaya Mangpo
Phothilimthana  Google ResearchGoogleMountain ViewCAUS<EMAIL_ADDRESS>and
Sudip Roy  CoherePalo AltoCAUS

(2022)

###### Abstract.

Neural architecture search (NAS) has become an increasingly important tool
within the deep learning community in recent years, yielding many practical
advancements in the design of deep neural network architectures. However, most
existing approaches operate within highly structured design spaces, and hence
(1) explore only a small fraction of the full search space of neural
architectures while also (2) requiring significant manual effort from domain
experts. In this work, we develop techniques that enable efficient NAS in a
significantly larger design space. In particular, we propose to perform NAS in
an abstract search space of program properties. Our key insights are as
follows: (1) an abstract search space can be significantly smaller than the
original search space, and (2) architectures with similar program properties
should also have similar performance; thus, we can search more efficiently in
the abstract search space. To enable this approach, we also introduce a novel
efficient synthesis procedure, which performs the role of concretizing a set
of promising program properties into a satisfying neural architecture. We
implement our approach, $\alpha$NAS, within an evolutionary framework, where
the mutations are guided by the program properties. Starting with a ResNet-34
model, $\alpha$NAS produces a model with slightly improved accuracy on
CIFAR-10 but 96% fewer parameters. On ImageNet, $\alpha$NAS is able to improve
over Vision Transformer (30% fewer FLOPS and parameters), ResNet-50 (23% fewer
FLOPS, 14% fewer parameters), and EfficientNet (7% fewer FLOPS and parameters)
without any degradation in accuracy.

Neural Architecture Search, Program Synthesis, Abstract Interpretation

††copyright: rightsretained††doi: 10.1145/3563329††journalyear:
2022††submissionid: oopslab22main-p383-p††journal: PACMPL††journalvolume:
6††journalnumber: OOPSLA2††article: 166††publicationmonth: 10††ccs: Software
and its engineering Search-based software engineering††ccs: Computing
methodologies Neural networks

##  1\. Introduction

Neural architecture search (NAS) is a class of techniques that aims to
automate the process of designing neural network architectures (Zoph and Le,
2017). Specifically, rather than relying on fully hand-designed neural
architectures, which is time-consuming and subject to human biases and
failures, NAS proposes to automatically search for neural architectures within
a search space. These approaches have yielded significant improvements in both
raw accuracy and navigating the trade-off with other metrics of practical
interest such as parameter count and latency.

Despite many recent successes, however, the general NAS problem presents many
key technical challenges that have yet to be fully addressed. First, the
search space of deep neural networks is prohibitively large. Even if the high-
level structure of a network is fixed, one still needs to select between
operation variants (e.g., various types of convolutions) and parameter
settings (e.g., filter sizes, layer widths, layer depths). Second, good
architectures are extremely sparse, i.e., a randomly constructed network is
unlikely to perform well. Finally, evaluating candidate architectures is also
computationally expensive, as evaluation generally involves training the
proposed network to convergence on a target dataset from scratch.

To contend with these challenges, most existing approaches are specialized for
highly structured search spaces. For instance, a common strategy is to first
manually specify a fixed architecture, then use NAS to tune selected
parameters of the operators (e.g., depths and filter sizes) (Tan and Le, 2019,
2021; Zoph et al., 2018; Liu et al., 2018a, b; He et al., 2018; Li et al.,
2020). It has been observed that such restricted search spaces also tend to
bypass the second challenge, i.e., even randomly selected networks perform
quite well (Li and Talwalkar, 2020; Yu et al., 2019; Bender et al., 2020).

However, imposing such structure comes at a direct cost of the expressiveness
of the search space, and generalizing prior approaches to unstructured search
space is an open problem. Indeed, while existing approaches have delivered
impressive results when used to tune existing architectures, to date, major
architectural changes (AlexNet (Krizhevsky et al., 2012), ResNet (He et al.,
2016), Transformers (Vaswani et al., 2017), etc.) have still been driven by
the insight of human researchers.

More recently, several new approaches to NAS have been proposed that avoid the
need to define a highly structured search space by iteratively mutating a
randomly selected subgraph inside a neural network architecture, using an
evolutionary search mechanism (Real et al., 2019, 2020; So et al., 2021).
Given the number of possible operations, each with different functional and
performance characteristics, directly generating a random subgraph is unlikely
to perform well in place of the original subgraph. To counteract this, prior
approaches limit the scope of their mutations to only small changes. For
instance, Primer (So et al., 2021) uses mutations such as changing a single
parameter in a random operation, or swapping two nearby operations. However,
restricting the mutations to small changes requires many iterations to
discover high-quality, novel architectures, and in many cases, the search may
struggle to escape local minima.

###  1.1. Our Approach

In this work, we present a new evolutionary approach to NAS. Prior methods
evolve new architectures by applying small stochastic mutations directly on
the computation graphs of deep neural networks. Each such mutation produces a
new architecture, which is evaluated for accuracy, then inserted into the
population as a potential starting point for future mutations.

In contrast, our approach is able to progress through the search space
significantly faster by making high-quality, substantial changes to the
architecture in each mutation step. To achieve this, we propose to perform the
mutations in an _abstract space of program properties_. We identify the
following objectives that guide the design of our program properties:

  1. (1)

By mapping multiple concrete architectures to the same set of program
properties, the abstract search space can be significantly smaller in size
than the original search space.

  2. (2)

Architectures that have similar program properties should also have similar
performance. This enables search algorithms which rely on an assumption of
locality in the search space (e.g, hill-climbing or evolutionary algorithms)
to be applied to the unstructured search space.

Our approach, named $\alpha$NAS, begins by selecting a random subgraph of the
computation graph for mutation. Then, we infer a set of program properties for
the selected subgraph, and apply stochastic mutations on the properties of the
subgraph. Finally, we synthesize a new subgraph that satisfies the mutated
properties, and insert the new subgraph in place of the old subgraph to
produce a new architecture.

Figure 1. Our approach proposes a new neural network architecture by (1)
randomly selecting a subgraph of an existing architecture, (2) inferring
program properties of the subgraph, (3) mutating the program properties, and
(4) synthesizing a new subgraph that satisfies the mutated program properties.
We apply these four steps iteratively. This particular mutation is found
during our ImageNet experiment when starting from a Vision Transformer
architecture. A descendant of this model (consisting of 4 total mutations)
ultimately decreases FLOPS and parameter count by 28% and 30% respectively,
while slightly increasing accuracy.

Fig. 1 illustrates an example of a mutation synthesized by $\alpha$NAS during
the evolution of the Vision Transformer architecture (Dosovitskiy et al.,
2021) for image classification. To perform this mutation, we first select a
random subgraph from the computation graph of the _parent_ architecture (step
1, Fig. 1; the selected subgraph is enclosed in a gray box). Next, we abstract
the subgraph into a set of _program properties_ (step 2, Fig. 1). Since deep
neural network graphs can be computationally expensive to execute, one crucial
requirement is that our properties can be inferred _statically_ , that is,
without executing the computations on real data. Of course, it is also
important that the abstract properties capture semantically relevant
information about the underlying computation. For instance, our most basic
property is the _depth_ of the subgraph in terms of the number of alternating
linear and nonlinear layers; here, the selected subgraph has a depth of 3.

We then apply stochastic mutations at the level of abstract program properties
to obtain new program properties (step 3, Fig. 1; the mutated depth property
is marked by a red box). The mutated properties are concretized back into a
subgraph (step 4, Fig. 1). Finally, the new subgraph is inserted in place of
the original subgraph (marked by the green box), yielding a new, mutated
architecture (called a _child_), which is ready to be evaluated and added to
the population for the next round of evolution. Note that our search space
contains over 1402 possible operations for each node. To satisfy the new depth
property of 4, the synthesized subgraph must contain at least 4 operations,
yielding _over 3.8 billion legal subgraphs_. In order to perform the
concretization efficiently, in Section 4 we propose a novel program synthesis
algorithm. Using our techniques, synthesizing the subgraph in Fig. 1 (with 5
nodes) took only 88 seconds—a fraction of the time needed to evaluate the
resulting architecture (which involves training the model on a dataset).

The mutation displayed in Fig. 1 is ultimately a part of the 278th individual
(evolved using 4 total mutations) that improves the baseline architecture by
decreasing FLOPS by 28% and parameter count by 30%, while slightly increasing
accuracy. Note that this single mutation is equivalent to 8 steps in the
concrete space using previous techniques like Primer. Hence, the primary
benefit of our approach is that a single mutation in the abstract space can
result in a new architecture that would otherwise require many individual
concrete mutations to achieve. Intuitively, by requiring the synthesized
subgraph to satisfy similar properties to the original subgraph, our search is
biased toward high quality replacements. By enabling larger mutations, our
method is able to explore new architectures far more quickly, and requires
substantially fewer iterations of evolutionary search compare to prior
approaches; in our experiments, we only require evolving 800 individuals to
produce a population of novel, high quality architectures for image
classification on the ImageNet dataset, whereas Primer evolves nearly 25,000
individuals on the task of language modeling.

###  1.2. Our Contributions

Our first contribution is a set of program properties defined over arbitrary
neural architectures, which constitute the abstract search space in which the
search is performed. In particular, we introduce the _shape_ , _depth_ , and
_mixing_ properties for neural networks in Section 3. We also describe
efficient algorithms for inferring these program properties; crucially, we
infer these properties statically, which enables the inference to occur
exclusively on a CPU host, decoupling the costly evaluation process from the
rest of the search procedure.

Our second contribution is an efficient synthesis procedure, which accepts a
set of program properties and returns a satisfying neural architecture. In
general, inverting an abstraction function is nontrivial; in the worst case,
the only technique which is guaranteed to succeed is a brute-force search that
enumerates all possible architectures and returns the first satisfying
architecture. However, by carefully crafting our synthesis procedure to
leverage a notion of distance to the program properties, our procedure is able
to synthesize a satisfying architecture exponentially faster than the naïve
enumerative strategy.

To empirically validate our approach, we implement our techniques within a
basic evolutionary search and evaluate performance on image classification
tasks.111Code is available at https://github.com/google-research/google-
research/tree/master/abstract_nas. Starting with a ResNet-34 model on the
CIFAR-10 dataset, $\alpha$NAS produces a model with slightly improved accuracy
but 96% fewer parameters. On the ImageNet dataset, $\alpha$NAS is able to
improve over Vision Transformer (30% fewer FLOPS and parameters), ResNet-50
(23% fewer FLOPS, 14% fewer parameters), and EfficientNet (7% fewer FLOPS and
parameters) without any degradation in accuracy. When compared against the
current state-of-the-art search mechanisms from Primer (So et al., 2021) and
AutoML-Zero (Real et al., 2020), $\alpha$NAS discovers significantly more
Pareto optimal models.

##  2\. Problem Formulation

This section begins with a brief introduction of deep neural network
architectures, then describes how we formulate the problem of searching for
new neural architectures as a program synthesis task by treating deep neural
networks as programs. The remaining subsections formalize the setting for our
synthesis algorithm.

###  2.1. Deep Neural Network Architectures

Figure 2. A toy example of a convolutional neural network architecture for
image classification. The final architecture (right) is composed of two
different types of blocks (left, middle), with repetitions annotated on the
far right. Not shown is the classification head, which projects the “Output
(pre-logits)” through a fully-connected layer to the number of classes
followed by a softmax layer, yielding the final class probabilities.

Deep neural networks (DNNs) are a family of models composed of layers of
artificial neurons. Here we describe the most basic architecture, a simple
feedforward multilayer perceptron (MLP). The input to the first layer is often
some sensory data, such as an image; for subsequent layers, the inputs are the
outputs of the neurons in the previous layer. Each neuron first computes a
weighted combination of its inputs, where the weights are learnable
parameters. The result is then passed through an element-wise nonlinearity,
called an activation function; this becomes the output of the neuron, to be
consumed by the next layer. The output of the final layer of neurons is the
output of the neural network. Such an architecture is “deep” when it contains
many layers alternating linear functions with nonlinear activations. Each
layer is differentiable, so the entire network is trainable using gradient
descent via the back-propagation algorithm. Depending on the problem domain,
some common variations include selecting different nonlinearities,
constraining the inputs of a neuron to a subset of the previous layer (e.g.,
convolutional neural networks, which use convolutions), or supporting
additional types of operations (e.g., normalization layers).

##### Representing DNNs

Since each neuron in a layer has the same functional form, we can concisely
represent each layer of an MLP as a sequence of operations (e.g., a dense
linear layer followed by a sigmoid activation); the complete architecture is
represented by the full sequence of operations over every layer. Additionally,
modern deep neural network architectures are often composed of repeated
blocks, where each block consists of a fixed sequence of operations. These
blocks are then stacked in sequence to produce the final architecture. Fig. 2
displays a toy example of a convolutional neural network architecture,
composed of several repeated blocks. More generally, we can represent more
complex (i.e., nonfeedforward) architectures as a computation graph, where
nodes are operations and the directed edges represent dataflow relationships
(cf. Fig. 13).

##### From Neural Architecture Search to Program Synthesis

NAS is the problem of automatically searching for novel neural architectures,
given some performance objectives. For instance, we may want to search for CNN
architectures that maximize accuracy on the CIFAR-10 dataset. By representing
neural architectures as computation graphs, this paper casts the problem of
neural architecture search as a program synthesis task. More specifically, we
treat computation graphs as programs, and perform the search by synthesizing
new programs. The remainder of this section presents a formal setting for
synthesis based on _program properties_. In Section 3, we propose program
properties that can be leveraged to guide the synthesis procedure toward
architectures with better performance, thereby enabling us to apply program
synthesis techniques to NAS.

###  2.2. Program Properties

Program properties form the basis of our synthesis problem. We denote the
arbitrary, fixed space of programs as $\mathcal{P}$.

###### Definition 2.1.

A program property $\Pi=(\mathcal{V},\leq,\alpha)$ over the space of programs
$\mathcal{P}$ consists of a set $\mathcal{V}$ of _program property values_ ,
with a partial order relation $\leq$ over $\mathcal{V}$, and an _abstraction
function_ $\alpha:\mathcal{P}\mapsto\mathcal{V}$ that maps programs to
property values.

###### Definition 2.2.

A program $p\in\mathcal{P}$ satisfies a program property value
$v\in\mathcal{V}$, denoted $p\models v$, if $\alpha(p)\geq v$.

For instance, the previous section introduces a depth property for deep neural
networks. This property takes values $\mathcal{V}$ in the nonnegative
integers, where $\leq$ is the usual relation on integers, and $\alpha$ maps a
subgraph to its depth. For a feedforward neural network, the depth is simply
the number of alternating linear and nonlinear operators in the network, and a
subgraph satisfies the depth program property value $d$ if its depth is at
least $d$.

We can immediately generalize this definition to a setting where we are given
a set of program properties
$\mathbb{P}=\\{\Pi_{i}=(\mathcal{V}_{i},\leq_{i},\alpha_{i})\\}_{i=1}^{N}$:

###### Definition 2.3.

A program $p\in\mathcal{P}$ satisfies a set of program property values
$S=\\{v_{i}\,|\,v_{i}\in\mathcal{V}_{i}\\}_{i=1}^{N}$, denoted $p\models S$,
if for every $v_{i}\in S$, we have that $p\models v_{i}$.

We usually drop the subscript $i$ of the partial ordering $\leq_{i}$ when it
is clear from context.

###  2.3. Program Synthesis

Program transformations are the basic unit of our synthesis algorithm. We
formalize the task of program synthesis as the problem of producing a sequence
of transformations that transforms some initial program $p_{0}$ into a program
$p^{*}$ satisfying the desired program properties $S$.

###### Definition 2.4.

A program transformation $t\in\mathcal{T}:\mathcal{P}\mapsto\mathcal{P}$ is a
map from programs to programs.

###### Definition 2.5.

The synthesis task $(p_{0},v)$ is feasible if there exists some sequence
$t_{1},\ldots,t_{n}\in\mathcal{T}$ such that $(t_{n}\circ\cdots\circ
t_{1})(p_{0})\models S$.

In this work, we will always take the initial program $p_{0}$ to be the
identity program: $\text{id}(x)=x$ for all inputs $x$. We will also assume
that $\mathcal{T}$ is freely generated (via composition) by a known, finite
set $E$ of primitive transformations, i.e., $\mathcal{T}=E^{*}$. For
synthesizing subgraphs of deep neural networks, the primitive transformations
$E$ consist of appending one of the basic operations to the partial subgraph.
Given any set of program properties values $S$, our synthesizer incrementally
appends operations _without backtracking_ , until the resulting program
satisfies the given properties. The key to ensuring progress is defining an
appropriate notion of _distance_ from programs to the desired property, such
that we can always decrease the distance by selecting a transformation from a
small fixed subset $T\subset\mathcal{T}$. Hence, each step of the synthesis
algorithm simply enumerates over the transformations in $T$, and selects a
transformation that is guaranteed to decrease the distance. This process is
repeated until the subgraph achieves a distance of 0, satisfying the target
property.

For instance, to satisfy the depth property in Fig. 1, we can simply alternate
between appending linear and nonlinear operations. Clearly, this strategy can
always increase the depth of the subgraph until the property is satisfied. Our
main insight is that this seemingly simple procedure also applies to program
properties with more complex semantics. As each step of synthesis
progressively brings the program closer to satisfying the property, we call
our technique progressive program synthesis. Crucially, the runtime of this
algorithm is _linear_ in the length of the synthesized subgraph, whereas the
number of possible subgraphs is _exponential_ in the length.

###  2.4. Property Inference

$\alpha$NAS performs property inference ($\alpha$) during the abstraction and
synthesis phases (steps 2 and 4 in Fig. 1, respectively). During abstraction,
we infer the properties of the selected subgraph only once. During synthesis,
however, our algorithm relies on inferring the properties of each partially
synthesized program after applying some transformation $t$.

To infer program properties efficiently, we extend the semantics of $\alpha$
from programs $p\in\mathcal{P}$ to transformations $t\in\mathcal{T}$. The idea
is that if we already know $\alpha(p)=v$, instead of computing $\alpha(t(p))$
from scratch, we can leverage the partial result $v$ and compute the effects
of $t$ on $v$ abstractly. We formalize this intuition using the theory of
_abstract interpretation_ for transformations. In particular, when computing
the effects of a program transformation $t\in\mathcal{T}$ on a program
property value $v$, we need to preserve the soundness of the $\models$
relationship in the following sense:

###### Definition 2.6.

Given a program property $\Pi=(\mathcal{V},\leq,\alpha)$, an abstract
interpretation of a program transformation $t\in\mathcal{T}$ is a map
$t^{\alpha}:\mathcal{V}\mapsto\mathcal{V}$ such that $t^{\alpha}(u)=v$ implies
$\forall p\models u$, $t(p)\models v$.

Henceforth, we use the superscript $\alpha$ to identify transformations $t$
over concrete subgraphs with an abstract interpretation $t^{\alpha}$ over
program properties. Fig. 3 illustrates the key soundness property of abstract
interpretation as a commutative diagram.

Figure 3. The key soundness property of abstract interpretation:
$t^{\alpha}(u)=v$ implies that $\forall p\models u$, $t(p)\models v$.
Superscript $\alpha$ denotes the abstract interpretation of transformation $t$
with respect to a program property $\Pi$.

##  3\. Program Properties for Neural Architecture Search

In this section, we present the set of program properties used by $\alpha$NAS
to guide the neural architecture search. Before identifying the specific
properties, we first elaborate on our main considerations in defining such
properties for NAS.

As outlined in Section 1.1, a key step in evolutionary NAS is how
architectures are mutated over the course of the search. Thus, it is essential
to generate mutations that, on expectation, yield a better child
architectures. Since our approach involves inferring the properties of the
original subgraph, mutating these properties, then synthesizing a new subgraph
from the mutated properties, choosing the right set of properties is critical.

Specifically, our objectives in designing the program properties are
threefold:

  1. (1)

The abstract space is smaller because multiple concrete architectures are
mapped to a single set of properties. However, the abstraction function should
also be well-aligned with our search objective, i.e., architectures that are
mapped to the same point in the abstract space should have similar performance
characteristics.

  2. (2)

Since each point in abstract space represents multiple concrete architectures,
small steps in the abstract space represent large steps in the original
concrete space; but for the abstraction to be useful, we want small changes in
the abstract space to preserve at least some of the performance
characteristics in the concrete space—otherwise, there is no structure for the
search mechanism to leverage.

  3. (3)

Since the substitution step involves both inferring program properties for a
candidate subgraph, and synthesizing an alternate subgraph based on mutated
properties, both of these steps must be computationally efficient.

In particular, the first two points are desiderata that relate the program
properties to the semantics of deep neural network architectures. To this end,
we propose the following characterization of what constitutes a deep neural
network:

###### Definition 3.1.

A deep neural network is a function containing alternating layers of linear
and nonlinear functions.

The linear functions include layers such as convolutional, dense, and fully-
connected layers, while the nonlinear functions consist of activation
functions such as ReLU, sigmoid or tanh. This description sufficiently
captures the simplest type of deep neural network: the feedforward MLP. It
follows that any abstract search space for DNNs should be expressive enough to
capture this key characteristic. For instance, our properties should be able
rule out the following degenerate architectures, which are valid programs in
our search space, but do not satisfy the basic definition above:

  1. (1)

a sequence of activation functions, without any linear layers in between;

  2. (2)

a sequence of linear layers, without any activations in between;

  3. (3)

an alternating sequence of pooling layers and activation functions.

Note that the last example technically consists of alternating layers of
linear and nonlinear functions, but lacks expressivity from a functional
perspective, as it has no trainable parameters and therefore can be used to
represent only a very restricted class of functions. This motivates our
approach, which is to capture this characterization from the perspective of
mathematical functions. In the remainder of this section, we describe formally
the subgraph properties we propose in this work, as well as the associated
efficient inference algorithms based on abstract interpretation. For clarity
of presentation, we assume that the subgraphs have only a single input and
output; to generalize our definitions to subgraphs with multiple inputs or
multiple outputs, we simply compute the property for every input-output pair.

###  3.1. Mixing Property

The mixing property captures key information about the expressivity of a
subgraph _as a linear operator_. Intuitively, if a subgraph consists purely of
linear operators (and hence is linear as a whole), then each element of the
output is a linear combination of elements in the input; the mixing property
summarizes information about which elements of the input have nonzero
coefficients in the linear combination.

##### An example.

Consider a 3 $\times$ 3 convolutional layer:

(1) $\displaystyle
O[b,c_{o},w_{o},h_{o}]=\sum_{c_{i}=0}^{C_{i}}\sum_{k_{h}=-1}^{1}\sum_{k_{w}=-1}^{1}I[b,c_{i},w_{o}+k_{w},h_{o}+k_{h}]*K[c_{o},c_{i},k_{w}+1,k_{h}+1]$

and a dense layer:

(2) $\displaystyle
O[b,c_{o},w_{o},h_{o}]=\sum_{c_{i}=0}^{C_{i}}I[b,c_{i},w_{o},h_{o}]*W[c_{o},c_{i}]$

where $O$ is the output tensor, $I$ is the input tensor, $K$ is the kernel of
the convolution, and $W$ is the weight matrix of the dense layer.

Intuitively, we want to capture the fact that the 3 $\times$ 3 convolutional
layer is strictly more expressive than a dense layer, since the dense layer is
just a special case of the 3 $\times$ 3 convolution where only the middle
element of the convolutional filter is nonzero, i.e., any dense layer can be
written as a convolutional layer (but not vice-versa). Another way to express
this observation is that every output element of a convolutional layer depends
on a full slice of the input channel dimension, as well as _many_ elements of
the input spatial dimensions; however every output element of a dense layer
depends on a full slice of the input channel dimension, but only a _single_
element of the input spatial dimension. Similarly, fully connected layers are
strictly more expressive than both convolutional and dense layers. We
formalize these intuitions in the mixing property, which is composed of two
subproperties.

####  3.1.1. Pairing subproperty

The pairing subproperty captures coarse-grained information about which
_dimensions_ of the input tensor contribute to which _dimensions_ of the
output tensor. For instance, consider a convolutional layer applied to an
input with two spatial dimensions and one channel dimension (e.g., a standard
2D image with three color channels). Then the channel dimension of the output
depends on the channel dimension of the input; however, the channel dimension
of the output does not depend on the spatial dimensions of the input, because
the convolutional kernel has a limited receptive field in the spatial
dimensions.

(a) Pairing dimensions. Top: the input dimension C is paired with the output
dimension C. Bottom: the input dimensions C and H dimensions get paired with
the output dimension H.

(b) Locality. The input dimension C has all-to-one locality with the paired
output dimensions. The input dimensions H and W have many-to-one localities
with the paired output dimensions.

Figure 4. Determining the mixing property of a 3 $\times$ 3 convolutional
layer when applied to a 2D image (H x W) with a channel (C) dimension.

More explicitly, given an input tensor and an output tensor, we say the
operation pairs a dimension of the input and a dimension of the output if,
given a fixed slice of the output along the output dimension, there is at
least one element for each position in the input dimension which contributes
to the computation of the output slice.

The formal definition is as follows. Let $f$ be a tensor-valued function which
maps an input tensor $A$ of size $(a_{1},\ldots,a_{n})$ to an output tensor
$B$ of size $(b_{1},\ldots,b_{m})$. In other words, for any element
$B[o_{1},\ldots,o_{m}]$, where $1\leq o_{k}\leq b_{k}$ for all $1\leq k\leq
m$, we have a real-valued function $f_{o_{1},\ldots,o_{m}}$ over
$n$-dimensional tensor inputs $A$ such that

(3) $\displaystyle B[o_{1},\ldots,o_{m}]=f_{o_{1},\ldots,o_{m}}(A)$

###### Definition 3.2.

An element $A[i_{1},\ldots,i_{n}]$ (where $1\leq i_{k}\leq a_{k}$ for all
$1\leq k\leq n$) of the input tensor contributes to the computation of the
element $B[o_{1},\ldots,o_{m}]$ of the output tensor if

(4) $\displaystyle\dfrac{\partial f_{o_{1},\ldots,o_{m}}}{\partial
A[i_{1},\ldots,i_{n}]}(A)\neq 0$

i.e., the partial derivative _as a function_ of $A$ is not identically zero.

Note that if $f$ is a linear function, then the formula for
$B[o_{1},\ldots,o_{m}]$ can be expressed as a linear combination over the
elements of $A$, and the partial derivative of $f_{o_{1},\ldots,o_{m}}$ with
respect to $A[i_{1},\ldots,i_{n}]$ is just the coefficient of
$A[i_{1},\ldots,i_{n}]$ in the linear combination.

###### Definition 3.3.

The preimage of the function $f$, denoted as $f^{-1}$, is a map from sets of
output elements to sets of input elements, and is defined as follows. Let
$S=\\{B[o_{1,j},\ldots,o_{m,j}]\\}_{j\in J}$ be a set of output elements,
indexed by the set $J$. If $S$ consists of a single element
$B[o_{1},\ldots,o_{m}]$, then $f^{-1}(S)$ is the set of all input elements
that contribute to the computation of $B[o_{1},\ldots,o_{m}]$. Otherwise,

(5) $\displaystyle f^{-1}(S)=\bigcup_{j\in
J}f^{-1}(\\{B[o_{1,j},\ldots,o_{m,j}]\\})$

###### Definition 3.4.

Given a tensor $B$ of shape $(b_{1},\ldots,b_{m})$, a slice along the $k^{th}$
dimension, specified by $m-1$ indices
$\\{o_{1},\ldots,o_{k-1},o_{k+1},\ldots,o_{m}\\}$, is the set of elements

(6) $\displaystyle
B[o_{1},\ldots,o_{k-1},\bullet,o_{k+1},\ldots,o_{m}]=\bigcup_{o=1}^{b_{k}}B[o_{1},\ldots,o_{k-1},o,o_{k+1},\ldots,o_{m}]$

###### Definition 3.5.

The function $f$ pairs the $l^{th}$ dimension of the input tensor $A$ with the
$k^{th}$ dimension of the output tensor $B$ if there exists a slice $S_{B}$ of
the output tensor along the $k^{th}$ dimension such that the preimage $f^{-1}$
of $S_{B}$ contains one element in every position along the $l^{th}$ dimension
of the input, i.e., for every $1\leq i\leq a_{l}$, there exists
$i_{1},\ldots,i_{l-1},i_{l+1},\ldots,i_{n}$ such that
$A[i_{1},\ldots,i_{l-1},i,i_{l+1},\ldots,i_{n}]\in f^{-1}(S_{B})$.

Fig. 4(a) illustrates how the pairing subproperty of a convolutional layer is
determined for a standard 2D image with an additional channel dimension. We
can collect the pairing property over all pairs of input and output dimensions
into a matrix in the manner of Fig. 5(a), which summarizes the complete
pairing subproperty of a convolutional layer for a batch of 2D images.

|  | In
---|---|---
|  |  B |  H |  W |  C
Out |  B |  1 |  0 |  0 |  1
H |  0 |  1 |  0 |  1
W |  0 |  0 |  1 |  1
C |  0 |  0 |  0 |  1
(a) Pairing. “1” indicates a pairing and “0” indicates no pairing. For
instance, the output batch dimension is paired with the input channel
dimension.

|  | In
---|---|---
|  |  B |  H |  W |  C
Out |  B |  o |  x |  x |  a
H |  x |  m |  x |  a
W |  x |  x |  m |  a
C |  x |  x |  x |  a
(b) Locality + pairing. The entries are all-to-one (a), many-to-one (m), and
one-to-one (o) locality, or no pairing (x). For instance, the output H
dimension depends on the input H dimension with m locality.

Figure 5. Matrices representing the mixing property of a 3 $\times$ 3
convolutional layer with a batch dimension (B).

####  3.1.2. Locality subproperty

Consider again a dense layer versus a convolutional layer. The convolutional
layer has the same pairing subproperty as the dense layer. The locality
subproperty captures a more fine-grained notion of the contributing elements
which distinguishes the two operation types. In particular, the pairing
subproperty considers the preimage of _slices_ to capture the relationships
_between_ input and output dimensions, whereas the locality subproperty uses
the preimage of a single _element_ of the output to determine relationships
_within_ input dimensions.

We distinguish between all-to-one, many-to-one, and one-to-one localities. For
instance, a dense layer has a one-to-one locality within the spatial
dimensions and an all-to-one locality within the channel dimensions, while a
convolution has a many-to-one locality within the spatial dimensions and an
all-to-one locality within the channel dimensions. We have the following
formal definition:

###### Definition 3.6.

The locality of a function $f$ with respect to the $k^{th}$ dimension of the
input is:

  1. (1)

all-to-one, if there exists an element indexed by $\\{o_{1},\ldots,o_{m}\\}$
of the output tensor $B$ whose preimage
$S_{A}=f^{-1}(\\{B[o_{1},\ldots,o_{m}]\\})$ contains one element in every
position along the $k^{th}$ dimension of the input tensor, i.e., for every
$1\leq i\leq a_{k}$, there exists indices
$i_{1},\ldots,i_{k-1},i_{k+1},\ldots,i_{n}$ such that
$A[i_{1},\ldots,i_{k-1},i,i_{k+1},\ldots,i_{n}]\in S_{A}$;

  2. (2)

many-to-one, if $f$ is not all-to-one and there exists an output element whose
preimage contains elements in _more than one_ positions along the $k^{th}$
dimension of the input tensor;

  3. (3)

one-to-one, if every element of the output tensor has a preimage that contains
elements in _exactly one_ position along the $k^{th}$ dimension of the input
tensor.

Clearly, any (non-constant) input dimension is exactly one of all-to-one (a),
many-to-one (m), or one-to-one (o). Fig. 4(b) illustrates how the locality
subproperty of a convolutional layer is determined. For a given operation, the
locality subproperty is computed for each dimension of the input.

####  3.1.3. Mixing property

Similar to the pairing subproperty, we represent the full mixing property as a
matrix. However, we replace the paired entries (“1”) with the locality (o, m,
a) of the corresponding input dimension; entries which are not paired (“0”)
are replaced by the additional symbol x. Fig. 5(b) displays the full mixing
property of a convolutional layer (with an additional batch dimension); a
dense layer would have the same matrix, except the many-to-one entries in the
spatial dimensions would be replaced by one-to-one entries. Notice that this
representation does indeed capture both the pairing and locality
subproperties; we chose this representation to simplify the abstract
interpretation of the mixing property given by Lemma 3.7.

We define the following partial order $\leq$ on the mixing property: $P\leq Q$
if and only if (1) $P$ and $Q$ have the same number of input and output
dimensions and (2) $P\leq Q$ element-wise on all input-output pairs, where x ¡
o ¡ m ¡ a. The partial order succinctly captures the desired relationship
between dense, convolutional, and fully connected layers, where $<$
corresponds to “less expressive”.

Note that the locality subproperty cannot differentiate between an identity
operation and a transpose operation, and more generally, any operation that
simply reshapes its input; for that we must use the pairing subproperty.
Conversely, the pairing property does not differentiate between a dense layer
and a convolutional layer, while the locality subproperty does. Hence, the two
subproperties are complementary, and their combination in the mixing property
gives a more complete view of the subgraph as a linear operator.

##### Concrete Inference

We first describe how to infer the mixing property of an operation using
concrete values. The key is that the “contributes to” relationship between
input and output elements is defined using gradients; since our domain comes
with built-in auto-differentiation, we can leverage the existing functionality
to infer the mixing property. More explicitly, for the pairing subproperty, we
compute the gradient of a slice of the output tensor with respect to the input
tensor by summing along the slice of the output tensor. Any entries in the
input tensor with nonzero gradients are said to contribute to the slice.
Evaluating the locality subproperty is similar, except that we compute the
gradient of the input with respect to a single element of the output.

We additionally exploit the regularity of the individual operations used to
construct deep neural network graphs to simplify the inference procedure.
Namely, the “contributes to” relationship for the primitive operations is
equivalent for all slices and elements away from the boundaries; hence, we can
efficiently compute the pairing and locality subproperties (or more precisely,
a fairly tight lower bound for the subproperties) by evaluating them at only
the _center_ slice and element, rather than taking the maximum over _all_
slices and elements, respectively.

##### Abstract Interpretation

We next describe an abstract interpretation of the mixing property. Let
$\alpha_{M}$ denote the property inference function which maps concrete
subgraphs to their mixing properties. Consider two programs $p$ and $q$. We
will treat $q$ as the program transformation (appending $q$ to $p$) for which
we want to derive an abstract interpretation, i.e., we would like to infer a
lower bound for $\alpha_{M}(q\circ p)$ given $\alpha_{M}(p)=u$ without direct
access to $p$.

Recall that a mixing property is represented by a matrix with elements x, o,
m, a, (cf. Fig. 5(b)). The abstract interpretation $q^{\alpha}_{M}$ can be
defined as a matrix multiplication on $u$ and $\alpha_{M}(q)$.

###### Lemma 3.7.

$q^{\alpha}_{M}(u):=\alpha_{M}(q)\ \times\ u$ is an abstract interpretation of
$q$, where $\times$ is a matrix multiplication with $+$ and $*$ defined over
the elements $\\{\texttt{x}{},\texttt{o}{},\texttt{m}{},\texttt{a}{}\\}$ as:
$y+z=\max(y,z)$; and $y*z$ is given by the look-up table in Fig. 7.

We defer the proof to the Section D.1. Finally, to actually infer the mixing
property of a subgraph, we first infer the properties of each concrete
operation within the subgraph, and then compose them using the abstract
interpretation. To reduce overhead, we also cache the properties for each
unique operation by hashing its specification (e.g., operation type and
parameter values).

|  | z
---|---|---
|  |  x |  o |  m |  a
y |  x |  x |  x |  x |  x
o |  x |  o |  m |  a
m |  x |  m |  m |  a
a |  x |  a |  a |  a
Figure 6. Definition of $y*z$ over the elements
$\\{\texttt{x}{},\texttt{o}{},\texttt{m}{},\texttt{a}{}\\}$, representing the
locality property, used in Lemma 3.7

Figure 7. Depth property of a subgraph with inputs $I_{1},I_{2}$ and outputs
$O_{1},O_{2}$. The depth to $O_{1}$ from $I_{2}$ is defined to be 0 since
there is no path from $I_{2}$ to $O_{1}$. Since there are two paths from
$I_{2}$ to $O_{2}$, depth($O_{2}$, $I_{2}$) is the max of the two paths.

###  3.2. Depth Property

To complement the mixing property, which captures the expressivity of a
subgraph as a linear operator, the depth property captures the properties of
the subgraph as a _nonlinear_ function. More specifically, given an input and
an output of a subgraph, the depth property specifies the maximum depth over
all paths from the input to the output, where the depth of a path is defined
as the number of alternating linear and nonlinear operations along that path.
Fig. 7 gives an example of computing the depth property for a subgraph.

The depth property takes property values in the nonnegative integers. The
partial order $\leq$ is just the usual ordering on integers. In other words,
given a depth property value $d$, any subgraph whose depth property value
matches or exceeds $d$ is said to satisfy the depth property.

##### Concrete Inference

An operation $f$ is linear if $af(x)+bf(y)=f(ax+by)$ for all scalars $a,b$ and
inputs $x,y$. Hence, one way to infer whether a single operation is linear is
to simply take $x,y$ to be the inputs to the operation $f$ in the original
computation graph as produced by two random batches of inputs to the full
graph, and check whether the above equation holds for scalar $a,b$. However,
as specifying whether an operation is linear or nonlinear is relatively simple
and does not impose undue burden upon the programmer, we chose to manually
specify, for each operation, whether it is linear to avoid additional
inference overheads at synthesis time.

##### Abstract Interpretation

Our programs are represented as a directed acyclic computation graph,
flattened via topological sort. Hence, given a mapping of primitive operations
to their linear property, we simply scan all the nodes in topological order to
compute the depth property for every pair of inputs and outputs in a single
pass.

###  3.3. Shape Property

The shape property specifies the shape of every output of the subgraph, given
a shape for every input of the subgraph. More explicitly, for any program $p$,
the abstract interpretation $p_{S}^{\alpha}$ maps an input shape
$u=(i_{1},\ldots,i_{n})$ to an output shape $v=(o_{1},\ldots,o_{m})$, where
given any tensor $I$ with shape $u$, the output tensor $O=p(u)$ has shape $v$.
We use JAX’s built-in shape inference to easily infer the shape property
without executing the graph on any realized input tensors.

###  3.4. Example

Fig. 8 illustrates how we infer program properties step-by-step, using the
randomly selected subgraph from the running example in Fig. 1. The program
properties are initialized according to the identity program (i.e., the mixing
property is an identity matrix, the depth property is zero, and the shape
property preserves the input shape). We then interpret each operation on its
input properties abstractly, as described in this section, to produce its
output properties. The properties of the entire subgraph are the final outputs
from the abstract interpretation.

Figure 8. The abstract interpretation to infer program properties of the
randomly selected subgraph in Fig. 1

###  3.5. Discussion

We conclude by discussing how our program properties relate to the motivation
provided at the beginning of this section. Our properties are designed to
characterize neural architectures (and mutations thereof) as mathematical
functions, the intuition being that deep neural networks that share
similarities as mathematical functions are likely to have similar performances
as well. In terms of the two semantic desiderata: each point in the abstract
space contains points that are similarly expressive as mathematical functions,
and hence more likely to have similar performance (in terms of FLOPS,
parameter count, and accuracy); similarly, nearby points in the abstract space
yield similar subgraphs from a functional perspective.

We can further illustrate this point by considering the examples of degenerate
architectures from the beginning of this section. The depth property guides
the search away from the first two degenerate architectures: (1) a sequence of
activation functions, and (2) a sequence of linear functions, while the mixing
property rules out the last degenerate architecture: (3) a sequence of pooling
and activation functions. The shape property ensures that the synthesized
subgraph results in a legal substitution, so that the resulting graph still
represents a well-defined, executable computation. In particular, if the
output shape is too small, the resulting computation graph may not be well-
defined due to a subsequent operation producing a dimension of size zero; if
the output shape is too large, the remainder of the computation graph may not
be executable due to out of memory errors. To summarize, any architecture
which satisfies the same mixing, depth, and shape properties as a deep neural
network should at least also qualify as a valid deep neural network in the
sense of Definition 3.1, allowing the evolutionary search to prune large
portions of the concrete search space consisting of legal programs that
represent degenerate architectures.

##  4\. The Synthesis Algorithm

This section presents our synthesis algorithm formally and shows how we
leverage a notion of distance between programs and properties to achieve
progress, soundness, and completeness. To generate a program of length $n$
given a search space $T$ of transformations, the complexity of our algorithm
scales _linearly_ with $n$ and $|T|$. In contrast, the naïve enumerative
synthesis algorithm that tries all sequences of transformations until finding
a satisfying sequence has complexity $O(|T|^{n})$.

###  4.1. Distance Functions and Covering Sets

###### Definition 4.1.

Given a program property $\Pi=(\mathcal{V},\leq,\alpha)$, a distance function
is a function
$d:\mathcal{P}\times\mathcal{V}\mapsto\mathbb{R}^{+}\cup\\{\infty\\}$ such
that:

  1. (1)

$d(p,v)\geq 0$ for all $p\in\mathcal{P},v\in\mathcal{V}$.

  2. (2)

$d(p,v)=0\iff p\models v$.

  3. (3)

$d(p,v)=\infty$ $\iff$ there does not exist any finite sequence of
transformations $t=t_{1}\circ t_{2}\circ\cdots\circ t_{n}$ such that
$t(p)\models v$.

For the distance function to be useful for synthesis, it must be accompanied
by a set of transformations which can be used to minimize it:

###### Definition 4.2.

Given a space of programs $\mathcal{P}$, a program property
$\Pi=(\mathcal{V},\leq,\alpha)$, and a distance function $d$, a set of
transformations $T\subseteq\mathcal{T}$ is a covering if for all
$p\in\mathcal{P}$ and $v\in\mathcal{V}$ with $d(p,v)>0$, either (1) there
exists $t\in T$ such that $d(t(p),v)<d(p,v)$ or (2) $d(p,v)=\infty$.

For all feasible synthesis tasks, the covering $T$ is guaranteed to be able to
make progress as measured by the distance function $d$. However, _efficient_
synthesis requires a stronger condition:

###### Definition 4.3.

A covering $T$ is a uniform covering if there exists a constant $\epsilon>0$
such that for all programs $p\in\mathcal{P}$ and properties $v\in\mathcal{V}$
with $d(p,v)>0$, there exists $t\in T$ such that

(7) $\displaystyle d(t(p),v)+\epsilon\leq d(p,v)$

In other words, the amount of progress can be bounded _uniformly_ from below
(i.e., the same bound applies to all programs and properties). A uniform lower
bound guarantees that the distance will be zero after a finite number of
steps, rather than approach zero in the limit. Additionally, note that a
necessary condition for the viability of a distance is that the full space of
transformations $\mathcal{T}$ should be a covering. However, as our algorithm
will scale linearly with $|T|$, we would also like $T$ to be as small as
possible, whereas $|\mathcal{T}|$ is generally infinite (as in our case).

###  4.2. Progressive Synthesis

In this section, we will assume black-box access to a distance function $d$
for a program property $\Pi=(\mathcal{V},\leq,\alpha)$, as well as a uniform
covering $T\subseteq\mathcal{T}$. Given an initial program $p_{0}$ and a
program property value $v$, our synthesis procedure iteratively produces
programs $p_{1},p_{2},\ldots$ until it finds a program $p^{*}\models v$, where
we use $d$ to help in selecting a transformation at each step.

Algorithm 1 describes the greedy progressive synthesis algorithm that
synthesizes a program $p^{*}$ satisfying any (feasible) program property $v$.
Each iteration $i$ starts with a partial program $p_{i-1}$, where $p_{0}$ is
initialized to the input program. Given the distance function $d$, for each
transformation $t$ in the uniform covering $T$, the algorithm computes the
distance from the transformed program $t(p_{i-1})$ to the desired property
$v$, and selects the transformation $t_{i}$ which achieves the minimum
distance. This process is repeated until the distance is 0, at which point the
algorithm terminates and returns the sequence of transformations.

Algorithm 1 Greedy progressive synthesis

1:initial program $p$, program property $v$, distance function $d$, uniform
covering $T$

2:$\not\models$ if $(p,v)$ is infeasible; otherwise, a sequence of
transformations $\tau$ such that $\tau(p)\models v$

3:if $d(p,v)=\infty$ then

4: return $\not\models$

5:end if

6:$\tau\leftarrow\\{\\}$, $p_{0}\leftarrow p$

7:for $i$ = 1, 2, … do

8: if $d(p_{i-1},v)=0$ then

9: return $\tau$

10: end if

11: $t_{i}\leftarrow\operatorname*{\arg\min}_{t\in T}d(t(p_{i-1}),v)$

12: $p_{i}\leftarrow t_{i}(p_{i-1})$

13: $\tau\leftarrow(t_{1},\ldots,t_{i})$

14:end for

The following theorem characterizes the correctness and efficiency of
progressive synthesis.

###### Theorem 4.4.

Given a distance function $d$ and a uniform covering $T$, the progressive
synthesis algorithm satisfies the following three properties:

  1. (1)

Soundness: if the algorithm returns $p^{*}$, then $\alpha(p^{*})\models v$.

  2. (2)

Completeness: if the algorithm returns $\not\models$, then the synthesis task
is infeasible.

  3. (3)

Progress: the algorithm terminates after a finite amount of time, which is
linear in the length of the final sequence of transformations and linear in
$|T|$.

We defer the proof to the Section D.2.

####  4.2.1. Stochastic Progressive Synthesis

Selecting a random feasible operation (with probability $p>0$) and an
operation that makes progress (with probability $1-p$) increases the expected
length of the synthesized subgraph, but ensures that any satisfying subgraph
has a positive probability of being synthesized. We use this variant rather
than a pure greedy approach in our implementation to encourage greater
diversity.

####  4.2.2. Progressive Synthesis as a Universal Synthesis System

A natural question is the extent to which it is necessary to approach the task
of program synthesis by defining a distance function with a covering.
Alternatively, we would like to know whether there are synthesis tasks which
have efficient solutions, but cannot be solved efficiently via progressive
synthesis.

The main result of this section identifies a natural class of synthesis
algorithms that are exactly as powerful as progressive synthesis. In
particular, we define the class of _recursively consistent_ synthesis
algorithms as the set of algorithms $A$ that can be efficiently “restarted”
from a partial solution, e.g., if $A(p_{0},v)=(t_{1},t_{2},\ldots,t_{n})$,
then $A(t_{1}(p_{0}),v)=(t_{2},\ldots,t_{n})$.

The following (informal) theorem states that any task that can be efficiently
solved by a recursively consistent algorithm can also be solved efficiently by
progressive synthesis, and vice-versa.

###### Theorem 4.5 (Informal Version.).

Given a synthesis task specified by a space of programs $\mathcal{P}$, a
program property $\Pi=(\mathcal{V},\leq,\alpha)$, and a set of primitive
transformations $E$, the following are equivalent:

  1. (1)

There exists a sound, complete, and recursively consistent synthesis algorithm
$A$ that runs in time polynomial in the length of the synthesized
transformations $|A(p,v)|$, for all $p\in\mathcal{P}$, $v\in\mathcal{V}$.

  2. (2)

$E$ is a uniform covering with respect to an efficiently computable distance
$d$.

The second statement guarantees that progressive synthesis is sound, complete,
and runs in polynomial time. In particular, our analysis takes into account
the complexity of the distance function $d$ (cf. Theorem 4.4, which treats $d$
as an oracle). We state and prove the rigorous version of this result in
Section D.2.

###  4.3. Multiple Properties from Monotonic Transformations

This section discusses how to adapt our progressive synthesis algorithm when
there are multiple properties of interest. For instance, assume that we have
two program properties $\Pi_{1}$ and $\Pi_{2}$. Each property $\Pi_{i}$ has a
distance function $d_{i}$ with a uniform covering $T_{i}$. The objective is to
synthesize a sequence of transformations satisfying a set of program property
values $S=\\{v_{1}\in\mathcal{V}_{1},v_{2}\in\mathcal{V}_{2}\\}$.

The main problem is that applying a transformation $t\in T_{1}$ that decreases
the distance $d_{1}$ to the first property $v_{1}$ may increase the distance
$d_{2}$ to the second property $v_{2}$. In other words, we cannot guarantee
there exists a transformation $t\in T_{1}\cup T_{2}$ that simultaneously
improves both $d_{1}$ and $d_{2}$. In the worst case, progress is impossible:
we may trade-off between $d_{1}$ and $d_{2}$ indefinitely. To resolve this
issue, we introduce a notion of monotonic transformations:

###### Definition 4.6.

A transformation $t\in\mathcal{T}$ is monotonic with respect to a property
$\Pi$ and distance $d$ if for all programs $p\in\mathcal{P}$ and properties
$v\in\mathcal{V}$, $d(t(p),v)\leq d(p,v)$.

A monotonic transformation, by definition, cannot cause the property $\Pi$ to
regress. We will also refer to a set $T\subseteq\mathcal{T}$ as monotonic if
all $t\in T$ are monotonic. For instance, the set of all transformations
$\mathcal{T}$ is monotonic with respect to the depth property.

The following theorem gives a sufficient condition for progressive synthesis
to succeed over multiple properties. We defer the proof to Section D.3.

###### Theorem 4.7.

Let $\mathbb{P}=\\{\Pi_{i}=(\mathcal{V}_{i},\leq_{i},\alpha_{i})\\}_{i=1}^{N}$
be a set of program properties, each with a distance function $d_{i}$ and
covering $T_{i}$, respectively, and let
$S=\\{v_{i}\in\mathcal{V}_{i}\\}_{i=1}^{N}$ be a set of program property
values. If for all $i$, $\cup_{j\neq i}T_{j}$ is monotonic with respect to
$d_{i}$, then $d(p,S)=\sum_{i}d_{i}(p,v_{i})$ is a distance function for
$\mathbb{P}$ with covering $T=\cup_{i=1}^{N}T_{i}$. Furthermore if each
covering $T_{i}$ is uniform, then so is $T$.

###  4.4. Progressive Synthesis for NAS

This section shows how to apply the progressive synthesis algorithm to our
setting of synthesizing subgraphs satisfying the program properties described
in Section 3. As a technical matter, we need to first interpret the definition
of distance functions and covering sets from Section 4.1 in the context of an
abstract interpretation $\alpha$. Briefly, given an _abstract distance
function_ $d^{\alpha}(u,v)$ over properties $u,v\in\mathcal{V}$ (where
$d^{\alpha}(u,v)=0$ implies $u\geq v$), we say $T\subseteq\mathcal{T}$ is an
_abstract uniform covering_ if there exists $\epsilon>0$ such for all
$u,v\in\mathcal{V}$ with $d^{\alpha}(u,v)>0$, there exists $t\in T$ such that

(8) $\displaystyle d^{\alpha}(t^{\alpha}(u),v)+\epsilon\leq d^{\alpha}(u,v)$

Hence, if $\alpha(p_{0})=u$ and $t_{1},\ldots,t_{n}$ is a sequence of
transformations such that the distance of the abstractly interpreted property
is zero, i.e.,

(9) $\displaystyle d^{\alpha}((t_{n}^{\alpha}\circ\cdots\circ
t_{1}^{\alpha})(u),v)=0$

then $p=(t_{n}\circ\cdots\circ t_{1})(p_{0})\models v$. A complete treatment
is provided in Appendix C.

In order to apply the version of Theorem 4.4 using abstract interpretations to
our setting, in the following sections we will prove:

  1. (1)

For each of the mixing, depth, and shape properties, there exists an abstract
distance $d^{\alpha}_{i}$ computable in polynomial time with a uniform
abstract covering of transformations $T_{i}\subset\mathcal{T}$.

  2. (2)

$T=\cup_{i}T_{i}$ is monotonic with respect to both the depth and mixing
properties.

  3. (3)

$T\cap M_{S}$, where $M_{S}$ is the set of transformations that preserve the
shape of the output tensor, is a uniform covering for both the depth and
mixing properties.

For every property, we take $T_{i}=E$, the set of transformations $E$
consisting of adding a single primitive operation. Section A.1 describes the
full set of primitive operations we support. Then $T=E$, and the following
result is immediate:

###### Theorem 4.8.

The progressive synthesis algorithm for $\alpha$NAS is sound, complete, and
runs in time linear in $|p^{*}|$ and $|E|$, where $p^{*}$ is the synthesized
subgraph, and $E$ is the set of primitive operations.

####  4.4.1. Sequential Subgraphs Without Reshaping

As a first step, we will focus on synthesizing subgraphs that are sequential
(i.e., each operation consumes exactly one input and each output is consumed
exactly once) and preserve the dimensions of their inputs. In other words, we
restrict our attention to the set of _simple primitives_ $E_{s}\subseteq E$
that take one input and produce one output, and also do not reshape or
transpose their inputs. Synthesis occurs over the corresponding space of
_simple transformations_ $\mathcal{T}_{s}=E_{s}^{*}$. The set of program
properties values $\mathcal{V}$ is limited to those satisfiable by a
sequential subgraph with operations from $E_{s}$. We present the key results
below; all proofs are deferred to Section D.4.

####  4.4.2. Mixing Property

We denote the mixing property as $\Pi_{M}=(\mathcal{V}_{M},\leq,\alpha_{M})$.
Without any reshape operations, the number of input and output dimensions are
equal; hence, the space of property values contains only _square_ matrices
with entries in {a, m, o, x} satisfiable by a sequential subgraph (cf. Fig.
4(a)). We define the following abstract distance function for the mixing
property.

###### Definition 4.9.

Define $d^{\alpha}_{M}(U,V)$, where $U,V\in\mathcal{V}_{M}$, to be the number
of entries $i,j$ such that $V_{ij}>U_{ij}$. Then $d^{\alpha}_{M}$ is a
distance on the mixing property.

The following lemma establishes that the set of primitive ops $E_{s}$ is
monotonic with respect to the mixing property.

###### Lemma 4.10.

$\forall t_{1},t_{2}\in\mathcal{T}_{s}$ and $U\in\mathcal{V}_{M}$,
$(t^{\alpha}_{2}\circ
t^{\alpha}_{1})(U)\geq\max(t^{\alpha}_{2}(U),t^{\alpha}_{1}(U))$.

###### Theorem 4.11.

The set of simple primitives $E_{s}$ is a monotone uniform abstract covering
for the mixing property with respect to $d^{\alpha}_{M}$.

####  4.4.3. Depth Property

For the depth property $\Pi_{D}=(\mathcal{V}_{D},\leq,\alpha_{D})$, the space
$\mathcal{V}_{D}$ of depth properties for sequential subgraphs consists of all
the nonnegative integers. The function $d^{\alpha}_{D}(u,v)=\max(0,v-u)$ is an
abstract distance for this property. It is easy to see that the set of simple
primitive operations forms a uniform abstract covering with respect to this
distance, since we can always append alternating linear and nonlinear
operations to decrease the distance to $v$. The depth property is also
trivially monotonic for all transformations $\mathcal{T}$.

###### Theorem 4.12.

The set of simple primitives $E_{s}$ is a monotone uniform abstract covering
for the depth property with respect to $d^{\alpha}_{D}$.

####  4.4.4. Shape Property

In general, there are two ways a (dimension-preserving) operation can change
the shape of a tensor. The first is by changing the channel dimension to an
arbitrary integer (e.g., a dense layer). The second is by downsampling the
spatial dimensions by an integer factor (e.g., a 2 $\times$ 2 pooling
operation would decrease the spatial dimensions by a factor of 1/2).
Convolutional layers have the potential to perform both at the same time. Note
that we do not support operations that change the spatial dimensions by other
amounts (for instance, strided convolutions without padding), which does not
materially limit our search space; in fact, all of the base architectures
considered in Section 6.1 respect this condition.

The space of all shape properties $\mathcal{V}^{m}_{S}$ of dimension $m\geq 1$
consists of all $m$-tuples of positive integers, which specify the shape of an
$m$-dimensional tensor: the first entry is the batch dimension (which is never
changed); the last entry is the channel dimension; and all intermediate
entries are the spatial dimensions.

###### Definition 4.13.

The following function $d^{\alpha}_{S}(A,B)$ is an abstract distance on the
shape property:

(10) $\displaystyle d^{\alpha}_{channel}(A,B)$
$\displaystyle:=\begin{cases}1,&\text{if }a_{channel}\,\neq\,b_{channel}\\\
0&\text{otherwise}\end{cases}$ (11) $\displaystyle d^{\alpha}_{spatial}(A,B)$
$\displaystyle:=\begin{cases}\sum_{i=1}^{m-2}a_{i}/b_{i},&\text{if
}b_{i}\text{ divides }a_{i}\quad\forall i\\\
\infty&\text{otherwise}\end{cases}$ (12) $\displaystyle d^{\alpha}_{S}(A,B)$
$\displaystyle:=d^{\alpha}_{channel}(A,B)+d^{\alpha}_{spatial}(A,B)$

where $A=(batch,a_{1},\ldots,a_{m-2},a_{channel})\in\mathcal{V}^{m}_{S}$ and
$B=(batch,b_{1},\ldots,b_{m-2},b_{channel})\in\mathcal{V}^{m}_{S}$

Next we show that $E_{s}$ is a uniform covering. Indeed, it is always possible
to decrease $d^{\alpha}_{S}$ by appending one of two simple primitives: if any
spatial dimensions are not equal, a pooling operator $p$ with an appropriately
chosen window yields:

(13) $\displaystyle d^{\alpha}_{spatial}(e_{pool,S}^{\alpha}(A),B)$
$\displaystyle<d^{\alpha}_{spatial}(A,B)$ (14) $\displaystyle
d^{\alpha}_{channel}(e_{pool,S}^{\alpha}(A),B)$
$\displaystyle=d^{\alpha}_{channel}(A,B)$

If $d_{channel}>0$ then, a dense layer $e_{dense}$ achieves:

(15) $\displaystyle d^{\alpha}_{spatial}(e_{dense,S}^{\alpha}(A),B)$
$\displaystyle=d^{\alpha}_{spatial}(A,B)$ (16) $\displaystyle
0=d^{\alpha}_{channel}(e_{dense,S}^{\alpha}(A),B)$
$\displaystyle<d^{\alpha}_{channel}(A,B)$

###### Theorem 4.14.

The set of simple primitives $E_{s}$ is a uniform abstract covering for the
shape property with respect to $d^{\alpha}_{S}$.

####  4.4.5. Example

Consider the running example in Fig. 1. The goal is to synthesize a subgraph
that satisfies the mutated properties. Fig. 9 illustrates how our synthesis
algorithm makes progress toward this objective at each step by appending an
operation that reduces the abstract distance to the target properties (in
red). The first operation BatchNorm makes progress on the depth properties. In
the second step, the nonlinear activation function SiLU changes neither the
mixing nor shape properties, but increases depth. This process repeats until
the synthesized subgraph reaches a total distance of 0.

Figure 9. Illustration of the synthesis of the first three operations in the
subgraph from Fig. 1. The progressive synthesizer adds an operation that
reduces the distance to the target properties in each step. The annotation
“d=” on the right of each property indicates the distance to the target
property.

###  4.5. Compressing the Search Space

Many transformations are indistinguishable with respect to the abstract
properties. For instance, in our case, a 2 $\times$ 2 average pool and a 3
$\times$ 3 max pool have the same mixing, depth, and shape properties. Hence,
during synthesis it is sufficient to measure the progress of a single pooling
operator, which is representative of the progress for any other pooling
operator. Formally, given two transformations $s$ and $t$, if their abstract
interpretations are equivalent, i.e., $s^{\alpha}=t^{\alpha}$, then we can
safely remove one of them from the covering set $T$ while preserving the
safety and performance of the progressive synthesis algorithm. Our final
synthesis algorithm considers only 87 out of the 1,402 total primitive
transformations during synthesis. The remaining 1,315 operations consist
largely of different settings for spatial kernels (e.g., pooling or
convolutions) and feature groups (e.g., group normalization or grouped
convolutions).

After a satisfying subgraph has been synthesized, we perform a second pass to
randomly replace each operation $e$ in the synthesized subgraph with an
operation from the set originally represented by $e$; by construction, the
replacements preserve the desired properties of the subgraph. For example, we
can safely change the momentum of the first BatchNorm synthesized in Fig. 9.
To ensure the final subgraph is balanced, we only use operations of the same
type as representatives (e.g., both SiLU and ReLU are in the 87 operations,
even though they have equivalent abstract interpretations).

###  4.6. Extensions Beyond Sequential Subgraphs

This section briefly describes how to extend our synthesis algorithm beyond
sequential subgraphs composed of simple operations. Supporting mutations of
subgraphs with multiple inputs and outputs proceeds in three steps. First, we
identify the reshape and binary operations in the subgraph, and decompose the
subgraph into a set of sequential subgraphs composed of simple operations
connected by the reshape and binary operations. Second, we can mutate the
structure of the reshape and binary operators. Finally, we synthesize a
replacement for each of the sequential subgraphs using our aforementioned
techniques.

The details of the structure mutation are deferred to Section A.2. The key is
ensuring that the mutated structure remains feasible (e.g., the resulting
structure should still be connected). In practice, most common architectures
consist of a sequential backbone, augmented by basic residual connections.
Furthermore, reshaping occurs relatively infrequently and is usually only
applied at the end of the network to flatten the features for extracting
logits. Hence, our implementation does not perform the second step (structure
mutation).

##  5\. Implementation

##### Evolutionary search.

We initialize the evolutionary search with a given base architecture (e.g.,
ResNet-50). At each iteration, we randomly select a single individual to
mutate; individuals with higher fitness are more likely to be chosen. This
individual is trained from scratch and its fitness is evaluated. This
procedure is repeated for a fixed number of iterations, at which point we
terminate the search and return the population of evolved individuals. For
more details on our evolutionary search procedure with multiple objectives,
see Section A.3.

##### Mutating Architectures.

We perform our architecture search at the level of blocks. Each base
architecture is split into predefined blocks, where each block consists of
mutable components, possibly wrapped within a immutable residual connection.
For instance, we have the following block types in the ResNet-50 architecture:
(1) bottleneck block with a 2 $\times$ 2 spatial down-sampling and (2)
bottleneck block without any spatial down-sampling. We decompose the Vision
Transformer as follows: (1) self attention block, and (2) MLP block. We also
use a small 2-block CNN without residual connections; each block consists of a
convolution that doubles the feature depth, a ReLU activation, and an Average
Pool that reduces the spatial resolution by half. Hence, all our models
consist of a sequential stack of blocks with some residual connections.

##### Mutating Blocks.

To mutate an architecture, we select a block at random, then select a subgraph
within that block at random. We then synthesize a replacement subgraph with
mutated properties and replace the subgraph into the block. Each mutation is
also applied at random to other blocks of the same type within the model. In
addition to mutating individual blocks, we also include block deletion and
block duplication in our search space. When duplicating a block, we select a
block at random and insert a copy into another random location in the model.

##### Mutating properties.

In general, we mutate properties in the direction of relaxing constraints:
since a synthesized program $p$ satisfies a property value $v$ if
$\alpha(p)\geq v$, without any mutations the synthesis is bound to only return
subgraphs (and hence architectures) with the same property values or greater.
Relaxing properties also ensures that the synthesis task is feasible, since
the original subgraph automatically satisfies the mutated properties. The only
exception is the depth property, which is preserved with 50% probability,
otherwise we mutate it up or down by up to 2 uniformly at random. We mutate
the shape property by removing the output shape requirement with 50%
probability. We mutate the mixing property by removing pairings with 50%
probability.

##### Synthesis.

We implement stochastic progressive synthesis as described in Sections 4.2.1
and 4.6. At each step, an operation is selected at random with probability
proportional to $1/(1+d)$, where $d$ is the distance to the desired properties
after appending the operation. Once the synthesized subgraph reaches the size
of the original subgraph, we switch to the greedy algorithm, which selects an
operation that achieves the minimum distance. If synthesis does not complete
after two additional steps, we consider synthesis to have failed and report no
individual for that generation.

##### Environment.

We use JAX (Bradbury et al., 2018) to train and evaluate architectures on TPU
v2 (for CIFAR-10) and v3 (for ImageNet) accelerators. Our implementation is
$\sim$10,000 lines in Python.

##  6\. Experimental Results

This section presents results from experiments that evaluate the ability of
our approach to generate interesting novel architectures (Section 6.1), assess
the importance of key components in our approach (Section 6.2), and compare
against prior approaches (Section 6.3). In each experiment, we initialize the
evolutionary search with a base model (displayed as yellow stars in the
plots222We evaluate the base model twice to reduce the noise from the
stochasticity of the training procedure.). We run the search for a fixed
number of trials; each trial involves training a proposed candidate for a
fixed number of epochs to evaluate its accuracy on a given dataset. The search
trades off the primary objective of accuracy (higher is better) against some
secondary objectives: FLOPS (lower is better), number of parameters (lower is
better), and training throughput (images per second, higher is better). Table
2 in Section B.1 describes the setup for each experiment in more detail.

###  6.1. Case Studies

####  6.1.1. CIFAR-10

Our first set of experiments focuses on the CIFAR-10 dataset with 50,000
training images and 10 classes. We are specifically interested in how rapidly
our evolutionary search progresses when seeded with models that leave ample
room for improvement. Our first experiment seeds a small 2-layer CNN with
residual connections, which is suboptimal in terms of accuracy (80%) but
otherwise has good performance characteristics (low FLOPS, parameter count).
Our method discovers a model with substantially increased accuracy, from 81.3%
to 89.6%, while also decreasing the number of parameters slightly.

We also run a second search seeded with the ResNet-34 architecture. This base
model has much higher accuracy on CIFAR-10 (91.5%) but is less efficient.
Figure 10 displays the results. Keeping accuracy constant, our search
discovers one model that decreases the FLOPS by 68.7%, and a second model that
reduces parameters by more than 96% (from 21.3 to 0.8 million parameters). A
third model increases the accuracy to 93.0% using only 5.8 million parameters,
a 73.1% reduction. These results support the hypothesis that our approach is
able to make rapid progress and discover substantially improved models on
simpler tasks.

Figure 10. Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS. Yellow
stars represent the base architecture.

####  6.1.2. ImageNet

We next present results using the ILSVRC 2012 version of the ImageNet dataset
with 1.2 million training images and 1,000 classes. Our objective is to test
whether our approach can generate improvements in a more difficult setting.

Figure 11. Evolving a ResNet-50 model on ImageNet. We optimize for increased
accuracy, decreased FLOPS, increased training speed. For the same accuracy, we
have decreased GFLOPS by 23% and increased the training speed by 12%. Figure
12. Evolving a ViT-S/16 model on ImageNet. We optimize for increased accuracy,
decreased FLOPS, and increased training speed. Our search returns a model with
the same accuracy using 30% fewer FLOPS and parameters. Figure 13. Two
mutations of the self-attention block in the ViT architecture. The final model
is a strict improvement over the base architecture in all objectives.

##### ResNet-50

The first experiment is seeded with the standard ResNet-50 architecture (He et
al., 2016). The ResNet architecture has seen many variants since being
introduced in 2015, and its main innovation (the residual connection) remains
a central feature of many architectures today. It remains a common benchmark
for many vision tasks. Figure 11 displays our results. After evaluating 400
individuals, $\alpha$NAS discovers a model that has the same accuracy but 23%
fewer FLOPS (from 10.1 to 7.8 GFLOPS) and 13.7% fewer parameters (from 25.6 to
22.0 million); and a second model which increases the training speed 12% (from
480 to 538 images per second per core) with slightly better accuracy. We also
discover several models with nearly 80% accuracy (a 4.5% increase, not shown
in the plot), though at a nearly 15-fold increase in both FLOPS and parameter
count.

##### ViT-S/16

The second experiment is seeded with the S/16 variant of the Vision
Transformer architecture (ViT) (Dosovitskiy et al., 2021). ViT is a relatively
new architecture, and many variants have been proposed recently to improve the
base architecture in a number of ways, such as accuracy, training speed,
inference speed, and sample efficiency. We are interested in seeing whether
$\alpha$NAS can automatically discover similar improvements.

Figure 12 plots our results. After evolving a total of 400 individuals,
$\alpha$NAS discovers a model as the 278th individual that decreases FLOPS by
28% and parameter count by 30% (with a negligible increase in accuracy). The
mutation of the MLP block in Fig. 1 is present in this model. The resulting
block has almost no trainable parameters and very few FLOPS. Similar mutations
of the MLP block are common throughout the population. Such a mutation is
nearly impossible to perform using single-operation mutations, since it
requires eight mutations and simultaneously increasing depth while replacing
linear operations with cheaper ones. If a linear operator is replaced before
the depth is increased, the accuracy could suffer; but if depth is increased
before replacing the linear operator, the parameter count and FLOPS will
increase. In both cases, the intermediate model is worse than the parent,
making it unlikely to be selected for further mutation.

We present another series of mutations in Fig. 13 that increases accuracy by
nearly 1% and improves FLOPS, parameter count, and training speed by 6–7%.
Mutation 34 appears in nearly 20% of the evolved population, as it strictly
improves every metric for the base architecture. Mutation 161 replaces the
multiplicative scaling with a self-gating SiLU unit, and also replaces the
Softmax with a cheaper but related Sigmoid. These analyses suggest that
$\alpha$NAS is able to discover a wide range of novel architectural
improvements.

##### EfficientNet-B0

Our final experiment is seeded with the EfficientNetV1-B0 architecture (Tan
and Le, 2019). EfficientNet is a family of extremely parameter- and FLOP-
efficient models, and presents a strong baseline produced by existing NAS
techniques. We are interested in evaluating whether our methods can deliver an
improvement over a state-of-the-art model. The results after training each
candidate for 90 epochs are displayed in Fig. 14. Although EfficientNet is
indeed a more difficult architecture to improve on, $\alpha$NAS is still able
to discover a model (named E’) which improves both FLOPS and parameter count
by 7–8% with similar accuracy. Another model (named E”) increases accuracy by
nearly 2% with fewer parameters, but at a 3$\times$ increase in FLOPS.

We also selected a handful of promising models after 90 epochs to train for
the full 350 epochs, in order to match the evaluation in the original
EfficientNet paper. Under this setting, the base EfficientNet-B0 architecture
reports a final accuracy of 75.2%. Model E’ has a final accuracy of 74.3% (but
maintains the 7–8% improvement on FLOPS and parameter count). Model E”
outperforms the base architecture with fewer parameters and a higher final
accuracy of 76.9%.

Figure 14. Evolving an EfficientNet-B0 model on ImageNet. We optimize for
increased accuracy, decreased FLOPS, and increased training speed. We have
decreased GFLOPS by 9% and parameter count by 20% for comparable accuracy and
speed.

###  6.2. Ablation Studies

This section evaluates the importance of key elements in the design of
$\alpha$NAS. For these experiments, we used ResNet-34 as our base model and
CIFAR-10 for the dataset.

####  6.2.1. Program Properties

To evaluate the importance of program properties, we compared $\alpha$NAS with
a similar strategy that replaces a randomly selected subgraph with a random
subgraph (ignoring program properties), called the _random subgraph strategy_.
On average, both the original and replacement subgraphs are of size 3. Unlike
$\alpha$NAS, this strategy searches directly in the concrete space of
architectures, without performing property inference and guided synthesis.
This study tests the hypothesis that using abstract properties to guide the
search enables $\alpha$NAS to perform larger mutations while still evolving
high-quality candidates. As shown in Fig. 15, $\alpha$NAS’s accuracy-
parameters Pareto curve completely dominates the random subgraph strategy’s by
a wide margin; specifically, the random subgraph strategy struggles to evolve
models with high accuracy, and in fact makes next to no progress on improving
the base architecture. These results confirm our intuition that (1) small
steps in the abstract search space can be effectively translated into large
steps in the concrete space while maintaining good performance, whereas (2)
large random steps directly in the concrete space are dominated by poor
quality architectures. Additional results in Section B.2 further demonstrate
that the performance of the random search degrades rapidly as the size of the
mutations increases.

We also evaluated the importance of each individual program property by
modifying $\alpha$NAS to use only a single property throughout the search. Our
results show that all three program properties are important, as using them
together outperforms using any individual property alone. More details can be
found in Section B.3.

####  6.2.2. Progressive Synthesis Algorithm

Next, we evaluate the benefit of having an efficient synthesis algorithm. In
this experiment, we compare with a naïve enumerative algorithm that simply
enumerates all possible subgraphs of a given size in a random order, starting
from a size of 1 and increasing the size until it finds a subgraph that
satisfies the target program properties. As expected, the enumerative
algorithm is highly inefficient, taking an average of 1,932 seconds to
synthesize a satisfying subgraph, compared to only 67 seconds when using our
progressive synthesis algorithm; for context, training a ResNet-34 model to
evaluate its accuracy in our setting takes roughly 600 seconds, so enumerative
synthesis introduces over 300% overhead. Efficiency notwithstanding, the
_quality_ of candidates explored by the two variants are similar when
evaluating the same number of candidates (see Fig. 23 in Section B.4), which
suggests that the constraints imposed by the abstract properties are largely
responsible for the quality of our search.

Figure 15. Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. a
random subgraph mechanism.

###  6.3. Comparison with Existing NAS Techniques

This section compares $\alpha$NAS against prior approaches that do not require
defining a carefully-crafted structured search space. In particular, we adopt
the strategies used in Primer (So et al., 2021) and AutoML-Zero (Real et al.,
2020), two state-of-the-art NAS techniques for unstructured search spaces.
These approaches search directly in the concrete space of architectures,
similar to the random subgraph strategy in Section 6.2.1, but compensate by
using much smaller mutations. Primer mutates on the basis of individual
operations one at a time, by either deleting, inserting, or swapping
operations; or randomly changing one parameter value. AutoML-Zero considers an
additional mutation that randomizes an entire component, essentially combining
mutations used in Primer and the random subgraph strategy.

For clarity, we emphasize that our evaluation is only meant to imitate their
search mechanisms (i.e., mutation strategies) within our evolutionary
framework. In particular, both Primer and AutoML-Zero focus on slightly
different tasks and hence use different program representations compared to
ours. They also implement other advanced techniques, which are orthogonal to
the contributions in this work, to reduce candidate evaluation time (e.g.,
early stopping). For instance, AutoML-Zero was originally designed to evolve
both the neural network architecture and optimization algorithm jointly from
scratch. Since this strategy does not yield results comparable to even our
baseline (i.e., ResNet-34 on CIFAR-10), in order to establish a more fair
comparison, we instead apply the respective search mechanisms to evolve
architectures starting from the same base architecture.

According to the results in Figs. 16 and 24 in Section B.5, $\alpha$NAS
discovers significantly more Pareto optimal models than both Primer and
AutoML-Zero. Due to using only small mutations, Primer requires many more
evaluations to make large changes to the base architecture, leading to slower
exploration compared to AutoML-Zero and $\alpha$NAS; the slow exploration is
visible in Fig. 16 as Primer does not discover architectures with GFLOPS lower
than 0.3. The distribution of the candidates explored by AutoML-Zero is
between Primer’s and the random subgraph strategy’s, which is to be expected
as AutoML-Zero’s mutations are the union of those two’s. In summary, these
results further support the benefit of using properties to guide the search
over an abstract design space, as $\alpha$NAS delivers a consistent and
significant advantage over existing strategies that search directly over the
concrete space of actual architectures.

Figure 16. Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. the
Primer search mechanism.

Additionally, it is worth comparing our result against Turner et al. (2021),
which is another approach that applies techniques in program languages (i.e.,
compiler optimizations) to NAS. As we cannot reimplement Turner et al.
(2021)’s compiler optimizations easily in our framework, we compare our
results with those reported in their paper directly. On the CIFAR-10 dataset,
starting from ResNet-34, Turner et al. (2021) is able to compress the model by
2–3$\times$ without accuracy loss after proposing 1000 candidates (they reject
approximately 90% of their candidates without training using a heuristic that
estimates the likelihood a candidate architecture will have significantly
degraded accuracy). In contrast, $\alpha$NAS is able to compress the same
model by over 26$\times$ (Section 6.1.1) within 800 candidates. Finally, we
note that the architectures produced by Turner et al. (2021) are less
interpretable than ours as their optimization occur at the level of loop
transformations, and hence the resulting architectures cannot be expressed in
terms of the standard human-readable neural network primitives.

##  7\. Related Work

###  7.1. Neural Architecture Search

This section describes other existing NAS approaches related to our work that
have not been discussed previously. Somewhat similar to our property-guided
NAS, some approaches restrict their search spaces to only mathematically
structure-preserving transformations, e.g., only mutating the operation’s
parameters or changing network connections (Wei et al., 2016; Cai et al.,
2018). Their main motivation is to be able to transfer already-trained weights
from an existing architecture to new architectures, so as to accelerate the
candidate evaluation process; in contrast, our properties are motivated by the
semantics of deep neural networks. Their properties are also more strict than
ours, thus limiting their search spaces.

Our work is one of the first to apply techniques programming languages to NAS.
A prior work by Turner et al. (2021) combines non-semantics preserving
transformations from NAS with semantics preserving transformations from
compiler optimizations. In contrast, our work exploits other higher-level
program languages techniques including program synthesis, program abstraction,
and abstract interpretation.

###  7.2. Optimizing Neural Networks for Efficiency

Several techniques such as quantization (Gholami et al., 2021; Banner et al.,
2018; Wang et al., 2018) and pruning (Hassibi and Stork, 1992; LeCun et al.,
1989; Luo et al., 2017; Frankle and Carbin, 2019) aim to improve execution
time efficiency. Note that these approaches are orthogonal to our work in the
sense that one can use our technique to generate new architectures, and then
prune or quantize the weights to compress the model once trained. Similarly,
the primary benefit of auto-parallelization (Jia et al., 2019c; Huang et al.,
2019; Narayanan et al., 2019), graph substitutions (Jia et al., 2019b, a; Yang
et al., 2021), and other tensor compiler optimizations (Chen et al., 2018;
Adams et al., 2019; Vasilache et al., 2018; Kjolstad et al., 2017; Zhou et
al., 2020; Phothilimthana et al., 2021) is that they generate semantic-
preserving optimizations and can be (theoretically) applied to any neural
network architecture. In contrast, our method aims to discover semantically
novel architectures.

###  7.3. Goal-Directed Program Synthesis

Our key idea of using program properties to guide the synthesis of neural
network subgraphs can be classified as goal-directed program synthesis. A
number of prior works use abstract properties of partial programs to direct
their synthesis procedure (Polozov and Gulwani, 2015; Phothilimthana et al.,
2016; Wang et al., 2017b, a). The main difference is that we develop a precise
notion of distance between partial programs and properties; thus, we can
devise a linear-time algorithm to synthesize satisfying programs. Our setting
also departs from most program synthesis tasks in that the design of neural
networks does not have a strict correctness requirement.

##  8\. Conclusion and Future Work

With the increasing complexity of hardware accelerators with diverse
performance characteristics, a large variety of ML compilers that target them,
and a wide range of well-known neural network architectures, finding the right
architecture to solve a task is challenging and often requires a deep
knowledge of the full stack. Techniques like neural architecture search (NAS)
that automate the exploration of this complex design space are therefore
likely to be increasingly more important. In this work, we identified some of
the fundamental limitations of current approaches for NAS, and proposed a
principled approach for overcoming these limitations using a novel property
guided synthesis strategy. We demonstrate that a simple evolutionary search
over the resulting abstract search space can produce significantly improved
architectures on several widely used benchmarks for image recognition,
compared to the base architecture used to initialize the search. One possible
direction for future work would be to to initialize the search with multiple
base architectures, and let the evolutionary mechanism decide which
individuals to optimize—possibly with more sophisticated evolutionary
techniques such as crossover. Additionally, as our approach is broadly
applicable to most (if not all) deep neural net architectures and domains, we
also leave to future work the evaluation of other interesting tasks such as
language modeling or audio speech recognition.

###### Acknowledgements.

We would like to thank Chen Liang, David So, Esteban Real, Hanxiao Liu,
Hyeontaek Lim, Omar Costilla-Reyes, Martin Abadi, Mike Burrows, Ras Bodik,
Rishabh Singh, and Yanqi Zhou for their help and insightful feedback during
the development of this project.

## References

  * (1)
  * Adams et al. (2019) Andrew Adams, Karima Ma, Luke Anderson, Riyadh Baghdadi, Tzu-Mao Li, Michaël Gharbi, Benoit Steiner, Steven Johnson, Kayvon Fatahalian, Frédo Durand, and Jonathan Ragan-Kelley. 2019\.  Learning to Optimize Halide with Tree Search and Random Programs.  _ACM Trans. Graph._ 38, 4, Article 121 (July 2019), 12 pages.  https://doi.org/10.1145/3306346.3322967
  * Banner et al. (2018) Ron Banner, Itay Hubara, Elad Hoffer, and Daniel Soudry. 2018\.  Scalable Methods for 8-Bit Training of Neural Networks. In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ (Montréal, Canada) _(NIPS’18)_. Curran Associates Inc., Red Hook, NY, USA, 5151–5159.
  * Bender et al. (2020) Gabriel Bender, Hanxiao Liu, Bo Chen, Grace Chu, Shuyang Cheng, Pieter-Jan Kindermans, and Quoc V Le. 2020.  Can Weight Sharing Outperform Random Architecture Search? An Investigation With TuNAS. In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_. IEEE, 14311–14320.
  * Bradbury et al. (2018) James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018\.  _JAX: composable transformations of Python+NumPy programs_.  http://github.com/google/jax
  * Cai et al. (2018) Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang. 2018.  Efficient architecture search by network transformation. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 32.
  * Chen et al. (2018) Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018.  TVM: An Automated End-to-End Optimizing Compiler for Deep Learning. In _Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation_ (Carlsbad, CA, USA) _(OSDI’18)_. USENIX Association, USA, 579–594.
  * Dosovitskiy et al. (2021) Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. 2021\.  An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=YicbFdNTTy
  * Frankle and Carbin (2019) Jonathan Frankle and Michael Carbin. 2019.  The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=rJl-b3RcF7
  * Gholami et al. (2021) Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W. Mahoney, and Kurt Keutzer. 2021\.  A Survey of Quantization Methods for Efficient Neural Network Inference.  _CoRR_ abs/2103.13630 (2021).  arXiv:2103.13630 https://arxiv.org/abs/2103.13630
  * Hassibi and Stork (1992) Babak Hassibi and David Stork. 1992.  Second order derivatives for network pruning: Optimal Brain Surgeon. In _Advances in Neural Information Processing Systems_ , S. Hanson, J. Cowan, and C. Giles (Eds.), Vol. 5. Morgan-Kaufmann.  https://proceedings.neurips.cc/paper/1992/file/303ed4c69846ab36c2904d3ba8573050-Paper.pdf
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * He et al. (2018) Yihui He, Ji Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han. 2018\.  Amc: Automl for model compression and acceleration on mobile devices. In _Proceedings of the European conference on computer vision (ECCV)_. 784–800.
  * Huang et al. (2019) Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, et al. 2019\.  Gpipe: Efficient training of giant neural networks using pipeline parallelism.  _Advances in neural information processing systems_ 32 (2019).
  * Jia et al. (2019a) Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia, and Alex Aiken. 2019a.  TASO: Optimizing Deep Learning Computation with Automatic Generation of Graph Substitutions. In _Proceedings of the 27th ACM Symposium on Operating Systems Principles_ (Huntsville, Ontario, Canada) _(SOSP ’19)_. Association for Computing Machinery, New York, NY, USA, 47–62.  https://doi.org/10.1145/3341301.3359630
  * Jia et al. (2019b) Zhihao Jia, James Thomas, Todd Warszawski, Mingyu Gao, Matei Zaharia, and Alex Aiken. 2019b.  Optimizing DNN Computation with Relaxed Graph Substitutions. In _Proceedings of the 2nd SysML Conference_ _(SysML ’19)_.
  * Jia et al. (2019c) Zhihao Jia, Matei Zaharia, and Alex Aiken. 2019c.  Beyond Data and Model Parallelism for Deep Neural Networks.  _Proceedings of Machine Learning and Systems_ 1 (2019), 1–13.
  * Kjolstad et al. (2017) Fredrik Kjolstad, Shoaib Kamil, Stephen Chou, David Lugato, and Saman Amarasinghe. 2017.  The Tensor Algebra Compiler.  _Proc. ACM Program. Lang._ 1, OOPSLA, Article 77 (Oct. 2017), 29 pages.  https://doi.org/10.1145/3133901
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. 2012\.  ImageNet Classification with Deep Convolutional Neural Networks. In _Advances in Neural Information Processing Systems_ , F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (Eds.), Vol. 25. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2012/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf
  * LeCun et al. (1989) Yann LeCun, John Denker, and Sara Solla. 1989.  Optimal Brain Damage. In _Advances in Neural Information Processing Systems_ , D. Touretzky (Ed.), Vol. 2. Morgan-Kaufmann.  https://proceedings.neurips.cc/paper/1989/file/6c9882bbac1c7093bd25041881277658-Paper.pdf
  * Levin (1973) Leonid Anatolevich Levin. 1973\.  Universal sequential search problems.  _Problemy peredachi informatsii_ 9, 3 (1973), 115–116.
  * Li and Talwalkar (2020) Liam Li and Ameet Talwalkar. 2020.  Random search and reproducibility for neural architecture search. In _Uncertainty in artificial intelligence_. PMLR, 367–377.
  * Li et al. (2020) Muyang Li, Ji Lin, Yaoyao Ding, Zhijian Liu, Jun-Yan Zhu, and Song Han. 2020\.  Gan compression: Efficient architectures for interactive conditional gans. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 5284–5294.
  * Liu et al. (2018b) Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. 2018b.  Progressive Neural Architecture Search. In _Computer Vision – ECCV_ , Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss (Eds.). Springer International Publishing.
  * Liu et al. (2018a) Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. 2018a.  Hierarchical Representations for Efficient Architecture Search. In _International Conference on Learning Representations_ _(ICLR’18)_.  https://openreview.net/forum?id=BJQRKzbA-
  * Luo et al. (2017) Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. 2017.  ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression. 5068–5076.  https://doi.org/10.1109/ICCV.2017.541
  * Narayanan et al. (2019) Deepak Narayanan, Aaron Harlap, Amar Phanishayee, Vivek Seshadri, Nikhil R. Devanur, Gregory R. Ganger, Phillip B. Gibbons, and Matei Zaharia. 2019.  PipeDream: Generalized Pipeline Parallelism for DNN Training. In _Proceedings of the 27th ACM Symposium on Operating Systems Principles_ (Huntsville, Ontario, Canada) _(SOSP ’19)_. Association for Computing Machinery, New York, NY, USA, 1–15.  https://doi.org/10.1145/3341301.3359646
  * Phothilimthana et al. (2021) Phitchaya Mangpo Phothilimthana, Amit Sabne, Nikhil Sarda, Karthik Srinivasa Murthy, Yanqi Zhou, Christof Angermueller, Mike Burrows, Sudip Roy, Ketan Mandke, Rezsa Farahani, Yu Emma Wang, Berkin Ilbeyi, Blake Hechtman, Bjarke Roune, Shen Wang, Yuanzhong Xu, and Samuel J. Kaufman. 2021\.  A Flexible Approach to Autotuning Multi-Pass Machine Learning Compilers. In _2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT)_. 1–16.  https://doi.org/10.1109/PACT52795.2021.00008
  * Phothilimthana et al. (2016) Phitchaya Mangpo Phothilimthana, Aditya Thakur, Rastislav Bodik, and Dinakar Dhurjati. 2016.  Scaling up Superoptimization. In _Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems_ (Atlanta, Georgia, USA) _(ASPLOS’16)_. Association for Computing Machinery, New York, NY, USA, 297–310.  https://doi.org/10.1145/2872362.2872387
  * Polozov and Gulwani (2015) Oleksandr Polozov and Sumit Gulwani. 2015.  FlashMeta: A Framework for Inductive Program Synthesis. In _Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications_ (Pittsburgh, PA, USA) _(OOPSLA’15)_. Association for Computing Machinery, New York, NY, USA, 107–126.  https://doi.org/10.1145/2814270.2814310
  * Real et al. (2019) Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. 2019.  Regularized evolution for image classifier architecture search. In _Proceedings of the aaai conference on artificial intelligence_ , Vol. 33. 4780–4789.
  * Real et al. (2020) Esteban Real, Chen Liang, David R. So, and Quoc V. Le. 2020\.  AutoML-Zero: Evolving Machine Learning Algorithms From Scratch. In _International Conference on Machine Learning_ _(ICML’20)_.  arXiv:2003.03384 https://arxiv.org/abs/2003.03384
  * So et al. (2021) David So, Wojciech Mańke, Hanxiao Liu, Zihang Dai, Noam Shazeer, and Quoc V Le. 2021\.  Searching for Efficient Transformers for Language Modeling. In _Advances in Neural Information Processing Systems_.
  * Tan and Le (2019) Mingxing Tan and Quoc V. Le. 2019.  EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks. In _Proceedings of International Conference on International Conference on Machine Learning_ _(ICML’19)_.  arXiv:2104.00298
  * Tan and Le (2021) Mingxing Tan and Quoc V. Le. 2021.  EfficientNetV2: Smaller Models and Faster Training. In _Proceedings of International Conference on International Conference on Machine Learning_ _(ICML’21)_.  arXiv:2104.00298
  * Turner et al. (2021) Jack Turner, Elliot J. Crowley, and Michael F. P. O’Boyle. 2021\.  Neural Architecture Search as Program Transformation Exploration. In _Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ (Virtual, USA) _(ASPLOS’21)_. Association for Computing Machinery, New York, NY, USA, 915–927.  https://doi.org/10.1145/3445814.3446753
  * Vasilache et al. (2018) Nicolas Vasilache, Oleksandr Zinenko, Theodoros Theodoridis, Priya Goyal, Zachary DeVito, William S. Moses, Sven Verdoolaege, Andrew Adams, and Albert Cohen. 2018\.  Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions.  _arXiv preprint arXiv:1802.04730_ (2018).  arXiv:1802.04730 [cs.PL]
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017\.  Attention is All you Need. In _Advances in Neural Information Processing Systems_ , I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc.  https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * Wang et al. (2017a) Chenglong Wang, Alvin Cheung, and Rastislav Bodik. 2017a.  Synthesizing Highly Expressive SQL Queries from Input-Output Examples. In _Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation_ (Barcelona, Spain) _(PLDI’17)_. Association for Computing Machinery, New York, NY, USA, 452–466.  https://doi.org/10.1145/3062341.3062365
  * Wang et al. (2018) Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yu Chen, and Kailash Gopalakrishnan. 2018.  Training Deep Neural Networks with 8-Bit Floating Point Numbers. In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ (Montréal, Canada) _(NIPS’18)_. Curran Associates Inc., Red Hook, NY, USA, 7686–7695.
  * Wang et al. (2017b) Xinyu Wang, Isil Dillig, and Rishabh Singh. 2017b.  Program Synthesis Using Abstraction Refinement. In _Symposium on Principles of Programming Languages_ _(POPL’17)_. Association for Computing Machinery, New York, NY, USA.  https://doi.org/10.1145/3158151
  * Wei et al. (2016) Tao Wei, Changhu Wang, Yong Rui, and Chang Wen Chen. 2016\.  Network Morphism. In _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ (New York, NY, USA) _(ICML’16)_. 564–572.
  * Yang et al. (2021) Yichen Yang, Mangpo Phitchaya Phothilimtha, Yisu Remy Wang, Max Willsey, Sudip Roy, and Jacques Pienaar. 2021.  Equality Saturation for Tensor Graph Superoptimization. In _MLSys_.  https://arxiv.org/abs/2101.01332
  * Yu et al. (2019) Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. 2019.  Evaluating The Search Phase of Neural Architecture Search. In _International Conference on Learning Representations_.
  * Zhou et al. (2020) Yanqi Zhou, Sudip Roy, Amirali Abdolrashidi, Daniel Wong, Peter Ma, Qiumin Xu, Hanxiao Liu, Phitchaya Phothilimtha, Shen Wang, Anna Goldie, Azalia Mirhoseini, and James Laudon. 2020\.  Transferable Graph Optimizers for ML Compilers. In _NeurIPS 2020_.
  * Zoph and Le (2017) Barret Zoph and Quoc Le. 2017.  Neural Architecture Search with Reinforcement Learning. In _International Conference on Learning Representations_.  https://openreview.net/forum?id=r1Ue8Hcxg
  * Zoph et al. (2018) Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc Le. 2018.  Learning Transferable Architectures for Scalable Image Recognition. In _Conference on Computer Vision and Pattern Recognition_ _(CVPR’18)_. 8697–8710.  https://doi.org/10.1109/CVPR.2018.00907

##  Appendix A Implementation Details

###  A.1. Primitive Operations

Table 1 presents the set of primitive operations we currently support in our
framework. Note that our framework supports evolving models with operations
outside the table, but our subgraph selection mechanism will only select
subgraphs containing operations in the table (and our synthesis procedure will
only synthesize subgraphs using the operations in the table).

Name |  Description |  Parameters
---|---|---
Dense |  Dense layer applied to the output features |  output features
Convolution |  Convolution operator with same padding |  output features, strides (either 1 or equal to kernel), kernel shape (always square)
Grouped Convolution |  Grouped convolution operator with same padding |  output features, strides (either 1 or equal to kernel), kernel shape (always square), feature groups ¿ 1
Dilated Convolution |  Dilated convolution operator with same padding |  output features, strides (either 1 or equal to kernel), kernel shape (always square), input dilation ¿ 1
Add |  Adds two input tensors |
Scalar Multiply |  Multiply input by a scalar |  scalar value
ReLU |  ReLU activation |
GeLU |  GeLU activation |
SiLU |  SiLU activation |
Sigmoid |  Sigmoid activation |
Softmax |  Softmax layer |
Batch Norm |  Batch normalization |
Layer Norm |  Layer normalization |
Group Norm |  Group normalization |  number of groups
Dropout |  Dropout layer |  dropout rate
Average Pool |  Average pooling layer |  window dimension (always square)
Max Pool |  Max pooling layer |  window dimension (always square)
Table 1. Primitive operations that we use to synthesize subgraphs

###  A.2. Structure Mutations for Subgraphs with Multiple Inputs and Outputs

This section provides a high level description of how to support structure
mutations for subgraphs with multiple inputs and outputs. Recall that our
synthesis algorithm first decomposes a subgraph with reshapes and binary
operations into sequential subgraphs connected by reshape and binary
operations. When then mutate each sequential subgraph individually.

####  A.2.1. Reshape Operators

The main challenge with synthesizing sequential subgraphs containing reshape
operators is that in satisfying the mixing property, we can no longer rely on
Corollary D.16, which is defined only for square matrices. For instance, if
the input has 3 dimensions, but the output has 4 dimensions, it is not clear a
priori how to associate the input dimensions with the output dimensions
without fixing in advance the sequence of reshape operations.

One approach is to always synthesize reshape operators in pairs. Every reshape
operator $t$ (e.g., transpose, flatten) has a corresponding inverse $t^{-1}$
such that $t\circ t^{-1}=\text{id}$. Hence, we can always “undo” a reshape
operator if it makes the synthesis problem infeasible. After applying the
reshape operator $t$, we can simultaneously transform the target property via
$t^{-1}(u)$ and continue with synthesis—this new problem is still guaranteed
to be feasible (and will have the same distance as before). At a later point,
we then need to reverse the transformation by applying $t^{-1}$ to the program
and reverting back to $u$ as the target property. This guarantees that the
original properties are satisfied.

In some cases, we may have that $d(t(p),u)<\infty$, i.e., the synthesis
problem is feasible without reversing the reshape operation. In this scenario,
it is safe to continue synthesis without reversing the transformation;
however, we should also limit the number of such reshape operators as there is
no guarantee that $d(t(p),u)\leq d(p,u)$ (which violates the assumption of
progress).

####  A.2.2. Support for Binary Operations

We next describe how to support the insertion and deletion of binary
operations. Namely, whenever we choose to synthesize a binary operation as the
next transformation, we must also synthesize something to fill the other input
slot before proceeding. To accomplish this, we first select a random starting
point, which is either a previously generated operation, or an input to the
subgraph, with the requirement that the shape property from the selected
starting point to the binary input must be feasible. From here, a recursive
call to the sequential synthesizer can generate a subgraph that connects the
selected starting point to the missing input of the binary operation.

To delete a binary operator, we first check whether the operator is necessary
by replacing one of its inputs with a placeholder (constant) input, and
inferring the resulting properties with respect to its output. If the target
properties are satisfied, then we can safely replace the binary operation with
an identity operation, deleting the unneeded input. Note that one way a binary
operation can become unnecessary is if a previous synthesis step already
synthesized another binary operation elsewhere that satisfied the associated
properties.

Finally, combining the ability to insert and delete binary operations yields
the desired mutation of subgraph structures.

###  A.3. Evolutionary Neural Architecture Search

In this section, we describe our evolutionary framework for NAS. Our design is
based on the evolutionary algorithm of Real et al. (2019), except that we do
not perform the age regularization due to only running the evolutionary search
for 800 individuals.

In order to support multi-objective optimization, we develop a notion of
weighting individuals based on their Pareto optimality. A point is Pareto
optimal with respect to multiple objectives if no other point is a strict
improvement on all objectives.

We assume that all objectives trade-off against a single primary objective; in
our case, the goal is always to maximize accuracy versus the various secondary
objectives. We define the Pareto weight of an individual as the shortest
distance (in the $\ell_{2}$ sense) from the individual to the Pareto curve,
which is built by linearly interpolating the Pareto-optimal points. Lower
Pareto weights correspond to better Pareto optimality; Pareto optimal points
having a Pareto weight of 0.

However, as this distance is not invariant to units, we also perform a
normalization in each dimension. To compute the normalization factor, we
simply compute the average slope of the full Pareto curve, which is equivalent
to the slope of the two endpoints. The idea is that this slope captures an
average notion of how difficult it is to trade off between the two objectives.

Algorithm 2 Evolutionary selection mechanism

1:set of candidates $M$, primary objective $o_{p}$, set of secondary
objectives $O_{s}$, percentage $k$

2:candidate to be mutated

3:Randomly select a secondary objective $o_{s}\in O_{s}$

4:Build the Pareto curve $C$ of the primary objective $o_{p}$ versus the
secondary objective $o_{s}$

5:Compute $W=\\{w_{i}\ |\ w_{i}=$ Pareto weight of $m_{i}\in M$ with respect
to $C\\}$

6:$M_{\text{top}}=$ top $k\%$ of $M$ according to $W$

7:return Random $m\in M_{\text{top}}$

Algorithm 2 provides a summary of our selection mechanism. This process is
repeated independently each time a new individual is requested for mutation,
with the current population of individuals as the input.

##  Appendix B Experimental Setup and Additional Experimental Results

###  B.1. Experimental Setup

Table 2 summarizes the setup of our experiments.

For the ResNet architectures (ResNet-34, ResNet-50), we train for 90 epochs
using SGD with base learning rate 0.1, momentum 0.9, and weight decay 0.0004.
The learning rate warms up over 5 epochs then follows a cosine decay schedule.
We also add a nonstandard dense layer between the head and the first block, to
project the feature dimension from 3 to 64, so that all the blocks have the
same shape signature and hence type (the first block is otherwise a singleton
type).

For the ViT-S/16 architecture, we train for 90 epochs using the Adam
optimizer, with base learning rate .003, beta1 = 0.9, and beta2 = 0.999. The
learning rate warms up over 10,000 batches, then follows a cosine decay
schedule down to .00001.

For the EfficientNet-B0 architecture, we follow the same setting as the
original paper (Tan and Le, 2019), except that we train for 90 epochs. We use
the RMSProp optimizer, with a base learning rate of 0.016. The learning rate
warms up over 5 epochs, then decays exponentially down to 0.012. We also use
exponential moving average with decay 0.9999.

We use standard Inception-style data augmentation for training on ImageNet,
and train and test at 224$\times$224 resolution.

Experiment | Dataset | Base Model | Accuracy | Trials | Epochs | Secondary Objectives
---|---|---|---|---|---|---
Case Studies | CIFAR-10 | 2-layer CNN | 81.3% | 400 | 90 | flops, parameter count
(Section 6.1) |  | ResNet-34 | 91.5% | 400 | 90 | flops, parameter count
| ImageNet | ResNet-50 | 75.7% | 400 | 90 | flops, training throughput
|  | ViT-S/16 | 70.4% | 400 | 90 | flops, training throughput
|  | EfficientNet-B0 | 72.8% | 400 | 90 | flops, training throughput
Property Ablation | CIFAR-10 | ResNet-34 | 91.5% | 800 | 90 | flops, parameter count
(Section B.3, |  |  |  |  |  |
Section 6.2.1, |  |  |  |  |  |
Section B.2) |  |  |  |  |  |
Synthesis Ablation | CIFAR-10 | ResNet-34 | 91.5% |  800‡ | 90 | flops, parameter count
(Section 6.2.2, |  |  |  |  |  |
Section B.4) |  |  |  |  |  |
Comparison with | CIFAR-10 | ResNet-34 | 91.5% | 800 | 90 | flops, parameter count
Existing Approaches |  |  |  |  |  |
(Section 6.3, |  |  |  |  |  |
Section B.5) |  |  |  |  |  |
Table 2. Training setup for the experiments. We initialize the search with the
base model and run the search for a given number of trials; each trial
involves training a proposed candidate for a given number of epochs. the
accuracy column indicates the accuracy of the base model on the dataset. ‡The
enumerative search comparison uses only 600 trials, due to the enumerative
synthesis being very slow.

###  B.2. Random Subgraph Ablations

We additionally varied the expected size of the subgraph synthesized by the
random subgraph strategy in Figs. 17(a), 17(b) and 17(c). In particular, we
select a random subgraph of expected size 3 for mutation. Then, we synthesize
a single (random) operation. At this point, we stop and return the current
subgraph with probability $1-p$. Otherwise, we synthesize another (random)
operation and repeat. Hence, the expected subgraph size is $1+1/(1-p)$. For
instance, the plot for $p=0.2$ synthesizes subgraphs of size roughly 2 on
average, which represents fairly small mutations; correspondingly, we see that
the performance is the best of the three random subgraph strategies, and also
similar to the performance of the AutoML-Zero and Primer strategies. At
$p=0.5$, the expected subgraph size is 3 and there is a rapid decline in
quality. The worst setting is at $p=0.75$, with an expected random subgraph of
size 5. Note that Fig. 17(b) is the same as Fig. 15 in the main text.

Figs. 17(a), 17(b) and 17(c) demonstrate that the performance of random search
degrades very rapidly as we increase the (expected) size of the mutation from
2 to 5, to the point where there is practically no progress on improving
either FLOPS or parameter count at $p=0.75$. In contrast, $\alpha$NAS with
property-guided synthesis consistently discovers mutations that improve
performance at size $p=0.75$ in the same setting (and outperforms the random
search at all mutation sizes).

(a) Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. a random
subgraph mechanism with p=.20.

(b) Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. a random
subgraph mechanism with p=.50.

(c) Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. a random
subgraph mechanism with p=.75.

Figure 17. Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. a
random subgraph mechanism with varying expected sizes

###  B.3. Program Property Ablations

To evaluate the contributions of the proposed program properties, we compare
$\alpha$NAS using the standard properties and mutations with the modified
variants in Table 3. For this experiment, we train a ResNet-34 on CIFAR-10.
For all the variants, the synthesized subgraph must be at least the size of
the original subgraph minus 2. The results of our comparisons are shown in
Figs. 18, 19, 20, 21 and 22. Using a single program property allows the search
to discover architectures closer to Pareto optimal compared to using no
properties, but using a single property is still visibly inferior to the
baseline. When using all three properties without mutations, the outcome is
quite similar to the baseline in the medium to high FLOPS region. We attribute
this behavior to the search being biased toward proposing more expensive
architectures without property mutations: because a subgraph satisfies the
target properties so long as its properties exceed the target, without
mutations to decrease property values, the target property values can only
increase over time.

Variant |  Description
---|---
No Properties |  Use no program properties to guide synthesis (same as the random subgraph strategy).
Mixing Only |  Use only the mixing property to guide synthesis.
Depth Only |  Use only the depth property to guide synthesis.
Shape Only |  Use only the shape property to guide synthesis.
No Mutate |  Use all three properties to guide synthesis but do not mutate properties.
Baseline |  Use all three properties to guide synthesis and mutate properties.
Table 3.  Different variants of $\alpha$NAS to evaluate the benefit of each
program property. Figure 18. Evolving a ResNet-34 model on CIFAR-10 using the
baseline approach vs. no properties. Figure 19. Evolving a ResNet-34 model on
CIFAR-10 using the baseline approach vs. mixing property only. Figure 20.
Evolving a ResNet-34 model on CIFAR-10 using the baseline approach vs. depth
property only. Figure 21. Evolving a ResNet-34 model on CIFAR-10 using the
baseline approach vs. shape property only. Figure 22. Evolving a ResNet-34
model on CIFAR-10 using the baseline approach vs. no mutations.

###  B.4. Progressive vs. Enumerative Synthesis

In this section, we compare the performance of $\alpha$NAS when using
progressive vs. enumerative synthesis to perform the concretization step as
described in Section 6.2.2. In theory, both synthesis algorithms should
produce similar outcomes in terms of the quality of the candidates explored,
as they use the same set of abstract properties to guide the search. The main
difference is that the enumerative synthesis is much slower than the
progressive synthesis.

Fig. 23 presents the distributions of the candidates explored using the two
synthesis algorithms. Since enumerative synthesis always returns the smallest
subgraph that satisfies the target properties, while progressive synthesis may
not, enumerative synthesis is biased toward smaller subgraphs. Nevertheless,
the performance of enumerative synthesis is substantially similar to the
performance of progressive synthesis (and is by far the most similar of the
other synthesis approaches we consider).

Figure 23. Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. the
enumerative search mechanism. Due to enumerative synthesis being slow, we
compare it with $\alpha$NAS over 600 trials.

###  B.5. Comparison with AutoML-Zero

Fig. 24 shows the result when comparing $\alpha$NAS and AutoML-Zero as
described in Section 6.3.

Figure 24. Evolving a ResNet-34 model on CIFAR-10 using $\alpha$NAS vs. the
AutoML-Zero search mechanism.

##  Appendix C Abstract Progressive Synthesis

We first redefine the relevant notions using the lens of abstract
interpretation:

###### Definition C.1.

Given a program property $\Pi=(\mathcal{V},\leq,\alpha)$ and an abstract
interpretation $\alpha$, an abstract distance function is a function
$d^{\alpha}:\mathcal{V}\times\mathcal{V}\mapsto\mathbb{R}^{+}\cup\\{\infty\\}$
such that:

  1. (1)

$d^{\alpha}(u,v)\geq 0$ for all $u,v\in\mathcal{V}$.

  2. (2)

$d^{\alpha}(u,v)=0\iff u\geq v$.

  3. (3)

$d^{\alpha}(u,v)=\infty$ $\iff$ there exists $p\in\mathcal{P}$ such that (1)
$p\models u$, but (2) there does not exist any finite sequence of
transformations $t=t_{1}\circ t_{2}\circ\cdots\circ t_{n}$ such that
$t(p)\models v$.

###### Definition C.2.

Given a space of programs $\mathcal{P}$, a program property
$\Pi=(\mathcal{V},\leq,\alpha)$, an abstract interpretation $\alpha$, and an
abstract distance function $d^{\alpha}$, a set of transformations
$T\subseteq\mathcal{T}$ is an abstract covering if for all $u,v\in\mathcal{V}$
with $d^{\alpha}(u,v)>0$, either (1) there exists $t\in T$ such that
$d^{\alpha}(t^{\alpha}(u),v)<d^{\alpha}(u,v)$ or (2) $d^{\alpha}(u,v)=\infty$.

###### Definition C.3.

An abstract covering $T$ is a uniform abstract covering if there exists a
constant $\epsilon>0$ such that for all properties $u,v\in\mathcal{V}$ with
$d^{\alpha}(u,v)>0$, there exists $t\in T$ such that

(17) $\displaystyle d^{\alpha}(t^{\alpha}(u),v)+\epsilon\leq d^{\alpha}(u,v)$

We have the following guarantees for the abstract version of the greedy
progressive synthesis algorithm, where we instead provide as input an initial
program property value $\alpha(p_{0})=u$, a target property value $v$, an
abstract distance function $d^{\alpha}$, and an abstract uniform covering $T$:

###### Theorem C.4.

Given an abstract distance function $d^{\alpha}$ and an abstract uniform
covering $T$, the progressive synthesis algorithm satisfies the following
three properties:

  1. (1)

Soundness: if the algorithm returns $u^{*}=(t^{\alpha}_{n}\circ\cdots\circ
t^{\alpha}_{1})(u)$, then $u^{*}\geq v$.

  2. (2)

Completeness: if the algorithm returns $\not\models$, then the synthesis task
is infeasible.

  3. (3)

Progress: the algorithm terminates after a finite amount of time, which is
linear in the length of the final sequence of transformations and linear in
$|T|$.

We omit the proof as it is identical to the proof of Theorem 4.4 except with
the abstract semantics $t^{\alpha}$ substituted for the concrete semantics
$t$. Note that the only difference with the statement of Theorem 4.4 is the
first soundness property, which is stated in terms of the abstract semantics
$u^{*}\geq v$ instead of the corresponding concrete semantics
$p^{*}=(t_{n}\circ\cdots\circ t_{1})(p_{0})$. The key is that the soundness
property of the abstract interpretation allows us to translate this into the
required form:

###### Lemma C.5.

If $\alpha(p_{0})=u$ and $d^{\alpha}((t_{n}^{\alpha}\circ\cdots\circ
t_{1}^{\alpha})(u),v)=0$, then $p^{*}=(t_{n}\circ\cdots\circ
t_{1})(p_{0})\models v$.

###### Proof.

By definition, $d^{\alpha}((t_{n}^{\alpha}\circ\cdots\circ
t_{1}^{\alpha})(u),v)=0$ implies that $(t_{n}^{\alpha}\circ\cdots\circ
t_{1}^{\alpha})(u)=u^{*}\geq v$. By the soundness property of abstract
interpretations, since $p_{0}\models u$, it follows that
$p^{*}=(t_{n}\circ\cdots\circ t_{1})(p_{0})\models u^{*}$. Putting these two
facts together yields $p^{*}\models v$. ∎

###### Corollary C.6.

Running the progressive synthesis algorithm with an _abstract_ distance
function and an _abstract_ uniform covering also achieves soundness with
respect to the _concrete semantics_ , i.e., if the algorithm returns
$u^{*}=(t^{\alpha}_{n}\circ\cdots\circ t^{\alpha}_{1})(u)$, then
$p^{*}=(t_{n}\circ\cdots\circ t_{1})(p_{0})\models v$.

##  Appendix D Deferred Proofs

###  D.1. Abstract Semantics of the Mixing Property

###### Proof of Lemma 3.7.

Given two subgraphs $p$ and $q$, where $u=\alpha_{M}(p)$, we need to show that
$q^{\alpha}_{M}(u):=\alpha_{M}(q)\times u$ is an abstract interpretation,
i.e., $\alpha_{M}(q)\times u\leq\alpha_{M}(q\circ p)$.

Denote the input tensor as $I$, the intermediate output $p(I)$ as $P$, and the
output of the subgraph $q(P)=(q\circ p)(I)$ as $O$. We begin by showing that
$q^{\alpha}_{M}$ is an abstract interpretation for 1-dimensional inputs and
outputs, i.e., when $I$, $P$, and $O$ are all 1-dimensional tensors. First we
establish the safety of the pairing property, which corresponds to sufficient
conditions for when $\alpha_{M}(q\circ p)>\texttt{x}{}$. Note that when both
$q$ and $p$ pair their respective inputs and outputs, then so does their
composition (since the preimage of $O$ in $P$ is the entire slice, and the
preimage of $P$ in $I$ is also the entire slice, hence the preimage of $O$ in
$I$ is also the entire slice). Thus, we can safely define $\alpha_{M}(q)\times
v=\texttt{x}{}$ if $v=\texttt{x}{}$ or $u=\alpha_{M}(q)=\texttt{x}{}$. This
yields the first row and first column of Fig. 7.

Otherwise, both $u$ and $v$ are greater than x (i.e., one of o, m, or a). When
either $u$ or $v$ have all-to-one locality, so does $q(p)$: if $q$ is all-to-
one, then the preimage of a single element in $O$ is the entire slice of $P$
(and since $p$ has at least one-to-one locality, the preimage in $I$ is also
the full slice); if $p$ is all-to-one, then the preimage of a single element
in $O$ is at least an element of $P$, and so tracing back through $p$ yields
the preimage is again the full slice of $I$. So we can define
$\alpha_{M}(q)\times v=\texttt{a}{}$ if either $u=\alpha_{M}(q)=\texttt{a}{}$
or $v=\texttt{a}{}$ (and neither $u$ nor $v$ is x). This yields the remaining
entries of Fig. 7 in the last row and last column.

Finally, the only situation in which $q\circ p$ has one-to-one locality is
when both $q$ and $p$ are one-to-one; the remaining entries must be many-to-
one. This completes the definition of $\alpha_{M}(q)\times v=u*v$ as given in
Fig. 7.

When the tensors are higher dimensional, to determine whether a dimension $x$
in $I$ and $z$ in $O$ are paired, we need to check whether there exists some
dimension $y$ in $P$ which is paired with both $x$ and $z$. The locality is
the maximum locality over all paired dimensions $y$ in $P$, which corresponds
to the definition of $+$ in Lemma 3.7. Hence we see the computation is exactly
a matrix multiplication, and $q^{\alpha}_{M}(u):=\alpha_{M}(q)\times u$ is an
abstract interpretation as claimed. ∎

###  D.2. Complexity of Progressive Synthesis

This section culminates in the statement and proof of the formal version of
Theorem 4.5. We first clarify how “length” is measured for a sequence of
transformations $(t_{1},\ldots,t_{n})\in\mathcal{T}^{n}$. Note that taking the
length to be $n$ is not well-defined since $\mathcal{T}$ is the set of all
finite length strings $E^{*}$; in particular, $\tau=t_{n}\circ\cdots\circ
t_{1}\in\mathcal{T}$, i.e., any sequence of transformations is always
functionally equivalent to a singleton transformation.

Instead, we define a string representation of any sequence of transformations
$(t_{1},\ldots,t_{n})$ to be the string representation of the composed
transformation $\tau=t_{n}\circ\cdots\circ t_{1}$ (recall that this is defined
since $\tau\in\mathcal{T}$, and elements of $\mathcal{T}$ are also strings
over $E$). This yields the following equivalence relation over sequences of
transformations:

###### Definition D.1.

Let $t=(t_{1},\ldots,t_{n})$ and $s=(s_{1},\ldots,s_{m})$ be two sequences of
transformations. Then $t$ and $s$ are representationally equivalent, denoted
as $t\sim s$, if their string representations are lexicographically equal.