Hierarchical Representations for Efficient Architecture Search

Neural networks moved from simple chain-like CNNs toward increasingly graph-structured topologies such as Inception, ResNet, DenseNet, and other multi-branch designs. NAS aims to automate what used to be slow trial-and-error by human experts, with representative approaches including reinforcement learning NAS (e.g., Zoph & Le; Zoph et al.), evolutionary search (Xie & Yuille; Real et al.; Miikkulainen et al.), Monte Carlo Tree Search, and weight-prediction-based random methods. Yet evaluating each architecture is expensive because it usually requires training a model. Prior work often shrank the search space aggressively; this paper instead argues for a more expressive, hierarchical encoding that retains searchability while preserving rich topology.

The problem is to find high-performing neural architectures under severe compute constraints. Formally, one wants an architecture that maximizes validation accuracy, but each candidate is costly to evaluate and the search space grows combinatorially with graph size and operator choices. Flat spaces may be too restrictive; overly unconstrained spaces become intractable. The key bottleneck is balancing expressivity, diversity, and evaluation cost, while avoiding an encoding that biases search toward trivial or oversized models.

1) Hierarchical genetic representation: architectures are encoded as multiple levels of motifs, not a single flat graph. This is needed to capture reusable building blocks and complex topologies.

2) Recursive assembly: motifs are constructed bottom-up with assemble(G,o), so a mutation at one level can affect the whole network. This differs from flat encodings where local edits stay local.

3) Asynchronous distributed evolution: a controller-worker design keeps all GPUs occupied and removes synchronization barriers, making large-scale evaluation practical.

4) Diversified initialization: the population starts from a trivial identity-chain genotype and is diversified by many random mutations, avoiding handcrafted bias.

5) Strong random-search baseline: the paper demonstrates that a well-designed space plus simple sampling can already reach competitive accuracy, isolating representation as the main ingredient.

• �� Representation: a genotype is (G,o), where G is an adjacency matrix and Gij=k means operation ok is placed on edge (i,j).
• �� Hierarchy: level-ℓ motifs are assembled from level-(ℓ−1) motifs; the top level is the full architecture and the bottom level is the primitive operator set plus a none op.
• �� Primitives: 1×1 conv, 3×3 depthwise conv, 3×3 separable conv, 3×3 max-pooling, 3×3 average-pooling, identity; convolutions use BN+ReLU and fixed channel count C.
• �� Mutation: sample a target level, motif, successor node i, predecessor node j, and replacement op k′; then set [G(ℓ)m]ij=k′. This can add, alter, or delete edges.
• �� Initialization: build an identity-only genotype, then apply about 1000 random mutations to diversify the initial population and avoid manual initialization heuristics.
• �� Evolution: tournament selection uses 5% of the population, the population is never pruned, and each candidate is trained from scratch for a fixed budget before fitness evaluation.
• �� Implementation: ASYNCEVO is fully asynchronous; the controller mutates selected genotypes into a queue, and workers pop candidates, assemble models, train them, and write validation accuracy back to shared memory.
• �� Evaluation strategy: search is performed on CIFAR-10 cells, then the discovered cell is transferred into larger CIFAR-10 and ImageNet models for final testing.

Search is carried out entirely on CIFAR-10, splitting the training set into 40K training and 10K validation images; the test set is reserved for final reporting. The authors compare flat versus hierarchical representations, random search versus evolution, and an unconstrained flat encoding versus a parameter-constrained one. They run 7000 evolution steps with 200 GPU workers. Fitness models are intentionally small (c0=16, N=1, 5000 SGD steps, batch size 256, learning rate 0.1 decayed at 4000 and 4500 steps), while final evaluation uses larger CIFAR-10 models (c0=64 or 128, N=2, 80K steps) and an ImageNet model (299×299 input, 4 cell groups, 200K steps, batch size 1024).

The hierarchical encoding is better than the flat one at similar search cost: flat evolution yields 3.92% ± 0.06 CIFAR-10 error, while hierarchical evolution yields 3.75% ± 0.12. When the flat baseline is constrained to a similar parameter budget, performance drops to 4.17% ± 0.08, showing that the hierarchy itself matters. Random search is a particularly strong baseline: hierarchical random search with 200 samples reaches 4.04% ± 0.2 on CIFAR-10 and 20.4%/5.3% on ImageNet. The best hierarchical-evolution model achieves 3.63% ± 0.10 on CIFAR-10 and 20.3%/5.2% on ImageNet, competitive with strong NAS systems.

In practice, the method is most relevant for automated design of convolutional backbones. A team can search cells on a smaller proxy task, transfer them into larger models, and use the resulting architectures for image classification pipelines, feature extractors, or embedded/edge models where manual design is costly. It is also a valuable baseline for NAS research: if a new method does not beat strong random search in a rich space, its advantage may be illusory.

The approach remains compute-intensive because every candidate is trained from scratch, and the paper explicitly notes non-negligible optimization variance, averaging four runs for fitness. The search space is still image-centric and convolutional, so the method’s reach beyond classification remains untested. Finally, random search comes very close to evolution, implying that the main bottleneck is not the evolutionary rule itself but the design of the search space and the inductive bias it encodes.