(Im)possibility of Automated Hallucination Detection in Large Language Models
Authors: Amin Karbasi
Omar Montasser
John Sous
Grigoris Velegkas
Venue: COLM 2025 (2025)
Keywords: hallucinations
theory
RLHF
TL;DR: We propose a novel theoretical model for hallucination detection and show that it is generally impossible to automate this task only with positive examples; however, if we have negative examples, the task becomes much easier.

Abstract: Is automated hallucination detection fundamentally possible?
In this paper, we introduce a theoretical framework to rigorously study the (im)possibility of automatically detecting hallucinations produced by large language models (LLMs). Our model builds on the classical Gold-Angluin framework of language identification 
and its recent adaptation by Kleinberg and Mullainathan to the language generation setting. Concretely, we investigate whether an algorithm—trained on examples from an unknown target language $K$, chosen from a countable collection of languages $\mathcal{L}$, and given access to  an LLM—can reliably determine if the LLM’s outputs are correct or constitute hallucinations.

First, we establish a strong equivalence between hallucination detection and the classical problem of language identification. Specifically, we prove that any algorithm capable of identifying languages (in the limit) can be efficiently transformed into one that reliably detects hallucinations, and conversely, successful hallucination detection strategy inherently implies language identification. Given the notorious difficulty of language identification, our first result implies that hallucination detection is *impossible* for most collections of languages.  

Second, we show that once we enrich the detector’s training data, i.e., providing it with both positive examples (correct statements) and negative examples (explicitly labeled incorrect statements)— the conclusion dramatically changes. Under this enriched training regime, we show that automated hallucination detection is *possible* for any countable collection $\mathcal{L}$.

Our theoretical results, thus, underscore the fundamental importance of expert-labeled feedback in the practical deployment of hallucination detection methods, reinforcing why feedback-based approaches, such as reinforcement learning with human feedback (RLHF), have proven so crucial in improving the reliability and safety of real-world LLMs.

Published as a conference paper at COLM 2025
(Im)possibility of Automated Hallucination Detection in Large Language Models
Amin Karbasi
Omar Montasser Yale University omar wwnnmmontaseer@@y.... edu
John Sous Yale University john. soin.ssos@alle... edu
Yale University
amin. kawbasi@@all..e.. edu
Grigoris Velegkas
Yale University grigoris. veleekas@yyal..ed
Abstract
Is automated hallucination detection fundamentally possible? this paper, we introduce theoretical framework to rigorously study the (im)possibility automatically detecting hallucinations produced by large language mod- els (LLMs). Our model builds the classical Gold-Angluin framework of language identification (Gold, 1967; Angluin, 1980) and its recent adapta- tion by Kleinberg & Mullainathan (2024) the language generation setting. on example
Concretely, we investigate whether an algorithm- from an unknown target language K, chosen from a countable collection of languages L, and given access to an LLM-can reliably determine if the LLM's outputs are correct or constitute hallucinations.
First, we establish a strong equivalence between hallucination detection and the classical problem of language identification. Specifically, we prove that any algorithm capable of identifying languages (in the limit) can be efficiently transformed into one that reliably detects hallucinations, and conversely, successful hallucination detection strategy inherently implies language identification. Given the notorious difficulty of language identifi- cation, our first result implies that hallucination detection is impossible for most collections of languages.
Second, we show that once we enrich the detector's 's training data, i.e., providing it with both positive examples (correct statements) and nega- tive examples (explicitly labeled incorrect statements) the conclusion dramatically changes. Under this enriched training regime, we show that automated hallucination detection is possible for any countable collection L.
Our theoretical results, thus, underscore the fundamental importance of expert-labeled feedback in the practical deployment of hallucination detec- tion methods, reinforcing why feedback-basee approaches, such as rein- forcement learning with human feedback (RLHF), have proven so crucial in improving the reliability and safety of real-world LLMs.
1 Introduction
The recent breakthroughs in Large Language Models (LLMs) have significantly advanced the state-of-the-art in natural language processing and broader machine learning tasks (OpenAl et al., 2024; Team et al., 2024). Contemporary models routinely demonstrate exceptional performance across diverse tasks, including mathematical reasoning, complex problem-solving, and generating coherent, contextually appropriate text (Bubeck et al., 2023; Touvron et al., 2023).
However, alongside these remarkable capabilities, critical limitation has emerged: LLMs frequently produce hallucinations outtut that appear fluent and convincing yet are factu- ally incorrect (Ji et al., 2023). Hallucinations significantly limit the trustworthiness of LLMss,

---

Published as a conference paper at COLM 2025
posing substantial risks when deploying them in sensitive applications, and raising urgent concerns around ethics, reliability, and societal impacts (Weidinger et al., 2021; Zhang et al., 2023; Azamfirei et al., 2023).
A promising approach to addressing hallucinations is the development of automated de- tection mechanisms. Unfortunately, practical attempts to detect hallucinations using LLMs themselves as detectors have faced limitations. Empirical studies indicate that LLMs per- form significantly worse than humans identifying hallucinations, and typically require reliable external feedback-suce as explicit labeling by experts improve (Kamoi et al., 2024a;b). Despite these empirical observations, a theoretical understanding of these practical difficulties has remained open:
Is automated hallucination detection inherently difficult, or can expect it to become easier models improve?
To address this gap, we introduce a formal theoretical framework inspired by classical learning hheory--po particllar the foundational work of Gold and Angluin on language identification (Gold, 1967; Angluin, 1979; 1980), and its recent adaptation to the context of language generation by Kleinberg & Mullainathan (2024). Specifically, we propose novel theoretical abstraction to formally study the feasibility of reliably detecting hallucinations produced by language models. In our model, the hallucination detector is provided with corpus of training data coming from some unknown target language K and is allowed to interact with an LLM, whose outputs we denote by the set G. Conceptually, the language K encodes all statements that are factually correct, while any output outside of K is considered a hallucination. We say that a hallucination detection algorithm is successful if, after observing sufficiently many examples from K and interacting extensively with the LLM, it eventually determines correctly whether or not the LLM produces hallucinations. Formally, this means that if G K, the detector should eventually conclude that the LLM does not hallucinate, whereas if G E K, meaning the LLM generates outputs outside of K, the detector should correctly identify that the LLM hallucinates.
Our first main result formally establishes an equivalence between hallucination detection and the classical problem of language identification, which is known to be inherently challenging (Gold, 1967; Angluin, 1980). The practical implication is summarized concisely below:
Informal Result I. Automated detection of hallucinations by a detector that is trained only on correct examples (positive examples) is inherently difficult and typically impossible without additional assumptions or signals.
Thus, this result provides theoretical justification for the challenges encountered in practice when trying to automatically detect whether an LLM hallucinates.
Given this negative finding, we next examine a more optimistic scenario, inspired both by classical theory (Gold, 1967) and modern empirical approaches (Kamoi et al., 2024a), in which the detector receives both correct statements (positive examples) and explicitly labeled incorrect statements (negative examples). Under these conditions, the outlook changes dramatically:
Informal Result II. Reliable automated hallucination detection is achievable when the detector is trained using both correct (positive) and explicitly labeled incorrect (negative) examples.
This result has an interesting implication for practical attempts to create hallucination detectors: explicit expert feedback, particularly negative examples, is critical and fundamentally necessary for automated hallucination detection to succeed.
Implications for LLM practice. Our framework shows that, with access only to positive examples from the target language, reliable automated hallucination detection is impossible
2

---

