Searching for a good neural network design is expensive because the only reliable way to score a candidate is to train it. Cheap substitutes exist. "Zero-cost proxies" score an untrained network from one forward and backward pass. They separate bad designs from average ones well, but they become unreliable exactly where it matters: among the best 10% of candidates. This note proposes a specific explanation for that failure and tests it. The top tier is structurally diverse. A proxy may order candidates correctly within a family of similar designs yet mis-order designs from different families. If that holds, the right way to spend a small training budget is to use proxies only for local comparisons and reserve real training for moving between families.
The open question is what "local" should mean. We propose defining it with tools from manifold-constrained interpolation, the study of how to move between points in a generative model's latent space along curved, high-density paths rather than straight lines. Concretely, we train a graph autoencoder on architectures only, never on their accuracies. We then measure distance between architectures as the length of the shortest path through densely populated latent regions under the metric the decoder induces. We then test whether proxy rankings are more trustworthy inside these geodesic neighborhoods than inside neighborhoods defined by plain edit distance or flat latent distance. On tabular benchmarks this question can be answered without training a single network. If the answer is yes, a search procedure follows directly.
Core Claim
The claim is empirical and falsifiable. Among top-decile architectures on NAS-Bench-201, a zero-cost proxy's rank correlation with true accuracy is higher when computed within small neighborhoods defined by density-weighted latent geodesics than within neighborhoods of the same size defined by graph edit distance or Euclidean latent distance. A search that restricts proxy comparisons to such neighborhoods and spends full training only on proxy tournament winners reaches lower regret per fully-trained candidate than evolution, flat-latent Bayesian optimization, or proxy-filtered edit-distance mutation. The geometry is not used to avoid "invalid" decodings, a weak motivation on NAS-Bench-201 where every cell is valid. It is used to decide which cheap comparisons to believe.
What Exists and How This Differs
Two continuous-latent search methods are closest. Neural Architecture Optimization encodes architecture strings with an LSTM, trains an accuracy predictor on the latent vector, and takes straight gradient steps in latent space before decoding. D-VAE encodes architectures as directed acyclic graphs with message passing that follows the order of computation, and runs Bayesian optimization in the latent space. Both treat the latent space as flat. Both also use latent geometry to generate candidates that are then trained. We instead use it to gate which cheap proxy comparisons are trusted, and we never train the encoder on accuracy labels, so building the geometry costs no training evaluations.
The geometric machinery is reused, not invented. Latent Space Oddity defines the pullback metric, which measures how much a small latent move changes the decoder's output. It also gives a stochastic-decoder version, which we apply to the decoder's categorical distributions over operations. A Geometric Perspective on Variational Autoencoders shows that encoder variance marks off-manifold regions. Weighted Geodesic Distance Following Fermat's Principle sums edge lengths raised to a power $d>1$ so that paths avoid sparse gaps; it reports a useful range of roughly 1.7 to 3.2. Fast Approximate Geodesics for Deep Generative Models replaces continuous geodesic solvers with A* search on a nearest-neighbor graph, reporting about 0.09 seconds against 200–400 seconds in 20 dimensions.
That speedup matters because A prior-based approximate latent Riemannian metric reports that exact pullback geodesics often fail to converge above five latent dimensions, and architecture latents are larger. This constrains our design toward graph-based and conformal approximations rather than continuous ODE solvers. None of these papers touches architecture spaces.
On the cost side, EZNAS evolves proxy formulas and explicitly reports the top-10% failure that motivates us. Rethinking Performance Estimation in Neural Architecture Search cuts per-candidate cost by choosing short training budgets. That second approach is orthogonal to ours: it reduces the price of each evaluation, while we reduce how many evaluations are needed.
Research Program
We train a D-VAE-style encoder and decoder on every architecture in NAS-Bench-201, which has 15,625 cells, and on a large sample of NAS-Bench-101. We use reconstruction loss only. Encoding all architectures, we build a $k$-nearest-neighbor graph in latent space.
Each edge between latent points $z_i$ and $z_j$ gets weight $w_{ij} = \ell_{ij}^{\,d}$. Here $\ell_{ij}$ is the Riemannian length of the segment, computed from $J(z)^\top F(z) J(z)$, where $J$ is the decoder Jacobian and $F$ is the Fisher information of its categorical outputs. The length is evaluated at a few points along the segment, and $d$ is the Fermat exponent. We also test a cheaper conformal variant, in which $\ell_{ij}$ is Euclidean length scaled by inverse latent density, following the prior-based metric. The geodesic distance between two architectures is the shortest-path length on this graph, found with A*. A geodesic neighborhood of an architecture is its $m$ nearest architectures under this distance.
The analysis phase uses only tabular lookups and proxy computations. For every top-decile architecture, we compute Kendall τ between proxy score and true accuracy within its neighborhood. We do this for three metrics (geodesic, Euclidean latent, edit distance) and three proxies (NASWOT, Synflow, and EZNAS-A if its expression can be reproduced), matching neighborhood size $m$ across metrics.
The search phase, which we call geodesic proxy tournaments, keeps a small set of fully-trained architectures. From the current best, it scores its geodesic neighborhood with the proxy, "trains" the proxy winner by table lookup, and moves if the winner is better. When the local tournament stalls, it traces the A* path between the two best trained architectures from different latent clusters, proxy-scores the intermediate architectures, and trains the best one. The cost is counted as the number of full training lookups, converted to GPU-hours with the benchmark's recorded training times, plus proxy compute. As a secondary check tied to the known collapse of differentiable search toward all-skip cells on NAS-Bench-201, we report how often each method selects parameter-free-dominated cells.
Baselines
The naive reference points are random search and pure proxy selection. Random search spends the same number of full evaluations uniformly. Pure proxy selection trains only the architecture ranked highest by the proxy across the whole space. Pure proxy is the "do nothing beyond the proxy" point. EZNAS reports its evolved proxy reaching Kendall τ 0.65 on NAS-Bench-201 CIFAR-10, against 0.57 for NASWOT and Synflow (EZNAS). Our analysis must beat these global correlations inside the top decile to matter.
The strongest discrete competitor is Regularized Evolution, which mutates the best architectures and keeps a sliding population. NAS-Bench-101 reports that Regularized Evolution, BOHB, and SMAC reached random search's final performance about 5x faster (NAS-Bench-101). For regret curves of these methods on NAS-Bench-201 under our budget definition, no reported result was found on Lacuna, so we rerun them. Beating Regularized Evolution means lower mean regret against the benchmark optimum at equal full-evaluation budgets of 25, 50, and 100 over at least 50 seeds. The optimum is 94.37% on CIFAR-10, 73.51% on CIFAR-100, and 47.31% on ImageNet-16-120, per NAS-Bench-201.
The strongest latent-space competitor is D-VAE Bayesian optimization with a flat Euclidean kernel, run on our own encoder so that representation quality is identical. D-VAE reports 94.80% on its ENAS-space CIFAR-10 search (D-VAE). That space differs from ours, so the number is context rather than a target. We also run NAO-style predictor gradient ascent on the same encoder, with the predictor trained on the same evaluated points.
The ablation that isolates our key ingredient is proxy tournaments over edit-distance neighborhoods. It uses the identical procedure and the same neighborhood size, and differs only in the metric. We also add a learned weighted edit distance whose operation-substitution costs are fit from proxy disagreements. If geodesic tournaments do not beat both, the latent geometry has contributed nothing.
Every method gets the same full-evaluation budget, the same proxy, and the same hyperparameter tuning budget, with tuning done on NAS-Bench-101 and frozen for NAS-Bench-201.
Why not just…?
Why not just use edit-distance neighbors, since architectures are already discrete graphs? This is the most serious threat. Edit-distance mutation is exactly what evolution uses, and it may already capture structural families. Our argument against it is that edit distance treats every single-operation swap as equal. Swapping a 3x3 convolution for "none" can sever a cell, while swapping average pooling for a skip connection barely changes it. A decoder-induced metric weights these swaps differently without any accuracy labels. This is a hypothesis, not evidence. The matched-neighborhood Kendall τ analysis and the edit-distance tournament ablation settle it directly. If edit distance ties, we will report that latent geometry is unnecessary for proxy gating.
Why not just rank the whole space with the best available proxy? Because the top-tier breakdown is documented by the proxy authors themselves (EZNAS), and global τ of 0.65 leaves the best cells poorly ordered. Pure proxy selection is included as a baseline so that this failure is measured on our budget rather than assumed.
Why not just run Bayesian optimization or gradient ascent in a flat latent space? Flat-kernel Bayesian optimization and NAO-style gradient steps assume Euclidean latent distance tracks similarity. Latent Space Oddity and On Linear Interpolation in the Latent Space of Deep Generative Models show this is systematically wrong in image latents. The second reports a 10.20% expected worst-case gap on MNIST between straight lines and geodesics. Whether the same distortion exists in architecture latents is unknown. Comparing the Euclidean-latent and geodesic neighborhoods on the same encoder isolates the effect.
Why not just cut per-candidate cost with short training budgets instead? Budgeted estimation reports going from 3,150 to 0.33 GPU days at 2.66% CIFAR-10 error (Rethinking Performance Estimation in Neural Architecture Search). Its authors also note weakened discrimination among top models. It reduces the price of each evaluation, not the number of evaluations, so it composes with our method rather than replacing it. We test the composition by using NAS-Bench-101's 12-epoch records as the "full" evaluation for all methods.
Decisive Experiments
The first test is free: the matched-size neighborhood τ analysis on NAS-Bench-201 across CIFAR-10, CIFAR-100, and ImageNet-16-120. It succeeds if the geodesic top-decile τ exceeds edit-distance τ by a margin that holds across seeds of the autoencoder and at least two proxies. We also sweep the Fermat exponent $d$ from 1 to 3 to check that density weighting, not just the pullback metric, drives any gain.
The second test is the search comparison above, reporting regret against full-evaluation count and simulated GPU-hours. The third checks generality. We rerun the τ analysis on the evaluated samples of the five NDS design spaces used by EZNAS, where the encoder sees only sampled architectures and the geometry must extrapolate. We also run search on NAS-Bench-101, where invalid graphs do exist, and report how often each method's decodings are invalid.
The idea fails cleanly if geodesic neighborhoods show no τ advantage over edit distance in the first test. That outcome would still show where proxy failures come from, and it costs no GPU training to learn.
References
- Neural Architecture Optimization
- D-VAE: A Variational Autoencoder for Directed Acyclic Graphs
- Latent Space Oddity: on the Curvature of Deep Generative Models
- A Geometric Perspective on Variational Autoencoders
- Weighted Geodesic Distance Following Fermat's Principle
- Fast Approximate Geodesics for Deep Generative Models
- A prior-based approximate latent Riemannian metric
- EZNAS: Evolving Zero-Cost Proxies For Neural Architecture Scoring
- Rethinking Performance Estimation in Neural Architecture Search
- NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search
- NAS-Bench-101: Towards Reproducible Neural Architecture Search
- On Linear Interpolation in the Latent Space of Deep Generative Models