Searching for Architectures That Are Feasible After Rounding

Gradient-based architecture search methods, often called differentiable NAS, work in two steps. First they search over a blend of candidate operations, a "supernetwork" in which every layer is a softmax-weighted mixture of choices. Then they round that blend to one concrete network. When the search must respect a hardware budget, such as a 5 ms latency limit or a microcontroller's SRAM, the budget is usually checked on the blend: the method adds up each candidate's measured cost, weighted by its mixture coefficient. The deployed object is the rounded network, though, and real hardware cost does not add up. Compilers fuse adjacent layers, peak memory is a maximum over layers rather than a sum, and an unsupported operator can fall back to the CPU. A blend can therefore look under budget while most of the concrete networks it could round to are over budget, or the reverse. We call this the hardware discretization gap. It is the hardware counterpart of the accuracy collapse that Discretization-Aware Architecture Search documented, in which a DARTS supernet at roughly 88% accuracy falls to about 10% once rounded.

This proposal treats the architecture as a probability distribution over concrete networks and states the hardware budget as a constraint on those networks: the probability that a sampled concrete network exceeds its true, whole-network measured cost must stay below a small tolerance. As the search concentrates the distribution, the final rounding step stops changing anything. The deployed network is a sample the constraint has already covered. Prior sensitivity enters as the evaluation lens. A distributional search needs a prior over architectures, so we ask how strongly the final deployed network depends on that prior's concentration. We conjecture that constraining the deployed object, rather than the blend, makes the outcome far less sensitive to the prior than current Bayesian NAS methods are.

Core Claim

Let $q_\theta$ be a categorical distribution over concrete architectures $a$, with logits $\theta$ drawn from a Dirichlet with concentration $\beta$ as in DrNAS. Let $c_d(a)$ be the true cost of $a$ on device $d$: whole-network measured latency, or analytically exact peak memory. Let $T$ be the budget. The search solves

$$\min_\theta \; \mathbb{E}_{a\sim q_\theta}\big[\mathcal{L}_{val}(a)\big] \quad \text{s.t.} \quad \Pr_{a\sim q_\theta}\big(c_d(a) > T\big) \le \delta,$$

where $\mathcal{L}_{val}$ is the validation loss and $\delta$ is the tolerated violation rate. The constraint is enforced with a dual variable updated by gradient ascent, so no penalty weight is hand-tuned. Its gradient comes from a score-function estimator over $K$ sampled concrete architectures per step. Each sample is scored with the true cost table, which is cheap because the table is a lookup. The quantity the method is built to close is the gap

$$G_d(\theta) = c_d\big(\arg\max q_\theta\big) - \sum_{l,o} \pi_{l,o}(\theta)\, \mathrm{LUT}_d(l,o),$$

the difference between the true cost of the rounded network and the mixture-weighted per-layer lookup-table estimate. Here $\pi_{l,o}$ is the mixture weight of operation $o$ at layer $l$ and $\mathrm{LUT}_d$ is the per-operator cost table.

The claim is falsifiable in both directions. If $G_d$ is small on a device, because costs there really are additive, then the method reduces to sampled-hinge search and offers nothing. Our first experiment measures $G_d$ before any method is compared.

Research Program

The work has three parts.

The first part is a diagnostic. HW-NAS-Bench provides measured whole-network latency and energy for all 15,625 NAS-Bench-201 cells on six devices. It also reports that FLOPs rank-correlate with Edge TPU latency at only 0.18 Kendall tau, and below 0.5 across edge devices. That makes it possible to compute $G_d$ exactly along real search trajectories of DARTS, DrNAS, and a lookup-table-penalized search. We will report how $G_d$ grows as budgets tighten and how it differs across the Edge TPU, Pixel 3, Raspberry Pi 4, Jetson TX2, Eyeriss, and the ZC706 FPGA. A second diagnostic uses peak activation memory. Because it is a maximum over layers, the memory of the "average" network is provably not the average memory of the networks it can round to. This applies directly to the microcontroller setting of DUCCIO.

The second part is the method described above. Its two key ingredients are scoring discrete samples with non-additive true cost, and adapting the constraint multiplier automatically. A concentration schedule drives $q_\theta$ toward a point mass only as fast as the measured violation rate allows.

The third part is a prior-sensitivity study. We sweep the Dirichlet concentration $\beta$ over two orders of magnitude, and BayesNAS's sparsity-intensity hyperparameter over a comparable range. We then measure the spread of final accuracy and feasibility across the sweep. This question is motivated by The Bayesian Analysis of Complex, High-Dimensional Models: Can It Be CODA?, which shows that flat priors in high dimensions push mass to the edges of the parameter space and are therefore far from neutral. It is also motivated by BayesNAS, whose architecture size depends strongly on a manually tuned sparsity prior.

Relation to Prior Work

Three groups of work each cover two of our three ingredients.

The first group handles rounding without hardware. Discretization-Aware Architecture Search pushes mixture weights toward zero or one with entropy penalties to close the accuracy gap. DrNAS learns a Dirichlet over architectures and reports 2.46% CIFAR-10 error. Its authors explicitly leave hardware-constrained search to future work. We reuse DrNAS's distributional parameterization, but we constrain hardware cost on samples rather than regularizing toward binary weights.

The second group is Bayesian NAS. BayesNAS prunes on posterior uncertainty under hierarchical priors, but it measures efficiency in FLOPs. Its Laplace evidence approximation is also exposed to the scale non-invariance shown in Scale-Invariant Empirical-Bayes Laplace Approximation for ReLU Networks. We avoid evidence approximations entirely. Prior-Guided One-shot Neural Architecture Search uses FLOPs as a ranking prior, which the HW-NAS-Bench correlations above suggest is the wrong signal on edge accelerators.

