Spend Evaluation Compute Only Where the Advantage Sign Is Uncertain

A reinforcement-learning architecture search controller does not need to know how accurate each candidate network is. It only needs to know which candidates in its current batch beat which others, because that ordering is all its normalized learning signal keeps. Most of the cost of architecture search goes into measuring accuracy, either by training candidates for many epochs or by fine-tuning them inside a shared network. Much of that money buys precision the controller then throws away. We propose a controller whose reward is a bounded, centered win-rate within each group of sampled architectures. Each pairwise comparison is settled by climbing a ladder of evaluations that get more expensive at each step: a free score computed at initialization, then a few training epochs, then full training. A pair moves up the ladder only while its order is still in doubt.

The second motivation is a failure mode that both fields have seen without connecting. Language-model reinforcement learning has documented the "standard deviation trap": when a group of rollouts all score about the same, dividing by their tiny spread blows up gradients (Tricks or Traps?). Architecture search produces exactly this situation late in a run, when the controller concentrates on the top of the space. It is also the regime where cheap proxies are known to fail, since zero-cost scores "struggle to discriminate among the top 10%" (Zero-Cost Proxies for Lightweight NAS; EZNAS). Standard normalization therefore amplifies proxy noise at the moment the proxy is least reliable. Win-rate advantages with uncertainty-driven escalation address both problems: they never divide by a vanishing spread, and they spend compute on exactly the near-ties that matter.

Core Claim

In policy-gradient architecture search with cheap evaluations, the choice of reward normalization and the allocation of evaluation compute are one design problem. Our claim is that comparison-based, bounded advantages make it possible to allocate fidelity per pair, deciding for each pair of candidates how cheap an evaluation is good enough. At equal simulated GPU time, this should reach better architectures than either fixed-fidelity normalized REINFORCE or rank-based evolution given the same evaluation ladder.

The part we consider new is not "normalize rewards in NAS". It is using the structure of the normalized signal to decide how much each evaluation is worth. The claim is falsifiable. If a fixed cheap fidelity combined with rank normalization matches the adaptive scheme at equal cost, then the adaptive escalation is useless and the paper becomes a negative result about it.

Mechanism

The controller samples a group of $G$ cell architectures at each step. For a pair $(i,j)$, let $\hat p_{ij}$ be the estimated probability that $i$ has higher full-training validation accuracy than $j$, based on the evidence gathered so far for that pair. The advantage of architecture $i$ is

$$A_i = \frac{1}{G-1}\sum_{j \neq i} \hat p_{ij} - \tfrac{1}{2},$$

which is bounded in $[-\tfrac12,\tfrac12]$ and centered at zero within the group. When every member of a group is a genuine near-tie, all $\hat p_{ij}$ sit near one half. The resulting gradient is small rather than an amplified copy of the noise.

Each pair starts at the cheapest rung of the ladder, where $\hat p_{ij}$ comes from the zero-cost score difference passed through a calibration curve. A pair is escalated to the next rung only if $\hat p_{ij}$ falls inside an uncertainty band $[\tfrac12-\delta,\tfrac12+\delta]$ and the remaining step budget allows it. Each architecture's evaluation at a given rung is computed once and reused across all pairs it appears in, so escalation costs are paid per architecture, not per pair. The calibration curves map a score gap at a given rung to a probability that the full-fidelity order is the same. They are fit online from pairs that have already been escalated to full fidelity, using a single logistic model per rung. The band width $\delta$ is the only new hyperparameter, and we sweep it.

This design borrows from three prior methods and departs from each:

  • Win-rate transform. It comes from Calibrated Multi-Preference Optimization, which maps diffusion-model rewards into bounded expected win-rates against a fixed baseline model, computed offline. We compute win-rates online and within the group.
  • Pairwise view of evaluation. It comes from ReNAS, which showed that ranking, not absolute accuracy, is what search needs. ReNAS used that insight to train an offline surrogate for evolution, not to shape a controller's advantage or to decide how much to spend on each comparison.
  • Fidelity matters unevenly. Rethinking Performance Estimation found that training epochs matter for ranking fidelity while resolution can be pruned. It chose one budget for all candidates. We choose the budget pair by pair.

Research Program

All primary work runs on NAS-Bench-201. This benchmark is a lookup table of 15,625 cells trained on CIFAR-10, CIFAR-100 and ImageNet-16-120, with full training logs. That lets us simulate the evaluation ladder exactly. The rungs are a zero-cost proxy score, logged validation accuracy at a small number of epochs, and final accuracy.

Cost is charged in logged training wall-clock time, not FLOPs. Abdelfattah et al. report that a 64x FLOP reduction gave only a 4x wall-clock speedup, so FLOP-based accounting would flatter cheap rungs. For the zero-cost rung we use the vote ensemble of Synflow, jacob_cov and SNIP from Zero-Cost Proxies for Lightweight NAS. We charge it the cost of one forward and backward pass.

The analysis has two parts. First, we measure the phenomenon directly. For each normalization scheme and each rung, we track how often the sign of the computed advantage agrees with the sign of the advantage under true final accuracy, as the controller's sampling distribution sharpens over the run. The schemes are:

  • raw reward,
  • moving-average baseline,
  • group-mean and group-SD,
  • the hybrid of group-mean centering with batch-level SD that Liu et al. recommend,
  • batch-wise reward normalization in the style of DLER,
  • win-rate.

