Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models
Authors: Sima Noorani
Shayan Kiyani
George J. Pappas
Hamed Hassani
Venue: NeurIPS 2025 poster ()
Keywords: Conformal prediction
Uncertainty quantification
Primary area: probabilistic_methods

Abstract: Uncertainty quantification (UQ) is essential for safe deployment of generative AI models such as large language models (LLMs), especially in high-stakes applications. Conformal prediction (CP) offers a principled uncertainty quantification framework, but classical methods focus on regression and classification, relying on geometric distances or softmax scores--tools that presuppose structured outputs. We depart from this paradigm by studying CP in a query-only setting, where prediction sets must be constructed solely from finite queries to a black-box generative model, introducing a new trade-off between coverage, test-time query budget, and informativeness. We introduce **Conformal Prediction with Query Oracle** (CPQ), a framework characterizing the optimal interplay between these objectives. Our finite-sample algorithm is built on two core principles: one governs the optimal query policy, and the other defines the optimal mapping from queried samples to prediction sets. Remarkably, both are rooted in the classical **missing mass problem** in statistics. Specifically, the optimal query policy depends on the rate of decay--or the derivative--of the missing mass, for which we develop a novel estimator. Meanwhile, the optimal mapping hinges on the missing mass itself, which we estimate using Good-Turing estimators. We then turn our focus to implementing our method for language models, particularly in open-ended LLM tasks involving question answering, multi-step reasoning, and structured information extraction, where outputs are vast, variable, and often under-specified. Fine-grained experiments on three real-world open-ended tasks and two LLMs, show CPQ's applicability to **any black-box LLM** and highlight: (1) individual contribution of each principle to CPQ’s performance, and (2) CPQ's ability to yield significantly more informative prediction sets than existing conformal methods for language uncertainty quantification.

Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models
Sima Noorani* University of Pennsylvania nooranis@seas upenn. edu
Shayan Kiyani* University of Pennsylvania shayankOseas upenn. edu
George Pappas University Pennsylvania pappasgdseas. upenn. edu
Hamed Hassani University of Pennsylvania hassani @seas upenn edu
Abstract
Uncertainty quantification (UQ) essential for safe deployment of generative Al models such as large language models (LLMs), especially in high-stakes appli- cations. Conformal prediction (CP) offers a principled uncertainty quantification framework, but classical methods focus regression and classification, relying on geometric distances or softmax scores-tools that presuppose structured outputs. We depart from this paradigm by studying CP in query-only setting, where pre- diction sets must be constructed solely from finite queries to a black-box generative model, introducing new trade-off between coverage, test-time query budget, and informativeness. We introduce Conformal Prediction with Query Óracle (CPQ), framework characterizing the optimal interplay between these objectives. Our finite-sample algorithm is built on two core principles: one governs the optimal query policy, and the other defines the optimal mapping from queried samples to prediction sets. Remarkably, both are rooted in the classical missing mass problem in statisties. Specifically, the optimal query policy depends on the rate of decay-or the derivative-of the missing mass, for which we develop a novel estimator. Meanwhile, the optimal mapping hinges on the missing mass itself, Turing estimators. We then turn our focus to imple-
which we estimate using Good-Turing menting our method for language models, particularly open-ended LLM tasks involving question answering, multi-step reasoning, and structured information extraction, where outputs are vast, variable, and often under-specified. Fine-grained experiments on three real-world open-ended tasks and two LLMss, show CPQ's applicability any black-box I.IM and highlight: (1) individual contribution each principle to CPQ's performance, and (2) CPQ's ability yield significantly more informative prediction sets than existing conformal methods for language uncertainty quantification.
Introduction
Generative models such as L.MSs and diffusion models are widely deployed in high-stakes applica- tions, yet they often produce unreliable outputs. These models may generate plausible but incorrect information, hallucinate facts, or exhibit inconsistency across runs [1-4]. Uncertainty quantifica- tion (UQ) is therefore essential for safe and trustworthy deployment of generative AI, enabling downstream users to detect unreliable outputs and make informed decisions under uncertainty.
Equual contribution. Correspondence to: nooranis@seas upenn. edu, shayankdseas upen. edu. We relcase our code at http://hww....oooooooian////n//e
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Conformal prediction (CP) is a statistical framework for UQ in supervised learning [5-7], where input-output pairs (X, Y) are drawn from an unknown distribution. Instead of single prediction. CP produces prediction sets calibrated to include the true label with high probability. Formally, given miscoverage level a E (0. 1). CP guarantees P(Y E ((X)) 2 1 - a. where C(X) is the prediction set for input X. This holds under minimal assumptions: CP is distribution-
and model-agnostic,, making it widely applicable. These properties have made CP a key tool in deploying ML systems in high-stakes settings. Recent work also shows that CP sets are essential for risk-sensitive decision making, where decisions must account for predictive uncertainty in a principled way [8].
CP has been extensively studied for classical tasks such as classification and regression [9-12], In these settings, uncertainty typically expressed through prediction sets of the form {y S( y) S q). where S(x, y) is a nonconformity score measuring how atypical a label y is for a given imput z, and q a calibrated threshold. In regression, S(x, y) might be yy - [(x)] where fxx is a trained model. In classification, the score is often based on softmax probabilities, such as 1 - S- (z)), where fx(x) is the predicted probability for class y. However, this approach does not directly carry over to generative modeling-stt -uuch as open-ended text unstructured space of discrete sequences. While one can define similarity metrics over text or images, the core difficulty lies not in the absence of distance, but in the fact that sets defined via these distances-sude as "all outputs within a radius of q" are typically intractable and hard to represent. In generative models like LLMs, the model does not expose a full probability distribution over the output space, but instead only provides a query oracle a mechanism for sampling one output at a time. These challenges motivate the question: Can design conformal prediction procedures that meaningfully quantify uncertainty when the model only provides samples of its output space?
ceerrationnwwerr outputs come from an immense,
Recent works have made progress toward adapting CP to query- meery-based generative models [13, 14]. However, two key challenges remain mainly unresolved. First, querying at test time is resource intensive-more queries improve output exploration but incur substantial computational cost. Second, users often seek uncertainty quantification at high coverage levels (e.g., 90%), even when the model's few-shot accuracy is much lower (e.g., 60- 70%). In such regimes, some prediction sets are necessarily non-informative effecciveel suggesting that the true output could be anything-because because the model fails to produce it within the query budget. These challenges highlight fundamental trade- off between coverage, informativeness, and test-time query cost. Our goal is to design conformal procedures that navigate this trade-off by minimizing the number of non-informaaive prediction sets while maintaining valid coverage under a limited query budget.
A central insight in addressing this challenge is recognizing that the notion of missing mass plays foundational role. When only a few outputs are sampled from a generative model-such as querying an LLM handful of times for prompt-the key question becomes: have we already seen a correct answer, or could the correct output still lie the part of the distribution we haven't 't sampled yet? This uncertainty about the correct label remaining unseen- ttee missing mass is critical in deciding both whether to keep querying and how much confidence to place in the outputs we have.
To formalize the trade-off between coverage, informativeness, and query cost, we introduce an optimization framework that jointly designs a query policy (how many queries to allocate per test point) and a set map (how to turn sampled outputs into calibrated prediction sets). Remarkably, both components connect to the classical missing mass problem in statisties (see [15-18]). The optimal query policy corresponds to controlling the rate of decrease in missing mass, while the optimal set construction relies on estimating the missing mass itself. We now summarize our main contributions:
1) We introduce novel optimization framework (Section 2) that formally captures the trade-off between coverage, informativeness, and test-time query budget in generative modeling UQ This reinterprets conformal prediction from a budgeted query perspective and defines two interacting components: the query policy and the prediction set map, which connects sampled outputs to sets.
2) We identify two key algorithmic principles that emerge from this framework. First, the optimal query policy prescribes querying each test input until the rate of decrease in missing mass falls below a threshold-that is, one should keep querying as long as an additional sample significantly reduces uncertainty. Second, the optimal map from sampled outputs particular conformity score that properly accounts for the missing mass. These principles extend conformal prediction fundamentally new setting and may be of independent theoretical interest.
set is defined by thresholding
2

---

3) In Section 4, we design a finite-sample algorithm that combines these principles, integrating the estimation of missing mass (and its rate of reduction) into the conformal prediction pipeline while provably maintaining valid, distribution-free coverage guarantees. A key technical contribution novel estimator for the rate of decrease in missing mass, derived by revisiting the classical Good-Turing estimator-originall developed to estimate the missing mass itself.
4) We show the practical value of our approach through experiments on open-ended LLM tasks. Across three benchmark datasets, we quantify how each algorithmic principle contributes to prediction set informativeness under varying query and coverage constraints. Compared to recent query-base -ased CP baselines [13, 14], our method significantly reduces non- non-informative sets while maintaining valid coverage guarantees. These highlight the foundational role of our missing mass perspective in CP.
1.1 Related works
We briefly discuss closely related works here and defer a full discussion to Appendix A.
Conformal Language Modeling. Conformal Language Modeling (CLM) was introduced by [13] and similar ideas further studied by [14, 19-21]. CLM adapts conformal prediction to LLMs by calibrating a set of stopping rules that determine how many outputs to include in a prediction set. However, these methods do not account for uncertainty over unseen generations, and thus only provide valid sets for coverage levels less or equal than the few-shot accuracy of the underlying model. Furthermore, they do not explicitly optimize how the query budget used across different prompts. In contrast, we provide valid prediction sets for any user-defined coverage level and query budget, using a principled framework that bridges conformal prediction with classical missing mass estimation to optimize set informativeness and query efficiency. We also compare against CLM methods in Section 5, demonstrating substantial gains in informativeness, under fixed query budgets.
Conformal Abstention and Conformal Factuality. Conformal abstention algorithms refrain from generating response when uncertainty is high [22-24]. Other works focus aligning CP with LLM factuality in structured tasks [25-27]. or filtering long-form generations by validating sub-claims [28- 31]. However, these methods do not construct prediction sets and are thus not directly comparable to ours, though connecting our framework with theirs presents an interesting direction for future work.
2 Problem formulation
In this section, formalize the problem of conformal prediction with query oracle. Consider covariate space X' and a potentially infinite label space V An input-output pair (X, Y) E X' x y is drawn from unknown joint distribution p(x., y/), which represents the true data-generating process. For instance, in a text generation task, X could be prompt and Y the correct or intended response. We assume access to generative model, referred to query oracle, which allows us to sample from a conditional distribution T z). That is, querying the oracle at input yields an independent sample y T: 1t). Our goal is to construct prediction sets that provide rigorous coverage guarantees while querying the oracle a finite number of times per test input.
More formally, for user-specified miscoverage level (0, 1), seek to ensure the following coverage guarantee:
P(xYY~~ | E C(X)) 2 1 a.
Even though C(X) should be constructed using only a finite number of queries to (yysz), which may differ from p(y]æ)), the coverage constraint in (1) is with respect to p(y ar). This distinction is crucial: while ग governs the observable behavior of the model, coverage must be guaranteed with respect to the true, unknown distribution p.
In classical CP, one defines a nonconformity score function S X' + E to measure how atypical a label is for an input z, and constructs prediction sets of the form C(z) {v E yy: S(x, y) S q). where q a calibrated threshold. To use such a construction in practice, one must either enumerate the label space ),, as in multi-class classification, or describe the set compactly. such as an interval when y = R.. However, tasks such as text generation, sets defined as {y E y S(x,, y/ < q). when ) is the space of all the text sequences, are not tractable representation for uncertainty. That is, there no clear practical way to list all these labels or describe them using an interpretable structure (like an interval). Hence, the standard paradigm of defining score function and calibrating threshold
3

---

