Please summarize the following article: 
Hallucination has been widely recognized to be a significant drawback for large
language models (LLMs). There have been many works that attempt to reduce the
extent of hallucination. These efforts have mostly been empirical so far, which
cannot answer the fundamental question whether it can be completely eliminated.
In this paper, we formalize the problem and show that it is impossible to eliminate
hallucination in LLMs. Specifically, we define a formal world where hallucination is defined as inconsistencies between a computable LLM and a computable
ground truth function. By employing results from learning theory, we show that
LLMs cannot learn all of the computable functions and will therefore always hallucinate. Since the formal world is a part of the real world which is much more
complicated, hallucinations are also inevitable for real world LLMs. Furthermore,
for real world LLMs constrained by provable time complexity, we describe the
hallucination-prone tasks and empirically validate our claims. Finally, using the
formal world framework, we discuss the possible mechanisms and efficacies of
existing hallucination mitigators as well as the practical implications on the safe
deployment of LLMs.
1 Introduction
The emergence of large language models (LLMs) has marked a significant milestone in the field
of artificial intelligence, particularly in natural language processing. These models, with their vast
knowledge bases and ability to generate coherent and contextually relevant text, have greatly impacted
research, industry, and society. However, one of the critical challenges they face is the problem of
“hallucination,” where the models generate plausible but factually incorrect or nonsensical information.
This issue has brought increasing concerns about safety and ethics as LLMs are being applied widely,
resulting in a growing body of literature trying to classify, understand, and mitigate it.
Prior works have identified multiple possible sources of hallucination in LLMs from the data collection
to the training and inference aspects. For example, in the survey paper [29], the authors attribute
hallucination in natural language generation to heuristic data collection, innate divergence, imperfect
representation learning, erroneous decoding, exposure bias, and parametric knowledge bias. A
plethora of methods have been proposed to mitigate hallucination. For example, factual-centred
metrics [19, 20, 40, 57] and benchmarks [34, 35, 65] have been proposed to measure and reduce
hallucination on specific datasets. Retrieval-based methods reinforce LLM by knowledge graphs
or databases to help correct factual errors in models’ outputs [57, 76]. Prompting the models to
reason [69] and verify [13] their answers has also been shown to reduce hallucination.
Up to now, research on LLM hallucination remains largely empirical. Useful as they are, empirical
studies cannot answer the fundamental question: can hallucination be completely eliminated? The
answer to this question is fundamental as it indicates a possible upper limit of LLMs’ abilities. HowPreprint. Under review.
arXiv:2401.11817v1 [cs.CL] 22 Jan 2024
ever, since it is impossible to empirically enumerate and test every possible input, formal discussion
on this question is impossible without a clear definition and formal analysis of hallucination.
In the real world, formally defining hallucination, a factual or logical error of LLM, turns out to be
extremely difficult. This is because a formal definition of semantics in the real world is still an open
problem [12, 58]. Hence in this work, we rigorously define a formal world of computable functions,
wherein precise discussions on hallucination is feasible. In this world, hallucination occurs whenever
an LLM fails to exactly reproduce the output of a computable function. Under this definition, we
present a fundamental result that hallucination is inevitable for any computable LLM, regardless of
model architecture, learning algorithms, prompting techniques, or training data. Since this formal
world is a part of the real world, the result also applies to LLMs in the real world.
Based upon the theoretical results, we identify some formal problems in which real-world LLMs are
likely to hallucinate and empirically verify this identification. The theoretical and empirical results
lead to our discussions on their practical implications on proper usage of LLMs.
The contribution of this paper is summarized as follows:
• We formally define and discuss hallucination for LLMs and, by employing results in learning
theory [2, 3, 18, 28], we show that hallucination is inevitable for LLMs.
• Empirical study shows that state-of-the-art LLMs are hallucination-prone in some real-world
problems, which validates the theoretical results.
• We discuss practical implications of our theoretical results on the design of hallucination
mitigators and deployment of LLMs in the real world.
2 Related Works
Recent years have seen a growing interest in exploring hallucination in LLMs. This section offers a
concise overview of pertinent studies in the field. For an extensive review of hallucination in LLMs,
readers are directed to recent surveys [24, 29, 37, 46, 66].
2.1 Classification of Hallucination
Hallucination in language models is typically classified either phenomenally or mechanically. The
former approach classifies hallucination based on outcomes, while the latter focuses on training and
deployment methodologies. This section addresses the phenomenal classification and we will discuss
the mechanical classification in Section 2.2.
A conventional classification of hallucination is the intrinsic-extrinsic dichotomy [14, 25, 29, 75].
Intrinsic hallucination occurs when LLM outputs contradict with the provided input, such as prompts.
On the other hand, extrinsic hallucination occurs when LLM outputs cannot be verified by the
information in the input. Huang et al. [24] extends this dichotomy by introducing faithfulness
hallucination, which takes user instructions into account and includes instructional, contextual, and
logical inconsistencies. Rawte et al. [52] divided hallucination into “factual mirage” and “silver
lining”, denoting erroneous outputs based on factually correct or incorrect inputs. Each class is
further divided into intrinsic and extrinsic subclasses, and further decomposed into cases such as
acronym ambiguity and geographic erratum.
2.2 Causes of Hallucination
Hallucination has been generally attributed to issues in data, training, and inference stages as identified
in existing surveys [24, 29]. Issues in the data include poor quality [31], misinformation [35], bias [41,
47], and being outdated [33, 43] knowledge. Moreover, a fair portion of knowledge in the wild is
long-tailed, making it challenging to recall during deployment [30, 38]. During training, the model
could suffer from architectural and strategic deficiencies which hinder proper learning. For instance,
exposure bias [4] is a well-known problem that results from an inconsistency between training and
inference caused by teacher-forced training strategy [50]. Attention mechanism, a key component of
transformer-based LLMs, can also contribute to hallucination [36], possibly because attention across
tokens is diluted as the sequence length grows [10, 22]. During inference, hallucination can also be
2
caused by sampling randomness [1, 14], insufficient context attention [55], and softmax bottleneck [9,
73].
2.3 Mitigating Hallucination
The mitigation of hallucination involves tackling its underlying causes. For data-related issues,
solutions include fact-focused datasets [17, 21] and developing automatic data cleaning techniques [42,
51, 54]. Retrieval augmentation, which uses relevant external documents to ground LLMs, can
help reduce knowledge gap and reduce hallucination [57, 76]. Prompting techniques like Chainof-Thought [69] and Tree-of-Thought [74] have been applied to improve knowledge recall and
reasoning [67]. To mitigate training-related hallucination, architectural improvements and training
objectives are proposed. For example, sharpening softmax functions [36] can tackle the issue of
diluted attention. Factuality-enhanced training objectives [32, 56] have been shown to improve
the model’s ability to associate facts and produce logical outputs. To overcome inference-related
hallucination, new decoding methods are introduced to improve factuality or faithfulness of LLMs.
Factual-nucleus sampling, proposed by Lee et al. [32], aims to balance the diversity and the factuality
in model outputs. Chain-of-Verification, introduced by Dhuliawala et al. [13], prompts the LLM to
self-correct their mistakes during generation.
3 Definitions
In this section, we detail our definitions of LLMs, hallucination, and training and deployment of
LLMs under the hallucination context. While we will define hallucination in a small formal world,
we will generalize our definition for LLMs as much as possible. Readers are referred to Section A
for a Table of Notation.
3.1 Large Language Model
We start with the basic definitions for our alphabet and strings:
Definition 1 (Alphabet and Strings). An alphabet A is a finite set of N tokens A =
{a0, a1, . . . , aN−1}. A string is a sequence w0w1 . . . wn−1 obtained by concatenating tokens
for n times, where wi ∈ A.
Tokens are atomic symbols used to construct strings. For real-world LLMs, token are usually
unique combinations of alphanumerical characters. An LLM is a probabilistic model of a string that
conditions the output at time t based on all the tokens that come before it in the string. Formally, the
likelihood of string w0w1 . . . wn−1 is represented as
p(w0:n−1) = p(w0)
nY−1
t=1
p(wt|w0:t−1), wi ∈ A, n ∈ N. (1)
The most common usage of LLM is to complete a partial string w0w1 . . . wq−1, or a “prompt”, into a
complete string w1w2 . . . wn, by maximising the likelihood of the complete string:
p(w0:n−1) ∝ p(wq:n|w0:q−1) =
nY−1
t=q
p(wt|w0:t−1), wi ∈ A, q, n ∈ N, q < n. (2)
As the equation suggests, such completion occurs iteratively, one token at a time. In practice, the
iteration stops after a fixed number of iterations, or when a special stopping token is generated.
State-of-the-art LLMs [6, 45, 60, 61] are generally implemented using the Transformer architecture,
which is a multi-layer feedforward network equipped with attention mechanism [64]. The “large” in
LLM describes both the scale of the models, which is usually billions of parameters, and the size of
training corpora, which is usually trillions of tokens [45, 61]. An LLM is trained with the objective
that the output string w1:n resembles the real-world corpora and is coherent and reasonable. Common
training procedures include (1) unsupervised pretraining where LLMs are trained to complete strings
from general corpus auto-regressively, (2) supervised finetuning where the pretrained LLMs are
finetuned on training samples for specific tasks, and (3) reinforcement learning where human feedback
3
is put as training signals. We will discuss the formal definition of training samples in Section 3.2 and
a general training procedure in Section 3.3.
To facilitate more general discussions, we now ignore all the implementation details to build an LLM,
e.g., the probabilistic model in Equation (1) and (2), and only focus on its input and output. We put
a single assumption on LLMs: an LLM is a function h which, given any finite-length input string
s = w0:q−1, outputs a string of tokens h(s) that completes s within a finite time. This assumption is
true for any LLM proposed so far and is more general than any specific LLM. Formally, we define
the large language model as:
Definition 2 (Large Language Model). Let S be a computable seta of all the finite-length
strings of alphabet A and (s0, s1, . . .) be an one-to-one enumeration of all the elements in S. A
large language model, denoted h, is a function that completes the input string s ∈ S using the
function’s predicted tokens h(s), in a finite time. Function h is attained procedurally using a set
of training samples of input-completion pairs.
aA computable set [62] is a set whose membership can be decided by a computable function in a finite
time. By this definition, the set of all corpora of natural language is a computable set.
Based on this definition, all possible LLMs are total computable functions [5] on S, which means
that all of them produce output for any input s ∈ S in finite steps. Furthermore, all real-world LLMs
have provable properties, such as (a) they are all total computable by design, or (b) they all complete
their computation in polynomial time. To formally describe these properties, we define LLMs with
properties provable by some algorithm P:
Definition 3 (P-proved LLMs). Let P be a computable algorithm that takes in a function and
returns “true” only if the function has a specific property (e.g. total computable or polynomialtime complexity) of a function. Then a P-proved LLM is an LLM in Definition 2 which can be
proved by P to have the specific property in finite steps.
Following the definition, P-proved LLMs form a proper subset of all LLMs. This classification is
important for our further discussion about LLMs’ limitations, where we will view LLMs as a subset
of total computable functions. Different from general total computable functions, LLMs can be
categorised by the desirability of its outputs along a spectrum. On the “nonsensical” side is a clueless
token predictor which produces meaningless completion of input strings s. On the “ideal” side, a
hallucination-free function completes any well-formed input strings into a sensible and factual string.
In between are the real-world LLMs: their outputs are comprehensible most of the time; however,
they occasionally “hallucinate” and generate nonfactual statements. This spectrum, along with the
relation between LLMs and total computable functions, is shown in Figure 1.
Large Language Models
Total Computable Functions
(Works, with hallucination)
Clueless
Token Predictor
(Nonsensical)
Ideal LLMs
(Always truthful)
-proved Computable LLMs
Existing LLMs Figure 1: Illustration of LLMs and their relation with computable functions. The “ideal” side of
spectrum is shown as dashed lines because it is not attainable by any LLMs and therefore does not
exist in the set of LLMs, as will be shown in this paper.
4
3.2 A Formal World and Hallucination
Hallucination is in essence an erroneous output produced by an LLM. Without getting tangled in the
difficult problem of formalising “correctness” in our real world, we define hallucination in a formal
world where all we care about is a computable ground truth function f on S. In other words, in our
formal world, f is the ideal function that produces correct completion f(s) for any input string (or
prompt, question, query, etc.) s ∈ S.
Definition 4 (Formal World of f). A formal world of ground truth function f is a set Gf =
{(s, f(s)) | s ∈ S}, where f(s) is the only correct completion of input string s, for all s ∈ S.
For example, f could be a function that answers “true” for factual statements and “false” for
non-factual ones. It could also be a function that completes a prompt to produce a factual statement.
We only assume that such computable f always exists (though its exact implementation might be
unknown) in our formal world for all tasks. Otherwise, we can immediately say LLM will hallucinate
on some tasks in the formal world because LLM is computable while the ground truth function f is
not. We can similarly define Gh = {(s, h(s)) | s ∈ S} to be the world of LLM h.
The training samples T can be defined as a set of input-output pairs we get from the formal world.
Definition 5 (Training Samples T ). Training samples T is a set
{(s0, y0),(s1, y1), . . . ,(si
, yi), . . . | si ∈ S, i ∈ N, yi = f(si)}.
Set T is a generalized corpus of how ground-truth f answers/completes input strings. For example, if
f answers “true” for factual inputs and “false” otherwise, then our training samples could look like {
(“A shark is a mammal.”, “false”), (“Earth orbits around the Sun.”, “true”), ... }. On the
other hand, if f is a function that completes or answers input string s, then T could look like {
(“Is shark a fish or mammal?”, “Fish.”), (“What is the sum of binary numbers 10001 and
10110?”, “100111.”), ... }. Thanks to this general definition, we do not need to worry about the
exact task and corpus on which an LLM is trained. Furthermore, we do not assume anything about the
size of T , meaning the training procedure to be introduced in Section 3.3 can use as many samples
as needed.
With the ground truth f introduced, it is straightforward to define hallucination in the formal world as
when a trained LLM fails to fully reproduce the output of ground truth function f. Formally:
Definition 6 (Hallucination). An LLM h is hallucinating with respect to a ground truth function
f, if ∃s ∈ S such that h(s) ̸= f(s).
With this definition, hallucination is no longer related to correctness or factualness in the real world.
It is simply an inconsistency between the formal world of a ground truth function Gf and that of an
LLM Gh. There are three possible relations between Gf and Gh:
• Total hallucination: Gh ∩ Gf = ∅, where the LLM hallucinates on all s ∈ S.
• Some hallucination: Gh ∩ Gf ̸= ∅ and Gh ̸= Gf , where LLMs hallucinates on some s ∈ S.
• Hallucination-free: Gh = Gf , which is an ideal LLM that is hallucination-free w.r.t. f.
Venn diagrams showing the relation between Gh and Gf for the three cases above are shown in
Figure 2.
Gh Gf
(a) Total hallucination.
Gh Gf
(b) Some hallucination.
Gh = Gf
(c) Hallucination-free.
Figure 2: Venn diagrams showing possible relations between Gh and Gf .
5
3.3 Training an LLM
In the formal world, using our definition of hallucination in Definition 6, the core question of whether
hallucination can be eliminated can be translated to:
Definition 7 (The Fundamental Question). For any ground-truth function f, using training
samples T , can an LLM h be trained such that ∀s ∈ S, h(s) = f(s)?
We are not interested in the training and deployment details like initialisation of parameters, selection
of optimisers, learning rates, objective functions, stopping criteria, inference hyperparameters (e.g.,
temperature,) and so on, and wish our discussion to be independent of these factors. Therefore, we
lump together all the factors and call it a “training and deploying” procedure. In this procedure, an
LLM h is iteratively updated by training samples. We only check the output of the LLM during
deployment, when the stopping criteria are met and the training procedure stops.
The workflow of training an LLM h is the following iteration: a (batch of) training sample1
is taken
from T , then h is updated by the training procedure using the training sample. This repeats until the
training procedure stops. The final updated h will produce an output h(s) to complete any test string
s. Formally:
Definition 8 (Training and deploying an LLM). An LLM h is trained and deployed by the
following procedure, whose implementation must be computable:
• Inputs:
– A streama of training samples T = ((s0, f(s0)),(s1, f(s1)), . . .).
• Output: trained LLM h
[i]
for some i ∈ N, which is expected to be equal to f.
• Procedure:
1. Let h
[0] be the LLM with randomly initialised model parameters.
2. Let i = 0.
3. Training and Validation Iteration:
(a) If stopping criteria are met (LLM is ready): end iteration, goto step 4.
(b) Retrieve a training sample (si
, f(si)) from T .
(c) Update LLM h
[i]
to h
[i+1] according to {(sj , f(sj )) | j ≤ i}.
(d) Let i ← i + 1, go to step 3a.
4. Deployment: Let h = h
[i] be the final trained model. End the procedure.
aWe put training samples in a stream because we assume no limitations on their numbers.
There are a few notes about this procedure:
• In step 3a, traditional stopping criteria include reaching a preset number of training iterations
and when loss value stops improving. The procedure above is more permissive because we
do not assume any criterion, meaning the training can take arbitrarily many samples and
use arbitrarily long time. Nevertheless, it must eventually stop and use a final LLM for
deployment. Otherwise, it will loop infinitely and break the computability assumption.
• As a result of this procedure, h
[n]
is a particular state of LLM h in which it is trained on
samples {(si
, f(si)) | i < n}. In particular, h
[0] is an LLM state in which h is initialized but
never trained. In practice, we always deploy an LLM in a particular state. Therefore, when
there is no ambiguity, both h and h
[n] will be referred to as “LLM”.
• The LLM can be expected to: (i) answer f(s) =?, or (ii) given “(s,” complete it with “f(s))”,
or (iii) given “is it true that f(s) = t ?” answer “yes” or “no”. For ease of presentation and
without loss of generality, we assume case (i), where LLM uses h(s) to answer the question.
1
It does not matter whether an iteration uses a sample or a batch of samples. We assume it uses a sample
every iteration for the ease of presentation.
6
The Real World
(Hard to define)
The quick brown fox jumps over the lazy dog.
The lazy fox jumped over the brown dog.
...
Corpus Training Samples     
until stopping criteria are met
update
(a) (b)
(c) (d)
The Formal World
(Defined by computable    )
Initial LLM
Training
Input
Trained LLM
Deployment
Subset of
Check for
Hallucination
Figure 3: Illustration of relations between all concepts defined in Section 3. (a) shows the real-world
corpus, which is a superset of (b) the formal world of ground truth function f and training samples T .
(c) shows the procedure that trains LLM h as defined in Definition 8, which takes training samples
and updates h until the stopping criteria are met. Finally in (d), the trained LLM is deployed and
produces output given an unseen string s. Hallucination is defined by comparing LLM’s answer h(s)
with ground truth value f(s).
Up to now, we have defined everything needed for further discussion: LLM, hallucination in the
formal world, and a general training procedure which allows us to ignore the learning details. An
illustration showing the relations between all these definitions is shown in Figure 3. We would like to
highlight that our definition entails not only Transformer-based LLMs, but all the computable LLMs
and common learning frameworks. Moreover, LLMs trained by the procedure in Definition 8 are far
more powerful and flexible than their counterparts in the real world. Therefore, if hallucination is
inevitable for our LLMs in the relatively simple formal world, then hallucination is inevitable for
LLMs in the more complicated real world.
4 Hallucination is Inevitable for LLMs
In this section, we show that hallucination is inevitable in the formal world by suitably applying results
in learning theory literature. Specifically, we will use the diagonalization argument in our proof. The
diagonalization argument was originally used to prove that some infinite sets (e.g., the set of real
numbers) are larger than others (e.g., the set of natural numbers) by Cantor [8, 15]. The high-level
idea is to show that any enumeration of an uncountable set is not exhaustive by constructing a counter
example that is in the set but not in the enumeration [70]. The argument gets its name because such
counter example is constructed by flipping the diagonal elements, i.e., the i
th component of the i
th
element, in the table showing the enumeration.
This section is organized in a restricted-to-general manner, where we first discuss less complex LLMs
resembling real-world ones and then generalize to any computable LLMs. First, we show that all
LLMs in a (enumerable) set of P-proved LLMs will hallucinate on some inputs (Theorem 1). Such
provability constraint limits the complexity of LLMs, however, it helps us discuss concrete examples
of hallucination-inducing problems. Then, we remove the provability constraint and show that all
LLMs in a computably enumerable set will hallucinate on infinite many inputs (Theorem 2). Finally,
we show that hallucination is inevitable for all computable LLMs (Theorem 3). At the end, we will
answer the fundamental question posed in Definition 7.
7
Table 1: Illustration of diagonalization for the proof of Theorem 1. Each row represents a particular
LLM. Each column represents a string si with which the LLM is tested. A value in the j
th column of
i
th row represents hˆ
i(sj ). Blue cells are the outputs that we use to construct f, on which the LLM in
the corresponding row will hallucinate.
Test Samples
LLMs
s0 s1 s2 s3 s4 · · ·
hˆ
0 hˆ0(s0) hˆ
0(s1) hˆ
0(s2) hˆ
0(s3) hˆ
0(s4) · · ·
hˆ
1 hˆ
1(s0) hˆ1(s1) hˆ
1(s2) hˆ
1(s3) hˆ
1(s4) · · ·
hˆ
2 hˆ
2(s0) hˆ
2(s1) hˆ2(s2) hˆ
2(s3) hˆ
2(s4) · · ·
hˆ
3 hˆ
3(s0) hˆ
3(s1) hˆ
3(s2) hˆ3(s3) hˆ
3(s4) · · ·
hˆ
4 hˆ
4(s0) hˆ
4(s1) hˆ
4(s2) hˆ
4(s3) hˆ4(s4) · · ·
· · · · · · · · · · · · · · · · · · · · ·
f ∆(hˆ0(s0)) ∆(hˆ1(s1)) ∆(hˆ2(s2)) ∆(hˆ3(s3)) ∆(hˆ4(s4)) · · ·
4.1 Computably Enumerable LLMs will Hallucinate
We first use the classic diagonalization argument to show that LLMs will inevitably hallucinate, with
an assumption that LLMs are not only total computable, but are P-proved to be total computable
(see Definition 3). As we will discuss later in this section, P can be used to restrict the complexity of
LLMs, leading to useful corollaries about their limitations for real-world problems.
The P-provability assumption is important because we cannot enumerate2
the set of total computable
functions3
and thus cannot apply the classic diagonalization argument (which requires a table of
enumeration). However, we can enumerate the set of P-proved total computable functions using P
as the enumeration algorithm. The provability assumption is true for LLMs because, by design, all
LLMs (so far) will output an answer in finite time for any finite input string.
With this assumption, we use the diagonalization argument to prove the following theorem:
Theorem 1. For the set of LLMs {h0, h1, . . . | hi proved by P to be total computable.}, there
exists a computable ground truth function f, such that all h
[j]
i
, i, j ∈ N, will hallucinate.
Proof. Consider the set of LLMs: {h0, h1, . . . | hi proved by P to be total computable. }. An LLM
hi
in this set can be trained on no (zero) training sample, one training sample, two training samples,
and so on, resulting in its different states {h
[0]
i
, h[1]
i
, . . . , h[j]
i
, . . .}, i, j ∈ N. To facilitate the diagonalization argument, we want to use one index variable for all the states of LLMs. Therefore, using
the Cantor pairing function [7], we re-enumerate these LLM states as {hˆ
0, hˆ
1, . . . , hˆ
k, . . .}, where
h
[j]
i
is re-enumerated as hˆ
k with k = (i + j)(i + j + 1)/2 + j, ∀i, j ∈ N.
In order to demonstrate the contradiction, let us assume that at least one of the LLM states is
hallucination-free. This assumption is necessary because if there is no hallucination-free LLM, the
theorem is trivially proved. Feeding a string s to LLMs in all the enumerated states, we get their
answers as {hˆ
0(s), hˆ
1(s), . . .}. Repeat this for all s ∈ S, we get a table as in Table 1, which contains
all the outputs of all the LLMs. In other words, if a ground truth function f is not in enumeration
{hˆ
0, hˆ
1, . . .}, then no LLM can learn f (and w.r.t. which all LLMs will hallucinate).
Now we define the ground truth function f so that f(si) contradicts the elements along the diagonal
of the table (see blue cells in Table 1):
f(si) = ∆
hˆ
i(si)

