Prior-Corrected Zero-Cost Proxies for Architecture Search

Zero-cost proxies score a candidate neural network from a single minibatch at random initialization, with no training. They let architecture search run in seconds instead of GPU-months. Yet every proxy quietly treats the random initialization as a neutral starting point. Work in Bayesian deep learning shows it is not. The default Gaussian weight distribution, read as a prior over the functions a network computes, makes deep networks either collapse toward near-constant outputs or produce wildly heavy-tailed ones. How strongly this happens depends on depth, width and topology.

We propose that a large, measurable share of zero-cost proxy error comes from this mismatch. Two candidate architectures receive different scores partly because the default initialization hands them different random-function behavior, not only because they differ in how well they will train. We will measure each candidate's prior behavior cheaply. We will then rescale its initialization so that every candidate starts from comparable random-function statistics, and only then compute the standard proxies. If this works, it removes a source of ranking noise at essentially zero added cost. If it fails, it rules out a popular explanation for why proxies break.

Core Claim

The "prior predictive distribution" is the distribution of outputs a network produces when its weights are drawn at random, before any data is seen. Noci derived it exactly for fully connected ReLU networks. Width pushes outputs toward a Gaussian, while depth inflates the output kurtosis (a measure of how heavy the tails are) exponentially:

$$\kappa(m, L) = 3\left(\frac{m+5}{m}\right)^{L-1},$$

where $m$ is the layer width and $L$ the depth. Tran et al. showed empirically that as depth grows from 2 to 8 layers, Gaussian-prior networks degenerate into flat functions that map different inputs to nearly the same output. Fortuin explained why the isotropic Gaussian acts as a rigid, misspecified constraint rather than an uninformative default. These papers motivate the proposal. They establish that the random-function behavior at initialization is structured, architecture-dependent and often pathological.

On the architecture-search side, proxies such as NASWOT (Mellor et al.), synflow, snip and jacob_cov (Abdelfattah et al.) all read properties of exactly this random state. Their known failures fit a prior artifact. Proxies largely track parameter count (Krishnakumar et al.). Jacob_cov breaks across heterogeneous topologies (Abdelfattah et al.). Static neural-tangent-kernel proxies even correlate negatively with final accuracy on NAS-Bench-101 at initialization (Demystifying the Neural Tangent Kernel...).

That last paper attributes the failure to the absence of label information. It fixes the problem with one to five warm-up epochs, during which the kernel "twists" toward the labels. Our claim competes directly with this explanation. We claim that part of the warm-up's benefit comes from the network escaping a misspecified initial function distribution. Correcting that distribution at $t=0$ should therefore recover part of the warm-up's rank correlation at no training cost.

The key design decision concerns what to correct. NAS-Bench-style cells already contain batch normalization, which fixes per-unit variance at initialization. Simple variance rescaling is therefore largely redundant. Our correction targets the two statistics batch normalization does not control. The first is output kurtosis. The second is the cross-input output correlation, meaning the average correlation between the network's outputs on different images. Values near one indicate functional collapse.

Research Program

The first component is a cheap prior probe. For each candidate we draw $K$ (about 8) independent initializations and push one minibatch through each. From the logits we estimate output kurtosis and the mean cross-input correlation $\bar\rho$. This costs $K$ forward passes and no backward passes. It stays within the seconds-per-architecture regime that makes zero-cost search worthwhile, which is the computational constraint the second direction imposes.

We deliberately use moments rather than the Wasserstein matching of Tran et al. or the context-point norm penalties of Cinquin et al.. Both papers report that their objectives are expensive. Cinquin et al. also report high sensitivity to context-point and kernel choices. Those findings constrain us away from a full Gaussian-process target.

The second component is an audit. Over all of NAS-Bench-201 and a large sample of NAS-Bench-101, we measure how much of each proxy's score is predicted by parameter count, by depth, and by the prior statistics. We then compute the proxy's partial rank correlation with final test accuracy after controlling for each set. This tests the mechanism directly. If the prior statistics explain proxy variance that parameter count does not, the prior is a distinct confound.

The third component is the intervention. For each candidate we tune a small number of scalars by forward-pass-only bisection. These are a per-cell scale on the residual and skip branches and a per-stage weight-variance multiplier, in the spirit of the Generalized He-Priors of Noci. Noci's analysis does not cover skips, pooling or normalization, so we replace his closed form with empirical matching. The tuning drives $\bar\rho$ and kurtosis to shared targets across all candidates. We then compute the unchanged proxies on the corrected initialization. The targets themselves are hyperparameters. To prevent tuning on the evaluation benchmark, we choose them once on NAS-Bench-201 CIFAR-10 and freeze them for every other dataset and search space.

Baselines

