Anchor Architectures: Training Only the Networks That Define the Map

Architecture search is expensive because the only reliable way to know how good a network is, is to train it. Most of the cost-cutting literature tries to guess accuracy without training, or to train a predictor on a few trained networks. This proposal makes a different bet. Embed every candidate network in a cheap, label-free description space, built from quantities computable in seconds at initialization. Pick a small set of "anchor" networks that cover that space. Train only the anchors. Then spread their measured accuracies to every other candidate using the anchor-graph technique from scalable semi-supervised learning, in which each point is written as a convex mix of its nearest anchors, so that propagation over hundreds of thousands of nodes costs linear time. In this design, the set of networks we train and the skeleton of the graph used to predict everything else are the same object.

The opportunity comes from two observations in the literature. First, trustworthy rankings of architectures come from comparing them, but comparing every pair grows quadratically and produces logically inconsistent cycles. Second, graph-based semi-supervised learning has a well-understood way to scale to hundreds of thousands of points by routing all similarity through a few landmarks. Comparing $n$ candidates against $m$ anchors costs $O(nm)$ instead of $O(n^2)$, and it yields one scalar score per network. That score is transitive by construction.

Core Claim

Our central claim is narrow and testable. At very small training budgets of roughly 10 to 100 fully trained networks, the geometry of the large untrained candidate pool carries ranking information that supervised predictors trained only on the labeled networks cannot use. Anchor-graph propagation is a cheap, closed-form way to use it. This holds provided the description space is chosen so that accuracy varies smoothly within local neighborhoods. A corollary follows: zero-cost proxies, scores computed from one forward and backward pass at initialization, may be poor global rankers across search spaces yet good local similarity measures. If so, using them to define neighborhoods rather than to rank directly should transfer better than using them as scores.

Relation to Prior Work

The method is borrowed from Large Graph Construction for Scalable Semi-Supervised Learning. That paper replaces an $n\times n$ similarity graph with a sparse $n\times m$ matrix $Z$ of convex reconstruction weights to $m$ anchors, called Local Anchor Embedding. Its graph is $W = Z\Lambda^{-1}Z^\top$, where $\Lambda$ is the diagonal matrix of anchor degrees, and this reduces label propagation to an $m\times m$ solve. There, anchors are k-means centers and carry no labels. Our change is that anchors are real networks, and their labels are bought by training them. Anchor selection, which that paper flags as an upfront cost, becomes our experimental-design problem.

The closest NAS work is Semi-Supervised Neural Architecture Search. It established that unlabeled architectures help a predictor, but it exploits them through iterative pseudo-labeling with an autoencoder. That approach can reinforce its own early mistakes, and it does not choose which networks to train based on pool geometry. Our approach replaces self-training with a convex, closed-form propagation, and it ties the choice of trained networks to coverage of the pool.

Two pairwise-ranking predictors motivate the scalar-anchor formulation. BRP-NAS trains a graph network to predict which of two architectures is better and reports transitivity violations in about 2% of comparisons. Arch-Graph builds $n(n-1)$ pairwise relations and resolves cycles through an NP-complete acyclic-subgraph problem. That forces it to prune to 500 candidates first. Both show that relative judgments beat absolute regression, and both pay for it in cost and consistency. Anchor-relative scores keep the relative character, because every candidate is judged through its neighbors among trained anchors, while avoiding both problems.

FR-NAS improves the encoding of each individual architecture graph with forward and reverse graph encoders. That work is complementary: its embeddings could serve as a description space, but it never builds a graph between architectures. PaSca is the inverse of our setting. It searches for scalable graph networks, whereas we use scalable graph learning to make search over any architecture family cheaper.

Two negative results constrain the design. Zero-Cost Proxies for Lightweight NAS reports that proxies like jacob_cov degrade on architectures with differing topologies. NAS-Bench-Suite finds that proxies and methods tuned on one search space often fail on others, and that tuned XGBoost (gradient-boosted decision trees) is the best surrogate overall. Any claim we make must survive that comparison.

Research Program

The pipeline has four stages.

