Counting Correct Answers: Noise-Aware Surrogates for Cheap Architecture Search

Neural architecture search (automatically choosing a network's wiring) is expensive mainly because each candidate must be trained and scored. Most cost-saving tricks make each score cheaper and noisier: fewer epochs, one random seed instead of several, or a smaller validation set. The model that guides the search, a "surrogate" that predicts a candidate's accuracy from its structure, then has to separate a good architecture from a lucky measurement. Current surrogates treat accuracy as an unbounded number with Gaussian noise of fixed size. Accuracy has a different structure. It is the fraction of $m$ validation images classified correctly, so part of its noise is plain counting noise whose size is known in advance from $m$ and the accuracy level. The rest comes from training randomness and varies across architectures.

We propose a surrogate that models measured accuracy as a beta-binomial count. The number of correct images is binomial given the architecture's "true" accuracy for that training run. That true accuracy varies across seeds according to a Beta distribution (a distribution on the interval $(0,1)$) whose mean and spread a neural network predicts from the architecture. A separate point mass covers architectures that collapse to chance level. Because the known counting noise is factored out, the search can make a principled choice between paying for another seed or a larger validation set on a promising candidate and exploring a new one. The central claim is that this gives better-calibrated uncertainty under cheap evaluations, and so reaches a target accuracy with fewer GPU-hours than surrogates with Gaussian noise.

Core Claim and Model

For architecture $G$ evaluated on $m$ validation images with $k$ correct, the likelihood is

$$ p(k \mid G, m) = \pi(G)\,\mathbb{1}[k/m \approx a_0] + (1-\pi(G)) \int_0^1 \binom{m}{k} p^{k}(1-p)^{m-k}\, \mathrm{Beta}\big(p;\ \mu(G)\phi(G),\ (1-\mu(G))\phi(G)\big)\, dp . $$

Here $\pi(G)$ is the predicted probability of collapse, $a_0$ is chance accuracy (for example 0.1 on CIFAR-10), $\mu(G)$ is the mean accuracy across training seeds, and $\phi(G)$ is a precision that measures how reproducible the architecture is across seeds. The integral has a closed form, so training only needs log-Gamma functions. The variance of $k/m$ is roughly $\mu(1-\mu)\,[1/m + 1/(\phi+1)]$. The first term is counting noise, known from $m$. The second is seed noise, which the model learns. This split is what Gaussian surrogates cannot express. Shrinking $m$ or using a single seed changes the noise in a predictable way, and the surrogate tells the search how much a cheap measurement is worth.

The model reuses existing techniques. It takes the neural Beta heads of BERT-Beta, which predict two Beta shape parameters for toxicity scores. It takes the two-stage boundary mixture of the zero-inflated Beta model for speech recognition quality, which also supplies a fix for unstable digamma gradients. It borrows from Learned Beta Distributions the idea of reading a separate confidence parameter off the representation. We move the inflation point from 0 to chance level, because collapsed networks in tabular benchmarks score at chance rather than at zero. That is our reading of how such benchmarks behave; the file reports no count of collapsed architectures. The architecture encoder is the path encoding of BANANAS, so differences in search come from the likelihood and not from the input representation.

Relation to Prior Work

Two kinds of prior work motivate the gap. BANANAS and the surrogates in NAS-Bench-301 and NAS-Bench-Suite predict accuracy with mean-squared or absolute-error regressors. They take uncertainty from the spread of an ensemble, which mixes model uncertainty with measurement noise. NAS-Bench-301 also notes that a surrogate can beat single tabular measurements by smoothing training noise. That finding says noise matters, but no prior surrogate models the noise explicitly.

Other papers look similar by name but differ in substance. β-DARTS regularizes softmax operation weights, and its "beta" is notation, not a distribution. Beta product kernels place Beta densities on bounded inputs but keep a Gaussian likelihood on the output. We do the reverse: a bounded likelihood on the output and a standard encoder on the input.

Cost-reduction methods sit beside this work. Budgeted Performance Estimation tunes epochs and batch sizes for cheap scoring, and GenNAS replaces label training with synthetic regression. Both are compatible with our surrogate, since they produce noisier measurements that it could consume.

One paper constrains the design. Can Training Logs Make Model Comparisons More Precise? finds that fitting extra adjustment parameters with ten or fewer runs widens confidence intervals rather than narrowing them. Our precision $\phi(G)$ could suffer the same overfitting if it is fit per architecture. We therefore share it across architectures through the network and test whether it actually predicts held-out seed variance.

Research Program

We will build the beta-binomial surrogate with collapse mass and plug it into Thompson sampling, the acquisition rule used in BANANAS. On top of this we add a simple cost-aware rule. Each step chooses among three actions: evaluate a new architecture at low fidelity (one seed, subsampled validation set), add a seed to an already-evaluated candidate, or enlarge a candidate's validation sample. The choice maximizes expected improvement per GPU-second, computed from the surrogate's split of the noise.

Analysis comes before search. Using the three seeds per architecture in NAS-Bench-101, we will check two things. First, whether the predicted seed variance $\mu(1-\mu)/(\phi+1)$ matches the observed variance across seeds on held-out architectures. Second, whether seed variance really shrinks near the top of the accuracy range as the Beta form implies. If seed variance is roughly constant in the 90–94% band, the bounded geometry contributes little, and the value of the model rests on the counting-noise split and the collapse mass alone. We will report that outcome directly.

Baselines

The naive reference point is random search at the same simulated GPU budget, alongside regularized evolution. NAS-Bench-Suite reports regularized evolution as the best black-box optimizer overall, with an average rank of 2.36 across its 25 settings. On NAS-Bench-101, the authors report that regularized evolution, BOHB and SMAC reach random search's final performance about 5× faster.

The strongest guided-search competitor is BANANAS with its MLP ensemble on path encodings. It reports 2.64% average test error on CIFAR-10 in the DARTS space. I found no reported result on Lacuna for BANANAS regret on NAS-Bench-201 at a matched low-fidelity budget, so we will rerun it.

The strongest standalone predictor is tuned XGBoost, which has an average predictor rank of 1.23 in NAS-Bench-Suite. We will give it bootstrap ensembles so that it can drive Thompson sampling.

All methods will share the same encodings, the same budget of simulated evaluations measured in GPU-seconds from benchmark training times, and the same 50-trial hyperparameter search for each surrogate. Each method will be run over 25 search seeds. Beating a baseline means lower mean regret at matched cost with non-overlapping 95% bootstrap intervals, together with better negative log-likelihood and coverage of held-out single-seed measurements.

Two ablations isolate the key ingredient. The first is a logit-Gaussian heteroscedastic ensemble with a collapse classifier, which keeps everything except the beta-binomial count structure. The second is a plain Beta likelihood on $k/m$ that ignores $m$. This separates the value of boundedness from the value of known counting noise.

Why not just…?

Why not just logit-transform accuracy and fit a heteroscedastic Gaussian? This is the most serious alternative. Adding a delta-method term for binomial variance could recover much of what the beta-binomial does. Beta calibration shows that logistic families distort mid-range values when they cannot represent the identity, which argues against the logit route. That argument concerns calibration maps, though, not surrogates, so it does not settle the question here. The logit-Gaussian ablation will. If it matches us when given the same known-$m$ variance term, the contribution reduces to modeling the counting noise explicitly, whatever the distribution family, and we will present it that way.

Why not just use tuned XGBoost, the best predictor in NAS-Bench-Suite? XGBoost wins on ranking accuracy, but its bootstrap spread does not separate seed noise from counting noise, so it cannot price the choice between adding a seed and exploring. If bootstrapped XGBoost matches our search regret, explicit noise modeling is unnecessary for search, even if it still helps calibration.

Why not just average more seeds, or rank with a zero-cost proxy? Averaging seeds removes noise by paying for it, which is the cost we are trying to cut. A cost-matched baseline that always spends three seeds will test whether adaptive allocation beats uniform allocation. Ranking proxies such as GenNAS (Spearman 0.85 on NAS-Bench-101) avoid training altogether. We treat them as a source of prior means, not as competitors to uncertainty modeling.

Proposed Experiments

Experiments run on NAS-Bench-101, which has real multi-seed noise and 4/12/36/108-epoch fidelities. They also run on NAS-Bench-201, using the CIFAR-10, CIFAR-100 and ImageNet-16-120 tasks, whose best reported accuracies are 94.37%, 73.51% and 47.31%. That benchmark's collapsed architectures test the chance-level mass.

Smaller validation sets are simulated by drawing binomial counts from the benchmark accuracies. This approximation ignores correlation over which images are hard. To check it, we will train a few hundred NAS-Bench-201 architectures ourselves, score them on real subsampled validation sets, and compare against the simulation.

The decisive checks are three. First, on held-out NAS-Bench-101 architectures, the surrogate's 90% predictive intervals for a single new seed should achieve close to nominal coverage, where ensemble baselines under-cover. Second, at budgets equal to a few hundred full trainings, regret against GPU-hours should improve over BANANAS and bootstrapped XGBoost, with the gain largest on ImageNet-16-120, where both accuracy and noise are mid-range. Third, the logit-Gaussian ablation will show whether the beta-binomial form, not just the noise split, is responsible for any gain.