# Large language model validity via enhanced conformal prediction methods

John J. Cherian
Department of Statistics
Stanford University
Stanford, CA 94305
<EMAIL_ADDRESS>
Isaac Gibbs
Department of Statistics
Stanford University
Stanford, CA 94305
<EMAIL_ADDRESS>
Emmanuel J. Candès
Department of Statistics
Department of Mathematics
Stanford University
Stanford, CA 94305
<EMAIL_ADDRESS>
###### Abstract

We develop new conformal inference methods for obtaining validity guarantees
on the output of large language models (LLMs). Prior work in conformal
language modeling identifies a subset of the text that satisfies a high-
probability guarantee of correctness. These methods work by filtering claims
from the LLM’s original response if a scoring function evaluated on the claim
fails to exceed a threshold calibrated via split conformal prediction.
Existing methods in this area suffer from two deficiencies. First, the
guarantee stated is not conditionally valid. The trustworthiness of the
filtering step may vary based on the topic of the response. Second, because
the scoring function is imperfect, the filtering step can remove many valuable
and accurate claims. We address both of these challenges via two new conformal
methods. First, we generalize the conditional conformal procedure of Gibbs et
al. (2023) in order to adaptively issue weaker guarantees when they are
required to preserve the utility of the output. Second, we show how to
systematically improve the quality of the scoring function via a novel
algorithm for differentiating through the conditional conformal procedure. We
demonstrate the efficacy of our approach on both synthetic and real-world
datasets.

##  1 Introduction

Large language models (LLMs) are a breakthrough in machine learning. In
addition to their extraordinary performance on natural language processing
benchmarks, LLMs such as ChatGPT and Gemini are now used by hundreds of
millions of users around the world [22]. But even though these models match or
even surpass human performance on an increasingly complex and diverse set of
tasks, their reliability remains in doubt. For example, LLMs often confidently
hallucinate facts that do not exist, and can generate toxic outputs that may
offend or discriminate [20]. This “misalignment” between user goals and model
behavior hinders LLM deployment in settings where the potential for AI
assistance appears highest, e.g., legal work or customer service interaction
[29].

Since an LLM output is not always trustworthy, a growing body of work aims to
quantify uncertainty regarding a given output’s validity. While there are many
approaches to this problem [26, 4, 9, 16], this paper considers a particularly
popular method for black-box uncertainty quantification: conformal inference
[28, 2, 3]. Conformal inference provides a generic procedure for transforming
the predictions of any modeling procedure into valid prediction sets that are
guaranteed to contain the true outcome with high probability. Several recent
papers have applied conformal inference to define a set of LLM responses that
contains at least one factual response with high probability [3, 15, 23, 30].
But while generating a candidate set of outputs may be a reasonable strategy
in some question-answering problems, it is not a generalizable approach for
the diverse and unstructured tasks faced in real-world deployment.

More recently, Mohri and Hashimoto [19] propose to forgo sets of LLM outputs
and instead utilize conformal inference to filter out invalid components of
the LLM response. At a high level, given an LLM generation parsed into a set
of distinct sub-claims, their method censors all sub-claims for which a pre-
defined scoring function lies below some threshold. Mohri and Hashimoto [19]
then show how to calibrate this threshold such that the retained claims are
factual with high probability.

While these methods represent a promising step towards usable guarantees for
LLM outputs, they are not yet practical. One limitation is that the guarantee
attained by previous methods only holds _marginally_ over a random test
prompt. The true probability of output correctness may then vary substantially
based on the prompt’s characteristics. For example, we show in Section 4 that
the probability of output correctness (even after applying the conformal
factuality method) is substantially lower for responses whose subjects are
likely to be underrepresented in the model’s training corpus. Second, existing
methods remove too many claims to be practically useful. Recall that we remove
sub-claims for which some pre-defined score falls below a calibrated
threshold. If this score is perfect, only false claims will be censored. In
practice, however, these scores are only weakly correlated with the ground
truth. As Figure 1 demonstrates, a high probability factuality guarantee can
require the removal of a significant proportion of the generated text.111We
note that when conformal prediction is applied to more typical supervised
learning tasks, this problem is equivalent to the challenge of prediction set
“inefficiency,” i.e. large prediction set size. The conformal guarantee is not
useful if the filtered response has limited value for the end-user.

Figure 1: The left panel displays the output of GPT-3.5-Turbo for the prompt
“How often is a shingles vaccine required?” The first filtered output (center)
is calibrated using the frequency score described in Section D.1. The second
filtered output (right) is calibrated using a score obtained via conditional
boosting. Both filtered outputs are guaranteed to include no false claims with
the stated probability. The middle panel displays the output of the marginally
valid conformal factuality method of Mohri and Hashimoto [19] at a fixed level
of 90%. The rightmost panel displays the output of our method at a level of
63%, which is chosen adaptively to ensure that at least 70% of the claims are
retained. We calibrate our method to this adaptive level using a
generalization of conditional conformal prediction [10].

###  1.1 Summary of contributions

In this subsection, we will preview and summarize our results. A more complete
description of our theory and experimental setup is deferred to Sections 3 and
4.

As in prior literature on conformal language modeling, we will assume the
existence of an annotated calibration set of $n$ i.i.d. prompt-response-claim-
annotation tuples,
$\\{(P_{i},R_{i},\mathbf{C}_{i},\mathbf{W}_{i})\\}_{i=1}^{n}$. The vector
$\mathbf{C}_{i}$ is obtained by using an LLM to parse the response into a list
of scorable sub-claims, while $\mathbf{W}_{i}$ might correspond to human
verification of the underlying factuality of each claim. To simplify notation,
we will refer to these tuples using the shorthand, $\mathbf{D}_{i}$.

Figure 2: Empirical demonstration of our methods. The panels display results
for our conditional boosting and level-adaptive methods. We aim to issue
outputs with $0$ factual errors, and for the latter method, we choose the
level with the objective of retaining at least 70% of the original claims in
the prompt. The left panel compares the binned nominal probabilities of
factuality reported by our method against the realized probability of
factuality for data points belonging to each bin. These probabilities are
estimated using $500$ test points over 100 calibration-test splits. The
plotted bins, which are also given as inputs to our method, are
$[0.5,0.55],[0.55,0.6],\dots,[0.8,0.85]$. Finally, the right-hand panel
displays the claim retention obtained with unboosted scores (blue), boosted
scores (orange), and boosted scores + level-adaptive CP (green). The first two
methods are implemented at a fixed error rate of $\alpha=0.1$. Boxplots in
this panel show the distribution of retained claims for 100 calibration-test
splits with each containing 2354 calibration points and 500 test points.

At first glance, the twin goals we have outlined for this paper, improved
conditional validity _and_ enhanced quality of filtered outputs, appear to be
irreconcilable. Indeed, prior work establishes that precise conditional
guarantees in black-box uncertainty quantification require larger prediction
set sizes, i.e., smaller filtered outputs [5, 27]. We contribute two methods
to mitigate this trade-off, thus enabling the practical application of
conformal prediction to LLMs.

Our first method, which we call conditional boosting, allows for the automated
discovery of superior claim scoring functions via differentiation through the
conditional conformal algorithm of Gibbs et al. [10]. Automated conformal
score improvement was introduced by Stutz et al. [25]; their paper shows how
to minimize conformal prediction set size in a classification setting by
differentiating through the split conformal algorithm. As we show, however, in
Section 4, optimizing the score function subject only to a marginal coverage
constraint can lead to poor conditional properties.

Differentiating through the conditional conformal algorithm presents new
challenges that are, to the best of our knowledge, unaddressed by prior work.
Our key technical contributions are a proof that the cutoff output by the
conditional conformal method remains locally linear with respect to the
conformity score under mild assumptions as well as a computationally efficient
estimator of this derivative. By running gradient descent with this
derivative, we discover new scores that enable greater claim retention.

The right panel of Figure 2 demonstrates the efficacy of our method. Here, we
use boosting to learn an optimal linear combination of four candidate scoring
functions. We compare the learned, boosted scores (orange) against a baseline
method (blue) that uses the “frequency” scoring method developed by Mohri and
Hashimoto [19]. As the figure shows, the boosted score allows for higher claim
retention across all datasets (mean claim retention of 39% vs. 24% for the
boosted vs. unboosted scores).

Our second method, which we call level-adaptive conformal prediction, allows
the validity of the conformal output to depend on characteristics of the
queried prompt. In our LLM experiments, we adapt the level, i.e., the claimed
probability of correctness, to each prompt in order to ensure that issued
outputs retain at least $70\%$ of the original set of sub-claims. For example,
in Figure 1, we prompt GPT-3.5-Turbo to output a response to a question from
the MedicationQA dataset [6]. Outputting a filtered response that achieves the
stated factuality criterion with probability $90\%$ requires near-complete
censorship, but by relaxing the level to $63\%$ using our method, we can
preserve almost the entire response.

Given that we are now issuing an output-adaptive probability of correctness,
it is crucial that our issued probability is _calibrated_. Calibration
requires that the true probability of correctness matches the issued one. For
example, if a weather forecaster claims that there is a $70\%$ chance of rain,
their forecast is calibrated if it actually rains for $70\%$ of the days on
which a $70\%$ forecast is issued.

Figure 2 displays the advantages of our approach to this problem. First, the
left panel of Figure 2 verifies that the level-adaptive probabilities we
report are empirically well-calibrated. Second, the right panel of Figure 2
quantitatively demonstrates the improved claim retention of our method. For
each dataset included in the MedLFQA benchmark [13], we show that level-
adaptive conformal prediction retains at least 70% of the original output’s
claims in most examples. By combining our two methods, we retain most claims
_and_ output non-trivial guarantees of response factuality; the left panel
shows that the issued probabilities vary between $50$ and $85\%$. By contrast,
while the fixed level method guarantees a $90\%$ probability of correctness,
the method retains very little of the original LLM output.

To emphasize that these results are accompanied by formal guarantees, we
preview one instantiation of our theory here. Since it is well-known that
exact conditional guarantees in conformal inference are impossible to achieve
without strong distributional assumptions [5, 27], we present an interpretable
alternative: group-conditional calibration.222 Equation 1 closely resembles a
measure of calibration error known in the theoretical computer science
literature as multicalibration [12]. Formally, however, multicalibration is
defined conditionally on the calibration dataset, while the expectation in (1)
is over both the calibration and test points. For example, in this dataset, we
might group questions by medical area or data provenance; we would then hope
to show that across health conditions or data sources, the claimed probability
of factuality matches the true probability of factuality.