The third group is hardware-constrained search. DUCCIO already samples discrete networks with Gumbel-Softmax or step functions and penalizes budget excess with a hinge, but it ramps the penalty on a heuristic linear schedule. Constraint-guided Hardware-aware NAS through Gradient Modification (ConNAS) bends architecture gradients toward feasibility using per-edge lookup-table comparisons. It treats feasibility as a crisp boundary computed edge by edge. Neither method checks whether its cost model is correct for the rounded whole network. That check is exactly what our diagnostic measures.

Baselines

The naive reference is accuracy-only DrNAS followed by argmax rounding, with the budget checked only afterward. It shows how often ignoring hardware already happens to land inside the budget.

The second baseline is DrNAS with a soft penalty on the mixture-weighted lookup-table cost, with $\lambda$ tuned by grid search. This is the standard "lambda" approach. Its grid search consumes the same total GPU-hours we allot to our method.

The third baseline is DUCCIO-style sampled-hinge search. It samples discrete networks and applies a hinge on per-layer additive cost under its linear $\lambda$ ramp. It is the closest competitor because it already discretizes during search.

The strongest existing method is ConNAS. On NATS-Bench it reports architectures within 0.14% to 0.65% of the accuracy of the best feasible architecture, with 100% constraint satisfaction, including measured Jetson TX2 latency budgets. For NAS-Bench-201 accuracy we found no exact per-dataset number for DrNAS on Lacuna; the file reports only "near-optimal" results.

All methods run in the same search space, on the same datasets, with the same supernet training budget and seeds. Feasibility and accuracy are scored with HW-NAS-Bench's measured whole-network costs, not with each method's internal surrogate.

Beating ConNAS means one of two outcomes on devices where $G_d$ is large: (a) satisfying the measured budget in at least as many runs as ConNAS while cutting its accuracy regret relative to the oracle best-feasible architecture, or (b) matching its regret where ConNAS violates the measured budget because its lookup-table feasibility was wrong.

Two ablations isolate the key ingredient. In the first, our method scores samples with the additive lookup table instead of true cost; this tests whether non-additivity is what matters. In the second, our method uses a fixed $\lambda$ instead of dual ascent; this tests whether automatic multiplier adaptation is what matters.

Why not just…?

Why not just sample discrete networks with a hinge penalty, as DUCCIO does? This is the most serious threat, and the two methods coincide when costs are additive and the multiplier schedule happens to be good. Our method differs in two respects: it scores samples with whole-network cost, and it controls the violation probability directly rather than through a hand-ramped penalty. The first ablation above, which runs our method with additive cost, approximates DUCCIO with dual ascent. If it matches the full method on every device, we will report that the contribution is only the automatic multiplier, not the treatment of the gap.

Why not just run accuracy-only search and then filter its final samples for feasibility? This is cheap. Draw the top-$k$ concrete networks from the final DrNAS distribution, measure them, and keep the best feasible one. It works if the accuracy-optimal distribution puts mass on feasible networks. For tight budgets, around the 10th to 25th percentile of device latency, that seems unlikely, because accuracy pulls toward large networks. We will run this filter with $k$ matched to our total sample evaluations and report where, if anywhere, it closes the gap.

Why not just learn a better, non-additive latency predictor and keep the standard penalty? A better predictor fixes the per-network cost estimate. It does not fix the fact that the penalty is computed on a blend, so the mismatch between blend and rounded network survives. We test this by giving the soft-penalty baseline exact whole-network cost evaluated at the argmax architecture. If that baseline matches our method, the mixture gap is negligible in practice and our claim is wrong.

Why not just treat this as black-box multi-objective search over the tabular benchmark? On NAS-Bench-201 an exhaustive oracle exists, so black-box search such as LFBO serves as a ceiling, not a competitor. The question here is whether one-shot gradient search, which is what scales to spaces without full tables, can be made reliable under non-additive costs.

Proposed Experiments

We will run searches on NAS-Bench-201 and NATS-Bench's size space, using CIFAR-10, CIFAR-100, and ImageNet-16-120. Costs come from HW-NAS-Bench on all six devices, with budgets set at the 10th, 25th, and 50th percentiles of each device's latency distribution. NATS-Bench's accuracy ceilings, about 94.4% on CIFAR-10 and about 47.3% on ImageNet-16-120, anchor regret. To test the microcontroller case, we will apply analytic peak-memory budgets to MobileNet-style spaces in the DUCCIO setting.

Metrics are:

  • accuracy regret versus the oracle best feasible architecture;
  • measured violation rate over 10 seeds;
  • the gap $G_d$ along each trajectory;
  • the accuracy drop from supernet to rounded network, measured as in DA²S;
  • the cross-prior spread of regret over the $\beta$ sweep;
  • search GPU-hours.

The decisive check has three parts. On Edge TPU and Pixel 3, where we expect non-additivity to be largest, our method should satisfy the measured budget in at least 95% of runs at $\delta = 0.05$, and either strictly reduce regret relative to ConNAS or avoid violations that ConNAS's lookup-table feasibility misses. On Jetson TX2, where ConNAS already reports 100% satisfaction, both methods should be tied. And the cross-prior spread of regret should be smaller than DrNAS-with-penalty's. Two outcomes would refute the proposal: a near-zero measured $G_d$ across devices, or the additive-cost ablation matching the full method.