may not fully capture the nature of uncertainty in generative models. Instead, generative models allow for exploring the output space by multiple queries.
What is missing is a perspective that views uncertainty through the lens of querying the generative mhael-that is, sampling from the oracle. In this view, the information about the true label comes from a fimite set of queries: (x(x) = {yf..... yi }. where is a test point and is the number of queries. This multiple-query setting introduces a key limitation: the correct label Y may not be among the queried outputs. This scenario is common in practice-e.g, when using an LLM as the oracle to generate possible responses
prompt. If none of the generated completions contains the correct answer, we have no signal to recover it. In such cases, there is no choice but to admit high uncertainty and acknowledge that the correct label could lie anywhere in the vast, unseen remainder of y.
To address this, we introduce a special abstract label EE, short for "Everything Else", which denotes the collection Y (a:).. Intuitively, when the model has not yet produced the correct output in its first queries, the only way to ensure coverage is to include EE in the prediction set. With this formulation, the prediction set C(x) is a subset of Z(x) EE. The CP coverage guarantee P(Y E C(X)) 2 1- a then admits the interpretation: either the true label Y is among the sampled outputs, or is captured by EE. Including EE ensures valid coverage even when the true label has not been observed. The key challenge, then, is to avoid including EE unnecessarily- as to keep prediction sets informative-wiiiee
still maintaining coverage guarantees across all test points. This creates fundamental trade-off: querying the oracle more increases the chance of capturing the correct label explicitly, reducing reliance on EE: querying less conserves resources but often necessitates including EE, resulting in less informative predictions. To rigorously navigate this trade-off, we formalize an optimization framework that balances coverage, query cost, and informativeness.
Our framework consists of two components. The first is a query policy T'; X' + N U {O), which determines how many i.i.d. queries make the oracle for each input æ. This effectively allocates the total query budget across test inputs. For each input x, we query the oracle π (y][>) independently T(r) times, producing a sampled label set bT;; {vf (.. for each
The second component is set map / X x 2 + 23" which converts the queried labels into prediction set C(x) = f(x, x)); where y = JUEE. Given a finite computational query budget B and user-defined miscoverage rate [0, 1], our goal is to design T and jointly to ensure valid coverage while maximizing the informativeness of the prediction sets under the budget constraint.
Conformal Prediction with Query Oracle (CPQ)
[AI(BE E C(X)) + EVFER 11 E c(X))
minimize T()
Ex-p
subject to
Pr(xYr~'l E C(X) 2 a Ex Ex~r[T(X)] BB
We minimize two forms of uninformative prediction sets: one by the inclusion of EE, the other by the size of the prediction set. Whenever EE E C(x),, the conditional coverage at x is trivially satisfied: PlY E C(r) X æ| 1. Thus, including EE guarantees coverage but offers useful information. Penalizing EE therefore essential: the challenge lies not in achieving coverage, but in doing so while using EE infrequently as possible. The parameter À > 0 controls the penalty ratio. We focus on the regime where À > 1, expressing a strong preference for minimizing the use of EE across the population. However, the second term remains important to prioritize smaller sets among those that avoid EE maximally. In the next section, we analyze this objective to uncover two key algorithmic principles. These principles will ultimately guide the design of our practical, finite- sample algorithm.
3 Algorithmic Principles
The CPQ problem introduced above is a joint optimization over two components: the query policy T(-) and set map f()). this section, we adopt a decoupled analysis, splitting the problem into two stages. First, we fix a query budget and ask: What is the optimal query policy for allocating queries to minimize the chance of missing the correct label? Then, given a fixed query policy, we ask: What is the optimal set map for constructing informative prediction sets while ensuring valid coverage?

---

It is worth noting that this decoupled analysis only approximates the full CPQ solution, as it breaks the joint optimization over T' and f. Accordingly, optimality in this section refers the best solution within each stage, rather than the overall joint optimum.
To answer these questions, work in the population regime, assuming the query oracle Tt a)) is the same as the true conditional distribution p(y æ). Consequently, we assume throughout this section that p; i.e., the query oracle is perfect. This idealized setting allows us derive two algorithmic principles-one for query policy and one for prediction set construction foundation of our finite-sample algorithm. In Section 4, we show how to apply these principles with any black-box query oracle (e.g., an LLM), particularly when π (yl x) * p(y(z), a)), to construct practical prediction sets with saite coverage guarantees. Proofs are deferred Appendix B.
form the
3.1 Principle 1: Optimal Querying Policy by Missing Mass Minimization
We now focus on the query policy, aiming to allocate queries across covariate points to minimize the chance of missing the correct label. If computational resources were unlimited, we could query the oracle exhaustively for each input x, fully uncovering the label distribution and removing the need for the abstract label EE. But under finite budget, must query strategically- balancing where and how much to query-an objective naturally captured by the concept of missing mass.
Formally, the missing mass for covariate z after t queries is defined as the probability that the true label Y is not among the sampled set (x)):
0(x, t)
Pr [Y Zi(x) X X 2], ViZe(a)
where (x(x) consists of & i.i.d. samples from p(y x). Intuitively, (xx, () measures residual uncertainty-the chance that t independent draws from p(y 2) fail to capture the true label. As t increases, (xx, t) naturally decreases, and does so with diminishing returns: each additional query is less likely to reduce uncertainty than the previous one. To make this precise, define the finite difference as (xx 1) == [(x, + 1) ((., t). For each x, (xx, t) is negative and non-decreasing in meaning (a, t) non-increasing with diminishing returns (see Appendix B for proofs).
These properties make missing mass a natural objective for query policy. For each input x, increasing the number of queries ł reduces the probability of missing the true label-ie.., lowers 0(x, and and eventually, we may no longer need to include EE the prediction set for that æ. However, since our total query budget is limited, we cannot afford to exhaustively query all inputs. This raises the core question: how should we allocate our finite budget across different covariates to minimize overall uncertainty? That is. which imputs should receive more queries to reduce reliance EE most effectively? This naturally leads to the following optimization problem:
min (o) subject to Ex[T(X)) < B.
Ex [(X))
(2)
Theorem 3.1 (Optimal Query Policy). Assuming X is a continuous random variable, let T (-) be the optimal solution to the optimization problem (2). Then, there exists constant 3 E R such that, for all x E X almost surely, the optimal query size T (x) satisfies:
-a)
< (Z)
(3)
This condition implies that at the optimal query number Txxx) for each x, the discrete derivative A(x, T' (z)) from one more query is approximately equal to the threshold 8r (note that A(x, t) is non-decreasing in t). This result suggests a simple and intuitive principle: continue querying the oracle for a given x as long doing so substantially reduces the missing mass. In other words, we should stop sampling when the gain from an additional query falls below a threshold 3r. This behavior is directly driven by the diminishing returns property of 0(xr, and constitutes our first algorithmic principle. This insight guides the query policy in our finite-sample algorithm in Section 4, where we replace the exact derivative A(x, t) with data-driven estimate Á(x; t). and stop querying when A (z, t) < 3", with 8 calibrated from finite samples to satisfy the query budget B.
5

---

3.2 Principle 2: Optimal Prediction Sets by Missing Mass Estimation
In this section, we assume we are given access to a predetermined and known query policy function T: &' > N, which specifies the number of i..d. queries made to the oracle for each imput z. For each X, we denote the resulting set of sampled labels by Z(T, , x) .yf..... VT(z) )- With these samples in hand, our goal is to construct prediction sets that satisfy the desired coverage guarantee while being informative as possible.
To achieve this, we formulate an optimization problem determine the best possible prediction sets under coverage constraints. The primary goal is twofold: (I) minimize the inclusion of the abstract label EE, its presence indicates complete uncertainty, and (2) among sets with minimal inclusion of
EE, minimizing the prediction set sizes. Reminding f X 2 - 2 and C(x) f(x, 2 (T; from Section 2, we introduce:
min Ex
AL{EE E C(X)+ Σ c(X))
S0
9-EE
subject to
Pr X,Y
[Y
2 21-a,
The parameter À 2 0 balances the off between avoiding EE and keeping prediction sets small. We are particularly interested in the regime where À is large. This reflects a strict preference for minimizing the use of EE, while still allowing the optimization to differentiate among prediction sets that achieve the same frequency of EE inclusion. The inclusion of the second term ensures that among with smaller set sizes.
all valid prediction rules minimizing EE, favor the most informative Next, we characterize the structure of the optimal set map solution to (4) in the following theorem.
Theorem 3.2 (Optimal Set-Assignment Policy). Assuming X is a continuous random variable, for sufficiently large values of X, the optimal solution J' to the optimization problem (4) has the following structure: there exists a scalar threshold qº' E IR satisfying
(I, (()) ty Z(x) U [EE} S(x, v) S {²},
almost surely for every
Also, defining p(EE[x) = Pry [Y & Z((x) X = z] we have,
[1 ply x)) if + EE, ( ply x)) if EE.
S(x y)
Theorem 3.2 shows that the optimal prediction sets can be constructed by thresholding a conformity score ((z, y). This score prioritizes explicitly sampled labels over the abstract label EE, ensuring that EE is included only if necessary. Specifically, EE is assigned score of 2 p(EE x), where p(EE| .r) corresponds exactly to the missing mass. This means EE is most likely to be included when the missing mass is high-an intuitive and desirable behavior. Moreover, this result generalizes the classic finding in conformal prediction that optimal prediction sets minimizing size under coverage p(y x), in classification and regression [32, 33].
constraint are obtained by thresholding
To summarize, we have derived two foundational principles: one connecting the optimal query policy to the derivative of the missing mass, and the other connecting the optimal set map to the missing mass itself through an optimal conformity score. In the next section, we build upon these principles to design a practical finite-sample algorithm.
4 Finite Sample Algorithm
In this section, we present our finite-sample algorithm, which consists of two modules, each carefully built upon the algorithmic principles derived in Section 3. The query module relies on an estimator of the missing mass derivative, denoted Áax, t), while the calibration module uses an estimator of the missing mass itself, 0(z,, both of which we detail below.
Estimating Missing Mass and Its Derivative. Let y be the label space, and suppose we observe sequence of t i..d samples (x) [vf.... yi } x (v]x), i.c., samples from the oracle. The

---

missing mass, ((x, t), is defined as the total probability of all labels in y that have not been observed
in the sample (z)... For each integer r 2 0, let N,, t) denote the number of distinct labels that occur exactly times in the sample (x)). In other words, (x, 1) Ky E 7x(x) #(v) = r)
where #(y) denotes the number of times the label y appears in the sample 7z(2)).
The classical Good-Turing estimator approximates the missing mass based on the labels seen exactly once, aka singletons. The intuition simple that if many labels appear only once, it is likely that there are more yet-unseen labels with comparable probabilities. This yields the estimator
((x,t)=- :- No In fact, Good-Turing estimators also provide estimates for seen labels. For y e (x),,, we estimate p(y 2)) using the Good-Turinn formula: ( x) + Nr+1 where r the number of times y appears in Z, (z). Hence, we estimate the conformity score derived our optimal (y x), if y Z,(z) set construction (see Eq. (5)) by S(x, v) 2 0x1,),,
N.
if $ Z.(x)
On the other hand, the query module requires an estimate for the missing mass derivative A(x,t) 0(x, È + 1) - 0xx, f), which captures the reduction in missing mass from drawing an additional sample. By revisiting the original calculations behind the classical Good- Good-Turing estimator, we derive
the following novel estimator for the derivative: (xx,) ==
2N2
Interestingly, we see that while the Good-Turine estimator relates the missing mass to the count of singletons, our estimator for the derivative reveals that the count of doubletons, number of unique labels that appear twice, is good proxy for the rate at which the missing mass decreases. detailed derivation is provided in Appendix D.1. Furthermore, of this estimator on two synthetic distributions in Appendix D.2, along with comparisons against a natural baseline: the plug-in estimate of the derivative computed by taking finite differences of the Good- -urrTuring missing mass estimates at successive values of t.
will showcase the empirical performance
Algorithm. Assume we have access to query oracle π (y(ar) that approximates- but may not perfectly match-the the true conditional distribution p(y]z)) By querying this oracle, we can draw independent samples from (y/a=r for each input and compute quantities such as the missing mass (or its derivative) as needed. Additionally, we are given calibration data Deat (X,, Yi) drawn from the ground truth distribution p(z, y), as is standard in CP.
To tune the query threshold 3r, we first partition the calibration data Deat into two disjoint subsets Deal, and Dealz- The first subset Deal, is used exclusively for tuning 8 as follows: for each input Deal, draw set of queries V1.T(a) <yy(z), where T(x) is the smallest integer number at which Á(x, T(x)) < 3". Given a query budget constraint B, select 9 such that the average number of queries [Den,, | Eg T(x) < B. Since 8 is a sealar, this can be done via exhaustive search
grid of values. Once 3²t is fixed, we apply our algorithm presented in Algorithm
Algorithm 1 Conformal Prediction with Query Oracle (CPQ)
Input: Query oracle лly x), conformity score S(z, v), calibration data Deala test point Prests miscoverage a, query budget B, missing- mass estimator Å (x. f), threshold f
Query Module
- Principle
For each x E Deatz U {=
Sample V1:T(x) ~ π ( x) until (z, T(x)) < 8 Let Z(x) = (,,,..., vr(a))
Calibration Module + Principle 2
For each (i) E Deal, compute s; $(1 v:). ($1, (........ ... S| 20).
Set q" Quantile, -a (
Output: C(Zteett = (y y E Z( (EE} S (Zteest v) S 5
7

---

The algorithm consists of two stages, each directly motivated by the algorithmic principles derived in Section 3. In the first stage-the query module-we determine how many queries draw for each imput x. We query sequentially from the query oracle Tt x)) (e.g. an LLMM), one at a time, and after each draw, we update the estimated missing mass derivative Á t). Guided by principle 1, we continue sampling until (ax, t) falls below the threshold 3*. The result of this stage set (xx) of observed labels for each input z, along with the associated estimated missing mass for the fallback label EE. In the second stage- the calibration
by principle 2, we calculate the conformity scores (zz. y) on held-out calibration set Deal, as described earlier in this Section. We then compute the (1 - a -quantile of the conformity scores on D Dent, (adjusted with oo for proper debiasing), and use this threshold to construct prediction sets for test inputs, following the standard split conformal procedure.
The following theorem guarantees the distribution-free coverage validity of our algorithm. Theorem 4.1 (Coverage Validity). Assuming Diest and Deat, are exchangeable, we have: Pr(Yren E ((x,em)] 2 a-
where the probability is over (Xneu, Yues) and Dealg-
In summary, CPQ adaptively query the oracle guided by an estimation of derivative of the missing mass, and then make prediction sets guided by Good-Turing estimate of the missing mass itself.
Experimental Results
We begin by outlining our experimental setup, then present empirical evaluations along two main axes: (i) component-wise analysis isolating the impact of optimal querying and optimal conformal calibration (Section 3), and (ii) a comparison against sfate-of-the- art conformal language modeling baselines, including CLM [13] and its recent variant, SCOPE Gen [14].
Datsets and Models. We evaluate on three benchmark datasets using two leading LLMs, adapting all
tasks to open-eneded generation by removing any multiple-choice structure. Generations are lexically normalized and marked correct only if they exactly match the ground truth answer; i.e evaluating using the exact match metric. The datasets are: (i) BBH Geometric Shapes [34] (250 prompts): Visual reasoning from SVG paths, with responses generated using LLaMA-3 8B- JB-Instruct [35]. (ii) GSM8K [36] (300 randomly selected prompts): Multi-step arithmetic reasoning, answers from Mixtral-8x7B-Ii InIItrttt [37]. (iii) BBH Date Understanding [34] (250 prompts): Temporal reasoning; responses generated using LLaMA-3 8B-Instu
Evaluation Metrics. Our goal is to construct prediction sets that are both valid and informative. We report three key evaluation metrics. First, Empirical Coverage: the fraction of test examples whose prediction set contains either the correct answer or EE, either ensures validity ( see Section 2). Second, EE fraraction measures how often EE appears; lower fractions indicate the model more often explicitly captures the correct answer without relying on fallback coverage via EE. Third, Average set size: the average number of seen labels per prediction set. While larger sets generally imply less informative sets, a larger set without EE conveys more information than smaller set with EE, the former expresses uncertainty within observed outputs, whereas the latter signals residual uncertainty over the entire unobserved label space. Together, these metries capture the tradeoff between coverage and informativeness. An ideal prediction set achieves target coverage with minimal reliance on EE
Clustering. Clustering is key step in our pipeline. Since LLMs produce lexically varied outputs that convey the same meaning, we group generations into semantic equivalence classes (clusters), each corresponding to a single label y E ) We use generations semantically equivalant and assign them to the same cluster if so. This approach has proven effective for handling complex and unstructured outputs [19, 38]. Prompts and implementation details are provided in Appendix C.5. Each cluster's frequency is used to estimate the missing mass (probability of unseen clusters) and its derivative (see Section 4). Probabilities for seen clusters are computed by normalizing frequencies and scaling to form a valid distribution over both seen and unseen clusters. Importantly, our finite sample algorithm is modular: it works with any clustering or probability estimation method. As long as clustering and associated probabilities are well defined and valid, our method applies.
model to decide if two
Calibration and sampling procedures. For each dataset, we randomly split examples equally into calibration and test sets. On the calibration set, we tune CPQ's sampling threshold 3" to meet the
8

---

Coverage
Fraction
Average
Vanilz
08
Vontia
14
sanil:
BBH- Géo Shapes
0.1
0.0
Coverge
0.6
0.5
0.
0.8
0.8
0.7
Coverage
EE Fraction
Awerage Set Size
0.5
2.25
P1
P1+
71+72
Avergg Sett 530
-+-
P1-P2
Coverage
1.75
GSM8K
0.8
02-
07-
0.
122
0.72
0.70
0.75
0.80
0.1b
040
0.70
0.75
0.00
0.85
0.90
0.70
0.75
0.00
11.5
0.50
1-0
1.-
1-10
Caverage
Fraction
Average
Venilla
Vanila
Vanil:
P1
0.8
0.0
BBH-Date
Coorage
07-
0.0
04
Figure I: Performance of the three algorithmic variants (Vanilla, Pl, P1+P2 corresponds to our full finite sample algorithm, i.c CPQ) across Geo Shapes (B 30), GSM8K (B 7), and BBH-Date (B 20). Each row shows coverage, EE fraction, and average set size as a function of a.
target average query budget and estimate the threshold g" for constructing prediction sets. All results are averaged over random splits calibration and test data.
5.1 Fine-grained Component-wise Analysis
To assess contributions of each algorithmic principle (Section 3), we compare three progressively refined variants: (i) Vanilla: A baseline with fixed. non-adaptive querying strategy- same number of generations per input-and and a simple, yet valid calibration rule. While not optimal, this baseline serves as reasonable starting point. Calibration details provided in the Appendix C.I. (ii) Principle Adds our adaptive querying, adjusting the number queries based on the estimated missing mass derivative, with calibration unchanged. (iii) Principle 1 2: Combines both optimal querying and conformal calibration, representing the full CPQ algorithm in Section
Figure shows results all benchmark datasets. We observe consistent gains from incorporating each algorithmic principle, with the full CPQ algorithm (both principles combined) achieving the largest reduction in the fraction of prediction sets that include the fallback label EE, while maintaining valid coverage. The query budget B is fixed per dataset, while the coverage level 1 - a is varied. Budgets were chosen reflect reasonable intermediate values based on the few-shot model accuracy for each dataset. Additional results across a range of budgets can be found in Appendix C.2.
We see that CPQ navigates a clear trade-off between reducing reliance on the fallback label EE and using observed labels. Both Principle and the full CPQ algorithm (Principles 1+2) actively leverage the queried labels to avoid including EE while maintaining valid coverage. The additional reduction fraction achieved by the full CPQ algorithm naturally comes cost: the number of non-EE labels included in the prediction set increases, leading to larger set sizes. This behavior is expected since aggressively minimizing reliance on EE requires exploiting the observed labels more fully to preserve coverage.

---

Dataset
Algorithm
Nom. Cov.
Emp. Cov.
EE Frac.
CLM
0,60
0.58 + 0.038
0.40 1 0.047
Geo
Scope-Gen
0.60
0.68 0.080
0.38 1 0.22
CPQ
0.60
0.61 0.06
0.07 0.07
CLM
0.95
0.93 1: 0.03
0.70 1 0.11
GSM8K
Scope-Gen
0.95
0.93 0.05
0.61 + 0.26
CPQ
0.95
0.95 + 0.02
0.16 + 0.14
CLM
0.70
0.68 0.07
0.32 + 0.11
Date
Scope-Gen
0.70
0.78 + 0.07
0.51 + 0.11
CPQ
0.70
0.71 + 0.07
0.25 + 0.08
Table 1: Comparison of nominal coverage, empirical coverage, and the fraction of sets that contain the fallback label (EE) across three benchmark datasets (Geometric shapes (Geo), GSM8K, Date understanding (Date)) for three methods: CLM, Scope-Gen, and our proposed CPQ.
5.2 Comparison with Conformal Baselines
We now compare CPQ to two recent conformal prediction methods for large language models: CLM [13] and its variant SCOPE-Gen [14]. While both represent state-of-the-are in this space, they are not out-of-the-bon comparable with CPQ in two key ways, First, neither accounts for the missing mass mass-the residual probability over unseen labels represented by EE in our framework. As result, they may fail to provide valid configurations at higher coverage levels, especially when the correct answer isn't among the sampled outputs. Second, they lack an explicit mechanism to control query budget: the number of model queries varies across coverage levels and is not directly tunable.
To enable meaningful comparison, we evaluate CLM and SCOPE-Gen using their original procedures, with one adjustment: we augment their output space include the abstract label EE alongside sampled responses. The underlying logic and mechanisms remain unchanged; we simply extend the prediction space reflect the possibility of unseen correct label, which necessary for complete coverage analysis. This enables us to assess how often these baselines would have needed to include to satisfy coverage validity. Since, there no principled way configure these baselines to target specific budget, we first measure their average query usage. We then tune CPQ's querying threshold 3 to match this budget. All methods are thus evaluated on equal footing the same nominal coverage level and under the same average query budget.
As shown Table CPQ dramatically reduces reliance on For example, on GSMSk 95% nominal coverage, CPQ achieves the desired coverage with an EE fraction of 16.5%, versus 70.4% for CLM and % for SCOPE-Gen under the same budget constraints. Moreover, CPQ only offers more informative prediction sets but also maintains tighter coverage, especially in high-coverage regimes where baselines struggle.
6 Conclusion and Limitations
We presented principled framework for UQ by introducing novel missing mass perspective. we derived two algorithmic principles that guide optimal query policy and prediction set construction. Our finite-sample algorithm integrates these insights and yields significantly more informative prediction sets compared existing conformal methods for L.LM UQ. Our method relies on estimation of missing mass and its derivative, which can be challenging in very low query regimes.
acknowledgments
This work was supported by the NSF Institute for CORE Emerging Methods in Data Science (EnCORE) and the ASSET (Al-Enabled Systems: Safe, Explainable and Trustworthy) Center.
10

---

References
[1] Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qiang- long Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, et al. A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions. ACM Transactions on Information Systems, 43(2):1-55 2025.
[2] Junyi Li, Jie Chen, Ruiyang Ren, Xiaoxue Cheng, Wayne Xin Zhao, Jian- Yun Nie, and Ji-Rong Wen. The dawn after the dark: An empirical study on factuality hallucination in large language models. arXiv preprint Stt1:2401.032000 2024.
[3] Nick McKenna, Tianyi Li, Liang Cheng, Mohammad Javad Hosseini, Mark Johnson, and Mark Steedman. Sources of hallucination by large language models on inference tasks. arXiv preprint arXiv:2305.14552, 2023.
[4] Sebastian Farquhar, Jannik Kossen, Lorenz Kuhn, and Yarin Gal. Detecting hallucinations in large language models using semantic entropy. Nature, 630(8017):625-6333 2024.
[5] Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learning applications of algorithmic randomness. 1999.
[6] Craig Saunders, Alex Gammerman, and Volodya Vovk. Transduction with confidence and credibility. 1999.
[7] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world, volume 29, Springer, 2005.
[8] Shayan Kiyani, George Pappas, Aaron Roth, and Hamed Hassani. Decision theoretic foundations for conformal prediction: Optimal uncertainty quantification for risk-averse agents. arXiv preprint arXiv:2502.02561, 2025.
[9] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9(3), 2008
[10] Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
[11] Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael I Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. 1000999/4999 14/93, 2020.
[12] Jing Lei, Max G'lell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Associ- ation, (035523):1094-111
2018
[13] Victor Quach, Adam Fisch, Tal Schuster, Adam Yala, Jae Ho Sohn, Tommi S. Jaakkola, and Regina Barzilay. Conformal language modeling. 2024.
[14] Klaus-Rudolf Kladny, Bernhard Schölkopf, and Michael Muchlebach. Conformal generative modeling with improved sample efficiency through sequential greedy filtering, 2025.
[15] William Gale and Geoffrey Sampson. Good-turing frequency estimation without tears. Journal of quantitative linguistics, 233::217- 1995.
[16] Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation: Why is good-turing good. Advances in Neural Information Processing Systems, 28, 2015.
[17] David A McAllester and Robert E Schapire. On the convergence rate of good-turing estimators. In COLT, pages 1-6, 2000.
[18] Alon Orlitsky, Narayana Santhanam, and Junan Zhang. Always good turing: Asymptotically optimal probability estimation. Science, 302(5644);4774331 2003.
[19] Ramneet Kaur, Colin Samplawski, Adam D. Cobb, Anirban Roy, Brian Matejek, Manoj Acharya, Daniel Elenius, Alexander M. Berenbeim, John A. Pavlik, Nathaniel D. Bastian, and Susmit Jha. Addressing uncertainty in Ilms to enhance reliability in generative ai, 2024.
11

---

[20] Hooman Shahrokhi, Devjeet Raj Roy, Yan Yan, Venera Amaoudova, and Janaradhan Rao Doppa. Conformal prediction sets for deep generative models via reduction to conformal regression. arXiv preprini arXiv:2503. 105/2, 2025.
[21]
Jiayuan Su, Jing Luo, Hongwei Wang, and Lu Cheng. Api is enough: Conformal prediction for large language models without logit-access, 2024.
[22] Yasin Abbasi Yadkori, IIja Kuzborskij. David Stutz, András György, Adam Fisch, Arnaud Doucet, Iuliya Beloshapka, Wei-Hung Weng. Yao Yuan Yang, Csaba Szepesvári, Ali Taylan Cemgil, and Nenad Tomasev. Mitigating Ilm hallucinations via conformal abstention, 2024.
[23] Sina Tayebati, Divake Kumar, Nastaran Darabi, Dinithi Jayasuriya, Ranganath Krishnan, and Amit Ranjan Trivedi. Learning conformal abstention policies for adaptive risk management in large language and vision-language models, 2025.
[24] Yasin Abbasi Yadkori, IIja Kuzborskij. András György, and Csaba Szepesvári. To believe or not to believe your 1lm, 2024.
[25] Dennis Ulmer, Chrysoula Zerva, and André F. T. Martins. Non-exchangeable conformal language generation with nearest neighbors, 2024.
[26] Yu Gui, Ying Jin, and Zhimei Ren. Conformal alignment: Knowing when to trust foundation models with guarantees, 2024.
[27] Bhawesh Kumar. Charlie Lu, Gauri Gupta, Anil Palepu, David Bellamy, Ramesh Raskar, and Andrew Beam. Conformal prediction with large language models for multi-choice question answering, 2023.
[28] John J. Cherian, Isaac Gibbs, and Emmanuel J. Candès. Large language model validity via enhanced conformal prediction methods, 2024.
[29] Christopher Mohri and Tatsunori Hashimoto. Language models with conformal factuality guarantees, 2024.
[30] Terrance Liu and Zhiwei Steven Wu. Multi-group uncertainty quantification for long-form text generation, 2024.
[31] Maxon Tolen-TTles, Maya Gambhir, Keshav Ramji, Aaron Roth, and Surbhi Goel. Conformal language model reasoning with coherent factuality. In The Thirteenth International Conference on Learning Representations.
[32] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223 234, 2019.
[33] Shayan Kiyani, George Pappas, and Hamed Hassani. Length optimization in conformal prediction. Advances in Neural Information Processing Systems, 17799519-99566 2024.
[34] Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann. Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V. Le, Ed H. Chi, Denny Zhou, and Jason Wei. Challeng- ing big-bench tasks and whether chain-of-though can solve them, 2022.
[35] AI@ Meta. The llama 3 herd of models, 2024.
[36] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichir Nakano, Christopher Hesse, and John Schulman. Training verifiers solve math word problems, 2021.
[37] Mistral AL Mixtral of experts, 2024.
[38] Lorenz Kuhn, Yarin Gal, and Sehastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation, 2023.
[39] Samuel S Wilks. Determination of sample sizes for setting tolerance limits. The Annals of Mathematical Statistics, 12(1):91-96, 1941.
12

---

[40] Henry Scheffé and John W. Tukey. Non-parametric estimation. i. validation of order statistics. Annals of Mathematical Statistics, 16(2):187-192, jun 1945.
[41] C. Saunders, A. Gammerman, and V. Vovk. Transduction with confidence and credibility. In Proceedings of the 16th International Joint Conference on Artificial Intelligence Volume IJCA1'99, page 722-726, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
[42] Yaniv Romano, Matteo Sesia, and Emmanuel J. Candès. Classification with valid and adaptive coverage, 2020.
[43] Harris Papadopoulos, Volodya Vovk, and Alex Gammerman. Conformal prediction with neural networks. In /9th IEEF International Conference on Tools with Artificial Intelligence(ICAAI 2007), volume 2, pages 388-395, 2007.
[44] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Tapio Elomaa, Heikki Mannila, and Hannu Toivonen, editors, Machine Learning: ECML 2002, pages 345-356, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.
[45] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression, 2017.
[46] Yaniv Romano, Evan Patterson, and Emmanuel J. Candès. Conformalized quantile regression, 2019.
[47] Sima Noorani, Orlando Romero, Nicolo Dal Fabbro, Hamed Hassani, and George J. Pappas. Conformal risk minimization with variance reduction, 2025.
[48] David Stutz, Krishnamurthy, Dvijotham, Ali Taylan Cemgil, and Arnaud Doucet. Learning optimal conformal classifiers, 2022.
[49] Linyu Liu, Yu Pan, Xiaocheng Li, and Guanting Chen. Uncertainty estimation and quantification for Ilms: simple supervised approach, 2024.
[50] Lukas Aichberger, Kajetan Schweighofer, Mykyta lelanskyi, and Sepp Hochreiter. Semantically diverse language generation for uncertainty estimation in language models, 2024.
[51] Jinhao Duan, Hao Cheng, Shigi Wang, Alex Zavalny, Chenan Wang, Renjing Xu, Bhavya Kailkhura, and Kaidi Xu. Shifting attention to relevance: Towards the predictive uncertainty quantification of form large language models, 2024.
[52] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models, 2023.
[53] Potsawee Manakul, Adian Liusie, and Mark J. F. Gales. Selfcheckgpt: Zero-resouree black-box hallucination detection for generative large language models, 2023.
[54] David McAllester and Luis Ortiz. Concentration inequalities for the missing mass and for histogram rule error. J. Mach. Learn. Res., 4(null):955911 December 2003.
[55] Daniel Berend and Aryeh Kontorovich. On the concentration of the missing mass, 2012.
[56] Anna Ben- Ben-Hamou, Stéphane Boucheron, and Mesrob I. Ohannessian. Concentration inequalities in the infinite um scheme for occupancy counts and the missing mass, with applications. Bernoulli, 23(1), February 2017.
[57] Prafulla Chandra and Andrew Thangaraj. Concentration and tail bounds for missing mass. pages 1862-1866, 07 2019.
[58] I. J. GOOD. The population frequencies of species and the estimation of population parameters. Biometrika, 40(3-4):237-264, 12 1953.
13

---

[59] Jayadev Acharya, Ashkan Jafarpour, Alon Orlitsky, and Ananda Theertha Suresh. Optimal probability estimation with applications prediction and classification. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Anmual Conference Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 764-796, Princeton, NJ, USA, 12-14 Jun 2013. PMLR.
[60] Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation: Why is good-turing good. C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[61] Moein Falahatgar, Mesrob Ohannessian, Alon Orlitsky, and Venkatadheeraj Pichapati. The power of absolute discounting: all-dimensional distribution estimation. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Guyon, U. Von
[62] Elchanan Mossel and Mesrob I. Ohannessian. On the impossibility of learning the missing mass. Entropy, 21(1), 2019.
[63] Alon Orlitsky and Ananda Theertha Suresh. Competitive distribution estimation, 2015.
[64] Maciej Skorski. Mqan-squared accuracy of good-turing estimator. In 2021 IEEE International Symposium Information Theory (ISIT), pages 2846-28511 2021.
[65] David A. McAllester and Robert E. Schapire. On the convergence rate of good-turing estimators. In Proceedings of the Thirteenth Annual Conference on Computational Learning Theory, COLT '00, page 1-6, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.
[66] Prafulla Chandra, Aditya Pradeep, and Andrew Thangaraj. Improved tail bounds for missing mass and confidence intervals for good-turing estimator. In 2019 National Conference Communications (NCC), pages 1-6, 2019.
[67] J. GOOD and G. H. TOULMIN. The number of new species, and the increase population coverage. when sample increased. Biometrika, 43(1-2)::5-63) 06 1956.
[68] Jerzy Neyman and Egon Sharpe Pearson. Ix. the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of Mathematical or Physical Character, 23 2316644700))229-333,,, 1933.
[69] David G Luenberger. Optimization by vector space methods. John Wiley Sons, 1969.
[70] Ellis Weng and Andrew Owens. Lecture 11: The good-turing estimate. https:/ httpss///wwwccco cornell. edu/ courses/ wttpeeeeeeee70001100e0// hwwggguddeseeeeeee seadee//eecl...pe 1.ff. 2010. CS6740: Advanced Language Technologies, Comell University. March 4, 2010.
14

---

Table of Contents
Extended Related Works
16
B Proofs
17
B.1 Proof of Theorem 3.1
17
B.2 Proof of Theorem 3.2
19
B.3 Proof of Theorem 4.1
20
Further Experiments and Details
21
C.1 Sub-optimal calibration procedure
C.2 Performance across different budget values
21
C.3 Additional comparison with baselines
................................
21
C.4 Robustness under high hallucination rates
C.5 Clustering algorithm
24
C.5.1 Comparison of alternative clustering methods
25
Missing Mass and Missing Mass Derivative
25
D.1 Derivation
26
D.2 Empirical evaluation
27
15

---

A Extended Related Works
Conformal Prediction. The notion of prediction sets originates from classical work on tolerance regions in statistics [39, 40J. However, the modern formulation of Conformal Prediction (CP), which provides distribution-fres finite-sample validity guarantees, was introduced by [5, 7, 41]. Since then, CP has emerged as standard framework for uncertainty quantification, particularly in classification [11, 42, 43] and regression tasks [44-66]. A growing body of work have then focused on improving the set size (length) efficiency of conformal prediction sets [28, 32, 33, 47, 48]. These developments reflect the increasing demand for flexible and reliable uncertainty quantification in modern predictive systems.
Conformal Prediction for LLMs. Recent work has explored conformal prediction as a principled tool for uncertainty quantification in Large Language Models (LLMs), where outputs are open-ended and unbounded. Conformal Language Modeling [13] introduced a sampling-and filtering that generates candidate responses until a calibrated stopping rule guarantees, with high probability, that at least one correct answer lies in the set. Generative Prediction Sets (GPS) [20] recasts the problem conformal regression the number of samples required for correct output, using the resulting distribution to infer minimal draw count needed to achieve nominal coverage, SCOPE-Gen [14] proposes a sequential pruning strategy using greedy admissibility filters, leveraging a Markov factorization to reduce verification costs during calibration. APlisEnough [21] offers a black-box approach that defines nonconformity via sampling frequencies and semantic similarity; their approach can be integrated in our modular framework seamlessly.
and-liiriini approach
Several complementary directions have further adapted CP to the generative language setting: token- level CP for non-exchangeable generation [25]. representation-level conformal alignment, filtering methods for long-form factuality guarantees [28, 29, 31], multi-group uncertainty quantification in structured text [30], and CP for enumerable, discrete output spaces such as multiple-choice tasks [27]. While all these methods offer valid coverage, they vary in efficiency, granularity, and scope, and none explicitly incorporate missing mass estimation as a means to reason about unseen correct responses to capture the full output space. Moreover, they do not account for or optimize under an explicit query budget, a central component of our framework. In contrast, out method address both coovese in the presence of unobserved labels and efficient query allocation allocation-through a unified, theoretically grounded approach.
Conformal abstention for LLMs. An alternative to constructing prediction sets is enable selective prediction: allowing the LLM to abstain from responding when uncertain. This line of work aims to mitigate erroneous outputs by identifying in puts where the model's predictions are unreliable. In particular, [22] apply conformal risk control to bound the probability of hallucination and derive abstention rules that trigger whenever the estimated risk exceeds calibrated
[23] integrate CP with reinforcement learning to learn abstention policies that adaptively respond to task difficulty and distributional shifts. Separately, (24) introduce information-theorrtiic decomposition of uncertainty into epistemic and alcatoric components, leveraging the epistemic signal to guide abstention decisions.
While these methods share the goal of reliable decision- -mainng under uncertainty in LLMs, they differ from our approach in that they do not produce explicit prediction sets, and therefore cannot be directly compares. One could, in principle, adapt intermediate quantities from our method-such as prediction set size or estimated missing mass-as as abstention criteria, which can be an interesting venue for future work.
Broader Uncertainty Quantification for LLMs. Our work is informed by broad literature on uncertain quantification (UQ) for LLMs that extends beyond conformal prediction. A substantial body of research focuses on mitigating hallucinations in LLM outputs, employing techniques ranging from direct uncertainty estimation [4, 49-51] to strategies that generate multiple responses to probe and analyze the output space [52]. Prior research has observed that semantic disagreement among sampled responses correlates with hallucinations risk, motivating a suite of detection methods based on self-consistency, lekenllevel log- probability, or verifier-based models [30, 38, 53]. While these heuristics have demonstrated empirical success, they generally lack formal coverage guarantees and often require extensive sampling auxiliary models.
Missing Mass. The missing mass problem- estimating the total probability of outcomes not observed in given sample- has been extensively studied under the assumption of independent and identically
16

---

distribution (i.id) data. Theoretical results have established concentration inequalities for the missing mass around its expectation [54-57], studying the stability and predictability of this quantity in large-sample regimes. Central to practical estimation, the classical Good-Turing (GT) estimator, first introduced by [58], has been analyzed extensively, with multiple variants developed improve its finite-sample performance [59-64]. Confidence intervals for missing mass were obtained using the GT estimator in [65] and subsequently refined by [66]. Building upon these ideas, [67] developed the "Good-Toulmie estimator, extending the missing mass framework to the dirsovyy problem. Though conceptually related, species discovery-estiman unseen categories expected to appear in enlarged sample-and missing mass estimation-whie quantifies unseen probability mass-ar are fundamentally different in objective and interpretation.
how many new previously
B Proofs
B.1 Proof of Theorem 3.1
We first start by reviewing the theorem statement. Let (xx, t) be the missing- mass curve defined in Section 3.1, and A(x,t) 0(z,t+ 1) ((x t). There exists a threshold s 0 such that, almost surely,
A (x, (z) 1) - $ < (x)
or, 7 (I) = whenever (x, 0) S
Let T = [T' X' :2 measurable [X[[()] < B} and let 7 E T be optimal solution.
For 8 < 0 define the measurable sets
AB {= (a, (z) 1) B, and T (x:) > 0), B₃ = (x:
3).
Because (xx, (x)) < A (z, 7 1), the sets Ag and B3 are disjoint. We can prove the following claim.
Claim. p(As) = 0 for every 3 S O.
Proof of the claim. Assume p(As), p(B²) O. Take measurable A S As. B S Bg with p(A) p(B) = 17 > 0 (this exists due to the assumption that is continuous random variable) and set
(+) A
('(x)
+() IE Bg. (T))),,
otherwise.
Then we have,
E [X) Ex Ex 1[X e Asl 1[X B&]] EXT" s B,
therefore, T' E T. Furthermore,
B FOOXX ((X))
B[[[ E Aa) A(X, - - E B&] ((,,(X))(
(6)
B[[X E A,) (X) -1]+ (x) + +1]
(9) B[[[X E Agl E e Bz]
- m3 + 1 0
where (a) follows from the definition of T", (b) stems from Lemma B. which indicates the dimin- ishing return property, (c) follows from the definitions of Ag and B3. and finally, (d) is due to the definition of 17. This is a contradiction with the optimality of T hence we proved the claim.
Existence and characterization of the threshold S*. Define the threshold 3 by setting
8*
inf inf B < 0: p(Ap) 0}.
17

---

Intuitively, this threshold separates covariate points into two groups: those for which an additional query would yield a marginal improvement strictly greater than 5 and those for which the marginal improvement from additional queries is at most 3 To see why 3 is indeed the correct threshold, suppose there existed covariates violating the threshold condition at this 3 Then, we could slightly perturb the threshold, obtaining nearby threshold / such that both sets Ag and Bg simultaneously have positive probability. But this situation would directly contradict the claim we proved earlier, which ensures that at no threshold can both Ag and B3 have positive probability. Thus, violation at threshold 3 can occur, confirming that 3 precisely the desired threshold.
We now formalize this intuition precisely. Define the violation probabilities
f(ā) p(As) and g( = (B)), 850.
Observe that enlarging the threshold 3 reduces the set Ag and expands the set Bg. Therefore, the function ((3) is non-increasing and right-continuous, and g(33) is non-decreasing and left-continuous.
Additionally, at / = O, we have f()) = 0, since by construction Axx, L) S 0.
By right-continuity of f(-), it follows immediately from the definition of 8* that
p(As-) [(3)) 0.
Next, assume towards contradiction that p( (3.)) ) 0. By left-continuity of g(-), there would exist an e > 0 sufficiently small so that p pBBx--e > 0. However, by the definition of 8", lowering the threshold 3 would yield p(A 0. Thus, threshold 3 E, both Ag. and B3-- would simultaneously have positive probability, contradicting the claim we previously established. Hence, we must have
p(B3-) 0.
Finally, since p(Ag-) = 0 and p(B3-) ) = 0, we have for almost every
Arr, T (x) - 1) < r < (x)
In the corner case where A(x, 0) S 8*, the definition of Ag- forces the optimal query count (x)) = 0. This establishes precisely the threshold characterization asserted in the theorem, thereby completing the proof.
We now prove the following lemma, which we used in the above proof.
Lemma B.1 (Diminishing Returns). For every fixed covariate X, the marginal
Aax,t) 0(x, 1) ((x, t),
t t 0,
strietly negative and non-decreasing that is,
(ax
and A(z,t+1) 2 A(x,t) Vt 0.
Lemma B.1 establishes that as t increases, the missing mass ((z, naturally decreases, and does so with diminishing returns, meaning each additional query is less likely to reduce the uncertainty than the previous one. Thus the derivative of the missing mass, namely A(x, t) is negative and non-decreasing in f.
Proof. The missing mass is
8(x,t) Pr ( $ Zz(z) X= Er & Z((=))] V.Z.(z)
Applying law of total expectation
(xr = Bylx= Bx & Z(xx))]
and evaluating the inner expectation Conditioned Y y, the draws in Ze(x)) miss y with probability (1 (1y((y ", hence
0(x,t) Eyxx= p(Y =))]].
18

---

The, the finite difference becomes:
( t) 0(z, + 1) ((r,t)
= -Ey[(1 - -p(Y xx)) - p( x))
- --By((1-(** x))² p(Y [x)]
For each y, (1 - p(y x))² is decreasing in 1. Multiplying by the positive p(y | x) preserves this property, and expectation is linear; therefore the sequence gr g((z) == Ey[(1 p(Y x)) x)) x)] is non-increasing, so (xx, t) = (a(()) is non-decreasing.
B.2 Proof of Theorem 3.2
Let's start by restating the optimisation problem: For every input E X' the fixed query policy T X returns the random multiset (xx) = =Tx)), = ......(())) set map
outputs the prediction set C(x) fx, (a)) Z(x) {EE}. The goal is
A AL{EE E c(X) - Σ E
1 e c(x)
min
(6)
V/
Pr(Y 2 a-a.
Let us first outline the strategy for the proof clearly. The optimization problem (4) involves selecting subsets of labels minimize the frequency of including the abstract label EE and the size of the prediction sets, subject to coverage constraint. To solve this precisely, we begin by introducing a relaxation to linear programming problem, argue strong duality and optimality conditions, and then show the relaxation introduces no strictly better fractional solutions, hence the relaxation is actually equivalent to the original problem. Finally, we identify the optimal solution explicitly and demonstrate it has the threshold-baas based structure stated in the theorem.
Relaxation to Linear Program. For each x X' and realized set Z(z). define a selection variable,
g(2, Z(x).)) [0, 1]. y Z(z) U (EE)
which represents the probability of including label y the prediction set for covariate x and sampled set Z (x). Replacing f by g and allowing the full interval [0, 1), the optimization problem (4) can then be relaxed to:
Z((), EE) + Σ o Z())))
min
FEEE
s.t. E(d(, 2 1-a,
This relaxation enlarges the feasible region, i.e., its feasible region contains that of the discrete problem (6) (simply restrict g to {0, 1}), hence the optimal value of (7) is no larger than the optimum of the original integer-valued problem (6).
Both objective and constraint are linear in so (LP) is a linear programme. In particular, This is a linear programme with one linear constraint, identical in form the -eyman-Pearson Pearson allocation problem. The classical lemma (see, [68] for the case of finite dimensional optimization and Theorem Section 8.3 of [69] for infinite dimensional optimization) states that optimal solution is obtained by selecting those labels with largest benefit-to-en toeefit-to-costt ratio until the coverage constraint is met, possibly randomizing single tie. As assumed that there is mass mass-point in the underlying distribution, tie-breaking randomization is not necessary, a situation that similarly arises in the original derivation of Neyman- lemma.
Here the benefit label y (EE or not) is ply z). However, the cost is when y # EE and when y EE. The benefit-to-coe ratio ordering is therefore equivalent to ordering by the non-conformity
score
p(y Ix), P(EELu)
y * EE, y E.F.
So 3) =
19

---

As result of Neyman-Pearson lemma, there exists threshold Φö IR such that,
9 (a. Z, y) (So(z, y) %
(8)
where 9 is the optimal solution to (7). This automatically results that the relaxed optimization problem (7) is equivalent to the original integer problem (6), as the optimal solution to (7) is of the integer form. That to say, f == g" is also the optimal solution to (6). We now focus on g" and show that one can rewrite the same decision rule in the form that is described in Theorem 3.2.
The decision rule, 9", depends solely on the level sets of Sg. Here, the key observation the set of selected labels depends on the level-sets of the function g". rather than the values it takes. We may therefore apply any strictly decreasing transformation So without changing the selected labels. First, translate the EE row by +1 to obtain
(1 p(y x),
y マ EE,
S (r. v)
2 p(EE)a)
EE.
To ensure this transformation does not interfere with the ordering of the original labels, we require that is sufficiently large. This guarantees that for any y * EE, have p(E x) p(y x),
so the EE score in So is strictly greater than the scores assigned any concrete label (here also used the fact that py ι) > 0, which is true as is one of the "seen" samples, hence the probability of it should be non-zero). Then, shifting the EE score by +1 preserves the separation of score ranges: all concrete labels lie in (0, 1] and EE lies in (1,2).
Next, apply the strictly decreasing map t. ~ 2 X(2 t) on (1, 2]: this leaves the concrete labels untouched and sends the score to p(EE z). The resulting score
p x)
y サ EE
S(x v) 2 p EE x))
y = EE
induces exactly the same selection rule and matches (5). That is, the optimal solution to is of the form: (y S(x, S } for some d E This concludes the Theorem 3.2.
B.3
Proof of Theorem 4.1
Proof of Theorem 4.1 (Coverage Validity).
Define the conformity scores:
8 = (X,, Yi), V(X,, Yj) E Dealg and
8test S( 3(Xeest: Vrest)
The prediction set defined as:
C(Xtest) = {v E )U ((Xtest, 8) S 9"), where q = -ua SN 00).
We now derive a chain of equalities and inequalities:
(a)
(0)
Pr[Veest E C(Xtest))
Pr[Stest
S
Pr Stest (s N2z 20)]
No+1
E
I [s: S Quantile, 1 (81, ........ 8N2 Stest
N
1=1
a,
where,
(a) By definition of the prediction set and q²
(b) Follows from exchangeability of the scores {81,... 8Ng, Stost), since (Xtest, Yustt) is exchangeable with the calibration pairs.
(c) By definition of the (1 a)) quantile, at least a 1 a fraction of the N2 + values are less than or equal to it.
Therefore, we conclude:
Pr(Yuest C(Xtest)) 2 a,
required.
20

---

C Further Experiments and Details
C.1 Sub-optimal calibration procedure
In our fine-graine fine-grained, component wiss comparisons, employ simple yet valid calibration rule to ensure empirical coverage at the target level 1 - a. This serves as a sub-optimal but interpretable baseline for evaluating the contributions of each algorithmic principle.
To calibrate, we perform a grid search over a set of candidate thresholds (TI,..., Tm C [o, 1], uniformly spaced across the interval. For each candidate threshold т;, we apply the following two-step procedure on the calibration data (2,, 3k )== (i) include the fallback EE cluster in the prediction set if its estimated probability satisfies P(EE) 2 TN. (ii) sort the remaining clusters by their probabilities in descending order, and sequentially add them to the prediction set until the cumulative probability mass exceeds T₁- We then compute the empirical coverage at each threshold:
cou(TT)) Σ ts E Cr,(
where Cr, (z.) denotes the prediction set constructed with threshold T,. We choose T min(r E (T1...., F coo(T;) 2 a).
At test time, we construct prediction sets using the calibrated threshold r* via the same two-step strategy: include EE if its predicted probability satisfies P(EE) 2 r", and then add remaining non-EE clusters in order decreasing probability until the cumulative mass exceeds T".
C.2 Performance across different budget values
To assess the robustness of each algorithmic component under varying resource limits, we conduct experiments at two additional budget levels for every dataset. These settings are chosen to span regimes where additional queries provide substantial gains (low budget) versus diminishing returns (high budget). Figure 2 shows that in all settings, progressively adding adaptive optimal querying (principle 1) and conformal calibration (principle 2) consistently improves or maintains performance relative to the vanilla baseline. Notably, the largest reductions in EE fre-fration occur under tighter budget constraints-when the average number queries per input is small relative to the model's inherent uncertainty and the difficulty of the dataset. In these regimes, adaptive querying provides the greatest benefit by allocating queries more strategically, thus increasing the likelihood observing informative labels. In contrast, when the budget is generous enough that most correct answers already revealed through uniform sampling, the marginal gains from adaptive querying diminish but never harmful.
These results collectively reinforce that CPQ delivers targeted gains with the addition of each optimal modular component.
C.3 Additional comparison with baselines
In this section, we provide further comparison of our algorithm CPQ with CLM and SCOPE-Gen across varying nominal coverage levels for each dataset. Since scope-gen and CLM do not explicitly control the query budget; their number of queries varies depending on the dataset and the desired coverage level. To ensure a fair comparison under shared resource constraints, we first compute the average number of queries used by both CLM and SCOPE- at each coverage level, and configure CPQ to operate under the minimum of these two query budgets. While this setup may disadvantage CPQ in cases where a baseline uses larger query budget, Table 2 shows that CPQ still consistently achieves tighter empirical coverage and lower EE fractions.
C.4 Robustness under high hallucination rates
LLMs are inherently prone to hallucinations. While all of our experiments involve black-box LLMs which already exhibit nontrivial hallucination behavior, we additionally evaluate robustness under settings with elevated hallucination rates. To this end, in this section we consider SimpleQA, an adversarial benchmark specifically designed to expose hallucination failures in GPT models.
21

---

Coverage
Average
36++ 18 20)
cassage
yex
0.
P3-F3
0.2
0.
0.3
0.0
0.5
Fraction
Verix
0.5
+-
MAcra:: Sct Sue
BBe-Date IB Geo
0.5
0.0
09
0.5
0.5
0.0
0.9
0.5
135
Obverage
EC Fraction
Avstage Set Size
Set Ste
cowery
Coverage
Froction
Merrage Set Size
9BI-Date 251
P2:12
Pycroo 200
x=
055
1.-0
0.35
Sandi
Ven
GSABK 30)
CE/rection
2.5
0.53
0.80
0.02
1.5
0.78
0.0
0.00
0.94
0.66
0.00
0.00
3.00
0.50
6.04
0.66
3.60
8.00
0.32
3.87
2.04
1.56
3.52
3.00
Traction
4.0
Wiil
0.10
GSMBK (8
0.35
11400 21099 01001
(1901
2.00
2100
0.00
1100%
3.50
0.40
Figure 2: Comparison of the fine-grained variants pariants-vanilla baseline, optimal adaptive querying strategy (Principle 1), and full CPQ (Principles + --ndder different budget levels for each dataset. For BBH-Grometric Shapes, the corresponding budget levels are 20 and 40 for BBH Date Understanding. 10 and 25; and for GSM8K, 20 and 30. Shaded regions correspond the standard deviation over ten independent runs.
22

---

Dataset
Algorithm
Nom. Cov.
Emp. Cov.
EE Frac.
GSM8K
CLM
0.97
0.93 1 0.02
0.74 +: 0.09
Scope-Gen
0.97
0.93 + 0.05
0.56 + 0.32
CPQ
0.97
0.96 0.02
0.48 + 0.15
CLM
0,90
0.89 + 0.05
0.54 + 0.14
Scope-Gien
0.90
0.86 + 0.06
0.10 + 0.12
CPQ
0.90
0.89 + 0.03
0.00 + 0.00
CLM
0.85
0.86 1 0.05
0.48
Scope-Gen
0.85
0.07
0.01
CPQ
1.8400004
0.00 0.00
CLM
0.80
0.83 - 0.03
0.48 0.04
Scope-Gen
0.80
0.84 + 0.02
0.00 0.00
CPQ
0.80
0.79 1 0.03
1.00
BBH Geometric Shapes
CLM
0.90
0.05 0.88 0.05
0.77 0.05
Scope- Gen
0,90
0.95
0.93 0.05
CPQ
0.90
0.90
0.06
CLM
0.80
0.73
0.60
Scope-
0.80
0.85
0.06
CPQ
0.80
0.81
0.52
CLM
0.70
0.65 + 0.07
0.08
Scope-Gen
0.70
0.80 0.05
0.70
CPQ
0.70
0.70 0.06
0.20
CLM
0.50
0.42 1 0.08
0.21 0.06
Scope-Gen
0.50
0.58 1 0.10
0.12 0.19
CPQ
0.50
0.50 + 0.07
0.00 + 0.00
BBH Understanding
CLM
0.90
0.84 0.06
0.63 + 0.08
Scope-Gen
0.90
0.96 0.05
0.92 0.10
CPQ
0.90
0.90 0.03
0.72 1 0.06
CL.M
0.80
0.72 + 0.10
0.41 + 0.12
Scope-Ges
0.80
0.88 + 0.04
0.71 0.05
CPQ
0.80
0.81 1 0.04
0.47 0.06
CLM
0.60
0.52 0.08
0.12 2 0.05
0.05
Scope-Ger Gen
0.60
0.68 0.06
0.33 - 0.08
CPQ
0.60
0.61 0.610000 0.06
0.06
CL.M
0.50
0.45 + 0.08
0.05 0.05
Scope-Gen
0.50
0.60 0.08
0.07
CPQ
0.50
0.51 1 0.08
0.00 1 0.01
Table 2: Comparison of CPQ with CLM and SCOPE-Gen across nominal coverage levels on GSMSK,
BBH-Geometri Shapes, and BBH-Date Understanding, CPQ is constrained the lowest average query budget used by the baselines at each coverage level. Despite this restriction, CPQ maintains tighter empirical coverage and lower EE fractions.
23

---

Table 3 reports our results on GPT-4o generations under this high- sighhaallucination setting, Even in this challenging regime, we observe consistent improvement using our method, following the same trends observed in the main body.
Algorithm
1
Emp Cov = Std
EE = Std
Avg Set Size + Std
Vanilla
0.60
0,62 + 0.04
0.16 0.03
0.85 0.02
PI
0.60
0.59 = 0.06
0.11 0.03
1.20 + 0.14
P1 P2 (CPQ)
0.60
0.61 0.05
0.04 + 0.04
3.47 + 0.53
Vanilla
0.65
0.63 + 0.06
0.19 0.05
0.89 0.07
P1
0.65
0.63 + 0.06
0.16 0.05
1.28 + 0.14
Pl + P2 (CPQ)
0.65
0.65 0.05
0.11 + 0.06
2.89 0.67
Vanilla
0.70
0,68 = 0.07
0.23 - 0.06
0.89 0.03
P1
0.70
0.68 = 0.05
0.22 0.04
1.04 + 0.04
P1 + P2 (CPQ)
0.70
0.69 = 0.04
0.18 + 0.06
1.93 + 0.58
Vanilla
0.80
0,82 = 0.06
0.48 + 0.10
1.15 + 0.21
Pl
0,80
0.79 0.06
0.41 0.11
1.77 + 0.80
P1 + P2 (CPQ)
0.80
0.79 = 0.05
0.40 + 0.09
1.70 + 0.18
Table 3: Performance under high hallucination rates (SimpleQA, GPT-4o)
C,5
Clustering algorithm
To group semantically equivalent answers, apply relaxed clustering procedure based pairwise entailment checks using LLaMA-3-8B [35]. Given a question æ and two candidate responses V/1 and /2, we query LLaMA-3-8B 3-BB twice:
to determine whether y/1 entails 1/, and once for the reverse direction. We declare two responses as a match under a relaxed bidirectional entailment criterion: one direction must return entailment, and the other must return either entailment or neutral. This relaxation tolerates mild asymmetries when one answer adds detail without changing the core meaning. Using this matching function, construct clusters through simple iterative merging process. Each response is compares against existing clusters, and added to the first cluster containing match; otherwise it initiates produced highly coherent clusters in practice and was robust across datasets. We emphasize that CPQ agnostic the particular clustering routine used. Any method that produces coherent and valid whetter heuristic, learned, or rule-based-cam be substituted.
cluster. This bucket-merge strategy, while simple,
Below provide the exact system and user prompts used for LLaMA entailment checks, followed by the pseudo code for our relaxed clustering procedure:
System:
You are expert at determining semantic entailment between answers to questions. Given question and answers, determine if Answer entails Answer 2. Respond with only one word: entailment, contradiction, or neutral.
User:
Question:
<QUESTION>
Answer <RESP1> Anaver 2: <RESP2>
Does Answer semantically entail Answer 2?

---

Algorithm 2 Relaxed Entailment Clustering
Input: question z, responses {y 1
MATCH Function (via LLaMA)
I: function MATCII(,, a, b)
entl LLaMAEntail(r, a.
3: ent2 + LLaMAEntail(z; a)
refurn (entl entailment and ent2 fentailment, neutral))
end function or (ent2 = entailment and entl E {entailment, neutrrl )
Clustering
Initialize empty cluster set: C C-
for each response yi E (yi....,yT
Ur
if c E C, y such that (x,CH( y/, v) returns True: add y: to cluster
else: create new cluster {y:} and add it to
Output: clusters C
C.5.1
Comparison of alternative clustering methods
Although clustering is not the primary focus of our work, serves necessary pre-processing step when applying our method to natural language outputs. To ensure that our conclusions are sensitive to the particular clustering strategy used, we conducted an ablation study comparing several representative methods on the TriviaQA dataset and evaluated their effect on our algorithm's s downstream performance. We considered the following clustering methods:
I.L.MA---BB Entailment (default): Pairwise entailment queries between responses using LLaMA-3-8B.
W2V: Averaging 300-dimensional Word2Vec embeddings per response and clustering with KMeans
Cosine similarity: Embedding each response with MiniLM encoder and linking responses with cosine similarity 2 0.85.
NLI-based: using fine-tuned RoBERTa-LLarg model instead for entailment.
evaluate across two metrics, namely pairwise overlap and Jaccard similarity (intersection-overr union of clusters across methods), well as downstream CP metrics (coverage, EE fraction) to evaluate the impact of clustering variation on the behavior our algorithm. As shown in Table 4, all clustering methods produced highly consistent partitions of the model outputs, with pairwise overlaps exceeding 0.88 and Jaccard similarities above 0.80. The downstream CP results in Table confirm that these differences in clustering had only minimal effect on the final results. Across all methods, the coverage and EE fraction difference remained statistically insignificant. These results suggest that long semantically similar outputs grouped reasonably well, the specific clustering method has little effect on overall performance. That said, clustering remains an active research area, especially for very long-form domain-specific generations, and can leverage advances in NLP to fit their particular use cases.
D Missing Mass and Missing Mass Derivative
In this section, we will first derive an estimator for the missing mass derivative introduced in Section and then empirically evaluate its performance two synthetic distributions.
25

---

Method Pair
Overlap
Jaccard
RoBERTa vs M
0.91
0.91
RoBERTa vs W2V
0.90
0.83
RoBERTa vs LLaMA
0.88
0.81
Cosine-MiniLM W2V
0.95
0.82
Cosine-MiniLMM vs LLaMA
0.94
0.83
W2V LLaMA
0.93
0.87
Table 4: Average Pairwise Overlap and Jaccard Similarity Between Clustering Methods
Clustering Method
1 a
Coverage
EE Fraction
RoBERTa
0.8
0.81 + 0.03
0.42 + 0.05
0.6
0.61 + 0.02
0.09 + 0.02
W2V
0.8
0.81 + 0.02
0.44 + 0.04
0.6
062+0.00
0.10 0.02
Cosine-MiniLM
0.8
0.82
0,44 0.05
0.6
0.62 + 0.03
0.03
0.09 + 0.02
LLaMA (default)
0.8
0.80 = 0.02
0.42 = 0.02
0.6
0.61 = 0.02
0.08 + 0.01
Table 5: Performance of CPQ with Different Clustering Methods on TriviaQA (LLaMA-3-8B Generations)
D.1 Derivation
In this section, we study the problem of estimating the missing mass and its rate of change. We abstract away from any specific context (such as input z) and define the missing mass problem in general form. The missing mass the probability of observing previously unseen label if we were to draw one additional sample after observing t f.id. samples from discrete distribution. The classical Good-Turing estimator addresses this problem. Here, we derive an estimator for the derivative of the missing mass, which quantifies the rate at which the mass of unseen labels is shrinking more samples are collected.
We begin by introducing some key quantities and explaining generative process that mirrors the derivation of the classical Good-Turing estimator, following the notation and exposition from [70]. We then use similar principles to derive an estimator for the rate of change in the missing mass.
Let ) be the label space, and W denote the sequence of T independent samples W f........ w. where Wk E y. Let 0y be the probability that a future sample will be yy, where we'd like to account for the probability of yj occurring even if it has not appeared in the sample W. Thus, simple frequency #(ys) in W. Throughout this derivation, we assume that 0g Oy if #(r)) #(,,), ). thus appear the same amount of times if they have the same probability of occurring. This assumption also needed for the classical derivation of the Good -uring estimator. Though not realistic, this assumption reduces the number of parameters significantly.
T does not suffice, where #(y;) is defined as the number of times label yj E y appears samples
Let N, Ky; #(w,) r}] be the number of labels that occur exactly times in W. Let (r) denote the probability of a label occuring given that it appeared r times in W.To derive an estimate for (rr), consider the following generative process: assume have access to 6y. Draw j and hence also 8y uniformly at random from the label space y. Then. flip a coin times, where 8, is the probability of success. Then the number of successes is the number of times yj appears. if yJ appears times, put 0, in (r)). At the end ((r) will approximately be the average of the 02 for which #(u)) = r.
Precisely
((r) E E6 (w2)) -
50,P #(1)) =r]
26

---

Now, condition on 8g by applying Bayes rules, and given the uniform prior on P(O,) = 1 we obtain the following for the probability of a yj appearing given that it has appeared r times
P(+)))))) 0,]
Σx (r
We can rewrite both the numerator and the denominator in terms of the pdf of the binomial distribution:
-,)
Σ, 8, (,)r (1-8, (1-8)))-
We can rewrite the denominator in terms of Ein [Nr]. the expected value of Nr given that we flipped t coins at each step of our experiments, yielding the following equation:
Σ 03
8 -,) 8,)
Em c[N,,]
This quantity is estimating the probability of a label conditioned on it appearing exactly r times in the sample-that that is, the expected value of 0, given # (y,) However, what we actually want is the total probability mass of all such labels. To obtain that, we need to multiply the average by the number of labels that appeared times. Notably, the denominator of the expression we derived is E[N,], the expected number of such labels. So in fact, the numerator alone gives an estimation of the total probability mass.
Furthermore, we'd like to derive and estimate of the change in missing mass, we set r = 0,thus we are interested in the following quantity:
01-(10 -
E0, - -0,)² = =E --0(1-0,))
-2
Σ
(1+2)
03 -0,)*
(t+ 2)(t 1)
2
(a)
-2
Ein 0+2 [22
(++ +1)
(M)
-2
(2
where (a) follows from the fact that Em +22 N2] = E, (tt2) 0,)² which is due to a simple counting argument. (b) is due an approximation for sufficiently large t, and plugging N2 as Ein 1+2 N2).
Hence, this yields our proposed estimator introduced in Section 4 for the missing mass rate of decay
-2 t²
(t)
D.2 Empirical evaluation
We conduct experiments two synthetic distributions over support of size 100: (i) uniform distribution, ग. = 1/100 for all i, and (ii) geometric distribution, मं = p p [1pppp--1 with p = 0.05.
Figure 3 presents two panels for each distribution. In the left panels, compare the true missing mass (t) (red dashed) against the Good-Turing estimate O(t) (blue solid). In the right panels, we compare the true derivative (red dashed) against our proposed derivative estimator Á(t) -2N²
(blue) and the naive finite-diffent -iffe-diffeeeece of the Good-Turin Turing estimator baseline Á(t) 0(t + 1) 0(t) (Green). Across both distributions, the Good-Turing estimator closely tracks the ground truth and its variance decays as more observations are collected. Similarly, our estimator closely captures the decay rate of the missing-mas. derivative with substantially lower variance and fluctuations than the naive difference-based baseline.
27

---

Missing Mass (Uniform)
Derivative Estimates it s 15) (Uniform)
1,2
0.2
True missing mess
1.0
GT estimate
0.1
0.8
0.0
-0.1
0.4
-0.2
True derivative
0.2
estimator
Direct GT-d fffrrncc
10
20
30
40
50
8
10
12
Missing Mass (Geometric)
Derivative Estimates it 15) (Geometric)
True missing mess
0.2
GT estimate
0.0
-0.2
True derivative
0.2
Our estimator
Direct GT Giffrreeeecce
-0.6
10 20 30
10
Figure 3: Empirical comparison of missing mass and its derivative estimators on two synthetic distributions: uniform (top panels) and geometric with p= 0.05 (bottom panels). Left panels: true missing mass (red dashed line) versus the Good-Turing estimator (blue solid line). Right panels: true derivative (red dashed line) compared
proposed derivative estimator (blue) and the naive finiteddifference baseline (green). The standard deviation after averaging across 100 independent trials is represented by the shaded region in each corresponding color.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
All of our contributions and claims are properly explained in the abstract and introduction
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
We discuss the limitations our current work and possible avenues for future research in separate section called Limitation and Future work.
Justification:
28

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Due to space limit, we have moved all the proofs to the supplementary material, where we show full derivations the proofs carefully, and clearly state all assumptions. We provide references for technical details as needed. Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our experimental setting well explained in the main body the paper, with specifics and all extra details of the implementations provided in the supplementary material due to space limit. Further, we will publish our code for the camera ready version case of acceptance.
29

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will publish our code for the camera ready version in case of acceptance, and we will ensure instructions are clearly stated.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / ciitps.cc/uubbice http:/ubllggggidess../p /twpgdde/oeeeeueeiiiiiiiieee htt.///ummmissiiooooooo.oooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
30

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details needed for self-contained experiments section are provided, the main body. Further specifies are provided in the appendix for completeness and exact reproducibility.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, provide all necessary statistics including error-bars for fair compari- son.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
31