, ∀i ∈ N, (3)
where ∆ is a computable function that returns a different string from its input. For example, we could
define ∆

sk

= sk+1, which returns the next string of sk in S. Therefore ∆

hˆ
i(si)

̸= hˆ
i(si).
2A set is enumerable if there exists an enumeration algorithm that produces all the elements in that set. In
other words, if an element is in the set, then the algorithm must confirm so. This is exactly what prover P can do.
3
Suppose there exists an enumeration of all the total computable functions, denoted as (h0, h1, h2, . . .).
Then, define a function g(i) = hi(i) + 1. It follows that g(i) is a total computable function, yet it is different
from each hi in the enumeration. This implies that the enumeration is incorrect, leading to a contradiction.
By the above construction and according to Definition 6, hˆ
0 hallucinates w.r.t. f as f(s0) ̸= hˆ
0(s0),
so for hˆ
1 as f(s1) ̸= hˆ
1(s1), and so for hˆ
2 as f(s2) ̸= hˆ
2(s2). Repeating this reasoning for all
si ∈ S, we see that all LLMs hallucinate w.r.t. f because f(si) ̸= hˆ
i(si) for all i ∈ N. This
contradicts with our assumption of the existence of at least one hallucination-free trained LLM and
thus proves the theorem.
The theorem and its proof indicate that if f is not listed in the enumeration table, then it is not
learnable by any LLM in the table, and therefore all LLMs in the table will hallucinate on f.
LLMs will Hallucinate on What they Cannot Compute Since P is a prover and an enumeration
algorithm for LLMs, we can further examine P to see what problems are hallucination-inducing
for LLMs. Up till now, all LLMs produce output not only in finite time, but also in polynomial
time O(Π(m)), where Π(m) is a polynomial of m, the length of input questions. This means that
if f cannot be computed within O(Π(m)) time, then P-proved O(Π(m)) LLMs will inevitably
hallucinate w.r.t f. Therefore, we can list some hallucination-prone tasks for these LLMs:
Corollary 1. Let m be the length of LLM’s input and Π(m) be a polynomial of m. If LLM h
is P-proved to finish in at most O(Π(m)) steps for any input, then h will inevitably hallucinate
w.r.t. f, if f is the ground truth function for the following problems:
Problem 1 Combinatorial List: f lists all the strings with length m using an alphabet of two
characters. Computing f takes O(2m) time.
Problem 2 Presburger arithmetic [49, 59]: given a statement in this axiom system, f returns “yes”
if the statement can be proved within the system and “no” otherwisea
. Computing f
takes O(22
Π(m)
) time [16].
Assuming P ̸= NP, O(Π(m)) LLMs will hallucinate on the NP-complete problems such as:
Problem 3 Subset Sum: given a set of m integers and a number q, f returns “yes” when there
is a subset that sums up to q and “no” otherwise.
Problem 4 Boolean Satisfiability (SAT) [11]: given a formula of m Boolean variables, f returns
“yes” if there exists an assignment on these variables which results in the formula to
be true and “no” otherwise.
a
Presburger arithmetic is the first-order theory of natural numbers with addition and order <. It is
consistent, complete, and decidable. Therefore, there exists a computable f for this problem.
As a result, real-world LLMs’ answers about mathematical problems should always be subjected to
proper scrutiny. The result is supported by a recent study [23]. In Section 5, we provide an empirical
study to illustrate Problem 1 listed above.
Table 2: Illustration of proof for Theorem 2. Each row represents a particular LLM. Each column
represents a string si where the LLM is tested on. A value in the j
th column of i
th row represents
hi(sj ). Blue cells are the outputs that we use to construct f, on which the LLM in the corresponding
row will hallucinate.
Test Samples
LLMs
s0 s1 s2 s3 · · ·
hˆ
0 hˆ0(s0) hˆ0(s1) hˆ0(s2) hˆ0(s3) · · ·
hˆ
1 hˆ
1(s0) hˆ1(s1) hˆ1(s2) hˆ1(s3) · · ·
hˆ
2 hˆ
2(s0) hˆ
2(s1) hˆ2(s2) hˆ2(s3) · · ·
hˆ
3 hˆ
3(s0) hˆ
3(s1) hˆ
3(s2) hˆ3(s3) · · ·
· · · · · · · · · · · · · · · · · ·
f ∆

