Lexicographic Budget Allocation for Hardware-Constrained Architecture Search

When engineers search for a neural network to run on a phone or an edge accelerator, the requirements usually come in a fixed order. The model must fit the device's latency or memory budget, and only then does accuracy matter. A third criterion such as energy matters only when two models tie on accuracy. Most of the cost of architecture search comes from measuring candidates: training them to estimate accuracy, or profiling them on real hardware to measure latency. Our idea is that a strict priority order tells you which of those measurements are worth paying for. Profiling precision matters only for candidates near the latency limit that could still be the most accurate. Training precision matters only for candidates that could plausibly meet the limit. Every other measurement is wasted compute.

We propose a search procedure that treats hardware feasibility as the top-priority objective, accuracy as the second, and energy as the third, and that sends evaluation compute only to candidates whose place in this order is still uncertain. The procedure borrows from lexicographic reinforcement learning, which optimizes ranked objectives in which a higher rank can never be traded for gains lower down. Specifically, it takes the "tolerance" that decides how strictly a higher tier is enforced and replaces the hand-tuned value with one computed from the measured error of the cheap estimators. The claim we would test is concrete: for a fixed compute budget, the procedure returns architectures that violate the hardware budget less often and lose less accuracy relative to the true constrained optimum than filter-then-search, penalty-weighted search, or Pareto-front search.

Core Claim and Mechanism

Let $c(a)$ be the true on-device latency of architecture $a$, $B$ the hard latency budget, and $f(a)$ its fully trained test accuracy. The target is $a^\star = \arg\max_a f(a)$ subject to $c(a) \le B$, with energy used only to break ties. All we ever observe are cheap, noisy estimates. Latency comes from a learned predictor or a few profiling runs, giving an estimate $\hat c(a)$ with standard error $\sigma_c(a)$. Accuracy comes from a zero-cost score or a short partial training run, giving $\hat f(a)$ with error $\sigma_f(a)$. A candidate is certified feasible if $\hat c(a) + \kappa\sigma_c(a) \le B$ and plausibly feasible if $\hat c(a) - \kappa\sigma_c(a) \le B$, where $\kappa$ sets the confidence level. The plausibly optimal set is

