No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Models

## Abstract

Abstract Generative models have shown impressive capabilities in synthesizing high-quality outputs across various domains. However, a persistent challenge is the occurrence of “hallucinations”, where the model produces outputs that are plausible but invalid.
While empirical strategies have been explored to mitigate this issue, a rigorous theoretical understanding remains elusive. In this paper, we develop a theoretical framework to analyze the learnability of non-hallucinating generative models from a learning-theoretic perspective. Our results reveal that non-hallucinating learning is statistically impossible when relying solely on the training dataset, even for a hypothesis class of size two and when the entire training set is truthful. To overcome these limitations, we show that incorporating inductive biases aligned with the actual facts into the learning process is essential. We provide a systematic approach to achieve this by restricting the facts set to a concept class of finite VC-dimension and demonstrate its effectiveness under various learning paradigms. Although our findings are primarily conceptual, they represent a first step towards a principled approach to addressing hallucinations in learning generative models.

## 1 Introduction

Generative models have emerged as powerful tools with applications in virtually all socio-economic enterprises. At a high level, these techniques integrate large amounts of data to provide good statistical concentration and build on the resulting mixture of embeddings to produce incredible generative models of text, images, video, mechanical drawings, computer programs, mathematical proofs, and others. However, there is increasing recognition of “hallucinations” in generative models, that ultimately limit their utility in critical application settings, such as those that have correctness, accuracy, or safety constraints. Hallucinations correspond to plausible but invalid, incorrect, or misleading outputs. The key challenge in mitigating hallucinations is that there are often no characterizations of the space of “valid”, “correct”, or “logical” assertions, making it difficult to assess hallucinations. A common retort is that generative models should generate hypotheses that are grounded in training data. However, this assertion limits the rich potential of generative systems to that of powerful information retrieval (IR) systems, rather than those capable of new insight not grounded in training data. This tension between the desired ability of AI models to generate new hypothesis, while not generating “falsifiable” artifacts, without a well characterized notion of “true” artifacts represents the key underlying challenge of mitigating hallucinations.

Although many methods have been proposed for addressing hallucinations, such as factual data enhancement (Dziri et al., ), hallucination detection (Manakul et al., ), and fine-tuning with human feedback (Ouyang et al., ), their performance has primarily been validated through empirical studies, and their suitability for critical applications remains unresolved. This strongly motivates the study of hallucination and its relation to model performance from a general mathematical perspective.
This paper advances the state of the art by developing a theoretical framework to understand hallucinations in generative models from a learning-theoretic perspective. We establish a rigorous theoretical foundation for analyzing the *learnability* of non-hallucinating generative models under various learning paradigms. Specifically, we characterize the conditions under which non-hallucinating learning is possible, identify the appropriate learning rules, and determine the corresponding sample complexity required to achieve learnability.

We consider the following formal setup: let $\mathcal{X}$ be an instance space; for example, in the context of language models, $\mathcal{X}$ represents the set of *all* sentences (factual or otherwise). We denote by $\mathcal{T}\subset\mathcal{X}$ a set of *facts*, which may correspond to a subset of sentences that describe true statements relevant to the task at hand. Throughout this paper, we will treat the set $\mathcal{T}$ abstractly. A generative model is represented by a distribution $p\in\Delta(\mathcal{X})$, where $\Delta(\mathcal{X})$ is the set of all probability distributions over $\mathcal{X}$ (^1^11Although in practice the model may also depend on certain *prompts*, this can be incorporated via *conditional* sampling. For clarity of exposition, we consider this simplified version as in Kalai & Vempala ().). We define the *hallucination rate* of $p$ w.r.t. $\mathcal{T}$ as:

$$ $\mathsf{hall}(p,\mathcal{T})=\mathrm{Pr}_{\mathbf{x}\sim p}[\mathbf{x}\not\in \mathcal{T}].$ (1) $$

That is, hallucination rate measures how much probability mass a generative model assigns to *non-fact* instances.
A data generation mechanism is modeled as a distribution $q\in\Delta(\mathcal{X})$, which we also refer to as a *demonstrator*. We say the demonstrator $q$ is *faithful* w.r.t. the facts set $\mathcal{T}$ if $\mathsf{hall}(q,\mathcal{T})=0$, i.e., the demonstrator *does not* produce non-fact samples. A learning rule is a function $\Phi:\mathcal{X}^{*}\rightarrow\Delta(\mathcal{X})$. For any given $\epsilon,\delta>0$, we say the learner $\Phi$ *non-hallucinatingly learns* $(q,\mathcal{T})$ with sample complexity $n$ at hallucination rate $\epsilon$ and confidence $\delta$, if:

$$ $\mathrm{Pr}_{\mathbf{x}^{n}\sim q}\left[\mathsf{hall}(\Phi(\mathbf{x}^{n}), \mathcal{T})\geq\epsilon\right]\leq\delta,$ (2) $$

where the *training* set $\mathbf{x}^{n}:=\{\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\}$ is sampled $i.i.d.$ from the demonstrator $q$.

It is crucial to note that the learner $\Phi$, in general, *does not* know the tuple $(q,\mathcal{T})$, and the only available information comes from the training set $\mathbf{x}^{n}$. However, the construction of $\Phi$ can incorporate *prior* information about $(q,\mathcal{T})$ (i.e., *inductive bias*) into the learning process. Throughout the paper, we assume that $q$ is *faithful* w.r.t. $\mathcal{T}$. That is, we aim to characterize the non-hallucinating learnability in the *cleanest* scenario where the entire training set is truthful. The main goal of this paper is to address the following *meta*-problem:

> *What structural assumptions on the tuple $(q,\mathcal{T})$ are necessary to achieve non-hallucinating learnability, even when the training set is entirely truthful?*

#### Proper v.s. Improper Learners.

We distinguish two learning paradigms – proper and improper learning. Let $\mathcal{P}\subset\Delta(\mathcal{X})$ be a *hypothesis* class; for instance, $\mathcal{P}$ may represent the class of all distributions specified by a transformer architecture with different parameters. We say a learning rule $\Phi$ is *proper* w.r.t. $\mathcal{P}$ if $\mathsf{img}(\Phi)\subset\mathcal{P}$, that is the learner must produce a model *within* the hypothesis class. In the proper learning case, learnability also depends on the structure of $\mathcal{P}$. Otherwise, we say that the leaner $\Phi$ is *improper*; i.e., its outcome is completely *unconstrained*, or equivalently, we take $\mathcal{P}:=\Delta(\mathcal{X})$. We demonstrate in this paper that the characterization of proper and improper learnability are fundamentally different for non-hallucinate learning of generative models.

We now summarize our main contributions as follows:

- •
Agnostic proper learning is impossible. Clearly, a natural question one may ask is why do we need assumptions on the tuple $(q,\mathcal{T})$ at all. This is a valid argument; for instance, in the context of PAC learning, we do not need to make any specific assumptions on the data generation process. Instead, we quantify the goodness of the learner by comparing its performance to the best hypothesis in a hypothesis class $\mathcal{P}$. Learnability then reduces to characterizing the complexity of $\mathcal{P}$. We show in Theorem 1 that, perhaps surprisingly, such an *agnostic* competitive guarantee is *impossible* for non-hallucinating learning, even for a hypothesis class with only two elements, if the learner is proper. Our proof follows a probabilistic construction of hard instances of $(q,\mathcal{T})$, which also applies to other natural variants of non-hallucinating learning and is of independent interest.
- •
Improper learning is possible and generalizes under VC concept classes. Our second main result is a characterization of non-hallucinating learnability with *improper* learners. It is easy to observe that a naïve improper learner that produces the *empirical* distribution over the training set $\mathbf{x}^{n}$ never hallucinates (provided the demonstrator is faithful). This is clearly undesirable, since the produced model does not *generalize*. To resolve this issue, we introduce a new measure of *generalizability*, by requiring that the model contain as much *information* as the demonstrator, in addition to being non-hallucinating. We show in Theorem 2 that if the facts set $\mathcal{T}$ lies in a *concept* class $\mathcal{C}$ of finite VC-dimension, then non-hallucinating is possible with an improper learner that also generalizes to the amount of information of the demonstrator. We further show in Theorem 3 a matching sample complexity lower bound on the VC-dimension for the *worst-case* concept classes.
- •
Proper learning can be hard even with VC concept class. Finally, we address the case of non-hallucinating learning with *proper* learners. We show in Example 3 a hypothesis class $\mathcal{P}$ and concept class $\mathcal{C}$ that are of size two, yet any *proper* learner must hallucinate. We then identify a sufficient condition on the triplet $(q,\mathcal{C},\mathcal{P})$ in Theorem 4 that allows non-hallucinating learning with proper learner, which is also necessary for certain cases.

#### Interpretation.

Our results demonstrates that non-hallucinating learning is statistically *impossible* by solely leveraging the training data set at hand, even if it is completely truthful. Therefore, to reduce hallucination in the learned model, one must incorporate certain *inductive biases* that depend on the facts set itself. This aligns with practical approaches, such as the *post-training* process that incorporates human feedback (Achiam et al., ). Our work provides a systematic approach to achieving this by restricting the facts set to a *concept* class of finite VC-dimension. Although our result is primarily conceptual, it serves as the first step towards a *principled* approach to addressing hallucination in generative models.

### 1.1 Related work