Published as a conference paper at COLM 2025
for broad classes of collections; by contrast, providing explicitly negative examples makes detection feasible. This mirrors empirical findings on LLM-based verifiers (Manakul et al., 2023; Azaria & Mitchell, 2023; Kamoi et al., 2024b;a; Tyen et al., 2023; Niu et al., 2023; Sriramanan et al., 2024; Ji et al., 2023; Zhang et al., 2023), which repeatedly observe large gains when verifiers can consult external sources (e-g., RAGs). These retrieval-augmenter tools as the "negative examples" " we require in our positive result. While this analogy is imperfect (real retrieval is incomplete and noisy), the practical takeaway is clear: effective detectors need access to falsification signals, not just additional positive text.
1.1 Related Work
1.1.1
Theoretical frameworks for LLMs
Our proposed framework builds on seminal works in learning theory, including the seminal Gold-Angluin framework (Gold, 1967; Angluin, 1979; 1980) for language identification, and its recent adaptation to language generation by Kleinberg & Mullainathan (2024). Following Kleinberg's 's and Mullainathan's formulation, Li et al. (2024) extended this perspective, using a learning-theore theoretic lens to characterize when " "uniform" " and "non-uniform" " language generation are achievable. Further, recent works by Kalavasis et al. (2025; 2024); Charikar & Pabbaraju (2024) explored notions of generation "with breadth," " demonstrating that this goal is inherently harder than standard language generation, and, in some cases, as chal- lenging as language identification itself. In similar spirit, Peale et al. (2025) formalized and studied a notion of "representative generation," " and showed that it is possible to achieve in the limit for all countable collections of languages. In a complementary direction, Raman & Raman (2025) studied language generation from noisy examples, considering scenarios where training data includes instances outside the target language K. In a concurrent and trade-off based
independent work, Kleinberg & Wei (2025) studied a hallucination- on notion of density of languages. Subsequent work showed that generation need not be closed under finite unions (Hanneke et al., 2025). Diverging from the Gold-Angluin frame- work, Kalai & Vempala (2024) connected calibration in generation increased hallucination rates. Additionally, recent analyses by Peng et al. (2024); Chen et al. (2024) identified fun- damental limitations of transformer architectures. Using techniques from communication complexity, they proved transformers are incapable of composing functions when domains become sufficiently large, providing rigorous evidence for inherent hallucination tendencies in LLMss given that function composition underlies reasoning (Guan et al., 2024). Lastly, Xu et al. (2024) leveraged complexity theory tools to demonstrate inevitable hallucinations in LLMs under certain assumptions. Earlier work by Hanneke et al. (2018) also illustrates the value of using external feedback to mitigate hallucinations of generative models. Our work contributes to this literature which aims to give theoretical insights into the capabilities and limitations of LLMs.
1.1.2 Empirical works on automated hallucination detection
Automated hallucination detection has recently gained significant attention, driven by the practical urgency to mitigate hallucinations. Several empirical approaches have emerged to tackle this challenge. For instance, Manakul et al. (2023) introduce SelfCheckGPT, black-box hallucination detection method that relies solely on stochastic sampling of model responses. The core intuition of their method is that factually accurate responses are typi- cally consistent and frequent, whereas hallucinated outputs tend to vary and contradict each other. In contrast to the black-box consistency-based pose leveraging the internal hidden states of the LLM to classify outputs as hallucinated or factual. Notably, their classifier is trained using an explicitly labeled dataset comprising sen- tences marked as either correct or incorrect, highlighting the benefit of explicitly supervised hallucination detection. Their results significantly outperform wobbbblityddistribttin based methods, illustrating the advantage of internal-state supervision and leveraging annotated datasets to perform this task. Building upon these empirical insights, Kamoi et al. (2024a) conduct a comprehensive evaluation demonstrating the limitations of current LLM-based hallucination detection approaches. In particular, they show that LLMs perform poorly as detectors when evaluating responses generated by other models, emphasizing
method, Azaria & Mitchell (2023) pro-
3

---

Published as a conference paper at COLM 2025
the challenge in using LLMs for automated hallucination detection without robust external signals. Echoing this observation, Tyen et al. (2023) further demonstrate that introducing even minimal human feedback greatly enhances the capability of LLMs to reliably detect hallucinations. Similarly motivated, Niu et al. (2023) illustrate the benefits of fine-tuning LLMs using carefully curated, high-quality labeled datasets containing explicit annotations of hallucinations. This supervised fine-tuning improves hallucination detection perfor- mance and underscores the importance of explicitly labeled negative examples. In another related work Sriramanan et al. (2024), study computational efficient methods for automated hallucination methods in several different cases, including black-box access to the model, white-box access to the model, and access to external databases for validation. Similarly, Rawte et al. (2024) study the usefulness of such databases in detecting hallucinations. For comprehensive surveys on the broad topic of hallucinations in LLMs, including various detection methods discussed above, we refer the interested reader to Ji et al. (2023); Zhang et al. (2023).
Our theoretical findings provide formal validation for these empirical results, clearly high- lighting the crucial role played by explicitly labeled negative examples in successful halluci- nation detection.
Model and Formal Results
2.1
Model
In this section we define the formal model we consider in this work. We denote by = {I,, .. a countable collection of candidate languages, where each language L; is subset of some countable domain X. We assume that we have membership access to the collection &, meaning that for any i E N and x E X we can ask whether x E L,. We allow L to contain multiple occurrences of the same language, i.e. there might exist # j such that L; = L.. Each language L, can have finite or infinite cardinality. We define an enumeration of a language L to be an infinite sequence E = (W1, W2, W3....) such that for all i E IN we have w, L,, and for all E L there is some j IN such that wi = Notice that this allows for repetitions of strings, but, crucially, for any given string x L there is a finite index where this string appears.
We define the hallucination detection game as the following interaction between a learner and an adversary: the adversary picks a target language K E L, an arbitrary enumeration (w,, w2.,..) of K, and target set G S X. We say that G hallucinates with respect to K if it contains elements outside of K, ie.,
g 3 We denote by E, = (w.....,nn w.) the prefix of the first elements of E. In every timestep 1 = 1,2,..., the learner observes W;, asks finitely many membership queries to G, i.e., for finitely many X4, E X it can ask x; E G, and get the correct response. Then, it has to output its guess gr E {0,1) whether G K; it outputs 0 it believes G hallucinates and 1 otherwise. We say that the learner detects hallucinations in the limit if for every target language K &, enumeration E of K, and candidate G C X it holds that after sufficiently long but finite f the guesses of the learner become correct, i.e., there exists some to E IN such that g: = 1 (G C K} AA 2 to. The formal definition is provided below.
Definition (Hallucination Detection in the Limit). Fix some K from the language collection A = L2,.. and some set G C X. The hallucination detection algorithm D = (D)) detects hallucinations for G in the limit if there is some t" E IN such that for all steps t > 8 the detector's 's guess di satisfies di = 1 [G C K}- The language collection E allows for hallucination detection in the limit if there is a hallucination detector that detects in the limit for any E for any G C X, and for any enumeration E of K.
This is because there might be different canonical representations of the same language. 2n the model of Kleinberg & Mullainathan (2024) the languages need to have infinite cardinality; this is not needed in our model.
In the terminology of Bang et al. (2025), this type of hallucination referred as "factuality."
4

---

