EvoPrompting: Language Models for Code-Level Neural Architecture Search
Authors: Angelica Chen
David Dohan
David So
Venue: NeurIPS 2023 poster (2023)
Keywords: language models
evolution
prompting
neural architecture search
code generation

Abstract: Given the recent impressive accomplishments of language models (LMs) for code generation, we explore the use of LMs as general adaptive mutation and crossover operators for an evolutionary neural architecture search (NAS) algorithm.
While NAS still proves too difficult a task for LMs to succeed at solely through prompting, we find that the combination of evolutionary prompt engineering with soft prompt-tuning, a method we term EvoPrompting, consistently finds diverse and high performing models. We first demonstrate that EvoPrompting is effective on the computationally efficient MNIST-1D dataset, where EvoPrompting produces convolutional architecture variants that outperform both those designed by human experts and naive few-shot prompting in terms of accuracy and model size. We then apply our method to searching for graph neural networks on the CLRS Algorithmic Reasoning Benchmark, where EvoPrompting is able to design *novel* architectures that outperform current state-of-the-art models on 21 out of 30 algorithmic reasoning tasks while maintaining similar model size. EvoPrompting is successful at designing accurate and efficient neural network architectures across a variety of machine learning tasks, while also being general enough for easy adaptation to other tasks beyond neural network design.

EvoPrompting: Language Models for Code-Level Neural Architecture Search
Angelica Chen"
David M. Dohan'
New York University
OpenAl
angelica.chennnyuu edu
david@ddohan.com com
David R. So Jane Street
david. r. so. a..aaii aaiigmmallcoom com
Abstract
Given the recent impressive accomplishments of language models (LMs) for code generation, we explore the use of LMs as general adaptive mutation and crossover operators for an evolutionary neural architecture search (NAS) algorithm. While NAS still proves too difficult task for LMs to succeed at solely through prompting, we find that the combination of evolutionary prompt engineering with soft prompt- tuning, a method we term EVOPROMPTING, consistently finds diverse and high the
performing models. We first demonstrate that EVOPROMPTING is effective computationally efficient MNIST-1D 1D dataset, where EVOPROMPTING produces convolutional architecture variants that outperform both those designed by human experts and naive few-shot prompting in terms of accuracy and model size. We then apply our method to searching for graph neural networks on the CLRS Algorithmic Reasoning Benchmark, where EVOPROMPTING is able to design novel architec- tures that outperform current state-of of-the-ar models on 21 out of 30 algorithmic reasoning tasks while maintaining similar model size. EVOPROMPTING is success- ful at designing accurate and efficient neural network architectures across variety machine learning tasks, while also being general enough for easy adaptation to other tasks beyond neural network design.
Introduction
Scaling of Transformers (Vaswani et al., (017)) has produced language models (LM) with impressive performance. Beyond achieving of results on conventional natural language processing tasks, these LMs demonstrate breakthrough technical capabilities, such as learning how to code (Chen al. 2021), doing math (Noorbakhsh al. (021). and solving reasoning problems (Weil et al. 2022). 2. Yet, despite these strides, several works have noted LMs' current limitations in solving complex problems and creating novel solutions (Qian al. 2022 Dakhel al. 2022). In this work, we improve upon a base LM's ability to propose novel and diverse solutions to complex reasoning problems by iteratively evolving in-context prompts and prompt-tuning the LMM We call this technique EvoProMPTING and demonstrate its success on the difficult task of deep learning architecture design. Our key finding is that, while LMs perform poorly at designing novel and effective neural architectures via naive few-shot prompting, EVoPROMPTING enables LMs to create novel and effective deep neural architectures, particularly when combined with prompt-tune -uniigg methods.
Work done while Student Researcher Google DeepMind. Work done while at Google DeepMind.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Generate chidd code sampres
Initielize seed code semples
class Hededine extcat: peders Dn
Train and Evaluste
generated models
Heak ratice 1.00
07 7 Lry
Crossceer and musation
Ont round
Aipsnn 6900
prompting
Mireas -0000-0000000 -0.0 240
Pro Pre-trained LLM
Select and prompt-turing eocompplis
Lex 101- 0.2)
Pronept-
Atreee -5200 -1000
-000
Hinnre:: 1190
WitnEER: TEDO
-400
Figure I: An overview of EVOPROMPTING. After initializing the search with a handful of manually designed program seeds, the meta-learning loop begins. First, code vode-pretrained LM uses the seeds as in-context prompt examples to generate candidate architectures. Those candidate architectures are then trained on the task training data and evaluated on the task validation set. Next, the most fit members of the population are selected as in-context examples for the next meta-learning loop and all evaluated individuals are used as training data for prompt-tuning the LM. From there, the meta-learning loop begins again.
EvoPrOMPTING is based on the recently popularized practice of in-context prompting. Prompting is the technique of conditioning a LM's decoded output on a custom prefix known as a prompt, which can include natural language task instructions a few input-output examples. The prompt is used only at inference time and requires no gradient updates (Brown et al. 2020). In past work, prompting has been demonstrated to elicit impressive performance on wide variety of tasks without requiring task-specific fine-tuning (Sanh et al.] [201]] WWei et al.] [002 Kojima et al.) (2022). Here, we leverage LM prompting for the task of designing improved deep learning architectures.
To engineer adequately powerful prompts, we draw inspiration from existing ideas in the field of neural architecture search. There, evolution has long been used to search over discrete spaces to efficiently discover improved deep learning architectures (Yao) 1999 Real et al., 2017). However, evolutionary approaches typically require careful manual design of a discrete search space (e.g. small set of known convolutional neural network components, as in Real et al. (017)) or TensorFlow primitives, as in So et al. (202T)) As result, the performance of the evolutionary algorithm is then sensitive to and possibly limited by the design of the search space. In EVoPROMPTING the LM's vocabulary replaces the search space, which both increases the flexibility of the search and reduces reliance on manual design. The LM also an adaptive mutation/croossoerr operator, in the sense that it can be improved round over round via prompt-tuning. Furthermore, EVoPrOMPTING also improves on naive few-shot prompting by using an evolutionary search approach to iteratively improve the in-context examples for few-shot prompting.
To demonstrate the effectiveness of this method, we first do extensive testing and analyses on the relatively low-compute problem of MNIST-ID (Greydanus) 2020). The key finding of these experiments is that EYOPROMPTING is capable of producing conventional convolutional architectures superior to published manually designed models (Section 4.1). In Section 4.2 then apply our method to the more challenging task of designing graph neural networks using problems from the CLRS Algorithmic Reasoning Benchmark (Veličković et al.) 2022), where EVOPROMPTING generates novel architectures that outperform state-of-the-art models on 21 out of 30 algorithmic reasoning tasks (Appendix B)
The contributions of this work are summarized as follows:
1. We propose EVOPROMPTING, a method that utilizes evolutionary search to create and curate data to improve LM in-context prompting examples. Although this work focuses on the specific task of neural architecture design to develop this method, EVOPROMPTING is generally applicable to LM tasks that rely on in-context learning (ICL) or prompt-tuning.
2. A study applying LMS to code-level neural architecture design. Our experiments demonstrate that applying shot prompting alone to neural architecture design is unsuccessful, but few-

---

shot prompting with EVOPROMPTING enables LMs to create architectures that outperform those designed by human experts.
3. Novel graph neural network architectures that were discovered using EvoPROMPT- ING. These architectures outperform the current state-of-the-art architecture, Triplet- GMPNN (Ibarz et al.) (022), on 21 out of 30 CLRS Algorithmic Reasoning Benchmark tasks (Appx. 3).
2
Related Work
2017 is currently a popular route for reliably creating state-of-the-art natural language systems (Brown al. 2020; Du al. 202T BigScience Workshop et al. 2022] Zhang et al., 2022 Thoppilan et al. 2022, Chowdhery et al. 2022). Many works have observed that large LMs are capable of performing technical tasks such as writing code (Chen et al.
LMs for code generation Scaling Transformers Vaswani et al.
202 I, doing math (Noorbakhsh et al. 2021). D. and solving complex
reasoning problems (Wei et al. (2022) ) Our work is most closely related to efforts that have applied
LMs to coding tasks (Chen et al.
2021 Odena et al. 2021 Xu et al. 2022) Wang et al. 2021 Ahmad
ct al.
2021
Feng et al. 2020). since our technique proposes architectures in code.
Prompting Brown et al. (2020) demonstrated that LMs can be prompted with in-context examples
to steer LM decoding towards solving problems in-context without gradient updates. Numerous works
have utilized this prompting to further boost LM abilities (Sanh et (00T Wei et al. [022]] Kojima
et al. 2022). Others have focused on optimizing these prompts (Min et al. 2022, Liu et al. (021)
as via approaches such as augmentation with retrieval systems (Rubin et al. 202 permutations
of few-shot examples (Lu et al. [222 /Zhao et al., 202T), generating prompts via LMs (Zhou et al.)
2022). and instruction-tuning perspective of Dohan et al. (2022), prompts are parameters that can be tuned using probabilistic inference techniques. Brooks et al. (2022) proposes using few-shot prompts to implement both the rollout policy and world model of policy iteration algorithm. Our EVOPROMPTING method extends these efforts by proposing evolutionary search as a means to both better design prompts for ICL and tune the base LM to use the prompt more effectively.
(Wei ct al. 2021 Ouyang et al.) 2022 Sanh et al. (021). From the
Evolutionary Algorithms Our method is closely related to evolutionary neural architecture search (NAS) (Real et al.) 2017 2018 Elsken et al., 2018; [oo et al., 2019: Liu et al., 2020), in which architectures are represented discrete DNAs, and evolved and filtered based fitness metrics that assess architecture performance. However, our method can search over arbitrary strings of code, whereas conventional evolutionary NAS algorithms rely on hand-crafted search spaces that can strongly bias and contrain the search (Li & Talwalkar] 2019; Sciuto et al. 2019: Bender et al., 2020, Real Real
al. 2020 So et al.) 2021). work close to ours is Lehman et al. (2022) in which an LM is fine-tuned to produce Python code diffs given one of three fixed messages that describe what should be changed, and then used the mutation operator in an evolutionary algorithm. Their work is validated on the Sodarace domain. Our work differs in that we use an LM as a crossover operator, without specifying the class of changes to make, which may offer greater flexibility. Furthermore, we evaluate our approach on the real-world task of NAS, rely on mixed temperature sampling of the LM for diversity instead of using QD algorithm, and also use prompt-tuning in our algorithm. We choose not to use QD algorithm such MAP-Elites since this approach requires the design and discretization of descriptor space, which is complex and difficult to hand-design for the space of all possible neural networks.
Another concurrent work is Mcyerson et al. (2023), which uses an LM as a crossover operator to produce variations of text-based genotypes in the domains of symbolic regression, text sentiment, images, and Sodaracer programs. Like Lehman et al. (2022), they use MAP-Elite to trade off quality with diversity in two of the domains and demonstrate that their overall algorithm reliably produces a diverse range of outputs. They additionally demonstrated performance comparable state-of-the thetthrrrt approaches on the toy task of symbolic regression. Their study varies from ours in a number of ways we apply our algorithm to the real-world task of NAS, we optimize for a tradeoff between state-of-the-ard task performance and model size, we condition on target performance in our prompts, we do not use MAP-Elites, and we use prompt-tuning to iteratively improve the L.'s crossover abilities instead.
3

---

