Abstract

Hallucinations, a phenomenon where a language model (LM) generates nonfactual content, pose a significant challenge to the practical deployment of LMs. While many empirical methods have been proposed to mitigate hallucinations, recent studies established a computability-theoretic result showing that any LM will inevitably generate hallucinations on an infinite set of inputs, regardless of the quality and quantity of training datasets and the choice of the language model architecture and training and inference algorithms. Although the computability-theoretic result may seem pessimistic, its significance in practical viewpoints has remained unclear. This paper claims that those "innate" inevitability results from computability theory and diagonal argument, in principle, cannot explain practical issues of LLMs. We demonstrate this claim by presenting a positive theoretical result from a probabilistic perspective. Specifically, we prove that hallucinations can be made statistically negligible, provided that the quality and quantity of the training data are sufficient. Interestingly, our positive result coexists with the computability-theoretic result, implying that while hallucinations on an infinite set of inputs cannot be entirely eliminated, their probability can always be reduced by improving algorithms and training data. By evaluating the two seemingly contradictory results through the lens of information theory, we argue that our probability-theoretic positive result better reflects practical considerations than the computability-theoretic negative result.

hallucinations, computability theory, statistical learning theory

1 Introduction↩︎

A language model (LM), in a broad sense, is a computer program to solve a task whose input and/or output are natural language sentences. Typically, both the input and output of the task are formulated as natural language sentences. For example, in scenarios like translation or chatbots, the task is to receive natural language sentence input that users type or chat and generate a natural language sentence output that meets the users’ desire described in the input sentences. Early approaches relied on rule-based pattern matching, e.g., ELIZA [1], PARRY [2], ALICE [3], etc. or statistical language models based on Markov theories, e.g., [4]–[6]. However, the introduction of artificial neural networks in LMs, pioneered by, e.g., [7]–[10], has led to a paradigm shift over the past two decades, as advances in techniques and hardware have enabled large-scale neural models. The techniques supporting the success include effective neural network architectures, e.g., long short term memory [11], [12], the encoder-decoder model [13], the attention architecture [14], Transformer [15], etc., pretraining strategies, e.g., BERT [16], and learning strategies human feedback, e.g., [17]. Those large-scale neural language models, often simply called large language models (LLMs), have impacted academia and society, represented by the launch of powerful chatbots, e.g., ChatGPT [18]–[20], Gemini [21], [22], LLaMA [23]–[25], Claude [26], Qwen [27]–[29], DeepSeek [30], [31], etc., as well as success in the fields of machine translation [32], search engine [33], recommendation systems [34], [35]. For more details of language models, refer to, e.g., [36]–[38].

As LLMs have impacted society, hallucinations have been identified as crucial issues, complicating their practical deployment in applications [39]. Here, hallucinations are defined as a phenomenon where a LM generates nonfactual content [39] or content nonsensical or unfaithful to the provided source [40]. The root causes of hallucinations have generally been categorized [39], [40] into data, training, and inference, and many empirical methods have been proposed to mitigate hallucinations, e.g., by exploiting knowledge bases [41], [42], refining the requirement on LMs [43], [44], or applying information theoretic methods [45]. However, based on computability theory, a recent study [46] has proved using diagonal argument that in a certain ground truth setting, any LM regardless of its training and inference algorithms or training dataset employed will inevitably produce hallucinations on an infinite set of input strings. Another study [47] construct a concrete example of an inevitable hallucination instance by reducing the problem to the halting problem, which is also essentially based on diagonal argument. This theoretical result may seem fatally pessimistic for practitioners since hallucinations on infinite input instances sound like an insurmountable obstacle in practice. Indeed, those results have been referred to as fundamental limitations of LLMs not only in academia but also in the general public, e.g., articles in an online encyclopedia [48] and written by a journalist [49], being referred to as a ground to state that we need to "live with them (hallucinations)" [47] or hallucinations "can’t be stopped" [49].

However, generally speaking, the implications of computability-theoretic theorems based on diagonal argument need to be carefully discussed from practical viewpoints. For example, although there exist uncountably infinite non-computable mathematical functions, computers have been significantly useful in computing plenty of practical functions. Hence, it is crucial to know what the theoretical result by [46] actually implies from more practical viewpoints. In other words, our question is the following: Can the inevitability of hallucinations have practical implications? Since the core of those discussions is in non-computable functions, no numerical simulations can rebut them. Hence, theoretical discussions are necessary.

This paper claims that those "innate" inevitability results from computability theory and diagonal argument, in principle, cannot explain practical issues of LLMs, by presenting a contrastive, positive theoretical result from a probabilistic perspective on a problem setting compatible with the previous work [46]. Specifically, we show that we can reduce the probability of hallucinations arbitrarily close to zero, provided that the training data is of sufficient quality and quantity and certain training and inference algorithms are employed. In other words, even if LLMs fail, we should ascribe the failure to the algorithm and the quality or quantity of the dataset, not to the "innate" inevitability of hallucinations proved by diagonal arguments. Crucially, our positive result mathematically coexists with the negative result of [46] under a wide range of settings. We also solve the paradox behind the coexistence, recalling that an infinite set equipped with a probability measure can have an infinite subset with an arbitrarily small probability. In other words, even though we cannot avoid hallucinates on infinite input instances, it is still possible to reduce the probability of hallucinations arbitrarily close to zero by improving training data and training and inference algorithms. The practical significance of hallucinations occurring only on infinite input sets with arbitrarily small probability can ultimately depend on the application domain. Still, using Shannon’s coding theorem as an example, we point out that, in the field of information theory, errors occurring on subsets with arbitrarily small probabilities are often considered negligible in practice. Thus, based on our theoretical result, we can conclude that hallucinations are practically negligible in domains where information theory has been successfully applied without practical issues, provided the quality and quantity of training data are sufficient. In other words, where hallucinations are indeed a practical issue, the cause should be attributed to either the dataset (quality or quantity) or the algorithm, but not to an "innate" inevitability of hallucinations derived from computability theory based on the diagonal argument.

Note that we make no assumptions regarding the grammatical or semantic structure of natural language or the nature of the ground truth mapping. This is a significant advantage of our theorems since natural languages are not considered to satisfy mathematically convenient conditions completely.

The contributions of the paper are listed as follows:

We show in the discrete setting reflecting natural language processing that hallucinations are statistically negligible with an appropriate algorithm and the quality and quantity of training data, provided prior knowledge about the input length distribution is available.
We evaluate the statistical negligibility and inevitability of hallucinations through the lens of information theory, arguing that the statistical negligibility better reflects practical considerations.

Our work is directly inspired by [46], stating that any language model hallucinates on infinite input instances. While they evaluate hallucinations on computability theory only, our work evaluates hallucinations from both computability and probability perspectives to clarify the theories’ implications from practical viewpoints. [50] clarified that hallucinations are inevitable when the real-world distribution and the training data distribution are different. However, such situations are out of our scope since we are interested in the situation where training data is qualified, where the computability-theoretic limitation still holds.

Some work has focused on specific neural network architectures based on Transformer [15] in the continuous function approximation context. For example, [51] and [52] have proved that Transformers are universal approximators of continuous sequence-to-sequence functions with compact support, though they suffer from the curse of dimensionality under their assumptions. Transformers have been known to avoid the curse of dimensionality with stronger assumptions on the function space, such as sparse boolean functions [53], hierarchical compositions [54], and shift-invariant and piecewise smooth functions [55], [56]. However, the continuous function framework in these studies is different from the discrete set framework that [46] and our work consider to be modeling natural language tokens directly. Since the computability-based limitation proved by [46] comes essentially from the discrete set setting, the theoretical framework must be based on the same setting with minimal assumptions so that we can compare the result with the limitation proved by [46]. We also point out a similar problem setting is intensively considered by [57], while their motivation is in how the probably approximately correct (PAC) learnable changes where we restrict the hypothesis class to computable functions rather than in evaluating the probability of hallucinations caused by the computability limitation.

Technically, our theorems are straightforwardly derived from either computability theory, intensively used in [46], or the classical no-free-lunch theorem in statistical learning theory in, e.g., [58]. Our technical contribution lies in providing an integrated framework to discuss LMs from the two completely different theories at the same time, rather than novel proof techniques.

The remainder of the paper is organised as follows. Section 2 provides preliminaries. Section 3 reviews the computability-theoretic limitation of the LM. Section 4 formally states that we can make hallucinations statistically negligible. Section 5 solves the paradoxical conflict between the statements provided by Section 3 and Section 4 through information theory’s lens, clarifying that our statement in Section 4 is more relevant to practical perspectives. Section 6 concludes the paper.

1.2 Notation↩︎

We use the symbol \(:=\) to define the left-hand side by the right-hand side. We denote the set of real numbers, the set of integers, and the set of nonnegative integers by \(\mathbb{R}\), \(\mathbb{Z}\), and \(\mathbb{Z}_{\ge 0}\), respectively. We denote the floor function and ceiling function by \(\lfloor \cdot \rfloor\) and \(\lceil \cdot \rceil\), respectively, i.e., for \(a \in \mathbb{R}\), \(\lfloor a \rfloor := \max \{a' \in \mathbb{Z}\mid a' \le a\}\) and \(\lceil a \rceil := \min \{a' \in \mathbb{Z}\mid a' \ge a\}\). For a nonnegative integer \(n\) and a set \(A\), we denote the direct product set of \(n\) copies of \(A\) by \(A^{n}\) (e.g., \(A^{3} = A \times A \times A\)). For a set \(A\), \(2^{A}\) denotes the power set of \(A\), i.e., the set of all subsets of \(A\). Also, \(|A|\) denotes the cardinality of \(A\). In particular, the cardinality \(|A|\) equals the number of elements in the set \(A\) if \(A\) is a finite set.

2 Preliminaries↩︎

