What our NAS paper actually found | Grid vs. random vs. genetic, seven years on

In December 2019 my brother and I put a short paper on arXiv called Grid Search, Random Search, Genetic Algorithm: A Big Comparison for NAS. It is not a complicated piece of work. We took three search algorithms that any undergraduate has met, pointed them at the problem of designing a convolutional network, trained everything on CIFAR-10, and wrote down how long each one took and how accurate the resulting models were.

We were both working on our master’s theses at the time, and the paper came out of that — a question we needed answered for our own work, written up because nobody seemed to have written it up plainly.

It has since been cited around 1,650 times — more than everything else I’ve published put together, by a wide margin. That gap is interesting enough on its own that I want to come back to the paper: what it actually says, what it doesn’t, and why I think the simple thing outran the clever things.

Neural architecture search, without the jargon

When you train a neural network you are adjusting weights. The shape of the network — how many convolutional layers, how many fully-connected layers after them, how many filters each one has — isn’t learned. Somebody chooses it, usually by copying a known-good design and nudging it.

Neural architecture search is the idea of automating that choice: search a space of designs, not a space of weights. The uncomfortable part is what evaluating a candidate costs. To score one point in the space you have to train that architecture, which in our case meant 50 epochs on CIFAR-10. In ordinary optimisation you evaluate a candidate in microseconds. Here a single evaluation takes minutes to hours. Every property of every search algorithm has to be re-read in that light.

The three strategies

Grid search enumerates. You list the values each parameter may take, and you try every combination. It is exhaustive over the grid you defined, which is its virtue and its whole problem: the cost is the product of the list lengths, so the grid you can afford is tiny, and anything interesting outside it is invisible.

Random search samples. You define ranges rather than lists, draw configurations at random, and run as many as your budget allows. It guarantees nothing. In exchange, its cost is decoupled from the dimensionality of the space — you decide how many runs you can afford, and that’s the bill. It also reaches values a grid would never have contained, because you were never asked to name them in advance.

A genetic algorithm breeds. Encode an architecture as a string of bits, evaluate a population of them, keep the ones that score well, recombine and mutate them into the next generation. It has more knobs than the others — population size, generation count, encoding — but those knobs are how you buy control over a space too big to enumerate and too big to sample usefully at random.

The setup

The search space was macro-level: a fixed base CNN, into which the search inserts some number of convolutional cells and some number of dense cells. The base model — He uniform initialisation, L2 weight decay of 10⁻⁴, 32 filters in the first convolution, Adamax at a learning rate of 2×10⁻³, dropout, 512-unit dense cells — reached 76% after 50 epochs. That is the number everything else has to beat.

Every candidate was trained for 50 epochs on CIFAR-10 with standard augmentation, on a single Tesla K80. The comparison was on execution time as well as accuracy, and that framing is the part I’d defend hardest. A search method that finds a marginally better architecture in three times the compute has not obviously won anything.

The budgets each algorithm got:

grid search     conv cells ∈ (0, 2, 3, 4) × dense cells ∈ (1, 2)   → 8 models
random search   conv ~ U[2,8], dense ~ U[1,4]                      → 5 runs
genetic         population 2, 8 generations, genome 8 bits         → 4 bits conv, 4 bits dense

What the results showed

Method	Wall clock	Best accuracy	Best architecture
Grid search	≈4.3 h	83%	2 conv, 2 dense
Random search	≈2.7 h	≈86%	4 conv, 1 dense
Genetic algorithm	≈4.13 h	≈86%	10 conv, 1 dense

Three things fall out of that table.

Random search won on time and tied on accuracy. Five random draws, 2.7 hours, 85.8%. The exhaustive grid took 4.3 hours to reach 83%. This is not a subtle margin, and it is not a new result — it’s Bergstra and Bengio’s 2012 finding reproduced in a NAS setting. Grids waste evaluations on parameters that don’t matter, because every combination re-tries every value of the parameters that don’t affect the outcome.