Our work is related to the recent theoretical investigation in Kalai & Vempala (), which demonstrates that under certain regularity conditions, a model that is well *calibrated* must hallucinate, highlighting the importance of incorporating “factual information” into the learning process. Other impossibility results have also being reported very recently from a *computability* point of view, such as Xu et al. (); Banerjee et al. (). While our impossibility results are in the same spirit, our primary focus is to characterize the *minimal* assumptions under which non-hallucinating learning is statistically *possible*. Moreover, our formulation and results are grounded in learning theory (Shalev-Shwartz & Ben-David, ), where we treat the facts set itself as a research object, rather than adding ad-hoc constraints. This offers more flexibility in incorporating *domain-specific* factual constraints, instead of resolving hallucination in a “universal” sense. There has been extensive empirical investigation on understanding and addressing hallucinations, such as factual data enhancement (Dziri et al., ), hallucination detection (Manakul et al., ), and fine-tuning with human feedback (Ouyang et al., ). We refer to surveys by Huang et al. (); Ji et al. (); Zhang et al. () and the references in Kalai & Vempala () for more extensive discussions. Our work complements these investigations by providing a *principled view* aimed at understanding hallucination in learning generative models. Technically, our formulation of non-hallucinating learnability is related to *distribution PAC learning*, as investigated in Ashtiani et al. (); Bousquet et al. (; ). Our lower bounding techniques are rooted in information-theoretical methods, such as Le Cam’s two-point method and Fan’s inequality (Polyanskiy & Wu, ).

## 2 Preliminaries

We review in this section some notations and concepts from the classical *distribution learning* literature, and highlight some immediate connections with our *non-hallucinating* learning paradigm. Let $\mathcal{X}$ be an instance space, and $\mathcal{P}\subset\Delta(\mathcal{X})$ be a hypothesis class. There exists some (unknown) ground truth distribution $q\in\Delta(\mathcal{X})$ (not necessarily in $\mathcal{P}$) that generates a sample $\mathbf{x}^{n}$ i.i.d. from $q$. The *distribution PAC learning* problem aims to find a learning rule $\Phi$ so that the produced distribution $\hat{p}_{n}:=\Phi(\mathbf{x}^{n})$ satisfies (for some $\alpha,\epsilon>0$):

$$ $\|q-\hat{p}_{n}\|_{\mathsf{TV}}\leq\alpha\inf_{p\in\mathcal{P}}\|q-p\|_{ \mathsf{TV}}+\epsilon,$ (3) $$

with probability $\geq 1-\delta$ over $\mathbf{x}^{n}\sim q$.

A hypothesis class $\mathcal{P}$ is said to be $\alpha$-agnostic PAC learnable if there exists a learning rule $\Phi$ such that for any $\epsilon,\delta>0$ there exists a number $n$ (sample size) such that, for *any* distribution $q$, equation (3) holds. It can be shown (see e.g. Bousquet et al. ()) that *any finite* hypothesis class $\mathcal{P}$ is $3$-agnostic learnable for *proper* learners. Intuitively, agnostic (proper) PAC learning ensures that the learned distribution’s total variation distance to the ground truth $q$ is as close as possible to the best hypothesis in $\mathcal{P}$ that minimizes this distance.

For the *non-hallucinating* learning paradigm investigated in this paper, we need additionally an (unknown) *facts set* $\mathcal{T}$ such that the produced model $\hat{p}_{n}$ has a small hallucination rate $\mathsf{hall}(\hat{p}_{n},\mathcal{T})$ as in (1). Clearly, if $q$ is *realizable* w.r.t. $\mathcal{P}$, i.e., $\inf_{p\in\mathcal{P}}\|q-p\|_{\mathsf{TV}}=0$, then $\alpha$-agnostic PAC learning implies non-hallucinating learning, as demonstrated in the following simple fact:

###### Fact 1 (Realizable learning of $q$ implies non-hallucinate learning) .

For any facts set $\mathcal{T}$ and any faithful demonstrator $q$ w.r.t. $\mathcal{T}$, if there exists a learner $\Phi$ such that w.p. $\geq 1-\delta$ over $\mathbf{x}^{n}\sim q$ we have
$\|\Phi(\mathbf{x}^{n})-q\|_{\mathsf{TV}}\leq\epsilon,$
then w.p. $\geq 1-\delta$ over $\mathbf{x}^{n}\sim q$ the following holds:
$\mathsf{hall}(\Phi(\mathbf{x}^{n}),\mathcal{T})\leq\epsilon.$

###### Proof.

We have
$\|\Phi(\mathbf{x}^{n})-q\|_{\mathsf{TV}}=\sup_{A\subset\mathcal{X}}|\Phi(
\mathbf{x}^{n})[A]-q[A]|\leq\epsilon.$
Therefore, taking $A:=\bar{\mathcal{T}}$ we have
$\mathsf{hall}(\Phi(\mathbf{x}^{n}),\mathcal{T})\leq q[\bar{\mathcal{T}}]+
\epsilon=\epsilon$, since $q[\bar{\mathcal{T}}]=\mathsf{hall}(q,\mathcal{T})=0$ due to faithfulness.
∎

Fact 1 demonstrates that if the learned distribution is $\epsilon$-close to a faithful demonstrator $q$ under total variation distance, then $\Phi$ is guaranteed to be non-hallucinating with a hallucination rate upper bounded by $\epsilon$. At first glance, this may suggest that non-hallucinating learning is easier than distribution PAC learning. However, it is important to note that the requirement for the learned model to be close to the *ground truth* distribution $q$ is rather strong. This necessitates that: (i) the model class correctly approximates the ground truth distribution, and (ii) there are sufficient training samples to enable the learned model to generalize. Neither of these requirements is guaranteed or verifiable in practice, since the ground truth distribution $q$ is *unknown*.

In fact, as we will show in the following sections, (agnostic) learning of the demonstration distribution $q$ is neither sufficient nor necessary to achieve non-hallucinating learning.

###### Fact 1 (Realizable learning of q 𝑞 q italic_q implies non-hallucinate learning) .

###### Proof.

## 3 Impossibility Results

In this section, we establish several *impossibility* results for certain natural formulations of *agnostic* (proper) non-hallucinating learning. Analogous to the $\alpha$-agnostic (distribution) PAC learning formulation, one may consider the following definition:

###### Definition 1 ( $\alpha$ -agnostic non-hallucinating learning) .

A hypothesis class $\mathcal{P}\subset\Delta(\mathcal{X})$ is *$\alpha$-agnostic non-hallucinating* learnable if for some $\alpha>0$ there exists a proper learner $\Phi$ such that for any given $\epsilon,\delta>0$, there exists a number $n$, such that for any facts set $\mathcal{T}$ and faithful-demonstrator $q$ w.r.t. $\mathcal{T}$

$$ $\mathrm{Pr}_{\mathbf{x}^{n}\overset{i.i.d.}{\sim}q}\left[\mathsf{hall}(\Phi( \mathbf{x}^{n}),\mathcal{T})-\alpha\inf_{p\in\mathcal{P}}\mathsf{hall}(p, \mathcal{T})\geq\epsilon\right]\leq\delta.$ $$

Intuitively, $\alpha$-agnostic non-hallucinating learnability requires that w.h.p., the learner produce a distribution within the class $\mathcal{P}$ that has hallucination rate not much higher than the minimal achievable hallucination rate of $\mathcal{P}$, *regardless* of how the facts set $\mathcal{T}$ and demonstrator $q$ are chosen. It is crucial to note that we do not require the learned distribution to be close to the demonstrator $q$ under total variation. Although this may appear to be a much weaker condition than learning the distribution $q$ itself, the following example demonstrates that it is *impossible* even for a hypothesis class with two elements and the minimal achievable hallucination rate is 0 0.

###### Example 1 .

Let $A$, $A_{1}$, and $A_{2}$ be disjoint non-empty sets. We define $p_{1}$ and $p_{2}$ to be any distributions supported over $A_{1}$ and $A_{2}$, respectively. Take $\mathcal{P}:=\{p_{1},p_{2}\}$ and $q$ to be any distribution supported over $A$. Now, for any given learner $\Phi$ and sample size $n$, $\Phi$ must produce $\hat{p}_{n}\in\mathcal{P}$. Therefore, w.p. $\geq\frac{1}{2}$ over the sample $\mathbf{x}^{n}\sim q$, it will select $\hat{p}_{n}:=p_{i}$ for some $i\in\{1,2\}$. We now (adversarially) select the facts set $\mathcal{T}:=A\cup A_{3-i}$. It is easy to verify that: (1) $q$ is faithful w.r.t. $\mathcal{T}$; (2) $\mathsf{hall}(\hat{p}_{n},\mathcal{T})=1$; and (3) $\inf_{p\in\mathcal{P}}\mathsf{hall}(p,\mathcal{T})=0$. This implies that the learner $\Phi$ cannot satisfy Definition 1 for all $\epsilon<1$, $\delta<\frac{1}{2}$ and $\alpha>0$. Since the learner $\Phi$ is selected arbitrarily, the class $\mathcal{P}$ is *not* $\alpha$-agnostic non-hallucinating learnable for all $\alpha>0$.

We mentioned in Section 2 that any *finite* hypothesis class is $3$-agnostic (proper) PAC learnable but Example 1 demonstrates a striking distinction between the agnostic distribution PAC learning and the agnostic *non-hallucinating* learning.

One may noticed that Example 1 is fairly pathological, since the constructed distribution $q$ is supported *outside* of the support of $p_{1}$ and $p_{2}$. Therefore, in effect, it provides no information for distinguishing between $p_{1}$ and $p_{2}$. For this reason, we introduce the following refined definition of hallucination rate *relative* to $q$.

