#  C-RAG: Certified Generation Risks for Retrieval-Augmented Language Models

Mintong Kang
UIUC
<EMAIL_ADDRESS>
&Nezihe Merve Gürel
TU Delft
<EMAIL_ADDRESS>
&Ning Yu
Salesforce Research
<EMAIL_ADDRESS>
&Dawn Song
UC Berkeley
<EMAIL_ADDRESS>
&Bo Li
UChicago & UIUC
<EMAIL_ADDRESS>
###### Abstract

Despite the impressive capabilities of large language models (LLMs) across
diverse applications, they still suffer from trustworthiness issues, such as
hallucinations and misalignments. Retrieval-augmented language models (RAG)
have been proposed to enhance the credibility of generations by grounding
external knowledge, but the theoretical understandings of their generation
risks remains unexplored. In this paper, we answer: 1) whether RAG can indeed
lead to low generation risks, 2) how to provide provable guarantees on the
generation risks of RAG and vanilla LLMs, and 3) what sufficient conditions
enable RAG models to reduce generation risks. We propose C-RAG, the first
framework to certify generation risks for RAG models. Specifically, we provide
conformal risk analysis for RAG models and certify an upper confidence bound
of generation risks, which we refer to as conformal generation risk. We also
provide theoretical guarantees on conformal generation risks for general
bounded risk functions under test distribution shifts. We prove that RAG
achieves a lower conformal generation risk than that of a single LLM when the
quality of the retrieval model and transformer is non-trivial. Our intensive
empirical results demonstrate the soundness and tightness of our conformal
generation risk guarantees across four widely-used NLP datasets on four state-
of-the-art retrieval models.

##  1 Introduction

Large language models (LLMs) (Touvron et al., 2023; OpenAI et al., 2023)
recently exhibit emergent abilities across different NLP tasks, such as text
summarization, question answering, and machine translation. However, existing
works (Wang et al., 2023a; Liang et al., 2022; Liu et al., 2023) show that the
generations of LLMs can be unreliable, untrustworthy, and risky in many cases.
Therefore, certifiably controlling the generation risks of LLMs becomes
particularly important before the deployment of LLMs, especially in safety-
critical domains.

Retrieval-augmented language models (RAG) (Lewis et al., 2020; Karpukhin et
al., 2020; Xiong et al., 2020) have been proposed to enhance the credibility
of LLMs by retrieving relevant documents from an external knowledge base and
generating contents conditioned on the retrieved knowledge. RAG models are
shown effective in mitigating generation risks via in-context learning from
the retrieved documents (Brown et al., 2020). However, theoretical
understandings of their generation risks still remain unexplored. In this
work, we focus on this problem and ask:

Can RAG indeed lead to low generation risks? How can we provide provable
guarantees on the generation risks of RAG and vanilla LLMs? What are the
sufficient conditions that enable RAG models to reduce generation risks? Can
we provably control the generation risks below a desired level?

To theoretically analyze the generation risks of RAG and answer the above
questions, we propose C-RAG, the first framework of certified generation risks
for RAG models. We first propose a constrained generation protocol for RAG
models to produce a controlled set of generations. The protocol operates based
on specific parameter configurations, including the number of retrieved
examples, the size of the generation set, and a similarity threshold for
generation diversity. We then provide conformal analysis (Bates et al., 2021;
Angelopoulos et al., 2021, 2022) for RAG models under the constrained
generation protocol, aiming to provably control the generation risks based on
test statistics from in-distribution calibration samples. To achieve this
goal, we derive a high-probability upper bound of generation risks during
inference time, which we call conformal generation risk. We show that (a) the
conformal generation risk serves as a sound upper bound to the empirical
generation risks given a RAG configuration in Proposition 1; (b) the
generation risk can be certifiably controlled below a desired level by
computing a valid set of RAG configurations via C-RAG in Proposition 2; (c)
the conformal analysis can be extended to more complex scenarios under test-
time distribution shifts in Theorem 2, which presents the first generation
risk guarantee under test-time distribution shifts for general bounded risk
functions. Based on our conformal analysis for the generation risks of RAG and
vanilla LLMs, we prove that (a) the conformal generation risk of RAG is lower
than that of the corresponding vanilla LLM in Theorem 1; (b) under bounded
test-time distribution shifts, RAG also lowers the conformal generation risks
compared to the vanilla LLM in Theorem 3.

We evaluate the conformal generation risk guarantees of C-RAG with different
retrieval models on four widely-used datasets. For all retrieval methods and
datasets, we empirically validate that our conformal generation risk
guarantees are sound and tight even with distribution shifts, as they upper
bound the empirical generation risks observed on random test sets while
maintaining only a minimal gap, narrowing down to the scale of $1e-3$. We
empirically show that RAG consistently achieves a lower conformal generation
risk than a single LLM without retrieval, which is consistent with our
theoretical findings in Sections 4 and 5. We also evaluate the conformal
generation risk for different SOTA retrieval models, such as sparse encoding
metrics BM25 (Robertson et al., 2009), text-embedding-ada-002 model from
OpenAI, bge model from BAAI (Zhang et al., 2023a), and supervised fine-tuned
embedding model (Wang et al., 2023b) to validate our analysis on retrieval
quality. We show that among these models, text-embedding-ada-002 and
supervised fine-tuned embedding models outperform other baselines in achieving
low conformal generation risks.

##  2 Related work

Retrieval augmented generation (RAG) is a framework for improving the
generation quality of LLMs via retrieving relevant information from an
external knowledge base and grounding the model on the retrieved knowledge for
conditional generations. SOTA retrieval methods (Lewis et al., 2020; Karpukhin
et al., 2020; Xiong et al., 2020) employ dual encoders to project both query
and candidate texts into the embedding space and retrieve candidate texts that
exhibit high similarity to the embedded query text. Although RAG is
demonstrated to be effective in enhancing the generation credibility, their
theoretical understanding is limited. Basu et al. conduct retrieval analysis
for a constrained function and data class from a statistical perspective, but
the results cannot be applicable to self-attention transformers and to
arbitrary data distribution. In this work, we provide the first theoretical
analysis of how RAG leads to low generation risks in self-attention
transformers for arbitrary data distribution.

Conformal prediction is a statistical technique used to create prediction sets
with assured coverage. (Vovk et al., 1999, 2005; Lei et al., 2013; Yang &
Kuchibhotla, 2021). Broadly, conformal risk control methods (Bates et al.,
2021; Angelopoulos et al., 2021, 2022; Quach et al., 2023) provide a high-
confidence risk guarantee for black-box risk functions, assuming data
exchangeability. However, the risk guarantee can be broken under test-time
distribution shifts. While Angelopoulos et al. and Farinhas et al. offer a
valid conformal risk guarantee for monotonic risk functions under distribution
shifts, the monotonicity assumption is not always practical. In this work, we
introduce the first conformal risk guarantee for general bounded risk
functions, under distribution shifts at test time.

Figure 1:  Overview of C-RAG. In the estimation stage (upper row), the
conformal risk controller computes conformal generation risks for different
RAG configurations (Proposition 1), and valid configuration sets for different
risk levels (Proposition 2), both based on risk statistics on the calibration
set. In the inference stage (lower row), for any configuration
${\bm{\lambda}}$ and any desired risk level $\alpha$ provided by users, the
conformal risk controller outputs the conformal generation risk
$\hat{\alpha}_{\bm{\lambda}}$ with Risk Guarantee (1) and the configuration
set $\hat{\Lambda}_{\alpha}$ with Risk Guarantee (2).

##  3 Conformal generation risks of RAG models

We introduce the problem setup in Section 3.1, our constrained generation
protocol for RAG models in Section 3.2, and the conformal generation risks in
Section 3.3. We prove that (1) Given a RAG configuration, C-RAG provides a
high-probability generation risk upper bound in Proposition 1, and (2) Given a
desired risk level $\alpha$, C-RAG offers a set of configurations that can
provably maintain the risk below $\alpha$ in Proposition 2.

###  3.1 Problem setup

For a pretrained language model (LM) and any user input text, we aim to
provide rigorous guarantees for the generation risks (e.g., $1-\text{ROUGE}$).
To achieve this, we develop a constrained generation protocol for RAG models.
The generation protocol is governed by adjustable parameter configurations
(e.g., number of retrieved examples, size of generations), which allow for
more controlled RAG generations to achieve a desired risk level.

Formally, we let ${\mathcal{V}}$ be the vocabulary set, $n_{I}$ be the maximal
length of input text and $n_{O}$ be the maximal length of output text. Let
${\mathcal{X}}:={\mathcal{V}}^{n_{I}}$ be the input text space, and
${\mathcal{Y}}:={\mathcal{V}}^{n_{O}}$ be the output text space. We notate
$p_{\theta_{l}}(y|x)~{}(x\in{\mathcal{X}},y\in{\mathcal{Y}})$ as the
probability distribution of output text $y$ given input text $x$, estimated by
a pretrained LM parameterized by $\theta_{l}$. Consider a RAG generation
protocol $T_{{\bm{\lambda}},p_{\theta_{l}}}:{\mathcal{X}}\mapsto
2^{\mathcal{Y}}$ with LM $\theta_{l}$ and parameter configuration
${\bm{\lambda}}\in\Lambda={\mathbb{R}}^{B}$, where $B$ is the maximal number
of parameters to control the generation procedure. To evaluate the quality of
the generation under $T_{{\bm{\lambda}},p_{\theta_{l}}}(x)$ given input $x$,
we define a risk function
$R(T_{{\bm{\lambda}},p_{\theta_{l}}}(x),y):2^{\mathcal{Y}}\times{\mathcal{Y}}\mapsto[0,1]$,
where $y$ is the reference text of $x$. For text generation tasks, a typical
selection of the risk function could be $1-\max_{y^{\prime}\in
T_{{\bm{\lambda}},p_{\theta_{l}}}(x)}\text{ROUGE}(y^{\prime},y)$, where ROUGE
measures the matching score between the generation $y^{\prime}$ and reference
text $y$. Notably, our generation protocol outputs a set of generations
instead of just one, allowing us to explore better generations and adjust the
generation set size through a parameter for risk control.

###  3.2 Constrained generation protocol for RAG models

RAG models (Wang et al., 2023b; Rubin et al., 2021; Huang et al., 2023)
combine a retrieval model and a generation LM. The retrieval model retrieves
$N_{\text{rag}}$ relevant examples to the query from an external knowledge
base, and the LM learns in-context from these examples. The knowledge base
contains $N_{\text{ext}}$ samples in
$\hat{{\mathcal{D}}}_{\text{ext}}=\\{(X_{i},Y_{i})\\}_{i=1}^{N_{\text{ext}}}$.
The retrieval model uses an encoder to map instances into an embedding space,
and then identifies the relevant examples to the query $X_{\text{test}}$ based
on similarity. This similarity, defined by
$s_{\theta_{r}}(\cdot,\cdot):{\mathcal{X}}\times{\mathcal{X}}\mapsto{\mathbb{R}}$
and parameterized by $\theta_{r}$, is used to find the nearest examples using
KNN search in the embedding space.

We arrange the retrieved $N_{\text{rag}}$ in-context examples and the test
example $X_{\text{test}}$ into augmented input text $X^{\text{(rag)}}$ using a
template. We then sample the generation from
$p_{\theta_{l}}(\cdot|X^{\text{(rag)}})$ repeatedly until $\lambda_{g}$
generations are collected. To control the diversity of generations, we reject
those with a similarity higher than a threshold $\lambda_{s}$ to the previous
generations. In essence, the constrained generation protocol is controlled by
configuration ${\bm{\lambda}}=[N_{\text{rag}},\lambda_{g},\lambda_{s}]$ and
output a generation set $T_{{\bm{\lambda}},p_{\theta_{l}}}(x)$ based on the
configuration ${\bm{\lambda}}$ and input $x$. We refer to Algorithm 1 in
Section C.1 for the pseudocode of the protocol.

###  3.3 Conformal generation risks for RAG models

We certify generation risks of the RAG models with the constrained generation
protocol $\normalsize T_{{\bm{\lambda}},p_{\theta_{l}}}$ via conformal risk
analysis (Bates et al., 2021; Angelopoulos et al., 2022, 2021). Conformal
analysis provably controls the generation risks based on test statistics from
in-distribution calibration samples. In this work, we consider a calibration
set
$\hat{{\mathcal{D}}}_{\text{cal}}=\\{(X_{i},Y_{i})\\}_{i=1}^{N_{\text{cal}}}$
with size $\normalsize N_{\text{cal}}$, and compute the empirical generation
risk
$\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})=\nicefrac{{1}}{{N_{\text{cal}}}}\sum_{(x,y)\in\hat{{\mathcal{D}}}_{\text{cal}}}R(T_{{\bm{\lambda}},p_{\theta_{l}}}(x),y)$.

#### Risk Guarantees for RAG Models

For an LM $\theta_{l}$, calibration set $\hat{{\mathcal{D}}}_{\text{cal}}$,
test sample $(X_{\text{test}},Y_{\text{test}})$, generation protocol
$T_{{\bm{\lambda}},p_{\theta_{l}}}$ with configuration ${\bm{\lambda}}$ and
confidence level $1-\delta~{}(\delta\in[0,1])$, C-RAG provides two types of
generation risk guarantees for RAG models:

######  Proposition 1 (Risk Guarantee (1)).

Given a configuration ${\bm{\lambda}}$ in generation protocol, C-RAG
guarantees that:

$\normalsize{\mathbb{P}}\left[R(T_{{{\bm{\lambda}}},p_{\theta_{l}}}(x),y)\leq\hat{\alpha}_{\bm{\lambda}}\right]\geq
1-\delta,\vspace{\pspace}$ (1)

where the high-probability risk upper bound $\hat{\alpha}_{\bm{\lambda}}$, the
so-called conformal generation risk, is given by:

$\hat{\alpha}=\min\left\\{h^{-1}\left(\dfrac{1/\delta}{N_{\text{cal}}};\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right),\Phi^{-1}_{\text{bin}}\left(\dfrac{\delta}{e};N_{\text{cal}},\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right)\right\\}\vspace{\pspace}$

with $h^{-1}(\cdot;\cdot)$ as the partial inverse $h^{-1}(h(a,b);a)=b$ of
$h(a,b)=a\log(\nicefrac{{a}}{{b}})+(1-a)\log(\nicefrac{{(1-a)}}{{(1-b)}})$,
and $\Phi^{-1}_{\text{bin}}$ as the inverse of binomial cumulative
distribution function (CDF).

######  Proposition 2 (Risk Guarantee (2)).

Given a desired risk level $\alpha$, C-RAG computes a configuration set
$\hat{\Lambda}_{\alpha}$ such that each configuration in
$\hat{\Lambda}_{\alpha}$ is guaranteed to keep the generation risk below
$\alpha$. Namely,

$\vspace{\pspace}{\mathbb{P}}\left[\sup_{\hat{{\bm{\lambda}}}\in\hat{\Lambda}_{\alpha}}\left\\{R\left(T_{\hat{{\bm{\lambda}}},p_{\theta_{l}}}(x),y\right)\right\\}\leq\alpha\right]\geq
1-\delta,\vspace{\minspace}$ (2)

where the valid configuration set $\hat{\Lambda}_{\alpha}$ is given by family-
wise error rate controlling algorithms such as Bonferroni correction:
$\hat{\Lambda}_{\alpha}=\\{\hat{{\bm{\lambda}}}_{j}:p_{j}\leq\delta/|\Lambda|\\}$
where $p_{j}$ is the $\normalsize p$-value of the null hypothesis:
${\mathcal{H}}_{j}:R(T_{{\bm{\lambda}},p_{\theta_{l}}}(x),y)>\alpha~{}(j\in\\{1,...,|\Lambda|\\})$
and can be computed by finite-sample valid bounds as shown in Section D.2.

#### Connection between Risk Guarantees (1) and (2)

Risk Guarantee (1) computes the conformal generation risk (risk upper bound)
$\hat{\alpha}_{\bm{\lambda}}$ given a configuration ${\bm{\lambda}}$, while
Risk Guarantee (2) computes a configuration set $\hat{\Lambda}_{\alpha}$ such
that any configuration in the set results in a risk below the desired level
$\alpha$. Risk Guarantee (2) can be conceptualized as accepting configurations
with generation risks statistically below $\alpha$ with a certain error rate
(p-value), such that the union of error rates over parameter space is within
the uncertainty budget $\delta$. The Bonferroni correction in Proposition 2
adopts an even partition of the uncertainty budget, while we can have a
dynamic partition algorithm based on graph search (see Section D.2).
Therefore, Risk Guarantee (1) and (2) are connected by the duality between
p-values and confidence intervals (Bates et al., 2021). We mainly focus on the
conformal analysis of Risk Guarantee (1) in the following, and the results can
be extrapolated to Risk Guarantee (2) directly. We defer the proofs of
Propositions 1 and 2 to Appendix D.

#### Out-of-distribution test samples

Conformal risk analysis assumes that test and calibration samples come from
the same distribution, which allows statistical risk predictions for test
samples based on the calibration data. While the conformal generation risk
bounds are previously studied (Angelopoulos et al., 2022; Farinhas et al.,
2023b), the scope is limited to the monotonic risk functions. In this work, we
extend the scope to provide the first conformal generation risk analysis under
test-time distribution shifts for general bounded risk functions in Section 5.

##  4 Theoretical analysis of C-RAG

In this section, we prove that RAG model achieves a lower conformal generation
risk compared to LLMs without retrievals and its benefits are correlated with
the quality of the retrieval model and transformer. We provide the structure
of our theoretical analysis and conclusions in Figure 2.

Figure 2: Certification framework of C-RAG. We provide theoretical results
with the data exchangeability assumption in Section 4 (upper row) and extend
the results to more complex scenarios under test distribution shifts in
Section 5 (lower row).

###  4.1 Analysis setup

For our analysis, paralleling the previous transformer studies by (Von Oswald
et al., 2023; Zhang et al., 2023b; Han et al., 2023), we consider a one-layer
self-attention transformer parameterized with the embedding matrix
$W_{E}:{\mathcal{V}}\mapsto{\mathbb{R}}^{d_{1}}$, query matrix
$W_{Q}:{\mathbb{R}}^{d_{1}}\mapsto{\mathbb{R}}^{d_{2}}$, key matrix
$W_{K}:{\mathbb{R}}^{d_{1}}\mapsto{\mathbb{R}}^{d_{2}}$, value matrix
$W_{V}:{\mathbb{R}}^{d_{1}}\mapsto{\mathbb{R}}^{d_{2}}$, projection matrix
$W_{P}:{\mathbb{R}}^{d_{2}}\mapsto\Delta^{|{\mathcal{V}}|}$, and treat each
instance approximately as a single token. The retrieval-augmented input text
then consists of $N_{\text{rag}}$ retrieved examples and $1$ query example. We
denote the augmented input text by
${\bm{q}}\in{\mathcal{V}}^{N_{\text{rag}}+1}$. We categorize pairs of queries
${\bm{q}}_{i},{\bm{q}}_{j}~{}(i,j\in[N_{\text{rag}}+1])$ as positive if they
convey identical semantic meanings, indicated by
$g({\bm{q}}_{i})=g({\bm{q}}_{j})$. In this context, ${\bm{q}}_{i}$ can be
referred to as a positive example of ${\bm{q}}_{j}$. Conversely, pairs
${\bm{q}}_{i},{\bm{q}}_{j}~{}(i,j\in[N_{\text{rag}}+1])$ are considered
negative if they are semantically different. We use such a definition for
clear interpretation of our findings, but our analysis can be extended to
include broader definitions of positive pairs, as addressed in the remarks of
Theorem 1.

