Lipschitz Architecture Embeddings Shaped by Zero-Cost Proxies

Searching for a good neural network architecture is expensive mainly because each candidate must be trained to learn how good it is. One way to cut that cost is to compress every candidate network into a short vector, an embedding, and run Bayesian optimization in that vector space. Bayesian optimization is a method that fits a cheap statistical model of "architecture → accuracy" and uses it to choose which few candidates to actually train. This only works if nearby vectors correspond to networks of similar quality. Existing architecture autoencoders such as D-VAE never ask for that property. Work on molecules shows that without it, very different inputs end up at nearly the same point, and the statistical model sees this as noise (CoBO; LOCO).

The fix those papers use is a Lipschitz penalty, a training term that limits how fast the objective may change as one moves through the embedding. Applied naively to architecture search, it needs the very labels that are expensive: trained accuracies. We propose shaping the architecture embedding's geometry with signals that cost almost nothing. These are zero-cost proxies, scores computed from an untrained network in one or two forward and backward passes. They are cheap enough to compute for hundreds of thousands of unlabeled architectures. The scarce trained accuracies are kept for the Bayesian optimization model alone. In short, we spend free compute to build a smooth search space, so that expensive training runs are wasted less often.

Core Claim

A graph autoencoder over architecture DAGs (directed acyclic graphs, here the cell wiring diagrams of networks) can be trained with a Lipschitz, collision-free penalty that refers to the vector of zero-cost proxy scores rather than to accuracy. We claim that Bayesian optimization in that space reaches a given simple regret with fewer trained architectures than three alternatives: optimization in an unregularized D-VAE space, CoBO-style regularization using only the few accuracy labels available, and surrogates that consume the proxies directly as features. Simple regret is the gap between the best architecture found and the best one in the search space.

This differs from CoBO and LOCO in two ways. Those methods regularize against the true objective, and they were tested only on molecules, grammars and synthetic vectors, never on computational graphs. It also differs from NAS-Bench-Suite-Zero and OMNI from White et al., which feed proxies as input columns to a regressor rather than using them to shape a representation that a probabilistic surrogate then searches.

The penalty, for a minibatch of architectures with embeddings $z_i$ and standardized proxy vectors $p_i$ (the 13 proxies of NAS-Bench-Suite-Zero), is

$$\mathcal{L} = \mathcal{L}_{\text{ELBO}} + \lambda \sum_{i,j} w_{ij}\,\max\!\big(0,\ \|p_i - p_j\| - L\,\|z_i - z_j\|\big),$$

where $\mathcal{L}_{\text{ELBO}}$ is D-VAE's usual reconstruction-plus-KL loss and $L$ is a target Lipschitz constant. The weight $w_{ij}$ upweights pairs whose proxy scores are high, borrowing DW LOCO's idea of prioritizing the promising region, and $\lambda$ trades this term against reconstruction. The hinge forbids collisions: two architectures with different proxy profiles cannot sit close together. Reconstruction and the KL term keep the space from simply stretching apart. The pairwise term costs $O(B^2)$ in batch size $B$, which the file flags as a known overhead. At $B\approx 256$ on graph inputs this overhead is small next to proxy computation, and we will report it.

Research Program

The method itself is mechanical. We reuse D-VAE's asynchronous message-passing encoder, which D-VAE proves maps isomorphic DAGs to the same code, and add the penalty above. Pretraining uses the entire unlabeled architecture pool with precomputed proxies. Search then runs a Gaussian-process surrogate in the frozen embedding with expected-improvement acquisition, decoding chosen points back to graphs. Because the encoder is frozen, we avoid the coordinate drift that forced CoBO to re-center its trust region. A secondary variant allows light fine-tuning on accumulated accuracy labels, to test whether the drift problem returns.

The scientific question is which geometry the proxies impose, and whether it transfers. We expect three findings. First, the Pearson correlation between latent distance and accuracy difference should rise in the proxy-shaped space even though accuracy was never used. CoBO's analogous measurement on molecules went from about 0.2 to about 0.7 when it regularized against the true objective. Second, single proxies are space-specific: Evaluating Efficient Performance Estimators finds relu_logdet best on topological spaces and synflow on non-topological ones. Shaping against the full vector should therefore matter more than shaping against any one proxy. Third, the real danger is that proxies largely track parameter count, which the same paper and ZiCo document. If so, the proxy-shaped space could just be a size axis. We test this directly with a parameter-count-only shaping ablation and with search restricted to size-matched subsets.

Baselines