Definition 1 (String and the set of strings). Let \(\Sigma\) be the set of input symbols. For example, \(\Sigma= \{\textrm{`\texttt{A}'}, \textrm{`\texttt{B}'}, \dots, \textrm{`\texttt{Z}'}, \textrm{`\texttt{a}'}, \textrm{`\texttt{b}'}, \dots, \textrm{`\texttt{z}'}, \textrm{`\texttt{.}'}, \textrm{`\texttt{,}'}, \textrm{`\texttt{!}'}, \textrm{`\texttt{?}'}, \textrm{`\texttt{ }'}\}\) in the typical English language setting. A finite-length sequence of symbols is called a string. For \(n\in \mathbb{Z}_{\ge 0}\), we denote by \(\Sigma^{n}\) the direct product set of the \(n\) copies of \(\Sigma\), i.e., the set of strings of length \(n\). We denote by \(\Sigma^{*}\) the set of strings, i.e., \(\Sigma^{*} := \Sigma^{0} \cup \Sigma^{1} \cup \dots\). We denote the set of all probability measures on \(\Sigma^*\) by \(\Delta(\Sigma^*)\).

For example, “language” \(\in \Sigma^{8}\) as the word consists of 8 alphabet letters. Likewise, “language model” \(\in \Sigma^{14}\) as the phrase consists of 14 letters including a space letter.

Below, we define a language model, which is our main focus in this paper. Since our ultimate motivation is to compare our results with those in [46], we adopt the discrete set framework in the chatbot context as they did. The framework is also compatible with the nature of natural language processing, where discrete natural language tokens are processed.

Definition 2 (Language model (LM)). A (deterministic) computable map \(h: \Sigma^{*} \rightarrow \Sigma^{*}\) is called a language model (LM). Here, we say a map \(h\) is computable* if there exists a Turing machine halts with just \(h(s)\) on its tape for every input \(s\). We denote the set of all LMs by \(\mathcal{H}\). Specifically, \(\mathcal{H}:= \{h: \Sigma^{*} \rightarrow \Sigma^{*} \mid \text{h is computable}\}\).*

Refer to, e.g. [59], for rigorous definitions of, e.g., Turing machines.

The definition of the computability of a function is invariable even if we replace the Turing machine in the definition with another well-known computation model such as the \(\lambda\)-calculus, \(\mu\)-recursive function, or a modern computer with unlimited amounts of time and storage space. No matter what computing device, training and inference algorithms, and datasets for pre-training and fine-tuning datasets we use, the resulting LM \(h\) is computable thus in the set \(\mathcal{H}\) as long as it is deterministic. In particular, every LLM (*large* LM) is also in \(\mathcal{H}\). The computability of LMs plays a crucial role in the discussion in the following section. In contrast, since the largeness of a LM itself does not directly matter in this paper, we only use the term LM, not LLM, in the remainder of this paper. Nevertheless, all the discussions concerning LMs in this paper apply to any LLM.

Take examples to be familiar with notation. If we input “What is language?” \(\in \Sigma^{17} \subset \Sigma^{*}\) to a LM \(h_{1}\), then it may output “A system of communication.” \(\in \Sigma^{26} \subset \Sigma^{*}\). In this case, \(h_{1} (``\texttt{What is language?}'') = ``\texttt{A system of communication.}''\) Note that we consider a deterministic map as a LM, so the output of this LM \(h_{1}\) with the input “What is language?” is always “A system of communication.” and the LM \(h_{1}\) has no stochastic behavior.

LMs are often defined as a conditional probability mass function \(P(w_{t}|w_{1}, w_{2}, \dots, w_{t- 1})\), which eventually defines the conditional probability mass function of the output string defined on the output space \(\Sigma^{*}\). This definition sees a LM as a stochastic algorithm. Nevertheless, for simplicity, we focus on deterministic LMs only, which are special cases of stochastic LMs. The reasons why this simple discussion suffices in this paper are the following:

To show the existence of a LM satisfying desirable conditions, which is the main goal of this paper, it suffices to raise a special case.
If we aim to avoid hallucinations, it is a reasonable strategy to make the best output that is known not to be a hallucination, rather than having a possibility of output multiple strings against the given input.
In practice, even when we define a LM as a stochastic algorithm, it often works in practice as a deterministic output algorithm through, e.g., the beam-search algorithm.
It is in line with the setting in [46], so it allows us to focus on the essential difference between the previous work and our results.

It is, still, interesting to consider the compatibility of reducing hallucinations and output diversity, in which case considering stochastic LMs is beneficial. However, we leave such discussion to future work.

Both \(\Sigma^{*}\) and \(\mathcal{H}\) are countably infinite sets. Here, we say an infinite set \(A\) is countably infinite if there is a injective map from \(A\) to the set of nonnegative integers \(\mathbb{Z}_{\ge 0}\). The set \(\Sigma^{*} = \Sigma^{0} \cup \Sigma^{1} \cup \dots\) of finite-length strings is countably infinite since it is the countably infinite union of finite sets. The set \(\mathcal{H}\) of computable maps are also countably infinite since there exists a universal Turing machine, which emulates any Turing machine from a string describing the machine, so \(\mathcal{H}\) can be identified as an infinite subset of \(\Sigma^{*}\). The countablity of \(\Sigma^{*}\) and \(\mathcal{H}\) play a core role in Section 3, in particular in the proof of Theorem 1.

We formally define hallucinations. Our definition of hallucinations is not semantic but rather formal so that it is in line with the previous work [46]. We begin by defining an acceptable output set for each possible input and define hallucinations for each input as the complement set of the acceptable output set.

Definition 3 (Acceptable outputs and hallucinations). An acceptable output set map* is a map \(F_{0}: \Sigma^{*} \rightarrow 2^{\Sigma^{*}}\), i.e., a map taking a string as an input returning a set of strings. When we fix an acceptable output set map \(F_{0}\), for a string \(s\in \Sigma^{*}\) we call \(F_{0}(s)\) the acceptable output set for the input string \(s\). We say that the acceptable output set map \(F_{0}\) is non-vacuous if \(F_{0}(s) \neq \emptyset\) for all \(s\in \Sigma^*\). We can regard \(F_{0}\) as a formulation of the ground truth, and we say that an LM \(h\in \mathcal{H}\) hallucinates on the input \(s\in \Sigma^{*}\) with respect to \(F_{0}\) if \(h(s) \notin F_{0}(s)\).*

When ignore the change of acceptable outputs depending on the era, we can fix an acceptable output set map \(F_{0}\), but we will never know the map completely. Hence, our theoretical interest is in worst-case analysis with respect to the \(F_{0}\). Obviously, it is trivial that we cannot avoid a hallucination for the input \(s\) if \(F_{0}(s) = \emptyset\), so we omit those cases from the consideration. For some input instances, it has been proved that we cannot directly answer them. For example, it is known to be impossible to answer by yes/no the question “Is the continuum hypothesis true?” under a widely used axiomatic system (e.g., ZFC) of set theory. Even in that case, we would say “It can be neither proved nor disproved under ZFC.” \(\in F_{0}(``\texttt{Is the continuum hypothesis true?}'')\). Hence, we can assume the existence of \(F_{0}\) such that its return value is always nonempty, regardless of Gödel’s incompleteness theorems or the existence of undecidable problems in computability theory.

3 Innate computability limitation of LMs↩︎

We first formally state the innate limitation of the LMs in the computability aspect.

The following theorem is a modified version of Theorems 2 and 3 in [46].

Theorem 1. There exists an acceptable map \(F_{0}: \Sigma^{*} \rightarrow 2^{\Sigma^{*}}\) such that

\(|F_{0}(s)| > 0\) for every \(s\in \Sigma^{*}\), and
For any \(h\in \mathcal{H}\), \(h\) hallucinates on infinitely many inputs, i.e., \(\{s\in \Sigma^{*} \mid h(s) \notin F_{0}(s)\}\) is an infinite set.

Proof. See Appendix 8. ◻

Theorem 1 claims that in the worst case with respect to the acceptable map \(F_{0}\), no matter what LM we use, it hallucinates on infinitely many input strings. Note that this negative result holds regardless of our choice of neural network architecture, algorithms, and training data.

Theorem 1 is similar to Theorems 2 and 3 in [46] both in its statement and its proof strategy but technically stronger than those for the following senses:

Our Theorem 1 claims the existence of a map \(F_{0}\) for which all the LMs hallucinates on infinitely many input sequences. In particular, \(F_{0}\) does not depend on the choice of \(h\). Theorem 2 in [46] does not consider the whole LMs in \(\mathcal{H}\) and Theorem 3 in [46] allows the dependency of \(F_{0}\) on the choice of the learning procedure. Nevertheless, if we note that \(\mathcal{H}\) is a countable set, the modification from Theorems 2 and 3 in [46] to our Theorem 1 is straightforward.
Our proof avoids using the axiom of choice. See Appendix 8 for details, including why it matters in computer science, not in the context of pure mathematics.

Theorem 1 may look fatally negative to practitioners at one glance as it states that infinite hallucinations are inevitable. However, our main claim is that this result itself is not a practical issue, as we explain below.

4 Hallucinations can be made statistically negligible↩︎

As a preliminary, we first formalize a training data sequence and a LM trainer, which receives a training data sequence and returns a LM.

Definition 4 (Training dataset and language model trainer). An input-output string pair \((s, y) \in \Sigma^{*} \times \Sigma^{*}\) is called a training data point. Also, a finite sequence
\(((s_{1}, y_{1}), (s_{2}, y_{2}), \dots, (s_{m}, y_{m})) \in (\Sigma^{*} \times \Sigma^{*})^{*}\) of training data points is called a training data sequence* or training dataset. A map \(\mathfrak{A}: (\Sigma^{*} \times \Sigma^{*})^{*} \to (\Sigma^{*} \to \Sigma^{*})\), taking a training data sequence as and input and returning a LM, is called a language model trainer (LMT).*

Any practical LM can be regarded as an output of a computable LMT. This includes cases where a neural network is pretrained first on a general corpus to make a general next token predictor and fine-tuned on input-output string pairs (a training dataset) to modify the neural network model to one for a chat-bot. In practice, it is sufficient to consider computable LMTs. Nevertheless, we do not assume the computability of a LMT to clarify that the computability does not essentially matter in the following statistical results. Obviously, the theoretical results holding on general LMTs also apply to computable LMTs.

In this paper, we are interested in the probability of hallucinations happening, rather than the number of input instances causing hallucinations. Hence, we formally define the hallucination probability.

Definition 5 (Hallucination probability). We define the hallucination probability \(\mathop{\mathrm{HP}}_{\mu} (h) \in [0, 1]\) of a LM \(h\) on a probability measure \(\mu\) on \(\Sigma^{*}\) by \[\mathop{\mathrm{HP}}_{\mu} (h) := \mathop{\mathrm{Pr}}(h(S) \notin F_{0}(S)),\] where the right-hand side is the probability with respect to the random variable \(S\) generated by \(\mu\).

The hallucination probability is often called the 0-1 risk in a general statistical learning theory context.

Now, let’s clarify our goal. The main claim of the inevitability results by [46] and [47] is that hallucinations are inevitable regardless of the choice of training and inference algorithms and training data sequence (dataset) if we consider the worst case with respect to the ground truth acceptable output set map \(F_{0}\). To argue that they do not have practical implications from statistical aspects, we need to prove that there exists an algorithm and a desired property of datasets such that for any acceptable output set map \(F_{0}\) and probability measure \(\mu\), we can make the hallucination probability arbitrarily small. Here, to consider the logical negation, we can consider any algorithm and property of datasets, but we should not assume anything about the acceptable output set map \(F_{0}\) or the probability measure \(\mu\). Of course, we can always obtain a good consequence if we make a strong assumption, but such a consequence cannot disprove the inevitability results by [46] and [47] unless we can confirm that real natural language satisfies it. Practically, there is no mathematically tractable assumption that real natural language satisfies.

Example 1 (We cannot assume that the ground truth is computable). For example, if we know that there is some countable set, e.g., the set of computable maps, that the acceptable output set map \(F_{0}\) belongs to, learning is possible from Mark Gold’s classical discussion [60]. However, we have no guarantee, for example, that \(F_{0}\) is computable. Indeed, the core of the diagonal arguments [46], [47] is the uncountability of the set of hypotheses (in this paper’s notation, the set that \(F_{0}\) may belong to). Saying that "if we limit the search space to some countable set, then learning is possible" is not a valid rebuttal to the claim that "since the search space is uncountable, hallucination is inevitable."

For the above reason, we are going to find an ideal property of a training data sequence, denoted by \(T\) in this paper and an appropriate training and inference algorithm, denoted by \(\mathfrak{A}\), exploiting the training data sequence. We begin by defining an ideal property of a training data sequence.

Definition 6 (Qualified random training data sequence). Assume that \(F_{0}(s) \neq \emptyset\) for all \(s\in \Sigma^{*}\) and let \(\mu\) be a probability measure on \(\Sigma\). Then, a \((\Sigma^{*} \times \Sigma^{*})^{m}\)-valued random variable \(T= ((S_{1}, Y_{1}), (S_{2}, Y_{2}), \dots, (S_{m}, Y_{m}))\) is called a length-\(m\) qualified random training data sequence* compatible with \(F_{0}\) generated by \(\mu\) if \(T\) is generated as follows:*

\(S_{1}, S_{2}, \dots, S_{m}\) are \(\Sigma^{*}\)-valued random variables independently and identically generated by \(\mu\).
For \(i= 1, 2, \dots, m\), the distribution of the \(\Sigma^{*}\)-valued random variable \(Y_{i}\) is determined only by the value of \(S_{i}\) and \(Y_{i} \in F_{0}(S_{i})\) is satisfied in probability 1.

From practical aspects, it is a strong assumption to presume \(Y_{i} \in F_{0}(S_{i})\) is satisfied in probability 1. In fact, the following discussion essentially holds as long as the most frequently appearing output string is in the acceptable set. However, this extension bring to discussion complexity unnecessary for our motivation, which is to clarify the computability-based limitation of LMs is not a practical issue. Hence, we omit such an extension.

Then, we formally define statistical negligibility. Our definition is inspired by the framework of probably approximately correct (PAC) learning, but our viewpoint is from hallucinations and distributions, rather than from the hypothesis set. This is to make easier its comparison to the result in Section 3.

Definition 7 (Statistical negligiblity of hallucinations). (1) We say that hallucinations of a LMT \(\mathfrak{A}\) with a qualified random training data sequence are \((\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}})\)-negligible* on \(\mu\in \Delta(\Sigma^*)\) with training sequence length \(\bar{m}\) if for any non-vacuous acceptable output set map \(F_{0}\), any \(m\ge \bar{m}\), and any length-\(m\) qualified random training data sequence \(T\) compatible with \(F_{0}\) generated by \(\mu\), the hallucination probability satisfies \(\mathop{\mathrm{HP}}_{\mu} (\mathfrak{A}(T)) < \epsilon_{\mathrm{H}}\) in probability (with respect to \(T\)) at least \(1 - \epsilon_{\mathrm{T}}\).*

(2) Let \(\mathcal{P}\subset \Delta(\Sigma^*)\) be a set of probability measures on \(\Sigma^*\). For a set of probability measure \(\mathcal{P}\subset \Delta(\Sigma^*)\), we say that hallucinations of a LMT \(\mathfrak{A}\) with a qualified random training data sequence are uniformly statistically negligible* on \(\mathcal{P}\) if for any \(\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}} \in (0, 1]\) there exists a \(\bar{m} \in \mathbb{Z}_{\ge 0}\) such that for any \(\mu\in \mathcal{P}\), hallucinations are \((\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}})\)-negligible on \(\mu\) with training sequence length \(\bar{m}\). Also, we say that hallucinations of a LMT \(\mathfrak{A}\) with a qualified random training data sequence are non-uniformly statistically negligible on \(\mathcal{P}\) if for any \(\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}} \in (0, 1]\) and any \(\mu\in \mathcal{P}\), there exists a \(\bar{m} \in \mathbb{Z}_{\ge 0}\) such that hallucinations are \((\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}})\)-negligible on \(\mu\) with training sequence length \(\bar{m}\).*