---

Justification: To generate responses from the LLM, we can rely on API access which would remove the need for local GPU resources. The estimated total run-time of the experiments for this paper is in order of 3-5 hours, with majority of the time spent querying the L.M. The algorithm itself after these generations, runs matter of few minutes. Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / http:///wwwrips.pppiiiiiieeeeeee
Answer: [Yes]
Justification: This paper has no forsecable ethical issues.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We propose a general framework for quantifying the uncertainty with LLMs, which can have positive direct societal impact and applications in all application of LLMs, including areas such as healthcare. We do not anticipate any negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
32

---

11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do see any foreseeable need for safeguards.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We have cite and credited all models and datasets used in our experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. wwt.cooo///////e com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There is no new asset as an output.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
33

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
our experiments do not involve human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: Our paper does not include such studies.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core methods do not involve LLM as any important, original, or non- standard component.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non con-standard components.
Please refer to our LLM policy (https / //nuriurip..../ //oo/offreecee/22255 for what should or should not be described.
34


Reviews:
[{"review_id": "HKjfuHs5U9", "reviewer": "Reviewer_ZMjq", "summary": "This paper studies conformal prediction for LLMs. It focuses on a setting with only query access to black-box LLMs. The authors propose Conformal Prediction with Query Oracle (CPQ), a framework that balances coverage, informativeness, and query budget. Specifically, CPQ consists of two stages. First, a query budget is determined based on a missing-mass estimator. The LLM is then queried for that specific number of times, and a final prediction set is constructed from the sampled responses by thresholding a conformity score. Experiments on three real-world benchmarks demonstrate the effectiveness of the proposed method.", "questions": "Please see weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper is well written. Although involving many technical contents, it achieves a good balance between including enough details and background for understanding, as well as deferring detailed proof to the appendix. The practical algorithm is also well motivated by the theoretical analyses.\n2. Experiments show that the method has a smaller EE fraction, demonstrating the informativeness of the prediction set.\n\nWeaknesses\n1. All three datasets focus more on the reasoning tasks. It would be better if the authors could demonstrate the effectiveness on other tasks, e.g., factual QA.\n2. Results in Figure 1 are a bit difficult to interpret, especially on the size of the prediction set, which first increases and then decreases. My understanding is that it's because of EE fraction. But it's hard to compare across different methods when the two metrics entangle.", "was_revised": true, "final_justification": "The authors' response has addressed my issues, so I have raised my score.", "rebuttal": "We thank the reviewer for their thoughtful feedback. We're glad you found the paper well written, clearly organized, and supported by sound experimental evidence. Below we respond to each of the concerns you raised.\n\n### **Evaluation beyond reasoning benchmarks (e.g., factual QA):**\n\nThank you for this suggestion. We also agree adding other types of datasets (non-reasoning) can enrich our experimental demonstration. In response, we conducted additional experiments on factual QA tasks. These new experiments include:\n- **TriviaQA**, a widely used open-domain factual QA benchmark.  \n- **SimpleQA**, an adversarial dataset where even GPT-4o achieves only <~30% EM accuracy in our experiments.\n\nAdditionally, for these new datasets, we conduct experiments on larger black-box models, including **GPT-3.5-turbo** and **GPT-4o**, in addition to LLaMA-3-8B, which was used in the experiments already reported in the paper.\n\n**Across all settings, we observed consistent trends with the results presented in the main paper**. Specifically, our method consistently improves the EE fraction when such improvement is feasible (i.e., at moderate coverage levels), and yields smaller average set sizes at higher coverage levels where reducing the EE fraction becomes increasingly difficult. For a more detailed discussion on how to interpret the trade-off between EE fraction and set size, please refer to the section **Interpreting Figure 1** toward the end of this rebuttal.\n\nIn what follows, we provide a summary of these new results, and we will add a more detailed report in the revised version.\n#### **SIMPLE QA – GPT-4o**\n\n| Algorithm           | 1 - α | Emp Cov ± Std    | EE ± Std        | Avg Set Size ± Std |\n|:--------------------|:-----:|------------------:|-----------------:|--------------------:|\n| Vanilla             | 0.60  | 0.62 ± 0.04       | 0.16 ± 0.03      | 0.85 ± 0.02         |\n| P1                  | 0.60  | 0.59 ± 0.06       | 0.11 ± 0.03      | 1.20 ± 0.14         |\n| P1 + P2 (CPQ)       | 0.60  | 0.61 ± 0.05       | **0.04 ± 0.04**  | 3.47 ± 0.53         |\n| ---                 |       |                   |                  |                     |\n| Vanilla             | 0.65  | 0.65 ± 0.06       | 0.19 ± 0.05      | 0.89 ± 0.07         |\n| P1                  | 0.65  | 0.63 ± 0.06       | 0.16 ± 0.05      | 1.28 ± 0.14         |\n| P1 + P2 (CPQ)       | 0.65  | 0.65 ± 0.05       | **0.11 ± 0.06**  | 2.89 ± 0.67         |\n| ---                 |       |                   |                  |                     |\n| Vanilla             | 0.70  | 0.68 ± 0.07       | 0.23 ± 0.06      | 0.89 ± 0.03         |\n| P1                  | 0.70  | 0.68 ± 0.05       | 0.22 ± 0.04      | 1.04 ± 0.04         |\n| P1 + P2 (CPQ)       | 0.70  | 0.69 ± 0.04       | **0.18 ± 0.06**  | 1.93 ± 0.58         |\n| ---                 |       |                   |                  |                     |\n| Vanilla             | 0.80  | 0.82 ± 0.06       | 0.48 ± 0.10      | 1.15 ± 0.21         |\n| P1                  | 0.80  | 0.79 ± 0.06       | 0.41 ± 0.11      | 1.77 ± 0.80         |\n| P1 + P2 (CPQ)       | 0.80  | 0.79 ± 0.05       | **0.40 ± 0.09**  | 0.70 ± 0.18         |\n\n#### **TRIVIAQA – GPT-3.5-Turbo**\n\n| Algorithm           | 1 - α    | Emp Cov ± Std    | EE ± Std        | Avg Set Size ± Std |\n|:--------------------|:----:|------------------:|-----------------:|--------------------:|\n| Vanilla             | 0.60 | 0.58 ± 0.06       | 0.08 ± 0.04      | 1.61 ± 0.31         |\n| P1                  | 0.60 | 0.58 ± 0.06       | 0.08 ± 0.04      | 1.52 ± 0.38         |\n| P1 + P2 (CPQ)       | 0.60 | 0.60 ± 0.07       | **0.01 ± 0.01**  | 5.34 ± 1.36         |\n| ---                 |      |                   |                  |                     |\n| Vanilla             | 0.65 | 0.63 ± 0.06       | 0.15 ± 0.05      | 1.76 ± 0.32         |\n| P1                  | 0.65 | 0.64 ± 0.06       | 0.14 ± 0.05      | 1.68 ± 0.30         |\n| P1 + P2 (CPQ)       | 0.65 | 0.64 ± 0.06       | **0.06 ± 0.05**  | 5.42 ± 1.09         |\n| ---                 |      |                   |                  |                     |\n| Vanilla             | 0.70 | 0.69 ± 0.06       | 0.23 ± 0.06      | 1.54 ± 0.28         |\n| P1                  | 0.70 | 0.68 ± 0.06       | 0.22 ± 0.07      | 1.43 ± 0.17         |\n| P1 + P2 (CPQ)       | 0.70 | 0.69 ± 0.07       | **0.15 ± 0.09**  | 3.90 ± 1.54         |\n| ---                 |      |                   |                  |                     |\n| Vanilla             | 0.80 | 0.78 ± 0.05       | 0.38 ± 0.07      | 2.35 ± 0.57         |\n| P1                  | 0.80 | 0.78 ± 0.06       | 0.40 ± 0.09      | 2.46 ± 0.65         |\n| P1 + P2 (CPQ)       | 0.80 | 0.79 ± 0.07       | **0.39 ± 0.07**  | 1.05 ± 0.52         |\n\n\n#### **TRIVIAQA – LLaMA3-8B**\n\n| Algorithm           | 1 - α    | Emp Cov ± Std    | EE ± Std       | Avg Set Size ± Std |\n|:--------------------|:----:|------------------:|----------------:|--------------------:|\n| Vanilla             | 0.60 | 0.61 ± 0.02       | 0.21 ± 0.01     | 0.82 ± 0.05         |\n| P1                  | 0.60 | 0.61 ± 0.03       | 0.16 ± 0.03     | 1.30 ± 0.07         |\n| P1 + P2 (CPQ)       | 0.60 | 0.60 ± 0.03       | **0.10 ± 0.03** | 2.99 ± 0.36         |\n| ---                 |      |                   |                 |                     |\n| Vanilla             | 0.65 | 0.67 ± 0.05       | 0.30 ± 0.05     | 0.83 ± 0.12         |\n| P1                  | 0.65 | 0.66 ± 0.02       | 0.25 ± 0.02     | 1.17 ± 0.08         |\n| P1 + P2 (CPQ)       | 0.65 | 0.66 ± 0.04       | **0.21 ± 0.05** | 1.93 ± 0.32         |\n| ---                 |      |                   |                 |                     |\n| Vanilla             | 0.70 | 0.70 ± 0.03       | 0.34 ± 0.04     | 0.81 ± 0.05         |\n| P1                  | 0.70 | 0.71 ± 0.04       | 0.30 ± 0.03     | 1.17 ± 0.05         |\n| P1 + P2 (CPQ)       | 0.70 | 0.71 ± 0.04       | **0.28 ± 0.03** | 1.39 ± 0.16         |\n| ---                 |      |                   |                 |                     |\n| Vanilla             | 0.80 | 0.81 ± 0.04       | 0.52 ± 0.06     | 1.02 ± 0.03         |\n| P1                  | 0.80 | 0.80 ± 0.04       | 0.46 ± 0.05     | 1.37 ± 0.14         |\n| P1 + P2 (CPQ)       | 0.80 | 0.80 ± 0.04       | 0.46 ± 0.05     | 0.62 ± 0.10         |\n\n### **Interpreting Figure 1**\nwe’re happy to clarify the trends in Figure 1 and how to interpret the interaction between the EE fraction and the average prediction set size. \nThe average set size reported in the figure refers to the average number of explicit labels (excluding EE) included in the prediction set. When EE is included, it signifies complete uncertainty over the remainder of the label space, effectively making the set size infinite.\n\nThus, when comparing two methods, one should first examine the **EE fraction** (the smaller, the better). If the EE fractions are similar (which often occurs at higher coverage levels), then the **average set size** becomes the distinguishing factor (again, smaller is better). This trade-off between EE and set size is precisely what our algorithmic framework is designed to capture.\n\nAt moderate coverage levels, where EE labels can potentially be avoided, our method significantly reduces the fraction of EE in the prediction sets. At higher coverage levels, where including EE becomes unavoidable to guarantee coverage, our method instead focuses on reducing the average set size, making the non-EE prediction sets more practical and informative.\n\nThis behavior is enabled by the careful design of the two key principles discussed in the paper. It is also reflected in the plots: as we sweep the value of $(1 - \\alpha)$ from low to high, the set size initially increases (to avoid using EE), then decreases (as including EE becomes necessary and the method adapts).\n\nIn other words, in the low-$(1 - \\alpha)$ regime, our method outperforms baselines by reducing EE inclusion. In the high-$(1 - \\alpha)$ regime, where all methods must include EE frequently, the advantage shifts to smaller prediction sets, while keeping the number of EE labels fixed.\n\nWe thank the author again for bringing this matter up, and we will revise the caption and text around Figure 1 to make sure this is clearly communicated in the revised version."}, {"review_id": "el34NmytIC", "reviewer": "Reviewer_YqEn", "summary": "This paper introduces CPQ, a framework for UC in generative models to address the challenge\nof constructing prediction sets when the true output may not be among sampled generations.\nThe key innovation is connecting optimal query policies and prediction set construction to the\nclassical missing mass problem in statistics. The authors introduce an abstract label EE to\nrepresent unseen outputs and derive two algorithmic principles for optimal query and optimal\nset construction for finite samples. The finite-sample algorithm maintains distribution-free\ncoverage guarantees while rely less on uninformative prediction sets compared to existing\nmethods.", "questions": "1. Can you compare to unsupervised clustering method with naïve embedding method\nlike word2vec? Would it feasible at all or more stable compared to relying on LLM\nembeddings?\n\n2. Is the gap between the proposed approximate optimization method significant enough\ncomparing to join optimization, especially in practice experiments?\n\n3. Is this method robust to shifted domains?\n\n4. Is this method practical/useful on larger models of size 70B+?\n\n5. Can this theory lead to an empirical p-value in terms of confidence, given EE fraction or\nwith extra assumptions?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe problem formulation addresses a real limitation in existing conformal prediction methods\nfor generative models. They introduce \"EE\" label to provide a reasonable way to handle\nscenarios where correct answers lie outside sampled sets, which also makes the original\nproblem somewhat more straightforward.\n\nTheorem 4.1 t to connect the problem to missing mass estimation reads sound and provides\ncoverage guarantees. Two algorithmic principles seem derived correctly. Though, as\nacknowledged by the authors, the decoupled optimization approach as an approximation to\nthe full joint optimization might be a limiting.\n\nThey’ve done fair comparison experiments showing improvement over baselines. They also did\nappropriate ablation studies.\n\nPaper is clearly written, providing a useful theoretical lens on perspective of missing mass.\n\n\nWeakness:\n\nExperimental scope seems limited focusing on just three benchmark datasets. Tasks are\nsimple and models are small. With the potential, more complex tasks should be tested. Also,\nimprovement seems minor considering the cost and imperfect oracles in real world, it raises a\nquestion on whether the work is practically impactful.\n\nAuthors mentioned clustering is critical which introduced extra indeterminacy, as well\nestimation of missing mass can be challenging at low sample situation.\n\nPerformance of semantic clustering from LLMs can vary dramatically. It needs a bit more\ndiscussion on the overhead of this part.\n\nBaselines were not originally designed for the same problem setting which makes the\ncomparison less fair.", "was_revised": true, "final_justification": "The authors have addressed many of my concerns. My assessment of the paper is that it makes a positive contribution, however, I remain unsure whether this rises to the level of acceptance at NeurIPS.", "rebuttal": "We thank the reviewer for their detailed and constructive feedback. We're glad they found the problem formulation meaningful, our theoretical perspective sound and useful, and the paper clearly written. Below, we respond to each of your comments and suggestions.\n\n## **Experimental Scope and Practical Impact + Q4) Practicality for large models 70B+**\nWe appreciate your feedback and agree that expanding the experimental scope can enrich our work. To clarify practical significance, we first note that the key metric in conformal prediction (CP) is efficiency, commonly quantified by prediction set size. In our context, two interrelated aspects determine practical utility: the fraction of sets including the EE label (\"EE fraction\") and the average size of prediction sets.\n\nIncluding EE signals full uncertainty over the label space, effectively making the set size infinite and the output uninformative. Thus, practical impact is best assessed by first minimizing the EE fraction. When EE fractions are similar (common at high coverage), the focus shifts to minimizing the average set size. Our framework is designed to optimize this trade-off:\n\n- At moderate coverage, it significantly reduces EE inclusion, improving informativeness.\n\n- At high coverage, where EE is unavoidable, it reduces the average set size, improving practical utility.\n\nMoreover, CP efficiency is known to depend on model accuracy. To reflect this, we intentionally designed our experiments to span a wide range of difficulty relative to the models used, covering best-of-N (5) accuracies from below 40% to above 90%, enabling evaluation across both strong and weak models.\n\nThat being said, we fully acknowledge the value of broader evaluations to larger-scale models and broader datasets. To further strengthen our experimental results, we have now expanded our evaluation to include:\n\n- **Larger models**: GPT-3.5-turbo, and GPT-4o, supplementing the smaller models used in the original submission.\n\n- **Additional datasets**: Two additional QA benchmarks --TriviaQA, a factual QA dataset, and SimpleQA, an adversarial benchmark notably challenging even for GPT-4o (achieving less than ~30% exact match accuracy in our experiments).\n\nThese new results are summarized in the table provided in our response to Reviewer ZMjq (omitted here due to space). A detailed report with plots will be added to the revised version. In short, **across all settings, we observed consistent trends with the results presented in the main paper.**\n\n\n## **Comparison of Clustering Methods**\nWhile clustering is not the contribution of our work, it is a necessary pre-processing step in applying our method to natural language outputs. To evaluate robustness to clustering, we compared four clustering methods on TriviaQA ( Table 1 ) and assessed the impact of each method on our algorithm’s downstream performance ( Table 2). **We found that as long as semantically similar outputs are reasonably grouped, the specific clustering method had minimal effect.**\n\nClustering methods evaluated:\n- **LLaMA-3 8B Entailment (default):**\n- **W2V:** Word2Vec avg + KMeans ( As per reviewer's suggestion)\n- **Cosine similarity:**  MiniLM-embeddings with cosine similarity ≥ 0.85.\n- **NLI-based:**  using a fine-tuned RoBERTa-Large model for entailment.\n\nWe report **Pairwise overlap** and **Jaccard Similarity** ( intersection-over-union of clusters across methods), as well as downstream CP metrics ( coverage, EE frac) in the table below.\n\n**Table 1: Average Pairwise Overlap and Jaccard Similarity Between Clustering Methods**\n\n| Method Pair                  | Overlap | Jaccard |\n|:-----------------------------|------------:|------------:|\n| RoBERTa vs Cosine-MiniLM |     0.91  |     0.91  |\n| RoBERTa vs W2V    |     0.90  |     0.83  |\n| RoBERTa vs LLaMA      |     0.88  |     0.81  |\n| Cosine-MiniLM vs W2V  |     0.95  |     0.82  |\n| Cosine-MiniLM vs LLaMA   |     0.94  |     0.83  |\n| W2V vs LLaMA       |     0.93  |     0.87  |\n\n**Table 2: Performance of CPQ with Different Clustering Methods on TriviaQA (LLaMA-3-8B Generations)**  \n(*All std < 0.05*) \n| Clustering Method   | 1 - α | Coverage | EE Fraction | \n|:--------------------|:-----:|:---------:|:------------:|\n| RoBERTa             | 0.8   | 0.81      | 0.42         | \n|                     | 0.6   | 0.61      | 0.09         | \n| W2V                 | 0.8   | 0.81      | 0.44         | \n|                     | 0.6   | 0.62      | 0.10         | \n| Cosine-MiniLM       | 0.8   | 0.82      | 0.44         | \n|                     | 0.6   | 0.62      | 0.09         | \n| LLaMA (default)     | 0.8   | 0.80      | **0.42**     | \n|                     | 0.6   | 0.61      | **0.08**     | \n\n**our key findings that address your questions:**\n- In our ablation study, switching between **different LLMs and clustering methods yielded comparable performance and CP metrics; no dramatic shifts were observed.**\n- Unsupervised **methods like Word2Vec + KMeans were feasible in our experiments.** Similarly the **impact on downstream CP metrics was minor and comparable to that of LLM-based clustering.**\n\nThese results suggest that as long as semantically similar outputs are grouped reasonably well, the specific clustering method has little effect on overall performance. That said, clustering remains an active research area, especially for very long‐form or domain-specific generations, and users can leverage advances in NLP to fit their particular use cases\n\n\n## **Imperfect Oracles and Costs**\nWe wanted to clarify that although the two principles are derived in a theoretical framework that assumes perfect oracles, our finite sample algorithm is designed for any (imperfect) oracle/LLM. Subsequently, all of our experiments are run with real-world, black-box LLMs. These models are inherently imperfect. The results show that the population-level principles lead to significant improvements in practice. \n\nAs for computational costs, our method is comparable to techniques like best-of-(N) sampling, widely used in practice, which query the model multiple times and select the best response. Our framework aligns with this paradigm but offers a principled way to decide how many queries to issue and when to stop. In high-stakes settings like medical decision-making, where decisions often take at least several minutes, this modest overhead is justified by the added reliability. Inference time for 10–20 queries typically ranges from a few seconds (small models) to a couple minutes (large models).\n\n**Practicality in very low query regimes**:  We provided a more detailed discussion on this setting in our response to Reviewer tHYJ.\n**When the query budget is very limited (e.g., ≤ 5), Principle 2 can still be used on its own and yield meaningful gains.**. Unlike Principle 1, which requires $N_2$ (doubletons), Principle 2 only depends on $N_1$ (singletons) via the Good–Turing estimator, which performs well even with few samples.\n\nTo illustrate this, we ran **an experiment with a fixed query budget of 5 per test point** (non-adaptive), applying only the calibration step from Principle 2.\n\n## **Fairness of Baseline Comparisons**\nAs the reviewer also noted, our work addresses a previously unsolved challenge in conformal prediction for generative models, namely, how to manage the three-way trade-off between coverage, test-time query budget, and the informativeness of prediction sets. Given the novelty of this problem, it is natural that no existing baseline fully aligns with the setting we aim to solve. That said, we took two steps to strengthen the robustness of our experimental evaluation. \n\n1. We conducted fine-grained ablation studies to isolate and assess the contribution of each algorithmic principle to the informativeness of the resulting prediction sets.\n2. We adapted, using the best available techniques, two recent conformal prediction methods that share our high-level objective: constructing valid prediction sets from LLM outputs. We also carefully tuned the query budgets to be favorable to these baseline methods, ensuring that the comparison remains as fair as possible.\n\n## **Other Questions:**\nQ2: Our framework, based on two derived principles, leverages the fact that the decoupled optimization admits closed-form solutions. In contrast, the joint optimization is significantly more complex: it lacks structural properties such as convexity and, to our knowledge, does not admit a closed-form solution. This makes it unclear how to design a practical finite-sample algorithm for the joint objective. Although the exact performance gap is difficult to quantify due to this intractability, our empirical results show that the decoupled approach performs strongly across tasks and models.\n\nQ3: Distribution shift is an active research area in the CP community, extending beyond LLM applications. In this work, we focused on CP challenges specific to generative modeling. That said, robustness to domain shifts is an important direction, which we will include in the future work section of the revised manuscript. As a starting point, one could integrate ideas from [1], e.g. calibrating a linear head on pretrained prompt representations via quantile regression instead of a scalar threshold calibration, potentially improving robustness. However, combining this with our missing mass framework remains an open question.\n\n[1]: Conformal prediction with conditional guarantees, Gibbs et. al.\n\nQ5: While we do not address p-value computation, there are related efforts in the literature that leverage conformal ideas to construct empirical p-values, e.g. in the context of outlier detection and multiple testing (e.g., Bates et al., 2021; Jin et al., 2022).\nExtending such ideas to our setting would require a careful treatment of the EE label and the missing mass, which introduce additional layers of uncertainty not present in standard CP, which is a promising direction for future research."}, {"review_id": "IiM5DebJnd", "reviewer": "Reviewer_mpV9", "summary": "The paper addresses uncertainty quantification of generative models of discrete sequences (where it is not feasible to enumerate the full label set) using conformal inference by introducing Conformal Prediction with Query Oracle (CPQ) which considers the trade-offs between coverage, query budget, and informativeness of the resulting prediction set. The paper introduces an algorithm for querying from the model and producing the prediction set from the queries, unifying both strategies via the missing mass problem.", "questions": "If the authors could comment on the above points under Weaknesses, that would be greatly appreciated, but I also understand that addressing some of these comments sufficiently would likely be another paper in itself.\n\nOn a separate note, to make the paper more self-contained, could the authors briefly describe the baseline methods as well?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The paper addresses the important question of uncertainty quantification of black-box generative models.\n- The paper provides an elegant conceptualization of how to construct the prediction sets and to end, starting from the strategy for querying.\n- The paper is clearly written, and the contributions are, to my knowledge, novel.\n- Experiments clearly show the benefits of the proposed algorithm.\n- The supplement does a good job explaining relevant concepts in the missing mass problem such that this paper can be self contained.\n\nWeaknesses:\n- Practically, the algorithm is quite expensive, requiring multiple generations from the model for each prompt. While I understand why this is necessary given the assumptions of the task, i.e., access only to a black box model, this limitation may prevent the use of the method in practice.\n- The canonical limitation that coverage is only marginal rather than conditional still applies in the setting, but this issue is a bigger one for conformal inference in general.\n- Small nitpick: the objective and the algorithm have the same name, which could get confusing for discussing this work.", "was_revised": true, "final_justification": "I appreciate the thorough response from the authors to both my review and the other reviews, and my positive review of the work still stands.", "rebuttal": "We sincerely thank the reviewer for their thoughtful and positive feedback. We're especially glad that you found the conceptual framework elegant, the contributions novel, and the paper clearly written. We also appreciate your recognition of the experimental validation and the clarity of the supplemental material in making the paper self-contained.\n\nBelow we will address the comments and questions made by the reviewer:\n\n### **Practical Cost of Querying**\nThank you for raising this thoughtful point. We agree that repeated querying can be costly in practice, especially for large models. However, there are three arguments here:\n\n1) **Querying is the only way to uncover the output space in black-box settings:** As you noted, when working with black-box generative models, querying is our only means of exploring the output space. Even with white-box access, for example to an LLM, it remains unclear how one could leverage internal representations to construct prediction sets. It’s important to emphasize that a prediction set must contain multiple fully plausible outputs, and in generative modeling, producing even a single output requires a full round of inference. That being said, computational cost is a central motivation behind our work. Our algorithmic framework is specifically designed to make the most out of a fixed query budget.\n\n2) **Moderate querying is already common in practice (e.g., best-of-\\(N\\) sampling):**  Techniques like best-of-\\(N\\) sampling, where a model is queried multiple times and the best response is selected, are widely used in practical applications. Our framework aligns with this paradigm but provides a principled way to determine how many queries to issue, and when to stop, to make useful prediction sets. The inference time for 10-20 queries lie somewhere between a few seconds (for smaller models) to a few minutes (for larger models) for a prompt in test time. In high-stakes applications such as medical decision-making, the decision-making process often takes more than a few minutes. In such cases, a modest increase in inference time may be well worth the additional reliability it provides.\n\n3) **Fallback in low-query regimes:**  \nImportantly, **when the query budget is very low (e.g. $\\leq 5$), one can still use the Principle 2 part of our algorithm alone!** Note that Principle 1 requires access to the value of $N_2$ (the number of double-tones), whereas Principle 2 only depends on $N_1$ (the number of singletons), as it estimates the missing mass using the Good–Turing estimator. Notably, it is well-documented in practice that the Good–Turing estimator based on $N_1$ performs reliably even with very few samples. To illustrate this, we conducted an experiment where the query budget is fixed at 5--querying each test point exactly five times (i.e., using a non-adaptive policy)--and applied only the calibration step guided by Principle 2. The results of this experiment are summarized in the table below ( more details can be found in our response to reviewer tHY). **In short, we still observe meaningful performance gains from applying our calibration module (Principle 2) when querying budget is extremely limited ( eg. <= 5)**. This highlights the practicality of our method even in such restrictive setting.\n\n**Budget = 5 queries – (Low Query Regime)**\n\n| Method   | 1 - α = 0.7 Coverage ± Std | EE ± Std | Size ± Std |   | 1 - α = 0.4 Coverage ± Std | EE ± Std | Size ± Std |   | 1 - α = 0.3 Coverage ± Std | EE ± Std | Size ± Std |\n|----------|------------------------|----------|-------------|---|------------------------|----------|-------------|---|------------------------|----------|-------------|\n| Vanilla  | 0.74 ± 0.06            | 0.59 ± 0.07 | 1.03 ± 0.09 |   | 0.42 ± 0.14            | 0.29 ± 0.15 | 1.05 ± 0.30 |   | 0.38 ± 0.04            | 0.21 ± 0.03 | 0.84 ± 0.15 |\n| P1       | 0.71 ± 0.07            | 0.56 ± 0.09 | 1.43 ± 0.09 |   | 0.40 ± 0.07            | 0.18 ± 0.05 | 1.58 ± 0.11 |   | 0.31 ± 0.06            | 0.09 ± 0.03 | 1.43 ± 0.27 |\n| **P2**   | **0.70 ± 0.06**        | **0.53 ± 0.06** | **0.96 ± 0.18** |   | **0.40 ± 0.09**        | **0.13 ± 0.07** | **2.40 ± 0.17** |   | **0.31 ± 0.08**        | **0.04 ± 0.04** | **2.28 ± 0.27** |\n| P1+P2    | 0.71 ± 0.07            | 0.53 ± 0.09 | 0.93 ± 0.06 |   | 0.40 ± 0.06            | 0.09 ± 0.06 | 3.18 ± 0.38 |   | 0.30 ± 0.06            | 0.004 ± 0.01 | 2.82 ± 0.55 |\n\n\n\n### **Conditional validity**\nThank you for bringing this up and also the kind wording. The problem of conditional coverage, as you noted, is an active area of research within the conformal prediction (CP) community and extends beyond CP applications involving LLMs. In this paper, our primary focus was advancing CP specifically for challenges arising in generative modeling, without explicitly addressing conditional coverage.\n\nThat said, conditional coverage is an important and promising direction for future work, which we plan to discuss explicitly in the revised manuscript. As a starting point, one could explore integrating our framework with recent techniques proposed by [1], which provides relaxed conditional coverage by replacing the scalar threshold (used in our current method) with a multi-dimensional calibration step. For instance, using their method, one might be able to calibrate a linear model head via quantile regression on representations derived from a pretrained model, thus achieving some levels of conditional validity.\n\nHowever, carefully exploring the precise implications, applicability, and practical implementation of integrating such methods with the missing mass ideas developed in our paper remains a valuable and open research direction.\n\n[1]: Conformal prediction with conditional guarantees, Gibbs et. al.\n\n### **Q – Brief Description of Baselines**\nThank you for the helpful suggestion. Due to space constraints, we originally omitted detailed descriptions of the baselines. However, we agree that including a brief overview would make the paper more self-contained and easier to follow. In the revised version, we will incorporate concise summaries of both **CLM** and **SCOPE-Gen** to clarify how they relate to our setting and evaluation. To describe each method briefly here:\n\n- CLM constructs a prediction set by sequentially sampling outputs from a language model. It stops once a calibrated conformal threshold indicates the set likely contains a correct answer. This threshold is computed during a separate calibration phase to guarantee coverage. However, if the model doesn’t generate the correct answer often enough (e.g., at high coverage levels), the method can’t find a valid stopping threshold and fails to return a set.\n\n- SCOPE-Gen improves on CLM by reducing the number of expensive “admissibility checks” needed during calibration—for instance, when a human expert needs to verify whether an output is valid (as in medical domains). Instead of sampling one-by-one like CLM, it starts with a large batch of outputs and prunes them using a sequence of filters. These filters are designed so that conformal guarantees still apply, but the number of checks needed is much lower.\n\n### **On the algorithm  and optimization name:**\nThank you for pointing this out. We really appreciate the thoughtful suggestion and agree that having the objective and algorithm share the same name could lead to confusion. In the revised version, we will rename the objective to better distinguish it from our finite sample algorithm (CPQ), while keeping the terminology aligned with the broader goals of the paper."}, {"review_id": "DdHAmPlJZI", "reviewer": "Reviewer_tHYJ", "summary": "The paper introduces CPQ, a framework for UQ in the query-only setting where prediction sets are constructed from queries to a generative model. CPQ is based on two components: a query policy, and a set mapping function. Notably, the query policy is based on the rate of decrease of the missing mass. The authors show on three tasks that CPQ yields informative predictions sets.", "questions": "- is the clustering robust enough in practice? for example, what happens if you change the LLM used to define the semantic equivalences, and what's the impact on the CP metrics\n- what happens in the low query regime?", "limitations": "The authors discuss the very low query regime as a possible limitation.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- the paper is very well-written \n- it tackles an important problem (UQ when the label space is unstructured, as is the case with text generation) and realistic setting (query only generative setting).\n- CPQ has finite sample coverage guarantees \n- the experimental results seem to suggest that the prediction sets are informative (based on the set's size and the fraction of EE labels)\n\nWeaknesses:\n- $\\hat{\\Delta}(x,t)$ is based on $N_2$, the number of samples that appear twice. When we don't have a lot of sampling budget, $N_2$ is likely to be $0$, meaning that the stopping condition is achieved. Hence additional results in this low-query setting might be interesting, for example via a sensitivity analysis on the budget. In the low query setting, it would be interesting to have an ablation where the authors use a fixed querying strategy, and their proposed calibration rule (hence a Principle 2 baseline)\n- as the authors admit it, the derivation of the estimator for $\\hat{\\Delta}(x,t)$ builds on quite a strong assumption that all samples appearing the same number of times have the same probability of occurring.\n- it would be interesting to check what is happening when $\\pi$ greatly differs from the ground truth $p$ (e.g. an LLM prone to hallucinations at some input points).", "was_revised": true, "final_justification": "I keep my recommendation for acceptance. The authors have provided detailed rebuttals that have addressed my questions.", "rebuttal": "Thank you for the clear and encouraging feedback. We're glad you found the paper well-written and recognized both the theoretical and practical strengths of our approach.\n\nWe appreciate your thoughtful suggestions and we have addressed each below:\n\n## **P2 baseline study: Fixed sampling + Optimal calibration rule** | **Low query regime**\nThank you for this insightful and interesting suggestion. To evaluate the effectiveness of our **Principle 2** in isolation we conducted an ablation where we used a fixed querying strategy and applied only our proposed optimal calibration rule. \nThese results confirm that **our calibration rule is effective even when adaptive querying is infeasible (e.g in very low query regimes),** and ensures our full algorithm (CPQ) remains beneficial under strict query budgets. A detailed report will be added to the revised manuscript.\n\nWe ran this study under two settings:\n- Moderate query budget (B = 30)\n- Low query budget (B =5)\n\nOur **Findings**:\n- In both regimes, **P2 alone improves over the vanilla baseline**, both in terms of reducing the prediction set size, and reducing the fraction of EE while maintaining coverage.\n- In the **low query regime**, as you also mentioned, the missing mass derivative becomes unstable, so adaptive querying alone (P1), is less effective. As a result, **P2 dominates** and **P1+P2 (CPQ) performs similarity to P2 only**.\n- In the moderate-query regime, where the derivative estimation is more reliable, combining P1 with P2  (CPQ) yields further gains over either principle in isolation--but **P2-only still provides meaningful improvements.**\n\n ### **Budget = 30 queries**\n\n| Method   | 1 − α = 0.7 Coverage ± Std | EE ± Std | Size ± Std |   | 1 − α = 0.6 Coverage ± Std | EE ± Std | Size ± Std |\n|----------|----------------------------|----------|-------------|---|----------------------------|----------|-------------|\n| Vanilla  | 0.70 ± 0.06                | 0.40 ± 0.07 | 5.92 ± 0.28 |   | 0.60 ± 0.07                | 0.20 ± 0.08 | 5.47 ± 0.31 |\n| P1       | 0.70 ± 0.06                | 0.29 ± 0.08 | 7.54 ± 0.35 |   | 0.60 ± 0.07                | 0.07 ± 0.06 | 7.23 ± 0.69 |\n| **P2**   | **0.71 ± 0.06**            | **0.31 ± 0.12** | **3.10 ± 1.10** |   | **0.60 ± 0.07**            | **0.03 ± 0.05** | **8.58 ± 1.39** |\n| P1+P2    | 0.71 ± 0.06                | 0.21 ± 0.12 | 7.38 ± 1.78 |   | 0.61 ± 0.07                | 0.01 ± 0.02 | 8.58 ± 1.39 |\n\n### **Budget = 5 queries – (Low Query Regime)**\n\n| Method   | 1 - α = 0.7 Coverage ± Std | EE ± Std | Size ± Std |   | 1 - α = 0.4 Coverage ± Std | EE ± Std | Size ± Std |   | 1 - α = 0.3 Coverage ± Std | EE ± Std | Size ± Std |\n|----------|------------------------|----------|-------------|---|------------------------|----------|-------------|---|------------------------|----------|-------------|\n| Vanilla  | 0.74 ± 0.06            | 0.59 ± 0.07 | 1.03 ± 0.09 |   | 0.42 ± 0.14            | 0.29 ± 0.15 | 1.05 ± 0.30 |   | 0.38 ± 0.04            | 0.21 ± 0.03 | 0.84 ± 0.15 |\n| P1       | 0.71 ± 0.07            | 0.56 ± 0.09 | 1.43 ± 0.09 |   | 0.40 ± 0.07            | 0.18 ± 0.05 | 1.58 ± 0.11 |   | 0.31 ± 0.06            | 0.09 ± 0.03 | 1.43 ± 0.27 |\n| **P2**   | **0.70 ± 0.06**        | **0.53 ± 0.06** | **0.96 ± 0.18** |   | **0.40 ± 0.09**        | **0.13 ± 0.07** | **2.40 ± 0.17** |   | **0.31 ± 0.08**        | **0.04 ± 0.04** | **2.28 ± 0.27** |\n| P1+P2    | 0.71 ± 0.07            | 0.53 ± 0.09 | 0.93 ± 0.06 |   | 0.40 ± 0.06            | 0.09 ± 0.06 | 3.18 ± 0.38 |   | 0.30 ± 0.06            | 0.004 ± 0.01 | 2.82 ± 0.55 |\n\n## **On the robustness of clustering**\nTo evaluate robustness to clustering, we compared four methods on TriviaQA and assessed their impact on our algorithm’s downstream performance. **We found that as long as semantically similar outputs are reasonably grouped, the specific clustering method had minimal effect.**\n\nClustering method evaluated:\n- **LLaMA-3 8B Entailment (default):** Pairwise entailment queries between responses using LLaMA-3-8B.\n- **Word2Vec + KMeans:** Averaging 300-dimensional Word2Vec embeddings per response and clustering with KMeans (as suggested by the reviewer).\n- **Cosine similarity:**  Embedding each response with a MiniLM encoder and linking responses with cosine similarity ≥ 0.85.\n- **NLI-based (RoBERTa-Large MNLI):**  using a fine-tuned RoBERTa-Large model instead for entailment.\n\nWe report **Pairwise overlap** ( fraction of response pairs clustered together in both methods) and **Jaccard Similarity** ( intersection-over-union of clusters across methods), as well as downstream metrics (empirical coverage, EE fraction, and average set size).\n\nOur **key findings** are: \n- All clustering methods yielded comparable CP metrics; no dramatic performance shifts were observed.\n- On longer or more open-ended generations, LLaMA-3-8B gave the most reliable clusters by manual inspection, and achieved slightly better downstream metrics.\n\nWe also evaluated clustering overlap between LLaMA-3-8B and GPT-4o on a small TriviaQA (50 exampels) subset ( reported below). The clusters showed high Jaccard and pairwise similarity. Due to time constraints, GPT-4o was not run on the full dataset, but based on similarity, we expect performance would remain consistent.\n\n**Table 1: Average Pairwise Overlap and Jaccard Similarity Between Clustering Methods**\n\n| Method Pair                  | Overlap | Jaccard |\n|:-----------------------------|------------:|------------:|\n| RoBERTa vs Cosine-MiniLM |     0.91  |     0.91  |\n| RoBERTa vs W2V    |     0.90  |     0.83  |\n| RoBERTa vs LLaMA      |     0.88  |     0.81  |\n| Cosine-MiniLM vs W2V  |     0.95  |     0.82  |\n| Cosine-MiniLM vs LLaMA   |     0.94  |     0.83  |\n| W2V vs LLaMA       |     0.93  |     0.87  |\n| GPT4o vs LLaMA  | 0.91|   0.89 |\n\n**Table 2: Performance of Different Clustering Methods on TriviaQA (LLaMA-3-8B Generations)**  \n| Clustering Method  | 1 - α   | Coverage (mean ± std) | EE Fraction (mean ± std) |\n|:-------------------|:----|:----------------------|:--------------------------|\n| RoBERTa        | 0.8 | 0.81 ± 0.03       | 0.42 ± 0.05           |\n|                    | 0.6 | 0.61 ± 0.02       | 0.09 ± 0.02           |\n| W2V         | 0.8 | 0.81 ± 0.02       | 0.44 ± 0.04           |\n|                    | 0.6 | 0.62 ± 0.03       | 0.10 ± 0.02           |\n| Cosine-MiniLM      | 0.8 | 0.82 ± 0.02      | 0.44 ± 0.05           |\n|                    | 0.6 | 0.62 ± 0.03      | 0.09 ± 0.02           |\n| LLaMA (default) | 0.8 | 0.80 ± 0.02       | **0.42** ± 0.02           |\n|                    | 0.6 | 0.61 ± 0.02      | **0.08** ± 0.01         |\n\n**Take-away**: as long as semantically equivalent outputs are correctly grouped, our algorithm is agnostic to clustering. When using a sufficiently strong model like LLaMA-3-8B, clustering quality is typically not a bottleneck. That said, clustering remains an active research area, especially for very long‐form or domain-specific generations, and users can leverage advances in NLP (from improved embeddings to specialized entailment models) to fit their particular use cases. A detailed report of our findings will be added to the revised version of the paper.\n\n## **Robustness under hallucination prone setting - when oracle $\\pi$ is very different than the ground truth $p$**\nWe appreciate the reviewer’s question regarding cases where model outputs may significantly differ from the ground truth (e.g., when the LLM hallucinates). In fact, all of our experiments are conducted with real black-box LLMs (e.g., LLaMA-3, GPT-3.5, GPT-4o), which are inherently prone to hallucinations.\n\nTo more directly address this question and evaluate robustness under high hallucination rates, we included SimpleQA, a benchmark adversarially constructed to expose hallucination failures in GPT models. **Even on this challenging dataset, we observed consistent improvements using our method, following the same trends observed in the main paper.**\n\n#### **SIMPLE QA – GPT4o**\n\n| Algorithm           | 1 - α    | Emp Cov ± Std    | EE ± Std         | Avg Set Size ± Std |\n|:--------------------|:----:|------------------:|------------------:|--------------------:|\n| Vanilla             | 0.60 | 0.62 ± 0.04       | 0.16 ± 0.03       | 0.85 ± 0.02         |\n| P1                  | 0.60 | 0.59 ± 0.06       | 0.11 ± 0.03       | 1.20 ± 0.14         |\n| P1 + P2 (CPQ)       | 0.60 | 0.61 ± 0.05       | **0.04 ± 0.04**   | 3.47 ± 0.53         |\n| ---                 |      |                   |                   |                     |\n| Vanilla             | 0.65 | 0.65 ± 0.06       | 0.19 ± 0.05       | 0.89 ± 0.07         |\n| P1                  | 0.65 | 0.63 ± 0.06       | 0.16 ± 0.05       | 1.28 ± 0.14         |\n| P1 + P2 (CPQ)       | 0.35 | 0.65 ± 0.05       | **0.11 ± 0.06**   | 2.89 ± 0.67         |\n| ---                 |      |                   |                   |                     |\n| Vanilla             | 0.70 | 0.68 ± 0.07       | 0.23 ± 0.06       | 0.89 ± 0.03         |\n| P1                  | 0.70 | 0.68 ± 0.05       | 0.22 ± 0.04       | 1.04 ± 0.04         |\n| P1 + P2 (CPQ)       | 0.70 | 0.69 ± 0.04       | **0.18 ± 0.06**   | 1.93 ± 0.58         |\n| ---                 |      |                   |                   |                     |\n| Vanilla             | 0.80 | 0.82 ± 0.06       | 0.48 ± 0.10       | 1.15 ± 0.21         |\n| P1                  | 0.80 | 0.79 ± 0.06       | 0.41 ± 0.11       | 1.77 ± 0.80         |\n| P1 + P2 (CPQ)       | 0.80 | 0.79 ± 0.05       | **0.40 ± 0.09**   | 0.70 ± 0.18         |\n\n## **On the assumption for deriving missing mass derivative estimator**\nThe assumption we make is exactly the one originally introduced and required by Good and Turing for their estimator of missing mass. We adopt the same assumption for estimating the missing mass derivative, as it is well-documented that the Good-Turing estimator performs reliably in practice despite this simplification."}]

Author rebuttal:

Meta-review: This paper proposes a new contribution on conformal prediction for large language models (LLM).  In such a setting, only a few outputs are sampled from the generative model (a few answers to a prompt for a LLM for instance). Therefore, estimating the uncertainty about the missing mass i.e. about the fact that the correct output is unseen is very challenging.  The authors propose a complete framework to formally capture the trade-off between coverage, informativeness, and query budget consisting of a query policy and a set map and split the problem into two steps:  allocating queries across covariate points and  constructing prediction sets with desired coverage. The proposed approach relies on simple yet theoretically grounded principles which allows to design a finite-sample algorithm outperforming recent conformal prediction baselines for generative models.

All reviewers agreed on the interest of the paper for the ML community, and noted that the paper is clearly written on an important problem about the limitations of conformal predictions for generative models. Although, they had questions on the experiments, they were mainly convinced by the experimental section of the paper.

The reviewers had mainly concerns on the experiments, in particular on the variety of the tasks considered in the experiments and on the baselines used by the authors. During the rebuttal the authors conducted additional experiments with TriviaQ and SimpleQA, using additional large LLM (GPT-3.5-turbo and GPT-4o). The results of these experiments confirm the numerical claims of the original paper. They also conducted an ablation using fixed querying strategy to highlight the performance of their optimal calibration rule.

A revised version of the paper including the additional experiments and detailed comments provided to the reviewers (detailed baselines, revised figures, discussions on the practical costs) will make a contribution of interest for a large ML audience.
Decision: Accept (poster)