Hyperspectral image segmentation is an emerging area with numerous applications, including agriculture, forestry, environment monitoring, and remote sensing. This paper proposes a new neural architecture search algorithm, named AdaptorNAS, for hyperspectral image segmentation. AdaptorNAS aims to design the optimum decoder for any given encoder. In our approach, the search space of AdaptorNAS is a large deep neural network (DNN), and the optimal decoder is derived by pruning the large DNN via a perturbation-based pruning strategy. Verified on three popular encoders, i.e., ResNet-34, MobileNet-V2, and EfficientNet-B2, AdaptorNAS can design high-speed decoders that are significantly better than six common hand-crafted decoders. Additionally, with the EfficientNet-B2 encoder, AdaptorNAS (mIoU of 92.47% and mDice of 95.15%) outperforms the state-of-the-art NAS algorithms and hand-crafted network architectures on the hyperspectral image segmentation task. We also introduce a new hyperspectral image dataset of 4,625 images for objective evaluation in hyperspectral image segmentation research.