When designing neural networks automatically, the most intuitive approach is often a greedy one: start with a base model and make sequential, incremental improvements. Whether adding a layer, expanding a channel width, or pruning an underperforming filter, greedy strategies evaluate immediate performance gains to decide the next step.
This approach is computationally appealing, but it harbors a fundamental flaw. The search space of neural architectures is highly non-convex and non-monotonic. By optimizing exclusively for immediate rewards, greedy search algorithms frequently become trapped in local optima—design dead-ends where no single incremental change yields a benefit, even though a vastly superior configuration lies just a few steps away.
An emerging body of research explores why these local optima occur, how greedy assumptions break down, and how we can design search algorithms that look beyond immediate horizons.
The Non-Monotonic Landscape of Architecture Search
To understand why greedy search fails, we must look at the geometry of the architectural search space. A greedy algorithm assumes that the path to a globally optimal network is a smooth, upward climb. However, as Huang et al. note, gradient-based and greedy optimization strategies are highly susceptible to converging on local optima because the underlying landscape of architectural parameters is rugged and non-convex.
This ruggedness manifests as a lack of immediate returns for necessary structural changes. For example, in Simple and efficient architecture search for Convolutional Neural Networks, Elsken et al. observe that greedy hillclimbing strategies stall precisely because the search encounters plateaus where no single incremental modification provides an immediate accuracy boost. To escape these plateaus, an algorithm must take multiple, non-improving steps in tandem—a maneuver that greedy selection explicitly forbids.
Greedy Path: [Current State] ---> (Drop in Performance) ---> [Blocked from Global Optimum]
Optimal Path: [Current State] ---> (Temporary Dip) ---------> [Globally Superior Configuration]
This problem is compounded in complex, multi-modal, or multi-task networks. When searching for optimal cross-modal connection topologies, Karazija et al. show that iterative methods prioritizing immediate performance gains miss superior global topologies. Similarly, Cui et al. point out that while gradient-based search methods are fast, they fail to explore the broader architectural space effectively, trapping the network in localized configurations.
The Breakdown of Greedy Assumptions
Greedy architecture search relies on two core assumptions: that an optimal larger model must contain an optimal smaller model as a sub-graph, and that an operation's current performance accurately reflects its ultimate potential. Both assumptions are routinely violated in practice.
The Sub-graph Fallacy
In Efficient Transfer Learning via Joint Adaptation of Network Architecture and Weight, Sun et al. explicitly challenge the incremental expansion paradigm. They argue that assuming an optimal large model is simply an extension of an optimal small model prioritizes short-term computational efficiency over global optimality. A network optimized for a small scale may have a completely different ideal topology than one optimized for a large scale.
Premature Pruning
When algorithms prune candidate operations or sub-networks early in the search to save compute, they risk cutting off branches that would eventually outperform the rest. In Sequential Greedy Architecture Search, Li et al. demonstrate that pruning candidate operations based on immediate performance overlooks complex architectural patterns that require sub-optimal intermediate choices.
This risk is highly visible in progressive search strategies. Flynn et al. show that greedy pruning strategies prematurely discard promising network branches if a child node exhibits lower intermediate performance than its parent, failing to realize that some architectures require temporary performance degradation or additional layers to reach their full potential. Similarly, in the context of few-shot NAS, Li et al. find that early greedy pruning of sub-supernets discards spaces that would have performed significantly better after further training or when combined with other components.
This sub-optimality extends to network compression and filter pruning. Lee et al. observe that relying on greedy search to select pruned sub-networks results in sub-optimal configurations, suggesting that search heuristics must be coupled with loss-landscape awareness to navigate the space effectively.
Structural Blindspots: Width, Depth, and Connectivity
Greedy algorithms struggle when an architectural change requires coordinated adjustments across multiple dimensions.
Consider network width optimization. In AOWS: Adaptive and Optimal Network Width Search With Latency Constraints, Berman et al. explain that sequential, locally-best decisions prevent the discovery of globally optimal configurations. An optimal trade-off between latency and accuracy might require shrinking one layer drastically to allow a massive, highly informative expansion in another—a choice a sequential greedy algorithm will never make.
A similar blindspot occurs when expanding networks across spacetime. In Expanding Architectures for Efficient Video Recognition, Feichtenhofer notes that stepwise greedy expansion strategies prioritize immediate gains in the accuracy-to-complexity ratio. This approach can overlook superior configurations that require simultaneous, multi-axis adjustments across time, resolution, and depth.
The same limitation applies to internal wiring and dynamic growth:
- Operator Connectivity: Zhang et al. show that standard optimization algorithms prioritizing immediate performance gains fail to discover globally superior connectivity designs within network cells.
- Adaptive Depth: Dong et al. demonstrate that adaptive growth strategies relying purely on the current state of a network to trigger depth changes suffer from greedy optimization, missing out on configurations that a long-term planning strategy would secure.
Strategies for Escaping the Trap
To move past the limitations of greedy optimization, researchers have introduced several alternative search paradigms that explicitly accommodate or bypass non-improving intermediate steps.
Global and Probabilistic Optimization
Instead of making sequential local decisions, some frameworks look at the search space globally. Berman et al. combine a black-box latency model with global optimization via dynamic programming to break out of the sequential trap. Alternatively, Perez-Rua et al. replace greedy selection with probabilistic sampling, allowing the algorithm to maintain and explore candidates that do not show immediate high performance but possess long-term potential.
Open-Ended Exploration and Meta-Learning
When designing highly complex systems, such as agentic memory or self-improving code bases, the risk of design dead-ends is severe. In Learning to Continually Learn via Meta-learning Agentic Memory Designs, Xiong et al. emphasize that greedy search cannot account for the necessary but non-improving intermediate steps required to build complex system architectures.
To resolve this, Zhang et al. propose combining evolutionary open-ended exploration with empirical testing. By explicitly introducing mechanisms to explore diverse, seemingly sub-optimal architectural variations, their approach prevents the system from stalling at local optima, enabling the discovery of complex, non-obvious structural changes that drive significant performance breakthroughs.
Key Foundational Work
Simple and efficient architecture search for Convolutional Neural Networks (2018) — contributed 2 concept elements to this direction.
Search Tree Pruning for Progressive Neural Architecture Search (Student Abstract) (2020) — contributed 2 concept elements to this direction.
Automatic Inference of Cross-modal Connection Topologies for X-CNNs (2018) — contributed 1 concept elements to this direction.