First, a description vector $x_i$ is computed for every candidate. It concatenates standardized zero-cost proxies (grad_norm, SNIP, GRASP, Fisher, Synflow, jacob_cov from Zero-Cost Proxies for Lightweight NAS), log FLOPs and parameter count, and optionally a low-dimensional projection of a structural encoding. We keep the dimension low on purpose, because distance-based neighborhoods degrade in high dimension.

Second, $m$ anchors are chosen by a coverage criterion in this space, such as k-means++ seeding or farthest-point sampling, and snapped to real candidate networks. The anchors are then trained, or looked up in tabular benchmarks.

Third, every candidate receives sparse convex weights $z_i$ over its $s$ nearest anchors via Local Anchor Embedding. Anchor scores $a\in\mathbb{R}^m$ are fit by

$$ \min_{a}\ \sum_{j\in\mathcal{L}} \left(z_j^\top a - y_j\right)^2 \;+\; \gamma\, a^\top \left(Z^\top Z - Z^\top Z\Lambda^{-1}Z^\top Z\right) a , $$

where $\mathcal{L}$ is the set of trained networks, $y_j$ is the measured accuracy of network $j$, and $\gamma$ trades data fit against smoothness on the reduced graph Laplacian from the anchor-graph paper. The predicted score for every candidate is then $Za$. The smoothness term matters because trained accuracies are noisy across seeds, so anchors should not be taken at face value.

Fourth, the search proceeds in rounds, in the spirit of BRP-NAS's iterative selection. New anchors are added where predicted scores are high and the reconstruction residual $\|x_i - \sum_k z_{ik} x_k\|$ is large, that is, in promising regions the current anchors describe poorly. The $m\times m$ solve is then rerun.

A fifth, diagnostic component asks which description space makes accuracy locally smooth. We will measure this post hoc on the tabular benchmarks as the accuracy variance among each network's nearest neighbors, relative to global variance. If no cheap description space yields local smoothness, the approach fails, and we learn this before any search experiment. That makes the diagnostic the project's first gate.

Baselines

The naive reference points are random search and regularized evolution. They pick and train networks with no predictor at all. NAS-Bench-Suite ranks regularized evolution first among black-box optimizers (average rank 2.36) and local search second (2.66), and NAS-Bench-101 notes that most of its space exceeds 90% accuracy, which makes random search hard to beat. Both will run through the same benchmark query interface with an identical cap on trained networks. Beating them means reaching higher best-found test accuracy at every budget from 10 to 150 trained networks, averaged over at least 20 seeds.

Pure zero-cost ranking is a second training-free reference. It uses the voting ensemble of Synflow, jacob_cov and SNIP, which Zero-Cost Proxies for Lightweight NAS reports at Spearman 0.82 on NAS-Bench-201 versus 0.61 for reduced training. Our method uses the same proxies as inputs, so it must beat this ranking correlation with a small number of trained anchors. More importantly, it must not collapse on the spaces where proxies are known to fail.

The strongest competitor is tuned XGBoost, the top surrogate in NAS-Bench-Suite with average rank 1.23 across 25 settings. That figure is a relative rank, and no absolute correlation value for XGBoost at small training sizes was found on Lacuna. We will run XGBoost on exactly the same description vectors, trained on exactly the same anchor networks, with the same hyperparameter search budget as our $\gamma$, $s$ and $m$ choices. This isolates whether the gain comes from propagation through unlabeled geometry or merely from good features and good anchor choice.

The strongest published sample-efficiency results are as follows. BRP-NAS finds the top NAS-Bench-101 model after 140 trained networks, against 150 for NPENAS and 1,000 for NAO and BONAS (BRP-NAS). Arch-Graph reaches average rank 5.24 on the TransNAS-Bench-101 macro space, and finds architectures within the top 0.29% of the micro space, with 50 sampled models (Arch-Graph). SemiNAS reaches 94.02% on NAS-Bench-101 against a 94.32% optimum (Semi-Supervised Neural Architecture Search). We will reproduce BRP-NAS and SemiNAS where code permits, and otherwise compare against the reported numbers under the same budgets. Beating them means finding the NAS-Bench-101 optimum with fewer than 140 trained networks, and matching or beating Arch-Graph's rank at 50 networks.