###### Definition 2 (Relative Hallucination Rate) .

For any given distributions $p,q$, the $\epsilon$-relative hallucination rate of $p$ w.r.t. $q$ is defined as:

$$ $\mathsf{hall}_{\epsilon}(p,q)=\sup_{A\subset\mathcal{X},q[A]\leq\epsilon}p[A].$ $$

Intuitively, the *relative* hallucination rate $\mathsf{hall}_{\epsilon}(p,q)$ measures the maximum probability that $p$ assigns to a set where the distribution $q$ has a small mass. In other words, the distribution $p$ is non-hallucinating relative to $q$ if every *rare* event under $q$ is also rare under $p$. Observe that, if $q$ is faithful w.r.t. some facts set $\mathcal{T}$, then:

$$ $\forall\epsilon\geq 0,~{}\mathsf{hall}(p,\mathcal{T})\leq\mathsf{hall}_{ \epsilon}(p,q).$ (4) $$

Therefore, a small relative hallucination rate automatically implies small (absolute) hallucination rate as in (1). However, the converse is generally not true. To see this, consider Example 1, we know that $\inf_{p\in\mathcal{P}}\mathsf{hall}(p,\mathcal{T})=0$ while $\inf_{p\in\mathcal{P}}\mathsf{hall}_{\epsilon}(p,q)=1$ for all $\epsilon\geq 0$, thus the impossibility result implied therein no longer holds. It is interesting to note that the relative hallucination rate can be naturally bounded by the notion of $\sigma$-smoothness (Haghtalab et al., ). We say $p$ is $\sigma$-smooth w.r.t. $q$ if $\forall A\subset\mathcal{X}$ we have $p[A]\leq\frac{1}{\sigma}q[A]$, therefore,
$\mathsf{hall}_{\epsilon}(p,q)\leq\frac{\epsilon}{\sigma}$ for all $\epsilon\geq 0$.

We show in the following theorem that $\alpha$-agnostic-non-hallucinating learning is *impossible* for all given $\alpha>0$ even for the *relative* hallucination rate and for a hypothesis class of size $2$.

###### Theorem 1 (Agnostic proper non-hallucinating learning is impossible) .

There exists a hypothesis class $\mathcal{P}$ of size $2$ such that for *any proper* learning rule $\Phi$, parameter $\delta\leq\frac{1}{3}$, and any sample size $n$, there exists a tuple $(q,\mathcal{T})$ such that for all $\epsilon<\frac{1}{2}$, with probability $>\delta$ over $\mathbf{x}^{n}\sim q$:

- 1.
$q$ is faithful w.r.t. $\mathcal{T}$;
- 2.
$\inf_{p\in\mathcal{P}}\mathsf{hall}(p,\mathcal{T})\leq\inf_{p\in\mathcal{P}}
\mathsf{hall}_{\epsilon}(p,q)\leq 2\epsilon$, i.e., there exists *non-hallucinating* $p\in\mathcal{P}$;
- 3.
$\mathsf{hall}_{\epsilon}(\Phi(\mathbf{x}^{n}),q)\geq\mathsf{hall}(\Phi(\mathbf
{x}^{n}),\mathcal{T})=1$, i.e., the *learned* model hallucinates.

###### Proof.

Let $p_{1}$ be the uniform distribution over $A_{1}:=[0,0.5]$, $p_{2}$ be uniform over $A_{2}:=[0.5,1]$ and $\mathcal{P}=\{p_{1},p_{2}\}$, where $[a,b]$ denotes for the *interval* in the real line from $a$ to $b$.
We now describe a way of selecting $(q,\mathcal{T})$ satisfying the conditions in the theorem statement. To do so, we use a *probabilistic* argument. Let $\mu_{1}$ and $\mu_{2}$ be two distributions over the tuple $(q,\mathcal{T})$ such that:

- 1.
For distribution $\mu_{1}$, we select the facts set $\mathcal{T}:=A_{1}\cup\tilde{A}_{2}$ where $\tilde{A}_{2}$ is (a discrete set) sampled $i.i.d.$ uniformly from $A_{2}$ with $|\tilde{A}_{2}|\gg 2n^{2}$. After generating $\mathcal{T}$, we take $q=\frac{1}{2}\mathsf{Uni}(A_{1})+\frac{1}{2}\mathsf{Uni}(\tilde{A}_{2})$, i.e., w.p. $\frac{1}{2}$ uniform over $A_{1}$ and w.p. $\frac{1}{2}$ uniform over $\tilde{A}_{2}$;
- 2.
For distribution $\mu_{2}$, we select the facts set $\mathcal{T}:=A_{2}\cup\tilde{A}_{1}$ where $\tilde{A}_{1}$ is (a discrete set) sampled $i.i.d.$ uniformly from $A_{1}$ with $|\tilde{A}_{1}|\gg 2n^{2}$. After generating $\mathcal{T}$, we take $q=\frac{1}{2}\mathsf{Uni}(A_{2})+\frac{1}{2}\mathsf{Uni}(\tilde{A}_{1})$ interpreted as above.

By construction, we know that the demonstrator $q$ is completely faithful w.r.t. $\mathcal{T}$, and for any $\epsilon<\frac{1}{2}$, the following key properties hold:

- 1.
If $(q,\mathcal{T})\sim\mu_{1}$ then $\mathsf{hall}(p_{1},\mathcal{T})\leq\mathsf{hall}_{\epsilon}(p_{1},q)\leq 2\epsilon$ and $\mathsf{hall}_{\epsilon}(p_{2},q)\geq\mathsf{hall}(p_{2},\mathcal{T})=1$;
- 2.
If $(q,\mathcal{T})\sim\mu_{2}$ then $\mathsf{hall}(p_{2},\mathcal{T})\leq\mathsf{hall}_{\epsilon}(p_{2},q)\leq 2\epsilon$ and $\mathsf{hall}_{\epsilon}(p_{1},q)\geq\mathsf{hall}(p_{1},\mathcal{T})=1$.

Therefore, the first two conditions in the theorem statement are satisfied.

We take now any $\delta\leq\frac{1}{3}$ and assume for now that condition 3 *does not* hold. We have if $(q,\mathcal{T})\sim\mu_{1}$ then $\Phi(\mathbf{x}^{n})=p_{1}$ happens w.p. $\geq 1-\delta\geq\frac{2}{3}$ over the randomness $\mathbf{x}^{n}\sim q$; else if $(q,\mathcal{T})\sim\mu_{2}$ then $\Phi(\mathbf{x}^{n})=p_{1}$ happens w.p. $\leq\delta\leq\frac{1}{3}$ over the randomness $\mathbf{x}^{n}\sim q$ (recall that the learner $\Phi$ must output either $p_{1}$ or $p_{2}$ since it is assumed to be *proper*). For $i\in\{1,2\}$, we define the *mixture* distribution $\nu_{i}$ over $\mathcal{X}^{n}$ as described by the outcome of the following Markov process:

$$ $\mu_{i}\sim(q,\mathcal{T})\overset{i.i.d.\text{ from }q}{\sim}\mathbf{x}^{n}.$ $$

Therefore, we have

$$ $\|\nu_{1}-\nu_{2}\|_{\mathsf{TV}}=\sup_{E\subset\mathcal{X}^{n}}\nu_{1}(E)-\nu _{2}(E)\geq\nu_{1}(E^{\prime})-\nu_{2}(E^{\prime})\geq\frac{2}{3}-\frac{1}{3}= \frac{1}{3},$ $$

where $E^{\prime}:=\{\mathbf{x}^{n}\in\mathcal{X}^{n}:\Phi(\mathbf{x}^{n})=p_{1}\}$ and the second inequality follows by discussion above.

Note that, the randomness of $\nu_{i}$ has two parts: w.p. $\frac{1}{2}$ the sample is uniform over $A_{i}$ and w.p. $\frac{1}{2}$ the sample is uniform over $\tilde{A}_{3-i}$. The set $\tilde{A}_{3-i}$ is selected uniformly from $A_{3-i}$ and is of size $\gg 2n^{2}$. Therefore, conditioning on the event that there is *no repetition* in sample $\mathbf{x}^{n}$, the distribution of $\mathbf{x}^{n}\sim\nu_{i}$ restricted on $A_{3-i}$ is *exactly* the same as sampling $i.i.d.$ uniformly from $A_{3-i}$. Let $E$ be the event over $\mathcal{X}^{n}$ so that $\mathbf{x}^{n}\in E$ has no repetition. We have:

$$ $\|\nu_{1}(\cdot\mid E)-\nu_{2}(\cdot\mid E)\|_{\mathsf{TV}}=0.$ $$

Since we have selected the size $|\tilde{A}_{i}|\gg 2n^{2}$ for $i\in\{1,2\}$, by the *birthday paradox* (Katz & Lindell, , Lemma A.9), we have
$\nu_{1}(E)=\nu_{2}(E)\geq 1-\frac{1}{4}=\frac{3}{4}.$
This implies that:

$$ $\displaystyle\|\nu_{1}-\nu_{2}\|_{\mathsf{TV}}$ $\displaystyle=\nu_{1}(B)-\nu_{2}(B),~{}\text{for some }B\subset\mathcal{X}^{n}$ $\displaystyle=\nu_{1}(B\cap E)-\nu_{2}(B\cap E)+\nu_{1}(B\cap\bar{E})-\nu_{2}( B\cap\bar{E})$ $\displaystyle=\nu_{1}(E)(\nu_{1}(B\mid E)-\nu_{2}(B\mid E))+\nu_{1}(\bar{E})( \nu_{1}(B\mid\bar{E})-\nu_{2}(B\mid\bar{E})),~{}\text{since }\nu_{1}(E)=\nu_{2 }(E)$ $\displaystyle\leq\nu_{1}(E)\|\nu_{1}(\cdot\mid E)-\nu_{2}(\cdot\mid E)\|_{ \mathsf{TV}}+\nu_{1}(\bar{E})\|\nu_{1}(\cdot\mid\bar{E})-\nu_{2}(\cdot\mid\bar {E})\|_{\mathsf{TV}}$ $\displaystyle\leq\nu_{1}(\bar{E})<1-\frac{3}{4}<\frac{1}{3}.$ $$

This contradicts to our previous conclusion that $\|\nu_{1}-\nu_{2}\|_{\mathsf{TV}}\geq\frac{1}{3}$, thus the presumption that condition 3 does not hold is *not true*. Therefore, proof of theorem is complited.
∎

Note that, although Theorem 1 is proved only for a specifically constructed pair of distributions, the arguments can be extended to *any* pair of distributions that have sufficiently separated densities, provided the distributions are smooth enough to allow for sufficiently long *non-repetitive* samples.

Theorem 1 implies the following corollary that strengthens Example 1, which shows that agnostic (proper) non-hallucinating learning can be *harder* than agnostic PAC learning, even if the hypothesis class is of size $2$ and even there exists a hypothesis within class that is *not* (relatively) hallucinating.

###### Corollary 1 .

There exists a hypothesis class $\mathcal{P}$ of size $2$, such that $\mathcal{P}$ is *not* $\alpha$-agnostic non-hallucinating learnable for any given $\alpha\geq 0$. This is true for both the (absolute) hallucinate rate as defined in (1) and the relative hallucination rate in Definition 2.

###### Proof.

We only prove the case for the *relative* hallucination rate, as the case for (absolute) hallucination rate follows similarly. For any given $\alpha>0$, we take $\epsilon$ small enough so that
$\epsilon\leq\frac{1}{2\alpha+1}$. By Theorem 1 condition 2, we have $\inf_{p}\mathsf{hall}_{\epsilon}(p,q)\leq 2\epsilon$. Moreover, by condition 3 of Theorem 1, we have w.p. $>\delta$ that $\mathsf{hall}_{\epsilon}(\Phi(\mathbf{x}^{n}),q)=1$. Therefore, we conclude w.p. $>\delta$ that:

$$ $\mathsf{hall}_{\epsilon}(\Phi(\mathbf{x}^{n}),q)-\alpha\inf_{p\in\mathcal{P}} \mathsf{hall}_{\epsilon}(p,q)\geq 1-\alpha\cdot 2\epsilon\geq\epsilon$ $$

whenever $\epsilon\leq\frac{1}{2\alpha+1}$. This violates the $\alpha$-agnostic-non-hallucinating learnability in Definition 1.
∎

###### Definition 1 ( α 𝛼 \alpha italic_α -agnostic non-hallucinating learning) .

###### Example 1 .

###### Definition 2 (Relative Hallucination Rate) .

###### Theorem 1 (Agnostic proper non-hallucinating learning is impossible) .

###### Proof.

###### Corollary 1 .

###### Proof.

## 4 Non-Hallucinating Learning via Knowledge of 𝒯 𝒯 \mathcal{T} caligraphic_T

As we demonstrated by Theorem 1, agnostic (proper) non-hallucinating learning is *impossible* by restricting the *hypothesis class* alone, even measured *competitively*. This is partially due to the fact that the learner must handle *any* tuple $(q,\mathcal{T})$, or in other words, it does not incorporate any *prior* knowledge of the facts set into the learning process. This phenomenon mirrors the “no-free lunch” theorems in the PAC learning literature (Shalev-Shwartz & Ben-David, ), which assert that learning is *impossible* without assumptions about the learning target. This is typically resolved by introducing additional *inductive biases* in the learning process that restrict the hypothesis class, such as limiting it to a finite VC-dimension. This section is devoted to introducing certain natural assumptions on $(q,\mathcal{T})$ that lead to non-trivial resolutions of non-hallucinating learning.

### 4.1 The improper learning case

Clearly, if the leaner is *improper*, then a naïve non-hallucinating learner that simply generates the *empirical distribution* over the training sample $\mathbf{x}^{n}$ never hallucinates. This is clearly not satisfactory, as the learned model is completely non-generalizable. To mitigate this restriction, we introduce certain constrains on the facts set $\mathcal{T}$ that allow our learned model to “generalize”. We assume that $\mathcal{T}\in\mathcal{C}$, where $\mathcal{C}\subset 2^{\mathcal{X}}$ is a *concept class* of all possible sets that $\mathcal{T}$ can be chosen from. Here, the concept class would be determined by *prior* knowledge of the learner on $\mathcal{T}$.

To quantify the “generalizability” of the learned model, we introduce an additional notion of *information measure* $I$ that quantifies the amount of “information” of distributions in $\Delta(\mathcal{X})$:

$$ $I:\Delta(\mathcal{X})\times\mathcal{X}^{*}\rightarrow\mathbb{R}^{\geq 0}.$ $$

Note that, here we allow the information measure $I(p,\mathbf{x}^{n})$ to be dependent on the training set $\mathbf{x}^{n}$ as well.
For any given information measure function $I$, we consider the following definition:

###### Definition 3 (Improper non-hallucinating learnable) .

For any $\gamma<1$, a concept class $\mathcal{C}$ is said to be $\gamma$-approximately improper non-hallucinating learnable w.r.t. information measure $I$, if there exists an (improper) learner $\Phi$ such that for any $\epsilon,\delta>0$, there exists a number n, so that for any $\mathcal{T}\in\mathcal{C}$ and any faithful-demonstrator $q$ over $\mathcal{T}$, w.p. $\geq 1-\delta$ over $\mathbf{x}^{n}\sim q$ the following holds:

- 1.
The hallucination rate $\mathsf{hall}(\Phi(\mathbf{x}^{n}),\mathcal{T})\leq\epsilon$;
- 2.
$I(\Phi(\mathbf{x}^{n}),\mathbf{x}^{n})\geq(1-\gamma)I(q,\mathbf{x}^{n})$.

Observe that the first part of Definition 3 ensures that the learned model does not hallucinate, while the second part ensures that the model is as informative as the demonstrator so that generalizability is possible. Moreover, it is crucial to note that, although the facts set $\mathcal{T}$ is restricted to the concept class $\mathcal{C}$, the demonstrator $q$ is *unconstrained*, as long as it is faithful w.r.t. $\mathcal{T}$.

There are many natural information measures. We mention a few here:

- 1.
For discrete $\mathcal{X}$, *Shannon entropy* is defined as $H(p):=\sum_{\mathbf{x}\in\mathcal{X}}p[\mathbf{x}]\log\frac{1}{p[\mathbf{x}]}$, which measures the (absolute) information contained in $p$ *independent* of the training set $\mathbf{x}^{n}$;
- 2.
The *$\alpha$-Rényi entropy* is defined as $H_{\alpha}(p)=\frac{1}{1-\alpha}\log\left(\sum_{\mathbf{x}\in\mathcal{X}}p[
\mathbf{x}]^{\alpha}\right)$, where $\alpha>0$ and $\alpha\not=1$, which subsumes the Shannon entropy for $\alpha\rightarrow 1$;
- 3.
The *out-of-sample mass* is defined as (for $n\geq 1$):
$I(p,\mathbf{x}^{n}):=p[\mathcal{X}\backslash\{\mathbf{x}_{1},\cdots,\mathbf{x}
_{n}\}]$,
which measures the amount of probability mass of $p$ assigned *outside* of the training set.

The specific choice of information measure typically depends on the task at hand. We show in the following theorem, perhaps surprisingly, that improper non-hallucinating learning is possible if the concept class $\mathcal{C}$ has finite VC-dimension, *regardless* of what information measure is selected.

###### Theorem 2 .

If a concept class $\mathcal{C}$ has finite VC-dimension, then $\mathcal{C}$ is 0 0-approximately (improper) non-hallucinating learnable w.r.t. *any* information measure function $I$. Moreover, the sample complexity is upper bounded by $n\leq O\left(\frac{\mathsf{VC}(\mathcal{C})\log(1/\epsilon)+\log(1/\delta)}{
\epsilon}\right).$

###### Proof.

Let $\mathcal{T}^{*}\in\mathcal{C}$ be a ground truth facts set and $q^{*}$ be a faithful-demonstrator w.r.t. $\mathcal{T}^{*}$. Let $\mathbf{x}^{n}\sim q^{*}$ be a set of samples. We define the *version space*:

$$ $\mathcal{C}_{n}=\{\mathcal{T}\in\mathcal{C}:\forall i\leq n,~{}\mathbf{x}_{i} \in\mathcal{T}\},$ (5) $$

as the subset of elements in $\mathcal{C}$ that are consistent with the sample $\mathbf{x}^{n}$.
Note that $\mathcal{T}^{*}\in\mathcal{C}_{n}$ holds always, since $q^{*}$ is faithful. For any $\mathcal{T}\in\mathcal{C}$, we say $q^{*}$ $\epsilon$-violates $\mathcal{T}$ if
$\mathsf{hall}(q^{*},\mathcal{T})\geq\epsilon.$
We claim that:

$$ $\mathrm{Pr}_{\mathbf{x}^{n}\sim q^{*}}\left[\exists\mathcal{T}\in\mathcal{C}_{ n},~{}s.t.~{}q^{*}~{}\epsilon\text{-violates}~{}\mathcal{T}\right]\leq\delta,$ (6) $$

provided $n\geq C\frac{d\log(1/\epsilon)+\log(1/\delta)}{\epsilon}$ for some constant $C$, where $d=\mathsf{VC}(\mathcal{C})$. To see this, we can view the sample $\mathbf{x}^{n}$ as feature-label pairs that has all labels being $1$. In this case, the hallucination rate $\mathsf{hall}(q^{*},\mathcal{T})$ can be viewed as the population risk of $\mathcal{T}$ under the data distribution. Moreover, since $q^{*}$ is faithful, the ground truth set $\mathcal{T}^{*}$ achieves 0 0 risk, therefore, the data distribution is effectively *realizable* w.r.t. $\mathcal{C}$. The claim then follows by standard uniform convergence result of VC class, see e.g. Shalev-Shwartz & Ben-David (, Theorem 6.8 (3)).

We now consider the following learning rule:

$$ $\Phi(\mathbf{x}^{n}):=\arg\max_{p\in\Delta(\mathcal{X})}\{I(p,\mathbf{x}^{n}): p~{}\text{does not}~{}\epsilon\text{-violate}~{}\mathcal{T},~{}\forall\mathcal {T}\in\mathcal{C}_{n}\}.$ (7) $$

Clearly, $\Phi(\mathbf{x}^{n})$ always satisfies condition $1$ of Definition 3, since $\mathcal{T}^{*}\in\mathcal{C}_{n}$ and therefore any feasible solution from (7) does not $\epsilon$-violate $\mathcal{T}^{*}$. Moreover, by (6), w.p. $\geq 1-\delta$ over $\mathbf{x}^{n}\sim q^{*}$ that $q^{*}$ is within the feasible set of (7). Therefore, we have:

$$ $I(\Phi(\mathbf{x}^{n}),\mathbf{x}^{n})\geq I(q^{*},\mathbf{x}^{n}),$ $$

by definition of $\arg\max$. Thus, condition $2$ of Definition 3 is also satisfied with $\gamma=0$.
∎

Theorem 2 demonstrates that if the facts set $\mathcal{T}$ can be correctly specified by a concept class of finite VC-dimension (this includes, for example, when the indicator function of the facts set is specified by a neural network), then we can always learn a non-hallucinating generative model which is as informative as the demonstrator, *regardless* of how the demonstration distribution is chosen, as long as it is faithful. Moreover, the learning rule can be extracted from the *meta*-algorithm in (7) depending on any information measure $I$ at hand, albeit not computationally efficiently.

It is crucial to distinguish our non-hallucinating learning paradigm in Theorem 2 from the standard PAC learning, even though the proof may look similar. This is because, in our non-hallucinating learning framework, the ultimate goal is to produce a *distribution* (i.e., a generative model) not a classification function (i.e., a discriminative model). The concept class only serves as a *regularization* to control the hallucination rate of the learned model. More importantly, our learning paradigm is *unsupervised* without any need of human labeling.

We now establish a matching sample complexity lower bound for (improper) non-hallucinating learning w.r.t. the *out-of-sample mass* information measure for the *worst* concept classes $\mathcal{C}$. This, together with Theorem 2, implies that the VC-dimension remains a meaningful complexity measure that characterizes improper non-hallucinating learning.

###### Theorem 3 .

For any $d\in\mathbb{N}$, there exists a concept class $\mathcal{C}$ of VC-dimension $d$ such that for any $\epsilon>0$ sufficiently small and any $\delta\leq\epsilon$, the sample complexity of 0 0-approximately (improper) non-hallucinating learning $\mathcal{C}$ w.r.t. out-of-sample mass measure is lower bounded by $\Omega(\frac{d}{\epsilon})$.

###### Proof.

For any $d\in\mathbb{N}$, we take $\mathcal{X}$ to be a set of size $2d+1$. Let $\mathbf{x}_{0}\in\mathcal{X}$ be any element. We define $\mathcal{C}:=\{\mathcal{T}\subset\mathcal{X}:\mathbf{x}_{0}\in\mathcal{T}\text
{ and }|\mathcal{T}|=1+d\}$. It is easy to verify that $\mathsf{VC}(\mathcal{C})=d$. We now describe a random process for generating $(q,\mathcal{T})$. We first uniformly sample $\mathcal{T}$ from $\mathcal{C}$ and then define $q=(1-\epsilon^{\prime})\delta_{\mathbf{x}_{0}}+\epsilon^{\prime}\mathsf{Uni}(
\mathcal{T}\backslash\{\mathbf{x}_{0}\})$ for some $\epsilon^{\prime}$ to be determined. Clearly, $q$ is faithful w.r.t. $\mathcal{T}$. Let $\mu$ be the derived distribution over $(q,\mathcal{T})$. For any given learner $\Phi$ and sample size $n\leq\frac{d}{4\epsilon^{\prime}}$, we denote $\hat{p}_{n}:=\Phi(\mathbf{x}^{n})$. Our goal is to lower bound the expected hallucination rate:

$$ $\mathbb{E}_{(q,\mathcal{T})\sim\mu}\mathbb{E}_{\mathbf{x}^{n}\sim q}[\mathsf{ hall}(\hat{p}_{n},\mathcal{T})]=\mathbb{E}_{\mathbf{x}^{n}}\mathbb{E}_{(q, \mathcal{T})\sim\mu\mid\mathbf{x}^{n}}[\mathsf{hall}(\hat{p}_{n},\mathcal{T})],$ $$

where $\mathbb{E}_{\mathbf{x}^{n}}$ is over the *mixture* $\mu\sim q\sim\mathbf{x}^{n}$ and $\mu\mid\mathbf{x}^{n}$ is the distribution of $\mu$ conditioning on $\mathbf{x}^{n}$.

Denote $A:=\{\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\}$ as the *set* formed by $\mathbf{x}^{n}$, and let $E$ be the event on $\mathbf{x}^{n}$ such that $\mathbf{x}_{0}\in A$ and $|A|\leq\frac{d}{2}+1$. We now condition on the event $E$ occurring. This implies that the *out-of-sample* mass $I(q,\mathbf{x}^{n})\geq\frac{\epsilon^{\prime}}{2}$, since $|\mathcal{T}\backslash A|\geq\frac{d}{2}$ and $q$ is uniform when restricted to $\mathcal{T}\backslash\{\mathbf{x}_{0}\}$. By condition 2 of Definition 3 with $\gamma=0$ (^2^22We take $\gamma=0$ for simplicity, however, our argument holds for general $\gamma>0$ as well.), we have
$I(\hat{p}_{n},\mathbf{x}^{n})=\sum_{\mathbf{x}\in\mathcal{X}\backslash A}\hat{
p}_{n}[\mathbf{x}]\geq I(q,\mathbf{x}^{n})\geq\epsilon^{\prime}/2.$
Note that the conditional distribution $\mu\mid\mathbf{x}^{n}$ restricted on $\mathcal{T}$ is exactly uniform over $\mathcal{C}^{\prime}=\{\mathcal{T}^{\prime}\in\mathcal{C}:A\subset\mathcal{T}^
{\prime}\}$.
We have, for any $\mathbf{x}\not\in A$ that

$$ $\mathbb{E}_{(q,\mathcal{T})\sim\mu\mid\mathbf{x}^{n}}[1\{\mathbf{x}\not\in \mathcal{T}\}]=\mathbb{E}_{\mathcal{T}^{\prime}\sim\mathcal{C}^{\prime}}[1\{ \mathbf{x}\not\in\mathcal{T}^{\prime}\}]=\frac{2d-|A|}{2d}\geq\frac{2d-d/2}{2d }=\frac{3}{4}.$ $$

This implies, for all $\mathbf{x}^{n}\in E$ that:

$$ $\displaystyle\mathbb{E}_{(q,\mathcal{T})\sim\mu\mid\mathbf{x}^{n}}[\mathsf{ hall}(\hat{p}_{n},\mathcal{T})]$ $\displaystyle=\mathbb{E}_{(q,\mathcal{T})\sim\mu\mid\mathbf{x}^{n}}\left[\sum_ {\mathbf{x}\in\mathcal{X}}\hat{p}_{n}[\mathbf{x}]1\{\mathbf{x}\not\in\mathcal{ T}\}\right]$ $\displaystyle\geq\mathbb{E}_{(q,\mathcal{T})\sim\mu\mid\mathbf{x}^{n}}\left[ \sum_{\mathbf{x}\in\mathcal{X}\backslash A}\hat{p}_{n}[\mathbf{x}]1\{\mathbf{x }\not\in\mathcal{T}\}\right]$ $\displaystyle\geq\frac{3}{4}\sum_{x\in\mathcal{X}\backslash A}\hat{p}_{n}[ \mathbf{x}]\geq\frac{3\epsilon^{\prime}}{8}.$ $$

We now observe that the distribution $q$ assigns only $\epsilon^{\prime}$ probability mass on $\mathcal{X}\backslash\{\mathbf{x}_{0}\}$. The expected number of elements in $\mathbf{x}^{n}$ *not* equal to $\mathbf{x}_{0}$ is upper bounded by $\epsilon^{\prime}n\leq\frac{d}{4}$. This implies, by Markov inequality, that w.p. $\geq\frac{1}{2}$ we have $|A|\leq\frac{d}{2}$ and $\mathbf{x}_{0}\in A$, therefore $\mathrm{Pr}[E]\geq\frac{1}{2}$. Putting everything together, we have

