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

Paper: 2603.22966 Authors: Ye Li, Anqi Hu, Yuanchang Ye, Shiyan Tong, Zhiyuan Wang, Bo Fu Categories: cs.CL

Abstract

Conventional LLM usage reports the most likely generation (MLG) as a point prediction, which underestimates the model’s true capability. Even when the top-ranked response is incorrect, valid answers may exist in the broader output space accessible through repeated sampling. This paper proposes a framework for set-valued prediction with feasibility-aware coverage guarantees. The key insight is that coverage is not always achievable — even with multiple samplings, LLMs may fail to yield an acceptable response. The authors establish the Minimum Achievable Risk Level (MRL), below which statistical coverage cannot be satisfied, and develop a data-driven calibration procedure that constructs prediction sets from sampled responses ensuring the correct answer is included with desired probability when feasible. The framework is tested on 6 language generation tasks with 5 LLMs.

Key Contributions

• Minimum Achievable Risk Level (MRL): Formally defines the threshold below which coverage guarantees are impossible, addressing a fundamental gap in existing conformal prediction methods that assume valid answers always appear in sampled sets
• Feasibility-aware coverage framework: Extends split conformal prediction to open-ended text generation, providing guarantees only when they are actually achievable
• Multi-view reliability scoring: Combines TokenSAR uncertainty quantification with semantic consensus to score candidate responses from multiple perspectives
• Learn-Then-Test (LTT) calibration: Data-driven procedure for constructing prediction sets that provably contain correct answers at the desired confidence level when feasible
• Broad empirical validation: Tested across 6 language generation tasks and 5 LLMs, demonstrating practical effectiveness

Methodology

The framework operates in several stages:

1. Sampling: Generate multiple candidate responses from the LLM through repeated sampling
2. Scoring: Evaluate each candidate using a multi-view reliability score combining TokenSAR (token-level sequence-aware uncertainty) and semantic consensus among responses
3. MRL estimation: Compute the Minimum Achievable Risk Level to determine whether coverage at the target level is feasible for a given query
4. Calibration: Apply Learn-Then-Test calibration on held-out data to select a threshold that determines which candidates enter the prediction set
5. Prediction set construction: Include all candidates whose reliability score exceeds the calibrated threshold

The approach is grounded in split conformal prediction but critically extends it by recognizing that for open-ended generation, the standard assumption — that a valid answer will always appear among samples — does not hold.

Results

• The framework successfully identifies when coverage is achievable versus when LLMs fundamentally cannot produce acceptable responses
• Prediction sets maintain valid coverage rates at or above the target level across all 6 tasks when the MRL condition is satisfied
• Multi-view scoring (TokenSAR + semantic consensus) outperforms single-metric approaches in constructing tighter prediction sets
• The method generalizes across 5 different LLMs without requiring architecture-specific modifications
• Addresses a practical gap: existing conformal methods often produce misleadingly large or vacuous prediction sets when the model simply cannot solve the task

Takeaways

• Point predictions from LLMs (taking only the top response) systematically underestimate model capability — set-valued prediction reveals valid answers that exist in the broader sampling space
• Not all coverage targets are achievable: the MRL concept is essential for honest uncertainty quantification in LLMs
• Combining token-level uncertainty with semantic consensus provides a richer signal for response quality than either metric alone
• The feasibility-aware approach prevents the false confidence that arises when conformal methods are applied without checking whether their assumptions hold
• This work bridges conformal prediction theory and practical LLM deployment, offering a principled way to report “here are the plausible answers” instead of a single best guess