The do-nothing reference is random search, plus ranking by parameter count. ZiCo reports Kendall's τ of 0.57 for #Params on NATS-Bench-TSS, against 0.61 for ZiCo and 0.54 for Synflow. A shaped embedding whose surrogate ranks no better than 0.57 has learned nothing beyond size.

Regularized evolution (REA) is the strongest discrete competitor. NAS-Bench-201 and NATS-Bench report it as a very robust baseline that beats more complex methods. We run it with the same budget of trained architectures, its population and mutation settings tuned on a held-out seed set using the same tuning budget we give our own hyperparameters ($\lambda$, $L$). No reported regret curve for REA on these benchmarks is in the file, so we will produce it ourselves.

The strongest representation-learning competitor is Bayesian optimization in an unregularized D-VAE embedding. D-VAE reports 94.80% CIFAR-10 accuracy for its best found architecture on the ENAS space, versus 92.79% for S-VAE, but no reported regret on NAS-Bench-201/101/301 was found on Lacuna. We retrain it on the identical pool.

The strongest predictor competitor uses the proxies directly. One variant is XGBoost on the 13-proxy vector, the setup NAS-Bench-Suite-Zero reports improves Spearman correlation by up to 42%, used inside the same acquisition loop. The other is a Gaussian process on the concatenation of the D-VAE embedding and the proxy vector.

For ranking quality alone, CTNAS's comparator reports Kendall's τ of 0.751 on NAS-Bench-101 (CTNAS), and we use it as the ranking bar.

Two ablations isolate the key ingredient, which is that the shaping signal is cheap and abundant. The first applies CoBO's penalty against accuracy using only the labels collected during search. The second applies the hinge against parameter count alone.

Beating the field means a lower median simple regret at fixed trained-architecture budgets, over at least 20 seeds and with nonoverlapping bootstrap intervals, against both REA and the proxy-feature surrogates. It also means matching or exceeding a Kendall τ of 0.751 on NAS-Bench-101 given an equal number of labels.

Why not just…?

Why not just feed the zero-cost proxies to XGBoost or a Gaussian process as features? This is the real threat. If the proxies carry the signal, a surrogate on the raw proxy vector may already exploit it, and NAS-Bench-Suite-Zero's 42% gain suggests it does for ranking. Our argument is that a tabular regressor cannot propose new candidates; it can only score ones you enumerate. A decodable embedding lets acquisition move continuously, which matters in NAS-Bench-301's $10^{18}$ space where enumeration fails. We are not assuming the argument wins. If the concatenated D-VAE-plus-proxy Gaussian process matches our regret on NAS-Bench-301, the geometry contributes nothing and the claim fails.

Why not just run regularized evolution? On NAS-Bench-201's 15,625 cells, evolution may well be as good, since the space is small enough to mutate through quickly. We expect any advantage to appear on NAS-Bench-101 (423k cells) and NAS-Bench-301, and we report results per space rather than averaging the small space away.

Why not just shape the embedding with accuracy labels, as CoBO does? In architecture search those labels are the cost being minimized. A few dozen of them are too sparse to regularize an embedding over hundreds of thousands of graphs. The label-only ablation tests exactly this at budgets of 25 to 200 labels. If it matches the proxy-shaped version, proxies are unnecessary.

Why not just add a regression head to D-VAE? LOCO reports that encoders trained under plain mean-squared-error regression produce the collisions the hinge is designed to prevent. We include a proxy-regression-head variant to check whether that finding holds on graphs.

Proposed Experiments

Experiments run on NAS-Bench-201 across CIFAR-10, CIFAR-100 and ImageNet-16-120, with optima of 94.37%, 73.51% and 47.31%. They also run on NAS-Bench-101 and on NAS-Bench-301, using the proxies precomputed in NAS-Bench-Suite-Zero (an 11,000-model subset for 301, which we extend). We also use the NATS-Bench size space as a non-topological check.

The primary metric is simple regret against the number of trained architectures. Secondary metrics are Kendall τ of the surrogate posterior mean, the latent-distance versus accuracy-difference Pearson correlation, and total GPU-hours including proxy computation and autoencoder pretraining. The last ensures the "free" signal is really free.

Three checks decide the question. First, the proxy-shaped space must beat the unregularized D-VAE in regret on at least two of the three benchmark families. Second, it must beat the proxy-feature surrogates on NAS-Bench-301. Third, it must keep its advantage within size-matched architecture subsets, where parameter count is uninformative by construction. Failing the third check would mean we had built an elaborate parameter counter, and we would report it as such.