Exact Second-Order Gradients for Latency-Constrained Architecture Search

Differentiable architecture search trains one large "supernet" that contains every candidate operation, and learns a soft weight for each one. Hardware-aware versions add a penalty for predicted on-device latency. Almost all of them use a first-order shortcut: they update the architecture weights as if the network weights would not change in response. This note argues that the shortcut is especially harmful once a latency budget is added, because the two errors point the same way. The first-order shortcut is known to over-reward parameter-free operations such as skip connections and pooling. A latency penalty also rewards those operations, since they are the cheapest. Under a tight budget, first-order search should therefore land on architectures that meet the budget but sit below the best accuracy achievable at that latency.

We propose to measure this bias exactly on tabular benchmarks, where the true accuracy and latency of every architecture are known. We then remove it with an exact second-order correction computed by automatic differentiation rather than by finite differences. The goal is to keep the extra search cost small and to keep the correction reliable when the search runs in half precision. In two sentences: latency penalties and first-order bilevel approximations together bias hardware-aware search toward cheap but weak architectures. An exact, cheaply computed second-order term should close much of that gap, and we can check this against ground truth.

Core Claim

DARTS frames architecture search as two nested problems. The architecture weights $\alpha$ minimize validation loss at the network weights $w^*(\alpha)$ that minimize training loss. It approximates $w^*(\alpha)$ with one virtual gradient step and obtains a correction term $-\xi\,\nabla^2_{\alpha,w}\mathcal{L}_{\text{train}}\,v$, where $\xi$ is the virtual step size and $v$ is the validation gradient at the stepped weights. DARTS evaluates this mixed Hessian-vector product with a central finite difference using step $\epsilon = 0.01/\|v\|$. That costs two extra forward-backward passes and introduces truncation and roundoff error.

The hardware-aware descendants drop the term entirely. These are FBNet, with a lookup-table latency penalty; EH-DNAS, with a learned latency model; RC-DARTS, which projects onto FLOP budgets; and ConNAS, which steers the gradient toward feasibility. All of them combine their hardware signal with a first-order task gradient.

Our claim has two parts. First, the accuracy regret of first-order search at a fixed latency budget grows as the budget tightens, and the exact bilevel correction shrinks that regret. Second, the correction can be computed exactly, in one extra forward-over-reverse pass on the architecture parameters, with lower memory and lower sensitivity to numeric precision than the finite-difference version. That makes it affordable in the regime where it matters.

Research Program

The work has three parts.

Diagnostic. We run differentiable search on the NAS-Bench-201 space with latency taken from HW-NAS-Bench for each of its six devices. Because every one of the 15,625 architectures has known accuracy and latency, we can compute the optimal feasible architecture at each budget. We can then report regret directly, rather than relying on retraining noise. We also log the softmax mass assigned to parameter-free operations over the search, so the proposed mechanism (shared bias toward cheap operations) can be observed, not just inferred from final accuracy.

Exact, compiled correction. We compute $\nabla^2_{\alpha,w}\mathcal{L}_{\text{train}}\,v$ exactly by differentiating the architecture gradient a second time along $v$. We capture the whole bilevel step as a static graph so that activations needed only for the correction can be freed early and fused. This follows the evidence from Enzyme, which reports a 4.2x geometric-mean speedup by differentiating after compiler optimization, and from the Tiny Training Engine, which uses compile-time graph pruning of the backward pass to shrink training memory by 2300x. Both papers supply the method: static, compile-time differentiation. Neither applies it to a search loop or to second-order terms.

Betty is the closest software precedent. It packages several best-response Jacobian estimators for nested optimization, including iterative differentiation, finite differences, conjugate gradients and Neumann series. It shows that no single estimator dominates, and reports finite differences as fastest on its CIFAR-10 search. Betty is entirely hardware-blind, so it constrains rather than pre-empts this work. We use it as a baseline and test whether its conclusion changes once a latency term is present.