$$ $\displaystyle\mathbb{E}_{(q,\mathcal{T})\sim\mu}\mathbb{E}_{\mathbf{x}^{n}\sim q }[\mathsf{hall}(\hat{p}_{n},\mathcal{T})]$ $\displaystyle=\mathbb{E}_{\mathbf{x}^{n}}\mathbb{E}_{(q,\mathcal{T})\sim\mu \mid\mathbf{x}^{n}}[\mathsf{hall}(\hat{p}_{n},\mathcal{T})]$ $\displaystyle\geq\frac{1}{2}\mathbb{E}_{\mathbf{x}^{n}}[\mathbb{E}_{(q, \mathcal{T})\sim\mu\mid\mathbf{x}^{n}}[\mathsf{hall}(\hat{p}_{n},\mathcal{T})] \mid E]\geq\frac{3\epsilon^{\prime}}{16}.$ $$

Taking $\epsilon^{\prime}>\frac{32}{3}\epsilon$, we have the *expected* hallucination rate $>2\epsilon$. Since hallucination rate is $\leq 1$, we have w.p. $\geq\epsilon$, the hallucination rate is $>\epsilon$. Meaning that, for any sample size $n\leq\frac{d}{4\epsilon^{\prime}}=\frac{3}{128}\frac{d}{\epsilon}$, *no* learner can achieve both conditions of Definition 3 for $\delta\leq\epsilon$. This completes the proof.
∎

Note that, although Theorem 3 is proved only for the *out-of-sample mass*, a similar lower bound can also be established for other information measures. We refer to Appendix A for a lower bound on the *Shannon entropy*.
Moreover, Theorem 3 only characterizes the sample complexity in the *minimax* sense, i.e., for the *worst* case VC classes. Indeed, the sample complexity can be *lower* for certain specific VC-classes, as demonstrated in the example below.

###### Example 2 .

Let $\mathcal{X}=A\cup\{1,\cdots,d\}$ where $|A|\gg d$; we define class $\mathcal{C}$ as the class of all subsets of $\mathcal{X}$ that contain $A$. We have $\mathsf{VC}(\mathcal{C})\geq d$. However, an algorithm that always produces *uniform* distribution over $A$ has 0 0 hallucination rate and the out-of-sample mass is lower bounded by $\frac{|A|-n}{|A|}$ for any sample of size $n$. Taking $n=1$, one can make the out-of-sample mass arbitrarily close to $1$ by choosing sufficiently large $|A|$.

We would like to point out that any complexity measure on $\mathcal{C}$ that characterizes the (improper) non-hallucinating learnability at the *instance* level would necessarily depend on the information measure (for the lower bounds). We leave it as an open problem to find more fine-grained characterizations tailored to specific information measures, such as for the out-of-sample mass and Shannon entropy.

###### Definition 3 (Improper non-hallucinating learnable) .

###### Theorem 2 .

###### Proof.

###### Theorem 3 .

###### Proof.

###### Example 2 .

### 4.2 The proper learning case

We demonstrated in Theorem 2 that non-hallucinating learning is possible for *improper* learners if the facts set lies in a concept class of finite VC-dimension. A natural questions is whether such an approach can be extended to the *proper* learning case, i.e., instead of allowing the learner to output an *arbitrary* distribution in $\Delta(\mathcal{X})$, we restrict the output to some *hypothesis class* $\mathcal{P}\subset\Delta(\mathcal{X})$.

We again assume that the facts set $\mathcal{T}$ is selected from some concept class $\mathcal{C}$. Let $q$ be any faithful demonstrator w.r.t. $\mathcal{T}$ and $\mathbf{x}^{n}\sim q$. A natural learning rule that is inspired from (7) is as follows:

$$ $\Phi(\mathbf{x}^{n})=\arg\max_{p\in\mathcal{P}}\left\{I(p,\mathbf{x}^{n}): \mathsf{hall}(p,\mathcal{T})\leq\epsilon,~{}\forall\mathcal{T}\in\mathcal{C}_{ n}\right\},$ (8) $$

where $\mathcal{C}_{n}$ is the *version space* defined in (5) and $I$ is some appropriately selected information measure. Unfortunately, this (in fact any proper) learning rule fails to achieve non-hallucinating learning even if the minimal achievable hallucination rate of distributions in $\mathcal{P}$ is 0 0.
This is discussed in the next example.

###### Example 3 .

There exist hypothesis class $\mathcal{P}$ and concept class $\mathcal{C}$ that are of size $2$, such that for any *proper* learner $\Phi$, we can select some $\mathcal{T}\in\mathcal{C}$ and faithful demonstrator $q$ w.r.t. $\mathcal{T}$ such that
$\mathrm{Pr}_{\mathbf{x}^{n}\sim q}\left[\mathsf{hall(\Phi(\mathbf{x}^{n}),
\mathcal{T})}\geq 0.99\right]\geq\frac{1}{2}.$
The construction is similar to that of Example 1. To see this, we take two sets $A_{1}$ and $A_{2}$ of size $|A_{1}|=|A_{2}|=100$ and $|A_{1}\cap A_{2}|=1$. The concept class $\mathcal{C}=\{A_{1},A_{2}\}$ and the hypothesis class $\mathcal{P}=\{\mathsf{Uni}(A_{1}),\mathsf{Uni}(A_{2})\}$.Furthermore, we select demonstrator $q=\delta_{\mathbf{x}_{0}}$ for the (single) element $\mathbf{x}_{0}\in A_{1}\cap A_{2}$, which is faithful for both $A_{1}$ and $A_{2}$. Now, for any learner $\Phi$, it must produce $\mathsf{Uni}(A_{i})$ w.p. $\geq\frac{1}{2}$ for some $i\in\{1,2\}$. To satisfy the claimed lower bound, the adversary then simply takes the actual facts set $\mathcal{T}$ to be $A_{3-i}$.

Although the impossibility result of Example 3 is not technically surprising, since the demonstrator $q$ effectively produces no “information.” It demonstrates a striking distinction between proper and improper learnability of non-hallucinating learning. Recall that, for improper learning, the learner can *adapt* to the amount of information provided by the demonstrator, yet still avoid hallucination.

Therefore, in order to obtain meaningful results for the proper learning case, one needs to control the behaviour of the demonstrator $q$ as well. To achieve this, we introduce a sufficient condition under which the learning rule from (8) achieves non-hallucinating learnability.

###### Definition 4 .

A demonstrator $q$ is said to be sufficiently informative for a pair $(\mathcal{C},\mathcal{P})$ if there exists a function $\xi:[0,1]\rightarrow[0,1]$ such that for any $\epsilon>0$

$$ $\inf_{p\in\mathcal{P}}\sup_{\mathcal{T}\in\mathcal{C}_{\xi(\epsilon)}}\mathsf{ hall}(p,\mathcal{T})\leq\epsilon,$ $$

where $\mathcal{C}_{\xi(\epsilon)}=\{\mathcal{T}\in\mathcal{C}:\mathrm{Pr}_{\mathbf{x
}\sim q}[\mathbf{x}\not\in\mathcal{T}]\leq\xi(\epsilon)\}$.

Intuitively, Definition 4 ensures that the pathological instance of Example 3 do not occur for a sufficiently small “local neighborhood” $\mathcal{C}_{\xi(\epsilon)}$ of $\mathcal{C}$ induced by $p$. Indeed, equipped with this condition, we can establish the following positive result.

###### Theorem 4 .

Let $\mathcal{C}$ be any concept class of finite VC-dimension and $\mathcal{P}$ be any hypothesis class. Then for any $\mathcal{T}\in\mathcal{C}$ and any sufficiently informative
faithful-demonstrator $q$ w.r.t. $(\mathcal{C},\mathcal{P})$ as in Definition 4, we have w.p. $\geq 1-\delta$ over $\mathbf{x}^{n}\sim q$ that for the predictor $\Phi$ in (8) satisfies

$$ $\mathrm{Pr}_{\mathbf{x}^{n}\sim q}[\mathsf{hall}(\Phi(\mathbf{x}^{n}),\mathcal {T})\geq\epsilon]\leq\delta,$ $$

provided
$n\geq\Omega\left(\frac{\mathsf{VC}(\mathcal{C})\log(1/\xi(\epsilon))+\log(1/
\delta)}{\xi(\epsilon)}\right),$
where $\xi(\cdot)$ is the function in Definition 4.

###### Sketch of Proof.

The proof essentially follows a similar path as Theorem 2. Note that the standard uniform convergence result (c.f. (6)) implies that for the particular choice of $n$ in the theorem, w.p. $\geq 1-\delta$, we have $\mathcal{C}_{n}\subseteq\mathcal{C}_{\xi(\epsilon)}$. By Definition 4, there exists some $p\in\mathcal{P}$ such that for all $\mathcal{T}\in\mathcal{C}_{n}$, $\mathsf{hall}(p,\mathcal{T})\leq\epsilon$. Since the ground truth facts set $\mathcal{T}^{*}\in\mathcal{C}_{n}$ holds always, the produced model $\hat{p}_{n}:=\Phi(\mathbf{x}^{n})$ using the predictor $\Phi$ in (8) must satisfy $\mathsf{hall}(\hat{p}_{n},\mathcal{T}^{*})\leq\epsilon$, as required.
∎

