Hedged Architecture Portfolios: Choosing k Networks per Device That Survive Proxy Error

Cheap neural architecture search does not end with a single answer. It ends with a short list. Training-free scores rank thousands of candidate networks, latency is predicted from FLOPs or a lookup table, and an engineer then fully trains and deploys a handful of the top-ranked models on each target device. The cheap signals are often wrong in exactly the region that matters. Evolved zero-cost scores lose most of their ranking power among the best 10% of networks (EZNAS). FLOPs correlate with measured latency at a Kendall rank correlation as low as 0.18 on an Edge TPU (HW-NAS-Bench). If the k models on the short list are near-copies of one another, they share the proxy's mistakes, and k verification runs buy little more than one.

We propose to treat the short list as the object of optimization. For each hardware niche (a device plus a latency budget), we pick a portfolio of k architectures that maximizes the expected best true accuracy among members that actually meet the measured latency budget. Proxy error is modeled as correlated across structurally similar networks. Under this objective, structural diversity is not an aesthetic goal or an extra objective to trade off against quality. It is what the math prescribes, and only to the degree that structurally distant networks really do have less correlated proxy errors. That degree is an empirical question, and we test it first.

Core Claim

Existing quality-diversity work in architecture search defines diversity by hardware cost. Tackling NAS with Quality Diversity Optimization keeps one elite per latency bin. MO-HDNAS rewards spread in hardware cost to escape the "small model trap," in which multi-objective search collapses onto tiny, easy-to-minimize models. MTF-PDNS measures novelty in a space of zero-cost statistics. None of them says how to choose several models inside one niche, and none ties diversity to the reason one wants several models at all, which is protection against the gap between the cheap model and reality. That gap is the central motivation of multi-solution optimization (Robust Scheduling with GFlowNets).

Our claim has two parts. First, residuals of zero-cost accuracy proxies and of latency predictors are spatially correlated in architecture graph space: nearby cells err together. Second, a portfolio chosen to maximize hedged best-of-k utility lowers per-niche regret after verification, compared with taking the top-k by proxy, compared with hardware-cost diversity, and compared with naive maximum-distance selection, at the same proxy and training budget. If the first part fails, the second cannot hold, and we will report that structural diversity does not help in this setting.

Formally, let $N$ be the architectures whose predicted latency fits a niche budget $L$. Let $f(x)$ be the true accuracy of architecture $x$ and $\ell(x)$ its measured latency on the device. We choose $S \subset N$ with $|S| = k$ to maximize

$$U(S) = \mathbb{E}\left[\max_{x \in S} f(x)\,\mathbf{1}\{\ell(x) \le L\}\right],$$

where the expectation is over a residual model. In that model, $f(x) = \mu(x) + \varepsilon(x)$, $\mu$ is a calibrated mapping of the proxy score, and $\varepsilon$ is a Gaussian process whose kernel is a function of graph edit distance between cells. A second process of the same form covers the latency residual. The expected maximum is monotone submodular in $S$ for any joint distribution, so greedy selection with Monte Carlo estimates has the standard $1 - 1/e$ approximation guarantee. That makes selection cheap even over thousands of candidates.

Relation to Prior Work

The method draws on three lines of work. Multi-solution optimization supplies the framing. Modelling Diversity of Solutions separates a quality threshold from an inter-solution distance requirement. Evolutionary Multi-Objective Diversity Optimization and Coevolutionary Pareto Diversity Optimization optimize whole solution sets against quality and diversity. In all three, quality and diversity are separate quantities whose trade-off the user must set. Our objective folds them into one quantity, with the exchange rate estimated from data rather than fixed by a threshold.

The "illusion of diversity" result in Illuminating the Diversity-Fitness Trade-Off shapes the design. Distance that does not track functional difference is useless. This is why we measure diversity's value through error correlation rather than assume it. Symmetry problems in naive distances (Evolutionary Multi-Objective Diversity Optimization) are why we compute graph edit distance on canonicalized cells, removing isomorphic duplicates as NAS-Bench-101 does.

The mechanism resembles batch Bayesian optimization (for example, Probability of Matching for Batch MOBO), and we say so plainly. What differs is the regime. Batch BO is sequential, and its batch draws feed further rounds. Here the k picks are a single, final verification batch scored only by its best feasible member. The covariance is over proxy residuals under a graph kernel, not over the objective itself. NEAS also selects multiple diverse subnetworks, but as a cooperative two-branch ensemble that runs jointly. Our portfolio members are interchangeable alternatives, and only one is deployed.

Research Program

The work runs in three stages. In the first stage we measure residual structure. On NAS-Bench-201 (15,625 cells, trained on CIFAR-10, CIFAR-100 and ImageNet-16-120) and NAS-Bench-101 (423,624 cells, CIFAR-10), we compute synflow, NASWOT, jacov, snip and an EZNAS-style evolved score. We fit monotone calibrations from each score to test accuracy, then estimate how residual correlation decays with graph edit distance, operation-histogram distance, and hardware-cost distance. The same is done for latency: FLOPs-based prediction and a learned predictor are compared against measured latency on the six HW-NAS-Bench devices. This stage alone answers whether structure carries information about proxy failure. No paper in the file reports it.

