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.