Equation 1, which follows from Theorem 3.2, presents one guarantee that our
method can satisfy. Here, we denote the (random) output of our data-adaptive
level function by $\alpha_{n+1}$ and our filtered set of claims by
$\hat{F}(\mathbf{C}_{n+1})$. Our method then satisfies the following guarantee
simultaneously over groups $G\in\mathcal{G}$ (e.g., prompt topic, data
provenance) and some discretization of $[0,1]$ given by the sub-intervals $I$
(e.g., all sub-intervals with endpoints belonging to $\\{0,0.1,\dots,1\\}$),

$\mathbb{P}\left(\hat{F}(\mathbf{C}_{n+1})\text{ is
factual}\mid\alpha_{n+1}\in I,P_{n+1}\in
G\right)=\mathbb{E}[\alpha_{n+1}\mid\alpha_{n+1}\in I,P_{n+1}\in G].$ (1)

More concretely, (1) establishes that the issued probabilities are well-
calibrated in the following sense: among similar prompts, the outputs that we
claim to be factually correct with probability, say, between 70 and 80% will
be _actually_ factual between 70 and 80% of the time. This guarantee holds in
expectation over the dataset used to run our procedure. In this paper, we also
allow for many notions of “factuality,” e.g., in Figure 1, we guarantee that
filtered outputs have no unsubstantiated claims, but in other examples, we
relax our guarantee so that no more than $k$ false claims are issued.

The remainder of the paper is outlined as follows. In Section 2, we introduce
the formal notation of our paper and contextualize our approach by reviewing
related work in conformal inference. Section 3 then presents our new
methodology for conformal language modeling. We first generalize the
conditional conformal procedure of Gibbs et al. [10] to obtain high-
probability control of arbitrary monotone risks. We then state and give
intuition for the key technical results underpinning our level-adaptive and
boosting methods. Section 4 outlines synthetic experiments displaying the
improvements of our approach over existing methods, gives a more detailed
description of the experiment presented in Figure 2 above, and presents
another experiment that filters short biographies output by an LLM.

We release a filtered version of the MedLFQA benchmark that removes some non-
health-related prompts, the generated and parsed text used to run our
experiments, as well as the notebooks used to produce the figures in this
paper at github.com/jjcherian/conformal-safety. We also update our Python
package for conditional conformal inference to support level-adaptive
conformal prediction. The new version of this package is available to download
at github.com/jjcherian/conditional-conformal and can be installed from PyPI.

##  2 Background and related work

###  2.1 Conformal prediction with conditional guarantees

Split conformal prediction provides a generic procedure for transforming the
outputs of any black-box model into valid prediction sets [21, 28]. Let
$\\{(X_{i},Y_{i})\\}_{i=1}^{n+1}$ be a set of covariate-ground truth pairs
where $X_{n+1}$ denotes a test value for which we would like to output a
response. Then, split conformal outputs a prediction set $\hat{C}(X_{n+1})$
such that

$\mathbb{P}(Y_{n+1}\in\hat{C}(X_{n+1}))=1-\alpha,$ (2)

for any user-specified value $\alpha\in(0,1)$.

While powerful, the guarantee given in (2) only holds on-average over the test
value. Critically, in the LLM context we consider, this means that methods
calibrated using split conformal prediction run the risk of displaying
systematically worse performance on the most safety-critical examples.

This problem is addressed in Gibbs et al. [10], which introduces a novel
target for obtaining coverage conditional on covariate information. In their
work, they observe that exact covariate-conditional coverage can also be
expressed as a marginal guarantee over any measurable function
$f\in\mathcal{F}$, i.e.,

$\displaystyle\mathbb{P}(Y_{n+1}\in\hat{C}(X_{n+1})$ $\displaystyle\mid
X_{n+1})=1-\alpha$ $\displaystyle\Leftrightarrow$
$\displaystyle\mathbb{E}[f(X_{n+1})\cdot(\mathbbm{1}\\{Y_{n+1}\in\hat{C}(X_{n+1})\\}$
$\displaystyle-(1-\alpha))]=0$ $\displaystyle\text{for all measurable $f$}.$

Since exact distribution-free covariate-conditional coverage requires the
analyst to issue vacuous prediction sets [27], Gibbs et al. [10] design a
prediction set that satisfies the same marginal guarantee over a user-
specified function class $\mathcal{F}$, i.e.,

$\displaystyle\mathbb{E}[f(X_{n+1})\cdot(\mathbbm{1}\\{Y_{n+1}\in\hat{C}(X_{n+1})\\}-(1-\alpha))]=0$
$\displaystyle\text{for all $f\in\mathcal{F}$}.$ (3)

To make this guarantee concrete, we might define
$\mathcal{F}:=\\{(\mathbbm{1}\\{X\in
G\\})^{\top}\beta\mid\beta\in\mathbb{R}^{|\mathcal{G}|}\\}$ for some set of
subgroups $\mathcal{G}$. Then, (3) is exactly equivalent to group-conditional
coverage, i.e., $\mathbb{P}(Y_{n+1}\in\hat{C}(X_{n+1})\mid X_{n+1}\in
G)=1-\alpha$ for all $G\in\mathcal{G}$.

To understand their construction, let $S(X,Y)\in\mathbb{R}$ denote a
conformity score that measures how well $Y$ “conforms” to an estimate of its
value. A typical choice in the regression setting is $S(X,Y)=|Y-\hat{\mu}(X)|$
for some fixed regression function $\hat{\mu}(\cdot)$; in the classification
setting, we might choose $S(X,Y)=1/\hat{\pi}(Y\mid X)$ for some estimated
conditional probabilities $\hat{\pi}$. Then, Gibbs et al. [10] estimate an
upper bound for these scores by fitting an augmented quantile regression in
which the unknown test score, $S(X_{n+1},Y_{n+1})$ is replaced by an imputed
value $S$. Formally, let $\ell_{\alpha}(r):=(1-\alpha)[r]_{+}+\alpha[r]_{-}$
denote the pinball loss. Then, they define

$g_{S}=\text{argmin}_{g\in\mathcal{F}}\frac{1}{n+1}\sum_{i=1}^{n}\ell_{\alpha}(S(X_{i},Y_{i})-g(X_{i}))+\frac{1}{n+1}\ell_{\alpha}(S-g(X_{n+1})),$
(4)

and output the prediction set given by
$\hat{C}(X_{n+1}):=\\{y:S(X_{n+1},y)\leq g_{S(X_{n+1},y)}(X_{n+1})\\}$.

Since $\hat{C}(X_{n+1})$ can be conservative, Gibbs et al. [10] also define a
smaller randomized prediction set, $\hat{C}_{\text{rand.}}(X_{n+1})$ that
achieves exact coverage. We will typically prefer to work with this set, but
defer a detailed definition of its construction to the Appendix. As the
following theorem shows, this randomized set achieves the guarantee stated in
(3).

######  Theorem 2.1 (Proposition 4 of Gibbs et al. [10]).

Let $\mathcal{F}=\\{\Phi(X)^{\top}\beta:\beta\in\mathbb{R}^{d}\\}$ denote any
finite dimensional linear class. Assume that $\\{(X_{i},S_{i})\\}_{i=1}^{n+1}$
are exchangeable and that solutions to (4) and its dual are computed
symmetrically on the input data. Then, for all $f\in\mathcal{F}$,

$\mathbb{E}[f(X_{n+1})(\mathbbm{1}\\{S_{n+1}\in\hat{C}_{\text{rand.}}(X_{n+1})\\}-(1-\alpha))]=0.$

###  2.2 Conformal factuality

As discussed in the introduction, prediction sets are not a practical object
for LLM outputs. Thus, to adapt conformal inference to this setting, Quach et
al. [23] and Mohri and Hashimoto [19] develop filtering methods that remove
false claims from an LLM’s output. We will focus specifically here on the work
of Mohri and Hashimoto [19] since this is most similar to the new methods that
we will propose in this article. Recall that
$\mathbf{C}_{i}=\\{C_{ij}\\}_{j=1}^{k_{i}}$ denotes the claims made in an
LLM’s response and $\mathbf{W}_{i}=\\{W_{ij}\\}_{j=1}^{k_{i}}$ denotes binary
variables for which $W_{ij}=1$ indicates that the claim is true.

Mohri and Hashimoto [19] aim to output a set of filtered claims,
$\hat{F}(\mathbf{C}_{i})\subseteq\mathbf{C}_{i}$, that contains no errors with
high probability, i.e.,

$\mathbb{P}\left(\exists C_{(n+1)j}\in\hat{F}(\mathbf{C}_{n+1})\text{ such
that }W_{(n+1)j}=0\right)\leq\alpha.$ (5)

To achieve this target, Mohri and Hashimoto [19] define a scoring function
$p(P_{i},C_{ij})\in\mathbb{R}$ that takes a prompt and claim as input and
summarizes the LLM’s internal confidence in the claim. Here, larger values of
$p(P_{i},C_{ij})$ indicate that the LLM believes that $C_{ij}$ is more likely
to be true. Then, Mohri and Hashimoto [19] set

$\hat{F}(\mathbf{C}_{i}):=F(\mathbf{C}_{i};\hat{\tau})=\\{C_{ij}:p(P_{i},C_{ij})\geq\hat{\tau}\\},$

where $\hat{\tau}$ is the $\frac{\lceil(1-\alpha)(n+1)\rceil}{n+1}$-quantile
of the conformity scores

$S(\mathbf{C}_{i},\mathbf{W}_{i})=\inf\\{\tau\mid\forall
C_{ij}\in\hat{F}(\mathbf{C}_{i};\tau),W_{ij}=1\\}.$ (6)

Theorem 1 of [19] shows that if
$\\{({P}_{i},R_{i},\mathbf{C}_{i},\mathbf{W}_{i})\\}_{i=1}^{n+1}$ are
exchangeable, this method satisfies (5).

##  3 Methods

###  3.1 Generalization to alternative targets

