(Im)possibility of Automated Hallucination Detection in Large Language Models

We would like to thank the Reviewer for their comments. We address them below:

The paper lacks any experiments or simulations to support its claims or demonstrate relevance to actual LLM behavior.

Our main focus is to provide a theoretical framework that explains experimental observations in automated hallucination detection for LLMs. Indeed, our results align with these works which show that incorporating feedback in the hallucination detection process leads to much better performance. Thus, we view our paper as complementing these applied works by providing a rigorous mathematical explanation of this phenomenon.

Theoretical insights are not translated into actionable methods or guidance for real-world hallucination detection.

The main theoretical insight is the incorporation of negative examples in the training process of real-world hallucination detectors. Our results indicate that this is a crucial component of the ability to achieve automated hallucination detection.

The contribution is intellectually interesting but may be better suited for a theory venue.

Thank you for brining this up. We would like to point out that the CFP of COLM mentions: "Science of LMs: scaling laws, fundamental limitations, ..., learning theory for LMs" (https://colmweb.org/cfp.html). Moreover, in the first iteration of COLM there were accepted theoretical papers such as https://arxiv.org/abs/2402.08164 which showed a theoretical limitation of LLMs. As we explained, we view the positioning of our paper as the first theoretical framework to explain some of the phenomena observed in experimental papers. Moreover, our abstractions are motivated by a long line of influential work on language identification, and its recent adaptation to the problem of language generation.

We would like to thank the Reviewer for their comments and for finding our framework highly novel. Below we address the points they raised.

The main contribution of the paper appears to be the modeling of a new framework for automated hallucination...

This is very good point to clarify. Our result shows that hallucination detection is as hard as language identification under the precise mathematical framework that we have defined. The (vast majority of) theoretical works provide worst-case guarantees, meaning that the results hold under the assumption that nature behaves in a worst-case way for the algorithm. For example, while most of the interesting optimization problems are NP-hard, there are many practical heuristics that work well on a wide range of instances. Nevertheless, problems that admit a theoretically polynomial-time algorithm tend to admit much faster practical algorithms too, so a theoretical understanding is still useful for practical applications. Our results also have a similar flavor: when there are no negative examples, in theory there are no detectors with good worst-case performance (think of NP hard problems), and when there are negative examples detection is easy (think of problems like shortest path). This is corroborated by applied works which show that when there is no feedback hallucination detection is much harder compared to having feedback. To be clear, our results do not say that hallucination detection rate in practice (without negative examples) should be 0%, they say that this rate cannot be (anywhere close to) 100%. Hence, our results indeed align with practice.

In proving Theorem 2.1..

Thank you for reading the paper carefully. We have provided an example (Lines 178-182) to instantiate the framework. The definitions are, indeed, the same as the Gold-Angluin framework and its recent adaptation by Kleinberg and Mullainathan: $\mathcal{L}$ is the set of languages (for instance, it could be the set of regular languages), $K$ is the target language (the language which specifies exactly what is true -- everything in $K$ is true, everything outside of $K$ is incorrect), and $G$ is the set of strings outputted by the LLM that the detector tests. The detector gets a stream of examples from $K$ and has access to $G$ (it can ask if $x \in G$ for strings $x$). Moreover, the detector knows that $K \in \mathcal{L}$. We have explained the hallucination detection game in line 166-176.

As mentioned in the previous point...

Please see our previous answer. We would appreciate it if you could let us know whether things are clear now. We're also happy to elaborate further.

The paper's second contribution is ...

The main point of this result is to highlight that the conclusion about the feasibility of hallucination detection changes when feedback is incorporated in the training process of the detector. In the current version of the statement, feedback comes in the former of negative examples. This isn't the only type of feedback the algorithm can use in practice, it's merely used to illustrate our results within the theoretical abstraction. Other types of feedback include, e.g., the ability to ask an oracle whether something is correct or not (for a limited amount of times). Such oracles are already implemented in practice, e.g. in the form of RAGs or proof verifiers such as Lean. Moreover, the idea of the result is that by seeing a (finite) amount of labeled data the hallucinator detector is able to identify $K$ and then use this knowledge to implement hallucination detection. Therefore, it isn't as straightforward as directly asking a human annotator for the label of every single output of the LLM. Please let us know if you need further clarifications on this result.

We would like to thank the reviewer for their thoughtful comments. Below we respond to the points they have raised.

The paper may be difficult to fully ... frameworks.

We have tried to make our results accessible to a broad audience that might not be familiar with the Gold-Angluin setting by explaining their informal versions in the Introduction. However, taking the reviewers feedback into account we will make further edits in the next version: we will have explicit informal theorem statements in the Introduction that state the conceptual takeaways of our results, we will further emphasize how our results can inform the design of automated detection methods (see below), and we will elaborate even further on the connections with experimental work. We are very happy to make further edits to make our paper more accessible, if the Reviewer has concrete suggestions.

While the paper provides theoretical justification..

Our model is grounded on a theoretical framework that has been fundamental to Learning Theory and Computational Linguistics, and has gained attention recently due to its adaptation to Language Generation by Kleinberg and Mullainathan. Moreover, we have tried to explain its connection to practical applications in Lines 205-247. If the Reviewer has concrete criticisms about the theoretical model, we would be very happy to try to address them and improve it. Similarly, if the Reviewer has some concrete suggestions for experiments that would help verify the model's assumptions we would also be happy to try to implement them. Moreover, we would like to point out that the CFP of COLM lists papers that show limitation of LLMs and develop theory of LLMs as topics of interest. Indeed, in the first iteration of COLM there were accepted theoretical papers such as https://arxiv.org/abs/2402.08164 which showed a theoretical limitation of LLMs.

Simplified model assumptions..

These are very important points to clarify. Regarding the promptless setting, our main technical result is an impossibility one. Hence, an impossibility result for an easier setting (the promptless one) immediately implies an impossibility result for a more involved one (the prompted setting). We will explain this in the next version of our work. Regarding the adversarial setting, while this might indeed seem like it makes the problem harder, building on technical tools developed by Kalavasis et al. (2025), we can extend it to a statistical setting where there is a distribution over $K$ and the LLM (and the hallucination detector) are trained on i.i.d. samples from the distribution. We have mentioned it in lines 216-222, and we will elaborate further in the next version.

Insufficient coverage of related work... FACTOID: FACtual enTailment fOr hallucInation Detection - https://aclanthology.org/2025.trustnlp-main.38.pdf

Thank you for bringing it to our attention, we will discuss it in the next version. We would like to point out that our main focus is developing a theoretical framework, and, to the best of our knowledge, such a framework does not exist in prior work.

You mention that extending to prompted generation ...

Our impossibility result directly translates to the prompted setting. The positive result, which shows possibility of detection using positive and negative examples also applies when such examples are available for every prompt separately. The main technical hurdle would show up in establishing a positive result which leverages labeled data from some prompt $p$ to decide hallucination under prompt $p'$.

Do you envision that your theoretical results can help guide...

This is a great point. We would our results will further highlight the necessity of feedback in the training process. While for some tasks obtaining feedback might be costly, in other areas such as theorem proving, such feedback is easier to obtain using verifiers such as Lean. Therefore, we would like to see how statements, such as explicitly labeled incorrect proofs, can be further used in training protocols.

Your results assume clean positive and negative examples...

This is also a great question. Our techniques can show a guarantee of the following form: if there are $m$ corrupted examples, then the detector can detect hallucinations up to some accuracy $O(k)$.

Would... validate your theorems numerically?

While something like that could definitely be possible, we aren't sure how it would add value to the paper. Our theoretical results provably hold within the theoretical model, so if we create a set of languages that fall within this model the numerical results will validate our findings. What we believe is more interesting is the fact that our theoretical results under an abstracted model validate the experimental results under real-world models. If the Reviewer sees any value to including such synthetic experiments we would be happy to revisit.

We would like to thank the reviewer for their thoughtful comments and suggestions. We provide answers to their comments below:

The authors' definition of hallucination is unclear. For a better understanding of their argument, the authors should provide a clear definition of hallucination.

We provide the definition of hallucinations in Lines 166-176. Since we work in the promptless model, we identify an LLM with the set of responses it can produce, denoted as $G$ in our paper. We assume there is some target language $K$, which is again a set. If the set $G$ contains any elements outside of $K$ we say that the LLM hallucinates. The interpretation is that $K$ contains all the factually correct statements, and everything outside of $K$ is incorrect. Even under this simplified setting we show that automated hallucination detection is hard.

I believe authors should mention and engage with recent empirical works such as [1], which demonstrates that LLMs are capable of detecting hallucinations without training on explicit hallucination labels.

Thank you very much for pointing out this empirical work, we will certainly discuss in the next version of our paper. The main goal of our work is to introduce the first theoretical framework of automated hallucination detection in order to rigorously argue the capabilities and limitations of detectors. We view our results as theoretically supporting experimental findings, such as the ones in [1]. In particular, this paper shows that the use of RAG systems improves the hallucination detection rate. In the abstraction we have proposed, the use of such systems can be thought of having access to negative examples. Therefore, we view our results as complementing the results of experimental papers from a theoretical point of view. We will elaborate more in the next version of our work.

No concrete claims are made about how this result should inform the design or evaluation of current LLM systems. If their results do not apply to LLMs, which are widely adopted as hallucination detectors in most works, it’s unclear what the practical implications are.

Our results apply to any automated hallucination detection system, therefore they also apply to LLMs as hallucination detectors. The main takeaway message that we hope can inform the design of current LLM systems is the incorporation of negative examples in the training process / hallucination detection process, especially in applications where hallucinations can be very damaging. These negative examples can be provided, implicitly, by external systems such as RAGs. In other applications, such as reasoning models for scientific problems, systems that give negative examples can be implemented by automated proof checkers such as Lean. We will mention this, and related takeaways, in the next version of our work.

While the theoretical contribution is clear, the paper does not provide any empirical experiments to validate its abstractions or show how the theory predicts/model observed behavior in real LLMs. Even a toy experiment or simulation would strengthen the impact.

Thank you for brining this up. As we explained, we view the positioning of our paper as the first theoretical framework to explain some of the phenomena observed in experimental papers such as [1]. Moreover, our abstractions are motivated by a long line of influential work on language identification, and its recent adaptation to the problem of language generation. In terms of providing experiments, for the impossibility result of automated hallucination detection, we aren't sure what experiments would be appropriate since this is a largely negative result. Lastly, we would like to point out that the CFP of COLM mentions: "Science of LMs: scaling laws, fundamental limitations, ..., learning theory for LMs" (https://colmweb.org/cfp.html). Moreover, in the first iteration of COLM there were accepted theoretical papers such as https://arxiv.org/abs/2402.08164 which showed a theoretical limitation of LLMs.

What do you define as "hallucination"? Borrowing terms from [2], is it extrinsic/intrinsic hallucination or factuality? I don't believe it was clearly defined in the paper.

Please see our previous comment. In the terminology of [2], our definition is closer to factuality: there is some target language $K$ that contains all the factually correct statements, at any given point the LLM observes training data from $K$ and we measure whether what it outputs is outside of $K$ or not.

Do your results apply... when LLMs are used as hallucination detectors, but if that's not the case, please clarify further.

Your understanding is correct; our results apply even when LLMs are used as hallucination detectors. While our theoretical result requires explicitly incorrect statements, it is possible to show that other type of feedback, such as the one obtained in RLHF, improves hallucination detection. We will elaborate in the next version.