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

• URL: http://arxiv.org/abs/2603.22966v1
• Date: Tue, 24 Mar 2026 09:00:07 GMT
• Title: Set-Valued Prediction for Large Language Models with Feasibility-Aware Coverage Guarantees
• Abstract summary: We propose a principled framework for set-valued prediction.<n>We show that, given the finite-sampling nature of LLM generation, coverage is not always achievable.<n>We then develop a data-driven calibration procedure that constructs prediction sets from sampled responses.
• Score: 11.874705280173387
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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.

Related papers

• Consistent but Miscalibrated: Evaluating LLM Limitations for Risk Communication in Natural Language [15.221434185896541]
  We evaluate whether nine LLMs meet requirements within a two-stage prediction pipeline.<n>We simulate predictions from an upstream model by taking samples from a Beta distribution parameterized by its mode and prior sample size.<n>We find that LLMs are generally consistent but miscalibrated, with substantially weaker performance on uncertainty than on likelihood tasks.
  arXiv  Detail & Related papers  (2026-07-04T13:57:21Z)
• Uncertainty Quantification for LLM-based Code Generation [18.240828221520257]
  We propose an approach RisCoSet that leverages multiple hypothesis testing to construct risk-controlling predictions for code generation.<n>Our method can significantly reduce the code removal by up to 24.5%, at the same level of risk.
  arXiv  Detail & Related papers  (2026-05-12T14:40:29Z)
• Adaptive Conformal Prediction for Improving Factuality of Generations by Large Language Models [86.8650252164764]
  Large language models (LLMs) are prone to generating factually incorrect outputs.<n>We propose an adaptive conformal prediction approach that extends conformal score transformation methods to LLMs.<n>This enables prompt-dependent calibration, retaining marginal coverage guarantees while improving conditional coverage.
  arXiv  Detail & Related papers  (2026-04-15T15:35:42Z)
• BEAVER: An Efficient Deterministic LLM Verifier [11.949243456810263]
  We present BEAVER, the first practical framework for computing deterministic, sound probability bounds on large language models.<n>We formalize the verification problem, prove soundness of our approach, and evaluate BEAVER on correctness verification, privacy verification and secure code generation tasks.
  arXiv  Detail & Related papers  (2025-12-05T05:34:06Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering [55.15192437680943]
  Generative models lack rigorous statistical guarantees for their outputs.<n>We propose a sequential conformal prediction method producing prediction sets that satisfy a rigorous statistical guarantee.<n>This guarantee states that with high probability, the prediction sets contain at least one admissible (or valid) example.
  arXiv  Detail & Related papers  (2024-10-02T15:26:52Z)
• Quantifying Prediction Consistency Under Fine-Tuning Multiplicity in Tabular LLMs [10.494477811252034]
  Fine-tuning multiplicity can arise in Tabular LLMs on classification tasks.<n>Our work formalizes this unique challenge of fine-tuning multiplicity in Tabular LLMs.<n>We propose a novel measure to quantify consistency of individual predictions without expensive model retraining.
  arXiv  Detail & Related papers  (2024-07-04T22:22:09Z)
• Cycles of Thought: Measuring LLM Confidence through Stable Explanations [53.15438489398938]
  Large language models (LLMs) can reach and even surpass human-level accuracy on a variety of benchmarks, but their overconfidence in incorrect responses is still a well-documented failure mode. We propose a framework for measuring an LLM's uncertainty with respect to the distribution of generated explanations for an answer.
  arXiv  Detail & Related papers  (2024-06-05T16:35:30Z)
• Self-Evaluation Improves Selective Generation in Large Language Models [54.003992911447696]
  We reformulate open-ended generation tasks into token-level prediction tasks. We instruct an LLM to self-evaluate its answers. We benchmark a range of scoring methods based on self-evaluation.
  arXiv  Detail & Related papers  (2023-12-14T19:09:22Z)
• Conformal Language Modeling [61.94417935386489]
  We propose a novel approach to conformal prediction for generative language models (LMs) Standard conformal prediction produces prediction sets with rigorous, statistical guarantees. We demonstrate the promise of our approach on multiple tasks in open-domain question answering, text summarization, and radiology report generation.
  arXiv  Detail & Related papers  (2023-06-16T21:55:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.