We expect SD-based schemes to lose sign agreement late in search at cheap rungs, and win-rates to degrade gracefully toward zero advantage. If that pattern does not appear, the motivation for the method is weaker than we think, and we will say so.

Second, we run full searches under fixed simulated budgets and record anytime regret against the benchmark optimum.

As a transfer check, we repeat the main comparison on NAS-Bench-101 with a two-rung ladder: zero-cost proxy, then final accuracy. This tests whether the calibration step survives a larger, differently structured space.

A secondary extension adds FLOPs as a second objective. The advantage becomes a weighted sum of per-objective win-rates, and we compare it against linear scalarization of accuracy and FLOPs. This extension is kept explicitly secondary.

Baselines

Naive reference. REINFORCE with the raw validation-accuracy reward, as benchmarked in NAS-Bench-201, run with full-fidelity evaluation and with each fixed cheap fidelity. Random search under the same simulated budget gives the floor. Dong and Yang report that REINFORCE is often outperformed by random search and regularized evolution. We found no reported numeric search result for REINFORCE or regularized evolution on Lacuna beyond that qualitative finding, so we will produce these numbers ourselves under one protocol. The only fixed reference values the file provides are the benchmark optima: 94.37% on CIFAR-10, 73.51% on CIFAR-100 and 47.31% on ImageNet-16-120.

Strongest normalized reinforcement-learning competitor. REINFORCE with the hybrid advantage normalization from Tricks or Traps?, using group-mean centering and batch-level standard deviation. Liu et al. found this scheme to be the most stable option in language-model reasoning, where GRPO and DAPO "peaked early and then collapsed." It is run with each fixed rung of our ladder, and with the zero-cost warmup of Abdelfattah et al. The controller architecture, group size, learning-rate sweep and number of seeds are the same as ours.

Strongest non-reinforcement-learning competitor. Regularized evolution, given the same three-rung ladder and the same simulated budget. Its tournament selection is already rank-based and so does not suffer from the standard deviation trap.

Static proxy pipeline. Rank all 15,625 cells by the zero-cost vote ensemble, which reaches 0.82 Spearman correlation on NAS-Bench-201 per Abdelfattah et al. Then fully evaluate the top-$k$ until the budget runs out. We also run a version using EZNAS-A, which reports a Kendall Tau of 0.65 on CIFAR-10 (EZNAS).

Ablations. These isolate the two ingredients. Win-rate advantages at a single fixed rung isolate the normalization. SD-normalized advantages with the escalation rule, where escalation is triggered by small score gaps, isolate the fidelity allocation.

What counts as beating them. Lower median final regret at matched simulated GPU time on at least two of the three datasets, with non-overlapping interquartile ranges over 30 seeds. The win must also hold against regularized evolution, not only against REINFORCE variants.

Why not just…?

Why not just use regularized evolution, which already beats RL on NAS-Bench-201 and needs no normalization? This is the real threat. Dong and Yang's results favor evolution, and evolution is rank-based by construction. Our answer is not that reinforcement learning is better per se. Our claim is that per-pair fidelity escalation is the active ingredient, so we also port the escalation rule into evolution's tournaments. If evolution with escalation ties our controller, we will report the result as a fidelity-allocation finding that is agnostic to the controller. The case for the policy-gradient version then rests only on the multi-objective extension, where Chen et al. report their policy-gradient method is 7.7x to 8.5x faster than LEMONADE (Multi-objective NAS via NPG).

Why not just rank-transform rewards at one cheap fidelity? That is our first ablation. It removes the standard deviation trap but still pays a uniform cost for every candidate, and it cannot recover order among top-decile near-ties that the cheap rung cannot see. If this ablation matches the full method at equal cost, escalation adds nothing and we will say so.

Why not just filter with zero-cost proxies and fully train the top few? That pipeline is cheap and strong across the whole space. But its known weakness is the top 10%, which is where the final choice is made. The static-pipeline baseline measures this directly. We expect it to win at very small budgets and lose once there is enough budget to resolve near-ties.

Why not just use a successive-halving-style schedule over a fixed pool? Such schedules allocate fidelity by survival over a pool, without a policy that learns where to sample. We will include a halving schedule over the controller's own samples as an additional ablation. It cuts candidates by rank at each rung instead of escalating uncertain pairs, and so tells us whether pair-level uncertainty beats rank-level culling.

Decisive Checks

Three outcomes settle the proposal. The first is the sign-agreement curves. Win-rate advantages must retain markedly higher sign agreement than SD-normalized ones at cheap rungs late in search. The second is the budget-matched regret against regularized evolution with the same ladder. The third is the fraction of total compute spent on escalations, together with the calibration accuracy of the online flip-probability model. The method's logic requires that escalations concentrate on pairs whose full-fidelity accuracies differ by less than the cheap rung's noise. If escalated pairs turn out no closer than random pairs, the mechanism is not doing what we claim, whatever the headline regret shows.