Following the single-layer transformer formulation in (Von Oswald et al.,
2023), given an input text ${\bm{q}}$, we consider the single-token output
$O^{\text{(rag)}}({\bm{q}})\in\Delta^{|{\mathcal{V}}|}$ corresponding to the
query example ${\bm{q}}_{N_{\text{rag}+1}}$ at the last position, formulated
as:

$\displaystyle
O^{\text{(rag)}}({\bm{q}})=\sigma\left(W_{P}W_{V}\left\\{W_{E}{\bm{q}}_{N_{\text{rag}+1}}+(W_{E}{\bm{q}})\sigma\left((W_{K}W_{E}{\bm{q}})^{T}W_{Q}W_{E}{\bm{q}}_{N_{\text{rag}+1}}\right)\right\\}\right),$
(3)

where $\sigma(\cdot)$ is the Softmax function. Note that without RAG, the
output probability vector $O({\bm{q}})$ is formulated as
$O({\bm{q}})=\sigma\left(W_{P}W_{V}W_{E}{\bm{q}}_{N_{\text{rag}+1}}\right)$.

###  4.2 Retrieval quality analysis

To quantify the quality of retrieval models, we introduce the concept of
$V_{\text{rag}}$-retrieval model, where $V_{\text{rag}}$ measures the variance
of the contrastive loss of the retrieval model. A small $V_{\text{rag}}$
implies a well-trained low-variance retrieval model and can be theoretically
linked to the retrieval quality, which is measured by the number of retrieved
positive examples with respect to the query text.

######  Definition 1 ($V_{\text{rag}}$-retrieval model).

Consider a retrieval model with similarity measurement
$s_{\theta_{r}}(\cdot,\cdot)$ parameterized with $\theta_{r}$ and trained with
contrastive loss ${\mathcal{L}}_{\text{cont}}$. Let $x^{+},x^{-}$ be positive
and negative samples to sample $x$. Consider common contrastive loss
${\mathcal{L}}_{\text{cont}}=-\log\left(\sigma_{\text{sig}}(\exp\\{s_{\theta}(x,x^{-})-\exp\\{s_{\theta}(x,x^{+}))\right)$,
where $\sigma_{\text{sig}}(\cdot)$ is the sigmoid function. We define a
$V_{\text{rag}}$-retrieval model as the retrieval model with (a) a non-trivial
utility such that the expected contrastive loss $L_{\tau}$ is better than
random: $L_{\tau}:=\mathbb{E}[{\mathcal{L}}_{\text{cont}}]<\ln 2$ (i.e.,
$\mathbb{E}[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})]>0$); and (b) bounded
variance such that the training is stable and converges well:
$V_{\text{rag}}:={\mathbb{V}[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})]^{1/2}}{\log(\exp\\{L_{\tau}\\}-1)}<1$

######  Remarks.

(R1) Note that a retrieval model with random initialization can achieve
$\mathbb{E}[s_{\theta}(x,x^{+})]=\mathbb{E}[s_{\theta}(x,x^{-})]$
asymptotically. We merely assume a $V_{\text{rag}}$-retrieval model that can
non-trivially differentiate the positive from negative examples. (R2) We also
assume a moderate stability with bounded variance, which implicitly assumes a
moderate generalization of the retrieval model based on the variance-
generalization link (Lam, 2016; Gotoh et al., 2018; Namkoong & Duchi, 2017).
This is essential for the analysis as the knowledge base distribution is non-
identical to the calibration/test distribution. (R3) We define
$V_{\text{rag}}$-retrieval model using a standard contrastive loss in (Wang et
al., 2023b; Rubin et al., 2021), but it can be adapted for other contrastive
loss such as triplet loss (Hermans et al., 2017), by altering the logarithmic
factor in the $V_{\text{rag}}$ formula. We defer the proof sketches as well as
the detailed proofs and remarks to Appendix F.

With a $V_{\text{rag}}$-retrieval model, we show that C-RAG can retrieve a
high number of positive examples as in-context demonstrations as follows.

######  Proposition 3 (lower bound of the number of retrieved positive
examples).

Consider the $V_{\text{rag}}$-retrieval model in Definition 1 and RAG
generation protocol in Section 3.2. Let $r^{(c)}_{\text{cal}}$ and
$r^{(c)}_{\text{ext}}$ be the portion of data with groundtruth output
$c\in{\mathcal{Y}}$ in the calibration data distribution and external
knowledge data distribution, respectively. We have:

$\displaystyle\mathbb{E}\left[N_{\text{pos}}\right]\geq$
$\displaystyle\dfrac{9}{10}N_{\text{rag}}\big{(}1-\sum_{c\in{\mathcal{Y}}}r^{(c)}_{\text{cal}}\left(N_{\text{ext}}-r^{(c)}_{\text{ext}}N_{\text{ext}}+{\sqrt{2\ln{10}}}\right)V_{\text{rag}}^{0.5\left(r^{(c)}_{\text{ext}}N_{\text{ext}}-{\sqrt{2\ln{10}}}\right)}\big{)}$
(4)

where $N_{\text{pos}}$ is the number of retrieved positive examples,
$N_{\text{rag}}$ is the total number of retrieved examples, and
$N_{\text{ext}}$ is the number of examples in the external knowledge base.

######  Remarks.

Proposition 3 offers a guarantee on the minimum number of positive examples
retrieved by the $V_{\text{rag}}$-retrieval model. (R1) The ratio of the
retrieved examples that are positive increases at an exponential rate with
respect to $N_{\text{ext}}$, which suggests that expanding the external
knowledge base could enhance the retrieval quality and therefore benefit in-
context learning of LLMs, as shown in (Min et al., 2022; Wang et al., 2022a).
For a sufficiently large $N_{\text{ext}}$ (a common scenario in practice), the
lower bound approximately scales with $0.9N_{\text{rag}}$. (R2) If the
knowledge base is highly long-tailed such that samples of certain reference
texts are rare (i.e., small $r_{\text{ext}}^{(c)}$), we require a larger
sample size of knowledge base $N_{\text{ext}}$ to compensate for the long-tail
distribution and achieve comparable retrieval quality. (R3) A low-variance
retrieval model is expected to generalize well to test distribution and
increase retrieval quality. The above guarantee we provide for
$\mathbb{E}[N_{\text{pos}}]$ in relation to $V_{\text{rag}}$ is a rigorous
demonstration of this.

###  4.3 RAG achieves provably lower conformal generation risk than a single
LLM without retrieval

Besides retrieval quality, the generation risk in RAG models is also affected
by LLM quality, and to measure transformer quality, we define a
$(d^{+},\Phi_{M})$-transformer as follows.

######  Definition 2 ($(d^{+},\Phi_{M})$-transformer).

We assume that each in-context example
$(X_{i},Y_{i})~{}(i\in[N_{\text{rag}}+1])$ is encoded with a single token
${\bm{q}}_{i}$. Let ${\bm{q}}$ be the retrieval-augmented input, consisting of
$N_{\text{rag}}$ retrieved in-context examples and $1$ query example. We
define a random variable to represent the negative prediction margin:
$M=\max_{c\neq
g({\bm{q}}_{N_{\text{rag}}+1})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N_{\text{rag}}+1})}({\bm{q}})$,
where $O({\bm{q}})$ is the output probability vector without RAG. Let
$\Phi_{M}(\cdot)$ be the CDF of random variable $M$. We define a
$(d^{+},\Phi_{M})$-transformer as a single-layer self-attention transformer
with (a) non-trivial self-attention layer with
$\sigma\left((W_{K}W_{E}{\bm{q}}_{i})^{T}(W_{Q}W_{E}{\bm{q}}_{j})\right)\geq
d^{+}>0$ for semantically identical examples with
$g({\bm{q}}_{i})=g({\bm{q}}_{j})$; and (b) the prediction utility that is
better than random: $\int_{-1}^{1}\Phi_{M}(v)dv>1$.

######  Remarks.

(R1) $d^{+}$ measures the minimal attention scores for positive pairs and
reflects the effectiveness of the transformer’s embedding, key, and query
matrices. Since we always have $d^{+}\geq 0$ due to the Softmax activation,
the condition $d^{+}>0$ only assumes a non-trivial self-attention layer. (R2)
The integral $\int_{-1}^{1}\Phi_{M}(v)dv$ measures the quality of the
embedding, value, and projection matrices. Note that a random prediction
margin $M_{\text{rand}}$ over a uniform distribution $[-1,1]$ results in
$\int_{-1}^{1}\Phi_{M_{\text{rand}}}(v)dv=1$. Thus,
$\int_{-1}^{1}\Phi_{M}(v)dv>1=\int_{-1}^{1}\Phi_{M_{\text{rand}}}(v)dv$ only
indicates better-than-random prediction utility.

Next, we prove that RAG in C-RAG achieves a lower conformal generation risk
than a single LLM without retrieval with high probability.

######  Theorem 1 (RAG reduces the conformal generation risk).

Consider the setup in Section 4.1 as well as the $V_{\text{rag}}$-retrieval
model in Definition 1 and $(d^{+},\Phi_{M})$-transformer in Definition 2. Let
$r^{(c)}_{\text{cal}}$ and $r^{(c)}_{\text{ext}}$ be as defined in Proposition
3. We show that the conformal generation risk of RAG
$\hat{\alpha}_{\text{rag}}$ is smaller than that of a single LLM
$\hat{\alpha}$ with high probability:

$\displaystyle{\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]\geq
1-p_{\text{t}}-p_{\text{r}},\quad\text{where}$ (5) $\displaystyle
p_{\text{t}}=\exp\\{-2N_{\text{cal}}[\underbrace{\Phi_{M}(\dfrac{1}{2}{\overbrace{d^{+}(\int_{-1}^{1}\Phi_{M}(v)dv-1)}^{\text{quality
of transformers}}}N_{\text{rag}})-\Phi_{M}(0)}_{\text{improvement of
generation quality with RAG}}]^{2}\\}$ $\displaystyle
p_{\text{r}}=\dfrac{25}{N_{\text{rag}}}(4-9\underbrace{\sum_{c=1}^{C}r^{(c)}_{\text{cal}}(1.5N_{\text{ext}}-r^{(c)}_{\text{ext}}N_{\text{ext}})V_{\text{rag}}^{0.25r^{(c)}_{\text{ext}}N_{\text{ext}}}}_{\text{number
of retrieved negative examples}})^{-2}$

provided that $\footnotesize{N_{\text{ext}}>{2\sqrt{2\ln
10}}/{\min_{c}r_{\text{ext}}^{(c)}}}$, $N_{\text{rag}}>{2}/{d^{+}}$ and
$\footnotesize{N_{\text{ext}}V_{\text{rag}}^{0.25\min_{c}r_{\text{ext}}^{(c)}N_{\text{ext}}}<{4}/{9}}$.
$p_{t},p_{r}$ are the uncertainty induced by the quality of transformer and
retrieval model.

######  Remarks.

(R1) The probability of reduced risk with RAG
(${\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]$) increases
with both $N_{\text{cal}}$, which improves risk approximation via enhanced
calibration, and $N_{\text{rag}}$ and $N_{\text{ext}}$, which expand the scope
of retrieved knowledge. (R2) The reduced risk probability also increases with
the transformer’s quality induced by attention scores and prediction
capability. (R3) A low-variance retrieval model (small $V_{\text{rag}}$)
enhances generalization and reduces retrieval model uncertainty $p_{r}$. (R4)
For certification simplicity, we define positive pairs as semantically
identical examples, but this can be expanded to pairs similar in the embedding
space for boosting attention scores, in-context learning, and generation
quality. (R5) These result can readily extend to various conformal risks such
as (Angelopoulos et al., 2022). (R6) For sufficiently large sample size
$N_{\text{ext}}$ in the external knowledge base, we further have
${\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]\geq
1-p_{t}-{25}/{16N_{\text{rag}}}$ (Corollary 1 in Appendix G). In contrast to
Theorem 1, the bound has no dependency on the external knowledge distribution
$r_{\text{ext}}^{(c)}$ and calibration distribution $r_{\text{cal}}^{(c)}$.

##  5 C-RAG under distribution shifts

Here, we present a valid distribution-drift conformal generation risk and
prove the benefit of RAG compared to vanilla LLM under test-time distribution
shifts.

###  5.1 Analysis setup

Conformal risk guarantees often assume that calibration and testing samples
come from the same distribution (Bates et al., 2021; Angelopoulos et al.,
2022, 2021). Next, building on Section 4.1, we extend these guarantees to
distribution shifts between calibration and testing.

###  5.2 Conformal generation risk under distribution shifts

Under test-time distribution shifts, the certification guarantees of prior
work (Angelopoulos et al., 2022; Farinhas et al., 2023a) are limited to the
monotonic risk functions and to distribution shifts caused by changes in
sample weights. Here, we provide generation risk certification for any bounded
risk function and any distribution shift, which is as follows.

######  Theorem 2 (Conformal generation risk under distribution shifts).

Suppose that the test instance $(X_{\text{test}},Y_{\text{test}})$ is sampled
from a shifted distribution ${\mathcal{Q}}$ with bounded Hellinger distance
from the calibration distribution ${\mathcal{D}}$:
$H({\mathcal{D}},{\mathcal{Q}})\leq\rho$. Let
$\hat{R}=\sum_{i=1}^{N_{\text{cal}}}R(Z_{i})/N_{\text{cal}}$ be the empirical
risk on calibration samples $Z_{i}~{}(i\in\\{1,...,N_{\text{cal}}\\})$ and
$\hat{V}={1}/{N_{\text{cal}}(N_{\text{cal}}-1)}\sum_{1\leq i<j\leq
N_{\text{cal}}}(R(Z_{i})-R(Z_{j}))^{2}$ be the unbiased estimator of the risk
variance on the calibration set. Then we have the following guarantee of
conformal generation risk on the shifted distribution ${\mathcal{Q}}$:

$\displaystyle{\mathbb{P}}\left[R(T_{\hat{{\bm{\lambda}}}};X_{\text{test}},Y_{\text{test}})\leq\hat{\alpha}(\rho)\right]\geq
1-\delta,\quad\text{where}\quad\hat{\alpha}(\rho):=\min\left\\{h^{-1}\left(\dfrac{8/\delta}{N_{\text{cal}}};\overline{\hat{R}_{\rho}}\right),\Phi^{-1}_{\text{bin}}\left(\dfrac{\delta}{8e};N_{\text{cal}},\overline{\hat{R}_{\rho}}\right)\right\\}$
(6)

where $h^{-1}(\cdot;\cdot)$ is the partial inverse function as defined in
Proposition 1 and $\overline{\hat{R}_{\rho}}$ is formulated as:

$\displaystyle\overline{\hat{R}_{\rho}}=\underbrace{\hat{R}+\rho^{2}(2-\rho^{2})(1-\hat{R})}_{\text{empirical
mean scaled by
}\rho}+\underbrace{2\rho(1-\rho^{2})\sqrt{2-\rho^{2}}\sqrt{\hat{V}}}_{\text{estimated
variance scaled by
}\rho}+\underbrace{(1-\rho^{2})\left(\dfrac{1-\rho^{2}}{\sqrt{2N_{\text{cal}}}}+\dfrac{2\sqrt{2}\rho\sqrt{2-\rho^{2}}}{\sqrt{N_{\text{cal}}-1}}\right)\sqrt{\ln(4/\delta)}+\sqrt{\dfrac{\ln{(8/\delta)}}{2N_{\text{cal}}}}}_{\text{finite-
sample error}}$

where the radius $\rho$ satisfies the following: $\rho^{2}\leq
1-\big{[}1+\big{(}\nicefrac{{\hat{R}-1+\sqrt{\nicefrac{{\ln(4/\delta)}}{{2N_{\text{cal}}}}}\big{)}^{2}}}{{\big{(}\sqrt{\hat{V}}+\sqrt{\nicefrac{{2\ln(2/\delta)}}{{(N_{\text{cal}}-1)}}}\big{)}^{2}}}\big{]}^{-2}$.

######  Remarks.

Theorem 2 offers a distribution-drift conformal generation risk
$\hat{\alpha}(\rho)$, under the distribution shift with radius $\rho$. (R1) We
adopt the Hellinger distance for measuring distribution distances due to its
f-divergence properties and direct applicability to total variation distance
between ${\mathcal{D}}$ and ${\mathcal{Q}}$ ((Steerneman, 1983), Equation 1).
(R2) For conformal guarantees under distribution shifts, we derive an
empirical risk upper bound considering worst-case shifts in Theorem 2, which
is efficiently calculable with empirical statistics on calibration
distribution ${\mathcal{D}}$. (R3) We recover the empirical mean $\hat{R}$
from $\overline{\hat{R}_{\rho}}$ when $\rho\rightarrow 0$ and
$N_{\text{cal}}\rightarrow\infty$ in Theorem 2.

###  5.3 RAG achieves provably lower conformal generation risk than a single
LLM under distribution shifts

Next, we prove that RAG mitigates conformal generation risk better than a
single LLM under distribution shifts.111Additionally, we examine retrieval
quality and prove a lower bound of retrieved positive examples under test-time
distribution shifts. We leave the analysis to Appendix H for interested
readers.

######  Theorem 3 (RAG reduces conformal generation risk even under
distribution shifts).

Suppose that the shifted test distribution ${\mathcal{Q}}$ is within bounded
Hellinger distance $\rho>0$ to the calibration distribution ${\mathcal{D}}$.
Consider the same setup and assumptions as Theorem 1. Consider also a
$V_{\text{rag}}$-retrieval model in Definition 1 and
$(d^{+},\Phi_{M})$-transformer in Definition 2. Under the condition that
$N_{\text{ext}}>{2\sqrt{2\ln 10}}/{r_{\text{ext}}^{m}}$,
$N_{\text{ext}}V_{\text{rag}}(\rho)^{0.25r_{\text{ext}}^{m}N_{\text{ext}}}<{8}/{17}$,
and $N_{\text{rag}}>{2}/{d^{+}}$ , we have:

$\displaystyle{\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}(\rho)<\alpha(\rho)\right]\geq
1-p_{t}-p_{r}(\rho),\quad\text{where}\quad
p_{r}(\rho)=\dfrac{100}{N_{\text{rag}}}\left(8-17N_{\text{ext}}V_{\text{rag}}(\rho)^{0.25\left(\min_{c}r^{(c)}_{\text{ext}}N_{\text{ext}}\right)}\right)^{-2},$
(7)

where $p_{\text{t}}$ is the uncertainty induced by the transformer quality as
Equation 5 and $p_{r}(\rho)$ is the uncertainty induced by the retrieval
model. Moreover, $V_{\text{rag}}(\rho)=m(\rho)V_{\text{rag}}$ quantifies the
quality of retrieval models under distance $\rho$, where

$\displaystyle\vspace{-1em}V_{\text{rag}}(\rho):=m(\rho)V_{\text{rag}},\quad\text{where}\quad
m(\rho)=\underbrace{\left(\dfrac{\sqrt{-6\rho^{4}+12\rho^{2}+1}-4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}}{1-16\rho^{2}+8\rho^{4}}\right)^{-2}}_{\text{retrieval
model quality decay factor under distribution shifts}}.$

######  Remarks.

Our result rigorously characterizes the effect of distribution shift on the
reduced risk guarantee of RAG. (R1) Compared to Theorem 1, only the
uncertainty of retrieval model $p_{r}(\rho)$ is affected by the distribution
shift $\rho$. This affect is reflected on the the retrieval quality
$V_{\text{rag}}(\rho)$. In particular, a large distance radius $\rho$ will
downgrade the retrieval quality $V_{\text{rag}}(\rho)$ and thus lead to a
higher uncertainty $p_{r}(\rho)$. However, the influence of $\rho$ on
$p_{r}(\rho)$ can be reduced by $N_{\text{rag}}$ inverse proportionally and by
$N_{\text{ext}}$ exponentially, demonstrating the robustness of RAG with more
retrieval knowledge. (R2) Since $V_{\text{rag}}(\rho)$ is proportional to
model variance $V_{\text{rag}}$, a low-variance retrieval model demonstrates
better robustness against distribution drifts, aligning with existing
empirical observations (Lam, 2016; Gotoh et al., 2018; Namkoong & Duchi,
2017), which evaluate the generalization ability of low-variance retrieval
models under distribution shifts. (R3) Compared to Theorem 1, Theorem 3 has no
dependence on varying label portions $r^{(c)}_{\text{cal}}$ during
distribution shifts, as long as the size of external knowledge base
$N_{\text{ext}}$ is moderately large, a condition often met in practice with
large knowledge bases.

AESLC

Generation risk

CommonGen

DART

E2E

Generation risk

Generation risk

# Retrieved examples $N_{\text{rag}}$

Generation risk

# Retrieved examples $N_{\text{rag}}$

# Retrieved examples $N_{\text{rag}}$

# Retrieved examples $N_{\text{rag}}$

Figure 3: Conformal generation risk $\hat{\alpha}_{\text{rag}}$ (black up-
pointing triangles) and empirical risk (gray dots) based on retrieval models
OpenAI/ada, Biencoder-SFT, BM25 and BAAI/bge (shown in row 1-4, respectively)
given different $N_{\text{rag}}$ ($\lambda_{g}=1,\lambda_{s}=1.0$). We observe
that our conformal generation risk (Proposition 1) is valid and tight; larger
$N_{\text{rag}}$ reduces conformal generation risk $\hat{\alpha}_{\text{rag}}$
(empirically validating Theorem 1).

AESLC

# Retrieved examples $N_{\text{rag}}$

Conformal Risk $\hat{\alpha}_{\text{rag}}$

CommonGen

# Retrieved examples $N_{\text{rag}}$

DART

# Retrieved examples $N_{\text{rag}}$

E2E

# Retrieved examples $N_{\text{rag}}$

Figure 4: Conformal generation risk $\hat{\alpha}_{\text{rag}}$ with different
$N_{\text{rag}}$ using different retrieval models
($\lambda_{g}=1,\lambda_{s}=1.0$). We observe that large $N_{\text{rag}}$
effectively reduces $\hat{\alpha}_{\text{rag}}$ for different models; the
trained Biencoder-SFT usually leads to the lowest conformal generation risk.

AESLC

Generation risk

CommonGen

DART

E2E

Hellinger Distance $\rho$

Generation risk

Hellinger Distance $\rho$

Hellinger Distance $\rho$

Hellinger Distance $\rho$

Figure 5:  Conformal generation risk $\hat{\alpha}_{\text{rag}}(\rho)$ (black
up-pointing triangles) and empirical risks (gray dots) based on retrieval
model OpenAI/ada and Biencoder-SFT (shown in row 1-2, respectively) under
distribution shifts ($N_{\text{rag}}=15,\lambda_{g}=1,\lambda_{s}=1.0$). We
observe that our distribution-drift conformal generation risk (Theorem 2) is
empirically valid and tight.

AESLC

CommonGen

Figure 6: Conformal generation risk $\hat{\alpha}_{\text{rag}}$ and empirical
risks with different $\lambda_{g}$ and $N_{\text{rag}}$ for OpenAI/ada.

##  6 Evaluation

We evaluate C-RAG on four datasets using different retrieval models. We find
that (1) our conformal generation risks in Proposition 1 is empirically sound
and tight in Section 6.2, (2) RAG reduces the conformal generation risks for
different retrieval models, which empirically validates Theorem 1 in Section
6.2, (3) the conformal generation risk under distribution shifts in Theorem 2
is empirically sound and tight for varying distances in Section 6.3, (4)
multi-dimensional RAG configurations maintain sound and tight conformal
generation risks in Section 6.4, and (5) C-RAG computes valid configurations
with empirical risks always below the desired risk level in Section 6.5.

Codes are publicly available at https://github.com/kangmintong/C-RAG.

###  6.1 Evaluation setup

#### Datasets & knowledge base

We evaluate C-RAG on four widely used NLP datasets, including AESLC (Zhang &
Tetreault, 2019), CommonGen (Lin et al., 2019), DART (Nan et al., 2020), and
E2E (Novikova et al., 2017). Following (Wang et al., 2023b; Cheng et al.,
2023), we construct the knowledge base as a collection of 30 public datasets
from 9 distinct categories with over 6 million documents.

#### Retrieval models

We consider four retrieval models: (1) BM25 (Robertson et al., 2009) with
token-level matching scores, (2) BAAI/bge (Zhang et al., 2023a) as SOTA
embedding model in MTEB benchmark (Muennighoff et al., 2022), (3) OpenAI/ada
as SOTA close source text embedding model, and (4) Biencoder-SFT (Wang et al.,
2023b) as a biencoder retriever trained with in-domain data samples.

#### RAG Generation protocol

We use our generation protocol (Algorithm 1 in Section C.1) controlled by the
number of retrieved examples $N_{\text{rag}}$, generation set size
$\lambda_{g}$, and diversity threshold $\lambda_{s}$. We use Llama-7b for
inference and perform conformal calibration on validation sets with
uncertainty $\delta=0.1$. We use $1-\text{ROUGE-L}$ as the risk function. See
Section J.1 for more details of evaluation setup.

AESLC

CommonGen

Figure 7: Valid configurations $\hat{\Lambda}_{\alpha}$ given a desired risk
level $\alpha$ and the empirical risks with different $\lambda_{g}$ and
$N_{\text{rag}}$ for OpenAI/ada.

###  6.2 Evaluation of conformal generation risks

#### Soundness and tightness of conformal generation risks

To achieve generation risk guarantee in Equation 1, C-RAG computes the
conformal generation risk using Proposition 1. We evaluate the conformal
generation risks of RAG models $\hat{\alpha}_{\text{rag}}$ under different
numbers of retrieved examples $N_{\text{rag}}$ by calibration statistics on
the validation set. To validate the soundness and tightness of the conformal
generation risk guarantee, we evaluate the empirical risks on randomly sampled
test instances. The sampling protocol is detailed in Algorithm 3 in Section
J.2. We provide the results using OpenAI/ada, Biencoder-SFT, BM25 and BAAI/bge
retrieval models in Figure 3. The results show that (1) the conformal
generation risks $\hat{\alpha}_{\text{rag}}$ upper bound the empirical risks
of the sampled test instances, (2) for some test instances, the empirical
risks nearly reach the conformal generation risk, demonstrating the soundness
and tightness of our generation risk guarantees, (3) the conformal generation
risk decreases as the number of retrieved examples $N_{\text{rag}}$ increases,
which shows the effectiveness of RAG models and aligns with our theoretical
analysis in Theorem 1.

#### Comparisons of different SOTA retrieval models

We compare the conformal generation risks for token-level BM25 scores, and
SOTA embedding models BAAI/bge, OpenAI/ada, and Biencoder-SFT. The results in
Figure 4 show that RAG achieves lower conformal generation risks than LLM
without retrieval (i.e., $N_{\text{rag}}=0$) for different retrieval models.
Biencoder-SFT, trained with in-domain data samples, leads to lower conformal
generation risk in general compared with other retrieval models. OpenAI/ada,
which is known of high quality and trained on large open corpus, also
demonstrates low conformal generation risks.

###  6.3 Conformal generation risk under distribution shifts

#### Soundness and tightness of conformal generation risk under distribution
shifts

In practice, user input text may deviate from the calibration distribution. In
Theorem 2, we provide the first conformal generation risk under distribution
shifts for general bounded risk functions. We evaluate the conformal
generation risk $\hat{\alpha}(\rho)$ in Equation 6. To empirically verify the
soundness, we create test sets with covariate shifts by varying sample
weights. The Hellinger distance is computed using original and shifted sample
weights, with details in Algorithm 4 in Section J.3. We compare the conformal
generation risk and empirical risks with $N_{\text{rag}}=15$ using OpenAI/ada
and Biencoder-SFT in Figure 5, and using BM25, BAAI/bge in Figures 8 and 9 in
Section J.3. The results show that (1) our conformal generation risks under
distribution shifts are sound and tight across various models, and (2)
conformal generation risks increase linearly with Hellinger distance $\rho$,
remaining non-trivial up to $\rho=0.2$.

#### Comparison of SOTA retrieval models under distribution shifts

We compare conformal generation risks for different retrieval models under
distribution shifts in Figure 10 in Section J.3. All models show a linear rise
in risk with increasing Hellinger distance, with BiEncoder-SFT and OpenAI/ada
showing lower risks at varying distances.

###  6.4 C-RAG with multi-dimensional RAG configurations

So far, we demonstrate the effectiveness of retrieved in-context examples
quantified by $N_{\text{rag}}$. To further improve the conformal generation
risk, we can adjust the RAG configurations, such as the number of generations
$\lambda_{g}$ and the diversity-controlling similarity threshold
$\lambda_{s}$. We follow RAG generation protocol in Algorithm 1 and define the
risk function as the minimal risk among $\lambda_{g}$ candidate generations.
Our tests on AESLC, CommonGen, DART, and E2E datasets (see Figure 6 and Figure
11 in Section J.4) show that the multi-dimensional RAG configurations maintain
sound and tight conformal generation risks. Notably, a higher $N_{\text{rag}}$
reduces generation risks more effectively than adjusting $\lambda_{g}$.

###  6.5 Valid configurations given desired risk levels

In risk guarantee (2) outlined in Section 3.3, given a desired risk level
$\alpha$, C-RAG computes a valid RAG configuration set
$\hat{\Lambda}_{\alpha}$, such that configurations within this set will lead
to generation risks below $\alpha$. We apply the Bonferroni correction in
Proposition 2 for rigorous family-wise error rate control and assess empirical
risks on random test sets with the identified valid configurations. We provide
the results on AESLC and CommenGen in Figure 7 and results on DART and ECE in
Figure 11 in Section J.5. These results validate our certification, as the
empirical risks of generated configurations $\hat{\Lambda}_{\alpha}$ are
consistently below the given conformal generation risk $\alpha$. The results
also show that a high number of retrieved examples $N_{\text{rag}}$ and a
larger generation set size $\lambda_{g}$ contribute to reducing conformal
generation risk. The impact of the diversity threshold $\lambda_{s}$ is
explored in Section J.5.

##  7 Conclusion

In this paper, we propose C-RAG to provide conformal generation risk
guarantees for RAG models. C-RAG certifies (1) a conformal generation risk for
a given RAG configuration, and (2) a valid configuration set for a given
desired risk level. We theoretically show that RAG reduces conformal
generation risks of a single LLM. We empirically validate the soundness and
tightness of our risk guarantees.

#### Acknolwdgement

This work is partially supported by the National Science Foundation under
grant No. 1910100, No. 2046726, No. 2229876, DARPA GARD, the National
Aeronautics and Space Administration (NASA) under grant no. 80NSSC20M0229, the
Alfred P. Sloan Fellowship, the Amazon research award, the eBay research
award, and CAIS.

