Search Space (NAS)

This defines the set of primitive operations (e.g., 3x3 convolution, 5x5 depthwise convolution, max pooling, identity, zero) that can be placed at each node or layer in the computational graph. For TinyML, the search space is often constrained to hardware-efficient operators like depthwise-separable convolutions to reduce FLOPs and parameter count. The choice of operators directly impacts the model's capacity, inductive bias, and computational cost on the target microcontroller.

This component defines the permissible connections between operations or layers, governing the network's data flow. Common patterns include:

• Chain-structured: Sequential layers, common in early NAS.
• Cell-based: A directed acyclic graph (DAG) of operations within a repeating cell, enabling skip connections and multi-branch structures for efficiency.
• Macro-architecture: The high-level skeleton defining the number of cells, stages, and resolution changes. For microcontroller targets, topologies are often shallower and narrower to fit within kilobyte-scale memory budgets.

Beyond operations and connections, the search space includes key architectural hyperparameters:

• Channel/Width Search: The number of output filters for each convolutional layer. This is a primary lever for trading accuracy (more channels) against memory and compute (fewer channels).
• Kernel Size Search: Choosing filter spatial dimensions (e.g., 1x1, 3x3, 5x5). Larger kernels increase receptive field but also computational cost quadratically.
• Expansion Ratio Search (for Mobile inverted bottlenecks): The factor by which channels are expanded within a block. These dimensions are often treated as categorical or integer choices within bounded ranges.

For Hardware-Aware NAS targeting microcontrollers, the search space is explicitly parameterized by device-specific constraints:

• Memory Budget: Defines maximum peak RAM (activation memory) and flash (model weights) usage, pruning architectures that exceed it.
• Latency/Energy Targets: Incorporates hardware cost models (e.g., lookup tables, neural predictors) that estimate a candidate's inference time or energy consumption on the target MCU.
• Quantization-Aware Design: The space may include operations known to be quantization-friendly or simulate quantization noise during search (Quantization-Aware NAS). This ensures the final model is robust to 8-bit or lower precision deployment.

A critical pre-search step is pruning the theoretical space of all possible architectures to a manageable, high-potential subset. This is done by:

• Incorporating Domain Knowledge: Mandating efficient operators like depthwise convolutions.
• Enforcing Valid Connectivity: Preventing cycles or invalid tensor shape mismatches.
• Applying Hardware Filters: Immediately discarding architectures that violate hard constraints (e.g., >256KB flash). A well-designed, pruned search space dramatically improves search efficiency and the likelihood of finding a viable microcontroller-optimized model.

For a search algorithm to manipulate architectures, the search space must be encoded into a searchable representation. Common encodings include:

• String-based: A sequence of tokens representing operation and connection choices.
• Graph-based: A direct DAG representation where nodes are operations and edges are connections.
• Continuous Relaxation (e.g., DARTS): Architecture parameters are represented as continuous variables in a supernet, enabling gradient-based optimization. The choice of encoding is tightly coupled with the search strategy (e.g., RL, evolution, gradient).

Operator search is the core process of selecting the type of computational layer (or 'operation') to apply at each position in a neural network. The algorithm chooses from a predefined set of primitives.

• Common operators include standard convolution, depthwise separable convolution, pooling (max/average), identity (skip connection), and zero (no connection).
• In hardware-aware NAS, the operator set is often constrained to operations efficient on the target device, such as favoring depthwise convolutions for mobile CPUs.
• The choice directly impacts the model's representational capacity, parameter count, and inference latency.

Channel search (or width search) optimizes the number of output channels for convolutional layers, controlling the network's width. This is a key lever for balancing accuracy and efficiency.

• Searching over layer widths allows the NAS algorithm to allocate computational budget strategically, creating bottlenecks where possible and expanding capacity where needed.
• For microcontroller deployment, channel search is critical for staying within severe memory constraints, as the number of parameters and activation maps scales with the square of the channel count in standard convolutions.
• It is often parameterized as a multiplier on a base channel count (e.g., width multiplier).

Kernel size search involves selecting the spatial dimensions of convolutional filters (e.g., 1x1, 3x3, 5x5). This dimension controls the receptive field and the computational cost per layer.

• Larger kernels (e.g., 5x5) capture broader spatial contexts but require more parameters and FLOPs.
• Smaller kernels (e.g., 1x1) are used for channel mixing and dimensionality reduction with minimal cost.
• In TinyML, 3x3 kernels are most common due to their efficiency; searching may be limited to {1x1, 3x3} to avoid the quadratic cost increase of larger sizes.

Connectivity search defines how layers are connected to form the overall network topology. It moves beyond simple sequential chains to explore branched, multi-path architectures.

• This includes searching for skip connections (as in ResNet), dense connections (as in DenseNet), or more complex directed acyclic graphs (DAGs).
• The connectivity pattern dramatically influences gradient flow, feature reuse, and parameter efficiency.
• In hardware-aware search, complex connectivity can increase memory bandwidth requirements and control logic overhead on accelerators, making it a critical search dimension.

Search space pruning is the technique of reducing the size of the explorable architecture set by eliminating unlikely or invalid configurations before or during the search. This is essential for tractable NAS.

• Pruning criteria can be based on prior knowledge (e.g., removing 5x5 convolutions for MCUs), preliminary performance estimates, or hardware legality checks.
• Methods include manual pruning by domain experts and automated pruning using zero-cost proxies or early-stopping benchmarks.
• Effective pruning reduces the search complexity from an intractable space to a focused region containing high-performing, hardware-feasible models.

A cell-based search space is a common design where the NAS algorithm discovers a small, repeating computational motif (a 'cell'), which is then stacked to form the final network. This enables search scalability and transferability.

• The search operates over two cell types: a normal cell (preserving feature map dimensions) and a reduction cell (downsampling spatial resolution).
• The discovered cell is a directed acyclic graph of nodes (feature maps) and edges (searched operations).
• This approach, pioneered by NASNet, drastically reduces the search dimension and allows the discovered architecture to generalize across different dataset sizes by changing the number of cell repeats.