Our first contribution in this paper will be to generalize the conditional
framework of Gibbs et al. [10] to generic alignment tasks. More formally,
suppose we are given a loss function
$L(\hat{F}(\mathbf{C}_{i}),\mathbf{W}_{i})$ that measures the quality of the
filtered output $\hat{F}(\mathbf{C}_{i})$ relative to the ground truth
$\mathbf{W}_{i}$. Our goal will be to ensure that
$\mathbb{P}(L(\hat{F}(\mathbf{C}_{n+1}),\mathbf{W}_{n+1})\leq\lambda)\geq
1-\alpha$, for some user-specified tolerance $\lambda>0$. For example, in the
prior section, $L(\cdot,\cdot)$ was the binary indicator that
$\hat{F}(\mathbf{C}_{n+1})$ contains a false claim. More generally,
$L(\cdot,\cdot)$ could measure the presence of toxic or discriminatory content
in the response.

To incorporate general losses into the conditional conformal framework, we
require two assumptions. First, we assume that the method is always permitted
to abstain from issuing a response and thus $L(\emptyset,\cdot)=0$. Second, we
assume the loss is monotone. Namely, for any sets of claims
$\hat{F}_{1}(\mathbf{C}_{i})\subseteq\hat{F}_{2}(\mathbf{C}_{i})$, it must be
the case that $L(\hat{F}_{1}(\mathbf{C}_{i}),W_{i})\leq
L(\hat{F}_{2}(\mathbf{C}_{i}),W_{i})$. This requirement also means that we
only incur loss for outputting incorrect information and do not receive any
reward for making a larger number of claims. In the sequel, we will discuss
methods for optimizing the filtering procedure to satisfy other auxiliary
objectives such as outputting a richer response.

With these assumptions, we extend the calibration procedure of Gibbs et al.
[10] as follows. Let $X_{n+1}=X_{n+1}(P_{i},R_{i})$ denote a set of features
computed using the prompt and response. Matching (6), we define
$p(P_{i},C_{ij})$ to be a score measuring the quality of claim $C_{ij}$. We
define the filtered set of claims by
$\hat{F}(\mathbf{C}_{i})=F(\mathbf{C}_{i};\hat{\tau}):=\\{C_{ij}:p(P_{i},C_{ij})\geq\hat{\tau}\\}$,
and the conformity score via

$S(\mathbf{C}_{i},\mathbf{W}_{i}):=\inf\\{\tau\mid
L(F(\mathbf{C}_{i};\tau),\mathbf{W}_{i})\leq\lambda\\},$

i.e., the minimum filtering threshold that controls the loss. Then, we set

$g_{S}=\text{argmin}_{g\in\mathcal{F}}\frac{1}{n+1}\sum_{i=1}^{n}\ell_{\alpha}(S(\mathbf{C}_{i},\mathbf{W}_{i})-g(X_{i}))+\frac{1}{n+1}\ell_{\alpha}(S-g(X_{n+1})),$
(7)

and filter claims at the cutoff $\hat{\tau}(X_{n+1})=\sup\\{S\mid S\leq
g_{S}(X_{n+1})\\}$. Similar to the prediction sets of Gibbs et al. [10],
$\hat{\tau}(X_{n+1})$ can be conservative, and, thus, we prefer to use a
randomized analog $\hat{\tau}_{\text{rand.}}(X_{n+1})$; its formal definition
can be found in Appendix A. As the following theorem shows, this randomized
cutoff satisfies the desired guarantee.

######  Theorem 3.1.

Let $\mathcal{F}=\\{\Phi(X)^{\top}\beta:\beta\in\mathbb{R}^{d}\\}$ denote any
finite dimensional linear class. Assume that
$\\{\mathbf{D}_{i}\\}_{i=1}^{n+1}$ are exchangeable, that solutions to (7) and
its dual are computed symmetrically in the input data, $L(\cdot,\cdot)$ is
monotone, and $L(\emptyset,\cdot)=0$. Then, for all $f\in\mathcal{F}$,

$\mathbb{E}[f(X_{n+1})(\mathbbm{1}\\{L(\hat{F}(\mathbf{C}_{n+1};\hat{\tau}_{\text{rand.}}(X_{n+1})),\mathbf{W}_{n+1})\leq\lambda\\}-(1-\alpha))]=0.$

As above, we can make this guarantee concrete by choosing $\mathcal{F}$ to be
a linear combination of group indicators, i.e.,
$\mathcal{F}=\\{(\mathbbm{1}\\{X\in
G\\})^{\top}\beta\mid\beta\in\mathbb{R}^{|\mathcal{G}|}\\}$. For example, in
our Wikipedia biographies experiment, groups might be defined using the
subject’s country of origin. This choice of $\mathcal{F}$ yields

$\displaystyle\mathbb{P}(L(F(\mathbf{C}_{n+1};\hat{\tau}_{n+1}),\mathbf{W}_{n+1})\leq\lambda\mid
X_{n+1}\in G)=1-\alpha$ for all $G\in\mathcal{G}$.

###  3.2 Level-adaptive conformal prediction

In addition to adapting the filtering cutoff to $X_{n+1}$, it may also be
beneficial to adjust the desired error probability $\alpha$.333Although our
methods’ implementations differ, we remark here that the level-adaptive
guarantee is inspired by a similar result in the unpublished work of Zhang and
Candès [31]. More formally, suppose now that we are given some function,
$\alpha(\cdot)$ and our goal is to ensure that
$L(\hat{F}(\mathbf{C}_{n+1}),\mathbf{W}_{n+1})\leq\lambda$ with probability
$1-\alpha(X_{n+1})$. Recall that in the previous section, we use the pinball
loss, $\ell_{\alpha}(\cdot)$ to learn the $1-\alpha$ quantile of
$S(\mathbf{C}_{i},\mathbf{W}_{i})$. To control the error rate adaptively, here
we will use a data-dependent loss for the $i$-th point,
$\ell_{\alpha(X_{i})}(\cdot)$. Then, similar to previous section, we define

$g_{S}=\mathop{\rm
argmin}_{g\in\mathcal{F}}\frac{1}{n+1}\sum_{i=1}^{n}\ell_{{\color[rgb]{0,0,1}\alpha(X_{i})}}(S(\mathbf{C}_{i},\mathbf{W}_{i})-g(X_{i}))+\frac{1}{n+1}\ell_{{\color[rgb]{0,0,1}\alpha(X_{n+1})}}(S-g(X_{n+1})),$
(8)

and apply filtering at the cutoff
$\hat{\tau}_{\text{l.a.}}(X_{n+1}):=\sup\\{S:S\leq g_{S}(X_{n+1})\\}$. As in
the previous section, it is more convenient to work with a slightly smaller
randomized cutoff, $\hat{\tau}_{\text{l.a., rand.}}$. The following theorem
shows that our previous guarantee for fixed $\alpha$ extends to this new
setting.

######  Theorem 3.2.

Under the assumptions of Theorem 2.1,

$\mathbb{E}[f(X_{n+1})(\mathbbm{1}\\{L(\hat{F}(\mathbf{C}_{n+1};\hat{\tau}_{\textup{l.a.,
rand.}}(X_{n+1})),\mathbf{W}_{n+1})\leq\lambda\\}-(1-\alpha(X_{n+1})))]=0,\
\forall f\in\mathcal{F}.$

Note that we recover the guarantee presented in (1) by defining

$\displaystyle\Phi(\cdot)=\left\\{\mathbbm{1}\\{\alpha(\cdot)\in
I\\}\cdot\mathbbm{1}\\{\cdot\in
G\\}:I\in\mathcal{I},G\in\mathcal{G}\right\\}\quad\text{ and
}\quad\mathcal{F}=\\{\Phi(\cdot)^{\top}\beta:\beta\in\mathbb{R}^{d}\\}.$

While this choice of function class elicits an interpretable guarantee, it can
be quite large in practice. This can both slow down the computation of the
conformal cutoff and reduce the proportion of retained claims. The
practitioner has some flexibility in choosing the function class to trade-off
between quality of guarantee and computational efficiency / claim retention.
For example, this class might be chosen to exactly satisfy other popular (and
more efficient) approximations to multicalibration such as low-degree
multicalibration [11]. In Section B.2, we briefly explore the consequences of
choosing an insufficiently complex function class in a synthetic regression
example, but remark that a much more substantial exposition of these trade-
offs can be found in Gibbs et al. [10].

#### Estimating $\alpha(\cdot)$

While the above theory treats $\alpha(\cdot)$ as fixed, in order to ensure
that the outputs of our method meet our desired quality criterion (e.g., small
interval length or sufficient claim retention) we will need to learn
$\alpha(\cdot)$ from the data. To do this, we split our training data into two
folds: one is used to estimate $\alpha(\cdot)$ and the other is used to run
the calibration method described above. After making these splits,
$\alpha(\cdot)$ can be learned using any regression method. In our
experiments, we will aim to learn the smallest possible values of
$\alpha(\cdot)$ that meet our target quality criterion. A detailed description
of our procedure for doing so is given in Section B.1.

###  3.3 Conditional boosting

In this section, we describe a new method for automated conformity score
design subject to _conditional coverage_ constraints. As discussed in the
introduction, the goal of this procedure is to find conformity scores that
when combined with our filtering method, allow the filter to retain as much of
the LLM output as possible while still ensuring validity. To make our
exposition more concrete, we will assume for the sake of simplicity that we
are boosting the conformity score defined in (6). Our approach, however, will
generalize to any parameterized score function.

Let $p_{\theta}(\cdot)$ denote a _parameterized_ claim-scoring function that
assigns a measure of confidence to each sub-claim. We run the conditional
conformal method on a set of size $n$ and optimize $\theta$ such that the
number of retained claims is maximized on a hold-out set of size $m$, i.e.,

$\theta^{*}=\mathop{\rm
argmax}_{\theta}\sum_{i=1}^{m}\sum_{j=1}^{k_{n+i}}\mathbf{1}\left\\{p_{\theta}(P_{n+i},C_{(n+i)j})\geq\hat{\tau}_{i}\right\\}.$
(9)

Here, $\hat{\tau}_{i}$ denotes the filtering threshold output by the
conditional conformal method on the held-out test point $X_{n+i}$. Crucially,
$\hat{\tau}_{i}=\hat{\tau}_{i}(\theta)$ carries a hidden dependence on
$\theta$: $\hat{\tau}_{i}$ is obtained by solving a quantile regression
problem on scores that depend on $p_{\theta}(\cdot)$.