In the second stage we build the selector. The residual model is fit from a small calibration set of $m$ fully trained architectures in the target task. Each one is charged as a training cost, and $m \in \{20, 50, 100\}$. We also test transfer: fit on CIFAR-10, apply to CIFAR-100 and ImageNet-16-120, with zero target calibration. Greedy hedged selection then fills each niche.

In the third stage, for regimes where the proxy itself is too expensive to run on every candidate, we add an in-search variant. A small coevolving population, in the spirit of the optimization and diversity populations of Coevolutionary Pareto Diversity Optimization, proposes candidates whose marginal gain in $U$ is high. We test this variant explicitly against search-then-select.

Baselines

The naive reference is top-k by proxy within each niche: rank feasible-by-prediction architectures by the best single zero-cost score and verify the top k. On NAS-Bench-201 CIFAR-10, EZNAS-A reaches Kendall tau 0.65 against NASWOT and synflow at 0.57 (EZNAS), so we use EZNAS-A, the strongest of these. Beating this baseline tests whether hedging adds anything over a good score.

The strongest existing quality-diversity method is BOP-ElitesHB (Tackling NAS with Quality Diversity Optimization). It combines random-forest surrogates with Hyperband multi-fidelity training to fill a priori latency niches, and it is reported to reach target solutions 2.41 times faster than the multi-objective ParEGOHB. Run as published, it gives one elite per niche. For a fair comparison we let it spend the same total training budget (calibration plus k verifications, in epoch-equivalents from the NAS-Bench lookup tables), use the same niches and the same predicted-latency signal, and take its top-k surviving elites per niche.

MO-HDNAS (MO-HDNAS) is the strongest proxy-only diversity method, reported at 0.65 GPU hours against 20.87 for HW-EvRSNAS. We run its NSGA-II with hardware-cost diversity and its representation-similarity proxy under the same proxy-evaluation budget, then take the top-k per niche. MTF-PDNS (MTF-PDNS), reported at 2.02 GPU hours against 104.44 for training-based search on NAS-Bench-101, is run the same way.

Two ablations isolate the key ingredient. The first sets the residual kernel to zero correlation. This turns hedged selection into ranking by a risk-adjusted score and removes any reason for diversity. The second replaces graph edit distance with hardware-cost distance in the kernel. Comparing the two shows whether structural distance specifically carries the benefit.

The headline metric is per-niche regret. It is the best true test accuracy among architectures whose measured latency fits the niche, minus the best true accuracy among portfolio members that truly fit, averaged over niches, devices and 20 seeds for k in {1, 2, 4, 8}. The NAS-Bench-201 per-dataset optima of 94.37%, 73.51% and 47.31% (NAS-Bench-201) give absolute context. We found no reported best-of-k or per-niche portfolio regret result on Lacuna for any baseline, so all baseline regrets will be measured in this study. Beating a baseline means lower mean regret at k ≥ 2 with a paired test across niches and seeds, with no loss at k = 1.

Why not just…?

Why not just pick the top-k by the best available proxy? If proxy residuals turn out to be uncorrelated across architectures, this is the optimal policy, and our method reduces to it through the zero-correlation ablation. The case against it rests on the documented collapse of proxy rankings in the top tail (EZNAS) and on proxy deception toward bloated networks (MTF-PDNS). Neither result shows that the errors are shared among neighbors. Stage one settles this directly, and we treat it as a real threat.

Why not just run ordinary multi-objective search and then greedily pick a maximally spread subset? This is the most serious alternative. On NAS-Bench-201, every candidate can be scored by a zero-cost proxy, so "search" adds almost nothing there, and the contribution is entirely the selection rule. We therefore compare hedged selection against max-min graph-distance selection over a quality threshold drawn from the same pool. Pure distance maximization ignores how much quality each pick sacrifices, and Illuminating the Diversity-Fitness Trade-Off warns that distance alone is often not functional difference. Whether doing the search with the portfolio objective beats search followed by selection is tested only where proxy calls are budgeted (1,000 to 5,000 calls on NAS-Bench-101). Here the concern from Modelling Diversity of Solutions, that post-hoc selection is limited by the pool it inherits, can actually bite. If post-hoc selection ties there, we will recommend it and drop the in-search variant.

Why not just spend the budget on multi-fidelity training, as Hyperband-style quality-diversity search does? Partial training directly reduces proxy error, so it competes for the same compute. The BOP-ElitesHB comparison at matched epoch-equivalents answers this. We also run a hybrid in which hedged selection chooses which candidates enter Hyperband. If BOP-ElitesHB alone wins at matched budget, hedging offers nothing beyond better fidelity allocation.

Decisive Checks

The idea stands or falls on two numbers. The first is the slope of proxy-residual correlation against graph edit distance on NAS-Bench-201 and NAS-Bench-101. A flat curve falsifies the premise. The second is the regret gap between hedged selection and both top-k-by-proxy and the hardware-distance ablation at k = 4 on the HW-NAS-Bench devices. Here measured latency is the feasibility check and FLOPs is the planning signal, the setting in which HW-NAS-Bench documents the worst mismatch.

A secondary check covers transfer. If a residual model calibrated on CIFAR-10 still reduces regret on ImageNet-16-120 with no target calibration, then the hedge costs nothing beyond the k verification runs that would have been spent anyway.