🤖 machine learning

Searching on a Budget: HW-NAS with 10 Latency Probes

This paper proposes a two-stage hardware-aware NAS framework that trains a controller on synthetic devices using training-free accuracy proxies, enabling it to efficiently adapt to unseen target devices at test-time by searching for latency-efficient architectures with only a few high-fidelity latency probes.

Original authors: Francesco Capuano, Gabriele Tiboni, Niccolò Cavagnero, Giuseppe Averta

Published 2026-05-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Francesco Capuano, Gabriele Tiboni, Niccolò Cavagnero, Giuseppe Averta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to design the perfect recipe for a dish. You have two goals: the dish must taste amazing (high accuracy), but it also must be cooked quickly enough to serve a hungry crowd before they leave (low latency/energy).

Usually, when chefs (AI researchers) design these recipes for specific kitchens (hardware devices like phones or robots), they face a big problem. They can't just guess how long a dish will take to cook in a new kitchen without actually trying it. But actually cooking every single variation of the recipe is slow, expensive, and risky.

Here is how the authors of this paper solved that problem, using a simple two-step strategy:

The Problem: The "Guessing Game" is Risky

Most current methods try to predict how long a dish will take to cook using a "recipe book" (analytical approximations) or a "fortune teller" (a machine learning predictor).

The Risk: If your fortune teller is wrong, you might promise the crowd a 5-minute meal, but it actually takes 20 minutes. In critical situations (like a robot needing to react instantly), this error is unacceptable.
The Cost: To make the fortune teller accurate, you often have to cook hundreds of test dishes first, which takes a lot of time and money.

The Solution: The "Traveling Chef" with a Magic Map

The authors propose a new way to find the perfect recipe that only requires tasting 10 dishes in the new kitchen. They call this a "two-stage" approach.

Stage 1: Training in a "Dream Kitchen" (Synthetic Devices)

Instead of trying to learn the rules of one specific kitchen, the chef trains in a simulated, dream kitchen where the rules change randomly every day.

The Analogy: Imagine the chef practices in a kitchen where the stove speed, oven temperature, and knife sharpness change randomly every time they cook. One day the stove is super fast; the next, it's slow.
The Goal: By practicing in this chaotic, changing environment, the chef learns a general skill: "How to adjust my recipe based on how the equipment feels right now." They don't memorize one specific stove; they learn how to adapt to any stove.
The Shortcut: To save time during this training, they don't actually cook the full dish to taste it. They use a "quick taste test" (a training-free proxy) that estimates if the recipe would taste good without spending hours cooking it.

Stage 2: The Real Kitchen (Deployment)

Now, the chef goes to a real, specific kitchen (like an iPhone or a robot) to cook for real.

The Strategy: The chef doesn't guess. They only cook 10 specific dishes (candidate networks) and time them exactly.
The Adaptation: Because the chef spent years training in the "Dream Kitchen" where conditions changed constantly, they are already an expert at reading the room. They look at the timing of those first few dishes, realize, "Ah, this stove is slower than I thought," and immediately adjust the next 9 dishes to fit that specific stove.
The Result: They pick the best dish from those 10 real tests. No guessing, no fortune tellers, just real data.

Why This is Better (The Results)

The paper tested this against other methods (like the "fortune teller" approach) on 18 different devices and even a real iPhone 13.

The Fortune Teller: Tried to predict the cooking time for hundreds of dishes based on a few samples. It often got the time wrong, leading to dishes that were slower than promised.
The "Dream Kitchen" Chef: Only cooked 10 dishes but measured them perfectly.
The Outcome: The "Dream Kitchen" method found recipes that were 8.7% faster in real-world tests than the prediction-based methods.

The Big Takeaway

If you have a very limited budget for testing (you can only check the clock 10 times), it is better to measure a few things accurately than to guess the outcome of many things.

By training a "smart agent" on a wide variety of fake, random scenarios first, it becomes so good at adapting that it can walk into a brand-new, unknown kitchen, taste just 10 dishes, and instantly know exactly how to cook the perfect meal for that specific environment.

In short: Don't try to predict the future; train your AI to be a master of adaptation, then let it make a few real-world checks to get the job done right.

Technical Summary: Searching on a Budget: HW-NAS with 10 Latency Probes

Problem Statement
Hardware-aware Neural Architecture Search (HW-NAS) aims to automate the design of Deep Neural Networks (DNNs) that balance task performance (e.g., accuracy) with hardware constraints (e.g., latency) for resource-constrained devices. Existing approaches face a critical trade-off:

Real-world measurements: Directly compiling and benchmarking candidate networks on target devices provides accurate latency data but is computationally expensive and time-consuming, especially when the target device changes.
Approximations: Analytical look-up tables (LUTs) or learned latency predictors reduce search costs but introduce estimation errors. In risk-sensitive applications (e.g., robotics), these errors can lead to violations of latency bounds, rendering the designs unreliable.

Furthermore, most HW-NAS methods are tailored to a single target device, requiring a complete re-search whenever the deployment hardware changes. There is a need for a multi-device HW-NAS strategy that minimizes the number of expensive, real-world latency probes while avoiding the inaccuracies of predictive models.

Methodology
The authors propose a two-stage framework that shifts the complexity from the deployment phase to a pre-training phase, enabling adaptation to unseen hardware with minimal interaction.

Meta-Training on Synthetic Devices (Stage 1):
- Objective: Train a Reinforcement Learning (RL) controller to generalize across diverse hardware profiles without accessing the specific target device.
- Domain Randomization: Instead of training on a single device, the controller is exposed to a distribution of "synthetic" devices. These are generated by sampling Gaussian latency models for each operation based on data from 18 different devices in the HW-NAS-Bench.
- Training-Free Proxies: To avoid the prohibitive cost of training full networks during RL, the controller is supervised using training-free accuracy proxies (specifically $p_{FreeREA}$ , a combination of NASWOT, LogSynflow, and SkipScore).
- Reward Function: The agent maximizes a reward combining the training-free accuracy proxy and a normalized latency term, allowing it to learn the trade-off between performance and efficiency across varying latency landscapes.
Zero-Shot Deployment with Direct Probes (Stage 2):
- Adaptation: The pre-trained controller is frozen and deployed on a new, unseen target device.
- Direct Measurement: The controller interacts with the target device by querying a very small number of candidate architectures (e.g., 10 probes). For each query, it compiles the network and measures the actual post-compilation latency.
- State History: The measured latency is normalized and appended to the state history. The controller uses this feedback to condition its next action (modifying the architecture), effectively learning the specific latency profile of the target device through direct observation rather than prediction.
- Selection: The final architecture is selected from the set of measured candidates based on the best observed trade-off, requiring no further training or prediction fitting.

Key Contributions

Randomized RL Training: A procedure that produces a controller capable of interacting directly with diverse devices at test time by training on a distribution of synthetic latency profiles.
Elimination of Predictors: The method entirely discards analytical approximations and learned latency predictors. Instead, it relies on direct on-device measurements of as few as 10 candidate networks, made feasible by the prior knowledge transferred from the synthetic training phase.
Training-Free Evaluation: The integration of training-free metrics for RL-based NAS, enabling rapid candidate scoring without the cost of full network training.

Experimental Results
The method was evaluated on the NATS-Bench search space for CIFAR-10, using data from 18 devices and validated on a real-world iPhone 13 mini.

Performance vs. Predictors: Under a strict budget of 10 target-device measurements, the proposed method achieved a median latency percentile of 1.65, significantly outperforming random search (30.16) and a HELP-style latency predictor baseline (4.51).
Real-World Validation: On an iPhone 13 mini, with a total budget of 20 measurements (split between normalization and search), the proposed controller achieved a median latency of 0.2261 ms, compared to 0.2477 ms for the HELP-EA baseline. This represents an 8.7% reduction in measured median latency.
Predictor Failure Analysis: The study highlighted that predictor-based methods (like HELP) often selected architectures that were slower than predicted in practice (measured latency was slower than predicted in 9/10 seeds), whereas the proposed method's reliance on direct measurement ensured the selected architecture's latency was known and verified.
Transferability: The controller successfully adapted to held-out devices (e.g., edgegpu, fpga, pixel3, raspi4) using a leave-one-device-out protocol, demonstrating effective transfer without retraining.

Significance and Claims
The paper argues that in scenarios where access to target hardware is scarce but measurements must be trustworthy (risk-averse deployment), it is preferable to measure a few carefully chosen architectures directly rather than predicting many unmeasured ones.

Reliability: By avoiding latency predictors, the method eliminates the risk of estimation errors invalidating latency guarantees.
Efficiency: The approach reduces the total deployment cost ( $C$ ) by bounding the number of ground-truth probes ( $|N|$ ) rather than reducing the per-probe cost ( $c$ ) via approximation.
Practicality: The results suggest that a pre-trained RL controller can effectively "learn" the latency characteristics of a new device through a handful of direct probes, making direct measurement a viable and superior alternative to approximation in low-budget, high-stakes HW-NAS scenarios.

Limitations
The authors acknowledge that the study is currently limited to the NATS-Bench topology search space and that the design of the synthetic device distribution ( $\Xi$ ) requires further exploration to ensure optimal transfer. Additionally, the current focus is primarily on latency; future work is needed to extend the framework to multi-objective constraints including memory and energy.