There are therefore two obstacles to optimizing (9) via gradient descent.
First, the indicator function is non-differentiable. To resolve this, we
approximate the indicator using a sigmoid function [25]. Second, it is unclear
how to backpropagate through the estimated cutoff $\hat{\tau}_{i}(\theta)$.

Observe that for linear function classes
$\mathcal{F}=\\{\Phi(X)^{\top}\beta:\beta\in\mathbb{R}^{d}\\}$, the regression
(8) by which we obtain $\hat{\tau}_{i}(\theta)$ is a linear program. Using
this observation, we find that $\hat{\tau}_{i}(\theta)$ can be expressed as
the solution to a linear system of equations given by a subset of the dataset
that we denote by $B$, i.e.,

$\hat{\tau}_{i}(\theta)=\Phi(X)_{B}^{-1}S_{B}(\theta).$ (10)

In the linear programming literature, this subset is typically referred to as
the “optimal basis.” It can be explicitly identified by selecting the points
at which the quantile regression interpolates the scores. Then, so long as $B$
is invariant to small perturbations of $\theta$ and $S$ is differentiable in
$\theta$, we can obtain the derivative of $\hat{\tau}_{i}(\theta)$ with
respect to $\theta$ by backpropagating through (10). Proposition 3.1
identifies a simple condition under which this is possible.

######  Proposition 3.1.

Assume that the solution to the quantile regression given by (7) with
$S=\hat{\tau}_{i}(\theta)$ is non-degenerate, i.e., it interpolates exactly
$\text{dim}(\Phi)$ points, and let $B$ denote the optimal basis of this
solution. Then, $\hat{\tau}_{i}(\theta)$ has derivative

$\partial_{\theta}\hat{\tau}_{i}(\theta)=\Phi(X)_{B}^{-1}\partial_{\theta}S_{B}(\theta).$
(11)

The non-degeneracy assumption in Proposition 3.1 nearly always holds; if it
does not, we remark that non-degeneracy can always be obtained by “dithering”
the scores, i.e., adding small i.i.d. noise, at each step of the boosting
procedure [7].

Now that we have resolved the gradient computation problem, the remainder of
our procedure emulates the analogous ConfTr algorithm of Stutz et al. [25].
Similar to the $\alpha(\cdot)$-estimation problem, we must leave a portion of
the dataset for the final calibration procedure. In our experiments, we re-use
the portion set aside for boosting. With this part of the available data, we
re-split our dataset at each iteration into a calibration and test set,
compute the quality criterion on the test set, and backpropagate on the
objective given by (9) subject to the above modifications. For the sake of
space, we defer Algorithm 1, which provides a complete description of the
procedure, to Appendix C.

##  4 Experiments

###  4.1 Synthetic data

Figure 3: Comparison of the marginal boosting procedure of Stutz et al. [25]
(blue) against our conditional boosting method (orange). The left panel shows
the prediction sets produced by each method, while the right panel displays
the conditional coverage, $\mathbb{P}(Y_{n+1}\in\hat{C}(X_{n+1})\mid X_{n+1})$
against the values of the first feature, $X_{n+1}^{(1)}$. Using the Adam
optimizer with learning rate set to $0.001$, the plotted scores are boosted
for $500$ steps on a synthetic dataset of size $n=1000$ and evaluated on
another test dataset of size $n=2000$.

To demonstrate how our methods improve upon previous approaches, we consider a
synthetic regression dataset with substantial heteroskedasticity. The data in
this experiment are generated by sampling two features
$X^{(1)}_{i}\stackrel{{\scriptstyle\rm iid}}{{\sim}}\text{Unif}(1,10)$ and
$X^{(2)}_{i}\stackrel{{\scriptstyle\rm iid}}{{\sim}}\text{Unif}(5,10)$, while
the labels are sampled from a distribution whose variance is given by the
sixth power of the first feature, i.e.,
$Y_{i}\sim\mathcal{N}(0,(X_{i}^{(1)})^{6})$. We then construct prediction
intervals using the score function $S_{\theta}(X,Y):=|Y|/|X^{\top}\theta|$.

Figure 3 compares the ConfTr algorithm of Stutz et al. [25] against our
Conditional Boosting method. While the left panel shows that the former method
issues shorter intervals, these come at the cost of degraded conditional
validity (right panel). In particular, the prediction sets resulting from
ConfTr have extremely poor coverage on the subset of data with high
conditional variance. By contrast, learning $\theta$ using our procedure still
attains near-perfect conditional coverage.

Figure 4: Performance of our level-adaptive method on a synthetic dataset. We
use $n=2000$ points to estimate the adaptive $\alpha(\cdot)$ function. We then
run the level-adaptive method on a calibration set of size $n=1000$ and
evaluate the method on $1$ test point; the plotted points (center, right) are
obtained from $200$ trials. The left panel shows the distribution of interval
lengths obtained on the test set for fixed values of
$\alpha\in\\{0.05,0.25,0.5,0.75,0.95\\}$. The center panel displays the
interval lengths obtained when the level $\alpha(X_{n+1})$ is now chosen
adaptively to ensure a maximum prediction set size of at most 500 (red line).
Finally, the right panel compares the realized coverage
$\mathbb{P}(Y_{n+1}\in\hat{C}(X_{n+1})\mid\alpha(X_{n+1}))$ against the
nominal level, $1-\alpha(X_{n+1})$ reported by our method with
$\mathcal{F}=\\{\beta_{0}+\sum_{i=1}^{2}\beta_{1}x^{i}+\beta_{3}\alpha(x)\mid\beta\in\mathbb{R}^{4}\\}$.

Figure 4 applies the level-adaptive conformal prediction procedure to the same
data-generating process. In this example, we use the naive absolute value
score $S(X,Y)=|Y|$. Since the score is poorly chosen and the data is noisy,
the resulting prediction interval can be very large. The left panel of the
figure shows boxplots that display the empirical distribution of interval
lengths over the test set at various fixed levels of
$\alpha\in\\{0.05,0.25,0.5,0.75,0.95\\}$. Unsurprisingly, at most fixed levels
for $\alpha$, many intervals are substantially larger than the maximum target
length of 500. This is corrected when we fit using an adaptive level,
$\alpha(X_{i})$ (center panel), which is estimated to ensure that the interval
lengths fall below $500$. Finally, the right-hand panel verifies that the
guarantee of Theorem 3.2 is accurate. The issued values of $\alpha(X_{n+1})$
closely track the true coverage probabilities; note that the latter can be
computed in closed-form for our data-generating process.

###  4.2 Medical long-form question-answering

In this section, we summarize the experimental setup for the claims and
figures presented in Section 1.1. Our experiment considers the long-form
medical question-answering dataset (MedLFQA) published in Jeong et al. [13].
It combines several previously established benchmarks in the medical question-
answering literature: HealthSearchQA ($n=3047$), K-QA ($n=1077$), LiveQA
($n=100$) and MedicationQA ($n=627$). Each prompt in these datasets is also
accompanied by either an LLM or human-generated response to each question [6,
1, 17, 24]. Following prior work [17, 13], we treat these responses as ground-
truth for model evaluation. Also matching Jeong et al. [13], in our plots, we
distinguish between the subset of questions ($n=201$) in the K-QA dataset that
have gold-standard physician responses (denoted by K-QA Golden) and those
questions with LLM-generated responses (denoted by K-QA Silver). To reproduce
our results, we point the interested reader to our GitHub repository, which
includes a filtered and combined dataset that removes some non-health-related
prompts contaminating the HealthSearchQA dataset as well as some extraneous
text from the questions.

To obtain the dataset used in our experiment, we query GPT-3.5-Turbo with each
of the prompts in the combined dataset, and then ask GPT-4o to parse these
prompts into self-contained sub-claims. Then, to obtain our “ground-truth”
labels, we ask GPT-3.5-Turbo to evaluate whether each claim is substantiated
by the pseudo-ground-truth response for that prompt. The prompts we use for
each of these tasks are included in Section D.2.

In all of the medical question-answering experiments displayed, we run the
conditional conformal method with the following scoring function,

$S(\mathbf{C}_{i},\mathbf{W}_{i})=\inf\\{\tau:\hat{F}(\mathbf{C}_{i};\tau)\text{
contains no unsubstantiated claims}\\}.$

To run our procedure, we must first split the dataset into two parts. We use
the first split to both run the conditional boosting method and estimate
$\alpha(\cdot)$, while we use the second split to run level-adaptive conformal
prediction and evaluate our method’s guarantees.

On the first split ($n=1421$), we boost our claim score via optimizing a
linear combination of four scores previously described in the literature: the
frequency, self-evaluation, and ordinal scores described in Mohri and
Hashimoto [19] and the token-level probability assigned to a single-token
self-evaluation [14]. Section D.1 includes a precise description of how we
compute these features. We then differentiate through the conformal
calibration step with respect to the function class $\mathcal{F}$ defined by
the linear combination of an intercept, the number of characters in the
prompt, the number of characters in the response, the mean frequency score
assigned to the claims, and the standard deviation of the frequency scores
assigned to the claims. The results shown in Figure 2 are obtained by running
the conditional boosting algorithm for $1000$ steps using the Adam optimizer
with learning rate set to $0.001$.

Having obtained an improved conformity score, we simulate the conditional
conformal step and estimate $\alpha(\cdot)$ by dividing this portion of the
dataset in half. On the first half of this dataset ($n=720$), we run the
fixed-level conditional conformal procedure (with the same $\mathcal{F}$ used
to boost the scores) for each $\alpha$ in a grid of $50$ evenly spaced values
between $0$ and $1$. Using the second half of this dataset, we evaluate the
percentage of retained claims at each $\alpha$. We record the smallest
$\alpha$ for which at least $70\%$ of claims are preserved at _all larger_
values of $\alpha$. We then obtain our estimate of $\alpha(\cdot)$ by fitting
a $0.15$-quantile regression over $\mathcal{F}$ to this dataset. For
interpretability and numerical stability in the next step, the final output of
the function is truncated to lie between $0.1$ and $0.5$.