It is known
[57], [61], [62] that whether or not a function class is PAC‑learnable can depend on whether the learning algorithm is required to be computable. Similarly, when we ask if hallucinations can be made statistically negligible over a distribution class, the answer may also hinge on assuming the algorithm is computable. However, in our paper, the positive results showing statistical negligibility are always obtained by explicitly constructing a computable algorithm, and the negative results, demonstrating failure to achieve ineligibility, are based on the no‑free‑lunch theorem that remains valid even when considering potentially non‑computable procedures. As a result, our theoretical conclusions about statistical negligibility hold, regardless of whether the algorithms are required to be computable.

If
hallucinations are statistically negligible, it implies that we can make the probability of hallucinations arbitrarily small with the help of a qualified and sufficiently long training sequence. It is because we can choose arbitrarily small \(\epsilon_{\mathrm{H}}\), and \(\epsilon_{\mathrm{T}}\). The difference between the above uniform statistical negligibility and non-uniform statistical negligibility of hallucinations only lies in whether the training data length \(\bar{m}\) can depend on the probability measure \(\mu\) or not. Specifically, if hallucinations are uniformly statistically negligible, we know in advance a sufficient condition on the training data size \(m\). In contrast, if we only know hallucinations are non-uniformly statistically negligible, we do not know how long a training data sequence we need, but eventually we can achieve the aimed hallucination probability (with high probability over training data distribution) if we increase the data size. By definition, if hallucinations are uniformly statistically negligible, then non-uniformly statistically negligible.

Interestingly, as shown in the Appendix, no LMT \(\mathfrak{A}\) can achieve the uniform statistical negligibility on the set \(\Delta(\Sigma^*)\) of all probability measures. In contrast, we can achieve non-uniform statistical negligibility. While we will state positive results for both later, as a preliminary for results about the uniform statistical negligibility, we define below the cumulative distribution function of the input length.

Definition 8 (Cumulative distribution function (CDF) of the input length). For a probability measure \(\mu\) on \(\Sigma^{*}\), we denote by \(\mathop{\mathrm{CDF}}_{\mathop{\mathrm{len}}\sharp \mu}\) the cumulative distribution function (CDF) of the length of a random variable generated by \(\mu\). Specifically, \(\mathop{\mathrm{CDF}}_{\mathop{\mathrm{len}}\sharp \mu}: \mathbb{Z}_{\ge 0} \rightarrow [0, 1]\) is defined by \(\mathop{\mathrm{CDF}}_{\mathop{\mathrm{len}}\sharp \mu} (n) := \mathop{\mathrm{Pr}}(\mathop{\mathrm{len}}(S) \le n)\), where \(S\) is generated by \(\mu\).

Definition 9 (The set of probability measures with a CDF lower bound). Fix a non-decreasing function \(\overline{\mathop{\mathrm{CDF}}}: \mathbb{Z}_{\ge 0} \rightarrow [0, 1]\) that satisfies \(\lim_{n\to +\infty} \overline{\mathop{\mathrm{CDF}}} (n) = 1\). We denote by \(\mathcal{P}_{\overline{\mathop{\mathrm{CDF}}}}\) the set of probability measures whose input length CDF is lower-bounded by \(\overline{\mathop{\mathrm{CDF}}}\), defined as \[\mathcal{P}_{\overline{\mathop{\mathrm{CDF}}}} := \{\mu\mid \forall n \in \mathbb{Z}_{\ge 0}, \mathop{\mathrm{CDF}}_{\mathop{\mathrm{len}}\sharp \mu} (n) \ge \overline{\mathop{\mathrm{CDF}}} (n)\}.\]

Now, we are ready to state our main result.

Theorem 2 (Hallucinations can be statistically negligible with \(\overline{\mathop{\mathrm{CDF}}}\)). There exists a LMT \(\mathfrak{A}\) (defined in Definition 4) such that:

for any non-decreasing function \(\overline{\mathop{\mathrm{CDF}}}: \mathbb{Z}_{\ge 0} \rightarrow [0, 1]\) that satisfies \(\lim_{n\to +\infty} \overline{\mathop{\mathrm{CDF}}} (n) = 1\), hallucinations of \(\mathfrak{A}\) with a qualified random training data sequence are uniformly statistically negligible on \(\mathcal{P}_{\overline{\mathop{\mathrm{CDF}}}}\) in the sense of Definition 7 and
hallucinations of \(\mathfrak{A}\) with a qualified random training data sequence are non-uniformly statistically negligible on the set \(\Delta(\Sigma^*)\) of all the probability measures on \(\Sigma^*\) in the sense of Definition 7.

Proof. Since for any \(\mu\in \Delta(\Sigma^*)\), \(\mu\in \mathcal{P}_{\mathop{\mathrm{CDF}}_{\mathop{\mathrm{len}}\sharp \mu}}\), we have that \(\Delta(\Sigma^*) = \bigcup_{\mu\in \Delta(\Sigma^*)} \mathcal{P}_{\mathop{\mathrm{CDF}}_{\mathop{\mathrm{len}}\sharp \mu}}.\) Hence, (2) follows from (1). (1) follows from Proposition [prp:trivial] immediately, which is stated in Appendix. ◻

For benefits of readers, we summarize the assumptions of Theorem 2. Theorem 2 claims that hallucinations are non-uniformly statistically negligible (regardless of \(F_{0}\) and \(\mu\)) if a certain LMT is used, when all of the following conditions are met.

Training data is qualified in the sense of Definition 6.
Training data is sufficient in the sense that it is more than \(\bar{m}\) in Definition 7.

Also, hallucinations are uniformly statistically negligible if the following condition is also met.

We know some lower bound of the input length CDF.

We remark that this does not require us to know any information about natural language’s grammar or syntax.

Although specific data size \(\bar{m}\) is not mentioned in the statement of Theorem 2, \(\bar{m}\) can be huge, and such a huge training data size is inevitable under this paper’s framework, as we will discuss in Appendix 7.3. However, this fact is not meant to assert that an extraordinary amount of data is practically necessary for the success of LMs. Rather, the framework of this paper is intended to rebut the practical implication of the "inevitability of hallucination" based on a diagonal argument. Its purpose is to conclude that even when assumptions are stripped down to this extent to align with their framework (for instance, even without assuming the computability of the acceptable output set map \(F_{0}\)), hallucinations can still be made statistically negligible. Naturally, if certain practical assumptions can be made, the sufficient data length can be shorter. However, we avoid such assumptions in this paper to clarify the essence of our rebuttal to diagonal-argument-based negative results.

Further discussions in the Appendix: Although the form of Theorem 2 suffices to rebut the negative results in[46], in the Appendix, we provide the specific form of Theorem 2 and indicate that the sufficient training data size can be huge, as stated in Remark [rem:HugeDataSize]. We also show that the specific theorem is nearly optimal in that its assumptions regarding the training data size and the availability of an input length CDF lower bound cannot be removed. We also point out that the optimality of our theorem enlightens future work directions.

Now, we have provided Theorem 2 stating that the probability of hallucinations can be arbitrarily small, which is a positive result from the probability theory aspect. However, the negative result Theorem 1, stating that hallucinations happen on infinite input instances still holds even in this case. The above positive and negative results seem to contradict each other. How do we interpret these seemingly contradicting two results from the viewpoint of practice? The following section answers this question.

5 Paradox and solution: infinite input instances causing hallucinations but with arbitrarily small probability↩︎

This section, first, clarifies why the paradoxical conflict between the statements provided by Section 3 and Section 4 coexist, and argue that our statement in Section 4 is more relevant to practical perspectives through information theory’s lens.

5.1 Why can those seemingly contradicting results coexist?↩︎

One might feel the negative result of Theorem 1 and the positive statement of Theorem 2 contradict each other. Indeed, since Theorem 1 makes no assumption on the data distribution, it still applies to the setting of Theorem 2. Hence, under the same setting, Theorem 1 states that every LM hallucinates on infinite input instances, whereas Theorem 2 states that there is a LM, of which hallucinations are statistically negligible. In fact, they do not contradict each other mathematically. Since the support \(\Sigma^{*}\) of the probability measures that we consider is an infinite set, the infinite subset on which a LM hallucinates can have little probability. An intuitive example of an infinite set having an arbitrarily small probability is the set \(\mathbb{Z}_{\ge m} = \{m, m+1, \dots\}\) that has probability \((1/2)^m\) when nonnegative integer \(i\) has probability mass \((1/2)^i\). Here, \(\mathbb{Z}_{\ge m}\) is an infinite set for any fixed \(m\), but its probability converges to 0 as \(m\) increases. Likewise, for fixed \(m\), the set of input instances on which a LM hallucinates is an infinity set as stated in Theorem 1, but we can make the probability of the set converge to zero as \(m\) increases, as suggested by Theorem 2.

5.2 Infinite set, but with arbitrarily small probability. Which matters in practice?↩︎

Now, what should be discussed is whether the infinite but arbitrarily small probability errors are accepted in practice. This is no longer a mathematical discussion and can ultimately depend on the domain. Nevertheless, we still claim that it has practically been negligible in information theory, where Shannon’s source coding theorem is one of its foundations. Here, one of the most fundamental versions of Shannon’s source coding theorem states the following (appearing in, e.g., [63]).

Theorem 3 (Shannon’s source coding theorem). Consider a probability measure \(\mu\) on a finite set \(\mathcal{X}\) and suppose that its entropy is \(H\) bits. Denote the product set of the \(m\) copies of \(\mathcal{X}\) by \(\mathcal{X}^{m}\) and the product measure of \(m\) copies of \(\mu\) by \(\mu^{m}\). In other words, \(\mu^{m}\) is the probability measure generating a random variable sequence \(X_{1} X_{2} \dots X_{m}\), where \(X_{i}\) is generated by \(\mu\) for \(i = 1, 2, \dots, m\). Given \(\epsilon > 0\) and \(0 < \delta < 1\), there exists a positive integer \(m_0\) such that for any positive integer \(m> m_0\), there exists a set \(A_{m} \subset \mathcal{X}^{m}\) such that

