No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Models
Authors: Changlong Wu
Ananth Grama
Wojciech Szpankowski
Venue: ICLR 2025 Poster (2025)
Keywords: generative models
hallucination
no-free-lunch theorem
distribution PAC learning
VC-dimension
Primary area: learning theory
TL;DR: We explore hallucination in generative models from a distribution PAC learning perspective, we prove both possibility and impossibility results on learnability across various paradigms.

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 not grounded in the underlying facts. 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 fact 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.

Published as a conference paper at ICLR 2025
No FREE LUNCH: FUNDAMENTAL LIMITS OF LEARN- ING HON-HALLUCINATING GENERATIVE MODELS
Changlong Wu', Ananth Grama' & Wojciech Szpankowskil.2
CCSol, Purdue University JJagiellonian University
nuchangl&hawale edu {ayg, seppssspaaajpddeeeeee edu
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 not grounded the underlying facts. While empirical strategies have been explored mitigate this issue, rigorous theoretical understanding remains clusive. In this paper, we develop a theoretical framework to analyze the learnability of non- hallucinating generative models from sults reveal that non-hallucinating learning is statistically impossible when relying solely on the training dataset, even for 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 pro- cess is essential. We provide a systematic approach to achieve this by restricting the facts set concept class of finite VC-dimension and demonstrate its effec- tiveness 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.
theoretic perspective. Our re-
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 statisti- cal 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 ulti- mately 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 in- formation retrieval (IR) systems, rather than those capable of new insight not grounded in training data. This tension between the desired ability of AI models generate new hypothesis, while not generating "falsifiable" artifacts, without 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 (Dzin al., (022), hallucination detection (Manakul et al., (203). and fine-tuning with human feedback (Ouyang et al. 2022), 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 mathe- matical perspective. This paper advances the state of the art by developing thcoretical framework to understand hallucinations in generative models from saaming-theorede perspective. We estab- lish a rigorous theoretical foundation for analyzing the learnability of non-hallucinating generative models under various learning paradigms. Specifically, non non-ballucinating learning is possible, identify the appropriate learning rules, and determine the corresponding sample complexity required achieve learnability.
characterize the conditions under which

---

Published as a conference paper at ICLR 2025
Instances X
Support of
Facts T
s..d: sampling
Support of p.. := x(xx)
Figure 1: Illustration of the non-hallucinating learning paradigm. Here, X' denotes the set of all sentences (factual otherwise), and T denotes the of facts, whose complements are hallucina- tions. The training sample x" := {'i. X,) supported on the facts set T. The learned model pr produced by learning rule based on x", with hallucinations illustrated in red.
is generated i.i.d. from (faithful) demonstrator
We consider the following formal setup: let X' be an instance space; for example, in the context of language models, X' represents the set of all sentences (factual or otherwise). We denote by T 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 T abstractly. A generative model represented by a distribution p E ( where (X) is the set of all probability distributions over We define the hallucination rate of p w.r.t. T as:
x
hall(p, T) Pix~p[x & T].
That is, hallucination rate measures how much probability mass generative model assigns non- fact instances. A data generation mechanism is modeled as a distribution E A(X), which we also refer as a demonstrator. We say the demonstrator q faithful w.r.t. the facts T hall(q, T) = 0, i.c., the demonstrator does not produce non-fact samples. A learning rule is function + X - (X)), where X denotes the set of all finite sequences of elements in X. For any given c, 5 > O, we say the learner & non-hallucine mon-hallucinatinngy learns (4, TT) with sample complexity n at hallucination rate and confidence 6, if:
Pix [hall( ((x))xxx,..)))))) T) 2 5
where the training set x" : [x,,.... x is sampled i.i.d. from the demonstrator q-
is crucial to note that the learner Q in general, does not know the tuple (q. T), and the only avail- able information comes from the training set x". However, the construction of & incorporate prior information about (4, T) (i.e., inductive bias) into the learning process. Throughout the paper, assume that q is faithful w.r.t. T. That is, we aim characterize the non-hallucinating learnabil- ity in the cleanes! scenario where the entire training set is truthful. The main goal of this paper is to address the following probllem
What structural assumptions on the tuple (4,T) are necessary to achieve non- hallucinating learnability, even when the training is entirely truthful?
Proper v.S. Improper Learners. We distinguish two learning paradigms - proper and improper learning. Let P C ( be hypothesis class; for instance, P may represent the class of all distributions specified by a transformer architecture with different parameters. We say a learning rule proper w.r.t. P if img( ( C P, that is the learner must produce model within the hypothesis class. In the proper learning case, learnability also depends on the structure of P. Otherwise, we say that the leaner & is improper; i.e., its outcome is completely unconstrained, or equivalently, we take P := ((X). We demonstrate in this paper that the characterization of proper and improper learnability are fundamentally different for calluuluee learning of generative models.
We now summarize our main contributions as follows:
Although in practice the model may also depend certain prompts, this can be incorporated via condi- tional sampling. For clarity of exposition, consider this simplified version as in Kalai & Vempala(2122
2

---

Published as a conference paper at ICLR 2025
Agnostic proper learning is impossible. Clearly, a natural question one may ask is why do we need assumptions on the tuple (g. 7) at all. This is a valid argument; for instance, in the context of PAC learning, do not need to make any specific assumptions ation process. Instead, we quantify the goodness of the learner by comparing its performance to the best hypothesis in hypothesis class P. Learnability then reduces to characterizing the complexity of P. We show in Theorem [ Ihat, perhaps surprisingly. such an agnostic compet- itive 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. T) which also applies to other natural variants of non- conlallucinating learning and is of independent interest.
the data gener-
Improper learning is possible and generalizes under VC concept classes. Our second main result is 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 x" never hallucinates (provided the demonstrator is faithful). This is clearly undesirable, since the produced model does not generalize. To resolve this issue, we introduce new measure of generalizability, by requiring that the model contain as much information as the demonstrator, in addition to being non-hal non-hallucinatin. We show in Theorem 2 that if the facts set T lies in a concept class of finite VC-dimension, then non-hallucinating possible with an improper learner that also generalizes to the amount of information of the demonstrator. We further show in Theorem 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-hall non-hallucinating learning with proper learners. We show in Example hypothesis class P and concept class C that are of size two, yet any proper learner must hallucinate. We then iden- tify a sufficient condition on the triplet (g. C, P) in Theorem that allows non-hallucinating learning with proper learner, which is also necessary for certain cases.
Interpretation. Our results demonstrate 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.] 2023). Our work provides a systematic approach to achieving this by restricting the facts set 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 related to the recent theoretical investigation in Kalai & Vempala (0024), which demon- strates that under certain regularity conditions, model that is well calibrated must hallucinate, highlighting the importance of incorporating "factual information" into the learning process. Other impossibility results have also been reported very recently from a computability point of view, such as Xu et al. (2024); |anerjee et al. 2024)). While our impossibility results are in the same spirit, our primary focus to characterize the minimal assumptions under which non-hallucinating learn- ing is statistically possible. Moreover, our formulation and results are grounded in learning the- ory (Shalev-Shwarde & Ben-David, 2014), where we treat the facts itself as a research object, rather than adding ad-hoe constraints. This offers more flexibility in incorporating domain-specific factual constraints, instead of resolving hallucination in a "universal" sense. There has been ex- tensive empirical investigation on understanding and addressing hallucinations, such as factual data enhancement (Dziri et al. 2022], hallucination detection (Manakul et al. 2023), and fine-tuning with human feedback (Ouyang et al. 2022). We refer to surveys by Huang et al. (2023); et al. (2023); Zhang et al. (2023) and the references in Kalai & Vempala (2024) for more extensive discussions. Our work complements these investigations by providing principled view aimed at understand- ing hallucination in learning generative models. Technically, our formulation of non non-haalucinaiig lcarnability is related to distribution PAC learning, investigated in Ashtiani al. (2020); [Bousquet jet al. (2019) 202T). Our lower bounding techniques are rooted in cermatioo-theoretinn methods, such Le Cam's two-point method and Fan's inequality (Polyanskiy & Wu 2022)
3

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
We review this section some notations and concepts from the classical distribution learning lit- erature, and highlight some immediate connections with our non-hallucinating learning paradigm. Let A' be an instance space, and P C ( be a hypothesis class. There exists some (unknown) ground truth distribution q E ( (not necessarily P) that generates a sample x" i.i.d. from The distribution Probably Approximately Correct (PAC) learning problem aims to find learning rule so that the produced distribution Pn, = ((x") satisfies (for some a, e >> 0):
llg PullTV S inf |lg Pl[TV +
pEp
with probability 2 1 - over x q, where TV denotes for total variation distance.
hypothesis class P said to o-agnostic PAC learnable there exists a learning rule such that for any e, > there exists a number n. (sample size) such that, for any distribution q, equation B holds. It can be shown (see e.g. [Bouqquet et al. (2022) that any finite hypothesis class P is 3-agnostic learnable for proper learners. Intuitively, agnostic (proper) PAC learning ensures that the learned distribution's 's total variation distance to the ground truth is as close as possible to the best hypothesis in P that minimizes this distance.
For the non- non-hallucinatin learning paradigm investigated in this paper, we need additionally an (unknown) facts set 'T such that the produced model pr. has small hallucination rate hall(pn, T) as in (T). Clearly, if q is realizable w.r.t. P. i.e. pn ||g - pllTv = 0, then o-agnostic PAC learning implies non-hallucinating learning, as demonstrated in the following fact:
Fact (Realizable learning of implies non-hallucinate learning). For any facts set T and any faithful demonstrator w.r.t. T, if there exists a learner tb such that with probability (w.p.) 2 1
x" q we have [x(x") g||TV then w.p. 1 8 over x" the following holds:
hall( ( (x"), )) S
q{AA]| S c. Therefore, taking A := we have hall(((x")) T) s q/T] + = e, since [ = hall(q, T) = 0 due to faithfulness.
Proof. We have [xx(x") - g/| = sup [xx") [[]]
Fact demonstrates that if the learned distribution is e-close a faithful demonstrator q under tal variation distance, then & is guaranteed to be non- non-hallucinating with a hallucination rate upper bounded by At first glance, this may suggest that non- honhlalluinnting learning is easier than distri- bution PAC learning. However, it is important to note that the requirement for the learned model to be close to the ground truth distribution q 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 guaranteed or verifiable in practice, since the ground truth distribution is unknown.
In fact, as we will show in the following sections, (agnostic) learning the demonstration distribu- tion q is neither sufficient nor necessary to achieve non non-hallucinating learning.
IMPOSSIBILITY RESULTS
In this section, establish several impossibility results for certain natural formulations of agnos- tie (proper) non-hallen haahhallucinaingg learning. Analogous to the a-agnostic (distribution) PAC learning formulation, may consider the following definition:
Definition (a-agnostic non-hallucinating learning). A hypothesis class P C 4(X) is a-agnostic non-ballucinating learnable for some a > 0 there exists proper learner such that for any given 6 > 0, there exists number n, such that for any facts set T and faithful-demoonstran q w.r.t T
Pr iid hall(((xx")
inf hall(p, p, T) 2 S.
PEp
Intuitively, c-agnostic non non-halle hallucinating learnability requires that with high probability (w.h.p.), the learner produce distribution within the class P that has hallucination rate not much higher than
4

---

Published as a conference paper at ICLR 2025
the minimal achievable hallucination rate of P. regardless of how the facts set 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 much weaker condition than learning the distribution @ itself, the following example demonstrates that is impossible even for a hypothesis class with two elements and the minimal achievable hallucination rate is O.
Example 1. Let A, A1. and Ag be disjoint non non-empry sets. We define p1 and Pa to be any distri- butions supported over A1 and A2, respectively. Take P {PI.P2) (2l and q be any distribution supported over A. Now, for any given learner ④ and sample size n, o must produce Pn E P. Therefore, w.p. 3 over the sample x" 4, it will select pr. == pt for some E (1,2). We now (adversarially) select the facts set "T == A AUAAA A3-i- It can be verified that: (1) q is faithful w.r.t. T; (2) hall( T) = 1; and (3) pnp hall(p, T) O. This implies that the learner cannot satisfy Destnition for all e 1, < and a > O. Since the learner & is selected arbitrarily, the class P is not a-agnostic non-hallucinaling learnable for all a > 0.
We mentioned in Section 2 that any finite hypothesis class is 3-agnostic (proper) PAC learnable but Example [ demonstrates a striking distinction between the agnostic distribution PAC learning and the agnostic non-hallucinattin learning.
One may noticed that Example T is fairly pathological, since the constructed distribution q is sup- ported outside of the support of p1 and p2- Therefore, in effect, it provides information for distinguishing between P1 and p2. For this reason, we introduce the following refined definition of hallucination rate relative q. Definition 2 (Relative Hallucination Ratc). For any given distributions p. q. the e-relative halluci- nation rate of P w.E.t q is defined
hall, (p. g) sup p[A] ACx.ofAAEe
Intuitively, the relative hallucination rate (p. g) measures the maximum probability that p signs to a set where the distribution g has a small mass. In other words, the distribution is non- hallucinating relative q if every rare event under q is also rare under p. Observe that, y is faithful w.r.t. some facts set T, then:
VE 2 0. hall(p, T) S hall, (p.
(4)
Therefore, a small relative hallucination rate automatically implies small (absolute) hallucination rate as in (T). However, the converse is generally not true. To see this, consider Example we know that inf peP hal T) 0 while pep hall 9) 1 for all 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 o-smoothness (Haghtalab
al. (022). We say p is o-smooth w.r.t. if A C X we have p|A] < [A), therefore, hall, (p. 9) S for all < 2 0.
We show in the following theorem that seggoosti-noon-aalleiien given a > even for the relative hallucination rate and for a hypothesis class of size 2.
learning is impossible for all
Theorem 1 (Agnostic proper non-hal non-hallucinatig learning is impossible). There exists a hypothesis class P of size such that for any proper learning rule 4, parameter S 1/2 and any sample size n, there exists tuple (g, T) such that for all e < I. with probability > 8 over x"
1. q is faithful w.r.t. T;
2. inf inp hall(p, 7) S inf (p. g) S 2e, i.e., there exists non-hallucinating E P;
3. hol), Z hall( 1, i.e., the learned model hallucinates.
Proof. Let pı be the uniform distribution over A := [0, 0.5], P2 be uniform over A₂ := [0.5, 1] and P = (P1,P2), where (a, b) denotes the interval in the real line from a to b. We now describe a way of selecting (q, T) satisfying the conditions in the theorem statement. To do so, we use a probabilistic argument. Let μn and μ2 be two distributions over the tuple (q. T) such that:
1. For distribution ft, we select the facts set T A U Åς where Åς is (a discrete set) sampled i.i.d. uniformly from Ag with [Ågl > 2n After generating T, take q Y Uni(Ai) + UUn((A2) i.e. w.p. uniform over A₁ and w.p. uniform over Āz;
5

---

Published as a conference paper at ICLR 2025
2. For distribution μzz, we select the facts set T = A2 U A1 where A1 is (a discrete set) sampled i.i.d. uniformly from A with |4ı] > 2n After generating T, we take 1 A2ni(A2) + + Uni((A) interpreted as above.
By construction, we know that the demonstrator is completely faithful w.r.t T, and for any 2+ the following key properties hold:
1. If (q, T) Mi then hall(p1: T) < hall, 4) S 2e and hall,(2a x) 2 hall(p2. 7) = 1;
2. If (q. T) jl then hal T) < hall.(22.) s 2c and (p1. 9) 2 hall(p1. T) 1.
Therefore, the first two conditions in the theorem statement are satisfied.
We take now any 8 f 5 and assume for now that condition 3 does not hold. We have if (g. T)
~ Pl
then (xx") P1 happens w.p. 1 8 2 over the randomness x" qi else if (g. T) μ then (xx") pi happens w.p. S 6 S 3 over the randomness x" ~ q (recall that the learner & must output either p1 or P2 since it is assumed to be proper). For E [1,2], we define the mixture distribution V4 over 2 as described by the outcome of the following Markov process:
f.5.d. from 9
M4 (q, T)
Therefore, we have
||2 - vel|TV = sup 21 (E) 12 2 (22 =
2
3 3'
where F' = {x" E xm +(x") = }1} and the second inequality follows by discussion above.
Note that, the randomness of v/ has two parts: w.p. the sample is uniform over A; and w.p. the sample is uniform over A3-3. The set A3-; is selected uniformly from As- and is of size >> 2n Therefore, conditioning on the event that there is no repetition in sample x", the distribution of x" ~ 1/ restricted on Az-; is exactly the same as sampling i.i.d. uniformly from Az-j. Let E be the event over X so that x" E E has no repetition. We have:
| (- E)
(2 E)][TV =0.
Since we have selected the size |A, 2n for i f1.2), by the birthday paradox Katz & Lindell, This implies that:
2007 Lemma A.9), we have 1n (E) = (2) 2 1 1 4-
|11 - 2/2 TV = vı (B) (B), for some B C X
= vn (B (2(Bn + v1 (Bn E) - (Bn E)
E)) + (B) E) v2 E)), since vI = 122 (E(())lu | - --) E) + (E)lla
= (E)(((( E) -) (B 1B
EE - ---21(-1 E)
1
(n) < 1
3
This contradicts to our previous conclusion that ||p - 12 2 1. thus the presumption that condi- tion 3 does not hold is not true. Therefore, proof of theorem is completed.
Note that, although Theorem T 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 M implies the following corollary that strengthens Example D which shows that agnostic (proper) non hallucinating learning can be harder than agnostic PAC learning, even if the hypothesis class of size and even there exists a hypothesis within class that is not (relatively) hallucinating.
Corollary 1. There exists hypothesis class P of size 2, such that P is not a-agnostic non- hallucinating learnable for any given a 2 0. This is true for both the (absolute) hallucinate rate as defined in 77) and the relative hallucination rate in Definition

---

Published as a conference paper at ICLR 2025
Proof. We only prove the case for the relative hallucination rate, the case for (absolute) halluci- nation rate follows similarly. For any given a > 0, we take e small enough so that c S 20+11 By p hall, q) S 2c. Moreover, by condition of Theorem we have w.p. ô that hall. (+(x") q.) Therefore, we conclude w.p. that:
Theorem condition 2, we have inf,
h ($(x"), ).9) inf hall, (p. 9) 2 a 2 pEP
whenever S 20+T- This violates the
learnability in Definition 1
n
4 NON-HALLUCINATING LEARNING VIA KNOWLEDGE OF T
As demonstrated in Theorem agnostic (proper) non-hallucinating learning is impossible by re- stricting the hypothesis class alone, even when measured competitively (i.e., by comparing with the best model in hypothesis class). This is partially due to the fact that the learner must handle any tuple (g. 7), or in other words, it does not incorporate any prior knowledge of the facts into the learning process. This phenomenon mirrors the "no-free lunch" theorems in the PAC learning literature (Shalev-Shwart & Ben- Ben-David 2014), which assert that learning impossible without as- sumptions 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 finite VC- dimension. This section is devoted to introducing certain natural assumptions on (q. T) that lead to non-trivial resolutions of non-hallucinating learning.
4.1 THE IMPROPER LEARNING CASE
Clearly, if the leaner is improper, then naive non- non-hallucinating learner that simply generates the empirical distribution over the training sample x" never hallucinates. This is clearly not satisfactory. as the learned model is completely non-generalizable. To mitigate this restriction, certain constrains on the facts set T that allow our learned model to "generalize". We assume that T E C. where C C 2 is a concept class of all possible sets that T can be chosen from. Here, the concept class would be determined by prior knowledge of the learner on T.
introduce
To quantify the "generalizability" of the learned model, we introduce an additional notion of infor- mation measure that quantifies the amount of "information" of distributions in A(X):
1: ((X) x X + +R200
Note that, here, we allow the information measure [pp, x") to be dependent on the training set x as well. For any given information measure function 1, we consider the following definition:
Definition 3 (Improper non- hallucinating learnable). For any ? < 1, concept class C is said to be
a-approximately improper non non-hallucinating learnable wrrt. information measure 1, if there exists an (improper) learner &b such that for any c, 5 > 0, there exists a number so that for any T E C and any faithful faithful-demonstne demonstrator q over T, w.p. 2 over x" ~ q the the following holds:
1. The hallucination rate
T) S
2. T(T(x"), (1-7))((1)
Observe that the first part of Definition Jensures that the learned model does not hallucinate, while the second part ensures that the model is as informative as the demonstrator that generalizability is possible. Morcover, it is crucial to note that, although the facts set T is restricted to the concept class C, the demonstrator q is unconstrained, long as it is faithful w.r.t. T.
There are many natural information measures. We mention a few here:
1. For discrete X, Shannon entropy is defined as H(p) = ExEx x p[x] log p(x)* sures the (absolute) information contained p independent of the training set x":
1 which mea-
2. The a-Rényi entropy is defined H.)p) (p) - log (Exexe p(x]s) where > 0 and
a * 1, which subsumes the Shannon entropy for + 1;
3. The out-of- sample mass is defined as (for n 2 1): xp,,x") := p|x') (x).... x,, H. which
measures the amount of probability mass of p assigned outside of the training set.
7

---

Published as a conference paper at ICLR 2025
The specific choice of information measure typically depends on the task at hand. We show in the following theorem, perhaps surprisingly, that improper non- sonnhhaluciiaiing learning is possible if the concept class C has finite VC-dimension, regardless of what information measure is selected.
Theorem 2. If a concept class C has finite VC-dimension, then C is O-approximately (improper) non- hallucinating learnable w.r.t. any information measure function I. Moreover, the sample complexity is upper bounded by O ( (og(1/))+log(//)))
Proof. Let T E C be ground truth facts set and q" be faithfullddemonsrratoo w.r.t T. Let x q² be a set of samples. We define the version space:
C, (T : vi S x, ET].
as the subset of elements in C that are consistent with the sample x". Note that T E C. holds
always, since q" is faithful. For any T C, we say q² e-violates T if hall(q", 7) 2 c. We claim that:
Pix [T E C.. s.t. q' e-violates 7 7 8,
(6)
provided 2. /=loo((/ee))oo//1b/)) for some constant C, where d = VC(C). To see this, we can view the sample x" as feature-label pairs that has all labels being hall(g", T) can be viewed as the population risk of T under the data distribution. Moreover, since qº is faithful. the ground truth set T achieves 0 risk, therefore, the data distribution is effectively realizable w.r.t. C. The claim then follows by standard uniform convergence result of VC class, see
this case, the hallucination rate
e.g. Shalev-Shwartz & Dan-David (2014) Theorem 6.8 (3)).
We now consider the following learning rule:
$ (xx) = arg max {1 )) does not e-violate T, VT E J.
pE)(X)
Note that, f(x") always satisfies condition 1 of Definition 3 since T E Cn and therefore any feasible solution from 7 does not c-violate T Moreover, by (6. w.p. 2 1 - 5 over x" q" that
q² is within the feasible set of (7. Therefore, we have:
I(2(x"), 2 xx",,
by definition of arg max. Thus, condition 2 of Definition 3 is also satisfied with y = O.
Theorem 2 shows that if the facts set T can be specified by neural network with binary outcome (which has finite VC-dimension), then improper learner can yield model that avoids halluci- nations while contains as much information as the demonstrator. This is conceptually analogous approaches in practice, such as Reinforcement Learning from Human Feedback (RLHF), where the reward model can be viewed as a "concept function" that characterizes the facts. However, our approach differs in that our "reward model" is learned solely from the training data without human input. The precise learning rule can be extracted from (7), albeit computationally inefficient.
It is crucial to distinguish our non-hallucinatin learning paradigm in Theorem 2 from the standard PAC learning Schale--Swwrrl & Ben-David 2014)) even though the proof may look similar. This is because, our halluciiiinnn learning framework, the ultimate goal is to produce a distribution (i.e., a generative model) not classification function (i.e., 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 C. This, together with Theorem 2 implies that the VC-dimension remains a meaningful complexity measure that characterizes improper non- non-hallucinating learning.
Theorem 3. For any d E N, there exists a concept class C of VC-dimension d such that for any c > sufficiently small and any 5 < c, the sample complexity of 0-approximately (improper) non- hallucinating learning C w.r.t. out-of-sample mass measure is lower bounded by (
Sketch of Proof. We only sketch the main idea here and refer to Appendix A for complete details. At high level, our goal is to construct, for any d N, concept class C of VC-dimension d that
8

---

Published as a conference paper at ICLR 2025
achieves claimed sample complexity lower bound. This is done by showing that if condition (2) of Definition 3 is satisfied for the sample information measure, then for any training set of size << and any learning rule, the expected hallucination rate must exceed 2c (this constitutes our main technical contribution). Therefore, condition (1) of Definition [ will be violated when taking 5 c. This implies that for any sample size < á. one cannot simulianeousyy satisfy both condition (1) and (2) of Definition 3 thus establishing the lower bound.
Note that, although Theorem 3 proved only for the out-of out-of-samnn oa-samlle mass measure, a similar lower bound can also be established for other information measures. We refer to Appendix [B for lower bound on the Shannon entropy. Moreover, Theorem 33 Jnnly characterizes the sample complexity in the minimax sense, i.c., 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 X' = (U .dd)) .d) where |A] > d; we define class C as the class of all subsets of X that contain A. We have VC(C)= 2 d. However, an algorithm that always produces uniform distribution over A has O hallucination rate and the out-of out-of-sampp sample mass is lower bounded by IAl-n [A] for any sample of size n. Taking = L, one can make the out-of-samppe mass arbitrarily close to 1 by choosing sufficiently large A|.
We would like to point out that any complexity measure on C that characterizes the (improper) non- hallucinating learnability the instance level would necessarily depend on the information measure (for the lower bounds). We leave it as an open problem to find more gine-graindd characterizations tailored to specific information measures, such as for the out-of-sample mass and Shannon entropy.
4.2 THE PROPER LEARNING CASE
We demonstrated in Theorem 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 (x)), we restrict the output to some hypothesis class P C A(X).
We again assume that the facts set T is selected from some concept class C. Let q be any faithful demonstrator w.r.t. T and x ~ A natural learning rule that is inspired from (7) is as follows:
((x") arg max pEP
{I) hall(p, T) S c, VT E C..)
where C. is the version space defined in (5) and / is some appropriately selected information mea- sure. Unfortunately, this (in fact any proper) learning rule fails to achieve non-hallucinating learning even if the minimal achievable hallucination rate of distributions in P is O. This is discussed in the next example.
Example 3. There exist hypothesis class P and concept class C that are of size 2, such that for any proper learner L we can select some T E and faithful demonstrator q w.r.l. T such that Pix [hall( (xx"), T) 0.99] > J. The construction is similar that of Example 7 To see this, we take two sets A1 and A2 of size |A1l = [Ag] = 100 and |A1 n Ag = 1. The concept class C AA,,, A2) and the hypothesis class P {Uni A1), Furtherrrrr we select demonstrator = 8xo for the (single) element X. E A1 n Az. which is faithful for both A and A2. Now, for any learner 4 it must produce Uni(A:) w.p. 2 1/2 for some E [1,2) 2). To satisfy the claimed lower bound, the adversary then simply takes the actual facts set TT to be As-i-
Although the impossibility result of Example iis is not technically surprising, since the demonstrator q effectively produces no "information." It demonstrates a striking distinction between proper and improper learnability of non 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 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 is said to be sufficiently informative for a pair (C,P) if there exists function E: : [0, 1] + [0, 1] such that for any e >> 0
inf sup hall(p, T) S. PEP TECECO
9

---

Published as a conference paper at ICLR 2025
where CEtC) {T E C: Pixva /x & Ti S E(c))
Intuitively, Definition 4 ensures that the pathological instance of Example do not occur for a suf- ficiently small "local neighborhood" Ce(e) of C induced by p. Indeed, equipped with this condition, we can establish the following positive result.
Theorem 4. Let be any concept class of finite VC-dimension and P be any hypothesis class. Then for any T E C and any sufficiently informative
q w.E.. (C,P) as in Definition 4 we have w.p. 2 1 over x" q that for the predictor 4 in (8) satisfies
Pr
T, 2 c) 6
provided 9
DO(VvcC (Cii))oo(1 (GGG)ooo where E(-) is the function in Definition 4 E(e)
Sketch of Proof. The proof essentially follows similar path as Theorem 2 At high level, our goal
to show that, for sufficiently long samples of size n, the version space Cn as in (6) is contained within the "good" neighborhood Cς(e). Therefore, any distribution p the feasible solution of (8)
must satisfy, for all T Cn. that hall(p, T) I e due to Definition 4 The final hallucination rate bound then follows from the fact that the ground truth facts set is within C,.
Note that, the condition in Definition in sense, the minimal requirement achieve proper non-hallucinating learnability. Otherwise, consider any demonstrator q that does not satisfy the condition. There must exist some e that for any & > 0 we have:
inf sup hall(p; T) > TEPTERs
A similar argument as in Example yields that for any proper learner, there must exist some T E Cg so that the hallucination rate > e w.p. 2 P prrovided [Cg] < oo and is small enough.
From a practical point of view, condition p cannot be verified directly, as it depends on the unknown demonstrator q. However, we demonstrated in the proof of Theorem one only needs verify the following condition
inf sup hall(p, 7) S,
PEP TEC.
ensure that the hallucination rate claimed in Theorem 4 holds. This can be verified empirically since Cn depends solely on the training data x" and not on the actual distribution
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 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 learn- ing is achievable by restricting the ground truth facts set to certain concept classes with finite VC- dimension, and determined the tight sample complexity required achieve learnability.
Although our contribution is primarily conceptual, we believe it will help practitioners understand the fundamental limitations of hallucinations in generative models in 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 ( and (8), albeit computationally inefficiently. Our framework lays the foundation for significant future research on mitigating hallucinations in generative models. This includes exploring differ- ent 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.
This work is partially supported by the NSF Center for Science of Information (CSol) Grant CCF-0939370, and also by NSF Grants CCF-2006440 and and CCF-2211422
Acknowledgments.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv preprint arXiv:2303. 08774, 2023.
Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM (JACM), 67(6): 1-2,,,4-22200 2020.
Sourav Banerjee, Ayushi Agarwal, and Saloni Singla. Llms will always hallucinate, and we need to live with this. arXiv preprint arXiv:2409.05746 2024.
Olivier Bousquet, Daniel Kane, and Shay Moran. The optimal approximation factor in density estimation. In Conference Learning Theory, pp. 1188341. PMLR, 2019.
Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. A theory of universal learning. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 532-541, 2021.
Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, and Shay Moran. Statistically near-optimal hypothesis selection. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 909-919. IEEE, 2022.
Nouha Dziri, Sivan Milton, Mo Yu, Osmar Zaiane, and Siva Reddy. On the origin of hallucinations in conversational models: Is it the datasets or the models? In Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz (eds.), Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1271-5285. Seattle, United States, July 2022. Association for Computational Linguistics. doi:
hwwp://.2222.22nlmn..e 2022 maiin.ain... 387
URL https://aclatthollee orq/
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive ad- versaries. In IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 942-953, IEEE, 2022.
Lei Huang, Weijiang Yu, Weitao Ma. Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, al. survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions. arXiv preprint 1.X522231..052.2,, 2023.
Ziwei Ji, Naycon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12):1-38, 2023.
Adam Tauman Kalai and Santosh S Vempala. Calibrated language models must hallucinate. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, pp. 160-171, 2024.
Jonathan Katz and Yehuda Lindell. Introduction modern cryptography: principles and protocols.
Chapman and hal//CRC, 2007.
Potsawee Manakul, Adian Liusie, and Mark JF Gales. Selfcheckgpt: Zero-resource black-box hallu- cination detection for generative large language models. arXiv preprint arXiv:2303.0m 08896, 2023.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to fol- low instructions with human feedback. Advances in neural information processing systems, 35: 27730-27744, 2022.
Yury Polyanskiy and Yihong Wu. Information Theory: From Coding Learning. Cambridge University Press, 2022.
Shai Shalev-Shwartz and Shai Ben-David Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
11

---

Published as a conference paper at ICLR 2025
Changlong Wu, Yifan Wang, Ananth Grama, and Wojciech Szpankowski. Learning functional distri- butions with private labels. In International Conference on Machine Learning, pp. 37728-37744 PMLR. 2023.
Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli. Hallucination is inevitable: An innate limitation of large language models. arXiv preprint arXiv:2401. 2024.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, al. Siren's song in the ai ocean: survey on hallucination in large language models. arXiv preprint arXiv:2309.01229, 2023.
A PROOF OF THEOREM
For any d E N, we take X to be set of size 2d + 1. Let X E X' be any element. We define := (T C X Xo E T and [T] = 1 + d}. is easy to verify that VC(C) = d. We now describe random process for generating (g. T) We first uniformly sample T from C and then define q = (1 - 6')ox + +'' e'Unni(T)(xo) (x for some e' to be determined. Clearly, q is faithful w.r.t T. Let ja be the derived distribution over (g. T). For any given learner t and sample size n S 427- denote Pn T(x"). Our goal is lower bound the expected hallucination rate:
Exr hhall(p,. 7) = ((. hall( (T)))))))) 7),,
where Ex" is over the mixture μ ~ x" and μ x" is the distribution of p conditioning on x".
Denote A {x1,-... } as the set formed by x", and let E' be the event x" such that xo E A d 2 + 1. We now condition the event E occurring. This implies that the out-of-sample
and |A|
mass (q. x²) 5. since [TA 2 and g is uniform when restricted to T((x)), By condition of Definition 3 with 7 = of we have ((nnx")) = ExEX P.. |x] 2 I(q. x") 2 ''/2. Note that the conditional distribution μ x" restricted on T is exactly uniform over C' = (T' EC: ACTACT). We have, for any x & A that
2d
A
2d d/2
3
bo [1 & TH Er [1fx T'H
2d
2d
This implies, for all x" E E that:
plgpT [hall(pn. T)] [TTTTT
LXEX
Σ 1xlx|1[x
2 E<gii>
XEX\A
3
Σ Pa[x] 2
3E'
We now observe that the distribution q assigns only e' probability mass on X' X'x The expected
number of elements in x" not equal to Xo is upper bounded by e'n < $. This implies, by Markov
inequality, that w.p. 2/2 we have A < and xu A, therefore Pr[E] > 2- Putting everything together, we have
E ng (hall( T) Ex Eg (. (hall(fn, T)
36'
2 Ex (E (hall) T)
16
Taking é' e, we have the expected hallucination rate > 2e. Since hallucination rate is < we
have w.p. 2 c, the hallucination rate is > c. Meaning that, for any sample size n < 4 leamerr can achieve both conditions of Definition for 5 < c. This completes the proof.
128 e no
3
We take 7 0 for simplicity, however, our argument holds for general 7 >> well.
12

---

Published as a conference paper at ICLR 2025
B ADDITIONAL LOWER BOUNDS
In this appendix, we provide lower bound for improper non-hallucinating learning when the Shan- non entropy is chosen as the information measure.
Theorem 5. For any number d E N, there exists concept class C of VC-dimension d such that the sample complexity of O-approximately (improper) non-hallucinate learning w.r.t. the Shannon entropy function H is lower bounded by Q((d) for all sufficiently small c, > 0.
Proof. We now take X' = [d] and define C to be collection of subsets of X' such that VT E C, [T] = d/2 and
VTi + T2 EC, 1T S d
It can be shown that such collection exists and |C| Z V Id 4/16, see e.g., (Wu et al. 2023 Thm. D.1) for proof. Moreover, the VC-dimension of C is at most d. For any 7 C,
denote qT as the uniform distribution over T. Now, in order for the Definition 3 hold, for any (T. the learner must produce a distribution P such that: (1) p[T] 2 1 c: and (2) the Shannon entropy (p) 2 log(d/2). We claim that for any other T' E C that differs from T, one must have p pTT' < 1 c, for any I 0.07. To see this, we split the support of P into 3 parts A TAT', T.
A TnT' and A3 [d] [d is clear that ò[Aa] S Assume now that D[T' > 1 1- then one
must have [[A2] 2 - 2e. By expressing the entropy of P conditioning on the A,, A2 and Ag we have
H = Σ (E(1))33)
p[A log P[A.]
1 + M[A]) H( Ad),
(10)
where (Ø A.)) is the entropy of the conditional distribution of p on A, Observe that H(p A1) S. log d/2, (6 A2) S logd/4 and H As) S log d, since uniform distribution maximizes entropy. Moreover, our previous discussion yields that ([ p[Aa] I and p[AA2 [2] 2 1 2e. There- fore, the RHS of (10p is upper bounded by (via Lagrangian multiplier method that the maximum attains on the boundary p{A = p[Ag] = c and O A2 = 2c whenever c S 0.18):
RHS < elogd/2 clog 1 + (1 2c) log d/4 + (1 2c) log
1
elogd clog 1
(1 22)
Contributed by A1
Contributed by As
Contributed As
logg d + 2e log + (1 - 2c) log
+ 3E - 2.
1-26 2e
Sine Hp) 2 log d 1, we have -2e 2e c c- 01 (1- log(1 - 2c) + 2. Rewrite the expression, this implies h(2c) + 5c 2 where h(-) is binary entropy function. Numerical computation yields that this can happen only when e 2 0.07.
Now, the above discussion implics that any successful learner that satisfies Definition with < 0.07 must be able to identify the distribution QT for all T E 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 q as the uniform distribution over [d], the Fano's ' inequality Polyanskiy & (202)) implies that the error probability of the identification problem of sample size is lower bounded by
1
1
sup KL (1q) TEC
log 6.
log [C|
Direct computation yields that KL(gT (7) < log for all T E Therefore, an O(1) error probabil- ity lower bound holds as long as < log [C], i.e., for sufficiently small 5 >> O we have the sample complexity 2 2(log (C]) 2 ((d) since |C] > #7 e/16 discussed above.
13


Reviews:
[{"review_id": "n81yZFs9SS", "reviewer": "Reviewer_fY7z", "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.  \n\nNotes from reading the paper: \n -Hallucinations are outputs which are plausible but invalid.  \n  -Impossible to stop hallucinations using data, but need to leverage inductive biases about facts.  \n  -Paper is purely conceptual, but if claim is valid, seems very striking.  \n  -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.  \n  -A demonstrator q is faithful wrt T if hall(q,T)=0.", "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.", "limitations": "", "rating": 1, "confidence": 4, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "The issue of conceptualizing and theorizing about hallucinations seems like an important and useful problem to address.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b5jzzDpEHK", "reviewer": "Reviewer_mw5f", "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:\n- Proper learning (i.e. restricted to a hypothesis class) without hallucination is impossible.\n- 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.\n- Proper learning with a VC concept class is possible as long as $q$ (the data generating process) is sufficiently informative.", "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?\n- I'm a bit confused by how exactly Example 3 differs from Example 1?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 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.\n- The paper is generally well-written and structured.\n- The construction of the counter-example for Theorem 1 is interesting and clear.\n- Section 4.1 is particularly valuable studying the case of a model that can generalize without hallucinating.", "weaknesses": "- The work could benefit for a more in-depth comparison with Kalai & Vempala (2024).\n- 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.\n- As acknowledged by the authors, the work is mostly conceptual and a first step in this research direction. \n- The messaging on the key takeaways from the paper could be improved (especially for practitioners not particularly interested in learning theory).\n\nNitpicks:\n- The work could do with less italicized words (feels like there's at least 1-2 every sentence).\n- Some typos such as:\n  - Line 245: For the -> the\n  - Line 294: Complited -> Completed\n  - Line 326: Leaner -> Learner", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YOq5XrpkK4", "reviewer": "Reviewer_S3iM", "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.", "questions": "# Questions\n- LL178: Is point (ii) even always possible in principle, i.e., will the learned model always generalize given sufficient training samples?\n\n# Minor suggestions\n- LL65: What is $\\mathcal X^*$?\n- LL130: typo \"being\" → \"been\"\n- 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\n- Eq. 3: $\\| \\cdot \\|_\\text{TV}$ what does this notation mean? I assume based on the paragraph below it is \"total variation distance\"?\n- §1, §2: as far as I can see, the term PAC learning is never introduced\n- LL167: What does \"w.p.\" stand for?\n- LL195: What does \"w.h.p.\" stand for?\n- LL336: Should be \"note that, here, ...\"\n\nGenerally, 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.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 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.\n\nThe paper is thorough in setting up the problem and does a good job of elucidating the importance of its results.", "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DsOKhnez2j", "reviewer": "Reviewer_m9LK", "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.", "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?\n- 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?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 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:**\n\n- the paper's topic is highly relevant, interesting, and the results (seem to be) strong\n- the setup is clear from the introduction (though it's maybe too technical to be placed into the introduction)\n- the technical results have nice intuitive explanations (even for someone who is not an expert in learning theory)", "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.**\n\n### Major points\n- 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)\n- 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.\n\n### Minor points\n- a Figure 1 for an intuitive overview would improve the paper\n- L55: what is an instance space?\n- 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\n- also, though the contributions list is helpful, it is too long to be considered as a \"summary\"\n- L117: \"Our results demonstrate\"\n- Eq (3): please specify what the subscript TV stands for.\n- L160: what does 3-agnostic mean? Does the \"3\" relate to Eq (3) or something else?\n- Fact 1: \n\t- please don't call this a \"simple fact.\"\n\t- what is \"w.p.\"?\n- L195: what is \"w.h.p.\"?\n- 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.\n- L317: what do you mean by \"measured competitively?\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vPi1h8BkVt", "reviewer": "Reviewer_NhVT", "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.", "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?\n2. 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?\n3. Can the framework be extended to evaluate hallucinations across multimodal generative models, such as vision-language models? If so, how would you do that?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper explores the inherent challenges and limitations of achieving non-hallucinating learning, introducing the theoretical impossibility of agnostic proper learning.\n2. 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.\n3. The paper provides upper and lower sample complexity bounds to balance model generalization and non-hallucination.", "weaknesses": "The framework proposed is primarily conceptual, and may need practical guidance for deploying non-hallucinating generative models in real-world applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)