On the second half of this dataset, we run level-adaptive conformal prediction
over the previously described $\mathcal{F}$ augmented by indicator functions
that correspond to $\alpha(\cdot)$ falling in some sub-interval with endpoints
lying in $\\{0,0.05,\dots,1\\}$. Finally, to produce the plots in Figure 2, we
run this step over $100$ random calibration-test splits of size $2354$ and
$500$, respectively.

###  4.3 Wikipedia biographies

Figure 5: Empirical demonstration of our method on the Wikipedia biographies
dataset. The left two panels display results for our level-adaptive method,
which aims to issue biographies with 3 or fewer errors, while retaining at
least 80% of the original claims in the prompt. The left panel compares the
binned nominal probabilities reported by our method with bin width $2.5\%$
against the true realized empirical values evaluated over $400$ test points
and 100 calibration-test splits. The center panel compares the number of
claims retained by our method (orange) against the fixed level method of Mohri
and Hashimoto [19] (blue). In this plot, the $y$-axis displays a moving
average of the number of claims retained with window size $1000$, while the
$x$-axis a moving average of the number of views (in Jan. 2023) of the
Wikipedia article associated with each prompt on the log-scale. Finally, the
right-hand panel displays the claim retention obtained with boosted (orange)
and unboosted (blue) scores at a fixed level of $\alpha=0.1$. Boxplots in this
panel show the distribution of retentions for 100 calibration-test splits each
containing 7246 calibration points and 381 test points.

Our LLM experiment reconsiders the biography dataset analyzed in Mohri and
Hashimoto [19]. We sample $8516$ names from Wikipedia and query GPT-3.5-Turbo
with the prompt “Write me a short biography of [NAME].” We then ask GPT-4o to
parse the prompts into self-contained sub-claims. While the prior work only
annotates $25$ biographies, we need to scale up this experiment to validate
our proposed methods. To get around expensive human annotation, we use a
variant of the FActscore procedure developed by Min et al. [18]. Their method,
commonly known as retrieval-augmented generation (RAG), passes in relevant
Wikipedia passages identified by the BM25 ranking function as part of the
prompt to the LLM and asks if the claims are supported. Scoring of the LLM
outputs (i.e., computation of $p(P_{i},C_{ij})$) is done using several self-
evaluation methods previously described in the LLM alignment literature [19,
14]. A more detailed description of the methods described in this paragraph
can be found in Sections D.1 and D.2.

In all of the experiments displayed here, we run the conditional conformal
method with the scoring function given by

$S(\mathbf{C}_{i},\mathbf{W}_{i})=\inf\\{\tau:\hat{F}(\mathbf{C}_{i};\tau)\text{
contains at most 3 false claims}\\}.$

We control this relaxed factuality criterion so that we can issue non-trivial
guarantees over all topics. For the sake of avoiding redundancy with the
previous subsection, further details about how our methods are instantiated
are deferred to Section D.3.

Figure 6: Comparison of the split conformal calibration method of Mohri and
Hashimoto [19] (blue) against our conditional conformal method (orange). The
left and right panels displays the miscoverage and percentage of claims
retained by the two methods against the number of views received by the
Wikipedia pages in January 2023. The displayed boxplots are computed over
$200$ trials in which we run both methods on a calibration set of $5890$
points and evaluate their coverage on a test set of size $2500$. The displayed
groups correspond to view counts that are binned into the intervals
$(-\infty,\infty)$, $[1000000,\infty)$, $[100000,1000000)$, $[1000,100000)$,
$[100,1000)$, $[0,100)$ .

Experimental results displaying the effectiveness of our level-adaptive and
conditional boosting procedures on this dataset can be found in Figure 5. In
Figure 6, we also provide additional comparisons contrasting the conditional
conformal method of Section 3.1 with the marginal method proposed in Mohri and
Hashimoto [19]. As anticipated by our theory, we find that our method provides
accurate coverage regardless of the popularity of the Wikipedia page, while
the split conformal method of Mohri and Hashimoto [19] gives variable results
(left panel). As the right panel of the figure shows, this conditional
accuracy is obtained by retaining more claims for frequently viewed topics and
less claims for rare topics on which the LLM is more uncertain.

## References

  * Abacha et al. [2017] A. B. Abacha, E. Agichtein, Y. Pinter, and D. Demner-Fushman.  Overview of the medical question answering task at trec 2017 liveqa.  In _TREC_ , pages 1–12, 2017.
  * Angelopoulos et al. [2022] A. N. Angelopoulos, S. Bates, E. J. Candès, M. I. Jordan, and L. Lei.  Learn then test: Calibrating predictive algorithms to achieve risk control.  _arXiv preprint_ , 2022.  arXiv:2110.01052.
  * Angelopoulos et al. [2024] A. N. Angelopoulos, S. Bates, A. Fisch, L. Lei, and T. Schuster.  Conformal risk control.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=33XGfHLtZg.
  * Azaria and Mitchell [2023] A. Azaria and T. Mitchell.  The internal state of an llm knows when it’s lying.  In _Findings of the Association for Computational Linguistics: EMNLP 2023_ , pages 967–976, 2023.
  * Barber et al. [2020] R. F. Barber, E. J. Candès, A. Ramdas, and R. J. Tibshirani.  The limits of distribution-free conditional predictive inference.  _Information and Inference: A Journal of the IMA_ , 10(2):455–482, 08 2020.  ISSN 2049-8772.  doi: 10.1093/imaiai/iaaa017.
  * Ben Abacha et al. [2019] A. Ben Abacha, Y. Mrabet, M. Sharp, T. Goodwin, S. E. Shooshan, and D. Demner-Fushman.  Bridging the gap between consumers’ medication questions and trusted answers.  In _MEDINFO 2019_ , 2019.
  * Charnes [1952] A. Charnes.  Optimality and degeneracy in linear programming.  _Econometrica: Journal of the Econometric Society_ , pages 160–170, 1952.
  * Dantzig and Thapa [2003] G. B. Dantzig and M. N. Thapa.  _Linear programming: Theory and extensions_ , volume 2.  Springer, 2003.
  * Detommaso et al. [2024] G. Detommaso, M. Bertran, R. Fogliato, and A. Roth.  Multicalibration for confidence scoring in llms.  _arXiv preprint arXiv:2404.04689_ , 2024.
  * Gibbs et al. [2023] I. Gibbs, J. J. Cherian, and E. J. Candès.  Conformal prediction with conditional guarantees.  _arXiv preprint arXiv:2305.12616_ , 2023.
  * Gopalan et al. [2022] P. Gopalan, M. P. Kim, M. A. Singhal, and S. Zhao.  Low-degree multicalibration.  In _Conference on Learning Theory_ , pages 3193–3234. PMLR, 2022\.
  * Hébert-Johnson et al. [2018] U. Hébert-Johnson, M. Kim, O. Reingold, and G. Rothblum.  Multicalibration: Calibration for the (computationally-identifiable) masses.  In _International Conference on Machine Learning_ , pages 1939–1948. PMLR, 2018.
  * Jeong et al. [2024] M. Jeong, H. Hwang, C. Yoon, T. Lee, and J. Kang.  Olaph: Improving factuality in biomedical long-form question answering.  _arXiv preprint arXiv:2405.12701_ , 2024.
  * Kadavath et al. [2022] S. Kadavath, T. Conerly, A. Askell, T. Henighan, D. Drain, E. Perez, N. Schiefer, Z. Hatfield-Dodds, N. DasSarma, E. Tran-Johnson, et al.  Language models (mostly) know what they know.  _arXiv preprint arXiv:2207.05221_ , 2022.
  * Kumar et al. [2023] B. Kumar, C. Lu, G. Gupta, A. Palepu, D. Bellamy, R. Raskar, and A. Beam.  Conformal prediction with large language models for multi-choice question answering.  _arXiv preprint_ , 2023.  arXiv:2305.18404.
  * Manakul et al. [2023] P. Manakul, A. Liusie, and M. J. Gales.  Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models.  _arXiv preprint arXiv:2303.08896_ , 2023.
  * Manes et al. [2024] I. Manes, N. Ronn, D. Cohen, R. I. Ber, Z. Horowitz-Kugler, and G. Stanovsky.  K-qa: A real-world medical q&a benchmark.  _arXiv preprint arXiv:2401.14493_ , 2024.
  * Min et al. [2023] S. Min, K. Krishna, X. Lyu, M. Lewis, W.-t. Yih, P. W. Koh, M. Iyyer, L. Zettlemoyer, and H. Hajishirzi.  Factscore: Fine-grained atomic evaluation of factual precision in long form text generation.  _arXiv preprint arXiv:2305.14251_ , 2023.
  * Mohri and Hashimoto [2024] C. Mohri and T. Hashimoto.  Language models with conformal factuality guarantees.  _arXiv preprint arXiv:2402.10978_ , 2024.
  * Nadeau et al. [2024] D. Nadeau, M. Kroutikov, K. McNeil, and S. Baribeau.  Benchmarking llama2, mistral, gemma and gpt for factuality, toxicity, bias and propensity for hallucinations.  _arXiv preprint arXiv:2404.09785_ , 2024.
  * Papadopoulos et al. [2002] H. Papadopoulos, K. Proedrou, V. Vovk, and A. Gammerman.  Inductive confidence machines for regression.  In T. Elomaa, H. Mannila, and H. Toivonen, editors, _Machine Learning: ECML 2002_ , pages 345–356, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg.  ISBN 978-3-540-36755-0.
  * Porter [2023] J. Porter.  Chatgpt active user count reaches new milestone, November 2023.  URL https://www.theverge.com/2023/11/6/23948386/chatgpt-active-user-count-openai-developer-conference.  Accessed: 2024-05-20.
  * Quach et al. [2024] V. Quach, A. Fisch, T. Schuster, A. Yala, J. H. Sohn, T. S. Jaakkola, and R. Barzilay.  Conformal language modeling.  In _The Twelfth International Conference on Learning Representations_ , 2024.  URL https://openreview.net/forum?id=pzUhfQ74c5.
  * Singhal et al. [2023] K. Singhal, S. Azizi, T. Tu, S. S. Mahdavi, J. Wei, H. W. Chung, N. Scales, A. Tanwani, H. Cole-Lewis, S. Pfohl, et al.  Large language models encode clinical knowledge.  _Nature_ , 620(7972):172–180, 2023.
  * Stutz et al. [2021] D. Stutz, K. D. Dvijotham, A. T. Cemgil, and A. Doucet.  Learning optimal conformal classifiers.  In _International Conference on Learning Representations_ , 2021.
  * Varshney et al. [2023] N. Varshney, W. Yao, H. Zhang, J. Chen, and D. Yu.  A stitch in time saves nine: Detecting and mitigating hallucinations of llms by validating low-confidence generation.  _arXiv preprint arXiv:2307.03987_ , 2023.
  * Vovk [2012] V. Vovk.  Conditional validity of inductive conformal predictors.  In S. C. H. Hoi and W. Buntine, editors, _Proceedings of the Asian Conference on Machine Learning_ , volume 25 of _Proceedings of Machine Learning Research_ , pages 475–490, Singapore Management University, Singapore, 04–06 Nov 2012. PMLR.
  * Vovk et al. [2005] V. Vovk, A. Gammerman, and G. Shafer.  _Algorithmic Learning in a Random World_.  Springer-Verlag, Berlin, Heidelberg, 2005.  ISBN 0387001522.
  * Weiser [2023] B. Weiser.  Avianca airline lawsuit uses chatgpt, May 2023.  URL https://www.nytimes.com/2023/05/27/nyregion/avianca-airline-lawsuit-chatgpt.html.  Accessed: 2024-05-20.
  * Ye et al. [2024] F. Ye, M. Yang, J. Pang, L. Wang, D. F. Wong, E. Yilmaz, S. Shi, and Z. Tu.  Benchmarking llms via uncertainty quantification, 2024.  arXiv:2401.12794.
  * Zhang and Candès [2024] Y. Zhang and E. J. Candès.  Posterior conformal prediction.  _Unpublished_ , 2024.

