Budgeted Fixed-Proxy Search for Zero-Shot NAS via Evaluation-Efficient Memetic NAS

Zero-cost proxies reduce the cost of neural architecture search (NAS), the automated design of neural network architectures, by scoring untrained candidate architectures without full training. Although this makes individual evaluations inexpensive, zero-shot NAS still operates over a large architecture space and therefore depends not only on proxy quality but also on how proxy evaluations are allocated under a limited budget. Despite this role, many zero-shot NAS studies have primarily focused on proxy design, while search over large architecture spaces has often relied on standard evolutionary procedures with limited attention to fixed-proxy budget allocation. In this study, we propose Evaluation-Efficient Memetic NAS (EEM-NAS), a memetic framework for budgeted fixed-proxy zero-shot NAS. EEM-NAS combines bounded one-flip local search, rank-plus-distance target selection, refined-candidate reinsertion, and entropy-guided mutation within one fixed-proxy search process. These components exploit promising candidates, reduce redundant refinement, preserve useful local improvements, and maintain population-level exploration under the same proxy-evaluation budget. On NAS-Bench-201 TSS with eight zero-cost proxies, three datasets, and four fixed-proxy baselines under a budget of 100 proxy evaluations per run, EEM-NAS records 93 wins, three ties, and zero losses over the 96 proxy–dataset–baseline comparisons on final proxy score under paired statistical testing. Because a higher proxy score is informative of final accuracy only when the proxy ranks architectures well, we also report the macro-average test accuracy of the top-10 architectures found in each run, where EEM-NAS achieves the highest macro-average top-10 accuracy among the compared methods on the three most rank-aligned proxies.