\(|\frac{1}{m} \log_{2} |A_{m}| - H| < \epsilon\), and
\(\mu^{m} (A_{m}) > 1 - \delta\).

Here, the first bullet point in Theorem 3 indicates that the number of elements in \(A_{m}\) is smaller than \(2^{m(H + \epsilon)}\) and so \(\lceil m(H + \epsilon)\rceil\) bits are sufficient to code every element in \(A_{m}\). The second bullet point indicates that the elements not in \(A_{m}\) appear in probability at most \(\delta\). Here, note that the number of elements of the set \(A_{m}\) is much smaller than that of \(\mathcal{X}^{m}\). As we can set \(\epsilon\) and \(\delta\) arbitrarily, the theorem has been understood as follows (the statement appears in the first half of “verbal statement” Shannon’s source coding theorem in [63]).

Theorem 4 (Shannon’s source coding theorem (verbal statement)). \(m\) i.i.d. random variables each with entropy \(H\) can be compressed into more than \(m H\) bits with negligible risk of information loss, as \(m\to \infty\).

The above common understanding of Shannon’s source coding theorem implies that, if we can make the probability of some unpreferred event arbitrarily small, the event is considered to be practically negligible in information theory even if the number of elements in the event is large.

Therefore, we can conclude that, although infinite hallucinations are inevitable in the sense of Theorem 1, they can be practically negligible in the application domains where information theory does not cause a practical issue.

6 Conclusion↩︎

We have shown that hallucinations are statistically negligible with an appropriate algorithm if the quality and quantity of the training data are sufficient, even in the worst scenario with respect to the ground truth and distribution. While hallucinations on an infinite set of inputs cannot be entirely eliminated, their probability can always be reduced by improving algorithms and training data. Section 5 has also pointed out that the hallucination probability, rather than the "number" of hallucinations, reflects practical considerations. By synthesising the above discussions, we can say that there exists a combination of dataset and algorithm that can make hallucinations unproblematic in practice. The existence of such a combination of dataset and algorithm (regardless of whether it is realistically preparable) implies the following: if hallucinations are indeed a practical issue, the cause should be attributed to either the dataset (quality or quantity) or the algorithm (including issues of computational complexity), and not to an "innate" inevitability of hallucinations derived from computability theory based on the diagonal argument.

7 Proof and optimality of Theorem 2 ↩︎

In this section, we discuss the assumptions of our main theorem Theorem 2. Theorem 2 assumes that the input length CDF lower bound is available and also that the training data size, as we see in detail later. We first go through our proof strategy based on constructing a trivial algorithm to see intuitively where those assumptions come from. Then, we theoretically show that those assumptions are necessary. The implication is significant since it means that no matter what algorithms we use, the worst-case data size is almost the same as that with which a trivial algorithm can succeed. We conclude this section by remarking that our result implies that we must not try to universally succeed under loose assumptions and rather should make stronger assumptions reflecting the nature of natural languages.

7.1 Proof strategy for Definition 7 ↩︎

We construct a trivial algorithm Algorithm 1, named Rote Memorizer (RM), to prove Theorem 2, stating that hallucinations can be statistically negligible. The algorithm gives us intuition behind the assumptions of Theorem 2. The idea of the algorithm is simple. We first find an input length threshold \(\bar{n}\) only depending on \(m\) and \(\overline{\mathop{\mathrm{CDF}}}\), and we simply rote-memorize the input-output pairs with an input shorter than \(\bar{n}\) in the training data sequence, If the training data size \(m\) is sufficient, there exists a string length \(\bar{n}\) such that it is so short that all the input strings shorter than \(\bar{n}\) appear in high probability in training data and so long that the probability of the input length longer than \(\bar{n}\) is small. The pseudocode of the straightforward algorithm is given in Algorithm 1. Note that we do NOT insist that Algorithm 1 should be used in practice. It is rather a tool for the proof.

With the help of Algorithm 1, we can show the following, which immediately gives us Theorem 2.

Assume that \(F_{0}(s) \neq \emptyset\) for all \(s\in \Sigma^{*}\). Fix a non-decreasing function \(\overline{\mathop{\mathrm{CDF}}}: \mathbb{Z}_{\ge 0} \rightarrow [0, 1]\) that satisfies \(\lim_{n\to +\infty} \overline{\mathop{\mathrm{CDF}}} (n) = 1\). Then, hallucinations of \(\mathfrak{A}\) given by Algorithm 1 with qualified random training data sequence are uniformly statistically negligible in the sense of Definition 7 on \(\mathcal{P}_{\overline{\mathop{\mathrm{CDF}}}}\), defined by Definition 9. Here, \(\bar{m}\) in the definition of uniform statistical negligibility is given by \(\bar{m} = \lceil\frac{|\Sigma^{*}|^{(\bar{n} + 1)}}{1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n})} \ln \frac{|\Sigma^{*}|^{(\bar{n} + 1)}}{2(1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n}))}\rceil\), where \(\bar{n}\) is an integer that satisfies \(1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n}) < \frac{1}{2} \min \{\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}}\}\). Note that such a \(\bar{n}\) exists by the definition of \(\overline{\mathop{\mathrm{CDF}}}\).

Proof. See Appendix 9. ◻

We can see that for uniform statistical negligibility of hallucinations, Proposition [prp:trivial] requires

the input length CDF lower bound and
the huge size \(\bar{m} = \lceil\frac{|\Sigma^{*}|^{(\bar{n} + 1)}}{1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n})} \ln \frac{|\Sigma^{*}|^{(\bar{n} + 1)}}{2(1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n}))}\rceil\) of training data, which is exponential with respect to \(\bar{n}\) depending on \(\overline{\mathop{\mathrm{CDF}}}\).

From the construction of Algorithm 1, we can intuitively understand why Proposition [prp:trivial] requires these two for hallucinations to be uniformly statistically negligible by Algorithm 1. To achieve the uniform statistical negligibility, we need to determine the training data size \(m\) in advance. For the rote memorization algorithm to achieve this, we need to limit the input length. With a lower bound of the input length CDF, we can find a string length threshold (which corresponds to \(\bar{n}\)) such that we can safely ignore inputs whose length is longer than the threshold, and we can determine the training data size \(m\) so that the training data covers the strings whose length is shorter than the threshold. Without the lower bound of the input length CDF, we cannot do this. Also, since it tries to rote memorize all the strings shorter than the string length threshold \(\bar{n}\), it is natural that it requires the training data size exponential to \(\bar{n}\).

A natural question is whether or not we can omit these two assumptions for uniform statistical negligibility of hallucinations from Proposition [prp:trivial] (or Theorem 2) by applying possible cleverer algorithms than the trivial Algorithm 1. Interestingly, neither of them can be omitted, as we will see for the input length CDF lower bound in Appendix 7.2 and for a huge training data size in Appendix 7.3.

7.2 The input length CDF lower bound is necessary for uniform statistical negligibility↩︎

The following theorem formally states that for uniform statistical negligibility of hallucinations, we cannot omit the input length CDF lower bound condition, no matter what algorithms we consider. Note that in the following, \(\mathbb{E}_{T}\) and \(\mathop{\mathrm{Pr}}_{T}\) denote the operators returning the expectation and probability over the length-\(m\) qualified random training data sequence \(T\).

Theorem 5 (No free lunch theorem in LM context). For any LMT \(\mathfrak{A}: (\Sigma^{*} \times \Sigma^{*})^{*} \rightarrow (\Sigma^{*} \rightarrow \Sigma^{*})\), any training data sequence length \(m\in \mathbb{Z}_{\ge 0}\), and any \(\lambda_{\mathrm{H}} \in (0, 1)\), there exist a map \(F_{0}: \Sigma^{*} \rightarrow 2^{\Sigma^{*}}\) satisfying \(F_{0}(s) \neq \emptyset\) for all \(s\in \Sigma^{*}\) and a probability distribution \(\mu\) on \(\Sigma^{*}\) such that the hallucination probability satisfies \[\begin{align} \mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) &\ge 1/2, \\ \mathop{\mathrm{Pr}}_{T} (\mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge \lambda_{\mathrm{H}}) &\ge \lambda_{\mathrm{T}}:= \frac{1 - 2 \lambda_{\mathrm{H}}}{2 - 2 \lambda_{\mathrm{H}}}, \end{align}\] where \(T\) is the length-\(m\) qualified random training data sequence.

See Appendix 10 for the proof of Theorem 5. It uses a variant of the no-free-lunch theorem, which we state in Appendix 10 as Theorem 7 [58].

For example, if \(\lambda_{\mathrm{H}} = 1/4\), then \(\lambda_{\mathrm{T}} = 1/3\). Hence, Theorem 5 states that \(\mathop{\mathrm{HP}}(\mathfrak{A}(T)) > 1/4\) happens in probability at least \(1/3 - \epsilon\) (for an arbitrarily small \(\epsilon\)) over the choice of the training data \(T\) in the worst case on the choice of \(F_{0}(s)\) and \(\mu\).

Despite its negative statement, we do not consider Theorem 5 to be implying issues from a practical perspective, since the lower bound could be easily obtained as it is nothing but a probability distribution of a scalar random variable without any information about syntax or semantics of natural languages. Nevertheless, Theorem 5 is theoretically interesting as proof of an optimality of Theorem 2.

7.3 Discussion on training data size↩︎

Proposition [prp:trivial] suggests that a training data size that is exponential to \(\bar{m}\), which depends on \(\overline{\mathop{\mathrm{CDF}}}\), is sufficient to make hallucinations statistically negligible. The following theorem states its converse in some sense. Specifically, it says that a training data size that is exponential to \(\underline{m}\), another variable depending on \(\overline{\mathop{\mathrm{CDF}}}\), is necessary.

Theorem 6 (No free lunch theorem in LM context). Fix a non-decreasing function \(\overline{\mathop{\mathrm{CDF}}}: \mathbb{Z}_{\ge 0} \rightarrow [0, 1]\) that satisfies \(\lim_{n\to +\infty} \overline{\mathop{\mathrm{CDF}}} (n) = 1\), and define \[\begin{align} \underline{n} &:= \mathop{\mathrm{argmin}}_{n\in \mathbb{Z}_{\ge 0}} \frac{|\Sigma|^{n+ 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (n)}, \\ \underline{m} &:= \left\lfloor\frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}\right\rfloor. \end{align}\] For any LMT \(\mathfrak{A}: (\Sigma^{*} \times \Sigma^{*})^{*} \rightarrow (\Sigma^{*} \rightarrow \Sigma^{*})\), any training data sequence length \(m\le \underline{m}\), and \(\lambda_{\mathrm{H}} \in (0, 1)\), there exist a map \(F_{0}: \Sigma^{*} \rightarrow 2^{\Sigma^{*}}\) satisfying \(F_{0}(s) \neq \emptyset\) for all \(s\in \Sigma^{*}\) and a probability distribution \(\mu\) on \(\Sigma^{*}\) such that the hallucination probability satisfies \[\begin{align} \mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) &\ge 1/2, \\ \mathop{\mathrm{Pr}}_{T} (\mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge \lambda_{\mathrm{H}}) &\ge \lambda_{\mathrm{T}}:= \frac{1 - 2 \lambda_{\mathrm{H}}}{2 - 2 \lambda_{\mathrm{H}}}, \end{align}\] where \(T\) is the length-\(m\) qualified random training data sequence.

See Appendix 10 for the proof of Theorem 6. Again, it uses the no-free-lunch theorem Theorem 7 [58], which we state in Appendix 10.