##  Appendix A Additional details about conditional conformal

We note that Gibbs et al. [10] also consider extensions of Theorem 2.1 to
other function classes and regularized quantile regression procedures. All of
these extensions can be readily applied to our present setting.

Formally, Gibbs et al. [10] consider extensions of their procedure to cases
where $\mathcal{F}$ is a general vector space and $g_{S}$ is fit using a
penalized regression. In this section, we extend the work of Gibbs et al. [10]
to our current setting. We then describe the randomization procedure that is
used to construct our filtering threshold, $\hat{\tau}_{\text{l.a.
rand.}}(X_{n+1})$ and prove Theorems 3.1 and 3.2.

To extend our procedure to general function classes and regularizers, we
consider regressions of the form

$g_{S}=\underset{g\in\mathcal{F}}{\text{argmin}}\frac{1}{n+1}\sum_{i=1}^{n}\ell_{\alpha(X_{i})}(S(\mathbf{C}_{i},\mathbf{W}_{i})-g(X_{i}))+\frac{1}{n+1}\ell_{\alpha(X_{n+1})}(S-g(X_{n+1}))+\mathcal{P}(g),$
(12)

where $\mathcal{P}(\cdot)$ denotes any convex penalty. Following our work in
the main text, this leads to the filtering threshold
$\hat{\tau}_{\text{l.a.}}(X_{n+1})=\max\\{S:S\leq g_{S}(X_{n+1})\\}$. As
discussed earlier, this definition of $\hat{\tau}_{\text{l.a.}}(X_{n+1})$ can
be slightly conservative and thus it can be preferrable to work with a
randomized analog. We derive this analog now. First, note that (12) is
equivalent to the program

$\begin{split}\underset{p,q\in\mathbb{R}^{n+1},\
g\in\mathcal{F}}{\text{minimize}}\quad&\sum_{i=1}^{n+1}(1-\alpha)p_{i}+\alpha
q_{i}+(n+1)\mathcal{P}(g),\\\ \text{subject
to}\quad&S(\mathbf{C}_{i},\mathbf{W}_{i})-g(X_{i})-p_{i}+q_{i}=0,\ \forall
1\leq i\leq n,\\\ &S-g(X_{n+1})-p_{n+1}+q_{n+1}=0,\\\ &p_{i},q_{i}\geq 0,\
\forall 1\leq i\leq n+1.\end{split}$

Our randomized variant of $\hat{\tau}(X_{n+1})$ will be based on the dual of
this program. Following the calculations of Gibbs et al. [10], the Lagrangian
for this problem is

$\displaystyle\sum_{i=1}^{n+1}(1-\alpha(X_{i}))p_{i}+\alpha(X_{i})q_{i}+(n+1)\mathcal{P}(g)+\sum_{i=1}^{n}\eta_{i}(S(\mathbf{C}_{i},\mathbf{W}_{i})-g(X_{i})-p_{i}+q_{i})$
$\displaystyle\ \ \ \
+\eta_{n+1}(S-g(X_{n+1})-p_{n+1}+q_{n+1})-\sum_{i=1}^{n+1}(\lambda_{i}p_{i}+\xi_{i}q_{i}),$

where $\lambda_{i}$ and $\xi_{i}$ are constrained to be non-negative. Letting
$\mathcal{P}^{*}(\eta)=-\min_{g\in\mathcal{F}}((n+1)\mathcal{P}(g)-\sum_{i=1}^{n+1}\eta_{i}g(X_{i}))$
and minimizing the Lagrangian over $g$ gives

$\sum_{i=1}^{n+1}(1-\alpha(X_{i}))p_{i}+\alpha(X_{i})q_{i}+\sum_{i=1}^{n}\eta_{i}S_{i}(\mathbf{C}_{i},\mathbf{W}_{i})+\eta_{n+1}S-\mathcal{P}^{*}(\eta)+\sum_{i=1}^{n+1}\eta_{i}(q_{i}-p_{i})-\sum_{i=1}^{n+1}(\lambda_{i}p_{i}+\xi_{i}q_{i}),$

and additionally minimizing over $p_{i}$ and $q_{i}$ produces the constraints

$\lambda_{i}=(1-\alpha(X_{i}))-\eta_{i},\ \xi_{i}=\alpha(X_{i})+\eta_{i}.$

Finally, since $\lambda_{i},\xi_{i}\geq 0$, these constraints are equivalent
to the inequalities $-\alpha(X_{i})\leq\eta_{i}\leq(1-\alpha(X_{i}))$. Putting
this all together, we arrive at the dual formulation

$\begin{split}\underset{\eta\in\mathbb{R}^{n+1}}{\text{maximize}}\quad&\sum_{i=1}^{n}\eta_{i}S(\mathbf{C}_{i},\mathbf{W}_{i})+\eta_{n+1}S-\mathcal{P}^{*}(\eta),\\\
\text{subject to}\quad&-\alpha(X_{i})\leq\eta_{i}\leq(1-\alpha(X_{i})),\
\forall 1\leq i\leq n+1.\end{split}$

Let $\eta^{S}$ denote a vector of solutions to this program. Then, the
critical observation of Gibbs et al. [10] is that the above calculations give
a close relationship between the event $S\leq g_{S}(X_{n+1})$ and the value of
$\eta^{S}_{n+1}$. In particular, assuming that strong duality holds,
complementary slackness tells us that
$S>g_{S}(X_{n+1})\implies\eta^{S}_{n+1}=1-\alpha(X_{n+1})$,
$S<g_{S}(X_{n+1})\implies\eta^{S}_{n+1}=-\alpha(X_{n+1})$, and
$\eta^{S}_{n+1}\in(-\alpha(X_{n+1}),1-\alpha(X_{n+1}))\implies
S=g_{S}(X_{n+1})$. The randomization scheme derived in Gibbs et al. [10] for
fixed alpha then corresponds to randomizing over the event that
$S=g_{S}(X_{n+1})$. In particular, following that work, here we define the
randomized threshold

$\hat{\tau}_{\text{l.a. rand.}}(X_{n+1})=\max\\{S:\eta^{S}_{n+1}\leq U\\},$

where $U\sim\text{Unif}([-\alpha(X_{i}),1-\alpha(X_{i})])$ is a random
variable drawn independent of the data. The following theorem states the
coverage guarantee of this method.

######  Theorem A.1.

Assume that $\mathcal{F}$ is a vector space and that for all
$f,g\in\mathcal{F}$, the derivative of $\epsilon\mapsto\mathcal{P}(g+\epsilon
f)$ exists. Assume additionally that strong duality holds between the primal
and dual programs derived above and that
$\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}$ is computed using an algorithm
that is symmetric in the input data. Finally, assume that
$\\{(P_{i},R_{i},X_{i},\mathbf{C}_{i},\mathbf{W}_{i})\\}_{i=1}^{n+1}$ are
exchangeable and that $L(\cdot,\cdot)$ is monotone and such that
$L(\emptyset,\cdot)=0$. Then, for all $f\in\mathcal{F}$,

$\displaystyle\mathbb{E}[f(X_{n+1})(\mathbbm{1}\\{L(\hat{F}(\mathbf{C}_{n+1};\hat{\tau}_{\textup{l.a.
rand.}}(X_{n+1})),\mathbf{W}_{n+1})\leq\lambda\\}-(1-\alpha(X_{n+1})))]$
$\displaystyle\hskip
213.39566pt=-\mathbb{E}\left[\frac{d}{d\epsilon}\mathcal{P}(g_{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}+\epsilon
f)\bigg{|}_{\epsilon=0}\right].$

This theorem has two key assumptions that may appear unusual at first glance.
First, we have assumed that the dual solutions
$\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}$ are computed using an algorithm
that is symmetric in the input data. This is an extremely minor assumption and
is satisfied by any standard method for solving convex programs (e.g. interior
point solvers). For a much more detailed exposition about efficient algorithms
for computing $\\{S:\eta^{S}_{n+1}\leq U\\}$, we refer the reader to the
original work of Gibbs et al. [10]. Second, we have assumed that strong
duality holds. As we will see shortly, this assumption is always satisfied for
the linear function classes considered in the main text. For more general
vector spaces, Gibbs et al. [10] prove that this condition holds for other
common choices of $\mathcal{F}$ such as reproducing kernel Hilbert spaces and
Lipschitz functions.

We now prove our main results.

Proof [Proof of Theorem A.1] By the monotonicty assumption on $L(\cdot,\cdot)$
and our definition of the conformity score, we have that