## References

  * Agrawal & Jia (2017) Agrawal, S. and Jia, R.  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Angelopoulos et al. (2021) Angelopoulos, A. N., Bates, S., Candès, E. J., Jordan, M. I., and Lei, L.  Learn then test: Calibrating predictive algorithms to achieve risk control.  _arXiv preprint arXiv:2110.01052_ , 2021.
  * Angelopoulos et al. (2022) Angelopoulos, A. N., Bates, S., Fisch, A., Lei, L., and Schuster, T.  Conformal risk control.  _arXiv preprint arXiv:2208.02814_ , 2022.
  * Basu et al. (2023) Basu, S., Rawat, A. S., and Zaheer, M.  A statistical perspective on retrieval-based models.  In _International Conference on Machine Learning_ , pp. 1852–1886. PMLR, 2023.
  * Bates et al. (2021) Bates, S., Angelopoulos, A., Lei, L., Malik, J., and Jordan, M.  Distribution-free, risk-controlling prediction sets.  _Journal of the ACM (JACM)_ , 68(6):1–34, 2021.
  * Bentkus (2004) Bentkus, V.  On hoeffding’s inequalities.  2004\.
  * Brown et al. (2020) Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D.  Language models are few-shot learners, 2020.
  * Cheng et al. (2023) Cheng, D., Huang, S., Bi, J., Zhan, Y., Liu, J., Wang, Y., Sun, H., Wei, F., Deng, D., and Zhang, Q.  Uprise: Universal prompt retrieval for improving zero-shot evaluation.  _arXiv preprint arXiv:2303.08518_ , 2023.
  * Farinhas et al. (2023a) Farinhas, A., Zerva, C., Ulmer, D., and Martins, A. F.  Non-exchangeable conformal risk control.  _arXiv preprint arXiv:2310.01262_ , 2023a.
  * Farinhas et al. (2023b) Farinhas, A., Zerva, C., Ulmer, D., and Martins, A. F. T.  Non-exchangeable conformal risk control, 2023b.
  * Gatt & Krahmer (2018) Gatt, A. and Krahmer, E.  Survey of the state of the art in natural language generation: Core tasks, applications and evaluation.  _Journal of Artificial Intelligence Research_ , 61:65–170, 2018.
  * Gotoh et al. (2018) Gotoh, J.-y., Kim, M. J., and Lim, A. E.  Robust empirical optimization is almost the same as mean–variance optimization.  _Operations research letters_ , 46(4):448–452, 2018.
  * Gou et al. (2023) Gou, Z., Shao, Z., Gong, Y., Shen, Y., Yang, Y., Duan, N., and Chen, W.  Critic: Large language models can self-correct with tool-interactive critiquing.  _arXiv preprint arXiv:2305.11738_ , 2023.
  * Han et al. (2023) Han, C., Wang, Z., Zhao, H., and Ji, H.  In-context learning of large language models explained as kernel regression.  _arXiv preprint arXiv:2305.12766_ , 2023.
  * Hermans et al. (2017) Hermans, A., Beyer, L., and Leibe, B.  In defense of the triplet loss for person re-identification.  _arXiv preprint arXiv:1703.07737_ , 2017.
  * Hoeffding (1994) Hoeffding, W.  Probability inequalities for sums of bounded random variables.  _The collected works of Wassily Hoeffding_ , pp. 409–426, 1994.
  * Holm (1979) Holm, S.  A simple sequentially rejective multiple test procedure.  _Scandinavian journal of statistics_ , pp. 65–70, 1979.
  * Huang et al. (2023) Huang, J., Ping, W., Xu, P., Shoeybi, M., Chang, K. C.-C., and Catanzaro, B.  Raven: In-context learning with retrieval augmented encoder-decoder language models.  _arXiv preprint arXiv:2308.07922_ , 2023.
  * Karpukhin et al. (2020) Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t.  Dense passage retrieval for open-domain question answering.  _arXiv preprint arXiv:2004.04906_ , 2020.
  * Kishore et al. (2023) Kishore, V., Wan, C., Lovelace, J., Artzi, Y., and Weinberger, K. Q.  Incdsi: incrementally updatable document retrieval.  In _International Conference on Machine Learning_ , pp. 17122–17134. PMLR, 2023.
  * Lam (2016) Lam, H.  Robust sensitivity analysis for stochastic systems.  _Mathematics of Operations Research_ , 41(4):1248–1275, 2016.
  * Lei et al. (2013) Lei, J., Robins, J., and Wasserman, L.  Distribution-free prediction sets.  _Journal of the American Statistical Association_ , 108(501):278–287, 2013.
  * Lewis et al. (2020) Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.-t., Rocktäschel, T., et al.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _Advances in Neural Information Processing Systems_ , 33:9459–9474, 2020.
  * Liang et al. (2022) Liang, P., Bommasani, R., Lee, T., Tsipras, D., Soylu, D., Yasunaga, M., Zhang, Y., Narayanan, D., Wu, Y., Kumar, A., et al.  Holistic evaluation of language models.  _arXiv preprint arXiv:2211.09110_ , 2022.
  * Lin et al. (2019) Lin, B. Y., Zhou, W., Shen, M., Zhou, P., Bhagavatula, C., Choi, Y., and Ren, X.  Commongen: A constrained text generation challenge for generative commonsense reasoning.  _arXiv preprint arXiv:1911.03705_ , 2019.
  * Lin (2004) Lin, C.-Y.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pp. 74–81, 2004.
  * Liu et al. (2023) Liu, Y., Yao, Y., Ton, J.-F., Zhang, X., Guo, R., Cheng, H., Klochkov, Y., Taufiq, M. F., and Li, H.  Trustworthy llms: a survey and guideline for evaluating large language models’ alignment, 2023.
  * Luo et al. (2023) Luo, Z., Xu, C., Zhao, P., Geng, X., Tao, C., Ma, J., Lin, Q., and Jiang, D.  Augmented large language models with parametric knowledge guiding.  _arXiv preprint arXiv:2305.04757_ , 2023.
  * Maurer & Pontil (2009) Maurer, A. and Pontil, M.  Empirical bernstein bounds and sample variance penalization.  _arXiv preprint arXiv:0907.3740_ , 2009.
  * Min et al. (2022) Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L.  Rethinking the role of demonstrations: What makes in-context learning work?  _arXiv preprint arXiv:2202.12837_ , 2022.
  * Muennighoff et al. (2022) Muennighoff, N., Tazi, N., Magne, L., and Reimers, N.  Mteb: Massive text embedding benchmark.  _arXiv preprint arXiv:2210.07316_ , 2022.
  * Namkoong & Duchi (2017) Namkoong, H. and Duchi, J. C.  Variance-based regularization with convex objectives.  _Advances in neural information processing systems_ , 30, 2017.
  * Nan et al. (2020) Nan, L., Radev, D., Zhang, R., Rau, A., Sivaprasad, A., Hsieh, C., Tang, X., Vyas, A., Verma, N., Krishna, P., et al.  Dart: Open-domain structured data record to text generation.  _arXiv preprint arXiv:2007.02871_ , 2020.
  * Novikova et al. (2017) Novikova, J., Dušek, O., and Rieser, V.  The e2e dataset: New challenges for end-to-end generation.  _arXiv preprint arXiv:1706.09254_ , 2017.
  * OpenAI et al. (2023) OpenAI, :, Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., Avila, R., Babuschkin, I., Balaji, S., Balcom, V., Baltescu, P., Bao, H., Bavarian, M., Belgum, J., Bello, I., Berdine, J., Bernadett-Shapiro, G., Berner, C., Bogdonoff, L., Boiko, O., Boyd, M., Brakman, A.-L., Brockman, G., Brooks, T., Brundage, M., Button, K., Cai, T., Campbell, R., Cann, A., Carey, B., Carlson, C., Carmichael, R., Chan, B., Chang, C., Chantzis, F., Chen, D., Chen, S., Chen, R., Chen, J., Chen, M., Chess, B., Cho, C., Chu, C., Chung, H. W., Cummings, D., Currier, J., Dai, Y., Decareaux, C., Degry, T., Deutsch, N., Deville, D., Dhar, A., Dohan, D., Dowling, S., Dunning, S., Ecoffet, A., Eleti, A., Eloundou, T., Farhi, D., Fedus, L., Felix, N., Fishman, S. P., Forte, J., Fulford, I., Gao, L., Georges, E., Gibson, C., Goel, V., Gogineni, T., Goh, G., Gontijo-Lopes, R., Gordon, J., Grafstein, M., Gray, S., Greene, R., Gross, J., Gu, S. S., Guo, Y., Hallacy, C., Han, J., Harris, J., He, Y., Heaton, M., Heidecke, J., Hesse, C., Hickey, A., Hickey, W., Hoeschele, P., Houghton, B., Hsu, K., Hu, S., Hu, X., Huizinga, J., Jain, S., Jain, S., Jang, J., Jiang, A., Jiang, R., Jin, H., Jin, D., Jomoto, S., Jonn, B., Jun, H., Kaftan, T., Łukasz Kaiser, Kamali, A., Kanitscheider, I., Keskar, N. S., Khan, T., Kilpatrick, L., Kim, J. W., Kim, C., Kim, Y., Kirchner, H., Kiros, J., Knight, M., Kokotajlo, D., Łukasz Kondraciuk, Kondrich, A., Konstantinidis, A., Kosic, K., Krueger, G., Kuo, V., Lampe, M., Lan, I., Lee, T., Leike, J., Leung, J., Levy, D., Li, C. M., Lim, R., Lin, M., Lin, S., Litwin, M., Lopez, T., Lowe, R., Lue, P., Makanju, A., Malfacini, K., Manning, S., Markov, T., Markovski, Y., Martin, B., Mayer, K., Mayne, A., McGrew, B., McKinney, S. M., McLeavey, C., McMillan, P., McNeil, J., Medina, D., Mehta, A., Menick, J., Metz, L., Mishchenko, A., Mishkin, P., Monaco, V., Morikawa, E., Mossing, D., Mu, T., Murati, M., Murk, O., Mély, D., Nair, A., Nakano, R., Nayak, R., Neelakantan, A., Ngo, R., Noh, H., Ouyang, L., O’Keefe, C., Pachocki, J., Paino, A., Palermo, J., Pantuliano, A., Parascandolo, G., Parish, J., Parparita, E., Passos, A., Pavlov, M., Peng, A., Perelman, A., de Avila Belbute Peres, F., Petrov, M., de Oliveira Pinto, H. P., Michael, Pokorny, Pokrass, M., Pong, V., Powell, T., Power, A., Power, B., Proehl, E., Puri, R., Radford, A., Rae, J., Ramesh, A., Raymond, C., Real, F., Rimbach, K., Ross, C., Rotsted, B., Roussez, H., Ryder, N., Saltarelli, M., Sanders, T., Santurkar, S., Sastry, G., Schmidt, H., Schnurr, D., Schulman, J., Selsam, D., Sheppard, K., Sherbakov, T., Shieh, J., Shoker, S., Shyam, P., Sidor, S., Sigler, E., Simens, M., Sitkin, J., Slama, K., Sohl, I., Sokolowsky, B., Song, Y., Staudacher, N., Such, F. P., Summers, N., Sutskever, I., Tang, J., Tezak, N., Thompson, M., Tillet, P., Tootoonchian, A., Tseng, E., Tuggle, P., Turley, N., Tworek, J., Uribe, J. F. C., Vallone, A., Vijayvergiya, A., Voss, C., Wainwright, C., Wang, J. J., Wang, A., Wang, B., Ward, J., Wei, J., Weinmann, C., Welihinda, A., Welinder, P., Weng, J., Weng, L., Wiethoff, M., Willner, D., Winter, C., Wolrich, S., Wong, H., Workman, L., Wu, S., Wu, J., Wu, M., Xiao, K., Xu, T., Yoo, S., Yu, K., Yuan, Q., Zaremba, W., Zellers, R., Zhang, C., Zhang, M., Zhao, S., Zheng, T., Zhuang, J., Zhuk, W., and Zoph, B.  Gpt-4 technical report, 2023.
  * Quach et al. (2023) Quach, V., Fisch, A., Schuster, T., Yala, A., Sohn, J. H., Jaakkola, T. S., and Barzilay, R.  Conformal language modeling.  _arXiv preprint arXiv:2306.10193_ , 2023.
  * Robertson et al. (2009) Robertson, S., Zaragoza, H., et al.  The probabilistic relevance framework: Bm25 and beyond.  _Foundations and Trends® in Information Retrieval_ , 3(4):333–389, 2009.
  * Rubin et al. (2021) Rubin, O., Herzig, J., and Berant, J.  Learning to retrieve prompts for in-context learning.  _arXiv preprint arXiv:2112.08633_ , 2021.
  * Saw et al. (1984) Saw, J. G., Yang, M. C., and Mo, T. C.  Chebyshev inequality with estimated mean and variance.  _The American Statistician_ , 38(2):130–132, 1984.
  * Stankeviciute et al. (2021) Stankeviciute, K., M Alaa, A., and van der Schaar, M.  Conformal time-series forecasting.  _Advances in neural information processing systems_ , 34:6216–6228, 2021.
  * Steerneman (1983) Steerneman, T.  On the total variation and hellinger distance between signed measures; an application to product measures.  _Proceedings of the American Mathematical Society_ , 88(4):684–688, 1983.
  * Tay et al. (2022) Tay, Y., Tran, V., Dehghani, M., Ni, J., Bahri, D., Mehta, H., Qin, Z., Hui, K., Zhao, Z., Gupta, J., et al.  Transformer memory as a differentiable search index.  _Advances in Neural Information Processing Systems_ , 35:21831–21843, 2022.
  * Touvron et al. (2023) Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_ , 2023.
  * Von Oswald et al. (2023) Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M.  Transformers learn in-context by gradient descent.  In _International Conference on Machine Learning_ , pp. 35151–35174. PMLR, 2023.
  * Vovk et al. (1999) Vovk, V., Gammerman, A., and Saunders, C.  Machine-learning applications of algorithmic randomness.  1999\.
  * Vovk et al. (2005) Vovk, V., Gammerman, A., and Shafer, G.  _Algorithmic learning in a random world_ , volume 29.  Springer, 2005.
  * Wang et al. (2022a) Wang, B., Min, S., Deng, X., Shen, J., Wu, Y., Zettlemoyer, L., and Sun, H.  Towards understanding chain-of-thought prompting: An empirical study of what matters.  _arXiv preprint arXiv:2212.10001_ , 2022a.
  * Wang et al. (2023a) Wang, B., Chen, W., Pei, H., Xie, C., Kang, M., Zhang, C., Xu, C., Xiong, Z., Dutta, R., Schaeffer, R., Truong, S., Arora, S., Mazeika, M., Hendrycks, D., Liu, Z., Cheng, Y., Keyejo, S., Song, D., and Li, B.  Decodingtrust: A comprehensive assessment of trustworthiness in gpt models.  _NeurIPS_ , 2023a.
  * Wang et al. (2023b) Wang, L., Yang, N., and Wei, F.  Learning to retrieve in-context examples for large language models.  _arXiv preprint arXiv:2307.07164_ , 2023b.
  * Wang et al. (2022b) Wang, Y., Hou, Y., Wang, H., Miao, Z., Wu, S., Chen, Q., Xia, Y., Chi, C., Zhao, G., Liu, Z., et al.  A neural corpus indexer for document retrieval.  _Advances in Neural Information Processing Systems_ , 35:25600–25614, 2022b.
  * Weber et al. (2022) Weber, M. G., Li, L., Wang, B., Zhao, Z., Li, B., and Zhang, C.  Certifying out-of-domain generalization for blackbox functions.  In _Proceedings of the 39th International Conference on Machine Learning_ , 2022.
  * Wei et al. (2021) Wei, J., Bosma, M., Zhao, V. Y., Guu, K., Yu, A. W., Lester, B., Du, N., Dai, A. M., and Le, Q. V.  Finetuned language models are zero-shot learners.  _arXiv preprint arXiv:2109.01652_ , 2021.
  * Xiong et al. (2020) Xiong, L., Xiong, C., Li, Y., Tang, K.-F., Liu, J., Bennett, P., Ahmed, J., and Overwijk, A.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  _arXiv preprint arXiv:2007.00808_ , 2020.
  * Xu & Xie (2021) Xu, C. and Xie, Y.  Conformal prediction interval for dynamic time-series.  In _International Conference on Machine Learning_ , pp. 11559–11569. PMLR, 2021.
  * Yang & Kuchibhotla (2021) Yang, Y. and Kuchibhotla, A. K.  Finite-sample efficient conformal prediction.  _arXiv preprint arXiv:2104.13871_ , 2021.
  * Zaffran et al. (2022) Zaffran, M., Féron, O., Goude, Y., Josse, J., and Dieuleveut, A.  Adaptive conformal predictions for time series.  In _International Conference on Machine Learning_ , pp. 25834–25866. PMLR, 2022.
  * Zhang et al. (2023a) Zhang, P., Xiao, S., Liu, Z., Dou, Z., and Nie, J.-Y.  Retrieve anything to augment large language models.  _arXiv preprint arXiv:2310.07554_ , 2023a.
  * Zhang & Tetreault (2019) Zhang, R. and Tetreault, J.  This email could save your life: Introducing the task of email subject line generation.  _arXiv preprint arXiv:1906.03497_ , 2019.
  * Zhang et al. (2023b) Zhang, R., Frei, S., and Bartlett, P. L.  Trained transformers learn linear models in-context.  _arXiv preprint arXiv:2306.09927_ , 2023b.

## Appendices

1Contents

##  Appendix A Discussions of limitations and future work

#### Limitations

One potential challenge of applying C-RAG practically could be the collection
of calibration data. In practice, the user input texts are sampled from a
time-series data distribution. Therefore, accessing in-distribution
calibration samples requires collecting real-time query samples, which could
pose the challenge of computational resources and system latency. Another
potential limitation may lie in the probability of the guarantee. Since C-RAG
can only provide a high-confidence risk bound via conformal risk analysis,
generations with excessive risks can exist. Therefore, we may need more
calibration samples to counter for a higher confidence level, and thus
mitigate the appearance of outliers to a large extent. Also, although the
analysis in C-RAG shows the benefits of a large external knowledge base to a
low conformal generation risk, the large knowledge base may induce a larger
time complexity of KNN searching and space complexity of storing the examples,
leading to a trade-off between the generalization/utility and inference
efficiency.

#### Future work

One interesting future work is to provide conformal risk analysis for time-
series data. Conformal prediction for time series (Zaffran et al., 2022; Xu &
Xie, 2021; Stankeviciute et al., 2021) adaptively adjusts the prediction
coverage for sequential data for the regression and classification task.
However, the adaptive risk calibration for time series is unexplored but
important to practical deployments. Therefore, conformal risk analysis for
time series can further motivate the application of conformal risk analysis
for LLMs.

##  Appendix B Additional related work

Retrieval augmented generation (RAG) is a framework for improving the
generation quality of LLMs via retrieving relevant information from the
external knowledge base and grounding the model on the information for
conditional generations. Biencoder retrieval methods (Lewis et al., 2020;
Karpukhin et al., 2020; Xiong et al., 2020) leverage two encoders to map the
query text and candidate texts into the embedding space and retrieve candidate
texts with high embedding similarity to the query text embedding. End-to-end
retrieval methods (Tay et al., 2022; Wang et al., 2022b; Kishore et al., 2023)
train a model to map the query text to the id of relevant candidate documents
directly. Another line of work (Luo et al., 2023; Gou et al., 2023) leverages
external tools such as LLMs to retrieve relevant documents via prompting
design. Although RAG demonstrates impressive capacities, the theoretical
analysis of retrieval models for LLM generations is limited. Basu et al.
analyze the retrieval model of constrained function class from a statistical
perspective, but the results cannot be generalized to the self-attention
transformers. In this work, we provide the first analysis of how RAG enhances
the generation quality and mitigate generation risks of self-attention
transformers.

Conformal prediction is a statistical tool to construct the prediction set
with guaranteed prediction coverage (Vovk et al., 1999, 2005; Lei et al.,
2013; Yang & Kuchibhotla, 2021), assuming that the data is exchangeable.
However, conformal prediction can only provide guarantees for the regression
and classification tasks and is not directly applicable to the generation
tasks, which are more relevant for LLMs. Conformal risk controlling methods
(Bates et al., 2021; Angelopoulos et al., 2021, 2022; Quach et al., 2023)
provide a high-confidence risk guarantee with the data exchangeability
assumption for any black-box risk functions. We can define a specific risk
function for a RAG model and certify a risk upper bound of generations based
on statistics on in-distribution calibration set. However, the risk guarantee
is violated under distribution shifts at test time. Angelopoulos et al.;
Farinhas et al. offer a valid conformal risk for monotonic risk functions
under distribution shifts, but the monotonicity assumption may not always hold
in practice. In this work, we introduce the first conformal risk bound for
general bounded risk functions under test-time distribution shifts.

##  Appendix C Conformal generation risks for RAG models

###  C.1 Constrained generation protocol for RAG models

RAG models (Wang et al., 2023b; Rubin et al., 2021; Huang et al., 2023)
combine a retrieval model and a generation LM. The retrieval model retrieves
$N_{\text{rag}}$ relevant examples to the query from an external knowledge
base, and the LM learns in-context from these examples. The knowledge base
contains $N_{\text{ext}}$ samples in
$\hat{{\mathcal{D}}}_{\text{ext}}=\\{(X_{i},Y_{i})\\}_{i\in[N_{\text{ext}}]}$.
The retrieval model uses an encoder to map instances into an embedding space,
and then identifies the relevant examples to the query $X_{\text{test}}$ based
on similarity. This similarity, defined by
$s_{\theta_{r}}(\cdot,\cdot):{\mathcal{X}}\times{\mathcal{X}}\mapsto{\mathbb{R}}$
and parameterized by $\theta_{r}$, is used to find the nearest examples using
KNN search in the embedding space.

We arrange the retrieved $N_{\text{rag}}$ in-context examples and the test
example $X_{\text{test}}$ into augmented input text $X^{\text{(rag)}}$ using a
template. We then sample the generation from
$p_{\theta_{l}}(\cdot|X^{\text{(rag)}})$ repeatedly until $\lambda_{g}$
generations are collected. To control the diversity of generations, we reject
those with a similarity higher than a threshold $\lambda_{s}$ to the previous
generations. In essence, the constrained generation protocol is controlled by
configuration ${\bm{\lambda}}=[N_{\text{rag}},\lambda_{g},\lambda_{s}]$ and
output a generation set $T_{{\bm{\lambda}},p_{\theta_{l}}}(x)$ based on the
configuration ${\bm{\lambda}}$ and input $x$. We refer to Algorithm 1 for the
pseudocode of the protocol.

Algorithm 1 Constrained generation protocol for RAG

1: Input: input prompt $X_{\text{test}}$, LM $p_{\theta_{l}}(y|x)$, generation
set size $\lambda_{s}$, retrieved example size $N_{\text{rag}}$, external
knowledge base $\hat{{\mathcal{D}}}_{\text{ext}}$, similarity measurement
function $s_{\theta_{r}}(\cdot,\cdot)$ with embedding model parameterized by
$\theta_{r}$, generation similarity threshold $\lambda_{g}$, parameter
configuration ${\bm{\lambda}}=[N_{\text{rag}},\lambda_{g},\lambda_{s}]$

2: Output: Generation set ${\mathcal{G}}_{\bm{\lambda}}(X_{\text{test}})$

3: ${\mathcal{G}}_{\bm{\lambda}}(X_{\text{test}})\leftarrow\Phi$

4:
${\mathcal{Z}}\leftarrow\text{KNN}(X_{\text{test}},N_{\text{rag}};\hat{{\mathcal{D}}}_{\text{ext}},s_{\theta_{r}})$
{Retrieve $N_{\text{rag}}$ examples from $\hat{{\mathcal{D}}}_{\text{ext}}$
via KNN search with similarity measurement $s_{\theta_{r}}(\cdot,\cdot)$}

5: $X^{\text{(rag)}}\leftarrow\text{Template}(X_{\text{test}},{\mathcal{Z}})$
{Augmented prompt with $X_{\text{test}}$ and retrieved examples
${\mathcal{Z}}$ with a template}

6: while $|{\mathcal{G}}_{\bm{\lambda}}(X_{\text{test}})|<\lambda_{s}$ do

7: $y\sim p_{\theta_{l}}(\cdot|X^{\text{(rag)}})$