$$ \mathcal{P} = \{a : a \text{ plausibly feasible and } \hat f(a) + \kappa\sigma_f(a) \ge \max_{a' \text{ certified}} \hat f(a') - \kappa\sigma_f(a')\}. $$

At each step the search spends its next unit of compute on the member of $\mathcal{P}$ whose ambiguity is largest. That unit may be one more profiling run if its feasibility is undecided, or one more fidelity step of training if its accuracy rank is undecided. Candidates outside $\mathcal{P}$ get nothing further.

The tier-1 slack is $\kappa\sigma_c$. This plays the role of the tolerance $\tau$ in Lexicographic Multi-Objective Reinforcement Learning, which filters actions within $\tau$ of the best primary value and leaves choosing $\tau$ as an open heuristic. Here the slack is set by estimator error that we measure on a held-out calibration pool, not tuned by hand. The rule also addresses the failure that Safety-Polarized and Prioritized Reinforcement Learning documents in safe RL: hard masks built on immature value estimates permanently exclude good options. Our gate rejects a candidate only once it is confidently infeasible, never on a point estimate alone.

Relation to Prior Work

The motivation comes from two strands. On the search side, MODNAS (Multi-objective Differentiable Neural Architecture Search) learns preference-conditioned Pareto fronts with multiple-gradient descent. SMEMNAS (A Pairwise Comparison Relation-Assisted Multiobjective Evolutionary Neural Architecture Search Method With Multipopulation Mechanism) and CENAS (Pareto-Wise Ranking Classifier for Multiobjective Evolutionary Neural Architecture Search) use classifiers that predict pairwise or Pareto-dominance relations. All three treat objectives symmetrically, so none can say that a 2 ms overrun is unacceptable at any accuracy. All three also spend compute mapping regions of the front that a deployment will never use.

On the measurement side, HW-NAS-Bench shows that cheap hardware surrogates are unreliable: the rank correlation between FLOPs and Edge TPU latency is 0.18. EZNAS shows that zero-cost accuracy proxies rank well overall (Kendall τ 0.65 on NAS-Bench-201 CIFAR-10) but cannot separate the top decile. Together these say the cheap estimators are good enough to discard most of the space and not good enough to decide the winner. That is the regime in which spending compute only on ambiguous candidates should pay off.

Two papers supply method components. Making Execution Time a Trainable Reward for Code Generation gates a speed reward behind full correctness. It also found that a collapsed binary percentile reward beats a graded runtime reward under timing noise: 27.7% versus 18.1% at its speed-conditioned pass rate. We adopt the same binary treatment of feasibility, rather than a graded latency penalty, and test whether that finding transfers to noisy device profiling. Can Training Logs Make Model Comparisons More Precise? shrinks the variance of accuracy comparisons with early-log covariates. We reuse that adjustment to tighten $\sigma_f$ at low cost.

The power-of-two encoding in Minimum-violation LTL Planning with Conflicting Specifications gives an exact lexicographic order when values are known. Our setting differs because the values are only estimated, and the open question is how to spend compute to resolve the order.

Research Program

We would build the allocator as a wrapper that can sit around any candidate generator. We would pair it with regularized evolution, because NAS-Bench-201 reports that simple evolution and random search are hard to beat and do not suffer the skip-connection collapse of differentiable methods.

The available evaluation actions are an EZNAS-style zero-cost score, partial training at increasing epoch counts read from NAS-Bench-201 learning curves, a latency predictor, and simulated profiling runs. Each profiling run draws from HW-NAS-Bench's measured latency with multiplicative and additive noise, following the noise model of the code-generation paper, with noise levels calibrated per device. Every action is charged a cost: epochs consumed for training, and a per-run cost for profiling.

The analysis has three parts. The first is a simple bound. If each estimator's confidence interval holds with probability $1-\delta$, the returned architecture violates the budget with probability at most roughly $\delta$ times the number of certification decisions, which follows from a union bound. The second is an empirical check that this rate is calibrated. The third is a study of where compute actually goes, measured as the fraction of spend inside $\mathcal{P}$ and how that fraction changes as the budget $B$ tightens.

Baselines

The naive reference is uniform random search with point-estimate filtering. It samples architectures, discards those whose predicted latency exceeds $B$, trains survivors at a fixed fidelity, and returns the best. It receives the same total compute as our method and shows what doing nothing clever buys.

The strongest practical competitor is filter-then-successive-halving with regularized evolution. It uses point-estimate latency filtering, then promotes candidates through increasing training fidelities as in budgeted performance estimation from Rethinking Performance Estimation in Neural Architecture Search, which reports search costs as low as 0.33 GPU days. This baseline already gates by stage, which makes it the fairest test of whether uncertainty-aware lexicographic allocation adds anything.

The second strong competitor is MODNAS run with a preference vector concentrated on accuracy, followed by post-hoc selection of the most accurate architecture that meets the budget. MODNAS reports finding fronts for 19 devices in 25.25 GPU hours on NAS-Bench-201. On the specific quantity we target, test-accuracy regret against the exhaustive constrained optimum under a hard latency budget, we found no reported result on Lacuna for any method, so we would compute it ourselves for every baseline.

We also add a weighted-penalty evolutionary baseline, whose penalty weight is tuned on a validation budget. Finally, we add a constrained-optimization baseline that weights expected improvement by the predicted probability of feasibility. The file contains no implementation of this approach, so we would build one.

All methods share the same benchmark, the same estimator pool, the same charged compute, and twenty search seeds. Every tunable knob, including $\kappa$ for our method, gets the same tuning budget, chosen on one device and frozen for the others.

Two ablations isolate the key ingredients. The first fixes $\kappa\sigma_c$ to a constant slack, which removes the error-calibrated tolerance. The second spends compute uniformly across plausibly feasible candidates, which removes the allocation targeted at ambiguous candidates.

Beating the baselines means matching the strongest baseline's regret at no more than half its compute, or achieving lower regret at equal compute, while keeping the true violation rate at or below the nominal $\delta$.

Why not just…?

Why not just filter infeasible architectures and run any good search? When latency is free and exact, as in a HW-NAS-Bench lookup, this is correct, and our method reduces to it. The question is whether the advantage survives once profiling is costly and noisy, as it is on real devices. The filter-then-successive-halving baseline is built to answer this. If it matches us under realistic noise, the proposal's value collapses to calibrated slack alone, and the first ablation tells us whether even that matters.

Why not just add a latency penalty to the accuracy objective? A penalty lets enough accuracy buy a violation. Lexicographic Multi-Objective Reinforcement Learning identifies this as the route to specification gaming, and the code-generation study shows the matching failure in which outputs that are fast but wrong win without a gate. We measure the penalty baseline's violation rate directly rather than assume it.

Why not compute the Pareto front and choose afterward? The front contains the answer, but it costs compute in regions the deployment rejects. Pareto rank-based search also inherits the rank disorder that CENAS documents. The MODNAS-plus-selection baseline reports both the regret and the compute spent outside the feasible region.

Why not use constrained Bayesian optimization with a probability-of-feasibility weight? This is the most serious threat, because it also uses uncertainty about feasibility. It does not, however, represent the lexicographic tie-breaking tier, and it does not choose between measurement types. We include it as a baseline. If it matches us, we would report that the lexicographic framing adds nothing beyond a clean derivation.

Proposed Experiments

The primary testbed is NAS-Bench-201 on CIFAR-10, CIFAR-100, and ImageNet-16-120, crossed with the six HW-NAS-Bench devices. Budgets are set at the 10th, 30th, and 50th percentiles of each device's latency. Because the space is exhaustively trained and profiled, the true constrained optimum and the true violation status of every returned architecture are known exactly.

The metrics are test-accuracy regret against the constrained optimum, the true violation rate, and the compute needed to reach a given regret.

Several checks would be decisive. First, the error-calibrated method should beat filter-then-successive-halving at the tight 10th-percentile budgets on the Edge TPU and FPGA, where FLOPs track latency worst. Second, its violation rate should track $\delta$ as noise varies. Third, the binary feasibility gate should beat a graded latency term, as it did for runtime in code generation.

A scale test on the FBNet space in HW-NAS-Bench checks feasibility gating alone, since that space has hardware costs but no exhaustive accuracies. A transfer run on a once-for-all MobileNetV3 space on ImageNet reports accuracy and latency compliance against the published SMEMNAS and CENAS figures for reference only: 78.91% Top-1 at 570M MAdds and 79.6% Top-1 at 482M FLOPs. Those papers did not enforce a hard latency budget, so these numbers are context rather than a direct comparison.