$\mathbbm{1}\\{L(\hat{F}(\mathbf{C}_{n+1};\hat{\tau}_{\text{l.a.
rand.}}(X_{n+1})),\mathbf{W}_{n+1})\leq\lambda\\}\Leftrightarrow\mathbbm{1}\\{\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}_{n+1}\leq
U\\}.$

Thus,

$\displaystyle\mathbb{E}[f(X_{n+1})(\mathbbm{1}\\{L(\hat{F}(\mathbf{C}_{n+1};\hat{\tau}_{\text{l.a.
rand.}}(X_{n+1})),\mathbf{W}_{n+1})\leq\lambda\\}-(1-\alpha(X_{n+1})))]$
$\displaystyle=\mathbb{E}[f(X_{n+1})(\mathbbm{1}\\{\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}_{n+1}\leq
U\\}-(1-\alpha(X_{n+1})))]$
$\displaystyle=\mathbb{E}[\mathbb{E}_{U}[f(X_{n+1})(\mathbbm{1}\\{\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}_{n+1}\leq
U\\}-(1-\alpha(X_{n+1})))\mid
X_{n+1},\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}_{n+1}]]$
$\displaystyle=-\mathbb{E}[f(X_{n+1})\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}_{n+1}].$

For ease of notation let $S_{i}:=S(\mathbf{C}_{i},\mathbf{W}_{i})$, for $1\leq
i\leq n+1$. Investigating the case where $S=S_{n+1}$ gives us the Lagrangian

$\displaystyle\sum_{i=1}^{n+1}(1-\alpha(X_{i}))p_{i}+\alpha(X_{i})q_{i}+(n+1)\mathcal{P}(g_{S_{n+1}})+\sum_{i=1}^{n+1}\eta^{S_{n+1}}_{i}(S_{i}-g_{S_{n+1}}(X_{i})-p_{i}+q_{i})$
$\displaystyle-\sum_{i=1}^{n+1}(\lambda_{i}p_{i}+\xi_{i}q_{i}).$

Now, following the calculations in the proof of Proposition 4 of Gibbs et al.
[10], we find that taking a derivative along the direction $\epsilon\mapsto
g_{S_{n+1}}+\epsilon f$ and applying KKT stationarity to the above gives the
equation,

$0=\frac{d}{d\epsilon}(n+1)\mathcal{P}(g_{S_{n+1}}+\epsilon
f)\bigg{|}_{\epsilon=0}-\sum_{i=1}^{n+1}\eta^{S_{n+1}}_{i}f(X_{i}).$

So, by the exchangeability of the data we have that

$\displaystyle-\mathbb{E}[f(X_{n+1})\eta^{S(\mathbf{C}_{n+1},\mathbf{W}_{n+1})}_{n+1}]$
$\displaystyle=-\frac{1}{n+1}\mathbb{E}[\sum_{i=1}^{n+1}f(X_{i})\eta^{S_{n+1}}_{i}]$
$\displaystyle=-\mathbb{E}\left[\frac{d}{d\epsilon}(n+1)\mathcal{P}(g_{S_{n+1}}+\epsilon
f)\bigg{|}_{\epsilon=0}\right],$

as desired. ∎

###  A.1 Proof of Theorem 3.1 and Theorem 3.2

Theorems 3.1 and 3.2 from the main text can now be proven directly as
corollaries of Theorem A.1.

Proof [Proof of Theorem 3.2] This result is the special case of Theorem A.1 in
which $\mathcal{P}(\cdot)=0$, $\alpha(X_{i})=\alpha$ is a constant function,
and $\mathcal{F}$ is a finite-dimensional linear class. Under this setup, the
primal and dual programs outlined above are linear program. Since the dual
program admits the interior feasible solution $\eta=0$, Slater’s condition
immediately implies that these programs satisfy strong duality. ∎

Proof [Proof of Theorem 3.2] This result is the special case of Theorem A.1 in
which $\mathcal{P}(\cdot)=0$ and $\mathcal{F}$ is a finite-dimensional linear
class. Similar to the previous result, the resulting primal and dual programs
are linear and satisfy strong duality by Slater’s condition. ∎

##  Appendix B Details of the level-adaptive procedure

###  B.1 Method for learning $\alpha(\cdot)$

To make our approach to learning $\alpha(\cdot)$ precise, we formally define
our quality criterion using a binary function $Q(\cdot,\cdot)$ that takes in a
data point and a cutoff and returns $1$ or $0$ if the criterion is satisfied
or not, respectively. For example, for the claim retention objective described
in Section 1.1,

$Q(\mathbf{C},\hat{\tau}):=\mathbbm{1}\left\\{\frac{|F(\mathbf{C};\hat{\tau})|}{|\mathbf{C}|}\geq
0.7\right\\}.$

As discussed in the main text, when running our method we split our training
data into a portion for fitting $\alpha(\cdot)$ and portion for calibrating
the conformity score. Then, we further divide the portion of the data that is
used to fit $\alpha(\cdot)$ into two folds. We use the first fold to run the
conditional conformal procedure at a fixed grid of quantiles,
$\alpha\in\\{0.01,\dots,0.99\\}$, and the second dataset to evaluate
$Q(\mathbf{C}_{i};\hat{\tau}_{\alpha}(X_{i}))$ for each choice of $\alpha$.
Here, $\hat{\tau}_{\alpha}(X_{i})$ denotes the conditional conformal cutoff
evaluated for test claims $\mathbf{C}_{i}$ at fixed level $1-\alpha$.

After collecting our estimates of
$Q(\mathbf{C}_{n+1};\hat{\tau}_{\alpha}(X_{n+1}))$, we compute the maximum
$\alpha$ at which the quality criterion is achieved. Formally, for each point
$(\mathbf{C}_{i},X_{i})$ in the dataset held out from fitting, we compute

$\displaystyle\alpha^{*}_{i}=\inf\\{\alpha:\forall\beta\geq\alpha,\
Q(\mathbf{C}_{i},\hat{\tau}_{\beta}(X_{i}))=1\\}.$ (13)

With this data in hand, our goal now is to fit a function $\alpha(\cdot)$ that
predicts $\alpha^{*}_{i}$ from $(X_{i},\alpha^{*}_{i})$. In principle, this
could be done using any number of regression algorithms. In our experiments,
we choose to estimate a quantile of $\alpha^{*}_{i}\mid X_{i}$ using the same
function class we used to run our conditional conformal procedure. We then
truncate these estimates to lie above $0.1$. See Figure 7 for a plot of this
estimated quantile and the underlying data points used to fit this regression.
Our choices of quantile and truncation are motivated by our desire to ensure
that the adaptive level will guarantee the quality criterion for most test
points without issuing completely vacuous guarantees, i.e., fitting some
$\alpha(\cdot)$ whose range is concentrated around $1$ or $0$.

Figure 7: For a hold-out set of size $424$, we plot the optimal level
threshold, $\alpha^{*}_{i}$ for claim retention (13) against the number of
Wikipedia page views (on the log scale) for the associated person. Letting
$v_{i}$ denote the view count for person $i$, the black line denotes the
estimate of the $0.25$-quantile of $\alpha^{*}_{i}\mid v_{i}$ obtained by
regressing over the function class given by
$\\{\beta_{0}+\sum_{i=1}^{3}\beta_{i}v^{i}\mid\beta\in\mathbb{R}^{4}\\}$.

###  B.2 Dependence of the level-adaptive guarantee on the function class

The quality of our level-adaptive guarantee strongly depends on the choice of
function class, $\mathcal{F}$. To understand this, recall that split conformal
prediction corresponds to taking $\mathcal{F}$ to be the class of constant
functions, $\mathcal{F}=\\{x\mapsto\beta:\beta\in\mathbb{R}\\}$. In this case,
Theorem 3.2 states that

$\mathbb{E}[\mathbbm{1}\\{L(\mathbf{C}_{n+1},\mathbf{W}_{n+1})\leq\lambda\\}]=\mathbb{E}[(1-\alpha(X_{n+1}))],$

i.e. with probability $\mathbb{E}[1-\alpha(X_{n+1})$] the error rate of our
method lies at the target level. This guarantee is extremely weak; our
objective is to ensure that the nominal probability is pointwise close to the
true level, i.e.
$|\mathbb{P}(L(\mathbf{C}_{n+1},\mathbf{W}_{n+1})\leq\lambda\mid\alpha(X_{n+1}))-(1-\alpha(X_{n+1}))|$
is small. In the main text, we saw empirical results in which our methods were
able to approximately achieve this target. These result were obtained by
designing $\mathcal{F}$ to include functions that depend on $\alpha(X_{n+1})$.

Figure 8: Comparison of the realized and nominal levels of our level-adaptive
method for various choices of $\mathcal{F}$. Here,
$(X_{i},Y_{i})\sim\mathcal{N}(0,I_{2})$ and we set the conformity score to be
simply $S(X_{i},Y_{i})=Y_{i}$. In this experiment, we use our level-adaptive
method (Section 3.2 in the main text) to construct prediction sets for $Y_{i}$
given covariates $X_{i}$. We set $\alpha(X)=\sigma(X)$ where $\sigma(\cdot)$
denotes the sigmoid function with temperature $1$. We then run the level-
adaptive method on a calibration set of size $n=1000$ and evaluate the method
on $1$ test point; the plotted points (center, right) are obtained from $500$
trials. The left panel shows results for
$\mathcal{F}=\\{x\mapsto\beta:\beta\in\mathbb{R}\\}$, while the right panel
displays results for
$\mathcal{F}=\\{(1,\alpha(X))^{\top}\beta:\beta\in\mathbb{R}^{2}\\}$.

To demonstrate the importance of this choice of $\mathcal{F}$ more explicitly,
Figure 8 compares the realized difference between the true coverage,
$\mathbb{P}(Y_{n+1}\in\hat{C}(X_{n+1})\mid\alpha(X_{n+1}))$ and the nominal
level $1-\alpha(X_{n+1})$ when
$\mathcal{F}=\\{x\mapsto\beta:\beta\in\mathbb{R}\\}$ and
$\mathcal{F}=\\{(1,\alpha(X))^{\top}\beta:\beta\in\mathbb{R}^{2}\\}$ on a
simple synthetic dataset. As anticipated, when $\mathcal{F}$ consists only of
constant functions, the nominal guarantee is spurious, and the true
probability of coverage is uncorrelated with the claimed level (left panel).
This is corrected by adding $\alpha(X)$ to the feature space of $\mathcal{F}$;
despite being quite simple this choice empirically achieves the desired
calibration (right panel). We leave a more substantial investigation of the
trade-off between $\mathcal{F}$ complexity, empirical calibration, and
efficiency to future work.