{hˆ0(s0)}
 ∆

{hˆj (s1) | j ≤ 1}
 ∆

{hˆj (s2) | j ≤ 2}
 ∆

{hˆj (s3) | j ≤ 3}

· · ·
LLMs will Hallucinate on Infinitely Many Questions One might argue that P-provability has
limited the complexity of LLMs. Moreover, Theorem 1 only shows that LLM h will hallucinat
on one input but not all inputs. Therefore, hallucination in the formal world could be negligible.
However, we can remove the provability constraint and further show the following theorem:
Theorem 2. For all computably enumerable sets of LLMs {h0, h1, . . .}, there exists a computable ground truth function f, such that all h
[j]
i
, i, j ∈ N, hallucinate on infinitely many
inputs.
Proof. Consider the following computably enumerable set of LLMs: {h0, h1, . . . }. Note that in this
theorem we have dropped prover P, which means this enumeration of LLMs is more general than
what is used in the proof of Theorem 1. Similar to the proof of Theorem 1, we enumerate all the
states of these LLMs as {hˆ
k|k ∈ N} using the Cantor pairing function. Feeding a string s to these
LLMs, we get their answers as {hˆ
0(s), hˆ
1(s), . . .}.
Define a computable function f as follows:
f(si) = ∆
{hˆ
j (si) | j ≤ i}

