Searching for neural network architectures is expensive because judging a candidate honestly means training it. The standard fix is to score candidates with a cheap stand-in. One kind is the "zero-cost proxy," a number computed from an untrained network in a single forward and backward pass. The other is a short training run. This is the same move alignment researchers make when they replace human judgment with a learned reward model, and it fails the same way. Once an optimizer pushes hard on the stand-in score, it finds whatever the score over-rewards. In language models that means verbose text. In architecture search it means oversized networks or cells full of skip connections. The reward-hacking literature has learned to describe this failure as a function of how hard you optimize. It has also learned that what matters is whether the score can tell great from excellent, not whether it ranks the whole population well. Architecture search still evaluates its proxies almost entirely by a single correlation computed over the whole search space.
We propose to import that view and turn it into a cost rule. Tabular architecture benchmarks contain the true trained accuracy of every candidate, so the full "over-optimization curve" of each proxy can be computed exactly and at almost no cost. That curve is the true quality of the proxy's pick as the number of candidates searched grows. Our claim is that the curve is governed by how well the proxy ranks within its own top tail, not by how well it ranks globally. A small number of full-training evaluations, spent only inside that tail, can estimate and repair the damage. Concretely, we will deliver three things: exact Goodhart curves for every published zero-cost and reduced-epoch proxy, a cheap tail-agreement diagnostic that predicts where each curve turns over, and a tail-targeted correction method that we will test against the strongest adaptive proxy method at equal compute.
Core Claim
Fix a proxy score $p(a)$ and the true trained accuracy $t(a)$ of architecture $a$. Define the Goodhart curve as
$$G(N) = \mathbb{E}_{S_N}\big[\, t(\arg\max_{a \in S_N} p(a)) \,\big],$$
where $S_N$ is a uniformly random set of $N$ candidates. $G(N)$ is the expected true accuracy of the proxy's favourite when the search looks at $N$ architectures. It is the architecture-search analogue of best-of-$N$ sampling against a reward model.
A noisy but unbiased proxy gives a $G(N)$ that rises and then flattens. A hackable proxy gives a $G(N)$ that rises and then falls. The fall happens because the region the proxy likes best is systematically worse than the region just below it. We define tail agreement $\tau_q$ as Kendall's rank correlation between $p$ and $t$, computed only over the top-$q$ fraction of candidates by $p$.
The hypothesis has two parts. First, $\tau_q$ for small $q$ predicts the regret at large $N$, meaning the gap to the best architecture in the space, much better than global Kendall's $\tau$ does. Second, $\tau_q$ can be estimated, and partially fixed, with a few dozen true evaluations drawn from the proxy's tail.
This framing is motivated by two observations in the literature. Chasing the Tail shows that LLM reward over-optimization is driven by misgrading in the high-reward tail rather than among mediocre responses. EZNAS separately reports that zero-cost proxies lose ranking ability among the top 10% of architectures. Nobody has checked whether the second observation is the cause of search failure in the way the first is for policy collapse.
There is a theoretical reason to expect the question to be interesting rather than trivially answered. Defining and Characterizing Reward Hacking proves that over all stationary policies every non-trivial proxy is hackable. Over a finite set of deterministic policies, however, non-trivial unhackable proxies exist. NAS-Bench-201 is exactly such a finite set of 15,625 candidates, so hacking there is not guaranteed by theory. Whether it happens is an empirical property of each proxy, and our curves measure it directly.
Research Program
The first component is measurement. NAS-Bench-Suite-Zero already provides precomputed scores for 13 zero-cost proxies across 28 task and search-space combinations. NAS-Bench-201 and NAS-Bench-101 provide true accuracies. We will compute $G(N)$ exactly by Monte Carlo over subsets, for $N$ from 10 up to the full space. We will do this for every proxy, for the ensembles of Zero-Cost Proxies for Lightweight NAS and AZ-NAS, and for plain FLOPs and parameter count.
We will also treat reduced training as a proxy. NAS-Bench-101 records accuracy at 4, 12 and 36 epochs alongside 108. Using the shorter runs as proxies tests the failure mode that Rethinking Performance Estimation in NAS hints at but does not measure: architectures that learn fast early and then plateau.
For each turning curve, we will characterize what the tail over-rewards. The candidate explanations are parameter count, FLOPs, skip-connection density, and depth, measured as the excess of each feature in the top-$q$ set relative to the true top-$q$ set. This is the architecture analogue of measuring the length–reward correlation in Loose lips sink ships.
The second component is the diagnostic. We will estimate $\tau_q$ from $k$ true evaluations sampled from the proxy's top tail, with $k$ between 10 and 100. We will then test whether this estimate predicts large-$N$ regret across all proxy–task pairs. If it does, a practitioner can decide cheaply whether a proxy is safe to push hard. They can also choose the search size $N^*$ beyond which more proxy-guided search stops helping. That gives a concrete answer to the cost question raised by A Survey of Methods for Low-Power Deep Learning and Computer Vision: the energy spent on search should not exceed what the resulting model saves.
The third component is repair. Given a budget of $B$ true evaluations, we spend them on candidates drawn from the proxy's current top tail. We use them to fit a small corrector that reorders only within that tail: a pairwise ranker over zero-cost features plus architecture encodings. We then iterate, re-drawing the tail under the corrected score.
This borrows the idea, from Chasing the Tail, of refining the evaluator specifically where top candidates are tied or misordered. It also borrows the extreme-contrast intuition of West-of-N, which showed that pairing the best and worst of 64 samples is a stronger training signal than doubling human data. It deliberately does not follow the multi-head decorrelation of ODIN or the counterfactual augmentation of RRM. Both of those remove a nuisance feature that is named in advance. Our measurement step is designed to reveal whether the exploited feature in architecture search is even a single nameable quantity.
All costs are reported in GPU-hours. Each tabular lookup of a true accuracy is charged the benchmark's recorded training time. Proxy evaluations are charged their measured wall-clock time, not FLOPs. We charge wall-clock time because Zero-Cost Proxies for Lightweight NAS found that a 64-fold FLOP reduction yielded only about a 4-fold wall-clock reduction.
Baselines
The naive reference point is random search with the same budget of true evaluations. Next to it we run "proxy argmax": pick the top proxy-scored candidate from all $N$ and train it, with no correction. Random search sets the floor. Proxy argmax is the uncorrected behaviour whose Goodhart curve we are characterizing, and the proposal has to beat both.
The simplest debiasing competitors are FLOPs alone and the parameter-penalized proxies of NAS-Bench-Suite-Zero. That paper found FLOPs to be among the most robust standalone proxies, and found that penalizing size improved correlation. We also include AZ-NAS, whose soft-AND aggregation of four metrics reports Kendall's $\tau$ of 0.710 on NAS-Bench-201 ImageNet-16-120. It is the strongest hand-built single-pass score in the file.
The learned-surrogate competitor is the XGBoost model over all 13 zero-cost features from NAS-Bench-Suite-Zero, which reports up to a 42% gain in Spearman correlation. We give it exactly $B$ true evaluations sampled uniformly at random.
The strongest existing method is ProxyBO. It fuses zero-cost proxies into Bayesian optimization, tracks each proxy's reliability online, and hands control to a Gaussian-process model as evaluations accumulate. It reports 3.92× to 5.41× speedups over regularized evolution and a 70% test-regret reduction on CIFAR-100 relative to its strongest baseline. We found no reported absolute regret value on Lacuna for ProxyBO, so we will rerun it ourselves. ProxyBO, regularized evolution, and our method will receive identical true-evaluation budgets, the same proxy feature set, the same seeds (at least 20 per configuration), and equal hyperparameter tuning effort on a held-out task.
Beating ProxyBO means lower mean test regret at matched GPU-hours, with non-overlapping 95% confidence intervals, on at least two of the three NAS-Bench-201 datasets and on NAS-Bench-101.
The key ablation gives the identical corrector the identical number of true evaluations, drawn uniformly instead of from the proxy's tail. If tail-targeted and uniform sampling perform the same, the tail hypothesis is wrong as a method, whatever the diagnostic shows.
Why not just…?
Why not just regress out parameter count and FLOPs? If the tail of every proxy over-rewards size alone, this works and our repair step adds nothing. The size-penalized baseline is included precisely to test that. The measurement study will show whether the over-represented features in proxy tails are size alone, or also skip density and depth. Skip density and depth are what weight-sharing search exploits, given the skip-connection collapse reported in NAS-Bench-201. If size explains the turnover, we will report that the simpler fix suffices.
Why not just use ProxyBO's online reliability tracking? ProxyBO measures reliability as correlation over all evaluated candidates. Because its own acquisition increasingly selects high-scoring points, that set drifts toward the tail. ProxyBO may therefore already be implicitly tail-aware, which makes it a real threat. The head-to-head at equal budget settles it. We will also report ProxyBO's internal reliability estimate against our $\tau_q$ estimate as predictors of its own final regret. If ProxyBO matches us, the contribution reduces to the diagnostic and the Goodhart-curve measurements, and we will say so.
Why not just use a better ensemble such as AZ-NAS and stop worrying? A high global $\tau$ does not tell you what happens under heavy selection. AZ-NAS's Complexity term is FLOPs, so its tail could still be size-inflated. Its Goodhart curve on the full 15,625-architecture space is the direct test. If the curve does not turn over and its $\tau_q$ stays high, ensembles are enough for this benchmark and we will report that.
Proposed Experiments and Decisive Checks
The first decisive check tests the diagnostic. Across all proxy–task pairs in NAS-Bench-Suite-Zero, we compute the rank correlation between each predictor and the full-space regret of the proxy's argmax. The predictors are tail agreement $\tau_{0.1}$, estimated from 30 tail evaluations, and global Kendall's $\tau$. The hypothesis fails if $\tau_{0.1}$ is not a clearly better predictor.
The second check tests whether hacking happens at all. A hackable proxy shows a statistically significant decrease of $G(N)$ at large $N$, with a confidence band from subset resampling. We expect turnover for size-correlated proxies and for 4-epoch training on NAS-Bench-101. We expect no turnover, or less, for FLOPs-penalized scores. If no proxy turns over, the finite-space result of Defining and Characterizing Reward Hacking is describing practice. Proxy failure would then be noise rather than exploitation, which is itself worth reporting.
The third check tests the repair. We plot regret against GPU-hours for every baseline above on NAS-Bench-201 (CIFAR-10, CIFAR-100, ImageNet-16-120, whose best test accuracies are 94.37%, 73.51% and 47.31%) and on NAS-Bench-101. We also include TransNAS-Bench-101 from the suite as a transfer task, with the corrector's hyperparameters frozen on CIFAR-10.
References
- Chasing the Tail: Effective Rubric-based Reward Modeling for Large Language Model Post-Training
- EZNAS: Evolving Zero-Cost Proxies For Neural Architecture Scoring
- Defining and Characterizing Reward Gaming
- NAS-Bench-Suite-Zero: Accelerating Research on Zero Cost Proxies
- NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search
- NAS-Bench-101: Towards Reproducible Neural Architecture Search
- Zero-Cost Proxies for Lightweight NAS
- AZ-NAS: Assembling Zero-Cost Proxies for Network Architecture Search
- Rethinking Performance Estimation in Neural Architecture Search
- Loose lips sink ships: Mitigating Length Bias in Reinforcement Learning from Human Feedback
- A Survey of Methods for Low-Power Deep Learning and Computer Vision
- West-of-N: Synthetic Preference Generation for Improved Reward Modeling
- ODIN: Disentangled Reward Mitigates Hacking in RLHF
- RRM: Robust Reward Model Training Mitigates Reward Hacking
- ProxyBO: Accelerating Neural Architecture Search via Bayesian Optimization with Zero-Cost Proxies