Expressive Neural Architecture Search (NAS) search spaces are desirable as they do not restrict the space of potential architectures to what is already established. However, few search spaces are expressive enough to represent a broad range of architecture families, and those that are have focused primarily on image classification problems. The task of autoregressive sequence modelling has become ubiquitous in modern machine learning, but no existing search space supports the construction of and search over sequence models from fundamental operations, instead imposing strong inductive biases on the structure of potential architectures. This work describes how the expressive einspace search space can be extended to yield a search space capable of representing autoregressive models using fundamental operations. We perform a series of experiments showing that the novel einspaceAR search space can find capable autoregressive sequence models from scratch--i.e., without imposing strong inductive biases. We believe that our einspaceAR search space will be a useful part of the NAS toolbox and that the techniques described in this work can serve as a blueprint for the integration of autoregressive modelling in other expressive search spaces.
Figures & tables
Figure 1: Architectures expressed in our einspaceAR , where the black node is the input and the red node is the output. The Transformer model has 2 layers, with 2 attention heads. ARCH1 and ARCH6 are capable sequence models found from scratch using NAS. See table 1 and 2 for experimental results.
Figure 2: Overview of the context-free grammar (CFG), which the search spaces are based on. Black symbols and red symbols are in einspace , with red removed and green added in einspaceAR .
Baselines
NAS from Scratch
Difficulty
Task
Transformer
Mamba
einspaceAR
ARCH1
ARCH2
ARCH3
Normal
Recall
99.95±0.04
99.92±0.02
99.96±0.03
99.90±0.01
99.95±0.03
Fuzzy Recall
49.03±6.70
12.80±0.30
33.20±5.28
11.95±3.84
7.21±0.20
Noisy Recall
99.93±0.03
99.93±0.02
99.97±0.01
99.09±1.43
99.95±0.02
Selective Copying
99.93±0.01
99.84±0.09
80.59±0.19
80.56±0.01
80.53±0.18
Table 1: Accuracies on the 6 MAD ( Poli et al., 2024 ) tasks. We search our einspaceAR search space three times per difficulty. The results show that einspaceAR finds architectures that approach the performance of the baselines. The baselines and NAS architectures are trained and evaluated three times on each task resulting in the reported mean and standard deviation. The NAS-found architectures are strictly smaller than the corresponding baseline architectures with details on parameter counts in appendix A.4 .
Baselines
NAS from Scratch
NAS from Seed
Dataset
GPT2
Mamba
einspaceAR
einspaceAR (GPT2)
TinyShakespeare
6.14±0.11
5.89±0.13
6.11±0.14
5.66±0.12
BabiStories
9.00±0.04
9.95±0.03
18.36±1.93
9.12±0.13
Table 2: Perplexities on the TinyShakespeare ( Karpathy, 2015 ) and BabiStories ( Zhang et al., 2024 ) text datasets. Our einspaceAR works well for TinyShakespeare, matching baseline performance when searching from scratch and improving the seed. However, it struggles in the BabiStories case. The baselines are trained and evaluated 3 times, the NAS search is run 3 times for each setting with the resulting architectures trained and evaluated 3 times. The resulting 3 and 9 values lead to the presented means and standard deviations.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
MAD
TinyShakespeare
BabiStories
Optimizer
AdamW
AdamW
AdamW
Base learning rate
0.0005
0.001
0.001
Min learning rate
0.000001
0.0001
0.0001
Learning rate schedule
cosine
cosine
cosine
Weight decay
0.0
0.1
0.1
Batch size
128
64
32
Appendix
Table 3: Training hyperparameters for MAD, TinyShakespeare, and BabiStories baselines.
Setting
MAD
TinyShakespeare
BabiStories
cr
fr
nr
sc
comp
mem
normal
228,880
228,880
232,992
228,880
262,672
290,560
10,770,881
19,312,256
hard
257,664
257,664
290,560
257,664
275,008
2,330,112
-
-
Appendix
Table 4: Transformer parameter counts for the different tasks under normal and hard settings. The language modelling tasks don’t have a hard setting.
Difficulty
Task
Sequence Length
Vocab Size
Num Train Examples
Normal
Context Recall
128
16
12800
Fuzzy Recall
128
16
12800
Noisy Recall
128
32
12800
Selective Copying
256
16
12800
Compression
32
16
12800
Memorization
32
256
256
Appendix
Table 5: MAD task settings. For Noisy Recall, the noise vocab size is half the vocab size and noise fraction is 0.2 for both difficulties. Selective Copying uses num_copy=16 for both difficulties. Fuzzy Recall uses motif sizes k=v=3 for both difficulties.
NAS from Scratch
Difficulty
Task
einspaceAR
einspaceARR
R1
R2
R3
R1
R2
R3
Normal
Recall
99.96
99.92
99.90
99.93
-
-
Fuzzy Recall
68.03
12.23
8.54
61.59
47.03
32.02
Noisy Recall
99.93
99.91
94.50
99.91
-
-
Selective Copying
82.09
81.92
81.25
99.75
99.57
99.19
Appendix
Table 6: MAD Task specific results as described in appendix C.2 .
Figure 4: Computation production rule of einspaceARR . All other production rules are identical to those of einspaceAR shown in figure 2 . Green symbols are added in einspaceAR ; blue symbols are the recurrence primitives, which are only part of einspaceARR .
Figure 5: A 2-layer Mamba model ( Gu & Dao, 2023 ) expressed in einspaceARR , where the black node is the input and the red node is the output. Representing Mamba requires the s6 recurrence primitive and is therefore not possible in einspaceAR .
Baselines
NAS from Scratch
Difficulty
Task
Transformer
Mamba
einspaceARR
ARCH-R1
ARCH-R2
ARCH-R3
Normal
Recall
99.95±0.04
99.92±0.02
99.97±0.02
99.94±0.02
99.95±0.04
Fuzzy Recall
49.03±6.70
12.80±0.30
42.22±11.10
19.11±3.10
8.07±0.49
Noisy Recall
99.93±0.03
99.93±0.02
99.94±0.03
99.94±0.03
99.97±0.03
Selective Copying
99.93±0.01
99.84±0.09
99.35±0.16
97.54±2.99
78.50±0.42
Appendix
Table 7: Accuracies of architectures found in einspaceARR on the 6 MAD ( Poli et al., 2024 ) tasks. As for einspaceAR (Table 1 ), we run the search from scratch three times per difficulty. The baseline results are repeated from Table 1 for convenience. The baselines and NAS architectures are trained and evaluated three times on each task, resulting in the reported mean and standard deviation. The NAS-found architectures are strictly smaller than the corresponding baseline architectures (appendix A.4 ).
Figure 7: Derivation trees for the six autoregressive architectures found for the MAD task.
Neural architecture search (NAS) faces a challenge in balancing the exploration of expressive, broad search spaces that enable architectural innovation with the need for efficient evaluation of architectures to effectively search such spaces. We investigate surrogate model training for improving search in highly expressive NAS search spaces based on context-free grammars. We show that i) surrogate models trained either using zero-cost-proxy metrics and neural graph features (GRAF) or by fine-tuning an off-the-shelf LM have high predictive power for the performance of architectures both within and across datasets, ii) these surrogates can be used to filter out bad architectures when searching on novel datasets, thereby significantly speeding up search and achieving better final performances, and iii) the surrogates can be further used directly as the search objective for huge speed-ups.
Shiwen Qin, Gabriela Kadlecová, Martin Pilát +5
University of Edinburgh · Charles University, Faculty of Mathematics and Physics · The Czech Academy of Sciences, Institute of Computer Science +1
Neural architecture search (NAS) in expressive search spaces is a computationally hard problem, but it also holds the potential to automatically discover completely novel and performant architectures. To achieve this we need effective search algorithms that can identify powerful components and reuse them in new candidate architectures. In this paper, we introduce two adapted variants of the Smith-Waterman algorithm for local sequence alignment and use them to compute the edit distance in a grammar-based evolutionary architecture search. These algorithms enable us to efficiently calculate a distance metric for neural architectures and to generate a set of hybrid offspring from two parent models. This facilitates the deployment of crossover-based search heuristics, allows us to perform a thorough analysis on the architectural loss landscape, and track population diversity during search. We highlight how our method vastly improves computational complexity over previous work and enables us to efficiently compute shortest paths between architectures. When instantiating the crossover in evolutionary searches, we achieve competitive results, outperforming competing methods. Future work can build upon this new tool, discovering novel components that can be used more broadly across neural architecture design, and broadening its applications beyond NAS.
Adri Gómez Martín, Felix Möller, Steven McDonagh +5
Carlos III University of Madrid · Instituto de Investigación Sanitaria Gregorio Marañón · Helmholtz-Zentrum Berlin für Materialien und Energie +3
Neural Architecture Search (NAS) deployment in industrial production systems faces a fundamental validation bottleneck: verifying a single candidate architecture pi requires evaluating the deployed ensemble of M models, incurring prohibitive O(M) computational cost per candidate. This cost barrier severely limits architecture iteration frequency in real-world applications where ensembles (M=50-200) are standard for robustness. This work introduces Ensemble-Decoupled Architecture Search, a framework that leverages ensemble theory to predict system-level performance from single-learner evaluation. We establish the Ensemble-Decoupled Theory with a sufficient condition for monotonic ensemble improvement under homogeneity assumptions: a candidate architecture pi yields lower ensemble error than the current baseline if rho(pi) < rho(pi_old) - (M / (M - 1)) * (Delta E(pi) / sigma^2(pi)), where Delta E, rho, and sigma^2 are estimable from lightweight dual-learner training. This decouples architecture search from full ensemble training, reducing per-candidate search cost from O(M) to O(1) while maintaining O(M) deployment cost only for validated winners. We unify solution strategies across pipeline continuity: (1) closed-form optimization for tractable continuous pi (exemplified by feature bagging in CTR prediction), (2) constrained differentiable optimization for intractable continuous pi, and (3) LLM-driven search with iterative monotonic acceptance for discrete pi. The framework reveals two orthogonal improvement mechanisms -- base diversity gain and accuracy gain -- providing actionable design principles for industrial-scale NAS. All theoretical derivations are rigorous with detailed proofs deferred to the appendix. Comprehensive empirical validation will be included in the journal extension of this work.