, ∀i ∈ N,
where ∆

{hˆ
j (si) | j ≤ i}

returns a string that is different from all the strings in set {hˆ
j (si) | j ≤ i}.
By the above construction, ∀i ≥ j, f(si) ̸= hˆ
j (si) because the value of f(si) is explicitly defined as
a string different from hˆ
j (si), i ≥ j (see Table 2). Therefore, hˆ
0 will hallucinate on s0, s1, . . .; hˆ
1
will hallucinate on s1, s2, . . .; and hˆ
2 will hallucinate on s2, s3, . . ., and so on. In general, LLM hˆ
k
will hallucinate on all input strings after sk−1 in the one-to-one enumeration (s0, s1, . . .) of S.
Note that P-proved total computable LLMs form a computably enumerable set. Therefore, Theorem 2
is a generalisation of Theorem 1.
4.2 Any Computable LLM will Hallucinate
We have shown that all LLMs in a computably enumerable set will inevitably hallucinate. In this
section, we go one more step towards a direct answer to the fundamental question by considering
LLMs as general total computable functions. The ground truth function f will still be assumed to be
any total computable function.
This step can be achieved by using Theorem 2. Any individual computable LLM h forms a set {h},
which only contains h itself and is thus computably enumerable. Therefore, applying Theorem 2 on
this set, we know that there exists a ground truth function f such that this particular h will hallucinate
on infinitely many inputs. This can be done for any total computable LLM. Therefore, we get the
following theorem similar to [18]:
Theorem 3. For all computable LLMs h, there exists a computable ground truth functiona f
such that each of h
[j]
, j ∈ N hallucinates on infinitely many inputs.
aNote that in this theorem f differs for every individual h, whereas f in Theorem 1 and Theorem 2 is
constructed for all LLMs in the set being considered.
To give a specific example, in Section B in the appendix we present a special case where f represents
a computable linear order, which is an abstraction of many real-world relations such as ranking of
movies or songs, chronological ordering of events, alphabetical sorting of words, and so on.
As a result, an LLM will inevitably hallucinate in our formal world of computable functions. Note that
we have only required h to be computable. Therefore, the conclusion is generally true independent of
model architecture, learning algorithms, training data, and other implementation details. Furthermore,
such inevitability indicates that it is impossible to use an LLM to eliminate its hallucination:
Corollary 2. All computable LLMs cannot prevent themselves from hallucinating.
If there exists an LLM h
′ which can prevent itself from hallucination, then h
′
is hallucination-free on
any computable f, which contradicts Theorem 3. This corollary is an obvious result of Theorem 3,
However, it explicitly suggests that methods relying on LLMs themselves to mitigate hallucination,
such as prompt-based chain of thoughts [69], cannot eliminate hallucination.