Note that, the condition in Definition 4 is, in a sense, the *minimal* requirement to achieve *proper* non-hallucinating learnability. Otherwise, consider any demonstrator $q$ that does not satisfy the condition. There must exist some $\epsilon>0$ so that for any $\xi>0$ we have:

$$ $\inf_{p\in\mathcal{P}}\sup_{\mathcal{T}\in\mathcal{C}_{\xi}}\mathsf{hall}(p, \mathcal{T})>\epsilon.$ $$

A similar argument as in Example 3 yields that for any proper learner, there must exist some $\mathcal{T}\in\mathcal{C}_{\xi}$ so that the hallucination rate $>\epsilon$ w.p. $\geq\frac{1}{|\mathcal{P}|}$, provided $|\mathcal{C}_{\xi}|<\infty$ and $\xi$ is small enough.

###### Example 3 .

###### Definition 4 .

###### Theorem 4 .

###### Sketch of Proof.

## 5 Conclusion and Discussion

In this paper, we investigated the learnability of non-hallucinating generative models from a learning-theoretic perspective. We showed that agnostic non-hallucinating learning is statistically *impossible* if one does not incorporate knowledge of the ground truth facts set into the learning process, even when hallucination is measured *relatively*. This contrasts substantially with classical distribution PAC learning, where agnostic learning is possible without restrictions on the ground truth distribution. We then established several *positive* results, showing that non-hallucinating learning is achievable by restricting the ground truth facts set to certain *concept classes* with finite VC-dimension, and determined the tight sample complexity required to achieve learnability.

Although our contribution is primarily conceptual, we believe it will help practitioners understand the *fundamental limitations* of hallucinations in generative models in a more *principled* way. Our work also provides several algorithmic approaches for incorporating knowledge of the ground truth facts set into the learning process via *regularization*, such as the learning rules provided in (7) and (8), albeit computationally inefficiently. Our framework lays the foundation for significant future research on mitigating hallucinations in generative models. This includes exploring different approaches to incorporating factual knowledge, such as through logical rules, synthetic data generation, or leveraging human feedback, as well as developing more computationally efficient algorithms.

## Appendix A Additional Lower Bounds

In this appendix, we provide a lower bound for improper non-hallucinating learning when the Shannon entropy is chosen as the information measure

###### Theorem 5 .

For any number $d\in\mathbb{N}$, there exists a concept class $\mathcal{C}$ of VC-dimension $d$ such that the sample complexity of 0 0-approximately (improper) non-hallucinate learning $\mathcal{C}$ w.r.t. the Shannon entropy function $H$ is lower bounded by
$\Omega(d)$ for all sufficiently small $\epsilon,\delta>0$.

###### Proof.

We now take $\mathcal{X}=[d]$ and define $\mathcal{C}$ to be a collection of subsets of $\mathcal{X}$ such that $\forall\mathcal{T}\in\mathcal{C}$, $|\mathcal{T}|=d/2$ and

$$ $\forall\mathcal{T}_{1}\not=\mathcal{T}_{2}\in\mathcal{C},~{}|\mathcal{T}_{1} \cap\mathcal{T}_{2}|\leq\frac{d}{4}.$ $$

It can be shown that such a collection exists and $|\mathcal{C}|\geq\sqrt{\frac{1}{4d}}e^{d/16}$, see e.g., (Wu et al., , Thm. D.1) for a proof. Moreover, the VC-dimension of $\mathcal{C}$ is at most $d$. For any $\mathcal{T}\in\mathcal{C}$, we denote $q_{\mathcal{T}}$ as the uniform distribution over $\mathcal{T}$. Now, in order for the Definition 3 to hold, for any $(\mathcal{T},q_{\mathcal{T}})$ the learner must produce a distribution $\hat{p}$ such that: (1) $\hat{p}[\mathcal{T}]\geq 1-\epsilon$; and (2) the Shannon entropy $H(\hat{p})\geq\log(d/2)$. We claim that for any other $\mathcal{T}^{\prime}\in\mathcal{C}$ that differs from $\mathcal{T}$, one must have $\hat{p}[\mathcal{T}^{\prime}]<1-\epsilon$, for any $\epsilon\leq 0.07$. To see this, we split the support of $\hat{p}$ into $3$ parts $A_{1}=\mathcal{T}\backslash\mathcal{T}^{\prime}$, $A_{2}=\mathcal{T}\cap\mathcal{T}^{\prime}$ and $A_{3}=[d]\backslash\mathcal{T}$. It is clear that $\hat{p}[A_{3}]\leq\epsilon$. Assume now that $\hat{p}[\mathcal{T}^{\prime}]\geq 1-\epsilon$, then one must have $\hat{p}[A_{2}]\geq 1-2\epsilon$. By expressing the entropy of $\hat{p}$ conditioning on the $A_{1},A_{2}$ and $A_{3}$ we have

$$ $H(\hat{p})=\sum_{i\in\{1,2,3\}}\hat{p}[A_{i}]\log\frac{1}{\hat{p}[A_{i}]}+\hat {p}[A_{i}]\cdot H(\hat{p}\mid A_{i}),$ (9) $$

where $H(\hat{p}\mid A_{i})$ is the entropy of the conditional distribution of $\hat{p}$ on $A_{i}$. Observe that $H(\hat{p}\mid A_{1})\leq\log d/2$, $H(\hat{p}\mid A_{2})\leq\log d/4$ and $H(\hat{p}\mid A_{3})\leq\log d$, since uniform distribution maximizes entropy. Moreover, our previous discussion yields that $\hat{p}[A_{1}],\hat{p}[A_{3}]\leq\epsilon$ and $\hat{p}[A_{2}]\geq 1-2\epsilon$. Therefore, the RHS of $(\ref{eq:thm3})$ is upper bounded by (via Lagrangian multiplier method that the maximum attains on the boundary $\hat{p}[A_{1}]=\hat{p}[A_{3}]=\epsilon$ and $\hat{p}[A_{2}]=1-2\epsilon$ whenever $\epsilon\leq 0.18$):

$$ RHS $\displaystyle\leq\underbrace{\epsilon\log d/2+\epsilon\log\frac{1}{\epsilon}}_ {\text{Contributed by }A_{1}}+\underbrace{(1-2\epsilon)\log d/4+(1-2\epsilon) \log\frac{1}{(1-2\epsilon)}}_{\text{Contributed by }A_{2}}+\underbrace{ \epsilon\log d+\epsilon\log\frac{1}{\epsilon}}_{\text{Contributed by }A_{3}}$ $\displaystyle=\log d+2\epsilon\log\frac{1}{\epsilon}+(1-2\epsilon)\log\frac{1} {1-2\epsilon}+3\epsilon-2.$ $$

Sine $H(\hat{p})\geq\log d-1$, we have $-2\epsilon\log\epsilon-(1-2\epsilon)\log(1-2\epsilon)+3\epsilon\geq 1$. Rewrite the expression, this implies $h(2\epsilon)+5\epsilon\geq 1$, where $h(\cdot)$ is binary entropy function. Numerical computation yields that this can happen only when $\epsilon\geq 0.07$.

Now, the above discussion implies that any successful learner that satisfies Definition 3 with $\epsilon\leq 0.07$ must be able to identify the distribution $q_{\mathcal{T}}$ for all $\mathcal{T}\in\mathcal{C}$ by observing only on their $i.i.d.$ samples. We now derive a lower bound for such a identification problem using the Fano’s inequality. Denote $\bar{q}$ as the uniform distribution over $[d]$, the Fano’s inequality Polyanskiy & Wu () implies that the error probability of the identification problem of sample size $n$ is lower bounded by

$$ $1-\frac{1}{\log|\mathcal{C}|}\left(\sup_{\mathcal{T}\in\mathcal{C}}n\cdot \mathsf{KL}(q_{\mathcal{T}}||\bar{q})+\log 2\right)=\delta.$ $$

Direct computation yields that $\mathsf{KL}(q_{\mathcal{T}}||\bar{q})\leq\log 2$ for all $\mathcal{T}\in\mathcal{C}$. Therefore, an $O(1)$ error probability lower bound holds as long as $n\ll\log|\mathcal{C}|$, i.e., for sufficiently small $\delta>0$ we have the sample complexity $n\geq\Omega(\log|\mathcal{C}|)\geq\Omega(d)$ since $|\mathcal{C}|\geq\sqrt{\frac{1}{4d}}e^{d/16}$ as discussed above.
∎

###### Theorem 5 .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 1
presentation: 2
questions: Couldn’t a statement simply be non-factual, but not a hallucination.  Context also seems important. For example, a claim may be factual in a story but not in general.  Additionally, a question seems like a sentence which is non-factual but not a hallucination.
soundness: 1
strengths: The issue of conceptualizing and theorizing about hallucinations seems like an important and useful problem to address.
summary: -This paper is rather strange, because it seems to be about hallucination as a specific problem, but the theoretical claims just treat hallucination as a subset of examples.  It seems like the claims are about a more general phenomena of trying to learn examples which belong to a set.  In this case, set is characterized as a set of factual claims, but this property isn’t used.  In the technical results, it’s just a set.  

Notes from reading the paper: 
 -Hallucinations are outputs which are plausible but invalid.  
  -Impossible to stop hallucinations using data, but need to leverage inductive biases about facts.  
  -Paper is purely conceptual, but if claim is valid, seems very striking.  
  -Let X be the set of sentences, while T is the set of facts, or sentences that describe true statements that are relevant.  The hallucination rate is the rate hall(p, T) of sentences generated which aren’t facts.  
  -A demonstrator q is faithful wrt T if hall(q,T)=0.