Cell count alone doesn’t tell you much. Along the grid, accuracy peaked at 2 convolutional cells and then fell: 83% at 2, 81.8% at 3, 80.9% at 4. Yet random search’s best model had 4 convolutional cells at 85.8%, and the genetic algorithm’s best had 10 at 85.7%. The difference is that the grid held everything else fixed while varying the counts, and the other two varied the per-layer hyperparameters too. A depth that looks bad under one set of filter and kernel choices is fine under another — which is precisely the interaction a grid over two axes cannot see. Both of the wider searches did agree on one thing: one dense cell, not two. Depth in the classifier head bought nothing.

Small models were competitive. The two configurations with no convolutional cells at all were the largest by parameter count — 4.2M and 4.4M — and the weakest, at 75% and 77%. The best random-search model was 0.66M parameters at 85.8%; the best genetic one was 0.49M at 85.7%. Nearly ten times smaller than the fat baselines and nine points better.

The paper’s own conclusion is modest and I’ll leave it modest: grid search is brute force and too slow; random search is faster but guarantees nothing and doesn’t scale into large spaces; when the space is genuinely large, the evolutionary algorithm’s population and generation parameters are what give you a handle on the cost, even though it too takes a long time to run.

Worth saying plainly: at these budgets the genetic algorithm did not beat random search. It matched it and took 50% longer. The argument for it is extrapolative — it’s about what happens when the space grows past the point where five random draws mean anything — and the experiment doesn’t prove that part. It’s a reasonable inference, not a finding.

The other honest caveats

The tables carry a “Score” column that combines accuracy with model size, and the paper never defines the formula. That’s a straightforward flaw; you can read the accuracies and the parameter counts, but you can’t reconstruct the ranking. The genetic algorithm section likewise gives population, generations and encoding but not the crossover, mutation or selection scheme, which means that run isn’t reproducible from the text.

The sample sizes are small — five random runs, a population of two — and several accuracy figures have error bars of a few tenths of a point around differences of a few tenths of a point. Treat “86% versus 83%” as real and anything finer as noise.

What I’d do differently in 2026

The field moved a very long way, and quickly, in the direction of not paying full training cost per candidate:

• Weight sharing and one-shot NAS. Train a single over-parameterised supernet once and evaluate sub-architectures as paths through it. The per-candidate cost collapses from hours to something near free. ENAS made this the default framing, and it postdates the mental model our paper works in.
• Differentiable search. DARTS relaxes the discrete choice of operation into a continuous mixture and optimises the architecture by gradient descent alongside the weights, turning search into training.
• Zero-cost proxies. Score an untrained network from a single minibatch. Crude, but at the point where an evaluation is nearly free, “crude” changes what search strategies are affordable.
• Benchmarks with tabulated results. NAS-Bench-101 and its successors precompute the accuracy of every architecture in a defined space, so you can compare search strategies without spending GPU time. Our comparison would have been a much better comparison run against one of those — it would have afforded hundreds of trials instead of eighteen.

So: a 2019 snapshot, on one dataset, one GPU, one small macro search space. It is not advice about how to do NAS today.

Why it got cited

I don’t think it got cited because it was good. I think it got cited because of when it landed and what it is for.

The timing was most of it. NAS in late 2019 was a field just starting its steep part of the curve — the foundational work was two or three years old, the wave of papers that followed hadn’t arrived yet, and there was very little written that simply compared the classical search strategies head to head with times attached. We were early, and being early into a field that then grew for years means every one of those subsequent papers had a related-work section to fill and a short list of things to cite for “the obvious baselines were tried”.

If you’re writing the related-work section of a NAS paper, you need one sentence establishing that the classical search methods were tried and what they cost. If you’re teaching, you need a worked example where the three algorithms are legible and the comparison is on a single table. If you’re an engineer deciding whether to bother, you want a number for how long each takes. A paper that is a clean baseline comparison gets reached for constantly. A paper that is 0.3% better than the previous state of the art gets superseded in eight months and cited by the paper that supersedes it.

The narrowness helps too. The abstract promises a comparison of three algorithms on CIFAR-10 by time and accuracy, and that is exactly what’s inside. Nobody has ever been disappointed by it, because it never claimed to be more.

That’s the lesson I actually took from this, and it transfers well outside academia: the artefact people reuse is usually the legible one, not the impressive one. Write down the boring comparison nobody bothered to run. Put the times in.

The paper is on arXiv; the rest of my work is on the research page.