8: while $\exists
g\in{\mathcal{G}}_{\bm{\lambda}},s_{\theta_{r}}(y,g)>\lambda_{g}$ do

9: $y\sim p_{\theta_{l}}(\cdot|X^{\text{(rag)}})$ {Reject sampling}

10: end while

11:
${\mathcal{G}}_{\bm{\lambda}}(X_{\text{test}})={\mathcal{G}}_{\bm{\lambda}}(X_{\text{test}})\cup\left\\{y\right\\}$

12: end while

13: Return ${\mathcal{G}}_{\bm{\lambda}}(X_{\text{test}})$

##  Appendix D Risk Guarantees

###  D.1 Risk guarantee (1) (Proposition 1)

###### Proof of Proposition 1.

The proof sketch follows (Angelopoulos et al., 2021). Since the risk function
$R(\cdot,\cdot)$ is upper bounded by $1$, we can apply a tighter version of
Hoeffding’s inequality (Hoeffding, 1994) for
$\hat{\alpha}>\mathbb{E}[R(T_{{{\bm{\lambda}}},p_{\theta_{l}}}(x),y)]$:

${\mathbb{P}}\left[R(T_{{{\bm{\lambda}}},p_{\theta_{l}}}(x),y)\geq\hat{\alpha}\right]\leq\exp\left\\{-N_{\text{cal}}h(\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}}),\hat{\alpha})\right\\}$
(8)

Also, applying Bentkus inequality (Bentkus, 2004), we have:

${\mathbb{P}}\left[R(T_{{{\bm{\lambda}}},p_{\theta_{l}}}(x),y)\geq\hat{\alpha}\right]\leq
e{\mathbb{P}}\left[\text{Bin}(N_{\text{cal}},\hat{\alpha})\leq\left\lceil
N_{\text{cal}}\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right\rceil\right]$
(9)

Combining Equations 8 and 9, we have:

${\mathbb{P}}\left[R(T_{{{\bm{\lambda}}},p_{\theta_{l}}}(x),y)\geq\hat{\alpha}\right]\leq\min\left(\exp\left\\{-N_{\text{cal}}h\left(\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}}),\hat{\alpha})\right)\right\\},e{\mathbb{P}}\left[\text{Bin}(N_{\text{cal}},\hat{\alpha})\leq\left\lceil
N_{\text{cal}}\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right\rceil\right]\right)$
(10)

Or equivalently, given uncertainty $1-\delta$, we have:

$\delta=\min\left(\exp\left\\{-N_{\text{cal}}h\left(\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}}),\hat{\alpha})\right)\right\\},e{\mathbb{P}}\left[\text{Bin}(N_{\text{cal}},\hat{\alpha})\leq\left\lceil
N_{\text{cal}}\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right\rceil\right]\right),$
(11)

which leads to the following by formulating an inverse function:

$\hat{\alpha}=\min\left\\{h^{-1}\left(\dfrac{1/\delta}{N_{\text{cal}}};\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right),\Phi^{-1}_{\text{bin}}\left(\dfrac{\delta}{e};N_{\text{cal}},\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right)\right\\}$
(12)

∎

######  Remarks.

Given the constrained generation protocol $T_{{\bm{\lambda}},p_{\theta_{l}}}$,
RAG generation parameter ${\bm{\lambda}}$, a calibration set
$\hat{{\mathcal{D}}}_{\text{cal}}$, and a risk function
$R(\cdot,\cdot):2^{\mathcal{Y}}\times{\mathcal{Y}}\mapsto{\mathbb{R}}$, we aim
to provide a risk guarantee of the test sample
$(X_{\text{test}},Y_{\text{test}})$:

${\mathbb{P}}\left[R(T_{{{\bm{\lambda}}},p_{\theta_{l}}}(X_{\text{test}}),Y_{\text{test}})\leq\hat{\alpha}\right]\geq
1-\delta,$ (13)

where $\hat{\alpha}$ is the conformal risk upper bound, and the confidence
level $1-\delta$ can be computed by Hoeffding-Bentkus inequalities (Bates et
al., 2021):

$\displaystyle\delta=\min\left(\exp\left\\{-N_{\text{cal}}h\left(\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}}),\hat{\alpha})\right)\right\\},e{\mathbb{P}}\left[\text{Bin}(N_{\text{cal}},\hat{\alpha})\leq\left\lceil
N_{\text{cal}}\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right\rceil\right]\right),$
(14)

where $h(a,b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))$, $\text{Bin}(\cdot,\cdot)$
denotes the binomial distribution, $N_{\text{cal}}$ is the number of samples
in the calibration set, and $\hat{R}(\cdot)$ computes the empirical risk on
the calibration set.

Given the confidence level $1-\delta$, we can also inversely compute the
conformal risk upper bound $\hat{\alpha}$ as the following:

$\hat{\alpha}=\min\left\\{h^{-1}\left(\dfrac{1/\delta}{N_{\text{cal}}};\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right),\Phi^{-1}_{\text{bin}}\left(\dfrac{\delta}{e};N_{\text{cal}},\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})\right)\right\\}$
(15)

where $h^{-1}(\cdot;\cdot)$ is the partial inverse function such that
$h^{-1}(h(a,b);a)=b$ with $h(a,b)=a\log(a/b)+(1-a)\log((1-a)/(1-b))$, and
$\Phi^{-1}_{\text{bin}}$ denotes the inverse of CDF of binomial distribution.
The HB bound uses the empirical risk on the calibration set as test statistics
and provides finite-sample statistical results with surprising empirical
effectiveness.

#### Alternative approach for Risk Guarantee Proposition 1

We can obtain a tighter guarantee of the conformal risk if we assume that the
given configuration vector ${\bm{\lambda}}$ has dimension $1$ (i.e., $B=1$)
and the risk function $R(\cdot,\cdot)$ monotonically increases in parameter
${\bm{\lambda}}$ and is upper bounded by $C$
$(R:2^{\mathcal{Y}}\times{\mathcal{Y}}\mapsto(-\infty,C])$. Then, we can have
the following conformal risk guarantee according to (Angelopoulos et al.,
2022):

$\displaystyle\dfrac{N_{\text{cal}}}{N_{\text{cal}}+1}\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})-\dfrac{C}{N_{\text{cal}}+1}\leq\mathbb{E}\left[R(T_{\hat{{\bm{\lambda}}},p_{\theta_{l}}}(X_{\text{test}}),Y_{\text{test}})\right]\leq\dfrac{N_{\text{cal}}}{N_{\text{cal}}+1}\hat{R}(\hat{{\mathcal{D}}}_{\text{cal}})+\dfrac{C}{N_{\text{cal}}+1}.$
(16)

Although the guarantee in Equation 16 is tighter with the guarantee of the
upper bound and the lower bound, the additional assumption of single
dimensionality and monotonicity does not hold for many practical generation
protocols. Therefore, we mainly consider the conformal risk bound in Equation
15 across the analysis. We also add discussions that C-RAG is flexible in
considering different types of conformal risk bounds, which basically presents
an explicit function of the controlled risk with respect to the empirical
risk. Since we build the connection between the empirical risk $\hat{R}$ to
the retrieval model in the risk in the analysis, we only need to directly
connect the empirical risk to the controlled risk via the explicit function to
achieve end-to-end certification.

###  D.2 Risk guarantee (2) (Proposition 2)

###### Proof of Proposition 2.

The proof follows (Holm, 1979). We consider $|\Lambda|$ independent hypothesis
test corresponding to the $|\Lambda|$ Null hypothesis. By the Bonferroni
method, each test is performed at a significance level of
$\dfrac{\delta}{|\Lambda|}$. Therefore, The probability of not making a Type I
error in a single test is $1-\dfrac{\delta}{|\Lambda|}$. The probability of
making no Type I error in all $|\Lambda|$ tests is
$(1-\dfrac{\delta}{|\Lambda|})^{|\Lambda|}$. The probability of making at
least one Type I error (i.e., FWER) is the complement of making no Type I
errors, which is $1-(1-\dfrac{\delta}{|\Lambda|})^{|\Lambda|}\leq\delta$.
Therefore, we prove that the familywise error rate is $\delta$ for Bonferroni
correction. Thus, going back to the risk guarantee, we have:

${\mathbb{P}}\left[\sup_{\hat{{\bm{\lambda}}}\in\hat{\Lambda}_{\alpha}}\left\\{R\left(T_{\hat{{\bm{\lambda}}},p_{\theta_{l}}}(x),y\right)\right\\}\leq\alpha\right]\geq
1-\delta$ (17)

∎

######  Remarks.

To achieve conformal analysis (2), we follow the procedure in (Angelopoulos et
al., 2021): (a) for each parameter configuration ${\bm{\lambda}}$ in the
feasible region $\Lambda$, associate the null hypothesis:
${\mathcal{H}}_{j}:R(T_{{\bm{\lambda}},p_{\theta_{l}}})>\alpha$ (rejecting the
null hypothesis implies controlling the risk below $\alpha$ with
hyperparameter ${\bm{\lambda}}$), (b) for each null hypothesis, compute a
finite-sample valid p-value $p_{j}$ using Hoeffding-Bentkus inequality, and
(c) return $\hat{\Lambda}_{\alpha}={\mathcal{A}}(p_{1},...,p_{|\Lambda|})$,
where ${\mathcal{A}}$ is an algorithm that controls the family-wise error rate
(FWER). Essentially, FWER controls the error by union bounds over the
hyperparameter space. The Bonferroni correction yields
$\hat{\Lambda}_{\alpha}=\\{\hat{{\bm{\lambda}}}_{j}:\delta_{j}\leq\delta/|\Lambda|\\}$.
The graph-based search in Algorithm 2 dynamically assigns the error levels and
yields a tighter certification. Specifically, we maintain a directed graph
with nodes denoting the error rate of the parameter configuration and edges
denoting the correlations between two parameters. The correlations can be
instantiated randomly. We first randomly assign error rates to all feasible
parameter configurations, and then once we search for one valid parameter with
a smaller p-value than the assigned error rate, we will add the parameter to
the valid set and propagate the excessive error rate to other nodes. The
procedure repeats until no valid parameter can be found.
Computation of p-values. Due to the duality between p-values and confidence
intervals (Bates et al., 2021), we compute the p-value by applying the
Hoeffding-Bentkus inequality as the following:

$p_{j}=\min\left(\exp\left\\{-N_{\text{cal}}h\left(\hat{\mathbb{E}}[R(T_{{\bm{\lambda}}_{j},p_{\theta_{l}}}(x),y)],\hat{\alpha})\right)\right\\},e{\mathbb{P}}\left[\text{Bin}(N_{\text{cal}},\hat{\alpha})\leq\left\lceil
N_{\text{cal}}\hat{\mathbb{E}}[R(T_{{\bm{\lambda}}_{j},p_{\theta_{l}}}(x),y)]\right\rceil\right]\right),$
(18)

where $\hat{\mathbb{E}}[R(T_{{\bm{\lambda}}_{j},p_{\theta_{l}}}(x),y)]$
denotes the empirical mean risk with configuration
${\bm{\lambda}}_{j}~{}(j\in\\{1,2,..,|\Lambda|\\})$.

Algorithm 2 Graph-based valid configurations search

1: Input: confidence error level $\delta$, parameter configurations
$\Lambda=\\{{\bm{\lambda}}_{1},...,{\bm{\lambda}}_{N}\\}$, $p-$values
$(p_{1},...,p_{N})$, graph ${\mathcal{G}}$, initial error budget $\delta_{i}$
such that $\sum_{i}\delta_{i}=\delta$

2: Output: valid configurations set with certified conformal risk
$\hat{\Lambda}$

3: $\hat{\Lambda}\leftarrow\Phi$

4: while $\exists i:p_{i}\leq\delta_{i}$ do

5: Select any $i$ such that $p_{i}\leq\delta_{i}$

6: $\hat{\Lambda}\leftarrow\hat{\Lambda}\cup\\{{\bm{\lambda}}_{i}\\}$

7: Update the error level and the graph:
$\delta_{j}\leftarrow\left\\{\begin{aligned}
&\delta_{j}+\delta_{i}g_{i,j},~{}~{}\lambda_{j}\in\Lambda\backslash\hat{\Lambda}\\\
&0,~{}~{}\text{otherwise}\end{aligned}\right.\quad\text{and}\quad
g_{k,j}\leftarrow\left\\{\begin{aligned}
&\dfrac{g_{k,j}+g_{k,i}g_{i,j}}{1-g_{k,i}g_{i,k}},~{}~{}\lambda_{k},\lambda_{j}\in\Lambda\backslash\hat{\Lambda},k\neq
j\\\ &0,~{}~{}\text{otherwise}\end{aligned}\right.$ (19)

8: end while

9: Return $\hat{\Lambda}$

##  Appendix E Grammian generalization bound

######  Lemma E.1 ((Weber et al., 2022)).

Let ${\mathcal{D}}$ and ${\mathcal{Q}}$ denote two distributions supported on
${\mathcal{X}}\times{\mathcal{Y}}$. Let
$h_{\theta}:{\mathcal{X}}\mapsto{\mathcal{Y}}$ be any black-box pretrained
model. Consider any risk/loss function
$\ell:{\mathcal{Y}}\times{\mathcal{Y}}\mapsto{\mathbb{R}}$ such that
$0\leq\ell(h_{\theta}(X),Y)\leq T$, then

$\displaystyle\max_{{\mathcal{Q}},\theta}\mathbb{E}_{(X,Y)\sim{\mathcal{Q}}}[\ell(h_{\theta}(X),Y)]\quad\mathrm{s.t.}\quad
H({\mathcal{D}},{\mathcal{Q}})\leq\rho$ (20) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{(X,Y)\sim{\mathcal{D}}}[\ell(h_{\theta}(X),Y)]+2C_{\rho}\sqrt{{\mathbb{V}}_{(X,Y)\sim{\mathcal{D}}}[\ell(h_{\theta}(X),Y)]}+$
$\displaystyle\rho^{2}(2-\rho^{2})\left(T-\mathbb{E}_{(X,Y)\sim{\mathcal{D}}}[\ell(h_{\theta}(X),Y)]-\dfrac{{\mathbb{V}}_{(X,Y)\sim{\mathcal{D}}}[\ell(h_{\theta}(X),Y)]}{T-\mathbb{E}_{(X,Y)\sim{\mathcal{D}}}[\ell(h_{\theta}(X),Y)]}\right),$

where $C_{\rho}=\sqrt{\rho^{2}(1-\rho^{2})^{2}(2-\rho^{2})}$, for any given
distance bound $\rho>0$ that satisfies

$\rho^{2}\leq
1-\left(1+\dfrac{(T-\mathbb{E}_{(X,Y)\sim{\mathcal{D}}}[\ell(h_{\theta}(X),Y)])^{2}}{{\mathbb{V}}_{(X,Y)\sim{\mathcal{D}}}[\ell(h_{\theta}(X),Y)]}\right)^{-1/2}.$
(21)

This theorem provides a closed-form expression that upper bounds the risk of
$h_{\theta}(\cdot)$ on shifted distribution (namely
$\mathbb{E}_{{\mathcal{Q}}}[\ell(h_{\theta}(X),Y)]$), given bounded Hellinger
distance $H({\mathcal{D}},{\mathcal{Q}})$ and the mean $E$ and variance $V$ of
loss on ${\mathcal{D}}$ under two mild conditions: (1) the function is
positive and bounded (denote the upper bound by $T$); and (2) the distance
$H({\mathcal{D}},{\mathcal{Q}})$ is not too large (specifically,
$H({\mathcal{D}},{\mathcal{Q}})^{2}\leq\bar{\gamma}^{2}:=1-(1+(T-E)^{2}/V)^{-\frac{1}{2}}$).
Since Equation 21 holds for arbitrary models and risk functions
$\ell(h_{\theta}(\cdot),\cdot)$ as long as the function value is bounded by
$[0,T]$, using Equation 21 allows us to provide a generic and succinct
retrieval analysis and conformal risk certificate in Theorem 2 and Theorem 3
that holds for generic models including DNNs without engaging complex model
architectures. Indeed, we only need to query the mean and variance under
${\mathcal{D}}$ for the retrieval model to compute the certificate in Equation
21.

##  Appendix F Proofs and detailed remarks in Section 4

###  F.1 Detailed remark of Definition 1

######  Remarks.

(R1) Note that a retrieval model with random initialization can achieve
$\mathbb{E}[s_{\theta}(x,x^{+})]=\mathbb{E}[s_{\theta}(x,x^{-})]$
asymptotically. We only assume a $V_{\text{rag}}$-retrieval model that
differentiates positive examples from negative examples slightly better than
random with the condition
$\mathbb{E}[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})]>0$. (R2) We also only
assume a moderate stability characterized with bounded variance
$\mathbb{V}[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})]^{1/2}<\ln(\exp\\{-L_{\tau}\\}/(1-\exp\\{-L_{\tau}\\}))$,
which implicitly assumes a moderate generalization of the retrieval model by
the variance-generalization connection (Lam, 2016; Gotoh et al., 2018;
Namkoong & Duchi, 2017). The moderate generalization ability of the retrieval
model is essential since we do not assume that the knowledge base distribution
is identical to the calibration/test distribution. Since the frequently
adopted cosine similarity is bounded in $[-1,1]$, the variance of difference
in similarities $\mathbb{V}[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})]$ is upper
bounded by $1$ (derived by the variance bound $\mathbb{V}[X]\leq(b-a)^{2}/4$
for random variable $X$ bounded in $[a,b]$). Therefore, as long as $L_{\tau}$
is small such that $\ln(\exp\\{-L_{\tau}\\}/(1-\exp\\{-L_{\tau}\\}))>1$, the
variance requirement can be automatically satisfied. (R3) We define the
$V_{\text{rag}}$-retrieval model with a commonly used contrastive loss for
retrieval model training (Wang et al., 2023b; Rubin et al., 2021), but we also
allow for flexibility in considering other types of contrastive loss such as
the triplet loss (Hermans et al., 2017). Towards that, we only need to connect
a different loss formulation to the denominator of the formulation of
$V_{\text{rag}}$ (i.e., $\ln(\exp\\{-L_{\tau}\\}/(1-\exp\\{-L_{\tau}\\}))$).

###  F.2 Detailed remark of Definition 2

######  Remarks.