Published as a conference paper at COLM 2025
To gain some intuition about this model, it is useful to consider simple example.
Example 1. Let X {0,1}* i.e. the set of all binary strings of finite length, and & [L,, L3..... where L; = {s : |s| 2 i) i.e., the i-th language contains all the strings that have length at least i. Notice that every language in this collection is regular. Assume the adversary chooses K Lz, i.e., the language of all strings of size at least 2. Then, it has to present to the learner all these strings, one at a time, potentially allowing for duplicates in the presentation. Crucially, for every string with |w| 2 2, there is some timestep f E IN such that W = s. Consider two potential choices of G : the first choice is G1 = L3 and the
second choice is G2 = 41. In the first case, a successful hallucination detection algorithm should claim, in the limit, that Gj does not hallucinate with respect to K, whereas in the second case it should claim that G2 does hallucinate with respect to K. To give the reader first glance of the difficulty of the hallucination detection task, while we have not stated our main result yet (Theorem 2.1), it is worth pointing out that this result, along with Angluin's 's characterization of language detection in the limit (Theorem A.1), implies that no hallucination detection algorithm exists for this collection.
Identification and generation in the limit. Our model is closely related to the Gold- Angluin language identification setting (Gold, 1967; Angluin, 1979; 1980), and the language generation setting of Kleinberg & Mullainathan (2024). In both of these models there is infinite game between a learner and an adversary: the adversary picks a target K E & and an enumeration of that target; however, unlike these models, the adversary does not pick a target set G S X as happens in our setting. Similar to these models, in every I E N the learner observes a new element from the enumeration. In the identification setting, the goal of the learner is to find an index of the target language K for all but finitely many steps, and in the generation setting the goal is to output unseen elements of K for all but finitely many steps. We present a more formal treatment of these settings in Appendix A. Angluin (1980) exactly characterized when identification in this setting is achievable. Her result is largely viewed as an impossibility result, since a very limited number of collections satisfy it. On the other hand, Kleinberg & Mullainathan (2024) showed that the landscape of generation is vastly different: it is achievable for all such collections.
Connections of theoretical model practical LLM training. At this point, it instructive to pause and consider some common features of these three models; we believe that while they are mathematical abstractions of the practical LLM training process, they capture lot of important aspects of this process. The way to interpret the different languages of the collection L is that they capture different "worlds" and the different elements of X are different "statements." Therefore, each "world" defines precisely which "statements" are accurate and which ones are inaccurate. Admittedly, real-world applications might be more nuanced than that and there could be statements that cannot be easily categorized into accurate or inaccurate ones. Since our model gives a clear taxonomy, it follows that a strong indication that in real-world applications
negative result here can be viewed hallucination detection is even more challenging.
In our model, we consider an adversarial enumeration instead of placing distributional assumptions on the language generation process and the way the outputs of the LLM are generated. While this might look like a restriction of our model at first glance, it turns out that our results carry over to a setting where the data are generated probabilistically; this follows from techniques similar to Kalavasis et al. (2025). We choose focus on the adversarial setting, following the work of Kleinberg & Mullainathan (2024), to make our exposition easier to follow.
Moreover, in all these models the "learner" is given access only to positive examples in the form of elements that belong to the target language. This assumption is capturing the pre-training process of modern machine learning architectures that are trained on large corpus of datapoints that are elements of the target language and are deployed to act at
We underline that do not place the restriction G E L, this is only done illustrate our example.
5

---

Published as a conference paper at COLM 2025
automatic language identifiers, generators or detectors. We also ignore the fact that the training dataset might be corrupted. Again, this simplification is made to ensure that our negative result reflects an innate difficulty of the hallucination detection task and is not artifact of inaccuracies contained in the training data.
Next, notice that in all three settings have discussed so far language identification, language generation, and hallucination detection the algorithm never receives feedback about its guesses. This is also largely consistent with the pre-training phase of the LLM training pipeline.
Furthermore, do not place any computational restrictions on the learning algorithm or the architecture that it relies upon. In fact, we only wish for the detection property to hold "in the limit." " This simplification is again made to ensure that any negative results in the setting reveal inherent difficulties of the underlying task and are not mere limitations of the current technologies or computational resources that might be rectified in the future.
Lastly, we underline that throughout our work we consider a promptless generation setting. Intuitively, this also simplification of the behavior of real-world LLMs, thus negative results in our model should also carry over to applied settings. We emphasize that all these assumptions are largely consistent with prior work on theoretical capabilities and limitations of LLMs (Kalai & Vempala, 2024; Xu et al., 2024; Kleinberg & Mullainathan, 2024; Kalavasis et al., 2024; Charikar & Pabbaraju, 2024; Kalavasis et al., 2025). We believe that our results can be extended to the prompted setting of Kleinberg & Mullainathan (2024), and we leave this as an interesting future direction.
2.2 Formal Results
Given the similarities of the different tasks we have described so far language identification, language generation, and hallucination detection is natural to ask: is hallucination detection easy generation,
hard as identification, or does it lie somewhere in between? Our first main result gives a precise answer to this question; we show that hallucination detection is hard as identification.
Theorem 2.1. A countable collection of languages L= (2, over some countable domain X admits an algorithm that detects hallucinations in the limit if and only if & is identifiable in the limit.
Given result and Angluin's characterization (Angluin, 1980) which we state in Theo- rem A.1, we get the following immediate corollary.
Corollary 2.2. A countable collection of languages & = 1,,, over some countable domain X admits an algorithm that detects hallucinations in the limit if and only if L satisfies Angluin's condition (Definition 4).
Given this largely negative result about the ability to perform automated hallucination detection of LLMs, we next ask what more information is needed by the learner to perform this task. Inspired by Gold's work (Gold, 1967), we consider a modified game termed hallu- cination detection with negative examples. The main difference is that instead of presenting an enumeration of the target language K, the adversary presents an enumeration of the whole domain X along with label in {0,1) indicating whether the enumerated element is in the target language or not. We call this type of enumeration a labeled enumeration. In stark contrast our previous result, we show that hallucination detection with negative examples is always possible. The formal description of this game igiven below.
Definition 2 (Hallucination Detection with Negative Examples in the Limit). Fix some K from the language collection = = L2,.. . and some set G C X. The hallucination detection algorithm D (D: detects hallucinations for G given negative examples in the limit if there is some t* E IN such that for all steps >> t*, the detector's guess d, satisfies d; = 1 1fG C K]. The language collection L allows for hallucination detection with negative examples in the limit if there is a hallucination detector that detects in the limit for any K E L, for any G C X, and for any labeled enumeration E. of X with respect to the target language K.

---

Published as a conference paper at COLM 2025
Having explained the mathematical setting, now ready to state our formal result.
Theorem 2.3. Every countable collection of languages & = (LI, L2..... over some countable domain X admits an algorithm that, given negative examples, detects hallucinations in the limit.
Overview of the Approach
Having discussed our formal setting and results, we now describe the main steps of our technical approach. We start with Theorem 2.1.
3.1 Proof of Theorem 2.1
Our approach here is divided into two main steps. First, we show that we can transform any algorithm that achieves identification in the limit in this setting to an algorithm that detects hallucinations in the limit.
Language identification given below.
hallucination detection. The formal statement of this result
Lemma 3.1. Let L be countable collection of languages over a domain X that is identifiable in the limit. Then, & admits an algorithm that achieves hallucination detection in the limit.
Let now explain the idea of our approach, which utilizes the identification algorithm in black-box way. In every timestep t, the learner feeds the element w, the adversary enumer- ates to the identification algorithm. The identification property (Definition 3) immediately shows that there exists some !" E N (which depends on the choice of the target language K and the enumeration E) such that for all > to the identifier's 's guess i, satisfies and L; = K. The learner next considers an enumeration of the domain X X2, In the i-th step of the execution, the learner uses the membership oracle to check which of the elements X,, belong to the language Li, Subsequently, the learner also queries the target LLM, modeled as the set G, to see which of these elements belong to it. for all x; G it holds that x; Li,, then the guess of the hallucination detection algorithm for this step will be that the LLM does not hallucinate. We present a formal overview of our hallucination detection strategy in Algorithm 1. We now give the formal proof of our result.
i,-1
Algorithm Hallucination Detection from Language Identification
Input: Identification algorithm enumeration (w,, W2,... of K; language collection L (with membership oracle); domain X; LLM output set
1: for 1,2, ... do
2: Feed E =
wi) to to obtain guess it
3: Let k t- Li-
4: Enumerate domain prefix X, (x NX....,x.) xi). for each x E X, do
5:
6:
if E G and x & K then return G hallucinates
7:
8: end if
9:
end for
10: return G does not hallucinate
end for
Proof of Lemma 3.1. First, notice that by definition the identification property, holds that there exists some f* IN (that depends both on the target language and the enumeration) such that for all f 2 t" the output of the identifier satisfies L;, K. Let us now consider any f > Ha. We divide outcomes. First, let us consider the case G C K. Then, for all 2 f" we have that if x; E G then X; E K, for all 1 < is Thus, our algorithm will correctly claim that the LLM does not
analysis into two disjoint cases, which jointly cover all possible
7

---

Published as a conference paper at COLM 2025
hallucinate for all f 2 f*. .Nxt, we consider the slightly more challenging case G g K. By definition, there exists some x E I such that x E G and x & K. Let i* E N be the smallest index in the enumeration of X for which this holds, i.e, Xx+ X, & K. Then, for any t 2 max }t}} when we consider the prefix of the enumeration x1....,XX X the element Xp will be included in this enumeration. Moreover, it holds that L;, = K. Thus, when the hallucination detector tests the element X,,, it will see that Xp- E G and X;+ & K and it will correctly deduce that the LLM G hallucinates. These two arguments conclude the proof. D
Hallucination detection = language identification. We now shift our attention to the more technically intricate result which shows that language identification not harder than hallucination detection. This is also a black-box transformation; it takes as input any hallucination detection algorithm and it constructs an identification algorithm.
Lemma 3.2. Let & be countable collection of languages over domain X that admits an algorithm that achieves hallucination detection in the limit. Then, & is identifiable in the limit.
Before explaining our construction, it is instructive to build some intuition about the diffi- culty of the language identification task. A natural attempt to achieve language identification is to keep track of all the language that are "consistent" with the current set of examples E, the adversary has enumerated, that is the set e₁ = { E & : E, S L} It is not very hard to see that for any language L; that is not (strict) superset of the target language K, there is some timestep 1, such that L, & C, Indeed, since L; D K, there exists some x; which satisfies x; E X; É L4- Thus, when the adversary enumerates x; the algorithm will deduce that L; & e, What happens if L; is (strict) superset of K? Unfortunately, in this case the language L, will always remain consistent with the sample E, Thus, the strategy of keeping track of the consistent languages is not sufficient to guarantee identification in the limit. Indeed, consider Example 1: no matter what the choice the target language K and the enu- meration E of the adversary is, the language L, will always be consistent with the sample E,. Thus, the consistency-based approach is not sufficient to distinguish between Lj.J A 1, and L1- Is there a more sophisticated approach that can overcome this obstacle? The seminal result of Angluin (1980) shows that, unless & satisfies some very strong structural conditions (Definition 4), the answer is largely negative.
The previous discussion highlights that in order to achieve identification in the limit we need to leverage the hallucination detection algorithm to distinguish between languages L; with L; 2 K and the target language K. Our main insight is that the "consistency-basedd" approach and the hallucination detection algorithm work in a complementary way: the former allows us to discard languages that are not (strict) supersets of K, while the latter helps us rule out languages that are (strict) supersets of K. Neither of these approaches is sufficient to be used for language identification on its own, but it turns out that a carefully crafted approach that coordinates their behavior gives the desired result.
We now explain our algorithm in more detail; its formal description is given in Algorithm 2. In each step we create the set e (L: E : E, S L;, < <i f) i.e., the set of the lan- guages whose index is at most t and are consistent with the elements E, that have been enumerated so far. Notice that this can be achieved with finitely many queries to the membership oracle for L.6 Let Li, be the languages of C/. Next, we run copies of the hallucination detection algorithm: the i-th copy is given as input the collection &, the currently enumerated set F,, and the target set L, as the LLM that needs to be tested for hallucinations. Our guess for the target language is the smallest element z' for which Lg C, and ii) the output of the z' z'h copy of the hallucination detection algorithm guesses that L. does not hallucinate. We now give the formal proof.
$In fact, the hallucination discards languages that are not subsets of K. 6n fact, we only need 2t- 1 fresh queries in the 1-th round.
8

