  Search spaces hallmark the advancement of Neural Architecture Search (NAS).
Large and complex search spaces with versatile building operators and
structures provide more opportunities to brew promising architectures, yet pose
severe challenges on efficient exploration and exploitation. Subsequently,
several search space shrinkage methods optimize by selecting a single
sub-region that contains some well-performing networks. Small performance and
efficiency gains are observed with these methods but such techniques leave room
for significantly improved search performance and are ineffective at retaining
architectural diversity. We propose LISSNAS, an automated algorithm that
shrinks a large space into a diverse, small search space with SOTA search
performance. Our approach leverages locality, the relationship between
structural and performance similarity, to efficiently extract many pockets of
well-performing networks. We showcase our method on an array of search spaces
spanning various sizes and datasets. We accentuate the effectiveness of our
shrunk spaces when used in one-shot search by achieving the best Top-1 accuracy
in two different search spaces. Our method achieves a SOTA Top-1 accuracy of
77.6\% in ImageNet under mobile constraints, best-in-class Kendal-Tau,
architectural diversity, and search space size.
