In machine learning and deep learning, uncertainty quantification helps to accurately assess a model’s confidence in its predictions, enabling the rejection of uncertain outcomes in safety-critical applications. However, in scenarios involving AI-assisted decision-making, proposing multiple plausible decisions can be more beneficial than either not making any decisions or risking incorrect ones. Set-valued classification is a relaxation of standard multiclass classification where, in cases of uncertainty, the classifier returns a set of potential labels instead of a single label. Current methods for set-valued classification often suffer from high computational complexity or fail to adequately quantify uncertainty. In this paper, we introduce a novel, computationally efficient approach to set-valued classification leveraging evidential deep learning and subjective logic, explicitly providing a measure of classification uncertainty. Our method employs a dual-head architecture: one head conducts multiclass evidential classification, while the other suggests candidate label sets when uncertainty is high. The proposed approach has linear worst-case computational complexity with respect to the number of classes. Extensive evaluation on several benchmark datasets demonstrates that our method showcases comparable performance to baseline set-valued methods, while being up to 23 times faster at inference on the benchmark datasets.