Answer to the Fundamental Question This section has presented theoretical results about hallucination in our formal world:
• Hallucination is inevitable for P-proved total computable LLMs (Theorem 1). Furthermore,
polynomial-time LLMs will hallucinate when solving many real-world problems, including
arithmetics (Corollary 1).
• Hallucination is inevitable for LLMs in any computably enumerable set (including the set
of P-proved total computable LLMs). All these LLMs could hallucinate on infinitely many
inputs (Theorem 2).
• Hallucination is inevitable for any total computable LLMs (Theorem 3).
Since our formal world is a part of the real world, and total computable LLMs are at least as
powerful as real-world LLMs, we now conclude with a negative answer to the fundamental question:
hallucination of LLMs cannot be eliminated in either our formal world, or in the real world. This
answer is independent of (1) LLMs’ architecture and complexity, (2) procedure used to train the LLM,
(3) the prompts and questions, (4) the number of training samples, and (5) inference hyperparameters.
5 Empirical Study: Can LLMs List Them All?
Consider a task intellectually simple for human beings: list all strings of a fixed length using a fixed
alphabet. Corollary 1 predicted that polynomial-time LLMs will hallucinate on this task. In this
section, we empirically validate this prediction. In Section B.2, we provide another empirical study
about LLMs and linear orders.
The Task An LLM is required to list all the strings with length m using an alphabet A. We denote
this task as L(m, A). For example, a solution to L(2, {a, b}) is “bb, ba, ab, bb”. For each
L(m, A), we run the LLM three times using three random seeds. The LLM is deemed successful in
solving L(m, A) if, in any of the three runs, the LLM’s output contains all and only strings of length
m using alphabet A. Note that duplicated entries are allowed in the output, for example, “aa, ab,
ba, bb, ab” is a valid solution to L(2, {a, b}).
Models In the experiment we study two state-of-the-art LLM families, namely Llama 2 [61]
and Generative Pretrained Transformers (GPT) [6, 45]. Models in both families have context windows of at least 4096 tokens. For Llama 2, we use its 70-billion-parameter version
llama2-70b-chat-hf publicly accessible on HuggingFace [27]. For GPT, we use the 175-billionparameter gpt-3.5-turbo-16k for GPT-3.5, and gpt-4-0613 for the GPT-4 family with more
parameters (GPT-4’s parameter number is not disclosed in the report [45]).
Prompt We use the following base prompt adapted from [26], which is used to prompt an LLM
towards completion a dialogue made of questions and answers. Modifications have been made to
prompt the LLMs to answer directly instead of providing high-level descriptions or code snippets:
Base Prompt
You are a helpful, respectful and honest assistant. Always answer as helpfully
as possible, while being safe. Your answers should not include any harmful,
unethical, racist, sexist, toxic, dangerous, or illegal content. Please ensure
that your responses are socially unbiased and positive in nature.
If you don’t know the answer to a question, please don’t share false
information. However, if you know the answer, you should always share it in
every detail and as requested. Always answer directly. Do not respond with a
script or any approximation.
Then, we describe the task to the LLM, for example, L(2, {a, b}) is described as:
Task Description for L(2, {a, b})
11
Table 3: Evaluation results of LLMs on L(m, {a, b}) and L(m, {a, b, c}) tasks. A check mark ✓
indicates that the LLM successfully solved the problem and a cross mark ✗ indicates the opposite.
The exact parameter number for GPT-4 is not disclosed.
LLM # Param # Context
(tokens) L(m, {a, b}) L(m, {a, b, c})
m → 1 2 3 4 5 6 7 1 2 3 4 5
llama2-70B-chat-hf 7.00 × 1010 4,096 ✓ ✓ ✗ ✗ ✗ ✗ ✗ ✓ ✗ ✗ ✗ ✗
gpt-3.5-turbo-16k 1.75 × 1011 16,385 ✓ ✓ ✓ ✓ ✓ ✗ ✗ ✓ ✓ ✓ ✗ ✗
gpt-4-0613 ≥ 1.75 × 1011 8,192 ✓ ✓ ✓ ✓ ✓ ✓ ✗ ✓ ✓ ✓ ✓ ✗
List ALL the strings with a length of two characters and only contains
characters "a" and "b". Do not miss a single string.
Result We feed the base prompt and the task descriptions for L(m, {a, b}) and L(m, {a, b, c})
with m ∈ N to the LLMs. The evaluation result is shown in Table 3. Consistent with the theoretical
result in Corollary 1, all LLMs failed eventually as m grows. Surprisingly, LLMs fail for tasks
with short answer, compared to the length of their context window. For example, the answer of
L(7, {a, b}) is a list of 2
7 = 128 strings, each with 7 characters. This results in an 896-character-long
answer, which is much shorter than the 4096-token context window. Furthermore, the number of
parameters and context size does not significantly impact LLMs’ performance on this task: they are
equally poor.
6 Discussion
6.1 Existing and Possible Hallucination Mitigators
Existing hallucination mitigators are generally developed using two principles: (a) improve the
capacity of LLMs, and (b) provide the LLM with more information about the real world4 ground truth
function f, by either using training samples or inductive biases. In this section, we briefly discuss
where these methods and some other possible mitigators are located in our analysis framework, and
their limitations.
Larger models and more training data LLMs are believed to show “emergent abilities” [68]
which are absent in smaller language models because of the significantly increased number of
parameters and training samples. Therefore, it is natural to think that hallucination will disappear as
LLMs grow larger. In the context of this work, increasing model parameters boosts the complexity of
LLMs, enabling it to capture more complex ground truth functions. Expanding the size of T helps
rule out invalid LLM candidates and help the training converge better. As the Probably Approximately
Correct (PAC) learning framework [63] indicates, increasing training data will result in diminishing
generalisation errors if training time is sufficient, provided that the task is learnable by LLMs.
However, increasing parameters and data is futile if the ground truth function f cannot be captured
by LLMs at all as suggested by Theorem 1 and Theorem 3. For example, adding more multi-head
attention layers to a polynomial-time LLM will only result in a larger polynomial-time LLM and will
only reduce and possibly eliminate hallucination w.r.t. polynomial-time ground truth functions. It
will not eliminate hallucination w.r.t. an exponential-time ground truth function, no matter how many
layers are added or how much additional training data are provided.
Prompting LLMs with Chain of Thoughts/Reflections/Verification This appoach belongs to
the larger family of in-context learning, which provides example solutions or relevant knowledge
about a target task in the prompt [13, 69, 74]. Essentially, it tries to introduce the inductive bias that
f generates answer in a procedural manner. Complex problems often have multiple solutions with
varying degrees of complexity. Consider the computation of the Fibonacci sequence: a recursive
approach leads to exponential time complexity, whereas applying dynamic programming significantly
4Note that the “real world” does not necessarily refer to the world where we are, but could be a world
constructed for a particular scenario, and could vary across problems.
12
reduces this to linear time in the input number. Prompting is effective in mitigating hallucination by
guiding them towards solutions more preferred by humans, which are possibly the ones with lower
complexities, and within LLMs’ capabilities. However, this approach will only work for specific
tasks. It is unlikely that all ground-truth functions f can be fully described by prompts. Moreover, as
suggested by Corollary 2, it is impossible to eliminate hallucination for all tasks by simply changing
the prompts and hope LLM can automatically prevent itself from hallucinating.
Ensemble of LLMs This approach uses multiple instances of LLMs to solve a single problem.
The solution is usually produced through majority votes or consensus after a dialogue among the
LLMs with natural language capabilities. It injects inductive bias that a prompt-completion string
cross-validated by different hypotheses of the world is more likely a true element of the world. An
ensemble of LLMs has a higher complexity than each member LLMs and therefore the ensemble
could be more capable and less hallucination-prone than individual LLMs. However, an ensemble is
essentially a single LLM viewed under Definition 2, which means it is bounded by Theorem 3 and
cannot eliminate hallucination.
Guardrails and Fences The guardrails are principles that align LLMs’ output with human values,
ethics, and legal requirements. The fences is a list of critical tasks that should never be fully automated
using LLMs. Both of them serve as safety constraints to prevent LLMs (and other AI models) from
generating undesirable outcomes. Guardrails and fences can be formally programmed [53] to
explicitly affect LLMs’ behaviours. Therefore, it is potentially a useful hallucination mitigator for
the formal world and some real-world problems. However, its scalability in the real world remains an
open problem.
LLMs Enhanced by Knowledge This approach uses external knowledge sources (e.g., knowledge
graphs and databases) and symbolic reasoning methods (e.g., logics) to aid LLMs both in training
and inference. Popular chatbots driven by LLMs, such as ChatGPT, has started utilising tools such
as search engine, code intepreter, and calculators to solve complex problems beyond their innate
capabilities [44]. Similar to programmable guardrails and fences, it explicitly controls the LLM
workflow by changing how information is recalled (through retrieval from knowledge database [39,
48]) or used (through logic inference, which has been done for deep networks as in [71, 72]). In this
way, LLMs receive extra information about the ground truth function f other than via training data
and is therefore not bounded by Theorem 3. This is potentially an effective mitigator of hallucination
in the formal world. However, whether it works scalably in real world tasks is an open problem.
6.2 Practical Implications
So far we have extensively described the limitation of LLMs. We believe these discussions have the
following implications for the AI practitioners.
All LLMs will hallucinate. In Section 4.1, we have given concrete examples of scenarios where
polynomial-time LLMs are hallucination-prone. Furthermore, such eventuality is guaranteed by
Theorem 3 for general computable ground truth functions and for any computable LLMs. An
important, but not the only, reason for hallucination is that the problem is beyond LLMs’ computation
capabilities. For those problems, any answer except “I don’t know” is unreliable and suggests that
LLMs have added premises implicitly during the generation process. It could potentially reinforce
stereotypical opinions and prejudices towards under-represented groups and ideas. Furthermore,
it can be dangerous if unexpected premises were added and resulted in unethical, disturbing, or
destructive contents.
Without guardrail and fences, LLMs cannot be used for critical decision making. This is a direct
corollary of the conclusion above. The purpose of guardrail and fences is to ensure that the LLMs
operate within expectation and never deviate into harmful realms. They are absolutely necessary
since all LLMs will hallucinate.
Without human control, LLMs cannot be used automatically in any safety-critical decision-making.
For example, no LLM should make decisions about human life, even if its decision is aided by
guardrail and fences. Any errors due to hallucination in these cases are very likely to be unacceptable.
Humans’ decision making role is paramount because human values are much more complex than
validity. Making safety-critical decisions usually requires rational and humane (understanding,
13
empathy, and ethical) judgements that are otherwise very difficult, if not impossible, to compute by
any algorithm.
Research on LLMs’ safety boundaries is crucial in ensuring sustainable development of LLMs. Misuse
of LLMs by human users is damaging in many ways and raised wide concern among researchers,
users, and regulators. For example, LLMs have been used to mine private information and cook
up misinformation and hate speech. On the other hand, usage of LLMs for automated sensing and
actuation, such as in a robotics setting, could result in dangerous real-world outcomes if hallucination
occurs. It is therefore important for theorists and practitioners to reach consensus on the ability
boundaries for LLMs. Towards this, we attempt to preliminarily identify an “upper bound” of LLMs’
capabilities in Section C in the appendix. There should also be appropriate regulations to control
their use and prevent intentional and unintentional misuse that poses real risk to human society.
6.3 In Defence of LLMs and Hallucination
Although we have shown that LLMs will inevitably hallucinate, this does not undermine their
tremendous value in enhancing productivity. Moreover, hallucination itself should not be viewed
entirely negatively. In this section, we would like to defend the usage of LLMs and their hallucinatory
inclinations.
First, the decision to use an LLM is fundamentally a trade-off between precision and efficiency, which
is largely determined by their application. LLMs excel in processing and structuring information at
scales and speeds unachievable by humans, facilitating rapid decision-making and idea generation.
In scenarios where speed and volume of information processing are overwhelming, the occasional
inaccuracies of LLMs are acceptable compromises. Conversely, in situations where precision is
critical, the outputs of LLMs can (and must) be verified and supplemented with human supervision. It
is notable that while LLMs cannot learn all computable ground truth functions f, it can learn some f
(see Section C) and can be useful therein. The key is not to view LLMs as infallible sources of truth
but as powerful assistive tools for information retrieval, analysis, summarisation, and presentation.
Moreover, it is crucial to recognize that LLMs are continuously evolving. Such evolution includes
advancements in model architecture, data processing techniques, training methodologies, and error
correction strategies. Over time, we anticipate that the nature of hallucination will be better understood
by human researchers and users. While it is impossible to completely eliminate hallucination, we are
optimistic that its severity may be controlled and reduced for many applications.
Finally, hallucination is not completely detrimental. In art, literature, and design, the unintentional
and unpredictable outputs from LLMs could inspire human creators. Such deviation from facts can
lead to unique perspectives that a strictly factual and precise system might never generate. In this
sense, the hallucinatory aspect of LLMs should be regarded positively as a source of inspiration,
innovation, and creativity.
6.4 Open Problems
Finally, we list some challenging and fundamental open problems stemming from our discussion:
• What real-world problems can be provably addressed by LLMs without hallucination? The
problem can be further divided into the following problems:
– What is the theoretical computational capability of an LLM?
– Are real-world problems always computable? If so, what are the complexities of
real-world problems?
– If LLMs are theoretically capable of solving a real-world problem, how can LLMs be
trained to achieve their theoretical capabilities so that hallucination can be eliminated
in that limited realm?
• Corollary 1 highlights the relation between computational complexity and hallucination. What
tasks are intrinsically more difficult than others? How to design benchmarks to evaluate
LLMs on tasks with different computational complexities?
• For problems which are provably within LLMs’ capabilities, is it more preferable to use
LLMs or use programs coded specific for the problems? Should we train an LLM that does
everything or an LLM that can use proper tools for specific problems?
14
• How can hallucination be detected and corrected for any real-world problems using external
knowledge sources and reasoning tools? Furthermore, can LLMs always find the appropriate
external tools for solving real-world problems?
• How can the risk of hallucination be quantified for real-world problems? Quantifying hallucination risk is an important step to identity on which problems can LLMs be safely deployed,
even with inevitable hallucination.
7 Conclusion
In this paper, we study the fundamental problem of eliminating hallucinations in LLMs. To do so, we
define a formal world where hallucination in LLMs can be clearly defined and discussed. Specifically,
hallucination is defined as inconsistencies between computable LLMs and a computable ground
truth function. By utilizing results in learning theory, we show that hallucination is inevitable for
computable LLMs if the ground truth function is any computable function. Since the formal world
is a part of the real world, we further conclude that it is impossible to eliminate hallucination in
the real world LLMs. Using the formal world framework, we discuss the possible mechanisms and
effectiveness of existing hallucination mitigators and discuss practical implications that our theoretical
results have on the deployment of LLMs in the real world. We emphasize that since hallucination is
inevitable, rigorous study of the safety of LLMs is critical.