# Set-Valued Prediction for Large Language Models with Feasibility-Aware Coverage Guarantees

arXiv: https://arxiv.org/abs/2603.22966 · HTML: https://mlsanity.com/paper/2603.22966/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 52 references that are in the map.
- First posted on arXiv 24 Mar 2026.

## Builds on (most cited first, 30 of 32)

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension](https://mlsanity.com/paper/1705.03551/) (2017)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [What Disease does this Patient Have? A Large-scale Open Domain Question Answering Dataset from Medical Exams](https://mlsanity.com/paper/2009.13081/) (2020)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [CoQA: A Conversational Question Answering Challenge](https://mlsanity.com/paper/1808.07042/) (2018)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Conformal Prediction with Large Language Models for Multi-Choice Question Answering](https://mlsanity.com/paper/2305.18404/) (2023)
- [Language Models with Conformal Factuality Guarantees](https://mlsanity.com/paper/2402.10978/) (2024)
- [Benchmarking LLMs via Uncertainty Quantification](https://mlsanity.com/paper/2401.12794/) (2024)
- [Can Large Language Models Faithfully Express Their Intrinsic Uncertainty in Words?](https://mlsanity.com/paper/2405.16908/) (2024)
- [PRISM: Self-Pruning Intrinsic Selection Method for Training-Free Multimodal Data Selection](https://mlsanity.com/paper/2502.12119/) (2025)
- [LLaVA Steering: Visual Instruction Tuning with 500x Fewer Parameters through Modality Linear Representation-Steering](https://mlsanity.com/paper/2412.12359/) (2024)
- [CoT-Kinetics: A Theoretical Modeling Assessing LRM Reasoning Process](https://mlsanity.com/paper/2505.13408/) (2025)
- [ASCD: Attention-Steerable Contrastive Decoding for Reducing Hallucination in MLLM](https://mlsanity.com/paper/2506.14766/) (2025)
- [Backdoor Cleaning without External Guidance in MLLM Fine-tuning](https://mlsanity.com/paper/2505.16916/) (2025)
- [Uncertainty-Aware Evaluation for Vision-Language Models](https://mlsanity.com/paper/2402.14418/) (2024)
- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees](https://mlsanity.com/paper/2506.20178/) (2025)
- [SPOT! Revisiting Video-Language Models for Event Understanding](https://mlsanity.com/paper/2311.12919/) (2023)
- [Sample then Identify: A General Framework for Risk Control and Assessment in Multimodal Large Language Models](https://mlsanity.com/paper/2410.08174/) (2024)
- [Addressing Uncertainty in LLMs to Enhance Reliability in Generative AI](https://mlsanity.com/paper/2411.02381/) (2024)
- [Can Visual Input Be Compressed? A Visual Token Compression Benchmark for Large Multimodal Models](https://mlsanity.com/paper/2511.02650/) (2025)
- [Beyond Magic Words: Sharpness-Aware Prompt Evolving for Robust Large Language Models with TARE](https://mlsanity.com/paper/2509.24130/) (2025)
- [Reinforcement Mid-Training](https://mlsanity.com/paper/2509.24375/) (2025)

## Built on by (most cited first, 4 of 4)

- [BalanceRAG: Joint Risk Calibration for Cascaded Retrieval-Augmented Generation](https://mlsanity.com/paper/2605.20084/) (2026)
- [MiRD: Reliable Set-Valued Prediction for Open-Ended Question Answering via Miscoverage Risk Decomposition](https://mlsanity.com/paper/2605.27091/) (2026)
- [Uncertainty-Aware Abstention in Large Language Models with Provable Alignment Guarantees](https://mlsanity.com/paper/2607.04430/) (2026)
- [Asymptotic Risk Calibration for Selective Question Answering](https://mlsanity.com/paper/2608.12008/) (2026)

## Abstract (arXiv)

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 satisfied. Building on this insight, we then develop a data-driven calibration procedure that constructs prediction sets from sampled responses by estimating a rigorous threshold, ensuring that the resulting set contains a correct answer with a desired probability whenever the target risk level is feasible. Extensive experiments on six language generation tasks with five LLMs demonstrate both the statistical validity and the predictive efficiency of our framework.