The huge data sizes that appear in Proposition [prp:trivial] and Theorem 6 do NOT imply that such vast quantities of training data are necessary for language models to succeed in practice. Rather, it enlightens future work directions, suggesting the necessity of stronger assumptions reflecting the behavior of natural languages. Specifically, from a theoretical perspective, Theorem 6 suggests that such assumptions are required to prove the success of LMs with practical training data size, as they were in the continuous function approximation setting, e.g., [51], [55], [56]. From a practical perspective, Theorem 6 suggests that we must give up trying to succeed in general settings and actively use properties of natural languages; otherwise, the performance will be at the same level as the trivial Algorithm 1. Having said that, since finding mathematically tractable assumptions that natural languages satisfy is hard in general, our Theorem 2 and Proposition [prp:trivial], holding under mild assumptions, are still significant as a fundamental guarantee.

8 Regarding the proof of Theorem 1 ↩︎

We first give the proof of Theorem 1, then explain the difference between our proof strategy and the previous work’s.

8.1 Proof of Theorem 1 ↩︎

Proof of Theorem 1. We prove the theorem by constructing a specific \(F_{0}: \Sigma^{*} \rightarrow 2^{\Sigma^{*}}\). Since each of \(\mathcal{H}\) and \(\Sigma^{*}\) is a countably infinite set, we can order each of them to obtain an infinite sequence \(h_{1}, h_{2},\dots \in \mathcal{H}\) and \(s_{1}, s_{2}, \dots \in \Sigma^{*}\). For example, we can order them in ascending order with respect to the Godel number. For \(i\in \mathbb{Z}_{> 0}\), define \(\tilde{\mathcal{I}}_{i} \subset \mathbb{Z}_{> 0}\) by \[\tilde{\mathcal{I}}_{i} := \{k \in \mathbb{Z}_{> 0} \mid \forall i' = 1, 2, \dots, i, s_{k} \neq h_{i'} (s_{i})\}.\] Here, \(\tilde{\mathcal{I}}_{i}\) is NOT empty since we can construct it by excluding at most finite elements from \(\mathbb{Z}_{>0}\), which is an infinite set. Hence, we can define \(\psi: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}\) by \[\psi(i) := \min \tilde{\mathcal{I}}_{i}.\] Define \(f_{0}: \Sigma^{*} \rightarrow \Sigma^{*}\) by \(f_{0}(s_{i}) := s_{\psi(i)}\) and \(F_{0}\) by \(F_{0}(s) = \{f_{0}(s)\}.\) Then, clearly, \(|F_{0}(s)| > 0\), and from the construction of \(\psi\), for any \(k \in \mathbb{Z}_{> 0}\) the inequality \(h_{k} (s_{i}) \neq s_{\psi(i)} = f_{0}(s_{i})\) holds. In other words, \(h_{k}\) hallucinates on infinitely many strings \(s_{k}, s_{k+1}, s_{k+2}, \dots\), which completes the proof. ◻

8.2 Motivation of avoiding depending on the axiom of choice (AC)↩︎

We remark that our proof of Theorem 1 does not use the axiom of choice (AC), while the previous work’s proof [46] depends on the AC. In this subsection, we discuss its significance.

As an axiomatic system of set theory, most mathematicians use either ZF (Zermelo-Fraenkel set theory) or ZFC, which consists of all the axioms of ZF combined with the axiom of choice (AC), as an axiomatic system of set theory. We leave the details of the axioms of ZF to textbooks, e.g., [64] and below show a version of the AC (Definition 1.1., [65]).

Definition 10. For each family \((A_{i})_{i \in I}\) of non-empty sets \(A_{i}\), the product set \(\prod_{i \in I} A_{i}\) is non-empty.

We remark that the statement can be proved from ZF when the index set \(I\) is a finite set. Hence, the difference lies in the cases where the index set \(I\) is an infinite set.

At one glance, the statement of the AC should be true, and on ZF, the axiom is equivalent to useful propositions, such as Zorn’s lemma, the well-ordering theorem, the existence of basis in every linear space, etc. However, we can also prove some "counterintuitive results," such as the Banach-Tarski paradox from the AC. For this reason, both ZF and ZFC have been intensively studied in the field of axiomatic set theory, while most fields of mathematics, like algebra and analysis, tend to assume the AC implicitly.

However, our interest is in the physical behavior of computers, not in differences coming from axiomatic systems. Since the discussion around Theorem 1 is about the physical behavior of computing devices, the results should not depend on the choice of an axiomatic system as long as the axiom system is consistent with physical phenomena. In other words, any purely computer-related theorem should be proved, regardless of the choice of a widely used axiom system. This is why we are interested in avoiding our proof’s dependence on the AC.

8.3 The dependency of the previous work’s proof on the AC and how we avoided it↩︎

Now, let us see how the previous work’s proof uses the AC and how we have avoided it. Specifically, when constructing \(\psi\), the previous work’s proof [46] arbitrarily chose an element from each of \(\tilde{\mathcal{I}}_{i}\) from \(i= 1, 2, \dots\). Since \(i\) is in the infinite set \(\mathbb{Z}_{> 0}\), such a construction of \(\psi\) is not guaranteed to exist without the axiom of choice. Specifically, if \(\prod_{i\in \mathbb{Z}_{> 0}} \tilde{\mathcal{I}}_{i}\) is empty, such a \(\psi\) does not exist. Hence, we must construct such a function \(\psi\) or prove \(\prod_{i\in \mathbb{Z}_{> 0}} \tilde{\mathcal{I}}_{i}\) in another way. On the other hand, our proof fixed the order of \(\Sigma^{*}\) and \(\mathcal{H}\) beforehand, and constructed a specific \(\psi\) using the \(\min\) operator. Hence, our proof is valid even without the axiom of choice.

8.4 Other parts of this paper and the AC↩︎

We do not investigate dependency on the AC in the other parts of the paper, especially when we consider the probability theory. As mentioned above, we often assume the AC in many fields of mathematics implicitly, and probability theory is no exception. This is natural since probability theory allows, e.g., probability mass functions whose value takes non-computable real numbers, which cannot be physically realized by a computer, so such a strong axiom is often necessary to induct results. Generally speaking, totally excluding the dependency of theories in those areas on the AC is quite demanding and does not make a difference in the implication of the real physical world. Therefore, we only consider the dependency of the purely computability-theoretic part, i.e., Section 3 on the AC, and we do not make an effort to remove the dependency of the other parts on the AC.

9 Proof of Proposition [prp:trivial]↩︎

Proof of Proposition [prp:trivial]. Recall that \(n= \max \{n' \mid m> \frac{|\Sigma^{*}|^{(n' + 1)}}{1 - \overline{\mathop{\mathrm{CDF}}} (n')} \ln \frac{|\Sigma^{*}|^{(n' + 1)}}{2 (1 - \overline{\mathop{\mathrm{CDF}}} (n'))}\}\). We prove the following lemma.

Lemma 1. Let \(\mathfrak{A}\) be the FLRM algorithm in Algorithm 1. Then, \(\mathop{\mathrm{HP}}_{\mu} (\mathfrak{A}(T)) < \epsilon'_{\mathrm{H}}\) holds in probability at least \(1 - \epsilon'_{\mathrm{T}}\) over choice of training data sequence \((S_{1}, S_{2},\dots,S_{m})\), where \(\epsilon'_{\mathrm{H}} = \epsilon'_{\mathrm{T}} = 2 (1 - \overline{\mathop{\mathrm{CDF}}} (n))\).

Once this lemma is proved, then for any \(\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}} \in (0, 1)\), we obtain that \(\mathop{\mathrm{HP}}_{\mu} (\mathfrak{A}(T)) < \epsilon_{\mathrm{H}}\) holds in probability at least \(1 - \epsilon_{\mathrm{T}}\) over choice of training data sequence if \(m> \frac{|\Sigma^{*}|^{(\bar{n} + 1)}}{1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n})} \ln \frac{|\Sigma^{*}|^{(\bar{n} + 1)}}{2(1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n}))}\), where \(\bar{n}\) is an integer that satisfies \(1 - \overline{\mathop{\mathrm{CDF}}} (\bar{n}) < \frac{1}{2} \min \{\epsilon_{\mathrm{H}}, \epsilon_{\mathrm{T}}\}\), which completes the proof of Proposition [prp:trivial]. Note that such a \(\bar{n}\) exists since \(\overline{\mathop{\mathrm{CDF}}}\) is non-decreasing and \(\lim_{n' \to +\infty} \overline{\mathop{\mathrm{CDF}}} (n') = 1\) by assumptions.