weaknesses: The paper seems extremely flawed.  First, it is a purely theoretical paper, with no analysis or experiments, even on toy models.  I think this is dubious, especially when the theoretical framework is speculative and not well established.  For example, even a small illustration on a real toy dataset would help to clarify the ideas of the paper.  Second, it doesn't seem like the analysis actually uses the nature of hallucinations in proving the result, which leads me to think that the paper could be written with a more general claim.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 2
questions: - Theorem 1 is written as specifically for the case of a hypothesis class of 2, do you think the result would still hold for hypothesis classes of arbitrary sizes?
- I'm a bit confused by how exactly Example 3 differs from Example 1?
soundness: 3
strengths: - The work provides a novel and important contribution that addresses a particularly relevant problem (namely that of hallucinations in generative models) which has not been thoroughly studied from a theoretical perspective.
- The paper is generally well-written and structured.
- The construction of the counter-example for Theorem 1 is interesting and clear.
- Section 4.1 is particularly valuable studying the case of a model that can generalize without hallucinating.
summary: The authors examine the problem hallucinations in generative models from a learning theory perspective. They provide a formal setup for the problem, define the hallucination rate formally (as the probability mass assigned to samples not in some true fact subset) and characterize the importance of distinguishing between proper/improper learning for this paradigm. They then provide three main theoretical results:
- Proper learning (i.e. restricted to a hypothesis class) without hallucination is impossible.
- Non-hallucinating learning that generalizes is possible given an improper learner and restrictions on the VC-dimension of the fact set $\mathcal{T}$. They provide sample complexity bounds for this case.
- Proper learning with a VC concept class is possible as long as $q$ (the data generating process) is sufficiently informative.
weaknesses: - The work could benefit for a more in-depth comparison with Kalai & Vempala (2024).
- The impossibility results in section 3 seem to rely on the pathological case of an uninformative $q$. It would be interesting to investigate the case where $q$ is sufficiently informative as per definition 4.
- As acknowledged by the authors, the work is mostly conceptual and a first step in this research direction. 
- The messaging on the key takeaways from the paper could be improved (especially for practitioners not particularly interested in learning theory).

Nitpicks:
- The work could do with less italicized words (feels like there's at least 1-2 every sentence).
- Some typos such as:
  - Line 245: For the -> the
  - Line 294: Complited -> Completed
  - Line 326: Leaner -> Learner

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: # Questions
- LL178: Is point (ii) even always possible in principle, i.e., will the learned model always generalize given sufficient training samples?

# Minor suggestions
- LL65: What is $\mathcal X^*$?
- LL130: typo "being" → "been"
- LL151: while it is technically correct to call $\mathrm x^n$ a "sample", this might confuse readers to assume $\mathrm x^n$ is a single point rather than a set of points. I recommend using a slightly different terminology
- Eq. 3: $\| \cdot \|_\text{TV}$ what does this notation mean? I assume based on the paragraph below it is "total variation distance"?
- §1, §2: as far as I can see, the term PAC learning is never introduced
- LL167: What does "w.p." stand for?
- LL195: What does "w.h.p." stand for?
- LL336: Should be "note that, here, ..."

Generally, I recommend double-checking that abbreviations and notations used are introduced whenever they first appear. Where not absolutely necessary, avoiding abbreviations increases readability and makes the paper more accessible to readers from other subfields.
soundness: 3
strengths: The paper, to the best of my knowledge, introduces a novel take on hallucinations in generative models and is the first to show such a strong impossibility result. While the paper remains purely theoretical and doesn't offer an implementation for cases in which hallucination-free learning is in principle possible (as the authors also admit), I believe this result will nontheless be informative for the community. Theorem 4 and §4.2 in general make a first step in understanding when avoiding hallucinations is possible.

The paper is thorough in setting up the problem and does a good job of elucidating the importance of its results.
summary: This paper considers the problem of hallucinations in generative models from a learning theory lense. The authors highlight that avoiding hallucinations poses a fundamental problem: On the one hand, a model should generalize beyond its training distribution, but on the other hand, undesired implausible artefacts (hallucinations) have to be avoided without a strict characterization of what is implausible. The authors formalize this issue and are able to show that without inductive biases that restrict the set of plausible samples, it is impossible to avoid hallucinations. This is an important result that will be of interest to the wider community, especially also for practicioners who attempt to avoid hallucinations via empirical means. The authors go on to explore how inductive biases can facilitate learning without hallucinations, but highlight that this problem remains challenging.
weaknesses: The paper is quite dense and might be inaccessible to a larger audience, especially to practitioners for whom this result might be very relevant. I would highly suggest the authors to add, e.g., a short paragraph after each theorem that translates the abstract results into specific examples and gives a higher-level intuition. E.g. consider a simple sample task using real data: Which assumptions of the theorem will be met? Are there some implications the theorem makes that would be violated but can be considered to be not very impactful in practice? I believe some of the proofs could be moved to an appendix to make space for this.

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 2
questions: - You use plausibility, validity, and factuality (and their negations) to describe hallucinations. Though for me the definition of hallucination rate was very clear, the definition in the abstract _("plausible but invalid")_ seems not to capture all aspects of hallucinations. I'd argue that implausible (and false) outputs also belong to hallucinations. Could you please clarify which one you mean?
- Out of curiosity, how does your intuition relate to impossibility results in the identifiability literature (eg,  http://proceedings.mlr.press/v97/locatello19a.html), which also state that some further assumption ("inductive bias") is needed for identifiability?
soundness: 3
strengths: **I am by far not an expert in learning theory, so my theoretical understanding of this paper is limited. Still, I can appreciate the authors' contributions:**

- the paper's topic is highly relevant, interesting, and the results (seem to be) strong
- the setup is clear from the introduction (though it's maybe too technical to be placed into the introduction)
- the technical results have nice intuitive explanations (even for someone who is not an expert in learning theory)
summary: The paper studies learning hallucination-free models from a learnng theory perspective and provides multiple negative and positive results, the latter for cases when inductive biases are present.
weaknesses: **My main point is that the presentation lacks clarity and detailed explanations of the steps taken. Note, however, that I am no expert in learning theory. Due to this fact, I choose a conservative score, but I am willing to reconsider during the rebuttal.**

### Major points
- several details are deemed "simple/clear/easy to verify" and left out, and non-standard abbreviations are not resolved (even though the reader might be able to guess them)
- the proofs could have been moved to the appendix, for the main text providing proof sketches would have been sufficient (and this would provide space to elaborate on intuition/notation) - by sketch I mean an intuitive description of the steps, not as technical as the one provided for Theorem 4.

### Minor points
- a Figure 1 for an intuitive overview would improve the paper
- L55: what is an instance space?
- the introduction is too long and already contains technical details (and readers probably won't expect to find these in the introduction), please consider restructuring the paper
- also, though the contributions list is helpful, it is too long to be considered as a "summary"
- L117: "Our results demonstrate"
- Eq (3): please specify what the subscript TV stands for.
- L160: what does 3-agnostic mean? Does the "3" relate to Eq (3) or something else?
- Fact 1: 
	- please don't call this a "simple fact."
	- what is "w.p."?
- L195: what is "w.h.p."?
- Example 1: I appreciate that you provide an example, though skipping steps by writing "It is easy to verify" doesn't help the reader. Please elaborate.
- L317: what do you mean by "measured competitively?"

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Your framework assumes that inductive biases can be introduced through concept classes. How is it applied to generative models in real-world scenarios?
2. The VC-dimension plays a key role in characterizing non-hallucinating learnability, but for complex models like transformers, estimating the VC-dimension is challenging. Are there alternative complexity measures or proxies you considered?
3. Can the framework be extended to evaluate hallucinations across multimodal generative models, such as vision-language models? If so, how would you do that?
soundness: 3
strengths: 1. The paper explores the inherent challenges and limitations of achieving non-hallucinating learning, introducing the theoretical impossibility of agnostic proper learning.
2. Through Theorems 1-4, the paper offers new theoretical insights, such as the impossibility of agnostic guarantees and the role of concept classes with finite VC-dimension in enabling non-hallucinating learning.
3. The paper provides upper and lower sample complexity bounds to balance model generalization and non-hallucination.
summary: The paper develops a theoretical framework to explore the limitations of training generative models that do not hallucinate. It finds that learning non-hallucinating models based purely on truthful training data is statistically impossible without incorporating inductive biases. The study further introduces scenarios where non-hallucinating learning is achievable by using improper learners or by restricting the hypothesis space with finite VC-dimension concept classes.
weaknesses: The framework proposed is primarily conceptual, and may need practical guidance for deploying non-hallucinating generative models in real-world applications.

Meta-review: This paper presents an impossibility result for non-hallucinating generative models and conceptually explains the role of inductive bias. Overall, while one reviewer was negative, the others stood up for the paper in the discussion, and I agree with their assessment. The direction is timely, and the definition and study of hallucinations are likely to inspire new work in learning theory and, hopefully, practice. The main criticisms addressed during the rebuttal concerned the presentation.

While I side with the majority of reviewers, I also want to say that I partially also agree with Reviewer fY7z. This paper could have had some experiments supporting the theoretical claims and showcasing how these results may lead toward a principled approach to address hallucinations, which would have made the contribution much stronger, in my opinion.

Decision: Accept (Poster)