##  Appendix C Details of the Boosting Procedure

For the boosting procedure, we will assume that we are working with the
derandomized variant of the conditional conformal method of Gibbs et al. [10].
In addition, these results will hold only for the finite-dimensional function
class variant of their method, i.e., we assume that

$\mathcal{F}=\\{\Phi(\cdot)^{\top}\beta:\beta\in\mathbb{R}^{d}\\}.$

We first restate and then prove Proposition 3.1.

######  Proposition C.1.

Assume that there the solution to the quantile regression given by (7) with
$S=\hat{\tau}_{i}(\theta)$ is non-degenerate, and let $B$ denote the optimal
basis of this solution. Then $\hat{\tau}_{i}(\theta)$ is locally linear in
$\theta$ with derivative given by

$\partial_{\theta}\hat{\tau}_{i}(\theta)=\Phi(X)_{B}^{-1}\partial_{\theta}S_{B}(\theta).$
(14)

Proof If the primal solution is non-degenerate, it is well-known that the dual
variables corresponding to the optimal basis are strictly bounded away from
its constraints [8]. Since the dual variables are piecewise linear in
$\\{S_{i}\\}_{i=1}^{n}$ (a fact commonly exploited in sensitivity analysis for
linear programs) [8], we know that there exists some $\epsilon$-ball in $S$
for which the basis is unchanged. Therefore, so long as $S$ is continuous in
$\theta$ (and we have assumed differentiability), the stated result holds. ∎

When running Algorithm 1, we must set aside some data to run the final
conformal procedure. Once the scores are boosted, they must be evaluated on a
fresh dataset for the resulting filtered output to satisfy any of our
guarantees.

Data: Boosting dataset $\mathcal{D}=\\{\mathbf{D}_{i}\\}_{i=1}^{n}$,
conformity score function $S_{\theta}(\cdot,\cdot)$, function class basis
$\mathbf{\Phi}$, initialization $\theta_{0}$, sigmoid temperature $\lambda$,
level $\alpha$, boosting iterations $N$.

for  _$i\in[N]$_ do

$\ell=0$;

$\mathcal{D}_{1},\mathcal{D}_{2}=\textsf{RandomSplit}(\mathcal{D})$ ;

$\Phi=\Phi(\mathcal{D}_{1})$ ;

/* Shorthand for computing the basis on the first set */

$S=S_{\theta}(\mathcal{D}_{1})$;

/* Shorthand for computing the scores on the first set */

for  _$\mathbf{D}_{i}\in\mathcal{D}_{2}$_ do

conf = CondConf$(S_{\theta},\Phi)$;

$B=$ conf.getOptimalBasis$(\alpha,\mathbf{D}_{i})$;

$\hat{\beta}_{i}=\Phi_{B}^{-1}(\mathcal{D}_{1})S_{B}$;

$\ell=\ell+\sigma_{\lambda}(\Phi_{n+1}^{\top}\hat{\beta}_{i}-\sum_{j=1}^{n_{i}}p_{\theta}(P_{i},C_{ij}))$;

$\theta_{i}=\text{Adam}(\ell)$.step();

return $\theta_{N}$.

Algorithm 1 Conditional boosting

We make one important simplification in this algorithm to produce this paper’s
experiments. The subroutine conf.getOptimalBasis obtains the optimal basis in
Algorithm 1 by identifying the $\text{dim}(\Phi)$ points that are interpolated
by the regression when $S_{n+1}>\hat{\tau}_{i}(\theta)$. Identifying this set
is computationally burdensome since each gradient step in $\theta$ requires
computing $\hat{\tau}_{i}(\theta)$ (and therefore $\hat{\beta}_{i}$) for each
point in the second split. Thus, the gradient computation step scales
quadratically in $|\mathcal{D}_{2}|$. A linear-time approximation to the
gradient can be obtained by defining $B$ as the optimal basis from the
quantile regression fit to $\mathcal{D}_{1}$ alone. This approximation, which
does not account for the test-point augmentation in the conditional conformal
procedure, is much faster since it yields a single $\hat{\beta}$ to use for
all the test points. To concretely modify Algorithm 1, $B$ is defined as the
optimal basis of the quantile regression fit to $\mathcal{D}_{1}$ alone, the
computation in the nested for loop is removed, and the estimated threshold in
the sigmoid function becomes $\Phi_{n+1}^{\top}\hat{\beta}$.

##  Appendix D Experiments

###  D.1 Claim scores

We collect several features to use for estimating a confidence level in each
claim. Unless otherwise noted, the claim scoring function used in this paper
is defined by the “frequency” score examined by Mohri and Hashimoto [19]. We
compute this score by querying GPT-3.5-Turbo 5 times at a temperature of
$T=5$. For each claim, we re-query the LLM to ask if the claim is supported in
the resampled generation. These scores which can be $-1$ for contradicted, $0$
for not present, and $1$ for supported are then averaged over the $5$
responses. For example, a claim that is also present in $3$ out of the $5$
responses, but absent in the other two would receive a score of $0.6$.

Since the frequency score requires many API queries, we also investigate
several cheaper and faster-to-compute features for claim scoring. Following
Mohri and Hashimoto [19], we also collect the self-reported probability
obtained by directly asking the LLM to report its estimated probability of
claim correctness to three significant figures. We also compute the ordinal
score, i.e., the order in which the claim appeared in the original response.
Going beyond Mohri and Hashimoto [19], we compute the LLM’s internal
probability of each claim by querying the model with the list of claims and
asking it to output a single-character (T or F) assessment of its beliefs. The
internal probability of the model can then be computed by exponentiating the
log probability of the returned token.

###  D.2 Prompts

To parse the initial response into scorable sub-claims, we prompt the LLM
(GPT-4o, in our experiments). After first parsing the prompt into its
component sentences, we copy the method of Min et al. [18] (made available on
GitHub under an MIT license) and use in-context learning to improve the
parsing accuracy of the LLM. We first use the BM25 ranking function to match
our sentences to similar examples previously parsed by Min et al. [18]. We
prepend these gold-standard examples as well as the new sentence to be parsed
to the prompt,

> Please breakdown the following sentence into independent facts: […]

To annotate the subclaims, we either retrieve the response given in the
MedLFQA dataset or emulate Min et al. [18] and retrieve Wikipedia passages
that are most relevant (using the BM25 ranking function) to the subject of the
biography. The prompt includes this passage followed by the previous claims in
the output that have already been annotated to ensure self-consistency,

> Answer the question about […] based on the given context and your previous
> answers. Title: […] Text: […] Previous input: […] True or False? Output: […]
> Input: […] True or False? Output:

To evaluate the support of the claims in new response, we prompt the LLM using

> You will get a list of claims and piece of text. For each claim, score
> whether the text supports, contradicts, or is unrelated to the claim.
> Directly return a jsonl, where each line is "id":[CLAIM_ID],
> "score":[SCORE]. Directly return the jsonl with NO explanation or ANY other
> formatting. For the [SCORE], return 1 for supports, -1 for contradicts, and
> 0 for unrelated. The claims are: […] The text is: […]’

We obtain self-assessed probabilities by prompting the LLM using

> You will get a list of claims and the original prompt that motivated these
> claims. For each claim, assess the probability of correctness. Directly
> return a jsonl, where each line is "id":[CLAIM_ID], "gpt-score":[SCORE].
> Directly return the jsonl with NO explanation or ANY other formatting. For
> the [SCORE], return the esimated probability of correctness to three
> significant figures. The original promptis: […] The claims are: […]

We obtain the internal probability of the model using a very similar prompt,

> You will get a list of claims and the original prompt that motivated these
> claims. For each claim, assess the correctness. Directly return a jsonl,
> where each line is "id":[CLAIM_ID], "gpt-bool":[BOOL]. Directly return the
> jsonl with NO explanation or ANY other formatting. For the [BOOL], return
> "T" or "F" in quotes so that it is valid json. The original prompt is: […]
> The claims are: […]

###  D.3 Details of Section 4.3

To define features for the conditional conformal function class, we obtain
page metadata from the Wikidata API. The metadata we use is the number of
views of the biography’s Wikipedia article in January 2023. Since this data is
quite right-skewed, the view counts for the most popular articles can cause
numerical issues in our optimizer. Consequently, we trim the largest entries
to the $0.95$-quantile of the view data.

Here we also provide some additional details regarding the function classes
used in our biography experiments. In all examples, we aim to provide uniform
coverage guarantees regardless of the underlying popularity of the topic. In
the fixed-level filtered biographies, we run the conditional conformal method
with
$\mathcal{F}=\\{\beta_{0}+\sum_{i=1}^{3}\beta_{i}v^{i}\mid\beta\in\mathbb{R}^{4}\\}$,
where $v$ denotes the number of views of the corresponding Wikipedia page in
January 2023. In the level-adaptive examples, a nearly identical two-step
workflow is used to estimate $\alpha(\cdot)$ and estimate the method’s
coverage. Here we make one small change; we estimate $\alpha(\cdot)$ using a
$0.25$-quantile regression over $\mathcal{F}$ (see Figure 7 for a plot of this
estimate). In the final level-adaptive fit, we add an additional linear term
to this function class given by $\beta_{4}(\alpha(\cdot)-0.1)^{2}$. Note that
in our experiments, we truncate $\alpha(\cdot)$ to lie above $0.1$. As a
result, a substantial proportion of outputs receive that estimated quantile
and thus, $(\alpha(\cdot)-0.1)^{2}$ correlates with the more variable portion
of the quantile function.

Though the final experiments in this section are run using the more performant
frequency score, the right panel of Figure 5 is obtained by finding an optimal
linear combination of the three cheaper-to-obtain claim scores (self
evaluation, token probability, ordinal). We obtain the displayed result by
running $1000$ steps of Adam (with PyTorch defaults, i.e., learning rate
$0.001$) through the conditional conformal procedure given by the same
$\mathcal{F}$ described in the previous paragraph.