The naive reference points are random search and parameter count alone. Random search is strong on tabular spaces where most models are already good (Dong & Yang). Parameter count alone is the confound Krishnakumar et al. identified. No reported Spearman correlation for parameter count alone on NAS-Bench-201 was found on Lacuna, so we compute it ourselves.

The strongest zero-cost competitor is the synflow, jacob_cov and snip voting ensemble of Abdelfattah et al.. It reports Spearman ρ = 0.82 with final accuracy on NAS-Bench-201, against EcoNAS at 0.61. It is the strongest because it already pools complementary signals at the same near-zero cost. We rerun it with identical minibatches, seeds and hardware. Beating it means our corrected ensemble exceeds its ρ on all three NAS-Bench-201 datasets by more than the seed-to-seed spread. If the corrected ensemble only matches the original, the correction adds nothing beyond ensembling.

For search outcome, NASWOT reports 92.81% CIFAR-10 accuracy in 30 seconds on NAS-Bench-201 (Mellor et al.). We compare against it under equal wall-clock budgets.

The strongest low-cost competitor is Label-Gradient Alignment after one epoch (Demystifying the Neural Tangent Kernel...). It reports ρ = 0.308 on NAS-Bench-101 and 94.30% search accuracy on CIFAR-10. We run it with its published warm-up settings and report our method's rank correlation as a fraction of LGA's. A training-free method reaching a substantial fraction of 0.308, where static kernel proxies are negative, would count as a win in cost-adjusted terms.

Two ablations isolate the key ingredient. The first, variance-only correction, scales initialization to fix output variance alone. The second, seed-averaging, averages each uncorrected proxy over the same $K$ initializations without any correction. Seed-averaging gives the same compute budget and separates the benefit of matching the prior from the benefit of simply sampling it more.

Why not just…?

Why not just regress parameter count out of the proxies? This is the most serious threat, because depth, width and parameter count are entangled with kurtosis and collapse. The audit settles it directly. We report proxy rank correlation after partialling out parameter count and FLOPs as Krishnakumar et al. suggest, and again after additionally partialling out the prior statistics. If the prior statistics add no explanatory power once size is controlled, we will report that the prior story reduces to size bias. That negative result is still informative, and we will not claim the intervention.

Why not just use one epoch of warm-up? LGA works, but it trains every candidate. That cost is substantial across tens of thousands of candidates, and real wall-clock savings are smaller than FLOP counts suggest (Abdelfattah et al.). The LGA authors also note sensitivity to warm-up hyperparameters. Our experiment tests whether warm-up is actually necessary, and if both help, combining them is a natural follow-up.

Why not just average proxies over more random seeds? If proxy failures are mere sampling noise, averaging would fix them as well as correction does. The seed-averaging ablation uses exactly the same forward passes. The correction must beat it to claim that the prior's systematic structure, not its variance, is the problem.

Why not use the Bayesian NAS methods that already exist? BayesNAS (Zhou et al.) puts priors on the routing variables of a trained supernet. GP-NAS (Li et al.) puts a Gaussian process over scalar accuracy as a function of architecture. Both require training, and neither examines the functions the candidate networks compute. They answer a different question. We cite their CIFAR-10 results (2.81% and 3.79% error) only as context and do not compare against them head to head.

Proposed Experiments

On NAS-Bench-201 (CIFAR-10, CIFAR-100, ImageNet-16-120, all 15,625 architectures) and NAS-Bench-101 (Ying et al.), we report several measures for each proxy before and after correction. These are Spearman ρ with final test accuracy, Kendall τ within the top 10% of architectures, and partial correlations after controlling for size. We also report search results under a fixed wall-clock budget, using both pure proxy ranking and proxy-assisted regularized evolution, measured as test accuracy relative to the optima of 94.37%, 73.51% and 47.31% on the three NAS-Bench-201 datasets and 94.32% on NAS-Bench-101.

The first decisive check targets static neural-tangent-kernel proxies (trace, Frobenius norm, condition number) on NAS-Bench-101. Their rank correlation is negative at $t=0$ under default initialization. If prior correction lifts it to a clearly positive value with zero training, the label-absence explanation of Demystifying the Neural Tangent Kernel... is at least incomplete. If correlations stay negative, labels really are required, and the prior hypothesis is falsified for that proxy family.

The second check stratifies NAS-Bench-101 by cell depth. If gains concentrate in the deepest cells, where Noci's analysis predicts the worst tails, the mechanism is supported. If gains are uniform or absent, it is not.

A secondary probe asks whether the probe statistic $\bar\rho$ at initialization predicts calibration after training. We will measure this on a few hundred NAS-Bench-201 architectures retrained with expected-calibration-error logging. This would be a first step toward searching for architectures with well-behaved uncertainty, not only accuracy.