(R1) $d^{+}$ represents the attention score of positive pairs and quantifies
the utility of embedding matrix $W_{E}$, key matrix $W_{K}$, and query matrix
$W_{Q}$ of the transformer. Note that the attention scores are always non-
negative after the Softmax activation, so $d^{+}>0$ usually holds. (R2)
$\int_{-1}^{1}\Phi_{M}(v)dv$ characterizes the quality of the embedding matrix
$W_{E}$, value matrix $W_{V}$, and projection matrix $W_{P}$. We have a
Softmax normalization for output probability vectors and $M$ is bounded in
$[-1,1]$, so the integral over $[-1,1]$ traverses the support of $M$.
Predictions aligning well with the reference text induce a generally small
value of $M$ and thus a large integral of CDF $\int_{-1}^{1}\Phi_{M}(v)dv$.
Also, note that a random prediction margin $M_{\text{rand}}$ with a uniform
distribution over $[-1,1]$ satisfies
$\int_{-1}^{1}\Phi_{M_{\text{rand}}}(v)dv=1$. Therefore,
$\int_{-1}^{1}\Phi_{M}(v)dv>1=\int_{-1}^{1}\Phi_{M_{\text{rand}}}(v)dv$ only
assumes a better-than-random prediction margin.

###  F.3 Proof and detailed remark of Proposition 3

######  Remarks.

Equation 4 shows the lower bound of the expectation of the retrieved positive
examples by the retrieval model. (R1) For a sufficiently large number of
instances in the external knowledge base $N_{\text{ext}}$ (a typical scenario
in practice), the lower bound approximately scales with $0.9N_{\text{rag}}$
and this scaling occurs at an exponential rate with respect to
$N_{\text{ext}}$. These findings imply that with a large external knowledge
base, a large ratio of the retrieved examples is positive (i.e., with the same
groundtruth output), which is valuable as the retrieved positive examples
which share similar semantic meanings as the query examples can improve in-
context learning of LLMs (Min et al., 2022; Wang et al., 2022a). To formulate
this observation in a rigorous way, we theoretically show the benefits of
retrieved positive in-context examples in achieving low conformal generation
risks in Theorem 1. (R2) The lower bound of the expected retrieved positive
examples also correlates with the balance in the external knowledge base
(i.e., $r^{(c)}_{\text{ext}}$). The correlation implies that if the knowledge
base is highly long-tailed such that samples of certain reference texts are
rare (i.e., $r_{\text{ext}}^{(c)}$ is small), we require a larger sample size
of knowledge base $N_{\text{ext}}$ to compensate for the long-tail
distribution and achieve comparable retrieval quality. (R3) The bound also
shows that a low-variance retrieval model (i.e., a small $V_{\text{rag}}$) can
generalize well to test distribution and induce a better retrieval quality.

Proof sketch. We first formulate the expectation of similarity difference
between positive pairs and negative pairs
$\mathbb{E}[s_{\theta_{r}}(x,x^{+})-s_{\theta_{r}}(x,x^{-})]$ as a function of
the contrastive loss of the retrieval model $L_{\tau}$. Then, we apply
Chebyshev’s inequality to upper bound the failure probability
${\mathbb{P}}[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})]$ as a function of
$V_{\text{rag}}$. We then derive a lower bound of the number of retrieved
positive examples, which follows a binomial distribution with $N_{\text{rag}}$
trials and the failure rate as a function of $V_{\text{rag}}$. We finally
correct the bound with the finite-sample errors of the knowledge base by the
tail bound of categorical distribution.

###### Proof of Proposition 3.

Let ${\mathcal{D}}$ be the data distribution, which is also the training
distribution of the retrieval model, conformal calibration distribution, and
test distribution. For a sample $(x,y)\sim{\mathcal{D}}$, we denote
${\mathcal{D}}_{\text{ext}}^{+}(x)$, ${\mathcal{D}}_{\text{ext}}^{-}(x)$ be
the distribution of positive examples (with the same groundtruth output $y$)
and negative examples (with different groundtruth output to $y$) of sample $x$
in the external knowledge base. Then we can formulate the expectation of
contrastive loss of the retrieval model as:

$\displaystyle L_{\tau}$
$\displaystyle=\mathbb{E}_{x\sim{\mathcal{D}},x^{+}\sim{\mathcal{D}}^{+}_{\text{ext}}(x),x^{-}\sim{\mathcal{D}}^{-}_{\text{ext}}(x)}\left[{\mathcal{L}}_{\text{contrastive}}(x,x^{+},x^{-})\right]$
(22)
$\displaystyle=\mathbb{E}_{x\sim{\mathcal{D}},x^{+}\sim{\mathcal{D}}^{+}_{\text{ext}}(x),x^{-}\sim{\mathcal{D}}^{-}_{\text{ext}}(x)}\left[-\log\dfrac{\exp\left\\{s_{\theta}(x,x^{+})\right\\}}{\exp\left\\{s_{\theta}(x,x^{+})\right\\}+\exp\left\\{s_{\theta}(x,x^{-})\right\\}}\right],$

which is equivalent to

$\mathbb{E}_{x\sim{\mathcal{D}},x^{+}\sim{\mathcal{D}}^{+}_{\text{ext}}(x),x^{-}\sim{\mathcal{D}}^{-}_{\text{ext}}(x)}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]=\ln\dfrac{\exp\left\\{-L_{\tau}\right\\}}{1-\exp\left\\{-L_{\tau}\right\\}}>0.$
(23)

Then we can apply Chebyshev’s inequality (Saw et al., 1984) to the random
variable $s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})$ and get the following:

$\displaystyle{\mathbb{P}}\left[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})\right]$
$\displaystyle={\mathbb{P}}_{x\sim{\mathcal{D}},x^{+}\sim{\mathcal{D}}^{+}_{\text{ext}}(x),x^{-}\sim{\mathcal{D}}^{-}_{\text{ext}}(x)}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})<0\right]$
(24)
$\displaystyle\leq\dfrac{\mathbb{V}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]}{\mathbb{E}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]^{2}}$
(25)
$\displaystyle\leq\left(\dfrac{\sqrt{\mathbb{V}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]}}{\mathbb{E}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]}\right)^{2}=V_{\text{rag}}^{2}<1.$
(26)

We first focus on one demonstration example $Z_{r}$ retrieved by
$s_{\theta}(\cdot,\cdot)$. According to the retrieval mechanism, the example
$Z_{r}$ has the highest similarity (measured by $s_{\theta}(\cdot,\cdot)$) to
the query sample $Z_{q}$. Recall that $r^{(c)}_{\text{cal}}$ and
$r^{(c)}_{\text{ext}}$ be the event probability of the $c$-th category in the
categorical calibration distribution and categorical external knowledge
distribution. Let
${\bm{r}}_{\text{ext}}=\left[r^{(1)}_{\text{ext}},r^{(2)}_{\text{ext}},...,r^{(C)}_{\text{ext}}\right]$.
Since we only have $N_{\text{ext}}$ finite sample drawn from
${\mathcal{D}}_{\text{ext}}$ in the external knowledge base in practice, we
notate the empirical categorical portions as
$\hat{{\bm{q}}}_{\text{ext}}=\left[\hat{r}^{(1)}_{\text{ext}},\hat{r}^{(2)}_{\text{ext}},...,\hat{r}^{(C)}_{\text{ext}}\right]$,
where $\hat{r}^{(c)}_{\text{ext}}~{}(c\in\\{1,..,C\\})$ represents the portion
of samples with grountruth text $c\in{\mathcal{Y}}$ in the external knowledge
base. Then we can apply the concentration bound of categorical distribution as
(Agrawal & Jia, 2017):

$\displaystyle{\mathbb{P}}\left[\|\hat{{\bm{r}}}_{\text{ext}}-{\bm{r}}_{\text{ext}}\|_{1}\geq\dfrac{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}{N_{\text{ext}}}\right]\leq\delta_{\text{ext}},$
(27)

where $\delta_{\text{ext}}>0$ represents the confidence level of the tail
bound. Then we can upper bound the probability that the groundtruth output
$g(Z_{r})$ of the retrieved sample $Z_{r}$ is not equal to that of the query
sample $g(Z_{q})$ as the following:

$\displaystyle{\mathbb{P}}\left[g(Z_{r})\notin g(Z_{q})\right]$
$\displaystyle={\mathbb{P}}_{Z_{q}\sim{\mathcal{D}}}\left[g(Z_{r})\notin
g(Z_{q})\left|s_{\theta}(Z_{q},Z_{r})\geq\max_{z\in{\mathcal{D}}_{\text{ext}}}s_{\theta}(z,Z_{q})\right.\right]$
(28)
$\displaystyle={\mathbb{P}}_{Z_{q}\sim{\mathcal{D}}}\left[\max_{Z^{-}\in{\mathcal{D}}^{-}_{\text{ext}}(Z_{q})}s_{\theta}(Z^{-},Z_{q})\geq\max_{Z^{+}\in{\mathcal{D}}^{+}_{\text{ext}}(Z_{q})}s_{\theta}(Z^{+},Z_{q})\right]$
(29)
$\displaystyle={\mathbb{P}}_{Z_{q}\sim{\mathcal{D}}}\left[s_{\theta}(Z^{-},Z_{q})\geq
s_{\theta}(Z^{+},Z_{q}),~{}~{}\forall
Z^{+}\in{\mathcal{D}}^{+}_{\text{ext}}(Z_{q}),~{}\exists
Z^{-}\in{\mathcal{D}}^{-}_{\text{ext}}(Z_{q})\right]$ (30)
$\displaystyle\leq\sum_{c=1}^{C}r^{(c)}_{\text{cal}}\left(1-r^{(c)}_{\text{ext}}\right)N_{\text{ext}}{\mathbb{P}}\left[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})\right]^{N_{\text{ext}}r^{(c)}_{\text{ext}}},$
(31)

where Equation 31 is derived by applying the union bound. Considering finite-
sample error of categorical distribution in Equation 27 and combining Equation
26, we finally have:

$\displaystyle{\mathbb{P}}\left[g(Z_{r})\notin g(Z_{q})\right]$
$\displaystyle\leq\sum_{c=1}^{C}r^{(c)}_{\text{cal}}\left(1-r^{(c)}_{\text{ext}}\right)N_{\text{ext}}{\mathbb{P}}\left[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})\right]^{N_{\text{ext}}r^{(c)}_{\text{ext}}}$
(32)
$\displaystyle\leq\sum_{c=1}^{C}r^{(c)}_{\text{cal}}\left(1-r^{(c)}_{\text{ext}}+\dfrac{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}{N_{\text{ext}}}\right)N_{\text{ext}}V_{\text{rag}}^{0.5N_{\text{ext}}\left(r^{(c)}_{\text{ext}}-{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}/{N_{\text{ext}}}\right)}.$
(33)

Since we assume that the retrieval model retrieves samples identically from
the external knowledge base, the number of retrieved positive examples
$N_{\text{pos}}$ follows a Binomial distribution with $N_{\text{rag}}$ trials
and failure rate in Equation 33. Therefore, we can lower bound the expectation
of $N_{\text{pos}}$ as the following:

$\mathbb{E}\left[N_{\text{pos}}\right]\geq
N_{\text{rag}}\left(1-\delta_{\text{ext}}\right)\left(1-\sum_{c=1}^{C}r^{(c)}_{\text{cal}}\left(1-r^{(c)}_{\text{ext}}+\dfrac{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}{N_{\text{ext}}}\right)N_{\text{ext}}V_{\text{rag}}^{0.5N_{\text{ext}}\left(r^{(c)}_{\text{ext}}-{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}/{N_{\text{ext}}}\right)}\right),$
(34)

which holds for any $\delta_{\text{ext}}>0$. Therefore, letting
$\delta_{\text{ext}}=0.1$, we can finally conclude that:

$\mathbb{E}\left[N_{\text{pos}}\right]\geq\dfrac{9}{10}N_{\text{rag}}\left(1-\sum_{c=1}^{C}r^{(c)}_{\text{cal}}\left(N_{\text{ext}}-r^{(c)}_{\text{ext}}N_{\text{ext}}+{\sqrt{2\ln{10}}}\right)V_{\text{rag}}^{0.5\left(r^{(c)}_{\text{ext}}N_{\text{ext}}-{\sqrt{2\ln{10}}}\right)}\right).$
(35)

∎

###  F.4 Proof and detailed remark of Theorem 1

######  Remarks.

In Theorem 1, we theoretically show that the conformal generation risk with
RAG $\hat{\alpha}_{\text{rag}}$ is smaller than the risk without RAG
$\hat{\alpha}$ with a high probability. (R1) We can observe that the
probability monotonically increases in the sample size of the calibration set
$N_{\text{cal}}$, the size of retrieved examples $N_{\text{rag}}$, and the
number of instances in the external knowledge base $N_{\text{ext}}$. In
particular, a large $N_{\text{cal}}$ reduces the finite-sample error during
the calibration and induces a better approximation of the true generation risk
with the empirical risk on the calibration set. A large $N_{\text{rag}}$ and
$N_{\text{ext}}$ brings in related background information from a more
knowledge-intensive knowledge base, which enhances the quality of generations
augmented by retrieval. (R2) Furthermore, the probability
${\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]$ increases
with the increase in transformer’s quality, which is quantified by the
attention scores for a positive pair (i.e., $d^{+}$ ) and the prediction
capability (without RAG) (i.e., $\normalsize\int_{-1}^{1}\Phi_{M}(v)dv-1$ ).
Since $1-\Phi_{M}(0)$ represents the population risk without RAG, the
difference of the prediction margin CDF $\Phi_{M}(\cdot)$ (monotonically
increasing) directly characterizes the benefit of generation quality with RAG.
The quality improvement provided by RAG also exponentially induces a larger
probability of reducing the conformal generation risk of a single LLM. The
transformer uncertainty $p_{t}$ also decreases exponentially with a large
number of retrieved examples, indicating that more examples retrieved by a
good retrieval model benefit a lower conformal generation risk. (R3) The
retrieval model uncertainty $p_{r}$ decreases with a low-variance retrieval
model (small $V_{\text{rag}}$), which can generalize well to test
distribution. (R4) We focus on the conformal generation risk formulated in
Proposition 1, but we can easily adapt the results to any other forms of
conformal risks. Since we build the connection between the empirical risk
$\hat{R}$ to the retrieval model quality, we only need to directly connect the
empirical risk to the certified generation risk via the explicit function to
achieve end-to-end certification. (R5) We define the positive pairs as
examples sharing the same semantic meanings of reference texts for simplicity
of the certification results. In the certification framework, we can also
consider a relaxed definition of positive pairs by the similarity of reference
texts in the embedding space. Similarly, the examples with high similarity of
reference texts to the query example will induce high attention scores and
benefit the generation with the attention mechanism.

Proof sketch. We decompose the one-layer self-attention mapping as the
combinations of attention with positive examples and attention with negative
examples. Based on the explicit formulation, we then derive a lower bound of
the logit difference of the ground truth token by taking a lower bound of the
number of positive examples (derived from Proposition 3) and the attention
scores with positive examples. Next, we get a lower bound of the risk
difference between the transformer without RAG and the RAG model. Finally, we
apply Hoeffding’s inequality to derive a lower bound of the difference in
empirical risks, and accordingly, conformal risk bounds. Applying union bounds
over all uncertainty levels concludes the proof.

###### Proof of Theorem 1.

From Proposition 3, we prove that:

$\mathbb{E}\left[N_{\text{pos}}\right]\geq\underline{N}_{\text{pos}}:=\dfrac{9}{10}N_{\text{rag}}\left(1-\sum_{c=1}^{C}r^{(c)}_{\text{cal}}\left(N_{\text{ext}}-r^{(c)}_{\text{ext}}N_{\text{ext}}+{\sqrt{2\ln{10}}}\right)V_{\text{rag}}^{0.5\left(r^{(c)}_{\text{ext}}N_{\text{ext}}-{\sqrt{2\ln{10}}}\right)}\right).$
(36)

Since $N_{\text{pos}}$ is a binomial random variable with $N_{\text{rag}}$
trials, we have the upper bound of the variance
$\mathbb{V}[N_{\text{pos}}]\leq\dfrac{N_{\text{rag}}}{4}$. Applying
Chebyshev’s inequality to the random variable $N_{\text{pos}}$, the following
holds $\forall n_{\text{pos}}<\underline{N}_{\text{pos}}$:

${\mathbb{P}}\left[N_{\text{pos}}\geq n_{\text{pos}}\right]\geq
1-\dfrac{\mathbb{V}[N_{\text{rag}}]}{(\underline{N}_{\text{pos}}-n_{\text{pos}})^{2}}\geq
1-\dfrac{N_{\text{rag}}}{4(\underline{N}_{\text{pos}}-n_{\text{pos}})^{2}},$
(37)

which implicates that we can do the analysis with $N_{\text{pos}}\geq
n_{\text{pos}}$ with probability
$1-\dfrac{\mathbb{V}[N_{\text{rag}}]}{(\underline{N}_{\text{pos}}-n_{\text{pos}})^{2}}$.

Since the query example is encoded at the last position of the sequence (i.e.,
$N_{\text{rag}}+1$-th position), we let $N:=N_{\text{rag}}+1$ for ease of
notation. We denote the probability vector at the position as
$O^{\text{(rag)}}({\bm{q}})$ with RAG and $O({\bm{q}}_{N})$ without RAG
(without RAG, the input text is only the query sample ${\bm{q}}_{N}$). Recall
the single-layer self-attention transformer:

$O^{\text{(rag)}}({\bm{q}})=W_{P}\left\\{W_{V}W_{E}{\bm{q}}_{N}+(W_{V}W_{E}{\bm{q}})\sigma\left((W_{K}W_{E}{\bm{q}})^{T}W_{Q}W_{E}{\bm{q}}_{N}\right)\right\\}.$
(38)

Note that each raw vector of the linear projection matrix (fully connected
layer) represents the prototype embedding denoted as ${\bm{p}}_{c}$ of the
corresponding groundtruth output $c$. Formally, we have
$W_{P}:=[{\bm{p}}_{1},{\bm{p}}_{2},...,{\bm{p}}_{C}]^{T}$. Recall that we
denote $g({\bm{q}}_{N})$ as the groundtruth output of example ${\bm{q}}_{N}$.
Then we can reformulate Equation 38 as the following:

$O^{\text{(rag)}}({\bm{q}})=[{\bm{p}}_{1},{\bm{p}}_{2},...,{\bm{p}}_{C}]^{T}\left\\{W_{V}W_{E}{\bm{q}}_{N}+(W_{V}W_{E}{\bm{q}})\sigma\left((W_{K}W_{E}{\bm{q}})^{T}W_{Q}W_{E}{\bm{q}}_{N}\right)\right\\},$
(39)

which indicates the formulation of $O_{c}^{\text{(rag)}}({\bm{q}})$ denoting
the probability of query sample ${\bm{q}}_{N}$ being with groundtruth output
$c$:

$O_{c}^{\text{(rag)}}({\bm{q}})={\bm{p}}_{c}^{T}\left\\{W_{V}W_{E}{\bm{q}}_{N}+(W_{V}W_{E}{\bm{q}})\sigma\left((W_{K}W_{E}{\bm{q}})^{T}W_{Q}W_{E}{\bm{q}}_{N}\right)\right\\}.$
(40)

