[2603.22966] Set-Valued Prediction for Large Language Models with Feasibility-Aware Coverage Guarantees

Computer Science > Computation and Language arXiv:2603.22966 (cs) [Submitted on 24 Mar 2026] Title:Set-Valued Prediction for Large Language Models with Feasibility-Aware Coverage Guarantees Authors:Ye Li, Anqi Hu, Yuanchang Ye, Shiyan Tong, Zhiyuan Wang, Bo Fu View a PDF of the paper titled Set-Valued Prediction for Large Language Models with Feasibility-Aware Coverage Guarantees, by Ye Li and 5 other authors View PDF HTML (experimental) Abstract:Large language models (LLMs) inherently operate over a large generation space, yet conventional usage typically reports the most likely generation (MLG) as a point prediction, which underestimates the model's capability: although the top-ranked response can be incorrect, valid answers may still exist within the broader output space and can potentially be discovered through repeated sampling. This observation motivates moving from point prediction to set-valued prediction, where the model produces a set of candidate responses rather than a single MLG. In this paper, we propose a principled framework for set-valued prediction, which provides feasibility-aware coverage guarantees. We show that, given the finite-sampling nature of LLM generation, coverage is not always achievable: even with multiple samplings, LLMs may fail to yield an acceptable response for certain questions within the sampled candidate set. To address this, we establish a minimum achievable risk level (MRL), below which statistical coverage guarantees cannot be sat...