3 EVOPROMPTING Method
3.1 Architecture search problem formulation
Let our target task be denoted by T and 'D be dataset consisting of input-output pairs (a, y) E D for task T. Define the probability distribution me V- model parameterized by 0. from which we can sample code segments с E V (for V the Kleene closure of V. i.e. the set of all concatenations of symbols in V). We also have an evaluation function (v D) V* x D + I that trains the model architecture given by code c on D and outputs some velled fitness score E I. which can be a function of model accuracy and other model characteristics. Our ultimate goal to identify some set of code samples ~ V that define neural network architectures that, when trained on D, maximize the reward EvALy(c, D).
- {0, 1] over vocabulary V as a language/code
3.2
LMs for evolutionary crossover and mutation
The goal of our algorithm is to generate a C consisting of k neural network architectures that maximize the reward (V,LT(C, D) for arbitrary pairs of (D, T):
arg
max
BeEC EVALT(C,
(1)
10j= [ovoo}
Since this optimization problem generally intractable, we turn to black-box evolutionary approach for iteratively generating, scoring. and selecting the best neural network architectures. Indeed, evolution has been demonstrated to perform particularly well in this domain because of how sparse high quality solutions tend to be (Real et al. 2017 2018). Although evolution has been used for architecture search many times before (Real et al.) 201 (2088] Elsken et al.) 2018 So et al. 2019). improve upon this approach by using an LM for crossover and mutation operations.
Using an LM in this manner has multiple appealing properties. While past evolutionary approaches for neural architecture search have required careful design and specification of discrete search space (e.g. the space of high level modules (Real et al.] 2018| [o et al. (2019). TensorFlow statements (So) eet al.) (021), or basic mathematical operations (Real et al. (0200), our algorithm's 's search space includes any neural network architecture that can be represented in Python. This allows for greater flexibility and diversity of the output architectures, and reduces the amount of manual design and human bias involved the algorithm. Furthermore, modern pre-trained LMs are typically trained on massive datasets containing significant number of source code files. This pre-training process encodes useful knowledge about code structure and functionality that is not otherwise available in evolutionary algorithms. Lastly, LMs also be used as self-adaptive crossover operators, in which the crossover operator is incrementally trained round after round to generate higher reward crossovers.
3.3 EVOPROMPTING meta-learning algorithm
Our complete algorithm is described in Algorithm At the core of our algorithm is a scoring function, which describes the general "fitness" of a model on the task at hand. Since higher accuracy can often be achieved simply by increasing the number of parameters in a model, we use the negative product of the validation error and the model size the fitness (see step 6 in Algorithm 3). More complicated objective functions have previously been used for dual objective neural architecture search (Bender) let al. 2020), but we find this simple product works best in our case and requires minimal tuning. Generally the higher the fitness, the better (with some caveats, noted in our description of fitness-based selection below).
The end-to-end meta-learning algorithm has several stages, which we describe below:
Initialization start by setting our global historical population to the empty list and initializing our current population P with few seed architectures that are known to be well-designed (step 3 in Algorithm T). which warm-starts the search (So et al., 2019). These seed models are evaluated using the same EVAL (c, D) function that is used to evaluate new candidate models (see below).

---

Algorithm I Complete meta-learning evolutionary algorithm using Pa as crossover and mutation operator.
1: Input: LM Tepp dataset D, task T, 7' number of rounds, m number of few-shot prompts per round, 7t number of samples to generate prompt, k number of in-context examples per prompt, P number of survivors select per generation, the upper threshold for the test error
2: G <-]
3: P INTIAAIZAPOPULATIONN)))
4: t<0 0
5: while < T do
6:
C' CROSSMUT(TA, p.m, k. Tτ)
7:
CRVALED &- -ILTERANDEVALLCC D,)))
8:
G G CEVALD
9:
< -
10:
P GETTOP(G.p)
11:
0.+1 < TRAIN(O,, CEVALED P)
12:
end if
13:
t ++1
14:
end while
15:
Return GETTOP(G.p)
Algorithm The crossover and mutation algorithm, CROSSMUT(Te,, P, m, k. n),. where Uniform(( P) denotes the uniform distribution over the set P. The set of potential parents P consists of the top examples from the previous round.
1: Input: LM nø, population of code samples and fitnesses P ((c, s) |e E V*, EVAI.T D)
$), m number of few-shot prompts to create, k number of in-context examples in each prompt, and n number of samples to sample per prompt.
2: C'+
3: +
4: while
do E e { where 2i Lid. Uniform(P)
5:
6:
p NAKFFIWSHOOPROOMP(())
7:
C.+ [e where ej To(-1p)
sidd
8:
C+C+C,
9:
iti+1
10: end while
Output: C
Algorithm 3 The algorithm for filtering and scoring child models, FLLTERANDEVALIC.TTD... a).
1: Input: set of code samples C, task T, dataset D, evaluation function EVALT(c, D), upper threshold for error
2: CEVALEd {
3: for in Coo
4: c.error +- EVALT(c,
5: c. then
6: 8 - size X error
7: CEVALED + CEVALED + [(c, 8)]
8: end if
9: end for
10: Output: CEVALED
Crossing and mutating the parent models To mutate and apply crossover to the parents P selected in the last step, we use both the source code and the evaluation metrics of each model in create few-shot prompts.
In the last line of the prompt, we create a target set metrics to condition no 's generations on that indicate the desired validation accuracy and model size of the proposed architecture. We set the target
5

---

model size as 90% of the minimum model size of the parent models, rounded to the nearest 100 parameters, and the target validation accuracy as 102% of the maximum validation accuracy of the parent models, rounded to the nearest tenth of percent. We create such prompts per round, each with in-context examples selected uniformly random from P. example of prompt is shown in Listing
o Metrics:
{' d'num_params: '4800', aval_accuracy'; 10.865
class Model (nn. Module):
@nn. compact
def __call.- (self, x):
x nn. Dense (features=10) (x)
return
10 .** Metriic:
11 ('num_params *4300', 'val_acuuracy' (0.880
12
class Model (nn Module):
Listing 1: The format of our few-shot prompts. In practice we use 2-shot prompts but we omit the second in-context example here for brevity.
Finally, we use my to generate n samples per prompt, yielding a total of n x m child samples per round of evolution. We denote this portion of the algorithm as CROSSMUT P, m,m,N; ke n) (Algorithm) and step 6 of Algorithm T)
Filtering and scoring child samples To score and filter child samples generated by Te, the evaluation function EVALy D), which trains the model encoded by on the dataset D and returns the lowest validation error encountered during training. All child models trained for the same number of steps, with the same optimizer hyperparameters. Since our fitness function can potentially be gamed by generating arbitrarily small models, we also add validation error threshold a, which is the upper limit of the validation error that model can incur without being removed from G. the global population. We refer this function as FILTERANDEVAL T, D, a) (Algorithm and step of Algorithm ID. Lastly, we add the remaining trainable models and their associated fitness scores into (step of Algorithm
Fitness-based selection After evaluating all child models in the current round, we apply fitness- based selection identify top candidate models for crossover (step 10 of Algorithm TT. We denote (o,(G, p). which refers simply to selecting the models with the highest fitness scores from G. Once these models have been selected, they are permanently removed from the population and cannot be used again as parents for crossover.
this as GETTOP (G,
Training Te, Lastly, all child models generated in the current round that were previously selected for crossover (i.e. CEVALEd \ P) are used to prompt-tune for the next round (step 1 of Algorithm
Experiments and Results
We evaluate meta-learning algorithm two datasets MNIST-ID (Greydanus, 2020) and the CLRS algorithmic reasoning benchmark (Veličković et al. 2022). While the former benchmark is lightweight and permits to do more thorough analysis of our algorithm, the latter is newer benchmark that covers 30 different algorithms with more headroom for discovering novel architectures with better performance.
In all of our experiments, our Top (i.e. the crossover operator) a 62B parameter PALM model (Chowdhery et al., 2022) pre-trained on 1.3T tokens of conversational, web, and code doc- uments. was additionally fine-tuned on a corpus of 64B tokens containing near-deduplicated, permissivelylliceneed Python source code files from Github. We always sample from To, with

---

mixed temperature sampling, in which the sampling temperature is selected uniformly from [0.2, 0.6, 0.8, 1.0]. Between each round, the model is prompt-tuned (Lester et al. 2021) for epochs with a soft prompt length of 16, batch size of 16, and learning rate of 0.1 (as described in Section 3.3 and Step 11 of Algorithm[| D. Unless stated otherwise, we run 10 rounds of evolution with 10 prompts per round and 16 samples generated per prompt, yielding total of 160 models generated per round and 1600 models generated during the entire search. Duplicate models and un-trainable models are not scored, but do count into the 1600. All other EVOPROMPTING hyperparameters are listed in Appendix A.T
4.1 MNIST-ID
Dataset We apply our method first to MNIST-ID (Greydanus) 2020), a one-dimensional, scaled- down version of the MNIST-ID dataset containing examples that are 20 times smaller than the original MNIST dataset. Each example is only 40-dimensional, with 4000 examples in the training dataset and 1000 in test. Since there is no validation dataset, we randomly set aside 500 examples from the training dataset to use as the validation dataset. Despite being more lightweight, MNIST-ID distinguishes more between different architecture types (Greydanus 2020) than its larger counterpart MNIST (LeCun et al. 1998).
Meta-learning set-up Throughout the model search we use the W optimizer (Loshchilov & Hutter (219)) to train each child model on single NVIDIA Tesla P100 GPU for 8000 steps, with learning rate 0.01 and batch size 128. We score child models according to the best validation accuracy achieved during training. We also seed the search with 4 seed models the 3 hand-designed neural baselines from the original MNIST-ID paper (Greydanus) 2020) (GRU, CNN, and MLP) and a fourth, larger CNN model of our own design. All four are implemented with Flax (Heek et al. 2020). We
refer the reader to Appendix A.2 for the source code of these seed models.
Baselines
We compare EVOPROMPTING with the following baselines:
Naive few-shot prompting: This baseline simply generates code samples ~ To, (-lp). where p is a 2-shot prompt constructed using in-context examples randomly selected from the seed models (Listing This is essentially an ablation of steps 7-12 in Algorithm [ with T 1. We increase the number of samples generated per prompt for the naive prompting baseline such that the total number of samples generated by mo matches that of the other baselines.
EVoPROMPTING (- prommt-tunnig): We run the entire algorithm as is, but without prompt- tuming between each round. This is an ablation of step 11 from Algorithm [
EVoPrOMPTING (random parents): Instead of selecting the most fit models from the last round parents for the next round, we select parents randomly. This is an ablation of Step which is the GETToP(G, p) step.
10 in Algorithm [
EVoPrOMPTING finds smaller and more accurate models Figure 2a shows a comparison of the test error and model size of the top 20 models discovered by EVoPROMPTING compared with those of our seed models and three baselines. The points approximate a Pareto frontier, below which each one dimension without hurting the other. EVOPROMPTING possesses the Pareto frontier closest to the origin, indicating that it finds more optimal models in terms of accuracy and size. In fact, many models in PYOPROMPTING'S top 20 discovered models orders of magnitude smaller than those of the other baselines, while still having lower test error.
algorithm cannot improve
We also note that this task in particular EVOPROMPTING excels especially at optimizing convolutional architectures. Many of the top 20 models are narrower and deeper convolutional architectures, with smaller strides, less padding, and no dense layers. These models consistently perform better than the shallower, denser, and wider convolutional architectures seen in earlier rounds of the model search.
Another important aspect of a meta-learning algorithm the relationship between the number of individuals evaluated and the maximum fitness observed so far, i.e. the sample efficiency. Neural architecture search can be an expensive process, with the most open-ended searches requiring the evaluation of trillions of individuals (Real et al. 2020). Thus, it is crucial to identify fit candidates
7

---

Maa mum fitvess of top model
Evetrompting
EvoPrampting premmt-turtnn)
Pompingpiing (rantimm pareres] No few shot prompting Seeds
0.6
0.4
0.2
200
400
500
500
1000
1200
1400
1000
genirrated
0.0
Experiment type
301
10
Eeahhampting Evoheoreting
Exchhumptnng trandor panmna
Model size (humber of parameters)
prorppt buniing
promepnng
(a) Pareto frontiers the model versus test error of top 20 experiments each variation of the MNISTID model search. Frontiers closer to the origin are considered more desirable.
(b) Number of child models generated versus max- imum fitness sample, as estimated using 100 bootstrap samples of size 20 for each point along the x-axis.
Figure 2: EVOPrOMPTING discovers smaller and better performing architectures on MNIST-ID than alternative search methods.
Articu lation Poi
Graharm Scan
Hit Krusial
Nosmum thess popuratinn
Mokmmm ltreos popetiaiin
thees in
Experimett
Ensharrt
Excihorppt: prompeoaniie)
Exsirorept promppmntiral
10'
Excirompe prompenariin)
Towvshok prampiingg
Trwvthos prampting
No Reeehhttoorottn
Mamber of modes gentrated
Number of models genertee
Numbbr models generates
Figure 3: Number of child models generated versus maximum fitness of top model seen so far (as estimated using 100 bootstrap samples of size 20 for each point along the x-axis) when searching over neural network models for three CLRS tasks. As mentioned in Section 4.2 these algorithms were selected because our preliminary analyses indicated that they had the most headroom for architectural improvements.
using few samples as possible. Figure 2b compares how the fitness of the best-performing child model improves as a function of the number child samples generated thus far. The random parents baseline plateaus the quickest, reaching maximum fitness by the time approximately 200 individuals have been generated. Furthermore, the maximum fitness it reaches is significantly worse than that of the other experiments. On the other hand, EvoPromptiNg without prompt-tuning and normal EvoProMPTING do not plateau until much later on. EvOPROMPTING'S plateau is the highest and therefore fitter average than the individuals discovered by any of the other experiments.
is also evident from both Figure 2a and 2b that performance suffers when any individual component is removed. Interestingly, Figure Paiincisssss that prompting with randomly selected parents combined with prompt-tuning is no more effective than naive prompting alone. This highlights the importance of selecting helpful in-context examples, particularly in task for which assume that less training signal exists in the pre-training data. However, selecting more models as in-context examples without prompt-tuning also does not perform nearly well as our full method.
Trajectory over meta-learning rounds We also explored the trajectory of our meta-learning algorithm round over round, as shown in Appendix In general, we observe that EVoPrOMPTING starts out further away from the origin (in round 0) and ends up closest to the origin in round 10, which signifies that it discovers - on average the smallest and most accurate models the last round. However, the search does not always yield improvements on both axes between consecutive rounds. rounds 0-2 and 10, EvoPrOMPTING improves test error while trading off model size. On the other hand, both dimensions are simultaneously improved upon in rounds 3-5.

---

4.2 CLRS
Although the MIIIT-ID ID task offers an efficient and practical setting for evaluating a meta-learning algorithm, CNN architectures already perform fairly well on this task and neural image classification architectures have been extensively studied as whole. There also exists the possibility that our LM has seen many convolutional architectures in its pre-training data. Instead, we turn to different learning task and class of neural network architectures order assess whether our meta-learning framework generalizes to other tasks, datasets, and neural architectures.
Dataset The CLRS algorithmic reasoning benchmark (Veličković et al. 2022 evaluates the ability of neural networks to learn algorithmic reasoning across a set of 30 classical algorithms covered in the Introduction to Algorithms textbook by Cormen, Leiserson, Rivest and Stein (Cormen et al. 2009). This benchmark is useful not only difficult logical reasoning task for neural networks, but also as a measure of a neural network's 's algorithmic alignment (Xu et al.) 2020). In brief, algorithmic alignment refers to model's ability to reason like an algorithm (i.e. using the computation graph for a task), rather than relying upon memorization or other less sample efficient learning strategies. Although model can approximate algorithm by pattern-matching on other shortcuts, it cannot generalize to arbitrarily long inputs or edge cases without learning the computation graph underlying the algorithm.
matching against similar inputs relying
Accordingly, the CLRS benchmark represents the algorithms' inputs and outputs as graphs, and the steps of the algorithm be straightforwardly processed by graph neural networks, which is explored Iharr et al. (2022). neural network (Gilmer et al. (017]) with
trajectory of operations over the input graph. This problem setup can
They find that Triplet- GMPNN model (a gating and triplet edge processing) exhibits the best performance when trained and evaluated across all 30 algorithms at once.
Table 1: A comparison of OOD accuracy and model size (in number of parameters) of models newly discovered by EVOPROMPTING on select CLRS tasks where EVoPrOMPTING has discovered more accurate architectures without large increases in model size, compared with the baseline model (the Triplet-GMPNN from Ibarz et al. 2022)). OOD accuracy numbers for the baseline model are from lbarz et al. (2022). For the full table of results all CLRS tasks, including accuracies of our implementation of the GMPNN, see Appendix
Model Size
OOD Accuracy ?
CLRS Task
Best Performing Model
Ours
Baseline
Ours
Baseline
Articulation Points BFS
QUADNNDEMINMAX
497969
531913
93.5 + 1.8%
88.3+ 2.0%
MAXMEAN
522931
523963
100.0 + 0.0% %
99.7+ 0.0%
Bubble Sort
CONCATREP
568533
524477
88.9 + 2.8 %
67.7+ 5.5%
DFS
DIV2MBAN
660158
661190
68.1 1 1.4%
47.8.L 4.2%
Floyd Warshall
CONCATREP
669145
625089
61.4 1 0.8%
48.51 1.0%
Heapsort
CONCATREP
703710
659654
69.9 1 4.2%
31.0.1 5.8%
Insertion Sort
DIV2MEAN
523445
524477
89.5 1: 2.6%
78.11 4.6%
Quicksort
DIV2MEAN
524727
525759
85.2 + 4.3%
64.6 5.1%
Task Scheduling
TANHEXPANDTRIPLETSS
262333
262333
88.2 + 0.4%
87.3+ 0.4%
Meta-lcarning set-up Similar to our MNIST-ID set-up, we use the AdamW optimizer to train each child model on a single NVIDIA Tesla P100 GPU. However, since most of the explored child models were much larger than the MNIST-1D models, we only trained each child model for 2000 steps. Anecdotally, we observed that the performance of different models often diverged by 2000 steps, which provided sufficient signal for the model search process. We otherwise followed the hyperparameters for single-task training in Ibarz et al. (2022 and evaluated models using validation accuracy.
Unlike our MNIST-ID set-up, we only search over the triplet representations of Triplet-GMPNN model (see Ibarz et al. (202)) for more details), rather than the entire graph processor. We also seed the search with nine different seed models each a variant of a Triplet-GMPNN model with a different triplet representation. Each seed triplet representation incorporates minor tweak of single component of the original triplet representation designed by Ibarz al. (2022). These include fully-connected output layer, aggregation, fully-connected node/edge/grai representations,

---

simple linear triplet representation, and a bilinear representation (Mnih & Hinton 2007). All nine are implemented with Haiku (Hennigan et al. 2020), an object-oriented neural network library for Jax (see Appendix A.5 for the source code of the seed models.)
Generalizing beyond image classification models We search using EYoPrOMPTING on 3 indi- vidual algorithms in the CLRS benchmark the articulation points, Graham scan, and Kruskal's minimum spanning tree algorithms. We select these algorithms because our preliminary analyses with hand-designed architectures showed that they had the most headroom for improvement, although we found that the discovered architectures transfer well to other CLRS benchmark tasks as well (Appx. B Our search results are shown in Figure EVOPROMPTING continues to find models that are more "fit" than our other two baselines, though we observed that the results also show more variation than our results for MNIST-ID did.
Analyzing newly discovered models Our search across triplet representations yielded several new designs that we sought to evaluate across all algorithms in the CLRS benchmark. Although these new models were discovered in model searches over single algorithms, they oftentimes generalized to other algorithms that were unseen during the model search. Jiswow the trajectory of validation accuracy during training and Table provides OOD accuracies for these models on a few select algorithms. (We defer the reader to Appendix A.4 for the full source code of each newly discovered model and (.6 the full list of OOD accuracies for every algorithm in the CLRS benchmark.)
We note that the model search suggested several simple but effective changes. For example, instead of taking the maximum of the triplet representation, the QUADNODEMINMA model uses quadruplet node representations instead of triplets, and it subtracts the minimum of the quad representation from the max instead. CONCATREP represents the node, edge, and graph representations as a concatenation of projection feedforward layer, and MAXMEAN takes the maximum of the triplet representations prior to taking the mean and passing it through the output dense layer. DIV2MEAN scales each of the node representations by 1/2 and uses mean aggregation of the triplet representations instead of the max aggregation. TANHEXPAND TRIPLETS applies additional dimension expansion to the triplet representations and applies hyperbolic tangent function after the max aggregation. See Appx. A.4 for the full code of each discovered model.
Of the 5 newly discovered models that we chose to analyze, CONCATREP is the only one that increases model size. However, as shown in Table CONCATREP frequently yielded improvements in OOD accuracy that far exceeded the percent increase in model size. For instance, algorithm CONCATREP increased OOD accuracy by 125. while only increasing model size by 6.68% over the baseline. The other four newly discovered models shown in Table [ simultannouusly improved OOD accuracy while decreasing model size on the articulation points, BIS, DFS, insertion sort, quicksort, and task scheduling algorithms. On the rest of the CLRS algorithms (Table our newly discovered models typically achieved OOD accuracy comparable to or better than the baseline, while maintaining similar model size.
the heapsort
5 Conclusion
We have shown that embedding a pre-trained LM in an evolutionary algorithm significantly improves the LM's performance on the task of neural architecture design. Our approach has demonstrated success at not only optimizing convolutional architectures for the MNIST-1D task, but also at developing new kinds of GNNs for the CLRS algorithmic benchmark. This demonstrates: 1) using evolutionary techniques can vastly improve the in-context capabilities of pre-trained LMs, and 2) EVOPROMPTING can discover novel and state-of-the-arr architectures that optimize for both accuracy and model size. Furthermore, EYOPROMPTING is general enough to be easily adapted to search for solutions to other kinds of reasoning tasks beyond NAS. We leave the adaptation of EVoPrOMPTING for other tasks to future work.
However, our study is limited by the lack of an extensive comparison against other standard NAS techniques because EYoPrOMPTING was designed for open-ended search, whereas other techniques were not, which would introduce a potential confounder. We include one such comparison on MATS-Benchaae in Appendix A.7 as well as discussion of the confounders thereof.
10

---

6 Acknowledgements
We thank Maarten Bosma, Kefan Xiao, Yifeng Lu, Quoe Le, Ed Chi, Borja Ibarz, Petar Veličković, Chen Liang. Charles Sutton, and the Google Brain AutoML team for providing valuable discussions and feedback that influenced the direction of this project. We also thank the Google Student Researcher program for providing the resources and opportunities necessary for this project to take place.
References
Ahmad, W. U., Chakraborty, S., Ray, B., and Chang, K.-W. Unified pre-training for program understanding and generation. ArXiv, 0bs/2103.006333, 2021.
Bender, G., Liu, H., Chen, B., Chu. G., Cheng, S., Kindermans, P.-.,, and Le, Q. V. Can weight sharing outperform random architecture search? an investigation with tunas. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 14311-14320, 2020.
BigScience Workshop, Scao, T. L.., Fan, A., Akiki, C., Pavlick, E., Ilié, S., Hesslow, D., Castagné, R., Luccioni, A. S.. Yvon, F., Gallé, M., Tow, J., Rush, A. M., Biderman, S., Webson, A., Ammanamanchi, P. S., Wang. T., Sagot, B., Muennighoff, N., del Moral, A. V., Ruwase, O., Bawden, R., Bekman, S., McMillan-Major, A., Beltagy, I., Nguyen, H., Saulnier, L., Tan, S., Suarez, P. O., Sanh, V., Laurençon, H., Jernite, Y., Launay, J., Mitchell, M., Raffel, C., Gokaslan, A., Simmi, A., Soroa, A., Aji, A. F., Alfassy, A., Rogers, A., Nitzav, A. K., Xu, C., Mou, C., I., Radev, D., Ponferrada, Levkovizh, E., Kim, E., Natan, E. B., De Toni, F., Dupont, G., Kruszewski, G., Pistilli, G., Elsahar, H. Benyamina, H., Tran, H., Yu, Abdulmumin, I., Johnson, I., Gonzalez-Dios, I., de la Rosa, J., Chim, J., Dodge, J., Zhu, Chang, J., Frohberg. J., Tobing, J., Bhattacharjee, J., Almubarak, K., Chen, K., Lo, K., Von Werra, L., Weber, L.. Phan, L.,, allal, B., Tanguy, L.,, Dey, M., Muñoz, M. R., Masoud, M., Grandury, M., $aško, M., Huang, M., Coavoux, M., Singh, M., Jiang, M. T.-J., Vu, M. C., Jauhar, M. A., Ghaleb, M. Subramani, N. Kassner, N., Khamis, N., Nguyen, O., Espejel. O., de Gibert, O., Villegas, P., Henderson, P., Colombo, P., Amuok, P., Lhoest, Q.. Harliman, R., Bommasani, R., López, R. L., Ribeiro, R., Osei, S., Pyysalo, S., Nagel, S., Bose, S., Muhammad, S. H., Sharma, S., Longpre, S., Nikpoor, S., Silberberg, S., Pai, S., Zink, S., Torrent, T. T., Schick, T. Thrush, T., Danchev, V., Nikoulina, V., Laippala, V., Lepercq. V., Prabhu, V., Alyafeai, Z., Talat, Z., Raja, A., Heinzerling, B., Si, C., Taşar, D. E., Salesky, E., Mielke, J., Lee, W. Y., Sharma, A., Santilli, A., Chaffin, A., Stiegler, A., Datta, D., Szczechla, E., Chhablani, G., Wang, H., Pandey, H., Strobelt, H., Fries, J. A., Rozen, J., Gao, L., Sutawika, L., Bari, M. S., Al-shaibani, M. S., Manica, M.. Nayak, N., Teehan, R., Albanie, S., Shen, S., Ben-David, S., Bach, H., Kim, T., Bers, T., Fevry, T., Neeraj, T., Thakker, U., Raunak, V., Tang, X., Yong, Z.-X., Sun, Z., Brody, S.. Uri, Y., Tojarich, H. Roberts, A., Chung, H. W., Tac, J., Phang. J., Press, O., Li, C., Narayanan, D., Bourfoune, H., Casper, J., Rasley, J., Ryabinin, M., Mishra, M.. Zhang, M., Shoeybi, M.. Peyrounette, M., Patry, N., Tazi, N., Sanseviero, O., Platen, P., Cornette, P., Lavallée, P. F., Lacroix, R., Rajbhandari, S., Gandhi, S., Smith, S., Requena, S., Patil, S., Dettmers, T., Baruwa, A., Singh, A., Cheveleva, A., Ligozat, A.,L., Subramonian, A., Névéol, A., Lovering, C., Garrette, D., Tunuguntla, D., Reiter, E., Taktasheva, E., Voloshina, E., Bogdanov, E., Winata, G. I., Schoelkopf, H., Kalo. J.-C., Novikova, J., Forde, J. Z., Clive, J., Kasai, J., Kawamura, K., Hazan, L.,, Carpuat, M., Clinciu, M., Kim, N., Cheng, N., Serikov, O., Antverg, O., van der Wal, O., Zhang, R., Zhang, R., Gehrmann, S., Mirkin, S., Pais, S., Shavrina, T., Scialom, T., Yun, T., Limisiewiez, T., Rieser, V., Protasov, V., Mikhailov, V., Pruksachatkun, Y., Belinkov, Y., Bamberger, Z., Kasner, Z., Rueda, A., Pestana, A., Feizpour, A., Khan, A., Faranak, A., Santos, A., Hevia, A., Unldreaj. A., Aghagol, A., Abdollahi, A., Tammour, A., HajiHosseini, A., Behroozi, B., Ajibade, B., Saxena, B., Ferrandis, C. M., Contractor, D., Lansky, D.,, David, D.. Kiela, D., Nguuenn D. A., Tan, E., Baylor, E., Ozoani, E., Mirza, F., Ononiwu, F., Rezanejad, H., Jones, H., Bhattacharya, I., Solaiman, I., Sedenko, Nejadgholi, I., Passmore, J., Seltzer, J., Sanz, J. B., Dutra, L., Samagaio, M., Elbadri, M., Mieskes, M., Gerchick, M., Akinlolu, M., McKenna, M., Qiu, M., Ghauri, M., Burynok, M., Abrar, N., Rajani, N., Elkott, N., Fahmy, N., Samuel, O., An, R., Kromann, R., Hao, R., Alizadeh, S., Shubber, S., Wang, S., Roy, S., Viguier, S., Le, T., Oyebade, T., Le, T., Yang, Y., Nguyen, Z.., Kashyap, A. R., Palasciano, A., Callahan, A., Shukla, A., Miranda- -acalaaaa A., Singh, A., Beilharz, B., Wang, B., Brito, C., Zhou, C., Jain, C., Xu, C.,
Emezue, C.,, Klamm, C., Leong. C., van Strien, D., Adelani,
G..
11

---

Fourrier, C., Periñán, D. L.. Molano, D., Yu. D., Manjavacas. E., Barth, F., Fuhrimann, F., Altay, G., Bayrak, G., Burns, G., Vrabec, H. U., Bello, I., Dash, I., Kang, J.. Giorgi, J., Golde. J., Posada, J. D., Sivaraman, K. R., Bulchandani, L.,, Liu, I.., Shinzato, I.., de Bykhovetz, M. H., Takeuchi, M., Pamies, M., Castillo, M. A., Nezhurina, M., Sänger, M., Samwald, M., Cullan, M., Weinberg, M., De Wolf, M., Mihaljcic, M., Liu, M., Freidank, M.. Kang. M., Seelam, N., Dahlberg, N., Broad, N. M., Muellner, N., Fung, P., Haller, P., Chandrasckhar, R., Eisenberg, R., Martin, R., Canalli, R., Su, R., Su, R., Cahyawijaya, S., Garda, S., Deshmukh, S. S., Mishra, S., Kiblawi, S., Ott, S., Sang-aroonsiri, S., Kumar, S., Schweter, S., Bharati, S., Laud, T., Gigant, T., Kainuma, T., Kusa, W., Labrak, Y.. Bajaj. Y. S., Venkatraman, Y., Xu, Y., Xu, Y., Xu, Y., Tan, Z., Xie, Z., Ye, Z., Bras, M., Belkada. Y., and Wolf, T. Bloom: A 776--paramete open-aceess multilingual language model,
2022. URL arxiv org/ abs abss/221222 22111.211... 05100
Brooks, E., Walls, L., Lewis, R. L.., and Singh, S. In-context policy iteration, 2022. URL https
7/arxiv. .rg. aba 2210. 03821
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P.. Sastry, G., Askell, A., Agarwal, S., Herbert- Voss, A., Krueger, G., Hemighan, T., Child, R.,
Ramesh, A., Ziegler, D. M., Wu, J., Winter, C.,, Hesse, C., Chen, M. Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners, 2020. URL https:::::// /tttcpp://axiivv arwii. wwwpxiiv...rg.oooooooo.o abs/ 14165
Chen, M., Tworek, J., Jun, H., Yuan, Q.. Ponde, H., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., Ray, A., Puri, R., Krueger, G., Petrov, M., Khlaaf, H., Sastry, G., Mishkin, P., Chan, B., Gray, S., Ryder, N., Pavlov, M., Power, A., Kaiser, I.., Bavarian, M., Winter, C.,, Tillet, P., Such, F. P., Cummings, D. W. Plappert, M., Chantzis, F., Barnes, E., Herbert- Voss, A., Guss, W. H., Nichol, A., Babuschkin, I., Balaji. S. A., Jain, S., Carr, A., Leike, J., Achiam, J., Misra, V., Morikawa, E., Radford, A., Knight, M. M., Brundage, M., Murati, M., Mayer, K., Welinder, P. McGrew, B., Amodei, D., McCandlish, S., Sutskever, and Zaremba, W. Evaluating large language models trained on code. ArXiv, abs/2107.0033777 2021.
Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., Schuh, P., Shi, K., Tsyyashchenko, S., Maynez, J., Rao, A., Barnes, P., Tay, Y., Shazeer, N., Prabhakaran, V., Reif, E., Du N., Hutchinson, B., Pope, R., Bradbury, J., Austin, J., Isard, M., Gur-Ari, G., Yin, P., Duke, T., Levskaya, A., Ghemawat, S., Dev, S., Michalewski. H., Garcia, X., Misra, V., Robinson, K., Fedus, L., Zhou, D., Ippolito, D., Luan, D., Lim. H., Zoph, B., Spiridonov, A., Sepassi. R., Dohan, D., Agrawal, S., Omernick, M., Dai, A. M., Pillai, T. S., Pellat, M., Lewkowycz, A., Moreira, E., Child, R., Polozov, O., Lee, K., Zhou, Z., Wang. X., Saeta, B., Diaz, M.. Firat, O., Catasta, M., Wei, J., Hellst-Hl,,s,emm, K., Eck, D., Dean. J., Petrov, S., and Fiedel, N. Palm: Scaling language modeling with pathways, 2022.
URL https: //apiiv///axiv..e/ org/ /2004 02311
Cormen, T. H., Leiserson, C. E., Rivest, R. L.,, and Stein, C. Introduction to Algorithmss Third Edition. The MIT Press, 3rd edition, 2009. ISBN 0262033844.
Dakhel, A. M., Majdinasab, V., Nikanjam, A., Khomh, F., Desmarais, M. C., and Jiang, Z. M. Github copilot ai pair programmer: Asset liability? ArXiv, abs/2206. 15331, 2022.
Dohan, D., Xu, W., Lewkowycz. A., Austin, J., Bieber, D., Lopes, R. G., Wu, Y., Michalewski, H., Saurous, R. A., Sohl-dickstein, J., Murphy, K., and Sutton, C. Language model cascades, 2022.
URL https: :/aaiiv///////////aa//aa/aaaaava www.rxii....gaaaeee abtp:/bb//2201 10342
Dong, X., Liu, L., Musial, K., and Gabrys, B. NATS-Bench: Benchmarking nas algorithms for architecture topology and size. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2021. doi: 10. 109/TPAML 130544444 doi/10. 1109/TPAML 2022.0022220 3054824
Du, N., Huang, Y., Dai, A. M., Tong, S., Lepikhin, D., Xu, Y., Krikun, M., Zhou, Y., Yu, A. W., Firat, O., Zoph. B., Fedus. L., Bosma, M., Zhou, Z., Wang, T., Wang, Y. E., Webster, K., Pellat, K., Duke, T., Dixon, L.., Zhang, K., Le, Q. V., Wu, Y., Chen, Z., and Cui, C. Glam: Efficient scaling of language models with mixture-of-exppere 2021. URL org/ abs/ 2222 06905
M., Robinson, K.,
https://ars
Elsken, T., Metzen, H., and Hutter, F. Efficient multi-objective neural architecture search via lamarckian evolution. arXiv: Machine Learning, 2018.
12

---

Feng, Z., Guo, D., Tang, D., Duan, N., Feng. X., Gong. M., Shou, L., Qin, B., Liu, T., Jiang, D., and Zhou, M. Codebert: A pre-trained model for programming and natural languages. ArXiv, abs/2002.081555, 2020.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 1263-1272. JMLR.org, 2017.
Greydanus, S. Scaling *down deep learning. CoRR, abs/2011.14439, 2020. URL https: (ttps://arxiy org/ hte/abs//000 20010 14439
Heek, J., Levskaya, A., Oliver, A., Ritter, M., Rondepierre, B., Steiner, A., and van Zee, M. Flax: A neural network library and ecosystem for JAX, 2020. URL httttt/://gtthhut com/ hamm//oool/fla...
Hennigan, T., Cai, T., Norman, T., and Babuschkin, I. Haiku: Sonnet for JAX, 2020. URL http://gi com wtt.ccommmeeeeee deepmind/ dtm
Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Bennani, M. A., Csordás, R., Dudzik, A.,
Bovsnjak, M., Vitvitskyi, A., Rubanova, Y., Deac, A., Bevilacqua, B., Ganin, Y., Blundell, and
Veličković, P. generalist neural algorithmic learner. ArXiv, abs/2209. 1 1114,, 2022.
Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. ArXiv, abs/2205. 1196, 2022.
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied document recognition. Proc. IEEE, 86:2278-2324 1998.
Lehman, J., Gordon, Jain, S., Ndousse, K., Yeh, C., and Stanley, K. O. Evolution through large models. ArXiv, abs/2206.08896, 2022.
Lester, B., AI-Rfou, R., and Constant, N. The power of scale for parameter-efficient prompt tuning, 2021. URL https: : arxiv. org/ abs/2104. 08691
Li L. and Talwalkar, A. S. Random search and reproducibility for neural architecture search. ArXiv, abs/1902.07638, 2019.
Liu, H., Brock, A., Simonyan, K., and Le, Q V. Evolving normalization-aativvan layers. ArXiv, 0bs//204400266,, 2020.
Liu, J., Shen, D., Zhang, Y., Dolan, B., Carin, L., and Chen, W. What makes good in-context examples for gpt-3? In Workshop on Knowledge Extraction and Integration for Deep Learning Architectures; Deep Learning Inside Out, 2021.
Loshchilov, I. and Hutter, F. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL htttp::/ http:://ppaarrrire..eeeeeeoneiir
Lu, Y., Bartolo, M., Moore, A., Riedel, S., and Stenetorp. P. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Annual Meeting of the Association for Computational Linguistics, 2021.
Meyerson, E., Nelson, M. J., Bradley, H., Moradi, A., Hoover, A. K., and Lehman, J. Language model crossover: Variation through few-shot prompting. 2023. httpstss::///// /ttpps:////xxvoo/oo .rg/ /bs/ 2302. 12170.
Min. S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishiri,, H., and Zettlemooer, L. Rethinking the role demonstrations: What makes in-context learning work? ArXiv, abs/2202..1237,, 2022.
Mnih, A. and Hinton, G. Three new graphical models for statistical language modelling. In
Proceedings of the 24th International Conference on Machine Learning, ICML '07, pp. 641-648, New York, NY, USA, 2007, Association for Computing Machinery. ISBN 978 1595937933. doi: 10. 10.1145//273496 1273577. URL httpss//////oo org/ 1111/1121111661 1273577
Noorbakhsh, K., Sulaiman, M., Sharifi, M., Roy, K., and Jamshidi, Pretrained language models are
symbolic mathematics solvers too! ArXiv, abs/2110.0350/ 2021.
13

---

Odena, A., Sutton, C., Dohan, D. M.. Jiang, E.. Michalewski, H., Austin, J., Bosma. M. P.. Nye. M., Terry, M., and Le, Q. V. Program synthesis with large language models. In n/a, pp. n/a, n/a, 2021. n/a.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L. E., Simens, M., Askell, A., Welinder, P., Christiano, P. F., Leike, J., and Lowe, R. J. Training language models to follow instructions with human feedback. ArXiv, abs/2203.02155. 2022.
Qian, J., Wang, H., Li, Z., LI, S.. and Yan, X. Limitations of language models in arithmetic and symbolic induction. ArXiv, hbs/2208.05051, 2022.
Real, E., Moore, S., Selle, A., Saxena, S., Suematsu, Y. L., Tan, J., Le, Q. V., and Kurakin, A. Large-scale evolution of image classifiers. ArXiv, 703001113,,
Real, E., Aggarwal, A.. Huang, Y., and Le, Q. V. Regularized evolution for image classifier architecture search. In AAAI Conference on Artificial Intelligence, 2018.
Real, E., Liang, C., So, D. R., and Le, Q. Automl-zero: Evolving machine learning algorithms from scratch. In International Conference on Machine Learning, 2020.
Rubin, O., Herzig, J., and Berant, J. Learning to retrieve prompts for in-context learning. ArXiv, abs/2112.08633, 2021.
Sanh, V., Webson, A., Raffel, C., Bach, S. H., Sutawika, L., Alyafeai, Z., Chaffin, A., Stiegler, A., Scao, T. L., Raja, A., Dey, M., Bari, M. S., Xu, C., Thakker, U.. Sharma, S., Szczechla, E., Kim, T., Chhablani, G., Nayak, N. V., Datta, D., Chang. J., Jiang, M. T.-J., Wang. H., Manica, M., Shen, S., Yong. Z. X., Pandey, H.,, Bawden, R., Wang, T., Neeraj, T., Rozen, J., Sharma, A., Santilli, A., Févry, T., Fries, J. A., Teehan, R., Biderman, S. R., Gao, L., Bers, T., Wolf, T., and Rush, A. M. Multitask prompted training enables zero-shot task generalization. ArXiv, abs/21 10.08207, 2021.
Sciuto, C., Yu, K., Jaggi, M., Musat, C. C.,, and Salzmann, M. Evaluating the search phase of neural architecture search. ArXiv, abs/1902.08 1902.08142 2019.
So, D. R., Liang, C., and Le, Q. V. The evolved transformer. ArXiv, 0tss/991.11117,, 2019.
So. D. R., Manke, W. Liu, H., Dai, Z., Shazeer, N., and Le, Q. V. Primer: Searching for efficient transformers for language modeling, 2021. URL https: htttp://arrxiii //tp:////iiv.//// org. abs 2109 08668
Thoppilan, R., De Freitas, D., Hall, J., Shazeer, N., Kulshreshtha, A., Cheng, H.-T., Jin, A., Bos, T. Baker, L., Du Y., Li, Y., Lee, H., Zheng, H. S., Ghafouri, A., Menegali, M., Huang, Y., Krikun, M., Lepikhin, D., Qin, J., Chen, D., Xu, Y., Chen, Z.. Roberts, A., Bosma, M., Zhao, V., Zhou, Y., Chang, C.-C., Krivokon, I., Rusch, W., Pickett, M., Srinivasaa, P., Man, L.,
K., Morris, M. R., Doshi, T., Santos, R. D., Duke, T., Soraker, J., Zevenbergen, B., Prabhakaran, V., Diaz, M., Hutchinson, B., Olson, K., Molina, A., Hoffman-John, F., Lee, Aroyo, I.., Rajakumar, R., Butryna, A., Lamm, M., Kuzmina, V., Fenton, J., Cohen, A., Bernstein, R. Kurzweil, R., Aguera-Arcas, B., Cui, C., Croak, M., Chi, E., and Le, Q. Lamda: Language models for dialog applications, 2022. URL http:://t///arre http:///axxvvvv/a org/ abs 221./2221..00 08239
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need, 2017. htt.s:tss:///rrttt org/ abs//706...//////////
1706. 03762
Veličković, P.,, Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., and
Blundell, C. The clrs algorithmic reasoning benchmark. In International Conference on Machine Learning, 2022.
Wang, Y., Wang, W., Joty, S. R., and Hoi, S. C. H. Codet5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation. ArXiv, abs/2109.00859, 2021.
Wei, J., Bosma, M., Zhao, V., Guu, K., Yu, A. W., Lester, B., Du N., Dai, A. M., and Le, Q. V. Finetuned language models are zero-shot learners. ArXiv, 0tt.22109.01552 2021.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., hsin Chi, F. H., Le, Q., and Zhou, Chain of thought prompting elicits reasoning in large language models. ArXiv, abs/2201. 12200..1199.,.. 2022.
14

---

Xu, F. F., Alon, U., Neubig, G., and Hellendoorn, V. J. A systematic evaluation of large language models of code. Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming, 2022.
Xu, K., Li, J., Zhang, M., Du, S. S., ichi Kawarabayashi, K., and Jegelka, S. What can neural networks reason about? International Conference on Learning Representations, 2020. URL https://openrevieer
Yao, X. Evolving artificial neural networks. Proc. IEEE, 87:1423 1771422-1447,, 1999.
Zhang, S., Roller, S., Goyal, N., Artetxe, M., Chen, M., Chen, S., Dewan, C., Diab, M. Li, X., Lin, X. V., Mihaylov, T., Ott, M., Shleifer, S., Shuster, K., Simig, D., Koura, P. S., Sridhar, A., Wang, T., and Zettlemoyer, L. Opt: Open pre-trained transformer language models, 2022. URL https://arxiv. org/ abs 2205 01068
Zhao, T., Wallace, E., Feng, S., Klein, D., and Singh, S. Calibrate before use: Improving few-shot performance of language models. ArXiv, abs/2102.09690, 2021.
Zhou, Y., Muresamu, A. I., Han, Z., Paster, K., Pitis, S., Chan, H., and Ba, J. Large language models are levenl prompt engineers. ArXiv, abspabl1..00000 1.01110, 2022.
15

---

A Appendix
A.1 EVOPROMPTING Hyperparameters
Table 2: Values of hyperparameters used in EvoPROMPT.
HYPERPARAMETER
DESCRIPTION
VALUE
Num. parents to select in every generation
10
Num. in-context examples in prompt
2
Num. rounds evolution
10
Num, prompts per round
10
Num. samples to generate per prompt
16
Lower threshold for test error
0.5
A.2 MNIST-1D Seed Models
Below we provide the source code for the four seed models used the MNIST-ID model search.
class Model (nn Module): features: int 32
nlayer: int 3
@nn compact
def call (self, x):
x x x(..., None]
x mn. Conv ffe.ttrrsssel..feeeeee
arree_ssiee-3,.) (x)
reluxl
11
x nn avg-poll (x, vindor_shape=(C (2,), strides= (2,))
for in range .aaffrrlayer 1):
= nn an. Conv features=self features,
15
16
(x)
- an.relu (xp) xp
20
x nn avg- (x, vindov_shape=(21 strides=(2,))
21
x x. reshape (xx ((x. shape [0] -1)) # flatten
22
nn Dense (features -alees22566)) 226) (x)
relu (x)
24
x un Dense (features=10) (x)
35
return
Listing 2: hand-designed convolutional model.
class Model (nn. Module):
features: int 25
Cnn compact
def call..l.......... (self, x):
x x(..., Nonel nn Conv(
features=self features, ternel_size=t strides=(2)) (2,),
padding-(1,)
(x)
x reluxxx
for in range (2)
16

---

Conv (
features=self features, kernel_size= (3,), strides= (2,)
padding=(1,)
14
(x)
nn. relu(x)
x.reshape ((x shape [0]; -1))
Dense (features=10) (x)
18
return x
Listing 3: Flax implementation of the convolutional baseline from Greydanus (2020).
class Model (nn Module):
n"*A simple GRU model. ..*
hidden_sized int 6 seed int 42
@nn compact
def mall..(selll x):
x jup. epppedddd_ddms dimm -1)
rng jax_random PRNGKey (self seed)
gru recurrent. GRU
12
hidden_size=self hidden_size,
num num_layers=1, dropout_rate=0000, bidirectional--True.
16
lengths np. full [x. [0]], shape [1])
initialized_param. gru. init (rag. x, lengths)
params initialized_paran ['params
outputs, gru. apply (f params}, x, lengths)
21
outputs outputs reshape (Coutputs shape [0], -1))
22
x mn Denae (features=10) (outputs)
23
return
Listing 4: A Flax implementation of the GRU baseline from Greydanus 2020
class Model (nn. Module) siidennsize:: int 100
Cnn. compact
def
ccallllll....................... (self, x):
x nn Dense (features-self hidden_size) (x)
x relu(x)
relu (nn Dense Seeatures-seff hidden_size (x))
Dense [features=10) (x)
return
return Model
Listing 5: A Flax implementation of the fully connected baseline from Greydanus 2020
A.3 Trajectory of search for MNIST-ID models
17

---

Average model size and
lest per round
4000
10
3x10-
86
8
Test error
R1
Round
.33
84
67
dit
68
dR2
10
f9
R10
10c
300
101
10a
10
Model size (number parameters)
Figure 4: The average model size and test error of the child models produced in each round of the model search. Data points closer to the origin represent rounds that yielded more "fit" models.
A.4 Newly Discovered CLRS GNNs
Bascline
ConcatRcp
Div2Mean
MexMoan
QuedhodioMinMar:
TonhExpandTrpicces
cirs-articulation points
sort
cirs-floyd
Moxi turn score seen so
Maxi muum score seen
Maxt mum score scen
2500
5000
25:00
5000
7500
250C
5000
7500
5000
Maximum score seen so far
cirs-heapsort
cirs-qulciselect
cirs-quicksort
cirs to.plooolicclll. sort
-100
Maximum S-COPe seeen
-100
Maximum soon
-10'
-10F
step
Figure 5: Maximum fitness scores of five of the newly discovered models, compared against the baseline, eight of the CLRS tasks.
Below list the Python source code of five of the newly discovered GNNs.
def get_ get_triplet.msgs_que (z, edge_fts, graph_ fts, nd ab_triplet_fts out_size):
node rope_reps [hk. Linear tub_triplet_fts for in range (4)) Sriplet_node_ree = [node_rep for node_rep in node_ repa] [(1, 2), (1, 3), (2, 3), (3, 1)]
bode_pair_inverese
triplets functools. lambda x, y: y.
[
jnp expand dims (tri_node rep, axis axis=perm) for tri_node _ep_p perm in zip
18

---

triplet_node_ret pode_pair_
12
}.
13
)
return jnp. max (triplets, axis-1) jnp min (triplets, axis-1)
Listing 6: The triplet representation that we refer to as QUADNODEMINMAX
def get get_triplet.mage cot.aaceeccarrepee,, edge_fte, graph_fts, mb_triplet_fts. out_size):
def rep_fn(x, size):
proj = hk. nets. NeP [[sizee)))
ff hk. nets. MLP ([size * 4, size])
return jnp. concatenttt proj (x),
ff fx),
1, axis=-1)
triplet_node_rgg [rep_fn(2, ab.triplet.fts) for in range (3))
criplet_edge_rot [rep_fn (edge_fts, ab.triplet_fts) for in range(3)]
triplet.graph_ree feg_fn fts, ab_triplet_ftas [(2, 3) (1, 3), (1, 2)] triplets functools. reduce
mode pode_pairr_errmtatiie
14
lambda x,
[
jnp. exp.exaand_dee dims (tri_node_rey) axis=perm) for tri_node _eep perm in zip(
18
node_pair.
21
1,
22
)
23
triplets functools reduce lambda x, y,
24
[
imp.expand dims edgee_eerepppp axis=i) for erge___e_rep in
37
range (3,
0, -1)) },
50
triplets jnp. output_layer hk Linear (out soue_size) return putput_layed (jnp. max (triplets, axis-1))
(rripettttttrpp...rpp...e.. axis=(1, 2, 3))
31
32
Listing 7: The triplet representation that we refer to as CONCATREP.
def get_triplet.msge_ htgp:/tc.nnggttttlppppaaarppppdd edge_fta, graph_fts,
ab_triplet_fte out_size):
node_reps [hk.Linear Lineea (ub_triplet_fer for in range [3)] edge_reps Linerr Lit.Lnnnabbbbrriileeeeee (ub_triplet_fta) for in range (3)] graph_rep hk nets MLP
triplet_node_ret
[node_rep (z) for node_rep in node node_reps] [edge_rep (edge_ fts) for edge_rep in
triplet_edge.r
edge_repa]
node.pair.permutationn [(2, 3) (1, 3), (1, 2)]
triplets functools.. reduce lambda x, y: y.
10
[ jnp expand dims (tri_node rep, axis axis=perm)
for tri_node _ep_p perm in zip
19

---

triplet_node_regt node_pairr.perauttiin
15
1.
16
triplets +- functools reduce lambda x, y: y,
[
20
jnp. www.exxdddddde. dims _cri_edge_rep rep, axis=i)
21
for tri sri_ed_e_rep. in zip (triplet_edge_.rg range (3,
0,
-1)) },
23
24
triplets jnp. expand_ orp.apdddiiae(pppppp.rrrrrpppppp axis=(1, 2, 3))
triplets += jnp exppan__daaaaarppp.rrreeeeeo
axis=(2,
1))
26
triplets jnp. erppaaldcaaaerappppp...pppppppp. 2))
axis=(3,
27
output_layer - hk Linear (out_size
return output_layer (jnp. tanh (jnp max (triplets, axis-1)))
Listing 8: The triplet representation that refer TANHEXPAND'RRPPLETS
def get_triplet__ee sene (z, edge_fts, graph_fts,
dis2meen
nb_triplet_ftt out_size):
node_reps Linear (nb wwwpeerrnnbtrreeeteeeeeeeee frrspee_fts)) for in range (3)]
edge_reps [hk.Lineat (nb_ (nb_triplet_fts) for in range (3)]
triplet_node_ret = [node_rep(z 2) for node_rep in node reps
triplet_edge_rept edge [dge_reps]
fts) for edge_rep in node_pair..ermuatiions [(2, 3), (1, 3), (1, 2)]
triplets functools.
lambda x, y: x
jap expand dims (tri (tri_node_r_ rep, axis=perm for tri_node_rep, perm in zip( sriplet_node_reet node_pairr.erruttatio
1.
15
)
triplets += functools. reduce lambda x, y: y,
18
jap expand_ dims (tri_edge_rep axis=perm) for tri edi__eeg_rep, perm in zip cip(triplet.edge_reg range
20
(3, 0, -1))
21
}.
22
23
output_layer = hk Linear (out_sizu return output output_layer (jnp. mean (triplets, axis=1))
Listing 9; The triplet representation that we refer to as DIV2MEAN.
def
(z, edge_fts, graph_fts,
nb nb_triplet_ffr out_size):
node_reps [hk. (nb_triplet__ts) for range (3)) edge_repp Linear (nb (mb_triplet_ftss) for in range (3)]
graph_rep nets ([p( ([nb_trippet__fts]]
triplet_node_ren (node_rep(z) for node_rep in node_
20

---

triplet_edge_ = [edge_rep (edge_fts) for edge_rep in edge_reps]
node node_patr-permuatioos [(2, 3), (1, 3), (1, 2)] triplets ceacctolssreeuceee.
lambda x, x y,
jnp expand dima _epp axis=perm) for tri_node_rep, perm in zip( triplet_node_rees
12
1,
16
)
17
triplets functools reduce lambda x, y: x y,
18
[
pap.expand dims (tri_edge_rep rep, axis=i) for tri_ in zip eaptrrppeet__de__rpp.. range (3,
21
0, -1)) },
22
)
24
triplets jup. maximum (triplets, -100.0) output_layer
25
Linear (out_size
26
return
(jup. mean (tripleta, axis=1))
Listing 10: The triplet representation that we refer to as MAXMEAN.
21

---

A.5
jnp. expand dims (tri eedeederrrppp axis=i) for tri_edge_rep, in zip (driplettedge_reps range CLRS Seed Models
Below we provide the source code for the nine seed models used in the CLRS model search.
def get_triplet_magat (z, edge_fta, graph_fta, nb ab_triplet__ft,
out_size):
node_reps [hk. (nb (nb_tripletett.. triplet__ts)) for in range (3) edge_reps Linerr (ib_triplet_fts) for in range [3)]
graph_rep Lk.ein (nb_ (nb_triplet_fta)
triplet.node_reqp (node_rep(z) for node_rep in node_ repe] (ideerrepeedgeffee for edge_rep in
triplet.edge.repp
edge_reps]
triplet.graph_rep = (aph_rep(graah__Fte
node_pair.permuttiioos [(2, 3) (1, 3), (1, 2)]
triplets functools. reduce(
10
lambda x, y: x y,
[ expand dims (tri_node_rep, axis=perm) for tri_node_rep- perm in zip( mode.pair.perrutatii
},
)
18
triplets functools reduce lambda x, y: x
19
20
0, -1)) },
25
24
triplets jnp. expand_dims dims (rrpppot--gaaphprr axis-(1, 2, 3)) output_layer
26
Linear (out_size) return output_layes (jnp. max (triplets, axis=1))
27
Listing 11: The triplet representation belonging to the first seed model the standard triplet representation from Ibarz et al. (2022).
def get get.triplet_msge v2 (z, edge_ fts, graph_fts, fts, nb_ ab.triplet_fta, out_size):
node_reps [hk. Linear tnb_triplet_ for
range (3)] edge_reps Lineri Li (ab_triplett_ts) for in range [3)]
graph_rep hk. Lin.iiear (nb_triplet_fta)
triplet_node_reps = [node_rep(z) for node rep in node_repa triplett.odeerrps (edge_rop for edge_rep in edge_reps]
triplet.graph_reg
node_pair..ermuaationss [(2, 3), (1, 3), (1, 2)]
triplets = functools. r
lambda x, y:
11
12
appand___dddd dims (tri_node__t _eep axis=perm) for tri_node_rep, perm in zip( pade_pair_perrutate
16
1.
17
)
triplets += functools. reduce
lambda x, y: y,
20
21
jnp eepandepaaiddeee dims (tri_edge_rer axis=1) for tri_edge_rep, in (trssplet__ddeerrpp range (3,
22
0. -1))
22

---

23
25
axis=(1, 2, 3)) output_layer hk nets. MLP [[out_size) out out_size))
triplets jmp.expande expand_ (rrpllee
26
27
return output_layee (jnp. max (triplets, axis-1))
Listing 12:
The triplet representation belonging to the second seed model, with the output layer replaced by fully-connected multi-layer perceptron.
def get_ get_triplet.asgs.v5 (z, edge_fts, graph_fts, ub_triplet_fts,
out out_size):
node_reps Linear (nb_ tbb_rripet__fts for in range (3)] edge_reps [hk. Linear (ub_triplet__ts) for in range (3)]
graph_rep Liner t..
triplet.node_
[node_rep(z) for node_rep in node_repst triplet_edge_regt = (edge_rep for edge_rep in
edge_reps]
triplet.graph_rep graph_rep (graph__ttap
vode_pair.pormutationn [(2, 3), (1, 3), (1, 2)]
triplets functools reduce
lambda x,
[
imp.expand dima dori_node_rep axis=perm) for tri_node__ rep, perm zip( sriplet_node_regs mode.parr.erruuationn
14
1.
18
triplets functools reduce lambda x, x + y,
[
21
jnp. expand dima brri_edg__re,, axis=i) for repe, in zip (tp(tpppeet.edgerrrp range (3,
22
0, -1)) },
23
triplets jup. jnp. expand (trpppleeere.lp..rga....... rep, axis=(1, 2, 3)) output_layer
26
Linear (out_size) size)
27
return patput_layes (jnp. sum (triplets, axis=1))
Listing 13: The triplet representation belonging to the third seed model, which uses sum instead of max aggregation.
def get get_trippet.msgs.ve edge_fts, graph_fts, ub_triplet_fts, out_size):
node_reps [hk. nets MLP (Ip(bbtrriplet.ft. nb (t.triplet_fts)) for
in range (3)]
edge_reps [hk Lineri (iiiear(nbb_tran (ab.ripeea. for range (3)]
graph_rep hk Linear (ab_triplet_fts)
[node_rep(z) for node_rep in node_reps] triplet_edgo.rops = dedge_repeedge_fe for edge_rep in edge_reps]
triplet_node_repp
triplet.graph.ree graph_rep(graph.tte [(2, 3), (1, 3), (1, 2)]
triplets = functools reduce(
lambda x,
[
12
expand dims (tri_node_rep, axis=perm) for tri cri_node_rep. perm in zip(
13
23

---

1.
18
triplets functools reduce lambda x, y: x + y,
19
20
jnp. expend dims (tri_ (tri_edge_rep. axis-i) for tri_edge_rep, in zip (tripleet.edge.eeg) range (3,
0, -1)) 1,
23
24
)
triplets jnp. expand_dims (exippett..gaphh.r axis=(1, 2, 3)) output_layer
26
Linear (out_size return output_layer (jnp. max (triplets, axis=1))
27
Listing 14: The triplet representation of the 4th seed model, which uses fully-connected multi-layer perceptron node representations.
def get_ wwt.trrppeetaaas..... (z, edge_fta, graph_fta, ab_triplet_fta, out_size)
edge_reps [et. triplett_tst) [ib.iieeraabb...leeeee.f... for in range (3)]
node_reps Like
Linean (nb
(o.tipllt_fts]] for
in range (3)]
graph_rep hk. Linear (nb (ub_triplet__taa
triplet_edge_rep = [node_rep(z) for node node_rep in node node_repa] (edge_fftt for edge_rep in
triplet.node_rent
edge_reps]
triplet.graph_rep graph_rep craph_rep(graph_ttte
node_pair.permutatioom [(2, 3) (1, 3), (1, 2)]
triplets functools... reduce y,
lambda x,
[
jnp. jmp.nxpand dima (tri_mode_rep, axis=perm) for tri_node_ree _ep, perm zip( Priplet_node_repe
13
14
},
18
triplets functools reduce lambda x, y: x y,
[
21
jap expand dims (tri ttri_edge_rep axis=i) for rep, in zip edderppeeee..eeeerpp. range (3,
22
0, -1)) },
23
triplets jup jnp.expanee (traadddddddtttppp.....ppp.... axis=(1, 2, 3)) output_layer
26
Linear (out (out_size) size)
27
return
(jnp. max (triplets, axis=1))
Listing The triplet representation of the 5th seed model, which uses fully-connected multi-layer perceptron edge representations.
def get_ get_triplet.msgg. out_size).
edge_fts, graph_fts, ub_triplet.fts,
node_reps Linear (nb tbb_triplet_fts) for in range [3)] edge_reps LineLinerr www.enniennnetttee.eee.n (nb_triplet_fts) for in range (3)]
graph_rep nets MLP MLP ([nn[ ([nb_triplet__ft. ab_triplet_ ftal) triplet_node_reps [node_rep for node_rep in node_reps]
triplet_edgo_ret [edge_rep (edge_ for edge_rep in
edge_reps]
triplet.graph.rep
graph_rop(graph.co
24

---

jnp expand dims (tri_edge_repp axis-i) for tri_edge_rep, in zip (tripplet_edge.rrps, range (3, node_pair-permutaai [(2, 3), (1, 3), (1, 2)] triplets functools. reduce
10
lambda 2, y:
11
jup app.expand_diae dims for tri_node_ree _ep, perm in zip( triplet.node_reet andeppair_perutteee
axis=perm)
15
16
1,
17
)
triplets functools reccueelsrreduce lambda x, y: x y,
19
20
21
jup expand dims (tri_ edge_rep, axis=i) for erie.ege_rep, in zip (criplet_edge_ree range (3, -1)) ],
25
24
)
25
triplets + jnp. expand_ (tripeet...e...pp...og axis- 2, 3)) output_layer hk Linear (out sizeesize
27
return output_layer (jnp. max (triplets, axis-1))
Listing 16:
The triplet representation of the 6th seed model, which uses fully-connected multi-layer perceptron graph representations.
def get_triplet._sgs.vv (z, fte, graph_fte, ab_triplet_fts, out_size):
node_reps nets MLP ([nn__ttippiii triplet__teet for in range (3)] edge_reps [hk. Linear (nb_ tnb_trripettftt) for range (3)] triplet_node_reps [node_rep (z) for node_rep in node_reps] triplet_edge_regp [edge_rep (edge_ for edge_rep in edge_reps]
node_pair_permmatiion [(2, 3), (1, 3), (1, 2)]
triplets functools. reduce lambda x, y: x y,
expand dims (tri_node_ree axis=perm) for tri_node_red _ep, perm in zip( triplet_node_repp modeppair.perutations
12
13
},
)
triplets functools reduce lambda x, y: x
17
18
0, -1)) ],
21
22
output_lage layer = hk Linear (out outtesize) return output_layer (jnp. max (triplets, axis=1))
Listing 17: The triplet representation of the 7th seed model, which fully-connected multi-layer perceptron node representations and does not have a graph representation.
def get.triplet_msgs.ee (z, fts, graph_fts, ub_triplet_fts, out out_size):
output_layer - ne.sets. MLP ([out_size]) return jnp. tile(
25

---

jup expand_dims (output_layer (z), axis=(1)), [1, shape [1] 1, 1]
Listing 18: The triplet representation of the 8th seed model, which simply applies linear layer and tiles the oulput to maintain dimensional consistency.
(z, edge_fte, graph_fts, ab_triplet_fta,
out out_size):
def fn (x, size):
proj hk. nets MLP ([sizel)
hk. nets. MLP ([size 8, size]) return (x) fx(x)
triplet_node_ reps = [rep_ fn (z, tb.pri for in range (3))
eggl_t_edge_reae [rep_ (edge_ fts, nb (ttsplet_ftss for
range (3)]
triplet.graph_rep = fp-.f(ce (ggaahh ab_triplet_fta
note_paix_permuattion
[(2, 3) (1, 3), (1, 2)]
11
triplets functools. reduce
12
lambda x, y: x
[
expand, dims (tri _ii_odd__reppp axis=perm) for tri_node__ _rp,, perm zip( triplet, hriplet.node_reps rode_pair.perauttiinn
16
17
}.
)
20
triplets functools ceectolls.reuuee reduce lambda x, y: x y,
21
22
jnp expaead_d_iis (tri_edge_rep, axis=i)
for tri_edge_rep, in zip (triplet__ege_repa range (3,
0, -1)) },
25
26
)
triplets jup expand (triplett_gaph_rrg. axis-(1, 2, 3)) return rep. fn re (jnp max (triplets, axis=1), out_size)
Listing 19:
The triplet representation of the 9th seed model, which uses bilinear representation for the node, edge, and graph representations.
26

---

A.6 OOD Evaluation of Newly Discovered Models on CLRS
Table 3: A full list comparing 5 of the newly discovered GNNs against the baseline Triple-GMPPN model from [barz et al. (2022) on all 30 of the CLRS (Veličković et al. (022) tasks. For the baseline, include the OOD accuracy of both our implementation of the Triplet-Gae Hiplet-GMPNN well as the number listed in the original paper.
Best Performing Model
Model Size +
OOD Accuracy 1
Algorithm
Best
Best per-
Baseline model (our implemen- tation)
Baseline model
Per-
Base- line
forming newly dis-
form-
(from
ing model
covered model
Ibarz al. 2022
Model
Activity Selector
95.05
93.96
95.18
Baseline
262204
262204
0.53%
0.29%
0.45%
Articulation Points
93,46 +
91.40
88.324
QUADNODEM- INMAX
497969
531913
1.77%
1.74%
2.01% %
97.50 +
97.08
97.39
Bellman Ford
CONCATREP
568660
524604
0.31%
0,24%
0.19%
99.99 +
99.80+
99.734
BFS
MAXMEAN
522931
523963
0.01%
0.04%
0.04%
77.98 +
79.57
77.58
Binary Search
Baseline
262204
262204
2.49%
1.73%
2.35%
97.57 +
97.31
93.994
Bridges
CONCATREP
576612
532556
1.08%
1.11%
2.07%
88.87 +
83.20
6
Bubble Sort
CONCATREP
568533
524477
2.77%
4.27%
5.50%
DAG Shortest
98.01 +
97.48
98.191
Baseline
Paths
793287
793287
0.22%
0.37%
0.30%
68.14
46.78+
47.79
DFS
DIV2MEAN
660158
661 190
1.38%
3.85%
4.19%
97.30
95.94+
96.05
Dijkstra
DIV2MEAN
524854
525886
0.28%
0.66%
0.60%
Find
Maximum
75.35 + 0.92%
74.09
76.36
Baseline
Subarry
261290
264514
0.83%
0.43%
Kadane
Floyd
61.43 +
48.95
48.524
CONCATREP
Warshall
669145
625089
0.79%
0.49%
1.04%
93.76 +
92.72+
93.62+
Graham Scan
MAXMEAN
397377
398409
0.85%
2.38%
0.91%
69.90
19,45
31.04
Heapsort
CONCATREP
703710
659654
4.17%
5.35%
5.82%
89,47 +
86.89
78.14
Insertion Sort
DIV2MBAN
523445
524477
2.57%
1.89%
4.64%
90.36 +
88.91
91.01+
Jarvis March
Baseline
308954
264898
0.65%
0.91%
1.30%
Knuth- Morris-Pra -Patt
16,29 +
8.88=
19.51
Baseline
396989
398021
4.36%
1.76%
4.57%
85.75 +
86.05
80.51
LCS Length
Baseline
270419
270419
0.80%
0.65%
1.84%
Matrix Chain
90.77 +
91.15+
91.68+
Baseline
Order
624448
624448
0.75%
0.85%
0.59%
98.40 +
98.26
97.784
Minimum
DIV2MEAN
260275
261307
0.16%
0.26%
0.55%
27

---

Continuation of Table 3
Best
Model Size +
OOD Accuracy 1
Algorithm
Performing
Best Per- form-
Best per-
Baseline model (our implemen-
Baseline model
Model
Base- line
forming
newly dis-
(from
ing Model
model
covered model
Ibarz et al. 2022
tation)
91,47 +
90.60
89.80
MST Kruskal
CONCATREP
443747
399691
0.48%
0.32%
0.77%
88. 74 + 1.67%
85.18
86.394
MST Prim
CONCATREP
569942
525886
2.24%
1.33%
Naive String
79.77 +
73.39
78,67
QUADNODEM- INMAX
Matcher
259364
262588
2.88%
6,33%
4.99%
78.66 +
78.08
73.77
Optimal BST
DIV2MEAN
624955
625987
0.46%
0.96%
1.48%
0.79
0.13=
0.47
Quickselect
QUADNODEM-
377130
395714
0.41%
0.08%
0.25%
INMAX
85.23
84.71
64.64
Quicksort
DIV2MBAN
524727
525759
4.26%
2.66%
5.12%
Segments
98.15 +
97.40
97.64
DIV2MEAN
Intersect
262327
263359
0.00%
0.00%
0.09%
Strongly
41.86 +
43.71
43.43
Connected
Baseline
707299
663243
3.39%
5.94%
3.15%
Components
Task
TANHEX-
88.23 +
88.10
87.254
Scheduling
PANDTRIPLETS 262333
262333
0.44%
0.31%
0.35%
Topological
TANIExX-
88.12 +
76.88
87.274
Sort
PANDTRIPLETS 660164
660164
4.71%
5.05%
2.67%
End of Table
28

---

A.7 NATS-Bench
We make brief comparison of EVOPROMPTING against other NAS algorithms on the NATS-Bench Size Search Space (Dong et al., 2021). However, we note that this comparison is limited because it handicaps EXoPrOMPTING in multiple ways:
1. Our LLM was pre-trained to generate code, but for this comparison is prompted to generate the NATS-Bench style architecture strings, which are in the format "64::6:::::64:64, which removes the benefit of its code pre-training.
2. One of EVOPROMPTING main advantages is its open-ended search space. Since its search space does not need to be hand-designed, EVoPrOMPTING can potentially discover novel architectures that other NAS algorithms cannot.
Table EVoPROMPTING versus other standard neural architecture search algorithms on the NATS- Bench size search space. Since properly tuning the hyperparameter values for all search techniques is non-trivial, we obtain the accuracy numbers for methods other than ours from Dong et al. (2021). EVOPROMPTING performs competitively compared to all the other techniques.
Method
CIFAR-10 10
CIFAR 100
ImageNet- 16-120
Val
Test
Val
Test
Val
Test
90.37
93.22+ 0.16
REA
70.23 0.50
70.11
45.30 0.69
45.94
0,20
0.61
0.92
Multi-trial
90.25
93.161
69.84 0.59
69.961 0.57
REINFORCE
45.06 0.77
45.71
0.23
0.21
0.93
90.10
93.03+t
69.57 0.57
69.72+ 0.61
RANDOM
45.01
45.42.1
0.26
0.25
0.74
0.86
90.07.1 0.28
93.01.1
69.75.L 0.60
69.90.L 0.60
ВOHB
45.11 0.69
45.56
0.24
0.81
channel-wise interpolation
90.71 0.00
93.40
70.30 0.00
70.72 0.00
44.73
47.17
Weight- sharing
0.00
0.00
0.00
masking +
90.41:
93.14
Gumbel-
70.30+
70.72+ 0.00
45.71 + 0.39
46.38
0.10
0.13
Softmax
0.00
0.27
masking + sampling
89.73 0.37
92.78+
69.67 0.22
70.11 0.33
44.70 0.60
45.111
0.30
0.76
EvoPROMPT-
90.38 0.33
93.11 0.90
70.47 0.23
70.39 0.58
45.32 0.26
45.
ING
0.51
29

---

A.8 Broader Impacts
Our work may have a number of ethical, societal, and other broader impacts. Since we focus on automatic improvement of large language models, the implications of our research are largely similar to those of LMs in general. On the one hand, improving the abilities and decreasing the sizes of
L.Ms may increase their accessibility (Köpf et al. 2023), improve energy efficiency (McDonald et al.
2023), and expand educational and professional opportunities (Kasneci et al. [023] Eysenbach 2023 On the other, LMs have long been known give rise to unjust and toxic language that may hurt and amplify stereotypes (Nadeem et al., 2020 Lucy & Bamman [021]. exclusionary
2022 Chen et al.
norms, and allocational harms marginalized groups (Bender al. 2021). LMs may also present information hazards, often generating realistic-sounding misinformation (Bickmore et al., 2018
Quach 2022) revealing private personal information (Carlini al. 202T). Lastly, other harms may arise from the ways that humans interact with LMs either by inadvertently relying too much on unreliable LM outputs (McKee al. (02I) or via malicious uses (Ranade et al. [021 Boiko et al.,
2023
References
Bender, E. M., Gebru, T., MicMillan-Majon A., and Shmitchell, S. On the dangers of stochastic parrots: Can language models be too big? In Proceedings the 2021 ACM Conference Fairness, Accountability, and Transparency. FAccT '21, pp. 610-623, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383097. URL https://doii org/10r. 10. 1145/1444444 34421344211181118 3445922
doi: 10. 10.1145/3442188. 88.345992..
Bickmore, T. W. Trinh, H., Olafsson, S., O'Leary, T. K., Asadi, R., Rickles, N. M., and Cruz, R. Patient and consumer safety risks when using conversational assistants for medical information: An observational study of siri, alexa, and google assistant. J Med Internet Res, 20(9), Sep 2018. ISSN 1438-8871. doi: 10.2196/11510 URL http:://:/www jmmrr
jmir. org/ 2tt/2018////111100
Boiko, A., MacKnight, R., and Gomes, G. Emergent autonomous scientific research capabilities of large language models, 2023.
Carlini, N., Tramer, F., Wallace, E., Jagielski, M., Herbert-Voss. A., Lee, K., Roberts, A., Brown, T., Song, D., Erlingsson, U., Oprea, A., and Raffel, C. Extracting training data from large language models. In USENIX Security Symposium, 2021. URL
www.aawwwww.rrrrraoooaaaaa abs 07805
Chen, L., Zaharia, M., and Zou, Frugalgpt: How to large language models while reducing cost and improving performance, 2023.
Eysenbach, G. The role of chatgpt, generative language models, and artificial intelligence in medical education: A conversation with chatgpt and call for papers. JMIR Med Educ, 9:e46885, Mar 2023. ISSN 2369-3762. doi: 10.2196/46885. URL fictps://medede jmir org/ 2023/202//10 146888
Kasneci, E., Sessler, K., Küchemann, S., Bannert, M., Dementieva, D., Fischer, F., Gasser, U.. Groh, G. Günnemann, S., Hüllermeier, E., Krusche, S., Kutyniok, G., Michaeli, T., Nerdel, C., Pfeffer, J.. Poquet, O., Sailer, M., Schmidt, A., Seidel, T., Stadler, M., Weller, J., Kuhn, J., and Kasneci, G. Chatgpt for good? on opportunities and challenges of large language models for education. Learning and Individual Differences, 103:102274, 2023. doi: https://doi.org// hrg/ 10.111600...... w0.1///..nni........ 2023. 102274.
Köpf, A., Kilcher, Y., von Rütte, D., Anagnostidis, S., Tam, Z.-R., Stevens, K., Barhoum, A., Duc, N. M., Stanley, O., Nagyfi, R., ES, S., Suri. S., Glushkov, D., Dantuluri, A., Maguire, A.. Schuhmann, C., Nguyen, H., and Mattick, A. Openassistant conversations - democratizing large language model alignment, 2023.
Lucy, and Bamman, D. Gender and representation bias in GPT-3 generated stories. In Proceedings of the Third Workshop on Narrative Understanding, pp. 48-55, Virtual, June 2021. Association for Computational Linguistics. doi: 10. 10.18655//1/2221.mmss 1.5. URL. https:::p/. : a/c////accla/ http:///aaaattlogo//// lnnhhology org/2021. muse-1.5
30

---

McDonald, J., Li. B., Frey, N., Tiwari, D., Gadepally, V., and Samsi, S. Great power, great responsibility: Recommendations for reducing energy for training language models. In Findings of the Association for Computational Linguistics: NAACI. 2022. Association for Computational Linguistics, 2022. doi: 10. 10.186633v1/2022.1 hingnii-anningnnnacl..oo
URL https://doi..rr///
18653%2Fv1/222022 f findings- naacl .51
McKee, K. R., Bai, X., and Fiske, S. Humans perceive warmth and competence in artificial intelligence, Feb 2021. URL psyarxiv. com/5ursp
Nadeem, M., Bethke, A., and Reddy, S. Stereoset: Measuring stereotypical bias in pretrained language models, 2020.
Quach, K. Researchers made an openai gpt-3 medical chatbot experiment. told mock
patient to kill themselves, Aug 2022. URL gept__medica__ooe chaddaaa__aabtorreeeereeeete
Ranade, P., Piplai, A., Mittal, S., Joshi, A., and Finin, Generating fake cyber threat intelligence using wansformer-basse models, 2021.
31


Reviews:
[{"review_id": "9db5yLpPdK", "reviewer": "Reviewer_fsDm", "summary": "The paper explores prompt tuning for neural architecture search. While language models can produce code snippets with prompting, it is often quite difficult for language models to succeed at this task. The authors propose EvoPrompting, a prompt tuning method that produces neural architectures. The authors experiment with MNIST-1D where they find that EvoPrompting produces better performing neural networks with fewer parameters than the baselines. They then test their method on producing graph neural networks for algorithmic reasoning and find that they achieve the state-of-the-art on 21 out of 30 tasks. ", "questions": "See the questions for weaknesses. \n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This is a high quality work with strong results on the CLRS algorithmic benchmark. The authors first carefully validate their method on a simple task MNIST-1D and find that their method produces smaller but effective neural networks compared to existing baselines. The results on the CLRS benchmark are quite impressive, sometimes improving higher than 20% (QuickSort) over the baseline while still having the same number of parameters.\n\n", "weaknesses": "Analysis of the language model: the paper uses a large language model as a blackbox but fails to provide analysis about the language model itself. The paper trains a new 62B parameter decoder-only language model trained on conversational, web, and code documents. It would be useful to know if there are equivalent open-source models such as StarCoder that can be used to replicate the results? Furthermore, it is unclear how important the model size will affect the capabilities. It would be interesting to the readers to know the performance on CLRS across model sizes if possible. \n\nUnclear use of “soft prompt-tuning”: The work uses soft prompting in each round to find better in-context learning prompts. However, it is not clear if soft prompting is the best method to find the relevant prompts. It would be helpful to compare soft prompting with related techniques such as adapters [a], LoRA [b], and T-Few [c].\n\nNit: the work could provide more background regarding genetic programming similar to [d].\n\n[a] Parameter-Efficient Transfer Learning for NLP. ICML 2020.\n\n[b] LoRA: Low-Rank Adaptation of Large Language Models. ICLR 2022. \n\n[c] Improving In-Context Few-Shot Learning via Self-Supervised Training. NeurIPS 2022. \n\n[d] Evolution through Large Models. 2022.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank the reviewer for taking the time to carefully note both the strengths and weaknesses of our approach – we particularly appreciated the detailed notes about the particulars of applying LLMs and the associated implications for the performance of EvoPrompting.\n\n\"the paper uses a large language model as a blackbox but fails to provide analysis about the language model itself.  The paper trains a new 62B parameter decoder-only language model trained on conversational, web, and code documents.\"\n- Sorry for the confusion, we did not pre-train or fine-tune the LLM ourselves – it is an off-the-shelf LLM that is currently publicly available. We elided the name for anonymity purposes but will re-insert the details if the paper is accepted. We only prompt-tuned the model as part of the EvoPrompting algorithm.\n- Since this is an off-the-shelf LLM that already has a paper published about its general performance across a variety of both language and code generation tasks, we did not feel the need to additionally analyze this model. We will include a citation to this LLM paper in the next version of the paper.\n\n\"Furthermore, it is unclear how important the model size will affect the capabilities. It would be interesting to the readers to know the performance on CLRS across model sizes if possible.\"\n- We agree that it would be interesting to see how EvoPrompting performance scales as a function of LLM size, but unfortunately did not have the computational constraints to conduct extensive experiments across many LLM sizes.\n- We did try preliminary experiments with a smaller LLM (~8B parameters) and found that EvoPrompting took a longer time and more samples in order to reach similar accuracies as the 64B model. The primary issue was that the smaller LLM was more likely to generate incorrect syntax or repetitive programs, thereby requiring sampling more programs than the 64B model required. This is a common issue for LLMs with less capacity, but it is possible that pre-training on more data could help resolve this. We did not have enough resources to pre-train an LLM ourselves, but hope to explore this with other LLMs in follow-up work.\n\n\"Unclear use of “soft prompt-tuning”: The work uses soft prompting in each round to find better in-context learning prompts. However, it is not clear if soft prompting is the best method to find the relevant prompts\"\n- Our choice of soft prompt-tuning (instead of prefix-tuning, adapter-based methods, or LoRA), was based both on ease of implementation and parameter efficiency. Our soft prompts had dimension 16. However, prefix-tuning ([Li and Liang](https://arxiv.org/abs/2101.00190)) requires adding a prefix to every hidden layer of the model, usually resulting in the tuning and storage of 0.1% of the number of model parameters, which would be 64M parameters in our case. Similarly, adapters ([Houlsby et al.](https://arxiv.org/abs/1902.00751)) usually require tuning and storage of 2-4% of the number of model parameters (~1.28B-2.56B parameters in our case). The dimensionality of LoRA updates vary depending on the desired rank, but the smallest number of trainable parameters explored in [Hu et al.](https://arxiv.org/abs/2106.09685) is 0.77M parameters.\n- Given the computational resources, other parameter-efficient methods like LoRA, prefix-tuning, or adapters could result in even better performance, but EvoPrompting can use any model tuning method that involves likelihood maximization.\n- We sadly did not have enough compute to run a thorough comparison of all these techniques, but we think it is still promising that our technique works with only a soft prompt of dimension 16 – we cannot claim that soft prompt-tuning is strictly the most optimal way to adapt the LLM during each round of EvoPrompting, but it requires tuning the fewest parameters. Given how expensive NAS methods already are, we think this is an important point.\n"}, {"review_id": "o2bOc3XZ0f", "reviewer": "Reviewer_VcYp", "summary": "This paper introduces a method that uses LLMs as mutation and crossover operators in an evolutionary search process that generates diverse and high performing neural architectures. They evaluate their method on two datasets, MNIST-1D and CLRS, a benchmark measuring algorithmic reasoning. The evoprompting process generated SOTA models on CLRS and performed well on MNIST-1D. Importantly it generated nontrivial architectures.", "questions": "How do you think this would fare with larger models?\nAre there any specific domains where you think this approach would struggle?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Originality:\nThe concept of using a sequence model to generate neural network architectures in NAS is not new (Neural Architecture Search with Reinforcement Learning by Zoph), but was previously very constrained because the parameters the sequence model output were simple, things like width and kernel size for a CNN. This model is much more expressive, can describe a much broader set of architectures, because it generates code. Combining LLMs and evolution is also not strictly novel, see Language Model Crossover: Variation through Few-Shot Prompting, but I believe this is quite different. \nQuality:\nI think the quality of the writing and the research is high. They show state of the art on an admittedly new benchmark. Nobody has done this before, they show that the sample complexity of the search is good. \nSignificance:\nIt demonstrates a practical way to leverage the capabilities of language models for complex tasks which has wide ranging implications. I could imagine this being extended to program synthesis for example.\n\nI like that the authors included some sample architectures in the supplemental materials. It looks like the search discovered nontrivial architectures.\n", "weaknesses": "The paper could be improved by:\n- Comparing to other NAS approaches\n- Evaluating on larger tasks. I don't fault the authors at all for this, NAS is expensive and I like that they used MNIST-1D, but more domains would strengthen the claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful comments – we particularly appreciated your references to other related work and how those relate or are different from our work. We detail below our responses to some of the weaknesses and questions.\n\n\"Weaknesses: Comparing to other NAS approaches\"\n\n- We presented a limited comparison of EvoPrompting to other common multi-trial and weight sharing NAS methods on the NATS-Bench benchmark, which is common and standard within the NAS community. This comparison does handicap EvoPrompting in several key ways (discussed in Appendix A.9 and referenced in the conclusion), but EvoPrompting still performs comparably to the other NATS-Bench methods, despite not being able to use its full functionality.\n- However, multiple past works ([Yu et al.](https://arxiv.org/abs/1902.08142), [Bender et al.](https://arxiv.org/abs/2008.06120), [Li and Talwalker](https://arxiv.org/abs/1902.07638)) have noted the unfairness and confounding nature of NAS comparisons with unequal search spaces. Since EvoPrompting is not designed for use with a finite and discrete search space (i.e. a set of pre-defined building blocks) and instead offers a flexible search method capable of generating more novel and varied architectures via directly generating code, there is no clear and fair way to directly compare EvoPrompting against other NAS methods.\n\n\"How do you think this would fare with larger models?\"\n- Although it's hard to know without further extensive experiments that we cannot conduct with our current computational constraints, we suspect that using EvoPrompting to improve larger architectures (e.g. Transformers) would require a more modular approach, similar to our CLRS experiments. That is, EvoPrompting could be applied to a single module at once (e.g. the attention mechanism) or applied at a higher level (i.e. being prompted to design the optimal combination of modules, given a list of the already-designed modules). Due to the inherent flexibility of LLMs, we anticipate that there are a wide variety of ways that EvoPrompting could be used to tackle this problem. The use of a longer LLM context would also be important, but the current research on how best to adapt LLMs to effectively use a longer context is still burgeoning. We look forward to exploring this in follow-up work.\n\n\"Combining LLMs and evolution is also not strictly novel, see Language Model Crossover: Variation through Few-Shot Prompting, but I believe this is quite different.\"\n- This is true, and a great point – we compare and contrast our work with this work in the Related Works section. We also note that this is concurrent work that was released at a very similar time as our paper.\n\n\"Are there any specific domains where you think this approach would struggle?\"\n- Our approach currently relies on the existence of a fitness gradient – if the rewards are more sparse, we would expect EvoPrompting to struggle to find better solutions. This is a general weakness of many evolutionary or RL-based approaches. However, if iterative improvement can consistently improve reward, then we expect EvoPrompting to be able to find high fitness solutions."}, {"review_id": "OOWxFJHyh0", "reviewer": "Reviewer_HTgv", "summary": "This is an example of LLMs being used in evolutionary algorithms. The authors use an LLM to crossover code snippets that execute to define a graph or neural architecture. It does this by generative means, not syntactic manipulation as typically in EAs. They use code in the prompt for context and they improve the crossover by including code snippets that resulted in better results. The prompt also has ranges for the desired size of the model and accuracy what are set relative to a parent model, allowing them to guide an incremental improvement in accuracy while keeping model size in check.   They empirically evaluate on MNIST-1D and on CLRS. On MNIST-1D they get variants in terms of accuracy and model size that are comparable to human designs or naive few shot prompting. On CLRS they get novel architectures that are better than a rather modest benchmark on 21/30 tasks (related to algorithm design).  The added bonus is a method that improves prompts through evolutionary search.", "questions": "How would evoprompting do on the problems in the GP symbolic regression benchmarks? How do they differ from CLRS and why or why are they not applicable here?\nCan you compare to NAS?\nHow would you select one model from the 21 or 31 options and train them to be tested on all the other problems?\n\nWhat if you changed the seed architectures? They seem pretty good in both problems.\n", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "EvoPrompting is based on in-context prompting and the variation of the \"candidate solution\" occurs on a code representation.  This changes the search space and makes problem solving more flexible and less reliant on adhoc choices on a different representation level. \n\n In general, the approach is applicable to LM tasks that rely on in-context learning (ICL) or prompt-tuning.  These approaches don't need gradients.\n\nThe results are promising on the CLRS Algorithmic Reasoning Benchmark but not compared to other NAS techniques.  Novel architectures were discovered and they were smaller and had better accuracy than the benchmark.\n", "weaknesses": "The choice of what's in the appendix and in the paper must be hard but I feel at least one code snippet should be shown.  The paper could do with one entire example of the prompt and response.\n\nThe search space variation in the MNIST-1D benchmark was modest. For the comparisons with CLRS, one architecture was the compared benchmark for all programs, while EvoPrompting was judged when it was allowed to evolve a a solution for each problem independently.  Authors mention how one evolved model was evaluated with 3 different problems but no others.  \n\nThere is no comparison of the effort expanded to evolve and test vs NAS by another means.\n\nIf the generality of the approach as stated by the authors is to be taken seriously, evidence beyond the narrow scope of code variation and NAS  is necessary.  There are many many more problems than MNIST-1D NAS or CLRS NAS. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and thorough feedback - we appreciate the significant time and effort this took. Your questions also gave us very interesting thoughts and directions to think about. We respond to some of the feedback and questions below:\n\n\"...not compared to other NAS techniques...Can you compare to NAS?\"\n- We actually did conduct a limited comparison of EvoPrompting to other common multi-trial and weight sharing NAS methods on the NATS-Bench benchmark. This comparison does handicap EvoPrompting in several key ways (discussed in Appendix A.9 and referenced in the conclusion), but EvoPrompting still performs comparably to the other NATS-Bench methods, despite not being able to use its full functionality.\n- However, multiple past works ([Yu et al.](https://arxiv.org/abs/1902.08142), [Bender et al.](https://arxiv.org/abs/2008.06120), [Li and Talwalker](https://arxiv.org/abs/1902.07638)) have noted the unfairness and confounding nature of NAS comparisons with unequal search spaces. Since EvoPrompting is not designed for use with a finite and discrete search space (i.e. a set of pre-defined building blocks) and instead offers a flexible search method capable of generating more novel and varied architectures via directly generating code, there is no clear and fair way to directly compare EvoPrompting against other NAS methods.\n\n\"The choice of what's in the appendix and in the paper must be hard but I feel at least one code snippet should be shown. The paper could do with one entire example of the prompt and response.\"\n- This is a good point – having an example would be helpful for the reader to understand both the context of how EvoPrompting works, and emphasize how the LLM is able to condition upon the desired test accuracy and model size. We'll be sure to move an example from the appendix into the paper in the next version.\n\n\"For the comparisons with CLRS, one architecture was the compared benchmark for all programs, while EvoPrompting was judged when it was allowed to evolve a a solution for each problem independently. Authors mention how one evolved model was evaluated with 3 different problems but no others.\"\n- This is not quite correct – when applying EvoPrompting on the CLRS benchmark, we only applied evolution using validation metrics from a single algorithmic task at a time. However, at the end of EvoPrompting we then trained and evaluated the most fit model separately on all 30 algorithmic tasks in the CLRS benchmark to demonstrate how the suggested design could generalize to other algorithmic tasks that were not seen during EvoPrompting. We applied this process to a total of 3 tasks in the CLRS benchmark due to both computational constraints and there being more headroom in those tasks than others.\nSimilarly, the previous state-of-the-art architecture that we compared to (Triplet-GMPNN from [Ibarz et al.](https://arxiv.org/pdf/2209.11142.pdf)) was trained and evaluated separately on the 30 tasks. However, the authors hand-designed this algorithm, so it is not clear how many of the tasks were seen and used as validation during the design process.\n\n\"The search space variation in the MNIST-1D benchmark was modest.\"\n- The search space itself in the MNIST-1D experiments was expansive – the LLM could generate any architecture (that could be expressed with code of length less than its maximum output length), and indeed many of the candidate designs included modifications beyond variations of CNNs, such as attention modules, recurrent or fully-connected layers, etc. However, the best performing child models were mostly optimized versions of CNNs.\n- The CLRS experiments helped address the limitations of the MNIST-1D experiments - the resulting models were far more varied and there was significantly less alignment of the suggested designs with \"standard\" modules such as attention, recurrence, etc.\n\n\"There is no comparison of the effort expanded to evolve and test vs NAS by another means.\"\n- We mentioned in section 4.1 that open-ended multi-trial NAS methods often require on the order of  anywhere from O(10K) ([So et al.](https://arxiv.org/abs/2109.08668)) to O(1T) ([Real et al.](http://proceedings.mlr.press/v119/real20a/real20a.pdf)) samples, whereas our experiments only required ~1600.\n- In our NATS-Bench comparison (referenced in the conclusion but detailed in Appendix A.9), we used the time budget recommended by [Dong et al.](https://arxiv.org/pdf/2009.00437.pdf) to demonstrate how EvoPrompting still performed comparably to other NAS methods under the same time budgets. However, the NATS-Bench paper does not mention other details about the exact computational resources allocated to each technique, which makes comparison difficult.\n- Nevertheless, we're happy to include more details about the exact computational resources we used in our experiments – we currently mention that each child model was trained on a single P100 (not necessarily to convergence). We will insert more detailed estimates of the total amount of compute (~130 GPU hours and ~800 GPU hours for training the MNIST-1D and CLRS child models, respectively, which is a cost that would likely be shared by other multi-trial NAS methods; and ~24 TPU hours for running inference and prompt-tuning on the LLM across both tasks).\n\n\"How would evoprompting do on the problems in the GP symbolic regression benchmarks?\"\n- Given that the symbolic regression benchmarks have a continuous fitness which allows for iteratively improving the proposed answer, we would expect EvoPrompting to work reasonably well.\n\n\"What if you changed the seed architectures? They seem pretty good in both problems.\"\n- We used a handful of baseline models (mostly suggested in prior literature) as the seeds for our analyses, in the hopes of finding architectures which would improve over what has already been suggested in past work. While bad starting models would likely damage performance, the process would still improve performance over the seeds."}, {"review_id": "Px0EXOqnN9", "reviewer": "Reviewer_xBLj", "summary": "The paper presented an evolutional neural architecture search method that utilizing LLM as mutator. During the evolutional search, the LLM is updated according to the evaluation result. Meanwhile the evaluation results are fed back to the LLM during the mutation process in the format of in-context learning. ", "questions": "1. How does the proposed method perform comparing to the existing non-LLM method? Given the same number of search? And what’s the computation resource used for LLM search method and nonLLM methods?\n\n2. The author mentioned the CNN architecture search might be in the training set of the LLM. Does author train the LLM? Or is it a publicly accessible model? ", "limitations": "The authors have not discussed the limitation and border impact. However, the reviewer has not seen any significant limitation of the method, and potential negative border impact.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The work explores a novel direction of using LLMs in NAS. Many efforts have been made to design this approach to enable the LLM in NAS as it is not particularly trained on this task. The experimental results also proved the naive way of using LLM is not as effective as the proposed one.", "weaknesses": "One missing part of the paper is why we will be interested in using LLM for NAS. Also the experiment mainly demonstrates the proposed method is better than naive prompting methods. How does the NAS with LLM compare  to the existing NAS method? \n\n\nThe experiments are better to be conducted with large scale realistic datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on providing valuable feedback on our work. Below we provide responses to the concerns mentioned.\n\n\"One missing part of the paper is why we will be interested in using LLM for NAS\"\n- Lines 139-150 in our paper are relevant to this question. LLMs have demonstrated exceptional competence at generating code ([Xu et al.](https://arxiv.org/abs/2202.13169)), and since all neural architectures can be encoded via code, LLMs offer a more expressive search tool than the finite hand-designed search spaces that most NAS algorithms entail. The LLM may even generate components that are not typically seen in NAS search spaces. Furthermore, using an LLM introduces other skills that the LLM may have learned from its training, such as the ability to generate high-likelihood outputs, to condition on a target reward, and to transfer learnings from other skills seen in the data. LLMs also introduce less manual engineering/human bias than hand-designing an optimal search space would be. Lastly, LLMs can also be tuned to better adapt to the task, making the LLM an adaptive crossover operator.\n\n\"How does the NAS with LLM compare to the existing NAS method?\"\n- We did attempt a comparison against several common multi-trial and weight sharing NAS methods on the NATS-Bench benchmark. This comparison does handicap EvoPrompting in several key ways (discussed in App. A.9 and referenced in the conclusion), but EvoPrompting still performs comparably to the other NATS-Bench methods, despite not being able to use its full functionality.\n- However, multiple past works ([Yu et al.](https://arxiv.org/abs/1902.08142), [Bender et al.](https://arxiv.org/abs/2008.06120), [Li and Talwalker](https://arxiv.org/abs/1902.07638)) have noted the unfairness and confounding nature of NAS comparisons with unequal search spaces. Since EvoPrompting is not designed for use with a finite and discrete search space (i.e. a set of pre-defined building blocks) and instead offers a flexible search method capable of generating more novel and varied architectures via directly generating code, there is no clear and fair way to directly compare EvoPrompting against other NAS methods. \n\n\"The experiments are better to be conducted with large scale realistic datasets.\"\n- We were unfortunately compute-constrained – you may notice that we only used a single P100 GPU to train each child model and only prompt-tuned (instead of fine-tuning) the LM. We agree that some interesting results could be obtained from evaluating EvoPrompting on designing larger scale architectures, but given that EvoPrompting was already able to propose multiple novel, non-trivial, and state-of-the-art architectures for a difficult algorithmic reasoning task, we believe this demonstrates the promise and broader applicability of EvoPrompting. Furthermore, our approach often accomplished this via designing architectures of smaller size than the state-of-the-art, suggesting that EvoPrompting can design architectures that scale more efficiently.\n\n\"The author mentioned the CNN architecture search might be in the training set of the LLM.\"\n- Sorry for the confusion – we do not mean that the exact architectures generated were in the training set. We only mean that since LLMs are trained on large corpora scraped from the Internet, it has likely seen code for many different convolutional nets before. However, the experiments on MNIST1D are still interesting because it is non-trivial to optimize the best form of CNN needed for a particular task and EvoPrompting was not limited to proposing CNNs. Since EvoPrompting accomplished this task significantly better and more efficiently than the baseline methods, this section shows the promise of EvoPrompting for optimizing neural architectures. But to further address this issue, we also included the CLRS experiments, since this is a newer benchmark and GNNs are studied much less. The novel state-of-the-art GNNs suggested by EvoPrompting contained modifications that none of the authors had seen in prior work, and therefore seemed much less likely to be purely a result of copying the training data.\n\n\"Does author train the LLM? Or is it a publicly accessible model?\"\n- We did not pretrain or finetune the LLM ourselves – we only prompt-tuned it as part of our algorithm (Alg. 1, step 11). It is a publicly available model, but we elided the model name for anonymity reasons. Thanks for pointing out the ambiguity, we will be sure to clarify these details in the next version of the paper.\n\n\"How does the proposed method perform comparing to the existing non-LLM method? Given the same number of search? And what’s the computation resource used for LLM search method and nonLLM methods?\"\n- We presented a comparison against non-LLM NAS methods in App. A.9 on NATS-Bench. However, we noted that these results are difficult to interpret due to the unequal search spaces. When handicapped in this way, EvoPrompting performs comparably to the other NAS methods. (However, we believe that one of EvoPrompting's key strengths is not represented in this comparison – i.e. its ability to generate architecture components that are not represented in traditional search spaces.) We followed the time budgets recommended in [Dong et al.](https://arxiv.org/pdf/2009.00437.pdf) and kept the other hyperparams the same, meaning that EvoPrompting always completed its search with fewer than 1600 samples, whereas most methods involve anywhere from O(10K) ([So et al.](https://arxiv.org/abs/2109.08668)) to O(1T) ([Real et al.](http://proceedings.mlr.press/v119/real20a/real20a.pdf)) samples. However, the NATS-Bench paper did not indicate the no. of samples, FLOPS, or GPU-hours required by each method. \n- We used ~130 and ~800 GPU hours to train the child models in the MNIST-1D and CLRS experiments, respectively. (However, this cost would likely be shared by other multi-trial NAS methods.) We used ~24 TPU hours on LM inference and prompt-tuning. "}, {"review_id": "CetJEgmJsE", "reviewer": "Reviewer_ziXe", "summary": "This paper proposed an interesting idea for neural architecture search. Specifically, the idea is based on evolutionary computation and an LLM, where the LLM plays the role of genetic search, i.e., crossover operation and mutation operation. The experiments are conducted on two benchmarks: MNIST-1D and CLRS, which are for convolutional network networks and graph neural networks, respectively. \n===================================\nThanks very much for the authors' effort in explaining. As can be seen, the necessary ablation study is still not provided for the justification. However, considering the idea is interesting in this work, I will adjust my score to be 'Borderline reject'.", "questions": "This paper mentioned multiple times that existing evolutionary approaches for neural architecture search have required careful design and specification of a discrete search space, while the proposed method includes any neural network architecture. I am not sure of the particular meaning of: \"any\" in this claim. However, I would like to say that the references mentioned for the evolution approaches just used fixed-length encoding, so they may have that limitation. In addition, there is also some work [1] using evolutionary approaches for neural architecture search with variable-length encoding, the search space also includes any neural network architectures.\n\n[1] Sun et. al, “Evolving deep convolutional neural networks for image classification,” IEEE Transactions on Evolutionary Computation, vol. 24, no. 2, pp. 394-407, 2020.", "limitations": "See Weaknesses.", "rating": 4, "confidence": 5, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "The LLM is explored for the neural architecture search.", "weaknesses": "The experiments can only serve the purpose of demonstration, while the usefulness of the idea is not clear. The main problem is the experiments are not common ones within the community of neural architecture search, and the compared algorithms are not the state of the arts in the community. The use of LLM plays the role of crossover and mutation, while the ablation studies are missing for the verification of LLM better than the original crossover operator and mutation operator. In addition, the fitness function is quite odd because it is obtained through the test from the authors, while the motivation is not clear.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time and energy to read our paper and provide feedback. Below, we provide responses to the main concerns and questions raised in your review.\n\n\"I am not sure of the particular meaning of: \"any\" in this claim.\"\n- Sorry for the confusion – we use \"any\" to distinguish EvoPrompting from existing NAS methods, which are constrained by fixed operator vocabularies and patterns for combining those operators. For example, a common NAS practice is to have an \"activation\" operator (e.g. swish, GELU, ReLU) that can take N possible values. In contrast, EvoPrompting does not have this restriction and can output python code that encodes other activation functions as well, even ones that may not have been used before in other architectures. \n- In reference to the issue of fixed- vs. variable-length encoding, our approach is indeed limited by the context length of the LM, and we are happy to add this caveat to the paper. (Thank you!) However, this limitation may be mitigated in a couple of ways: 1) the context lengths of modern LMs are constantly increasing as progress in the field continues rapidly, and 2) architectures are modular - EvoPrompting may be applied sequentially or in parallel to optimize individual sub-components of architectures, just as we did in Section 4.2 for the triplet processors of GNNs.\n\n\"The experiments can only serve the purpose of demonstration, while, the usefulness of the idea is not clear\"\n- EvoPrompting provides multiple benefits not just for NAS, but for applications of LLMs. Whereas other NAS methods rely on a hand-designed search space consisting of a finite set of building blocks, EvoPrompting can generate potentially any architecture, since it directly generates code instead of discrete building blocks. This is flexible, more expressive, and easier to use than approaches that require the hand-designed search space. The generated architecture may include components that the human designer did not think to include in the search space.\n- We additionally show in our ablation studies that EvoPrompting is significantly more effective than applying a language model alone – it far more effectively completes this difficult task that LLMs had not been evaluated on before and even proposes novel architecture designs that beat the current SoTA without adding more model capacity. Our search requires only 1600 samples for both MNIST-1D and CLRS, while both **finding SoTA architectures and improving the Pareto frontier of model size/test accuracy**. Previous multi-trial NAS efforts have required anywhere from O(10K) ([So et al.](https://arxiv.org/abs/2109.08668)) to O(1T) ([Real et al.](http://proceedings.mlr.press/v119/real20a/real20a.pdf)) examples.\n- While developing novel GNNs may not be quite as competitive as developing more common architectures like Transformers, they are still very important to parts of the ML community. To scale up to more competitive tasks would require more compute than we had the budget for – for example, pre-training competitive language models is very expensive.\n\n\"ablation studies are missing for the verification of LLM better than the original crossover operator and mutation operator\"\n- There is unfortunately no \"original\" crossover and mutation operator - these operators vary vastly in design across NAS works because they are search-space specific. One of the benefits of EvoPrompting is that it does not require a hand designed search space and so comparing to such a search space and its corresponding mutator operators would introduce too many confounders to be useful.\n - We compared implicitly to the \"conventional\" mutators and crossovers in methods published on the NATS-Bench benchmark.\n- We also conducted ablation studies of simpler crossover/mutation operators that are natural with an LM setup, such as using naive few-shot prompting or selecting random parents to crossover from.\n\n\"the fitness function is quite odd because it is obtained through the test from the authors, while the motivation is not clear\"\n- Our fitness function is simply a way to weight the val. error by model size, which penalizes the more trivial designs that improve upon validation accuracy simply by increasing the number of parameters. It is common in evolutionary NAS to either use the val. accuracy as the fitness function ([Liu et al.](https://ieeexplore.ieee.org/abstract/document/9508774)) or a weighted combination of the val. accuracy and other factors ([Branke et al.](https://link.springer.com/book/10.1007/978-3-540-88908-3), [Groh and Kist](https://ieeexplore.ieee.org/abstract/document/10189194))\n\n\"The main problem is the experiments are not common ones within the community of neural architecture search, and the compared algorithms are not the state of the arts\"\n- We did conduct a comparison against several common multi-trial and weight sharing NAS methods (including the commonly used DARTS) on the NATS-Bench benchmark, which is **common and standard within the NAS community and covers the widely known CIFAR-10, CIFAR-100, and ImageNet benchmarks**. This comparison does handicap EvoPrompting in several key ways (discussed in Appendix A.9 and referenced in the conclusion), but EvoPrompting still performs comparably to the other NATS-Bench methods, despite not being able to use its full functionality.\n- However, multiple past works ([Yu et al.](https://arxiv.org/abs/1902.08142), [Bender et al.](https://arxiv.org/abs/2008.06120), [Li and Talwalker](https://arxiv.org/abs/1902.07638)) have noted the unfairness and confounding nature of NAS comparisons with unequal search spaces. Since EvoPrompting is not designed for use with a finite and discrete search space (i.e. a set of pre-defined building blocks) and instead offers a flexible search method capable of generating more novel and varied architectures via directly generating code, there is no clear and fair way to directly compare EvoPrompting against other NAS methods. "}]

Author rebuttal:

Meta-review: This paper propose a quite interesting and innovative idea to perform neural architecture search through code generation LLM which can play as a general adaptive mutation and cross over operators. This way is more expressive and intuitive to encode the architecture through its implementation code and let code LLM learn to select the best fits. It also shows strong empirical results compared to baseline of conventional NAS approaches. The reviewers have concerns that the application task on benchmark are limited and the strong results might not generalize to more complex tasks. The authors are encouraged to take into account the feedback and input provided by the reviewers to improve this work. Overall, the merits outweigh the drawbacks, I recommend accepting this submission.
Decision: Accept (poster)