We can also similarly formulate the prediction without RAG:

$O_{c}({\bm{q}})={\bm{p}}_{c}^{T}W_{V}W_{E}{\bm{q}}_{N}.$ (41)

Then we will focus on analyzing $O_{c}^{\text{(rag)}}({\bm{q}})$ and connect
it with the quantities of characterizing the quality of the transformer (i.e.,
$d^{+},d^{-},t^{+},t^{-}$) and the quality of retrieved examples. Towards
that, we let ${\mathcal{I}}^{+}({\bm{q}}_{N})$ be the index set of retrieved
examples with the same groundtruth output as ${\bm{q}}_{N}$ (i.e., positive
examples), and ${\mathcal{I}}^{-}({\bm{q}}_{N})$ be the index set of retrieved
examples with the different groundtruth output to ${\bm{q}}_{N}$ (i.e.,
negative examples). Then we can reformulate Equation 40 as the following:

$\displaystyle O_{c}^{\text{(rag)}}({\bm{q}})=$
$\displaystyle{\bm{p}}_{c}^{T}W_{V}W_{E}{\bm{q}}_{N}+{\bm{p}}_{c}^{T}(W_{V}W_{E}{\bm{q}})\sigma\left((W_{K}W_{E}{\bm{q}})^{T}W_{Q}W_{E}{\bm{q}}_{N}\right)$
(42) $\displaystyle=$
$\displaystyle{\bm{p}}_{c}^{T}W_{V}W_{E}{\bm{q}}_{N}+\sum_{i^{+}\in{\mathcal{I}}^{+}({\bm{q}}_{N})}\sigma\left((W_{K}W_{E}{\bm{q}}_{i^{+}})W_{Q}W_{E}{\bm{q}}_{N}\right){\bm{p}}_{c}^{T}(W_{V}W_{E}{\bm{q}}_{i^{+}})$
$\displaystyle+\sum_{i^{-}\in{\mathcal{I}}^{-}({\bm{q}}_{N})}\sigma\left((W_{K}W_{E}{\bm{q}}_{i^{-}})W_{Q}W_{E}{\bm{q}}_{N}\right){\bm{p}}_{c}^{T}(W_{V}W_{E}{\bm{q}}_{i^{-}})$

Recall that we have the following assumption:

$\displaystyle\sigma\left((W_{K}W_{E}{\bm{q}}_{i})^{T}(W_{Q}W_{E}{\bm{q}}_{j})\right)\geq
d^{+}>0,\quad\text{for}~{}g({\bm{q}}_{i})=g({\bm{q}}_{j}),$ (43)

We denote $N_{\text{pos}}$ as the number of positive retrieved examples to the
query sample ${\bm{q}}_{N}$ and the lower bound of it $n_{\text{pos}}$ with
probability
$1-\dfrac{\mathbb{V}[N_{\text{rag}}]}{(\underline{N}_{\text{pos}}-n_{\text{pos}})^{2}}$
according to Equation 37. Note that the attention scores are normalized by
Softmax with the summation of them being $1$. By Equation 42, $\forall c\neq
g({\bm{q}}_{N})$, we have:

$\displaystyle\mathbb{E}\left[O_{g({\bm{q}}_{N})}^{\text{(rag)}}({\bm{q}})-O_{c}^{\text{(rag)}}({\bm{q}})-({\bm{p}}_{g({\bm{q}}_{N})}^{T}W_{V}W_{E}{\bm{q}}_{N}-{\bm{p}}_{c}^{T}W_{V}W_{E}{\bm{q}}_{N})\right]$
(44) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{i^{+}\in{\mathcal{I}}^{+}({\bm{q}}_{N})}\sigma\left((W_{K}W_{E}{\bm{q}}_{i^{+}})W_{Q}W_{E}{\bm{q}}_{N}\right)({\bm{p}}_{g({\bm{q}}_{N})}-{\bm{p}}_{c})^{T}(W_{V}W_{E}{\bm{q}}_{i^{+}})\right.$
$\displaystyle\left.+\sum_{i^{-}\in{\mathcal{I}}^{-}({\bm{q}}_{N})}\sigma\left((W_{K}W_{E}{\bm{q}}_{i^{-}})W_{Q}W_{E}{\bm{q}}_{N}\right)({\bm{p}}_{g({\bm{q}}_{N})}-{\bm{p}}_{c})^{T}(W_{V}W_{E}{\bm{q}}_{i^{-}})\right]$
$\displaystyle\geq$
$\displaystyle\mathbb{E}\left[d^{+}\sum_{i^{+}\in{\mathcal{I}}^{+}({\bm{q}}_{N})}({\bm{p}}_{g({\bm{q}}_{N})}-{\bm{p}}_{c})^{T}(W_{V}W_{E}{\bm{q}}_{i^{+}})+(1-n_{\text{pos}}d^{+})\left(-\sum_{i^{+}\in{\mathcal{I}}^{+}({\bm{q}}_{N})}({\bm{p}}_{g({\bm{q}}_{N})}-{\bm{p}}_{c})^{T}(W_{V}W_{E}{\bm{q}}_{i^{+}})\right)\right]$
$\displaystyle\geq$
$\displaystyle\left((n_{\text{pos}}+1)d^{+}-1\right)\mathbb{E}\left[\sum_{i^{+}\in{\mathcal{I}}^{+}({\bm{q}}_{N})}({\bm{p}}_{g({\bm{q}}_{N})}-{\bm{p}}_{c})^{T}(W_{V}W_{E}{\bm{q}}_{i^{+}})\right]$
$\displaystyle\geq$
$\displaystyle\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\mathbb{E}\left[{\bm{p}}_{g({\bm{q}}_{N})}^{T}W_{V}W_{E}{\bm{q}}_{N}-{\bm{p}}_{c}^{T}W_{V}W_{E}{\bm{q}}_{N}\right]$
$\displaystyle\geq$
$\displaystyle\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\mathbb{E}\left[{\bm{p}}_{g({\bm{q}}_{N})}^{T}W_{V}W_{E}{\bm{q}}_{N}-\max_{c\neq
g({\bm{q}}_{N})}{\bm{p}}_{c}^{T}W_{V}W_{E}{\bm{q}}_{N}\right]$

Recall that $\Phi_{M}(\cdot)$ is the CDF function of the random variable of
prediction marigin $\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N})}({\bm{q}})$ such that
$\Phi_{M}(v)={\mathbb{P}}[\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N})}({\bm{q}})<v]$. Since the
output probability of the transformer is bounded in $[0,1]$, we define a new
random variable $X=\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N})}({\bm{q}})+1$ with $P[0\leq
X\leq 2]=1$. Then we have the following:

$\displaystyle\mathbb{E}\left[O_{g({\bm{q}}_{N})}({\bm{q}})-\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})\right]$
$\displaystyle=1-\mathbb{E}\left[X\right]$ (45)
$\displaystyle=1-\int_{0}^{2}\left(1-\Phi_{X}(x)\right)dx$ (46)
$\displaystyle=1-\int_{-1}^{1}\left(1-\Phi_{M}(v)\right)dv$ (47)
$\displaystyle=\int_{-1}^{1}\Phi_{M}(v)dv-1$ (48)

Note that from Equation 41, we have
$O_{g({\bm{q}}_{N})}({\bm{q}})-O_{c}({\bm{q}})={\bm{p}}_{g({\bm{q}}_{N})}^{T}W_{V}W_{E}{\bm{q}}_{N}-{\bm{p}}_{c}^{T}W_{V}W_{E}{\bm{q}}_{N}$.
Combining Equation 44 and Equation 48, the following holds $\forall c\neq
g({\bm{q}}_{N})$:

$\mathbb{E}\left[O_{g({\bm{q}}_{N})}^{\text{(rag)}}({\bm{q}})-O_{c}^{\text{(rag)}}({\bm{q}})\right]\geq\mathbb{E}\left[O_{g({\bm{q}}_{N})}({\bm{q}})-O_{c}({\bm{q}})\right]+\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right).$
(49)

Letting $c^{*}=\operatorname*{arg\,max}_{c\neq
g({\bm{q}}_{N})}O_{c}^{\text{(rag)}}({\bm{q}})$, we have:

$\displaystyle\mathbb{E}\left[O_{g({\bm{q}}_{N})}^{\text{(rag)}}({\bm{q}})-\max_{c\neq
g({\bm{q}}_{N})}O_{c*}^{\text{(rag)}}({\bm{q}})\right]$
$\displaystyle=\mathbb{E}\left[O_{g({\bm{q}}_{N})}^{\text{(rag)}}({\bm{q}})-O_{c*}^{\text{(rag)}}({\bm{q}})\right]$
(50)
$\displaystyle\geq\mathbb{E}\left[O_{g({\bm{q}}_{N})}({\bm{q}})-O_{c^{*}}({\bm{q}})\right]+\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right)$
$\displaystyle\geq\mathbb{E}\left[O_{g({\bm{q}}_{N})}({\bm{q}})-\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})\right]+\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right),$

which implies the following:

$\mathbb{E}\left[O_{g({\bm{q}}_{N})}^{\text{(rag)}}({\bm{q}})-\max_{c\neq
g({\bm{q}}_{N})}O_{c}^{\text{(rag)}}({\bm{q}})\right]-\mathbb{E}\left[O_{g({\bm{q}}_{N})}({\bm{q}})-\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})\right]\geq\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right),$
(51)

which is equivalent to the following:

$\mathbb{E}\left[\max_{c\neq
g({\bm{q}}_{N})}O_{c}^{\text{(rag)}}({\bm{q}})-O_{g({\bm{q}}_{N})}^{\text{(rag)}}({\bm{q}})\right]\leq\mathbb{E}\left[\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N})}({\bm{q}})\right]-\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right),$
(52)

Recall that we define the risk as $1-\text{Accuracy}$ and notate $R$ and
$R_{\text{rag}}$ as the risk without RAG and with RAG, respectively. Then we
have:

$\displaystyle\mathbb{E}\left[R\right]$
$\displaystyle=1-\mathbb{E}\left[{\mathbb{I}}\left[\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N})}({\bm{q}})<0\right]\right]$
(53) $\displaystyle=1-{\mathbb{P}}\left[\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N})}({\bm{q}})<0\right]$ (54)
$\displaystyle=1-\Phi_{M}(0).$ (55)

Similarly for the risk with RAG $R_{\text{rag}}$, we have:

$\displaystyle\mathbb{E}\left[R_{\text{rag}}\right]$
$\displaystyle=1-\mathbb{E}\left[{\mathbb{I}}\left[\max_{c\neq
g({\bm{q}}_{N})}O^{\text{(rag)}}_{c}({\bm{q}})-O^{\text{(rag)}}_{g({\bm{q}}_{N})}({\bm{q}})<0\right]\right]$
(56) $\displaystyle=1-{\mathbb{P}}\left[\max_{c\neq
g({\bm{q}}_{N})}O^{\text{(rag)}}_{c}({\bm{q}})-O^{\text{(rag)}}_{g({\bm{q}}_{N})}({\bm{q}})<0\right]$
(57) $\displaystyle\leq 1-{\mathbb{P}}\left[\max_{c\neq
g({\bm{q}}_{N})}O_{c}({\bm{q}})-O_{g({\bm{q}}_{N})}({\bm{q}})<\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right)\right]$
(58) $\displaystyle\leq
1-\Phi_{M}\left(\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right)\right),$
(59)

where Equation 58 holds by applying Equation 52. Therefore, combining Equation
55 and Equation 59, the following holds:

$\mathbb{E}\left[R-R_{\text{rag}}\right]\geq\Phi_{M}\left(\left((n_{\text{pos}}+1)d^{+}-1\right)n_{\text{pos}}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right)\right)-\Phi_{M}(0).$
(60)

Let $n_{\text{rag}}=N_{\text{rag}}/2$. Combining Equation 60 and Equation 37,
we get that if $\underline{N}_{\text{pos}}>{N_{\text{rag}}}/{2}>1/d^{+}$, with
probability
$1-\dfrac{N_{\text{rag}}}{4(\underline{N}_{\text{pos}}-{N_{\text{rag}}}/{2})^{2}}$,
we have:

$\mathbb{E}\left[R-R_{\text{rag}}\right]\geq\Phi_{M}\left(\dfrac{d^{+}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right)N_{\text{rag}}}{2}\right)-\Phi_{M}(0).$
(61)

Let $R(Z)$ be the risk of $Z$ sampled from the distribution ${\mathcal{D}}$.
Define the empirical risk $\hat{R}$ and $\hat{R}_{\text{rag}}$ as the
following:

$\displaystyle\hat{R}=\dfrac{1}{N_{\text{cal}}}\sum_{i=1}^{N_{\text{cal}}}R(Z_{i}),\quad\hat{R}_{\text{rag}}=\dfrac{1}{N_{\text{cal}}}\sum_{i=1}^{N_{\text{cal}}}R_{\text{rag}}(Z_{i})$
(62)

According to Equation 14, the statistical guarantee of conformal risk
$\hat{\alpha}$ and $\hat{\alpha}_{\text{rag}}$ with confidence $1-\delta$ can
be formulated as:

$\displaystyle\hat{\alpha}$
$\displaystyle=\min\left\\{h^{-1}\left(\dfrac{1/\delta}{N_{\text{cal}}};\hat{R}\right),\Phi^{-1}_{\text{bin}}\left(\dfrac{\delta}{e};N_{\text{cal}},\hat{R}\right)\right\\},$
(63) $\displaystyle\hat{\alpha}_{\text{rag}}$
$\displaystyle=\min\left\\{h^{-1}\left(\dfrac{1/\delta}{N_{\text{cal}}};\hat{R}_{\text{rag}}\right),\Phi^{-1}_{\text{bin}}\left(\dfrac{\delta}{e};N_{\text{cal}},\hat{R}_{\text{rag}}\right)\right\\},$
(64)

where $\Phi^{-1}_{\text{bin}}(\cdot)$ is the inverse function of CDF of
binomial distribution. Noting that $\hat{\alpha}$ is monotonically increasing
in $\hat{R}$, the following holds by Hoeffding’s inequality:

${\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]\geq{\mathbb{P}}\left[\hat{R}_{\text{rag}}<\hat{R}\right]\geq
1-\exp\left\\{-2N_{\text{cal}}\mathbb{E}\left[R-R_{\text{rag}}\right]^{2}\right\\}.$
(65)

Combining Equation 61 and Equation 65 and using the union bound, under the
condition that $\underline{N}_{\text{pos}}>{N_{\text{rag}}}/{2}>1/d^{+}$, we
have:

${\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]\geq
1-\exp\left\\{-2N_{\text{cal}}\left[\Phi_{M}\left(\dfrac{d^{+}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right)N_{\text{rag}}}{2}\right)-\Phi_{M}(0)\right]^{2}\right\\}-\dfrac{N_{\text{rag}}}{4(\underline{N}_{\text{pos}}-{N_{\text{rag}}}/{2})^{2}}.$
(66)

Let $r_{\text{ext}}^{m}:=\min_{c\in\\{1,..,C\\}}r_{\text{ext}}^{(c)}$. Then we
can show that one sufficient condition of
$\underline{N}_{\text{pos}}>{N_{\text{rag}}}/{2}>1/d^{+}$ is that
$N_{\text{ext}}>\dfrac{2\sqrt{2\ln 10}}{r_{\text{ext}}^{m}}$,
$N_{\text{ext}}V_{\text{rag}}^{0.25r_{\text{ext}}^{m}N_{\text{ext}}}<\dfrac{4}{9}$,
and $N_{\text{rag}}>\dfrac{2}{d^{+}}$. Rearranging the terms and considering
the sufficient condition in Equation 66, we can finally conclude that, under
the condition that $N_{\text{ext}}>\dfrac{2\sqrt{2\ln
10}}{r_{\text{ext}}^{m}}$,
$N_{\text{ext}}V_{\text{rag}}^{0.25r_{\text{ext}}^{m}N_{\text{ext}}}<\dfrac{4}{9}$,
and $N_{\text{rag}}>\dfrac{2}{d^{+}}$, the following holds:

$\displaystyle{\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]\geq$
$\displaystyle
1-\exp\left\\{-2N_{\text{cal}}\left[\Phi_{M}\left(\dfrac{d^{+}\left(\int_{-1}^{1}\Phi_{M}(v)dv-1\right)N_{\text{rag}}}{2}\right)-\Phi_{M}(0)\right]^{2}\right\\}$
(67)
$\displaystyle-\dfrac{25}{N_{\text{rag}}}\left(4-9\sum_{c=1}^{C}r^{(c)}_{\text{cal}}\left(N_{\text{ext}}-r^{(c)}_{\text{ext}}N_{\text{ext}}+{\sqrt{2\ln{10}}}\right)V_{\text{rag}}^{0.5\left(r^{(c)}_{\text{ext}}N_{\text{ext}}-{\sqrt{2\ln{10}}}\right)}\right)^{-2}.$

∎

##  Appendix G Corollary 1: Asymtotic result of Theorem 1

######  Corollary 1 (Theorem 1 with a sufficiently large external knwoledge
base).

Under the same conditions as Theorem 1, suppose that we have a sufficiently
large sample size $N_{\text{ext}}$ in the external knowledge base. We then
have the following guarantee:

$\displaystyle{\mathbb{P}}\left[\hat{\alpha}_{\text{rag}}<\hat{\alpha}\right]\geq
1-p_{t}-\dfrac{25}{16N_{\text{rag}}},$ (68)

where $p_{\text{t}}$ is the uncertainty induced by the quality of the
transformer as formulated in Equation 5, and $\hat{\alpha}_{\text{rag}}$ and
$\hat{\alpha}$ are the conformal generation risks with and without RAG,
respectively.

###### Proof of Corollary 1.

The proof directly follows that of Theorem 1. Considering Equation 5 in the
asymptoptic limit (i.e., $N_{\text{ext}}\rightarrow+\infty$), we obtain the
formulation in Equation 68. ∎

######  Remarks.

(R1) Corollary 1 shows that the conformal generation risk of transformer with
RAG $\hat{\alpha}_{\text{rag}}$ is smaller than that of without RAG
$\hat{\alpha}$ with high probability (RHS of Equation 68), which
asymptotically approaches $1$ with a sufficiently large sizes of the
calibration set $N_{\text{cal}}$ and retrieved augmented examples
$N_{\text{rag}}$. (R2) In contrast to Theorem 1, the bound has no dependency
on distributions in the external knowledge base $r_{\text{ext}}^{(c)}$ since a
sufficiently large knowledge base can cover also rare examples. (R3) Compared
to Theorem 1, the bound also has no dependency on the distribution of the
calibration/test distribution $r_{\text{cal}}^{(c)}$, showing that a
sufficiently large external knowledge base can better generalize to unknown
test distributions. Additionally, the lower bound in Equation 68 is tighter
than that in Equation 5, which demonstrates the benefit of the large external
knowledge base.