Collapsed Taylor mode speeds up operators such as Laplacians by summing many derivative directions at the input. Here only one direction, $v$, is needed, so collapsing buys nothing. We say so explicitly rather than borrowing the method for show.

Gated correction. The correction should matter most when the latency constraint is active. We therefore test a variant that computes it only on steps where predicted latency is within a margin of the budget. This is the cost-control lever that relates the proposal to the overall price of search.

Baselines

The naive reference is random sampling of NAS-Bench-201 architectures, filtered by HW-NAS-Bench latency, given the same simulated compute as one supernet search. Regret here tells us whether gradient search earns its complexity at all.

The standard hardware-aware method is first-order search with a lookup-table latency penalty in the style of FBNet. Its penalty weight is tuned over a fixed grid, and every method receives the same grid size.

The strongest existing competitor is ConNAS. It is the only method in the file with guaranteed feasibility, and it reports architectures within 0.14% to 0.65% of the optimal feasible accuracy on NATS-Bench, with constraints satisfied in 100% of runs. We run its released code on the same spaces, budgets, devices and seeds.

Because our correction modifies the task gradient, it composes with ConNAS's steering. The decisive comparison is therefore ConNAS versus ConNAS plus the exact correction, at matched wall-clock time. Beating it means lower mean regret than ConNAS, with no loss of feasibility, at the tightest third of budgets on at least the devices with non-additive latency, such as the Edge TPU and the FPGA. We do not expect gains at loose budgets.

We also include two second-order alternatives under the same latency term: DARTS's finite-difference correction and Betty's estimators. A zero-cost-proxy baseline uses EZNAS-A to rank latency-feasible architectures; it reports a Kendall tau of 0.65 on NAS-Bench-201 CIFAR-10.

The ablations that isolate our key ingredient are four: exact versus finite-difference correction, each in FP32 and FP16, and always-on versus gated correction.

Why not just…?

Why not just tune the latency penalty more carefully, or use ConNAS, and stay first-order? If the bias toward cheap operations is real, no penalty weight fixes it, because the penalty and the bias push in the same direction. ConNAS guarantees feasibility, but its near-optimality figures leave the regret at tight budgets unreported in the file. This is the most serious threat. The ConNAS-plus-correction comparison settles it: if the correction adds nothing on top of ConNAS, the claim fails.

Why not just use DARTS's finite differences or Betty's fastest estimator? Betty found finite differences fastest and best on hardware-blind search, so they may suffice. Our FP16 ablation tests the specific weakness we expect. An $\epsilon$ scaled by $1/\|v\|$ subtracts two nearly equal gradients, which half precision handles badly. If finite differences match the exact correction in both precisions, we report that and drop the AD-engineering contribution, keeping only the diagnostic.

Why not skip gradient search and rank latency-feasible architectures with a zero-cost proxy? That is nearly free. However, EZNAS reports that proxy rankings degrade among the top 10% of models, which is exactly where budget-constrained selection operates. The proxy baseline measures whether this matters in practice.

Proposed Experiments

The primary metric is accuracy regret against the ground-truth optimal feasible architecture. We report it over a sweep of latency budgets on all six HW-NAS-Bench devices, for CIFAR-10, CIFAR-100 and ImageNet-16-120, with at least five seeds each. Secondary metrics are the feasibility rate, search wall-clock time and peak GPU memory, and the trajectory of softmax mass on parameter-free operations.

Two checks are decisive. First, the regret gap between first- and second-order search should widen as the budget tightens. If it stays flat, the shared-bias mechanism is wrong. Second, exact correction should match or beat finite differences in FP32 and clearly beat them in FP16, at no more than the cost of one extra backward pass.

A transfer check repeats the best configuration on NATS-Bench against ConNAS's reported numbers. A scale check runs a single search in the FBNet macro-space using HW-NAS-Bench latency. There the reference point is FBNet-B's reported 74.1% ImageNet top-1 at 23.1 ms on a Samsung S8. That device and space pairing is not identical to ours, so this comparison is indicative only.