Now, we prove Lemma 1. We first decompose the hallucination probability as follows: \[\begin{align} \mathop{\mathrm{HP}}_{\mu} (\mathfrak{A}(T)) &:= \mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S)) \nonumber\\ &= \mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S) \text{ and } \mathop{\mathrm{len}}(S) \le n) \nonumber \\ & \quad + \mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S) \text{ and } \mathop{\mathrm{len}}(S) > n) \nonumber\\ &\le \mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S) \text{ and } \mathop{\mathrm{len}}(S) \le n) + \mathop{\mathrm{Pr}}_{S\sim \mu} (\mathop{\mathrm{len}}(S) > n) \nonumber\\ &\le \mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S) \text{ and } \mathop{\mathrm{len}}(S) \le n) + \epsilon'_{\mathrm{H}}/2. \label{eqn:HallucinationDecomposition} \end{align}\tag{1}\] Here, \(\mathop{\mathrm{Pr}}(\mathop{\mathrm{len}}(S) > n) \le \epsilon'_{\mathrm{H}}/2\) is due to the definition of \(\overline{\mathop{\mathrm{CDF}}}\) and \(\epsilon'_{\mathrm{H}} = 2(1 - \overline{\mathop{\mathrm{CDF}}} (n))\). Remark that if \(\mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S) \text{ and } \mathop{\mathrm{len}}(S) \le n) < \epsilon'_{\mathrm{H}}/2\), then \(\mathop{\mathrm{HP}}_{\mu} (\mathfrak{A}(T)) < \epsilon'_{\mathrm{H}}\) holds by 1 . In the following, we evaluate \(\mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S) \text{ and } \mathop{\mathrm{len}}(S) \le n)\). Denote the set of strings no longer than \(n\) by \(\Sigma^{(\le n)}\), defined by \(\Sigma^{(\le n)} := \Sigma^{0} \cup \Sigma^{1} \cup \dots \cup \Sigma^{n}\). Also, define \(k:= |\Sigma^{(\le n)}| \in \mathbb{Z}_{\ge 0}\). Note that \(k:= |\Sigma^{(\le n)}| = |\Sigma^{0} \cup \Sigma^{1} \cup \dots \cup \Sigma^{n}| = \frac{|\Sigma|^{n} - 1}{|\Sigma| - 1} \le |\Sigma|^{n}\) holds. We index all the elements in \(\Sigma^{(\le n)}\) in the descending order with respect to its probability. In other words, \(s_{1}, s_{2}, \dots, s_{k} \in \Sigma^{(\le n)}\) satisfy \(s_{j} \neq s_{j'}\) and \(\mathop{\mathrm{Pr}}(S= s_{j}) \ge \mathop{\mathrm{Pr}}(S= s_{j'})\) for any \(j, j'\) satisfying \(1 \le j< j' \le k\) and any random variable \(S\) generated by the distribution \(\mu\). For \(j= 1, 2, \dots, k\), define \(p_{j} = \mathop{\mathrm{Pr}}(S= s_{j})\). Also, define \(j^{(*)} := \min \{j\in \{1, 2, \dots, k\} \mid \sum_{j'=j+ 1}^{k} p_{j'} < (\epsilon'_{(\mathrm{H})})/2\}\). In other words, \(j^{(*)}\) is the unique index that satisfies \(\sum_{j'=j^{(*)}}^{k} p_{j'} \ge (\epsilon'_{(\mathrm{H})})/2\) and \(\sum_{j'=j^{(*)}+1}^{k} p_{j'} < (\epsilon'_{(\mathrm{H})})/2\). Let \(S_{1}, S_{2}, \dots, S_{m}\) be mutually independent random variables, all generated by the distribution \(\mu\). Here, if \(\{S_{1}, S_{2}, \dots, S_{m}\} \supset \{s_{1}, s_{2},\dots, s_{j^{(*)}}\}\) holds, then the output of Algorithm 1 does not hallucinates on any inputs in \(\{s_{1}, s_{2},\dots, s_{j^{(*)}}\}\), which leads to \(\mathop{\mathrm{Pr}}_{S\sim \mu} (\mathfrak{A}(T) (S) \notin F_{0}(S) \text{ and } \mathop{\mathrm{len}}(S) \le n) < \epsilon'_{\mathrm{H}}/2\). Hence, all we need to do is to upper bound the probability of the event \(\{S_{1}, S_{2}, \dots, S_{m}\} \not\supset \{s_{1}, s_{2},\dots, s_{j^{(*)}}\}\). We denote this event by \(U_{(\le j^{(*)})}^{(m)}\). In the following, we evaluate \(\mathop{\mathrm{Pr}}(U_{(\le j^{(*)})}^{(m)})\).

Let \(U_{(j)}^{(m)}\) denote the event \((S_{1} \neq s_{j}) \text{ and } (S_{2} \neq s_{j}) \text{ and } \dots \text{ and } (S_{m} \neq s_{j})\). Since \(U_{(\le j^{(*)})}^{(m)} = \bigcup_{j=1}^{j^{(*)}} U_{(j)}^{(m)}\) holds, we have that \(\mathop{\mathrm{Pr}}(U_{(\le j^{(*)})}^{(m)}) \le \sum_{j=1}^{j^{(*)}} \mathop{\mathrm{Pr}}(U_{(j)}^{(m)})\). Recall that \(p_{j} := \mathop{\mathrm{Pr}}(S_{i} = s_{j})\) for all \(i= 1, 2, \dots, m\). Since \(S_{1}, S_{2}, \dots, S_{m}\) are mutually independent, we have that \(\mathop{\mathrm{Pr}}(U_{(j)}^{(m)}) = (1 - p_{j})^{m}\). By the definition of the indexing order, \(p_{j} \le p_{j^{(*)}}\) holds for \(j= j^{(*)}, j^{(*)} + 1,\dots, k\). Also, by the definition of \(j^{(*)}\), we have that \(\sum_{j= j^{(*)}}^{k} p_{j} \ge \epsilon'_{\mathrm{H}}/2\). Therefore, we obtain \[p_{j^{(*)}} = \max \{p_{j^{(*)}}, p_{j^{(*)} + 1}, \dots, p_{k}\} \ge \frac{\sum_{j= j^{(*)}}^{k} p_{j}}{k- j^{(*)} + 1} \ge \frac{\epsilon'_{\mathrm{H}}}{2 (k- j^{(*)} + 1)} \ge \frac{\epsilon'_{\mathrm{H}}}{2 k}.\] Here, the second inequality comes from the fact that the maximum value is always larger than or equal to the mean. Thus, for \(j= 1, 2, \dots, j^{(*)}\), we have that \(p_{j} \ge \frac{\epsilon_{\mathrm{H}}}{2 k}\). Hence, we obtain \(\mathop{\mathrm{Pr}}(U_{(j)}^{(m)}) = (1 - p_{j})^{m} \le (1 - \frac{\epsilon'_{\mathrm{H}}}{2 k})^{m} \le \exp(-\frac{m\epsilon'_{\mathrm{H}}}{2 k})\), where the last inequality comes from the general inequality \(1 + x \le \exp(x)\). Therefore, \[\begin{align} \mathop{\mathrm{Pr}}(U_{(\le j^{(*)})}^{(m)}) &\le \sum_{j=1}^{j^{(*)}} \mathop{\mathrm{Pr}}(U_{(j)}^{(m)}) \le \sum_{j=1}^{j^{(*)}} \exp\left(-\frac{m\epsilon'_{\mathrm{H}}}{2 k}\right) \\ &\le j^{(*)} \exp\left(-\frac{m\epsilon'_{\mathrm{H}}}{2 k}\right) \le k\exp\left(-\frac{m\epsilon'_{\mathrm{H}}}{2 k}\right) \\ &\le |\Sigma|^{n+ 1} \exp\left(-\frac{m\epsilon'_{\mathrm{H}}}{2 |\Sigma|^{n+ 1}}\right). \end{align}\] From the above, we can see that \(m> \frac{2 |\Sigma|^{n+ 1}}{\epsilon'_{\mathrm{H}}} \ln \frac{|\Sigma|^{n+ 1}}{\epsilon'_{\mathrm{T}}}\) is a sufficient condition for \(\mathop{\mathrm{Pr}}(U_{(\le j^{(*)})}^{(m)}) < \epsilon'_{\mathrm{T}}\) to hold. This completes the proof of Lemma 1. ◻

10 Proof strategy for LM limitations and no-free-lunch-theorem↩︎

Proposition [prp:trivial], essentially obtained by Proposition [prp:trivial], was proved by a specific algorithm. To prove such a positive result, constructing an algorithm suffices. On the other hand, to prove negative results such as Theorem 5 and Theorem 6, we need to show that the negative events happen no matter what algorithm we use. Thus, a simple construction-based proof does not work, and instead, we rely on the no-free-lunch theorem.

Indeed, we can prove Theorem 5 and Theorem 6 by the following no free lunch theorem proved in [58].

Theorem 7 (General no free lunch theorem). Consider a learning problem from a domain set \(\mathcal{X}\) to a codomain set \(\mathcal{Y}\) such that \(|\mathcal{Y}| \ge 1\), i.e., \(\mathcal{Y}\neq \emptyset\). For a probability measure \(\mu\) on \(\mathcal{X}\), a ground truth map \(f_{0}: \mathcal{X}\rightarrow \mathcal{Y}\), denote the hallucination probability (0-1 risk) of a hypothesis map \(h: \mathcal{X}\rightarrow \mathcal{Y}\) on \(\mu\) and \(f_{0}\) by \(\mathop{\mathrm{HP}}_{\mu, f_{0}} (h)\), which is defined by \(\mathop{\mathrm{HP}}_{\mu, f_{0}} (h) = \mathop{\mathrm{Pr}}(h(X) \neq f_{0}(X))\). Then, for any map (learning algorithm) \(\mathfrak{A}: (\mathcal{X}\times \mathcal{Y})^{*} \rightarrow (\mathcal{X}\rightarrow \mathcal{Y})\), any nonnegative integer (training data size) \(m\) that satisfies \(m\le \frac{1}{2} |\mathcal{X}|\), any finite positive integer \(p\) satisfying \(1 \le p\le |\mathcal{Y}|\), and any \(\lambda_{\mathrm{H}} \in (0, 1)\), there exist a computable map \(f_{0}: \mathcal{X}\rightarrow \mathcal{Y}\) and a finite subset \(\underline{\mathcal{X}}\subset \mathcal{X}\) such that both the following inequalities hold. \[\begin{align} \mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) &\ge \mu:= \frac{p-1}{2 p}, \\ \mathop{\mathrm{Pr}}_{T} (\mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge \lambda_{\mathrm{H}}) &\ge \lambda_{(\mathrm{T}, p)} := \frac{\mu- \lambda_{\mathrm{H}}}{1 - \lambda_{\mathrm{H}}} = \frac{p- 1 - 2 p\lambda_{\mathrm{H}}}{2 p- 2 p\lambda_{\mathrm{H}}}. \end{align}\] Here, \(T= ((\underline{X}_{1}, Y_{1}), (\underline{X}_{2}, Y_{2}), \dots, (\underline{X}_{m}, Y_{m}))\) is a length-\(m\) random training data sequence, where \(\underline{X}_{1}, \underline{X}_{2}, \dots, \underline{X}_{m}\) are i.i.d. random variables generated by \(\mathop{\mathrm{Uni}}(\underline{\mathcal{X}})\), the uniform distribution on \(\underline{\mathcal{X}}\), and \(Y_{i} = f_{0}(\underline{X}_{i})\) for \(i= 1, 2, \dots, m\) and the operators \(\mathbb{E}_{T}\) and \(\mathop{\mathrm{Pr}}_{T}\) return the expectation of the return value of the given function of the random variable \(T\) and the probability of the given condition depending on \(T\) being satisfied, respectively.

We are interested in the cases where \(|\mathcal{Y}| \ge 2\) and we can take \(p\) so that \(p\ge 2\). If \(p\ge 2\), then \(\mu\ge 1/4\) and \(\lambda_{\mathrm{T}} \ge \frac{1 - 4 \lambda_{\mathrm{H}}}{4 - 4 \lambda_{\mathrm{H}}}\). Moreover, if \(\lambda_{\mathrm{H}} = 1/8\), then \(\lambda_{\mathrm{T}} \ge 1/7\).

Theorem 7 holds even where \(\mathcal{X}\) or \(\mathcal{Y}\) is infinite. If \(\mathcal{Y}\) is an infinite set, the following corollary is useful.

Corollary 1. Under the setting of Theorem 7, if \(\mathcal{Y}\) is an infinite set, then for any map (learning algorithm) \(\mathfrak{A}: (\mathcal{X}\times \mathcal{Y})^{*} \rightarrow (\mathcal{X}\rightarrow \mathcal{Y})\), any nonnegative integer (training data size) \(m\) that satisfies \(m\le \frac{1}{2} |\mathcal{X}|\), and any \(\lambda_{\mathrm{H}} \in (0, 1)\), there exist a computable map \(f_{0}: \mathcal{X}\rightarrow \mathcal{Y}\) and a finite subset \(\underline{\mathcal{X}}\subset \mathcal{X}\) such that both the following inequalities hold: \[\begin{align} \mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) &\ge 1/2, \\ \mathop{\mathrm{Pr}}_{T} (\mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge \lambda_{\mathrm{H}}) &\ge \lambda_{\mathrm{T}} := \frac{1 - 2 \lambda_{\mathrm{H}}}{2 - 2 \lambda_{\mathrm{H}}}. \end{align}\]

Proof. For any \(\epsilon \in \mathbb{R}_{>0}\), we can prove that \(\mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge 1/2 - \epsilon\) by taking a sufficiently large \(p\) in Theorem 7. Hence, \(\mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) < 1/2\) cannot hold, which completes the proof of \(\mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge 1/2\). We can prove \(\mathop{\mathrm{Pr}}_{T} (\mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge \lambda_{\mathrm{H}}) \ge \lambda_{\mathrm{T}}\) by applying Lemma 3 with \(c=1\) and \(a = \lambda_{\mathrm{H}}\) to \(\mathbb{E}_{T} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{0}} (\mathfrak{A}(T)) \ge 1/2\). ◻

In Corollary 1, for example, if \(\lambda_{\mathrm{H}} = 1/4\), then \(\lambda_{\mathrm{T}} = 1/3\).

Theorem 7 is a generalized version of the no free lunch theorem given as [58] as Theorem 7 provides a tighter bound when \(|\mathcal{Y}| \ge 3\). However, the proof technique is essentially the same as that of Theorem 5.1. in [58]. We also remark that the computability of the map \(f_{0}\) was pointed out by [57].

From Theorem 7, we obtain Theorem 5 and Theorem 6 as follows.

Proof of Theorem 5. For any \(m\), consider a subset \(\mathcal{X}\subset \Sigma^{*}\) such that \(|\mathcal{X}| > 2 m\). We obtain the theorem by applying Theorem 7 to \(\mathcal{X}\). ◻

Proof of Theorem 6. First, the following lemma holds, whose proof is in Appendix.

Lemma 2. We can construct a set \(\mathcal{X}\subset \Sigma^{*}\) such that \(|\mathcal{X}| = \lfloor\frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}\rfloor\) and \(\mathop{\mathrm{CDF}}_{\mathop{\mathrm{len}}\sharp \mathop{\mathrm{Uni}}(\mathcal{X})} (n) \ge \overline{\mathop{\mathrm{CDF}}} (n)\) for all \(n\in \mathbb{Z}_{\ge 0}\).