##  Appendix H Proposition 4: Retrieval quality analysis under distribution
shifts

Under test-time distribution shifts, retrieval model quality declines. To
derive conformal generation risk, we first examine the lower bound of
retrieved positive examples.

######  Proposition 4 (Lower bound to the retrieved positive examples under
test-time distribution shifts).

Suppose that the potential test distribution ${\mathcal{Q}}$ is shifted from
the original test distribution ${\mathcal{D}}$ with bounded Hellinger distance
$\rho>0$. Consider the same setup as Proposition 3 and a large external
knowledge base where $N_{\text{ext}}>2\sqrt{2\ln
10}/\min_{c}r^{(c)}_{\text{ext}}$. We have:

$\normalsize\mathbb{E}\left[N_{\text{pos}}\right]\geq\dfrac{9}{10}N_{\text{rag}}\left(1-1.5N_{\text{ext}}V_{\text{rag}}(\rho)^{0.25\left(\min_{c}r^{(c)}_{\text{ext}}N_{\text{ext}}\right)}\right),\vspace{-.5em}$
(69)

where $V_{\text{rag}}(\rho):=m(\rho)V_{\text{rag}}$ and

$\displaystyle\vspace{-1em}V_{\text{rag}}(\rho):=m(\rho)V_{\text{rag}},\quad\text{where}\quad
m(\rho)=\underbrace{\left(\dfrac{\sqrt{-6\rho^{4}+12\rho^{2}+1}-4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}}{1-16\rho^{2}+8\rho^{4}}\right)^{-2}}_{\text{retrieval
model quality decay factor under distribution shifts}}.$

Proof sketch. We first formulate the expectation of similarity difference
between positive pairs and negative pairs
$\mathbb{E}[s_{\theta_{r}}(x,x^{+})-s_{\theta_{r}}(x,x^{-})]$ as a function of
the contrastive loss of the retrieval model $L_{\tau}$. Then, we apply
Chebyshev’s inequality to upper bound the failure probability
${\mathbb{P}}[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})]$ as a function of the
variance and expectation of the similarity difference. Considering the
distribution shifts, the variance and expectation bound can be derived via
Grammian bound as Weber et al. (2022). We then plug in the failure rate
corrected by distribution shifts and follow the proof structure of Proposition
3.

######  Remarks.

(R1) Different from Proposition 3, the quality of retrieval models under
distribution shifts is decreased from $V_{\text{rag}}$ to
$V_{\text{rag}}(\rho)$ with a linear decay factor $m(\rho)$. As we require
$V_{\text{rag}}(\rho)<1$ to ensure high retrieval quality, large distribution
shift radius $\rho$ must be compensated by small $V_{\text{rag}}$. This is
consistent with the existing observations that low-variance models can
generalize better under distribution shifts Lam (2016); Gotoh et al. (2018);
Namkoong & Duchi (2017). (R2) Compared to Proposition 3, Proposition 4 removes
the dependency on varying label portions $r^{(c)}_{\text{cal}}$ during
distribution shifts, as long as the size of external knowledge base is
sufficiently large $N_{\text{ext}}$ to offset the worst-case long-tail
distributions, a condition often met in practice with large knowledge bases.

###### Proof of Proposition 4.

Let ${\mathcal{D}}$ be the data distribution, which is also the training
distribution of the retrieval model and conformal calibration distribution.
Let ${\mathcal{Q}}$ be the test distribution where the test samples are drawn
from. ${\mathcal{Q}}$ is within Hellinger distance $\rho$ from the
distribution ${\mathcal{D}}$: $H({\mathcal{D}},{\mathcal{Q}})\leq\rho$.

For a sample $(x,y)\sim{\mathcal{D}}$, we denote
${\mathcal{D}}_{\text{ext}}^{+}(x)$, ${\mathcal{D}}_{\text{ext}}^{-}(x)$ be
the distribution of positive examples (with the same groundtruth output $y$)
and negative examples (with different groundtruth output to $y$) of sample $x$
in the external knowledge base. Then we can formulate the expectation of
contrastive loss of the retrieval model as:

$\displaystyle L_{\tau}$
$\displaystyle=\mathbb{E}_{x\sim{\mathcal{D}},x^{+}\sim{\mathcal{D}}^{+}_{\text{ext}}(x),x^{-}\sim{\mathcal{D}}^{-}_{\text{ext}}(x)}\left[{\mathcal{L}}_{\text{contrastive}}(x,x^{+},x^{-})\right]$
(70)
$\displaystyle=\mathbb{E}_{x\sim{\mathcal{D}},x^{+}\sim{\mathcal{D}}^{+}_{\text{ext}}(x),x^{-}\sim{\mathcal{D}}^{-}_{\text{ext}}(x)}\left[-\log\dfrac{\exp\left\\{s_{\theta}(x,x^{+})\right\\}}{\exp\left\\{s_{\theta}(x,x^{+})\right\\}+\exp\left\\{s_{\theta}(x,x^{-})\right\\}}\right].$

We can apply Chebyshev’s inequality Saw et al. (1984) to the random variable
$s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})$ and get the following:

$\displaystyle{\mathbb{P}}\left[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})\right]$
$\displaystyle={\mathbb{P}}_{x\sim{\mathcal{Q}},x^{+}\sim{\mathcal{D}}^{+}_{\text{ext}}(x),x^{-}\sim{\mathcal{D}}^{-}_{\text{ext}}(x)}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})<0\right]$
(71)
$\displaystyle\leq\dfrac{\mathbb{V}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]}{\mathbb{E}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]^{2}}.$
(72)

For ease of notation, we notate random variable
$S=s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})$. Then we have ${\mathbb{P}}[-2\leq
S\leq 2]=1$, and
$\mathbb{E}[S]\geq\underline{\mathbb{E}[S]}:=\dfrac{\exp\left\\{-L_{\tau}(\rho)\right\\}}{1-\exp\left\\{-L_{\tau}(\rho)\right\\}}$.
Note that ${\mathbb{P}}[0\leq S^{2}\leq 4]=1$, we have
$\mathbb{V}[S^{2}]\leq(4-0)^{2}/4=4$. Then by Equation 21, we have the
following:

$\displaystyle\mathbb{E}_{\mathcal{Q}}\left[S^{2}\right]$
$\displaystyle\leq\mathbb{E}_{\mathcal{D}}\left[S^{2}\right]+\rho^{2}(2-\rho^{2})\left(1-\mathbb{E}_{\mathcal{D}}\left[S^{2}\right]\right)+2\rho(1-\rho^{2})\sqrt{2-\rho^{2}}\sqrt{\mathbb{V}_{\mathcal{D}}\left[S^{2}\right]}$
(73)
$\displaystyle\leq(1-\rho^{2})^{2}\mathbb{E}_{\mathcal{D}}\left[S^{2}\right]+\rho^{2}(2-\rho^{2})+4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}.$
(74)

By applying the lower bound of expectation values in Theorem A.2 in Weber et
al. (2022),which is a straightforward variation of Equation 21, we have the
following:

$\mathbb{E}_{\mathcal{Q}}\left[S\right]\geq(1-\rho^{2})^{2}\mathbb{E}_{\mathcal{D}}\left[S\right]-2\rho(1-\rho^{2})\sqrt{2-\rho^{2}}\sqrt{\mathbb{V}_{\mathcal{D}}\left[S\right]}+\rho^{2}(2-\rho^{2})\dfrac{\mathbb{V}_{\mathcal{D}}\left[S\right]}{\mathbb{E}_{\mathcal{D}}\left[S\right]}.$
(75)

Since we assume that
$\mathbb{E}_{\mathcal{D}}\left[S\right]=\mathbb{E}_{\mathcal{D}}\left[s_{\theta}(x,x^{+})-s_{\theta}(x,x^{-})\right]>0$,
we have the following:

$\mathbb{E}_{\mathcal{Q}}\left[S\right]\geq(1-\rho^{2})^{2}\mathbb{E}_{\mathcal{D}}\left[S\right]-2\rho(1-\rho^{2})\sqrt{2-\rho^{2}}\sqrt{\mathbb{V}_{\mathcal{D}}\left[S\right]}.$
(76)

Combining Equations 74 and 76, we have the following:

$\displaystyle\dfrac{\mathbb{V}_{\mathcal{Q}}\left[S\right]}{\mathbb{E}_{\mathcal{Q}}\left[S\right]^{2}}$
$\displaystyle=\dfrac{\mathbb{E}_{\mathcal{Q}}\left[S^{2}\right]-\mathbb{E}_{\mathcal{Q}}\left[S\right]^{2}}{\mathbb{E}_{\mathcal{Q}}\left[S\right]^{2}}$
(77)
$\displaystyle\leq\dfrac{(1-\rho^{2})^{2}\left(\mathbb{V}_{\mathcal{D}}\left[S\right]+\mathbb{E}_{\mathcal{D}}\left[S\right]^{2}\right)+\rho^{2}(2-\rho^{2})+4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}}{\mathbb{E}_{\mathcal{Q}}\left[S\right]^{2}}-1$
(78)
$\displaystyle\leq\dfrac{(1-\rho^{2})^{2}\left(\mathbb{V}_{\mathcal{D}}\left[S\right]+\mathbb{E}_{\mathcal{D}}\left[S\right]^{2}\right)+\rho^{2}(2-\rho^{2})+4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}}{\left((1-\rho^{2})^{2}\mathbb{E}_{\mathcal{D}}\left[S\right]-2\rho(1-\rho^{2})\sqrt{2-\rho^{2}}\sqrt{\mathbb{V}_{\mathcal{D}}\left[S\right]}\right)^{2}}-1.$
(79)

Through some algebraic rearrangement, we can show that:

$\dfrac{\mathbb{V}_{\mathcal{Q}}\left[S\right]}{\mathbb{E}_{\mathcal{Q}}\left[S\right]^{2}}\leq
V_{\text{rag}}(\rho):=\dfrac{\mathbb{V}_{\mathcal{D}}\left[S\right]}{\mathbb{E}_{\mathcal{D}}\left[S\right]^{2}}\left(\dfrac{\sqrt{-6\rho^{4}+12\rho^{2}+1}-4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}}{1-16\rho^{2}+8\rho^{4}}\right)^{-2}.$
(80)

Therefore, one sufficient condition of $V_{\text{rag}}(\rho)<1$ is that:

$\displaystyle\sqrt{\mathbb{V}_{\mathcal{D}}\left[S\right]}$
$\displaystyle\leq\left(\dfrac{\sqrt{-6\rho^{4}+12\rho^{2}+1}-4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}}{1-16\rho^{2}+8\rho^{4}}\right)\mathbb{E}_{\mathcal{D}}\left[S\right]$
(81)
$\displaystyle=\left(\dfrac{\sqrt{-6\rho^{4}+12\rho^{2}+1}-4\rho(1-\rho^{2})\sqrt{2-\rho^{2}}}{1-16\rho^{2}+8\rho^{4}}\right)\ln\dfrac{\exp\left\\{-L_{\tau}\right\\}}{1-\exp\left\\{-L_{\tau}\right\\}}$
(82)

Then, we follow a similar procedure as the proof of Proposition 3 to analyze
the expected retrieved positive examples. We first focus on one demonstration
example $Z_{r}$ retrieved by $s_{\theta}(\cdot,\cdot)$. According to the
retrieval mechanism, the example $Z_{r}$ has the highest similarity (measured
by $s_{\theta}(\cdot,\cdot)$) to the query sample $Z_{q}$. Recall that
$r^{(c)}_{\text{test}}({\mathcal{Q}})$ and $r^{(c)}_{\text{ext}}$ be the event
probability of the $c$-th category in the categorical test distribution (i.e.,
${\mathcal{Q}}$) and categorical external knowledge distribution. Let
${\bm{r}}_{\text{ext}}=\left[r^{(1)}_{\text{ext}},r^{(2)}_{\text{ext}},...,r^{(C)}_{\text{ext}}\right]$.
Since we only have $N_{\text{ext}}$ finite sample drawn from
${\mathcal{D}}_{\text{ext}}$ in the external knowledge base in practice, we
notate the empirical categorical portions as
$\hat{{\bm{q}}}_{\text{ext}}=\left[\hat{r}^{(1)}_{\text{ext}},\hat{r}^{(2)}_{\text{ext}},...,\hat{r}^{(C)}_{\text{ext}}\right]$,
where $\hat{r}^{(c)}_{\text{ext}}~{}(c\in\\{1,..,C\\})$ represents the portion
of samples with grountruth output $c$ in the external knowledge base. Then we
can apply the concentration bound of categorical distribution as Agrawal & Jia
(2017):

$\displaystyle{\mathbb{P}}\left[\|\hat{{\bm{r}}}_{\text{ext}}-{\bm{r}}_{\text{ext}}\|_{1}\geq\dfrac{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}{N_{\text{ext}}}\right]\leq\delta_{\text{ext}},$
(83)

where $\delta_{\text{ext}}>0$ represents the confidence level of the tail
bound. Then we can upper bound the probability that the groundtruth output
$g(Z_{r})$ of the retrieved sample $Z_{r}$ is not equal to the groundtruth
output of the query sample $g(Z_{q})$ as the following:

$\displaystyle{\mathbb{P}}\left[g(Z_{r})\notin g(Z_{q})\right]$
$\displaystyle={\mathbb{P}}_{Z_{q}\sim{\mathcal{D}}}\left[g(Z_{r})\notin
g(Z_{q})\left|s_{\theta}(Z_{q},Z_{r})\geq\max_{z\in{\mathcal{D}}_{\text{ext}}}s_{\theta}(z,Z_{q})\right.\right]$
(84)
$\displaystyle={\mathbb{P}}_{Z_{q}\sim{\mathcal{D}}}\left[\max_{Z^{-}\in{\mathcal{D}}^{-}_{\text{ext}}(Z_{q})}s_{\theta}(Z^{-},Z_{q})\geq\max_{Z^{+}\in{\mathcal{D}}^{+}_{\text{ext}}(Z_{q})}s_{\theta}(Z^{+},Z_{q})\right]$
(85)
$\displaystyle={\mathbb{P}}_{Z_{q}\sim{\mathcal{D}}}\left[s_{\theta}(Z^{-},Z_{q})\geq
s_{\theta}(Z^{+},Z_{q}),~{}~{}\forall
Z^{+}\in{\mathcal{D}}^{+}_{\text{ext}}(Z_{q}),~{}\exists
Z^{-}\in{\mathcal{D}}^{-}_{\text{ext}}(Z_{q})\right]$ (86)
$\displaystyle\leq\max_{\mathcal{Q}}\sum_{c=1}^{C}r^{(c)}_{\text{test}}({\mathcal{Q}})\left(1-r^{(c)}_{\text{ext}}\right)N_{\text{ext}}{\mathbb{P}}\left[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})\right]^{N_{\text{ext}}r^{(c)}_{\text{ext}}},$
(87)

where Equation 87 is derived by applying the union bound. Considering finite-
sample error of categorical distribution in Equation 83 and combining
Equations 72 and 80, we finally have:

$\displaystyle{\mathbb{P}}\left[g(Z_{r})\notin g(Z_{q})\right]$
$\displaystyle\leq\max_{\mathcal{Q}}\sum_{c=1}^{C}r^{(c)}_{\text{test}}({\mathcal{Q}})\left(1-r^{(c)}_{\text{ext}}\right)N_{\text{ext}}{\mathbb{P}}\left[s_{\theta}(x,x^{+})<s_{\theta}(x,x^{-})\right]^{N_{\text{ext}}r^{(c)}_{\text{ext}}}$
(88)
$\displaystyle\leq\max_{\mathcal{Q}}\sum_{c=1}^{C}r^{(c)}_{\text{test}}({\mathcal{Q}})\left(1-r^{(c)}_{\text{ext}}+\dfrac{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}{N_{\text{ext}}}\right)N_{\text{ext}}V_{\text{rag}}(\rho)^{0.5N_{\text{ext}}\left(r^{(c)}_{\text{ext}}-{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}/{N_{\text{ext}}}\right)}$
(89)

Since we assume that the retrieval model retrieves samples identically from
the external knowledge base, the number of retrieved positive examples
$N_{\text{pos}}$ follows a Binomial distribution with $N_{\text{rag}}$ trials
and failure rate in Equation 89. Therefore, we can lower bound the expectation
of $N_{\text{pos}}$ as the following:

$\displaystyle\mathbb{E}\left[N_{\text{pos}}\right]$
$\displaystyle\geq\min_{\mathcal{Q}}N_{\text{rag}}\left(1-\delta_{\text{ext}}\right)\left(1-\sum_{c=1}^{C}r^{(c)}_{\text{test}}({\mathcal{Q}})\left(1-r^{(c)}_{\text{ext}}+\dfrac{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}{N_{\text{ext}}}\right)N_{\text{ext}}V_{\text{rag}}(\rho)^{0.5N_{\text{ext}}\left(r^{(c)}_{\text{ext}}-{\sqrt{2\ln{(1/\delta_{\text{ext}})}}}/{N_{\text{ext}}}\right)}\right)$
(90)

which holds for any $\delta_{\text{ext}}>0$. Therefore, letting
$\delta_{\text{ext}}=0.1$, we can finally derive the following:

$\displaystyle\mathbb{E}\left[N_{\text{pos}}\right]$
$\displaystyle\geq\min_{\mathcal{Q}}\dfrac{9}{10}N_{\text{rag}}\left(1-\sum_{c=1}^{C}r^{(c)}_{\text{test}}({\mathcal{Q}})\left(N_{\text{ext}}-r^{(c)}_{\text{ext}}N_{\text{ext}}+{\sqrt{2\ln{10}}}\right)V_{\text{rag}}(\rho)^{0.5\left(r^{(c)}_{\text{ext}}N_{\text{ext}}-{\sqrt{2\ln{10}}}\right)}\right)$
(91)
$\displaystyle\geq\dfrac{9}{10}N_{\text{rag}}\left(1-1.5N_{\text{ext}}V_{\text{rag}}(\rho)^{0.25\left(\min_{c}r^{(c)}_{\text{ext}}N_{\text{ext}}\right)}\right),$
(92)

with a sample size in the external knowledge base such that
$N_{\text{ext}}>2\sqrt{2\ln 10}/\min_{c}r^{(c)}_{\text{ext}}$.

∎

##  Appendix I Proofs and detailed remarks in Section 5

###  I.1 Proof and detailed remark of Theorem 2

######  Remarks.

(R1) Different from Proposition 3, the quality of retrieval models under
distribution shifts is decreased from $V_{\text{rag}}$ to