Search Space Pruning

This method eliminates architectures that violate specific hardware limitations before they are evaluated. Constraints are defined as hard bounds on metrics like peak memory usage, latency, or energy consumption. A hardware cost model—often a lookup table or a small predictor—estimates these metrics for a candidate. Architectures exceeding the budget are pruned from the search space. For Microcontroller NAS (MCU-NAS), this is essential to ensure models fit within kilobyte-scale RAM and microjoule energy budgets.

This strategy prunes candidate architectures during their training or evaluation phase if their intermediate performance indicates they are unlikely to be optimal. Common techniques include:

• Low-fidelity evaluation: Training candidates for only a few epochs to quickly rank them.
• Zero-cost proxies: Using metrics like gradient norm or synaptic saliency computed from the network's initial state to predict final accuracy without any training.
• Learning curve extrapolation: Halting the training of architectures whose accuracy progression lags behind others. This prevents wasting computational resources on poor candidates.

This approach prunes at the granular level of the search space definition itself. It reduces the set of allowable operations (e.g., removing large 5x5 convolutions in favor of 3x3 or depthwise convolutions) and connectivity patterns (e.g., limiting skip connections or layer depth). This is often informed by hardware-aware principles: for example, pruning operations known to be inefficient on a target Neural Processing Unit. It creates a smaller, more hardware-efficient search space from the outset.

Central to One-Shot NAS methods, this technique uses a single, over-parameterized supernet. Pruning occurs by evaluating sub-networks (paths) within this supernet and pruning away poorly performing edges or operations. In Differentiable Architecture Search (DARTS), the continuous architecture parameters are optimized via gradient descent, and operations with near-zero parameters are effectively pruned. The Once-For-All (OFA) method further extends this by training a supernet once, then pruning it to extract many efficient sub-networks for different hardware targets.

In Evolutionary NAS and Reinforcement Learning NAS (RL-NAS), pruning is an inherent part of the search strategy's selection pressure. The population in evolutionary algorithms is pruned by removing the least-fit architectures each generation. In RL-NAS, the controller's policy is trained to avoid generating architectures that historically received low rewards. These methods perform iterative pruning, where the search space is dynamically refined based on cumulative search experience.

Used in Multi-Objective Neural Architecture Search, this method prunes architectures that are Pareto-dominated. An architecture is dominated if another exists that is better in at least one objective (e.g., accuracy, latency) and no worse in all others. The search maintains only the set of non-dominated architectures, which form the Pareto frontier. This focuses the search on optimal trade-off points and prunes away sub-optimal compromises, efficiently navigating the trade-off between competing constraints like accuracy and model size.

The search space is the foundational set of all possible neural network architectures a NAS algorithm can consider. It is defined by parameters such as:

• Layer types (e.g., convolution, depthwise convolution, pooling)
• Connectivity patterns (e.g., residual blocks, dense connections)
• Hyperparameters like kernel size and channel count. For TinyML, the search space is explicitly constrained by hardware limits (e.g., maximum FLOPs, RAM footprint) before search begins, making pruning a critical first step.

The search strategy is the core algorithm that navigates the search space to find high-performing architectures. Common strategies include:

• Reinforcement Learning (RL-NAS): A controller network learns to generate architectures.
• Evolutionary Algorithms: A population of architectures evolves via mutation and crossover.
• Gradient-Based Methods (e.g., DARTS): Architecture parameters are optimized via gradient descent. Pruning directly aids these strategies by removing invalid or poor-performing regions of the search space, allowing the algorithm to focus its computational budget on promising candidates.

A hardware cost model is a predictive function that estimates the real-world efficiency metrics of a candidate neural network on target hardware. It is essential for pruning. Models can be:

• Analytical: Using pre-characterized lookup tables for operator latency and memory.
• Learned: A small neural network trained to predict latency or energy from an architecture description. During search space pruning, these models are used to immediately discard architectures that violate hard constraints like maximum SRAM usage or allowable inference latency on a microcontroller.

A supernet is an over-parameterized neural network that embeds all possible operations and pathways defined by the search space. Weight sharing is the technique of training this single supernet, allowing the performance of many sub-architectures to be estimated without individual training. Pruning is often applied to the supernet's structure itself. For example, operations with near-zero architectural weights in differentiable NAS (DARTS) can be pruned, effectively removing them from the continuous search space and simplifying the final discrete architecture selection.

Multi-Objective NAS seeks architectures that optimally balance competing goals, such as accuracy, latency, and model size. The output is a Pareto frontier of solutions where no objective can be improved without degrading another. Pruning is a key enabler. By first eliminating architectures that fail minimum thresholds on any single objective (e.g., accuracy below a baseline, latency above a limit), the search focuses on the feasible region where meaningful trade-offs exist, making multi-objective optimization computationally tractable.

Zero-cost proxies are metrics that estimate the potential performance of a neural network architecture using only its initialization state, requiring no training. Examples include gradient-based measures like grad_norm or snip. These proxies are a powerful tool for pruning at scale. In large search spaces, billions of candidate architectures can be ranked in seconds using zero-cost proxies. The bottom-performing fraction can be pruned away, allowing more expensive evaluation methods (like supernet sampling) to be focused on the top-ranked candidates.