We thank the reviewer for acknowledging our contributions, as well as for providing the detailed review. We now address the main questions:

1. Incorporating inductive biases in practice: As we have shown in Theorem 2, non-hallucinating learning is possible by restricting the concept class to a class with finite VC-dimension. This demonstrates that if the "non-hallucination" set can be described by a neural network, then an improper learner can construct a model that avoids hallucinations, while generalizing to the information provided by the data distribution. This is analogous to approaches in RLHF, where the reward model can be viewed as a concept function that characterizes what is "hallucination." 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.

2. Complexity measures: We would like to clarify that having a finite VC-dimension is not a stringent requirement, since for any neural network with a binary outcome and any reasonable activation function (such as ReLU), the VC-dimension can be upper-bounded by the size of the network. However, it is quite possible that there might be tighter complexity measures that characterize the sample complexity (such as Rademacher complexity). Since our paper is an initiation of this broad study, we have elected to use the VC-dimension as it is more natural and well-understood. As we have pointed out in our paper, investigating other complexity measures particularly tailored to the specific information measure would be of significant interest for future research.

3. Extending to other scenario: The primary purpose of our paper is to provide a clear exposition of understanding the fundamental challenges in learning a non-hallucinating model. To this end, it is beneficial to start with the simplest and clearest model to get the intrinsic insight. However, we believe it would be interesting to investigate various extensions to other scenarios, including incorporating context and dealing with multimodal models.

We thank the reviewer for appreciating our contributions, as well as for providing the detailed review. We now address the main questions:

1. Clarify abbreviations: We have clarified the abbreviations in the revised paper and removed the "simple/clear/easy to verify" statements where appropriate.

2. Clarity of Proof: We thank the reviewer for the suggestion. We have moved the proof of Theorem 3 to the appendix and replaced it with a proof sketch. Additionally, we clarified the proof sketch of Theorem 4 with a more intuitive argument. Please refer to the parts highlighted in teal in the revised paper. We hope this clarifies the high-level proof ideas.

3. Minor points: We thank the reviewer for the suggestions; we have incorporated them in the revised version as appropriate. We clarify some of the key points below:

   • The instance space in our context means all sentences (i.e., all finite sequences of tokens).

   • For the introduction, we appreciate the reviewer's suggestion. We include the formal setup in the introduction to provide sufficient information for the reader to quickly understand the "real" problem we address in the paper, which is a common practice in theoretical papers.

   • TV stands for Total Variation distance.

   • "3-agnostic" means that $\alpha = 3$ in Eq (3).

   • "w.p." stands for "with probability."

   • "w.h.p." stands for "with high probability."

   • In Example 1, statement (1) follows from the fact that $q$ is supported solely on $A$ and $A \subset \mathcal{T}$; (2) follows from the adversarial selection of $\mathcal{T}$; and (3) follows because the distribution $p_i$, which differs from $\hat{p}_n$, must have a hallucination rate of 0.

   • "Measured competitively" means that we do not quantify the hallucination rate absolutely for the learned model but compare it to the best model in a hypothesis class.

Questions:

1. We apologize for the confusion. In our formulation, the "facts set" is what should be considered the "non-hallucination set," which consists of all sentences excluding both "plausible but wrong" and "clearly wrong" sentences. Please note that our result does not rely on the exact definition of what "hallucination" means semantically; instead, our result aims to characterize the learnability of relating the "hallucination" in the learned model to that in the training data. We have revised the abstract from "plausible but invalid" to "not grounded in the underlying facts".

2. Comparison to Locatello et al. (2019): Indeed, the requirement of "inductive bias" is common in many machine learning paradigms, such as the disentangled representation learning in Locatello et al. (2019). What is unexpected (perhaps surprisingly) in our result is that we demonstrate that non-hallucinating learning is "strongly impossible" even when measured competitively (i.e., by comparing to the best model in a hypothesis class), which contrasts with classical PAC learning.

We thank the reviewer for appreciating the significance and relevance of our work, as well as for providing the detailed review. We now address the main questions:

1. Clarity of Writing: We thank the reviewer for the suggestions. We have added additional discussions as recommended and clarified some of the technical proofs in our revised version (highlighted in teal). Specifically, we included a discussion after Theorem 2 on the relationship of our approach with RLHF and added an explanation after Theorem 4 on how to verify the conditions stated in Definition 4 empirically. We hope this clarifies how our theoretical results can be interpreted in practice.

Questions:

1. The impossibility of point (ii) in LL178: Indeed, this point precisely highlights the challenge of requiring the model to generalize to the demonstration distribution under total variation. This is precisely the reason that motivated us to define generalizability via the "information measure" in Definition 4, rather than through PAC learning under total variation. Please note that in Definition 4, the learned distribution is not necessarily close to the demonstration distribution under total variation.

2. Minor suggestion: We are grateful to the reviewer for catching the typos; they have been fixed in the revised version.

We thank the reviewer for appreciating the novelty and significance of our work, as well as for providing the detailed review. We now address the main questions:

1. Comparison with Kalai & Vempala (2024): The negative result of Kalai & Vempala (2024) is mostly comparable to our Theorem 3, which shows a lower bound on the hallucination rate based on the notion of "calibration" of the learned distribution. Here, "calibration" can be viewed as a different way of quantifying the "generalizability" of the learned distribution. In our work, we define generalizability via the concept of information measure maximization. Technically, however, our lower bound is not directly comparable to theirs.

2. Sufficient informativeness of $q$ in Section 3: Indeed, any given instance $q$ constructed in Theorem 1 is sufficiently informative if we specify the concept class as all the possible $\mathcal{T}$ constructed therein. To see this, we observe that if $q \sim \mu_i$, then $p_i\in \mathcal{P}$ always satisfies the condition in Definition 4 for $\xi < \frac{1}{2}$. The reason why Theorem 1 does not contradict Theorem 4 is that the concept class used in Theorem 1 has an infinite VC-dimension.

3. Key takeaways: The main message we would like to convey is that there can be inherent limitations in learning a non-hallucinating generative model, even when the entire training set is non-hallucinating. This limitation is inherent in the sense that it is independent of the exact form of how one defines "hallucination". Therefore, one should not expect to find a "universal" solution and should instead focus on integrating factual information itself into the learning process.

Questions:

1. Indeed, for larger classes, the impossibility result may not hold. For instance, if we take $\mathcal{P}$ to be the class of all distributions, we reduce to the improper learning case. However, it is presently unclear to us how the transition occurs with respect to the size of the class.

2. Technically, Example 1 and Example 3 are nearly identical, with the only difference being the emphasis on the concept class size.

3. We thank the reviewer for identifying the typos; they have been corrected in the revised version.

We respectfully disagree with the reviewer's assessment of our work. The reviewer seems to have two main concerns: (i) the theoretical nature of our contribution, and (ii) that our formulation does not fully capture the semantic meaning of "hallucination." Regarding the first concern, our theoretical treatment, is, in fact, a key strength of our paper – we establish fundamental limitations on hallucination that are independent of empirical design choices and implementations. Concerning the second point, we would like to clarify that our formulation of the "facts set" is precisely what should be considered a "non-hallucination set," which is a general concept regardless of one's definition of "hallucination." Our work does not aim to characterize the semantic meaning of "hallucination"; rather, it focuses on establishing the inherent statistical limits of learning a non-hallucinating model that relies solely on the training sample, without external definitions of what constitutes "hallucination."

To set the stage for our discussion, we reiterate our main contributions as follows:

Our results reveal several inherent statistical challenges of learning non-hallucinating models, such as Example 1 and Theorem 1, which demonstrate that even in a class with only two models, a universal learner cannot learn a non-hallucinating model even if one exists in the class. This is a significant conceptual contribution (as acknowledged by reviewers S3iM and mw5f), showing that a non-hallucinating model cannot be learned "agnostically", in contrast to the standard PAC model. Additionally, we provide several approaches for incorporating "factual" information into the learning process to enable non-hallucinating learning. For example, Theorem 2 shows that if the "non-hallucination" set can be specified by a neural network, then an improper learner can learn a model that avoids hallucinations while generalizing to the information provided by the data distribution. This is analogous to approaches in RLHF, where the reward model can be viewed as our "concept function" that characterizes what is "hallucination." However, our approach differs in that our "reward model" is learned solely from the training data without human input. This is a significant contribution, as it puts forth a systematic approach with rigorously provable guarantees for non-hallucinating learning that relies solely on training data yet generalizes.

We now address the specific points raised:

Q1: The paper seems extremely flawed. First, it is a purely theoretical paper, with no analysis or experiments, even on toy models.

A1: We strongly disagree with this claim. As acknowledged by all other reviewers (mw5f, S3iM, m9LK, NhVT), our paper presents novel, significant, and insightful theoretical results that advance the understanding of non-hallucinating learning within a rigorous theoretical framework. Our findings are derived through rigorous theoretical analysis and proofs, and we find the assertion that our paper is "extremely flawed" to be inappropriate. Historically, ICLR has accepted a large number of theoretical contributions – this is not an acceptable reason for rejecting a paper.

Q2: 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.

A2: As stated in our paper, our primary contribution is conceptual, aiming to understand the fundamental limits of non-hallucinating learning in a principled manner (i.e., invariant to specific experimental setups). Our work provides a comprehensive theoretical investigation, which we believe will be valuable to the ICLR community. Our theoretical analysis is completely sound (i.e., with rigorous proof) and novel (i.e., previously unexplored). This is a core strength of our paper.

Q3: 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.

A3: Indeed, our analysis does not rely on any specific semantic definition of "hallucination"; this is the key novelty of our paper, as it enables us to analyze non-hallucinating learnability "relatively" that relies solely on the training data. However, our results do depend on the definitions of a "non-hallucinating model." We provide two characterizations using the concept of "hallucination rate" (which is agnostic to the semantic meaning of "hallucination"), specifically, the absolute and relative hallucination rates. Our proofs rely heavily on these definitions of "hallucination rate."