Two ablations isolate the key ingredient. The first replaces coverage-based anchors with random anchors, which tests whether choosing what to train matters. The second sets $\gamma=0$ and uses plain nearest-anchor interpolation, which tests whether graph smoothing matters. A third variant feeds the anchor-graph spectral coordinates to XGBoost as extra features, which directly tests the hybrid suggested by the tension between graph-network predictors and tree models.

Why not just…?

Why not just fit XGBoost on the trained networks? This is the real threat, and we treat it as such. Tree models cannot use the roughly 400,000 untrained networks in NAS-Bench-101's pool. Our bet is that at 10 to 50 labels this matters, while at hundreds of labels it likely does not. The matched comparison will settle it: same features, same anchors, same tuning budget. If XGBoost ties us at every budget, the honest conclusion is that the contribution is the anchor-selection design, not propagation. The XGBoost-on-anchor-coordinates variant would then be the method we recommend.

Why not just rank by zero-cost proxies and skip training altogether? Their 0.82 Spearman on NAS-Bench-201 is strong, but NAS-Bench-Suite shows proxy rankings fail or even invert on other spaces. Zero-Cost Proxies for Lightweight NAS itself reports degradation on topologically diverse models. Our hypothesis is that proxies define good neighborhoods even where their raw values rank badly. The test is the suite-wide experiment below: where proxy ranking correlation is low, does anchor propagation over proxy space still correlate well?

Why not just use SemiNAS-style pseudo-labeling? SemiNAS already shows unlabeled architectures help. Its iterative self-training, however, has no fixed point it is guaranteed to reach, and it does not choose which networks to train. We will run it with identical trained sets, swapping only the propagation step, and report variance across seeds as well as mean accuracy. A lower spread for closed-form propagation would be evidence of the claimed robustness. Higher SemiNAS accuracy would refute the claim.

Why not just run regularized evolution with early stopping? Evolution is the most reliable optimizer in the suite and needs no predictor. We do not expect to beat it at large budgets. The claim is restricted to the low-budget regime, and the budget-versus-accuracy curves will show where, if anywhere, the curves cross.

Proposed Experiments

The first gate is the local-smoothness diagnostic on NAS-Bench-101 and NAS-Bench-201 (all three datasets), across candidate description spaces. It costs only benchmark lookups and proxy computation.

The main experiment runs the full pipeline on NAS-Bench-101 (423,624 networks) and NAS-Bench-201. For NAS-Bench-101 we will report proxy cost honestly. We will either compute proxies on the full pool or on subsampled pools of 25k to 100k, and treat pool size as a variable, with wall-clock reported for proxies, anchor selection and the solve separately. Metrics are Kendall's tau and Spearman over the full space, best-found test accuracy versus number of trained networks, and the number of trained networks needed to hit the global optimum (94.32% on NAS-Bench-101; 94.37%, 73.51% and 47.31% on NAS-Bench-201 CIFAR-10, CIFAR-100 and ImageNet-16-120, per NAS-Bench-201).

The transfer experiment uses TransNAS-Bench-101. Here the description space and $Z$ are task-independent, so one graph is built once and only anchor labels change per task. At a 50-network budget we compare against Arch-Graph's reported 5.24 average rank. We also test whether reusing the same anchors across tasks loses much against re-selecting them per task.

The breadth experiment runs on the NAS-Bench-Suite spaces outside vision, where proxies are known to be fragile. It directly tests the claim that neighborhoods transfer better than scores.

The decisive outcomes are three. If the matched-feature XGBoost baseline equals anchor propagation at budgets of 50 or fewer trained networks, the propagation claim is falsified. If proxy-space propagation fails exactly where proxy ranking fails, the robustness corollary is falsified. If both survive, we will have shown that a linear-time graph method can turn a training budget of a few dozen networks into a consistent ranking of hundreds of thousands.