Once we admit Lemma 2, then we obtain Theorem 6 by applying Theorem 7 to the set \(\mathcal{X}\) constructed by Lemma 2, which completes the proof. ◻

The proof of Lemma 2 is given as follows.

Proof of Lemma 2. Recall that \(\underline{n} := \mathop{\mathrm{argmin}}_{n\in \mathbb{Z}_{\ge 0}} \frac{|\Sigma|^{n+ 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (n)}\). For \(n\in \mathbb{Z}_{\ge 0}\), construct \(\mathcal{X}_{n}\) as follows.

If \(\frac{|\Sigma|^{n+ 1} - 1}{|\Sigma| - 1} \le \frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}\), then \(\mathcal{X}_{n} := \Sigma^{n}\),
If \(\frac{|\Sigma|^{n} - 1}{|\Sigma| - 1} \le \frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})} < \frac{|\Sigma|^{n+ 1} - 1}{|\Sigma| - 1}\), then construct \(\mathcal{X}_{n}\) by collecting arbitrary \(\lfloor\frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}\rfloor - \frac{|\Sigma|^{n} - 1}{|\Sigma| - 1}\) elements in \(\Sigma^{n}\),
If \(\frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})} < \frac{|\Sigma|^{n} - 1}{|\Sigma| - 1}\), then \(\mathcal{X}_{n} = \emptyset\).

Then, the set \(\mathcal{X}:= \mathcal{X}_{0} \cup \mathcal{X}_{1} \cup \dots\) satisfies the following:

\(|\mathcal{X}| = \lfloor\frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}\rfloor\), and
Let \(X\) be a random variable generated by \(\mathop{\mathrm{Uni}}(\mathcal{X})\). For any \(n\in \mathbb{Z}_{\ge 0}\), \(\mathop{\mathrm{Pr}}(\mathop{\mathrm{len}}(X) \le n) = |\mathcal{X}_{(\le n)}|/|\mathcal{X}| \ge \overline{\mathop{\mathrm{CDF}}} (n)\), where \(\mathcal{X}_{(\le n)} := \mathcal{X}_{0} \cup \mathcal{X}_{1} \cup \dots \cup \mathcal{X}_{n}\),

which are the consequences of Lemma 1. Hence, we can complete the proof by confirming the above two properties. Here, the first property is trivial. Noting that \(|\mathcal{X}| \le \frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}\), the second property can be confirmed as follows.

If \(\frac{|\Sigma|^{n+ 1} - 1}{|\Sigma| - 1} \le \frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}\), then \(\mathcal{X}_{(\le n)} = \Sigma^{(\le n)}\), so \(|\mathcal{X}_{(\le n)}| = \frac{|\Sigma|^{n+ 1} - 1}{|\Sigma| - 1}\). Hence \(|\mathcal{X}_{(\le n)}|/|\mathcal{X}| \ge \frac{|\Sigma|^{n+ 1} - 1}{|\Sigma| - 1} \cdot \frac{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})}{|\Sigma|^{\underline{n} + 1} - 1} \ge \frac{|\Sigma|^{n+ 1} - 1}{|\Sigma| - 1} \cdot \frac{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (n)}{|\Sigma|^{n+ 1} - 1} = \overline{\mathop{\mathrm{CDF}}} (n)\) holds, where the second inequality is due to the definition of \(\underline{n}\).
If \(\frac{|\Sigma|^{\underline{n} + 1} - 1}{(|\Sigma| - 1) \overline{\mathop{\mathrm{CDF}}} (\underline{n})} < \frac{|\Sigma|^{n+ 1} - 1}{|\Sigma| - 1}\), then since \(\mathcal{X}_{(\le n)} = \mathcal{X}\), the inequality \(|\mathcal{X}_{(\le n)}|/|\mathcal{X}| = 1 \ge \overline{\mathop{\mathrm{CDF}}} (n)\) is trivial since \(\overline{\mathop{\mathrm{CDF}}} (n) \in [0, 1]\) by definition.

These complete the proof. ◻

We conclude this section with a complete proof of Theorem 7.

Proof of Theorem 7. The statement is trivial if \(p= 1\). Hence, in the following, we assume that \(|\mathcal{Y}|>1\) and \(1 \le p\le |\mathcal{Y}|\). Recall that for any positive integer \(a\), we denote the set \(\{1, 2, \dots, a\}\) by \([a]\). Recall that \(m\le \frac{1}{2} |\mathcal{X}|\). Define \(\underline{\mathcal{X}}:= \mathcal{X}\) if \(\mathcal{X}\) is a finite set and let \(\underline{\mathcal{X}}\) be an arbitrary finite subset of \(\mathcal{X}\) satisfying \(|\underline{\mathcal{X}}| = 2 m\) if \(\mathcal{X}\) is an infinite set. In any case, \(n:= |\underline{\mathcal{X}}| \ge 2 m\) is satisfied. Likewise, recall that \(p\le |\mathcal{Y}|\) and let \(\underline{\mathcal{Y}}\) be a finite subset of \(\mathcal{Y}\) satisfying \(|\underline{\mathcal{Y}}| = p\). Let \(\mathcal{Y}^{\underline{\mathcal{X}}}\) denote the set of all the maps from \(\underline{\mathcal{X}}\) to \(\mathcal{Y}\). Likewise, let \(\underline{\mathcal{Y}}^{\underline{\mathcal{X}}}\) denote the set of all the maps from \(\underline{\mathcal{X}}\) to \(\underline{\mathcal{Y}}\). Clearly, \(|\underline{\mathcal{Y}}^{\underline{\mathcal{X}}}| = |\underline{\mathcal{Y}}|^{|\underline{\mathcal{X}}|} = p^{n}\). In other words, there are \(Q:= p^{n}\) possible maps from \(\underline{\mathcal{X}}\) to \(\underline{\mathcal{Y}}\). We index these maps so that we have a sequence \(f_{1}, f_{2}, \dots, f_{Q}\) of distinct maps such that \(\{f_{1}, f_{2}, \dots, f_{Q}\} = \underline{\mathcal{Y}}^{\underline{\mathcal{X}}}\). In the following, for \(\boldsymbol{x}= (x_{1}, x_{2}, \dots, x_{m}) \in \mathcal{X}^{m}\) and \(f\in \mathcal{Y}^\mathcal{X}\), let \(f(\boldsymbol{x})\) denote \((f(x_{1}), f(x_{2}), \dots, f(x_{m})) \in \mathcal{Y}^{m}\) and \((\boldsymbol{x}, f(\boldsymbol{x}))^\top\) denote \(((x_{1}, f(x_{1})), (x_{2}, f(x_{2})), \dots, (x_{m}, f(x_{m}))) \in (\mathcal{X}\times \mathcal{Y})^{m}\). We are to prove that for any map \(\mathfrak{A}: \mathcal{X}^{m} \rightarrow \mathcal{Y}^{\mathcal{X}}\), the following holds: \[\max_{q\in [Q]} \mathbb{E}_{\boldsymbol{X}\sim \mathop{\mathrm{Uni}}(\underline{\mathcal{X}})^{m}} \mathop{\mathrm{HP}}_{\mathop{\mathrm{Uni}}(\underline{\mathcal{X}}), f_{q}} (\mathfrak{A}((\boldsymbol{X}, f_{q} (\boldsymbol{X}))^\top)) \ge \frac{p-1}{2p}, \label{eqn:NFL-proof1}\tag{2}\] where \(\mathbb{E}_{\boldsymbol{X}\sim \mathop{\mathrm{Uni}}(\underline{\mathcal{X}})^{m}}\) indicates the expectation operator with respect to the random variable sequence \(\boldsymbol{X}= (X_{1}, X_{2}, \dots, X_{m})\), a sequence of independent random variables, each of which is generated by the identical uniform distribution \(\mathop{\mathrm{Uni}}(\underline{\mathcal{X}})\). Note that since \(\underline{\mathcal{X}}\) and \(\underline{\mathcal{Y}}\) are finite sets, \(f_{q}\) is a computable map for all \(q\in [Q]\). There are \(D:= |\underline{\mathcal{X}}|^m\) possible data sequences in \(\underline{\mathcal{X}}^m\). We index these data sequences so that we have a sequence \(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \dots, \boldsymbol{x}_{D}\) of distinct data sequences satisfying \(\{\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \dots, \boldsymbol{x}_{D}\} = \underline{\mathcal{X}}^m\). By the definition of the uniform distribution \(\mathop{\mathrm{Uni}}(\underline{\mathcal{X}})^{m}\), we have \[\mathbb{E}_{\boldsymbol{X}\sim \mathop{\mathrm{Uni}}(\underline{\mathcal{X}})^{m}} \mathop{\mathrm{HP}}_{\dots} (\mathfrak{A}(\dots)) = \frac{1}{D} \sum_{d=1}^{D} \mathop{\mathrm{HP}}_{\dots} (\mathfrak{A}((\boldsymbol{x}_{d}, f_{q} (\boldsymbol{x}_{d}))^\top)). \label{eqn:NFL-proof2}\tag{3}\] The rest of the proof follows the standard no-free-lunch theorem argument. We omit the details which can be found in, e.g., [58]. The key idea is to average the risk over all possible functions and datasets, showing that for any learner, there must be a function for which it performs poorly. This leads to the desired lower bound on the expected risk.

The second part of the theorem, concerning the probability of high risk, is a direct consequence of the first part combined with the following variant of Markov’s inequality.

Lemma 3. Let \(c\) be a positive real number and let \(Z\) be a random variable taking a value in \([0, c]\) and assume its expectation is given by \(\mathbb{E}Z = \mu \in \mathbb{R}\). Then, for any real number \(a \in (0, c)\), the following inequality holds: \[\mathop{\mathrm{Pr}}(Z > a) \ge \frac{\mu - a}{c - a}.\]

Proof. Noting that \(Z \le a\) is equivalent to \(c - Z \ge c - a\) and that \(c - Z\) is a nonnegative random variable whose expectation is \(c - \mu\), we obtain the following evaluation by Markov’s inequality: \[\mathop{\mathrm{Pr}}(Z > a) = 1 - \mathop{\mathrm{Pr}}(Z \le a) = 1 - \mathop{\mathrm{Pr}}(c - Z \ge c - a) \ge 1 - \frac{c - \mu}{c - a} = \frac{\mu - a}{c - a},\] where we applied Markov’s inequality to the nonnegative random variable \(c - Z\) to get the inequality. ◻

We complete the proof of Theorem 7 by applying Lemma 3 with \(c=1\) and \(a = \lambda_{\mathrm{H}}\) to the expectation result. ◻

References↩︎

[1]

J. Weizenbaum, “ELIZA—a computer program for the study of natural language communication between man and machine,” Communications of the ACM, vol. 9, no. 1, pp. 36–45, 1966.

[2]

K. M. Colby, S. Weber, and F. D. Hilf, “Artificial paranoia,” Artificial intelligence, vol. 2, no. 1, pp. 1–25, 1971.

[3]

R. S. Wallace, The anatomy of ALICE. Springer, 2009.

[4]

R. Kuhn and R. De Mori, “A cache-based natural language model for speech recognition,” IEEE transactions on pattern analysis and machine intelligence, vol. 12, no. 6, pp. 570–583, 1990.

[5]

D. Hiemstra, “A linguistically motivated probabilistic model of information retrieval,” in Research and advanced technology for digital libraries: Second european conference, ECDL’98 heraklion, crete, greece september 21–23, 1998 proceedings 2, 1998, pp. 569–584.

[6]

S. F. Chen and J. Goodman, “An empirical study of smoothing techniques for language modeling,” Computer Speech & Language, vol. 13, no. 4, pp. 359–394, 1999.

[7]

D. E. Rumelhart, G. E. Hinton, and R. J. Williams, “Learning representations by back-propagating errors,” nature, vol. 323, no. 6088, pp. 533–536, 1986.

[8]

J. L. Elman, “Finding structure in time,” Cognitive science, vol. 14, no. 2, pp. 179–211, 1990.