---

Published as a conference paper at COLM 2025
Algorithm 2 Identification via Hallucination Detection
Input: Hallucination-deteccion algorithm Dj enumeration E = (wy ......) of target lan- guage K; language collection & (with membership oracle); domain X
1: for 1,2, do
2:
Let E (1,, w2...... 20))
3: Compute the consistent set e = {L: L: E S L: and S f).
4:
for .,, do
5:
Run a copy of D with inputs E and target set L; for f steps, and obtain output di,
where:
{0
{1 if no hallucinations detected,
d; 4
if hallucinations are detected.
6:
end for
7:
Let = (i t: 4 E e, and d; =11
8:
if + Ø then
9:
Let z' min NJ. return
10:
D Output the index of the identified language.
else
12:
return 1.
> We return an arbitrary index and proceed.
end if
14:
end for
Proof of Lemma 3.2. We let E N be the smallest number such that l,
= K.? Our algorithm
outputs the language with the smallest index that satisfies these two conditions we described above. Thus, to get the desired result we need to show that i) all the languages in L
{L, L2, 1 that precede L2 do not satisfy these conditions (for all sufficiently large
f), while the target language Lą does satisfy these conditions (again, for all sufficiently large
t). To that end, we divide &2 into two disjoint subsets: 2? (LE - 2 L3) and
c? = ( L Lz]. In words, - 1 is the set of all languages that precede Lz and are strict supersets it, and 2? is the set of all languages that precede L2 and are not strict supersets of it. Notice that, since L & Gz-11 we have L? - ----1- We now handle these two sets separately.
We first consider the set --1 (L I22. We denote by fig...,,le Li, the lan- 1. By definition, for every such Li, there
guages of this collection, where 0 < k 2-1 exists some element x; E Li, & L.. Moreover, since the adversary presents complete enumeration of L2 there exists some timestep 1t such that Wt, = Xi, (recall that wi, is the element enumerated by the adversary at timestep t.,.)) We define t = maxj<k te. Using the definition of the consistent set et we see that for all 2 1 these languages are not consistent with E,, i.e, .i, Lig & e,.
We now focus on the set - Let Lij....,LL. Lin Lim be the languages of this collection, where 0 < m < zz-1. For any < m consider the execution of the hallucination detection algorithm with imput the collection 4, the enumeration E, and the target set L,. Since E is a valid enumeration of L2 and L, 2 Lz, by definition of the hallucination detection property, there exists some f/, such that for all f 2 t'r the hallucination detection algorithm declares that L; hallucinates. To see that, notice that since L, 2 Lg and the hallucination detection algorithm observes sequence that enumerates all of L2, it must eventually conclude that Lj hallucinates. We define 1 = maxism l/2 It follows that for all f 2 lz the hallucination detection algorithm declares that each .i, Lin hallucinates.
Lastly, let us consider the language Lg. First, notice that for all 2 z we have L e/- Moreover, using the exact similar reasoning as in the above paragraph, there exists some
Recall that language allowed appear multiple times in the collection L.

---

Published as a conference paper at COLM 2025
timestep 1' such that for all t 2 f' the hallucination detection algorithm declares that Lg does not hallucinate. Let f3 = max {
We now have all the ingredients we need to prove our result. We let 1* max { (ti, 22 13)
Consider any 2 f* By definition of L", for any language L,, < 2, either L, & e, or the hallucination detection algorithm with input set L, declares that L, hallucinates, conditions are not simultaneously satisfied for this language. However, both conditions are simultaneously satisfied for La since L2 E e and the hallucination detection algorithm declares that L2 does not hallucinate. Hence, the smallest indexed language that satisfies both of our conditions is indeed Lg. Consequently, our algorithm achieves identification in the limit.
the two
We now note that the proof of Theorem 2.1 is an immediate corollary of Lemmas 3.1 and 3.2.
3.2 Proof of Theorem 2.3
Unlike Theorem 2.1, the technical details of Theorem 2.3 are not as challenging. The full proof of this result given below.
Proof of Theorem 2.3. We first describe the strategy we to achieve hallucination de- tection. Recall that G denotes the set we test, K denotes the target language, and E = (11,y)) (W2, 1/2) ... where y; = 1 {w; K}, Vi I,, in a labeled enumeration of X, i.e. every element x E X appears at some finite position in the enumeration, and its label indicates whether is part of the target language K. In every step 1,2,..., we do the following: For every element in the input stream that appears with a 0 label, i.e, (w, 0) E Es = (1 v1) ,..., (w,, y:)} we check if {w E G} (w,0) F, we declare that G hallucinates. Otherwise, we declare that G does not hallucinate. We now prove the correctness of this strategy. Similarly as before, we divide the analysis into two cases: If G C K, then the above algorithm correctly declares that G does not hallu- cinate in every step t E IN. This is because w & = w & G. If G Z K, we consider an Let i* be the smallest number such that X₃+ E G and X₃- & K. Notice that such an does exist. Moreover, there exists some !" such that (wp,, = (xp, Thus, for this tuple we get yr- 0, and (w, G) 1. Hence, for any 2 1" our algorithm will correctly declare that G hallucinates. This concludes the proof.
},,
1. If this holds for some
enumeration of the domain X X2,
4 Conclusion
In this work, we initiated the formal study of automated hallucination detection by in- troducing a mathematical framework to explore the possibilities and inherent limitations of this task. Our results provide theoretical justification for several phenomena observed experimentally. Specifically, we showed that hallucination detection is typically unattainable if detectors trained solely on positive examples from the target language (i.e., factually correct statements). In stark contrast, when detectors have access to explicitly labeled nega- tive factulll incorrect castements-hallucinaae
detection becomes tractable for all countable collections. These findings underscore the critical role of human feedback in practical LLM training. Several compelling directions for future work remain open. It would be va valuable to quantify precisely the amount of negative examples needed for reliable hallucination detection, and formally explore the computational complexity of the detection problem within our proposed framework. Additionally, investigating whether hallucination detection remains tractable under noisy negative examples, as well as exploring alternative forms of feedback beyond explicit labeling, are promising avenues that warrant further exploration. Finally, inspired by the definition of Kleinberg & Wei (2025) it would be inter- esting to explore whether can achieve more relaxed notion of hallucination detection, where we only wish to detect whether the "frequency" hallucinations greater than some target threshold e 0.
10

---

Published as a conference paper at COLM 2025
Acknowledgments
Amin Karbasi acknowledges funding in direct support of this work from NSF (IIS-1845032, ONR (N00014- 19-1-2406), 2406), and the AI Institute for Learning-Enabled Optimization at Scale (TILOS). Grigoris Velegkas was supported in part by the Al Institute for Gaariin--Enable Optimization at Scale (TILOS)
References
Dana Angluin. Finding patterns common to set of strings (extended abstract). In Proceed- ings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, pp. 130-141, New York, NY, USA, 1979. Association for Computing Machinery. ISBN 9781450374385, doi: 10.1145 011455/00135..00 804406. URL httpp:://oi.. org /000. 1111111//800133 804406.
Dana Angluin. Inductive inference of formal languages from positive data. Informa- tion and Control, 45(2):117-135, 1980. ISSN 0019-9958. doi: https:/ /ttp:////oooorr//01000////
50019-99558800902255-5 URL 500199958889902555.
Dana Angluin. Identifying Languages From Stochastic Examples. Yale University. Department of Computer Science, 1988. URL http://wwww cs, yale. http:/uuliiaainooteeeeeeeeeeeeee tr614.pdf.
Razvan Azamfirei, Sapna R Kudchadkar, and James Fackler. Large language models and the perils of their hallucinations. Critical Care, 27(1):120, 2023.
Amos Azaria and Tom Mitchell. The internal state of an 11m knows when it's lying. Xixiv preprint ar 0tte22304.33734 2023.
Yejin Bang, Ziwei Ji, Alan Schelten, Anthony Hartshorn, Tara Fowler, Cheng Zhang, Nicola Cancedda, and Pascale Fung. Hallulens: Lim hallucination benchmark. arXiv preprint arXiv:2504.17550 2025.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, Harsha Nori, Hamid Palangi, Marco Tulio Ribeiro, and Yi Zhang. Sparks of artificial general intelligence: Early experiments with gpt-4, 2023. URL https: org/ h/g///b//// ab03. 12712.
Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit, 2024. URL https: //axxiv wwtprriwivooogrrr..../ee wtgg/bs////e 15364.
Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer trans- former. Xiv preprint ar Xio:2412.00997,, 2024.
E. Mark Gold. Language identification in the limit. Information and Control, 10(5):447- 474, 1967. ISSN 0019-9958. doi: https: https::/ww..scienedirre. sciencedirect. ctmc
URL
Xinyan Guan, Yanjiang Liu, Hongyu Lin, Yaojie Lu, Ben He, Xianpei Han, and Le Sun. Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 18134, 2024. URL https:tt///// /oii. .twpei..rr//110 1609//aaii. www..6........ 20881..99770.....
Steve Hanneke, Adam Tauman Kalai, Gautam Kamath, and Christos Tzamos. Actively avoiding nonsense in generative models. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31s! Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 209-227. PMLR, 06-09 Jul 2018. URL https://proceedingg mlr. press/v75/hanneke 8a html.
Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. On union-closednesss of language generation. ar Xio preprint ar XrXi::2506.1866/ 18642,, 2025.
11

---

Published as a conference paper at COLM 2025
Ziwei Ji, Nayeon 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 on Theory of Computing, STOC 2024, pp. 160-171, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703836. doi: 0111455361860.34449 3649777.
URL https:://oo..rr//1..155////
Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. Characterizations of language generation with breadth, 2024. URL https: argg/bbs/441/ 18530.
Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. On the limits of language gen- eration: Trade-offs between hallucination and mode collapse. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (S7OC'25), New York, NY, USA, 2025. Association for Computing Machinery. URL
09642.
Ryo Kamoi, Sarkar Snigdha Sarathi Das, Renze Lou, Jihyun Janice Ahn, Yilun Zhao, Xiaoxin Lu, Nan Zhang, Yusen Zhang, Ranran Haoran Zhang, Sujeeth Reddy Vummanthala, et al. Evaluating Ilms at detecting errors in Ilm responses. arViv preprint arXiv:2404.03602, 2024a.
Ryo Kamoi, Yusen Zhang, Nan Zhang, Jiawei Han, and Rui Zhang. When can llms actually correct their own mistakes? a critical survey of self-correction of llms. Transactions of the Association for Computational Linguistics, 12:1417-1440, 2024b.
Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. In Advances in Neural Information Processing Systems, volume 37, 2024. URL https: http:///axxxv...aabbbbeb org/abs/ 2404. 06757.
Jon Kleinberg and Fan Wei. Density measures for language generation, 2025. URL https: //arxiv.org/ 255/ 14370.
Jiaxun Li, Vinod Raman, and Ambuj Tewari. Generation through the lens of learning theory, 2024. URL httpss//aare
/ weriii.org/abbee org/abs//4// 2410. 13714.
Potsawee Manakul, Adian Liusie, and Mark JF Gales. Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models. ar Xiv preprint arXiv:2303.08896, 2023.
Cheng Niu, Yuanhao Wu, Juno Zhu, Siliang Xu, Kashun Shum, Randy Zhong, Juntong Song, and Tong Zhang. Ragtruth: A hallucination corpus for developing trustworthy retrieval-uugmented language models. Xix preprint arXiv:2401 Xii:22401000366, 2023.
OpenAL, Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, ilge Akkaya, Floren- cia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, Red Avila, Igor Babuschkin, Suchir Balaji, Valerie Balcom, Paul Baltescu, Haiming Bao, Mohammad Bavarian, Jeff Belgum, Irwan Bello, Jake Berdine, Gabriel Bernadett-Shapp Christopher Berner, Lenny Bogdonoff, Oleg Boiko, Madelaine Boyd, Anna-Luisa Brak- man, Greg Brockman, Tim Brooks, Miles Brundage, Kevin Button, Trevor Cai, Rosie Campbell, Andrew Cann, Brittany Carey, Chelsea Carlson, Rory Carmichael, Brooke Chan, Che Chang, Fotis Chantzis, Derek Chen, Sully Chen, Ruby Chen, Jason Chen, Mark Chen, Ben Chess, Chester Cho, Casey Chu, Hyung Won Chung, Dave Cummings, Jeremiah Currier, Yunxing Dai, Cory Decareaux, Thomas Degry, Noah Deutsch, Damien Deville, Arka Dhar, David Dohan, Steve Dowling, Sheila Dunning, Adrien Ecoffet, Atty Eleti, Tyna Eloundou, David Farhi, Liam Fedus, Niko Felix, Simón Posada Fishman, Juston Forte, Isabella Fulford, Leo Gao, Elie Georges, Christian Gibson, Vik Goel, Tarun Gogineni, Gabriel Goh, Rapha Gontijo-Lppes, Jonathan Gordon, Morgan Grafstein, Scott Gray, Ryan Greene, Joshua Gross, Shixiang Shane Gu, Yufei Guo, Chris Hallacy, Jesse Han, Jeff Harris, Yuchen He, Mike Heaton, Johannes Heidecke, Chris Hesse, Alan Hickey, Wade Hickey, Peter Hoeschele, Brandon Houghton, Kenny Hsu, Shengli Hu, Xin Hu, Joost
12

---

Published as a conference paper at COLM 2025
Huizinga, Shantanu Jain, Shawn Jain, Joanne Jang, Angela Jiang, Roger Jiang, Haozhun Jin, Denny Jin, Shino Jomoto, Billie Jonn, Heewoo Jun, Tomer Kaftan, Lukasz Kaiser, Ali Kamali, Ingmar Kanitscheider, Nitish Shirish Keskar, Tabarak Khan, Logan Kilpatrick, Jong Wook Kim, Christina Kim, Yongjik Kim, Jan Hendrik Kirchner, Jamie Kiros, Matt Knight, Daniel Kokotajlo, Lukasz Kondraciuk, Andrew Kondrich, Aris Konstantinidis, Kyle Kosic, Gretchen Krueger, Vishal Kuo, Michael Lampe, Ikai Lan, Ieddy Lee, Jan Leike, Jade Leung, Daniel Levy, Chak Ming Li, Rachel Lim, Molly Lin, Stephanie Lin, Mateusz Litwin, Theresa Lopez, Ryan Lowe, Patricia Lue, Anna Makanju, Kim Malfacini, Sam Manning, Todor Markov, Yaniv Markovski, Bianca Martin, Katie Mayer, Andrew Mayne, Bob McGrew, Scott Mayer McKinney, Christine McLeavey, Paul McMillan, Jake McNeil, David Medina, Aalok Mehta, Jacob Menick, Luke Metz, Andrey Mishchenko, Pamela Mishkin, Vinnie Monaco, Evan Morikawa, Daniel Mossing, Tong Mu, Mira Murati, Oleg Murk, David Mély, Ashvin Nair, Reüchiro Nakano, Rajeev Nayak, Arvind Neelakantan, Richard Ngo, Hyeonwoo Noh, Long Ouyang, Cullen O'Keefe, Jakub Pachocki, Alex Paino, Joe Palermo, Ashley Pantuliano, Giambattista Parascandolo, Joel Parish, Emy Parparita, Alex Passos, Mikhail Pavlov, Andrew Peng, Adam Perelman, Filipe de Avila Belbute Peres, Michael Petrov, Henrique Ponde de Oliveira Pinto, Michael, Pokorny, Michelle Pokrass, Vitchyr H. Pong, Tolly Powell, Alethea Power, Boris Power, Elizabeth Proehl, Raul Puri, Alec Radford, Jack Rae, Aditya Ramesh, Cameron Raymond, Fran- cis Real, Kendra Rimbach, Carl Ross, Bob Rotsted, Henri Roussez, Nick Ryder, Mario Saltarelli, Ted Sanders, Shibani Santurkar, Girish Sastry, Heather Schmidt, David Schnurr, John Schulman, Daniel Selsam, Kyla Sheppard, Toki Sherbakov, Jessica Shich, Sarah Shoker, Pranav Shyam, Szymon Sidor, Eric Sigler, Maddie Simens, Jordan Sitkin, Katarina Slama, lan Sohl, Benjamin Sokolowsky, Yang Song, Natalie Staudacher, Felipe Petroski Such, Natalie Summers, Ilya Sutskever, Jie Tang, Nikolas Tezak, Madeleine B. Thomp- son, Phil Tillet, Amin Tootoonchian, Elizabeth Tseng, Preston Tuggle, Nick Turley, Jerry Tworek, Juan Felipe Cerón Uribe, Andrea Vallone, Arun Vijayvergiya, Chelsea Voss, Carroll Wainwright, Justin Jay Wang, Alvin Wang, Ben Wang, Jonathan Ward, Jason Wei, CJ Weinmann, Akila Welihinda, Peter Welinder, Jiayi Weng, Lilian Weng, Matt Wiethoff, Dave Willner, Clemens Winter, Samuel Wolrich, Hannah Wong, Lauren Workman, Sher- win Wu, Jeff Wu, Michael Wu, Kai Xiao, Tao Xu, Sarah Yoo, Kevin Yu, Qiming Yuan, Wojciech Zaremba, Rowan Zellers, Chong Zhang, Marvin Zhang, Shengjia Zhao, Tianhao Zheng, Juntang Zhuang, William Zhuk, and Barret Zoph. Gpt-4 technical report, 2024. www.riiv.ooggbbbee... org/abs/2303. 087744.
URL
Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation, 2025.
Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the trans- 08164.
former architecture, 2024. URL
Ananth Raman and Vinod Raman. Generation from noisy examples. arXiv preprint WwXiv:2501.0417,, 2025.
Vipula Rawte, SM Tonmoy, Krishnav Rajbangshi, Shravani Nag, Aman Chadha, Amit P Sheth, and Amitava Das. Factoid: Factual entailment for hallucination detection. Xrviv preprint XrXiv:2403.19113, 2024.
Gaurang Sriramanan, Siddhant Bharti, Vinu Sankar Sadasivan, Shoumik Saha, Priyatham Kattakinda, and Soheil Feizi. Lim-check: Investigating detection of hallucinations in large language models. Advances in Neural Information Processing Systems, 37:34188-34216, 2024.
Gemini Team, Petko Georgiev, Ving Ian Lei, Ryan Burnell, Libin Bai, Anmol Gulati, Garrett Tanzer, Damien Vincent, Zhufeng Pan, Shibo Wang, et al. Gemini 1.5: Unlocking multi- modal understanding across millions of tokens of context. arviv preprint arXiv:2403.05530, 2024.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023. URL https://arxiv..
http:///axxxiv.ooraa/////// www.obgg////// 13971.
13

---

Published as a conference paper at COLM 2025
Gladys Tyen, Hassan Mansoor, Victor Cärbune, Peter Chen, and Tony Mak. Lims can- not find reasoning errors, but can correct them given the error location. arXiv preprint #rXiv:2311.08516, 2023.
Laura Weidinger, John Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang, Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, et al. Ethical and social risks of harm from language models. arXiv preprint arXiv:2112.04339, 2021.
Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli. Hallucination is inevitable: An innate limitation of large language models, 2024. URL https://arriv.orr/abb//000//
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, Longyue Wang, Anh Tuan Luu, Wei Bi, Freda Shi, and Shuming Shi. Siren's 's song in the ai ocean: A survey on hallucination in large language models, 2023. URL https: / /arxiv.... www.w..wg/aaa.iaee..o...wweeee.e wtgggbb//309..0000 01219.
14

---

Published as a conference paper at COLM 2025
A Preliminaries
Building on the foundational work in learning theory by Gold (1967) and Angluin (1988), Kleinberg & Mullainathan (2024) introduced rigorous framework for language generation. In this model, the domain X is a countable set, and the target language K is an unknown subset of X.
A.1 Language Identification in the Limit
The problem of language identification in the limit from positive examples was introduced by Gold (1967) and further studied by Angluin (1979; 1980). For a fixed collection &, an adversary and an identifier play the following game: The adversary chooses language K from L without revealing to the identifier, and it begins enumerating the strings of K (potentially with repetitions) W1, w2,... over sequence of time steps 1,2,3,.... The adversary can repeat strings in its enumeration, but the crucial point is that for every string E K, there must be at least one time step i at which it appears. At each time the identification algorithm I, given the previous examples W1, W2...., Wt, outputs an index it that corresponds to its guess for the index of the true language K. Language identification in the limit is then defined as follows.
Definition 3 (Language Identification in the Limit (Gold, 1967)). Fix some K from the language collection L = 12,12 ). The identification algorithum = (4) identifies K in the limit if there is some t* E IN such that for all steps t > 1* the identifier's 's guess i, satisfies = and L,, K. The language collection L is identifiable in the limit if there is an identifier that identifies in the limit any K for any enumeration of K. In this case, we say that the identifier identifies the collection L in the limit.
Angluin's 's seminal result (Angluin, 1980) proposed a condition that precisely characterizes which collections are identifiable in the limit. Definition 4 (Angluin's Condition (Angluin, 1980)). Fix language collection & [I,, L2,...) }. The collection & is said to satisfy Angluin's condition if for any index i, there is
tell-tale, i.., a finite set of strings T₁ such that Ti is subset of Li i.., T; C Li, and the following holds:
For all 2 1, if 2 Tú, then Lj is not proper subset of Li.
Further, the tell-tale oracle is primitive that, given an index i, outputs an enumeration of the set Ti.
Formally, Angluin (1980) showed the following result.
Theorem A.1 (Characterization of Identification in the Limit (Angluin, 1980)). language collection & is identifiable in the limit if and only if it satisfies Angluin's 's condition.
Perhaps surprisingly, this result shows that language identification is impossible even for simple collections.
A.2 Language Generation in the Limit
Using the same game-theoretic setting as Gold (1967), Kleinberg & Mullainathan (2024) proposed modification of this game where the objective of the learner is to generate unseen elements of K instead of guessing its index.
Definition 5 (Language Generation in the Limit (Kleinberg & Mullainathan, 2024)). Fix some K from the language collection L {L,, Lz,... } and a generating algorithm G = (Gi). At each step t, let E, C K be the set of all strings that the algorithm G has seen so far. G must output string we & E, (its guess for an unseen string in K). The algorithm G is said to generate from K in the limit if, for all enumerations of K, there is some 1* IN such that for all steps 1 > 1", the algorithm's guess we belongs to KV Et (or K Et is empty). The collection & allows for generation in the limit if there is an algorithm G that, for any target K L, generates from K in the limit.
Note that for the problem of language generation to be interesting, the languages of the collection & must be of infinite cardinality. The main result of Kleinberg & Mullainathan
15

---

Published as a conference paper at COLM 2025
(2024) is that language generation in the limit is possible for all countable collections of languages.
Theorem A.2 (Theorem with the property that for any countable collection of languages & [,,,1,, 12..,, }. any target language K L, and any enumeration of K, the algorithum generates from K in the limit.
Kleinberg & Mullainathan (2024)). There a generating algorithm
16


Reviews:
[{"review_id": "TNLUEBXclR", "reviewer": "Reviewer_T4oz", "summary": "The paper demonstrates a theoretical framework to analyze automatic hallucination detection in LLMs by adapting Gold-Angluin language identification framework. The authors provide two fundamental results: First, hallucination detection is equivalent, in terms of difficulty, to language identification, which is known to be impossible for most languages due to Angluin's characterization. Second, they show that introducing negative examples (incorrect statements with labels) changes the landscape, making hallucination detection possible.\n\nThe model formalizes hallucination detection as determining whether an LLM's output set G is contained within a target language K (correct statements).", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "The paper provides a well-formulated theoretical result grounded in classical learning theory, bringing formal tools to the hallucination detection problem.\n\nThe equivalence between hallucination detection and language identification in the limit is cleanly presented.\n\nThe paper offers conceptual insight into why human feedback may be necessary for effective hallucination detection.", "reasons_to_reject": "The authors' definition of hallucination is unclear. For a better understanding of their argument, the authors should provide a clear definition of hallucination.\n\nI 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.\n\nNo 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.\n\nWhile 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.\n\n[1] Sriramanan, Gaurang, et al. \"Llm-check: Investigating detection of hallucinations in large language models.\" Advances in Neural Information Processing Systems 37 (2024): 34188-34216.", "questions_to_authors": "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.\n\nDo your results apply if the detector is implemented via an LLM — for instance, if one uses a naive pretrained model such as Llama-3.1 8B Base, or an instruction-tuned model such as GPT4o, Llama-3.1 8B Instruct acting as a verifier for another model's answer using zero-shot prompting? I want an explanation on both situations, since the former case is only trained on large text corpora, without data specifically labeled as \"incorrect examples\". Also, I believe even instruction-tuned models aren't likely to be trained with data that you define as \"incorrect examples\" (explicitly labeled incorrect statements). Of course, they would have gone through post-training process such as SFT, RLHF or DPO, but I don't think the widely-used negative samples used in such process (e.g., negative examples in preference pairs used for such process in datasets like [3]) can account for what you state as \"incorrect examples\". So based on my understanding, your results should apply even when LLMs are used as hallucination detectors, but if that's not the case, please clarify further. \n\n[2] Bang, Yejin, et al. \"HalluLens: LLM Hallucination Benchmark.\" arXiv preprint arXiv:2504.17550 (2025).\n[3] Cui, Ganqu, et al. \"ULTRAFEEDBACK: Boosting Language Models with Scaled AI Feedback.\" International Conference on Machine Learning. PMLR, 2024.", "extra_scores": {}}, {"review_id": "UGSjMF1RVx", "reviewer": "Reviewer_TJ7A", "summary": "This paper develops a rigorous theoretical framework to address a core open question in the safety and reliability of LLMs: is it fundamentally possible to automatically detect hallucinations without external supervision? Drawing on foundational work in learning theory, particularly Gold’s language identification and Angluin’s characterization of identifiability in the limit, the authors establish a key impossibility result: hallucination detection is equivalent in difficulty to language identification in the limit. This implies that for most practical settings, hallucination detection is not possible using only positive examples (i.e., correct statements). However, the paper also presents a positive result showing that when detectors are trained with negative examples (i.e., explicitly incorrect statements), hallucination detection becomes theoretically tractable. The work ties together deep theoretical insights with empirical observations and offers a valuable perspective on the design and limitations of current hallucination mitigation techniques such as RLHF.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "`Strong theoretical grounding:` Establishes a rigorous equivalence between hallucination detection and language identification.\n\n`Practical relevance:` The impossibility result explains real-world challenges in hallucination detection; the possibility result justifies existing RLHF-style methods.\n\n`Bridges theory and practice:` The paper draws meaningful connections between formal learning theory and empirical LLM behavior. The proofs are sound, and the writing is careful and thoughtful.", "reasons_to_reject": "`Accessibility:` The paper may be difficult to fully appreciate for those unfamiliar with formal models of learning, particularly Gold’s and Angluin’s frameworks.\n\n`Limited empirical validation:` While the paper provides theoretical justification for existing empirical findings, it does not directly verify its model's assumptions with empirical data or ablations.\n\n`Simplified model assumptions:` The adversarial and promptless setting is appropriate for theoretical clarity but limits direct applicability to real-world LLM deployments.\n\n`Insufficient coverage of related work:` Overlooks relevant prior research on automated hallucination detection - FACTOID: FACtual enTailment fOr hallucInation Detection - https://aclanthology.org/2025.trustnlp-main.38.pdf", "questions_to_authors": "- You mention that extending to prompted generation is a future direction. Could you speculate on the technical hurdles in doing so, and whether the current impossibility result would still apply in that context?\n\n- Do you envision that your theoretical results can help guide future architectures or training protocols? For instance, could your framework inspire new methods of automated feedback generation?\n\n- Your results assume clean positive and negative examples. How sensitive is the hallucination detection guarantee to noisy or adversarially labeled training data?\n\n- Would it be possible to empirically simulate a version of your theoretical framework (e.g., using synthetic languages) to validate your theorems numerically?", "extra_scores": {"ethics_concerns_details": "NA"}}, {"review_id": "zdBUvPHPqp", "reviewer": "Reviewer_ypnG", "summary": "This paper proposes a theoretical framework for evaluating the feasibility of automated hallucination detection in large language models (LLMs), grounded in the classic Gold–Angluin paradigm from language identification and its extensions to language generation. It formalizes the hallucination detection task and demonstrates that detection is generally infeasible when training relies solely on positive examples. However, the analysis shows that detection becomes viable with access to both positive and negative labeled data, offering theoretical support for practical detection approaches.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "1. The mathematical proofs in the paper are complete.\n2. The paper presents a novel insight into automated hallucination detection in LLMs.", "reasons_to_reject": "Although the paper presents a highly novel framework and method for automated hallucination detection in LLMs and provides mathematical proofs, I have some doubts about certain details of the ideas due to the slight disorganization in the language of the paper. These doubts can be summarized as follows:\n1. The main contribution of the paper appears to be the modeling of a new framework for automated hallucination detection in large language models (LLMs) by extending the classic Gold–Angluin framework from language identification and its variants in language generation. The paper uses this framework to demonstrate that, in an unsupervised and label-free manner, LLMs cannot achieve automated hallucination detection by being fed only positive examples. It also shows that this capability can be realized through positive and negative labeling based on human feedback (e.g., the yi in Definition 2.3 on line 397 of the paper). However, the reality is that, although line 45 of the paper mentions that current state-of-the-art LLMs like Claude and GPT-4 have hallucination detection capabilities far below that of humans, this does not mean that LLMs are incapable of judging whether other LLMs or themselves have generated errors in some areas of knowledge. Some recent papers have already revealed the reflective ability of LLMs to mitigate hallucinations. Therefore, disregarding the underlying proof process entirely, I am skeptical about the correctness of the conclusions drawn in the paper. In fact, the models mentioned above are not necessarily the most advanced models in the industry. Whether the premise \"no language identification algorithm exists,\" which the proof of Theorem 2.1 relies on, still holds under the current hallucination detection capabilities of LLMs is also questionable.\n2. In proving Theorem 2.1, the paper first demonstrates Lemma 3.1 and Lemma 3.2, establishing the equivalence between the existence of a hallucination detection algorithm and the existence of a language identification algorithm within the classic Gold–Angluin framework. I question whether there is a conceptual sleight of hand occurring here. Does the L and G used for the hallucination detection algorithm and within the classic Gold–Angluin framework for language identification truly represent the same things? After reading the paper carefully, I still have not found the answer I seek: detailed definitions and explanations of L and G in the real-world context of hallucination detection. Therefore, readers are left to define them based on their own understanding as specific knowledge or semantic spaces, which may or may not align with the definitions mentioned in the classic Gold–Angluin framework.\n3. As mentioned in the previous point, the paper equates the infeasibility of automated hallucination detection in LLMs with the non-existence of a hallucination detection algorithm within the Gold–Angluin framework (where hallucination is defined in the paper as the existence of elements in the generated G that are outside the language K), without providing a detailed explanation of how they are equivalent. This involves detailed interpretations of the abstract concepts L, G, K, and so on, in the context of hallucination detection. Since the paper lacks explanations on this crucial point, I believe there is still a significant gap between the paper's logic and its conclusions. This also makes the overall content of the paper rather abstract. This is not directly related to the strong theoretical nature of the research content or the focus on mathematics, but rather a result of the paper's complete omission of relevant descriptive details.\n4. The paper's second contribution is to demonstrate that hallucination detection algorithms can be achieved through positive and negative labeling based on human feedback. However, as I understand the paper, it seems that these labels directly point to whether something belongs to a certain language or not (for example, the y_i in Definition 2.3 on line 397 of the paper). This appears to directly replace the condition for the existence of a language identification algorithm in the proof of Theorem 2.1 with a human conclusion about whether something belongs to K (whether there is a hallucination). So, what is the point of using an LLM to automatically detect hallucinations? The previously mentioned weakness of LLMs in detecting hallucinations was in the context of directly judging the text. If humans have already labeled parts of the text as incorrect, LLMs should be fully capable of recognizing that the generation is erroneous. If the authors cannot further elaborate on the real-world correspondences of the concepts mentioned in the conclusions of Theorem 2.3 (and how they correspond to RLHF), this conclusion seems entirely meaningless to me.", "questions_to_authors": "See weaknesses.", "extra_scores": {}}, {"review_id": "fOYG9iFwA2", "reviewer": "Reviewer_zwtc", "summary": "This paper formalizes the task of hallucination detection in LLMs by framing it as a language identification problem. It proves that reliable detection is impossible with only positive (correct) examples, but becomes feasible when negative (incorrect) examples are available. The results are grounded in classical learning theory and offer a theoretical justification for the importance of feedback-based methods like RLHF.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "- This paper provides a novel theoretical framing of hallucination detection via language identification.\n\n- The authors prove formally that negative examples are necessary for reliable detection, aligning with empirical trends.\n\n- The paper is generally well-written.", "reasons_to_reject": "- The paper lacks any experiments or simulations to support its claims or demonstrate relevance to actual LLM behavior.\n\n- Theoretical insights are not translated into actionable methods or guidance for real-world hallucination detection.\n\n- The contribution is intellectually interesting but may be better suited for a theory venue.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper offers a clear, theoretically grounded answer to whether (one theoretical framing of) hallucination detection can be automated: under the classic Gold-Angluin model, detection without negative examples is as hard as language identification and thus impossible in the worst case, while even sparse labeled negatives make it tractable, conceptually explaining why feedback-rich methods like RLHF help. As is common in such theoretical results, there may exist a gap between "hallucination detection" as is empirically measured on finite benchmarks, and the theoretical claims on the most general case.    

Reviewers split (6, 6, 6, 5), with concerns about abstraction, lack of experiments and practical conclusions, yet they acknowledge the validity of the proofs, a novel framing, and alignment with empirical trends. After engaging in the discussion, the lowest scores rose, and clarifications showed how the framework maps to real-world detectors (e.g., RAG supplying negatives, thus not contradicting the theoretical results). Remaining weaknesses are absence of empirical validation and accessibility to non-theorists, but the contribution fits COLM’s "fundamental limitations" scope well. Overall, I support acceptance provided the camera-ready version adds concrete examples, better framing with respect to current detection work, and a brief empirical sanity check to aid audiences that are less theoretically-leaning.
Decision: Accept