[9]

M. V. Mahoney, “Fast text compression with neural networks.” in FLAIRS, 2000, pp. 230–234.

[10]

Y. Bengio, R. Ducharme, and P. Vincent, “A neural probabilistic language model,” Advances in neural information processing systems, vol. 13, 2000.

[11]

S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural Computation, vol. 9, no. 8, pp. 1735–1780, 1997.

[12]

F. A. Gers, J. Schmidhuber, and F. Cummins, “Learning to forget: Continual prediction with LSTM,” Neural computation, vol. 12, no. 10, pp. 2451–2471, 2000.

[13]

K. Cho et al., “Learning phrase representations using RNN encoder–decoder for statistical machine translation,” in Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), 2014, pp. 1724–1734.

[14]

D. Bahdanau, K. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” in The 3rd international conference on learning representations, 2015.

[15]

A. Vaswani et al., “Attention is all you need,” Advances in neural information processing systems, vol. 30, 2017.

[16]

J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in Proceedings of the 2019 conference of the north american chapter of the association for computational linguistics: Human language technologies, volume 1 (long and short papers), 2019, pp. 4171–4186.

[17]

L. Ouyang et al., “Training language models to follow instructions with human feedback,” Advances in neural information processing systems, vol. 35, pp. 27730–27744, 2022.

[18]

A. Radford et al., “Language models are unsupervised multitask learners,” OpenAI blog, vol. 1, no. 8, p. 9, 2019.

[19]

T. Brown et al., “Language models are few-shot learners,” Advances in neural information processing systems, vol. 33, pp. 1877–1901, 2020.

[20]

J. Achiam et al., “GPT-4 technical report,” arXiv preprint arXiv:2303.08774, 2023.

[21]

Gemini Team et al., “Gemini: A family of highly capable multimodal models,” arXiv preprint arXiv:2312.11805, 2023.

[22]

Gemini Team et al., “Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context,” arXiv preprint arXiv:2403.05530, 2024.

[23]

H. Touvron et al., “Llama: Open and efficient foundation language models,” arXiv preprint arXiv:2302.13971, 2023.

[24]

H. Touvron et al., “Llama 2: Open foundation and fine-tuned chat models,” arXiv preprint arXiv:2307.09288, 2023.

[25]

A. Dubey et al., “The llama 3 herd of models,” arXiv preprint arXiv:2407.21783, 2024.

[26]

Anthropic, “The Claude 3 model family: Opus, Sonnet, Haiku.” 2024, [Online]. Available: https://www-cdn.anthropic.com/de8ba9b01c9ab7cbabf5c33b80b7bbc618857627/Model_Card_Claude_3.pdf.

[27]

J. Bai et al., “Qwen technical report,” arXiv preprint arXiv:2309.16609, 2023.

[28]

A. Yang et al., “Qwen2 technical report,” arXiv preprint arXiv:2407.10671, 2024.

[29]

A. Yang et al., “Qwen2.5 technical report,” arXiv preprint arXiv:2412.15115, 2024.

[30]

A. Liu et al., “Deepseek-v3 technical report,” arXiv preprint arXiv:2412.19437, 2024.

[31]

D. Guo et al., “DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning,” arXiv preprint arXiv:2501.12948, 2025.

[32]

Y. Wu et al., “Google’s neural machine translation system: Bridging the gap between human and machine translation,” arXiv preprint arXiv:1609.08144, 2016.

[33]

Microsoft, “The new Bing: Our approach to responsible AI.” 2023, [Online]. Available: https://blogs.microsoft.com/wp-content/uploads/prod/sites/5/2023/04/RAI-for-the-new-Bing-April-2023.pdf.

[34]

J. Li, W. Zhang, T. Wang, G. Xiong, A. Lu, and G. Medioni, “GPT4Rec: A generative framework for personalized recommendation and user interests interpretation,” arXiv preprint arXiv:2304.03879, 2023.

[35]

Y. Gao, T. Sheng, Y. Xiang, Y. Xiong, H. Wang, and J. Zhang, “Chat-rec: Towards interactive and explainable llms-augmented recommender system,” arXiv preprint arXiv:2303.14524, 2023.

[36]

W. X. Zhao et al., “A survey of large language models,” arXiv preprint arXiv:2303.18223, 2023.

[37]

S. Minaee et al., “Large language models: A survey,” arXiv preprint arXiv:2402.06196, 2024.

[38]

S. K. Dam, C. S. Hong, Y. Qiao, and C. Zhang, “A complete survey on llm-based ai chatbots,” arXiv preprint arXiv:2406.16937, 2024.

[39]

L. Huang et al., “A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions,” arXiv preprint arXiv:2311.05232, 2023.

[40]

Z. Ji et al., “Survey of hallucination in natural language generation,” ACM Computing Surveys, vol. 55, no. 12, pp. 1–38, 2023.

[41]

K. Shuster, S. Poff, M. Chen, D. Kiela, and J. Weston, “Retrieval augmentation reduces hallucination in conversation,” arXiv preprint arXiv:2104.07567, 2021.

[42]

R. Zhao, X. Li, S. Joty, C. Qin, and L. Bing, “Verify-and-edit: A knowledge-enhanced chain-of-thought framework,” arXiv preprint arXiv:2305.03268, 2023.

[43]

J. Wei et al., “Chain-of-thought prompting elicits reasoning in large language models,” Advances in neural information processing systems, vol. 35, pp. 24824–24837, 2022.

[44]

S. Dhuliawala et al., “Chain-of-verification reduces hallucination in large language models,” arXiv preprint arXiv:2309.11495, 2023.

[45]

S. Farquhar, J. Kossen, L. Kuhn, and Y. Gal, “Detecting hallucinations in large language models using semantic entropy,” Nature, vol. 630, pp. 625–630, 2024.

[46]

Z. Xu, S. Jain, and M. Kankanhalli, “Hallucination is inevitable: An innate limitation of large language models,” arXiv preprint arXiv:2401.11817, 2024.

[47]

S. Banerjee, A. Agarwal, and S. Singla, “Llms will always hallucinate, and we need to live with this,” arXiv preprint arXiv:2409.05746, 2024.

[48]

Wikipedia, [Online; accessed 19-May-2025]“Hallucination (artificial intelligence) — Wikipedia, the free encyclopedia.” http://en.wikipedia.org/w/index.php?title=Hallucination%20(artificial%20intelligence)&oldid=1290914849, 2025.

[49]

N. Jones, “AI hallucinations can’t be stopped—but these techniques can limit their damage,” Nature, vol. 637, no. 8047, pp. 778–780, 2025.

[50]

A. T. Kalai and S. S. Vempala, “Calibrated language models must hallucinate,” in Proceedings of the 56th annual ACM symposium on theory of computing, 2024, pp. 160–171.

[51]

C. Yun, S. Bhojanapalli, A. S. Rawat, S. Reddi, and S. Kumar, “Are transformers universal approximators of sequence-to-sequence functions?” in The 8th international conference on learning representations, 2020.

[52]

M. Zaheer et al., “Big bird: Transformers for longer sequences,” Advances in neural information processing systems, vol. 33, pp. 17283–17297, 2020.

[53]

B. L. Edelman, S. Goel, S. Kakade, and C. Zhang, “Inductive biases and variable creation in self-attention mechanisms,” in International conference on machine learning, 2022, pp. 5793–5831.

[54]

I. Gurevych, M. Kohler, and G. G. Şahin, “On the rate of convergence of a classifier based on a transformer encoder,” IEEE Transactions on Information Theory, vol. 68, no. 12, pp. 8139–8155, 2022, doi: 10.1109/TIT.2022.3191747.

[55]

S. Takakura and T. Suzuki, “Approximation and estimation ability of transformers for sequence-to-sequence functions with infinite dimensional input,” in International conference on machine learning, 2023, pp. 33416–33447.

[56]

J. Kim, T. Nakamaki, and T. Suzuki, “Transformers are minimax optimal nonparametric in-context learners,” arXiv preprint arXiv:2408.12186, 2024.

[57]

S. Agarwal, N. Ananthakrishnan, S. Ben-David, T. Lechner, and R. Urner, “On learnability with computable learners,” in Algorithmic learning theory, 2020, pp. 48–60.

[58]

S. Shalev-Shwartz and S. Ben-David, Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.

[59]

M. Sipser, Introduction to the theory of computation. Cengage Learning, 2012.

[60]

E. M. Gold, “Language identification in the limit,” Information and control, vol. 10, no. 5, pp. 447–474, 1967.

[61]

S. Agarwal, N. Ananthakrishnan, S. Ben-David, T. Lechner, and R. Urner, “Open problem: Are all VC-classes CPAC learnable?” in Conference on learning theory, 2021, pp. 4636–4641.

[62]

T. F. Sterkenburg, “On characterizations of learnability with computable learners,” in Conference on learning theory, 2022, pp. 3365–3379.

[63]

D. J. MacKay, Information theory, inference and learning algorithms. Cambridge university press, 2003.

[64]

K. Kunen, Set theory an introduction to independence proofs. Elsevier, 2014.

[65]

H. Herrlich, Axiom of choice, vol. 1876. Springer, 2006.

Hallucinations are inevitable
but can be made statistically negligible.

Abstract

1 Introduction↩︎

1.2 Notation↩︎

2 Preliminaries↩︎

3 Innate computability limitation of LMs↩︎

4 Hallucinations can be made statistically negligible↩︎

5 Paradox and solution: infinite input instances causing hallucinations but with arbitrarily small probability↩︎

5.1 Why can those seemingly contradicting results coexist?↩︎

5.2 Infinite set, but with arbitrarily small probability. Which matters in practice?↩︎

6 Conclusion↩︎

7 Proof and optimality of Theorem 2 ↩︎

7.1 Proof strategy for Definition 7 ↩︎

7.2 The input length CDF lower bound is necessary for uniform statistical negligibility↩︎

7.3 Discussion on training data size↩︎

8 Regarding the proof of Theorem 1 ↩︎

8.1 Proof of Theorem 1 ↩︎

8.2 Motivation of avoiding depending on the axiom of choice (AC)↩︎

8.3 The dependency of the previous work’s proof on the AC and how we avoided it↩︎

8.4 Other parts of this paper and the AC↩︎

9 Proof of Proposition [prp:trivial]↩︎

10 Proof strategy for LM limitations and no-free-lunch-theorem↩︎

References↩︎

Subjects

Updated on Academus

Hallucinations are inevitable but can be made statistically negligible.

Abstract

1 Introduction↩︎

1.1 Related work↩︎

1.2 Notation↩︎

2 Preliminaries↩︎

3 Innate computability limitation of LMs↩︎

4 Hallucinations can be made statistically negligible↩︎

5 Paradox and solution: infinite input instances causing hallucinations but with arbitrarily small probability↩︎

5.1 Why can those seemingly contradicting results coexist?↩︎

5.2 Infinite set, but with arbitrarily small probability. Which matters in practice?↩︎

6 Conclusion↩︎

7 Proof and optimality of Theorem 2↩︎

7.1 Proof strategy for Definition 7↩︎

7.2 The input length CDF lower bound is necessary for uniform statistical negligibility↩︎

7.3 Discussion on training data size↩︎

8 Regarding the proof of Theorem 1↩︎

8.1 Proof of Theorem 1↩︎

8.2 Motivation of avoiding depending on the axiom of choice (AC)↩︎

8.3 The dependency of the previous work’s proof on the AC and how we avoided it↩︎

8.4 Other parts of this paper and the AC↩︎

9 Proof of Proposition [prp:trivial]↩︎

10 Proof strategy for LM limitations and no-free-lunch-theorem↩︎

References↩︎

Subjects

Updated on Academus

Hallucinations are inevitable
but can be made statistically negligible.

7 Proof and optimality of Theorem 2 ↩︎

7.1 Proof strategy for Definition 7 ↩︎

8 Regarding the proof of Theorem 1 ↩︎

8.1 Proof of Theorem 1 ↩︎