Why LLMs Hallucinate, and How to Get (Evidential) Closure: Perceptual, Intensional, and Extensional Learning for Faithful Natural Language Generation
Authors: Adam Bouyamourn
Venue: EMNLP 2023 Main (2023)
Keywords: Truth
Semantics
Meaning
Hallucination
Identification
Natural Language Generation
TL;DR: LLMs hallucinate because their output is not constrained to be synonymous with claims for which they have evidence. We show conceptually how to constrain LLM output to be synonymous with claims for which the LLM has evidence.

Abstract: We show that LLMs hallucinate because their output is not constrained to be synonymous with claims for which they have evidence: a condition that we call evidential closure. Information about the truth or falsity of sentences is not statistically identified in the standard neural language generation setup, and so cannot be conditioned on to generate new strings. We then show how to constrain LLMs to produce output that satisfies evidential closure. A multimodal LLM must learn about the external world (perceptual learning); it must learn a mapping from strings to states of the world (extensional learning); and, to achieve fluency when generalizing beyond a body of evidence, it must learn mappings from strings to their synonyms (intensional learning). The output of a unimodal LLM must be synonymous with strings in a validated evidence set. Finally, we present a heuristic procedure, Learn-Babble-Prune, that yields faithful output from an LLM by rejecting output that is not synonymous with claims for which the LLM has evidence.

Why LLMs Hallucinate, And How To Get (Evidential) Closure:
Perceptual, Intensional and Extensional Learning for Faithful Natural Language Generation
Adam Bouyamourn
UC Berkeley
adam. www.booyyymmuun@berelle...e.ee
Abstract
evidential closure. An LLM is factual if it is ful, and, in addition, its evidence about the world correct."
faith-
We show that LLMs hallucinate because their output is not constrained to be synonymous with claims which they have evidence: condition that call evidential closure. Infor- mation about the truth or falsity of sentences is statistically identified in the standard neural language generation setup, and so can- not be conditioned on to generate new strings. We then show how constrain L.MSs pro- duce output that satisfies evidential closure. A multimodal LLM must learn about the exter- nal world (perceptual learning); must learn a mapping from strings to states of the world (extensional learning); and, achieve fluency when generalizing beyond body of evidence, it must learn mappings from strings to their synonyms (intensional learning). The output of unimodal LLM must be synonymous with strings a validated evidence set. Finally, we present heuristic procedure, Bearn-Babblr Prune, that yields faithful output from an LLM by rejecting output that not synonymous with claims for which the LLM has evidence.
Many of the conceptual issues studied in natural language processing have received exten- sive treatment in the analytic philosophy of lan- guage (Quine, 1960; Davidson and Harman, 1972; Evans, 1982; McFetridge et al., 1992; McDowell, 1998). Conveniently, these treatments are often mathematically tractable.
One set of fundamental distinctions is between intension or meaning; extension or reference; and facts or states of the world, respectively. Words and sentences have meanings, which are equiv- alence classes of other words or sentences with which they are synonymous. They also have referents: states of the world that they map onto. Finally, there is external reality that the agent has access to, equipped with valuation function that assigns states of the world true false. Sen- tences are true when they correctly refer to states of the world that are truc.
A popular theory of meaning in the philosophy of language that links these three notions is the extensional semantics of Davidson (1967). This theory holds that the meaning of a sentence is just the set of states of the world in which that sentence is true.
1 Introduction
There is a growing body of evidence that LLMS systematically hallucinate (Ji et al., 2023; Maynez et al., 2020; Bang et al., 2023; Guerreiro et al., 2023; Dale et al., 2023). Hallucinations may limit the utility of LLMs, in addition having signif- icant implications for safety (Müller et al., 2020; Martindale and Carpuat, 2018; Martindale et al., 2019; Bender ct al., 2021).
Using this account, we can characterize a faithful speaker of a language as one who 1) uses their knowledge about the world 2) describe states of the world 3) using a variety of equivalent sen- tences. This entails that a faithful speaker must per- form three tasks: they must learn about the world
has been suggested that hallucinations occur because language models do not interpret training inputs semantically (Bender and Koller, 2020; Xiao and Wang, 2021; McKenna et al., 2023). We of- fer new formalization of this notion that allows explain why LLMs are inherently prone to hallucination, and what any faithful LLM must do: its output must be closed under synonymy with its evidence about the world, a condition we call
'e study intrinsic (Huang conflicting ballucinations (Zhang et al.. 2023); and extrinsic, or fact-con coct-conflicting hallueinations. This conception of hallu- cination does not include conceptions hallucination the literature: LLMs may produce output that ill-formed or contextually irrelevant, for instance (Guerreiro et al., 2023). 2 For accessible overviews, see Fitting (2022), Michaclson and Reimer (2022), David (2022).
2023), or input-

---

(perceptual learning); they must learn which sentences map onto which states of the world (extensional learning); and they must learn which sentences have the same meaning (intensional learning). A factual speaker performs the same tasks, with the difference that their evidence about the world is correct. Here, faithfulness to model imputs is conceptually prior to factuality, since, def- initionally, the information the model has about the world contained in its inputs.
sity of sentences for which the model has evidence (Theorem 5.10 and Theorem 5.11).
Third, we provide heuristic framework for build- ing factual or faithful LLMs, which we call Learn- Babble-Prune. In this setup, the output of an LLM is cross-checked against its evidence, and discarded if it is not a paraphrase of claim that it has evi- dence for. This ensures that the output of an LLM is consistent with its evidence. This ensures that the LLM is faithful its evidence, and hence, does not hallucinate.
We use this setup to state an impossibility result: neural probabilistic language models in the vein of Bengio et al. (2003) are not factual (Theorem 4.5). LLMs maximize the conditional probability of the generated strings given the corpus and the prompt. They do not explicitly learn states of the world, do not explicitly learn the meanings of words, and do not explicitly learn the referents of sentences. Each these types of information unobserved. As a re- sult, the conditional distributions learned by LLMs can be statistically independent of, or invariant to, their semantic content: that is, of the referents and the truth-conditions of the sentences in the corpus and prompts. So we may have variation in the truth falsity of state of the world without variation in the solution to a predictive model that generates the next sentence given prompt.
We consider two applications: when the evi- dence is corpus of strings, and when the evidence is in the form of sensor information.
If the evidence aarmeval-uugmentee language models (Guu et al.. 2020; Chen et al., 2017), then an LLM's s output is consistent with its retrieved body of evidence if its output is a paraphrase of a string in its evidence base. In this application, the model must learn paraphrases of sentences in order to cross-check the output of an LLM with its evidence base.
the form of text, as in some
If the evidence is in the form of information about the world gathered by sensors, as in some multimodal LLMs (Lian et al., 2023; Zhao et al., 2023b; Yuan et al., 2022), then, in addition to in- tensional learning, the LLM must learn mapping from perceptual information strings. Thus mul- timodal LLM is faithful if its output paraphrases information acquired by its perceptual learner, and factual if that perceptual learner is unbiased and consistent.
Because this semantic information is not con- tained in the conditional distribution from which an output string is generated, simulating from the learned distribution does not preserve this infor- mation, even when it is contained in the corpus (Theorem 4.6). Hence there no guarantee that LLMs are faithful to the semantic content of their inputs, either. We can think of this as the cause of hallucination in LLMs.
A final point is that, like any language speaker, an LLM can only make many true claims as are semantically entailed by the evidence it possesses (Williamson, 2000). Collecting and interpreting large bodies of evidence a vitally important task for the next generation of LLMs.
Second, we show conceptually how to build a faithful or factual LLM. The output of such an LLM must satisfy evidential closure: that is, its output must be synonymous with claims for which the LLM has evidence. This ensures that every claim made by the model is either directly corrobo- rated by evidence, or is a paraphrase of a directly corroborated claim. We first define the objective functions for faithful and factual LLMS using the- ory from the philosophy of language. We then decompose those objective functions into learnable distributions (Model 5.9). We show that the output of these models is faithful or factual, because solves the constrained learning task that incorpo- rates semantic information about the truth or fal-
2 Related work
2.1 Retrieval-Augmenttr Generation
Several approaches ground LLMs in external tex- tual knowledge hases (Chen et al., 2017; Lee et al., 2019; Guu et al., 2020), in which retriever model
2 *Intensional learning allows the speaker to say true things that they have never heard before: given a candidate string E, the speaker can verify it by first verifying the state of the world underpinning a different string Et, and then verifying that & is intensionally equivalent to e+. This is an example of semantic entailment (Beth, 1955). A fluent speaker of a language must he able to generalize beyond a set of observed sentence-use instances, and intensional learning allows speakers to do this.

---

is trained in order learn subsets of the training data that are more relevant for conditional text gen- eration. Asai et al. (2022) and Lee et al. (2021) highlight the role of evidence in controlling inci- dence of hallucination: models are less likely to hallucinate if they focus attention on passages with a high evidential value. Our approach provides theory to formalize the notion of evidential rele- vance, and proposes ex post consistency with the evidence enforce the factuality or faithfulness of the output of an L.M..
is that is, of what is not that it is not." This is correspondence theory of truth, in which truth is a property of sentences that correspond to states of the world (Schmitt, 2003).
Davidson (1967), building on work by Tarski (1936), equated the meaning of sentence with the circumstances in which that sentence was true: that the meaning of the sentence "p" is just that the state of the world p obtains. This is an extensional semantics: that the meaning of a sentence is the circumstances in which is true.
Frege (1892) noticed that distinct terms in lan- guage with the same referent could have different meanings associated with them. He described the meaning (intension) and reference (cxtension) of a term, noticing that it could count as nontrivial knowledge for person to note that "the Morning Star", and "the Evening Star", two terms with seem- ingly different senses in fact referred to the same object, Venus. It is type of knowledge to learn about objects;
2.2 Generalizable RL
Methods for generalizing reinforcement learning models in complex environments are also closely related (Agarwal et al., 2021; Zhao et al., 2023b; Belyaeva et al., 2023; Lian al., 2023). We can un- derstand differences in semantic content form of distribution shift, in which the desired output distribution and the observed input distribution dif- fer. Hence, generalizing across contexts in an RL setting is analogous to the problem of factual lan- guage generation: in each case, the output must be conditioned on the correct semantic information. This is not possible when that information is not observed.
different type of knowledge to learn about the names of objects. To language user, learning about intensions different from learning about extensions. As Quine (2008) put it: "truth depends in general on language and fact."
Learning about the world, learning which words refer which states of the world, and learning which words are synonymous together allow a speaker to attain fluency, by making true statements beyond a finite phrasebook of verified claims. A speaker whose utterances are constrained to be con- sistent with their evidence remains faithful to their knowledge about the world.
2.3 Causal Inference
The ability to generalize across semantic contexts is also closely connected to the identifiability of se- mantic information. Identifiability is a well-studied problem in causal inference in both computer sci- ence (Pearl, 1995; Shpitser and Pcarl, 2012; Barcin- boim and Pearl, 2012: Lee and Bareinboim, 2020; Li et al., 2023) and in statistics, epidemiology, and the social sciences (Holland, 1986; Petersen and van der Laan, 2014; Lewbel, 2019). One moral from this paper is that a grounded LLM is one that is causally connected to its environment. This also has a philosophical foundation in causal theories of perception (Grice and White, 1961; Hyman, 1992).
We now formalize these ideas.
3.2 Formalization
Consider stock of syntactically well-formed strings a natural language & E L; a set of possible states of the world a E Ω2 and a set of extensional or reference maps R L - Ω which map strings onto states of the world. We write R(2) = to show that é is the string of natural language that has as its referent the state w. We say that the pair (e, R(C)) is sentence, or interpreted string.
set
3 Setup and theory
3.1 A very brief philosophical overview
Aristotle (350 BCE [1989]), in Metaphysics, gave the following definition of truth: "To say of what
We require that the language L is fully- interpreted and unambiguous: for each sentence E L,, there exactly one element of w E Ω such that R(()) = w. We also require that the domain Ω is non non-empty.
'Agarwal et al. (2021) point out that generalization failures can happen even when the input and the output contexts are the same context. This is because, even though the contexts are identical, the model did not learn the relevant semantic information in each context, so its output is not conditioned on the relevant information, See Section 4.4.
A semantic structure s E S assigns to each state of the world Ω a binary value. We associate

---

each distinct structure with unique mapping V, - {0, 1}. which we call valuation func- tion. Each structure s represents a possible assign- ment of values to states of the world.
Equivalently, two sentences are synonymous if there exists no assignment of values states of the world that would make one sentence true and the other false. For example, "The Eiffel Tower is the tallest building in France", and "It is not the case that the Eiffel Tower is not the tallest building in France" are true in all and only the same circum- stances they are synonymous. There is no set of possible assignments of values states of the world that would make one of these claims true and the other false.
We are interested in pairs (e, R(()) evaluated under structures E S. That is, we are interested in strings and their referents sentences and the assignment of truth-values to those sentences. We start with states of the world.
Definition 3.1. A state of the world 12 obtains under structure if (,(w) 1.
Because meaning, this account, is defined in terms of truth, synonymy is prese-presrrving That is, if we know that a particular sentence is true, then we know that any sentence synonymous with that sentence is also true.
We take particular structure so as the one that describes the actual world, and denote its valuation function Vo- We say that a state of the world w actually obtains if Vo(w) 1. Learning about the real world therefore involves learning which facts actually obtain, or Yw Vo(w).
Proposition 3.5 (Closure under synonymy).
We next describe reference. The extensional map R : I. S2 maps strings of natural language onto states of the world. For example, the sentence "Joe Biden won the 2020 President election" is a string that refers to the state of the world in which Joe Biden won the 2020 Presidential election.
ve, 6' L: [([R()) 1 and R(O) R((") Vo[R(e))] =1
Proof. Apply Definition 3.4.
Proposition 3.5 says that if we start with a sen- tence that is true, then any sentence that has the same meaning as that sentence is also true. This is important for allowing language models make claims beyond an existing knowledge base of ver- ified claims: to ensure than an LLM is faithful, its output must be closed under synonymy with its evidence.
Definition 3.2 (Reference/Extension)) A string & refers to, has its extension, describes Ω if (()) W.
Truth is a property of strings and the states of the world that they describe. If the sentence suc- cessfully describes a state of the world that in fact obtains, we say that the sentence is true.
Why LLMs Hallucinate
Definition 3.3 (Truth). A sentence (t, R(E) is true under a structure s if and only if the state of the world it describes obtains under that is, V.[R(())=1 11
4.1 Setup
Consider a neural language generation task, as mo- tivated by Bengio et al. (2003) and others. The analyst observes a training corpus of strings C = {-; ) and learns (possibly masked) model that maximizes:
We are specifically interested in the privileged structure that deseribes reality, 8p- That is, we are interested sentences that are actually true, be- cause they refer to states of the world that actually obtain.
The meaning of sentence, in Davidson's 's ac- count, is just the set of circumstances in which a sentence is true. We say that two sentences syn- onymous, intensionally equivalent, if they are true on all and only the same structures. Definition 3.4 (Synonymy/Ineessional Equivalence (Davidson)). Sentences (4, R(G)), (Cg. R(E)) are synonymous, or intensionally equivalent, if Vs: V.(R())) (e))(
f(C)
II arg max Pr(x,(0p41)
(1)
Then, given prompt P, the model generates an output string ÿ:
= arg max f(x|C,
(2)
Good out-of-sample performance on conventional benchmarks is taken as evidence that f(x|C, P) f(x] P) (Zhao et al., 2023a).
*Wo use the word 'obtains" to distinguish valuations on states of the world from valuations on sentences.

---

4.2
Characterizing Factual and Faithful LLMs
Vaart, 1998, 62), in the sense that, for two possible structures 8, s', and for any given output string ÿt
A factual LLM is that produces only true sen- lences.
V.[R(O) + (.(()() + max f(=|C, P.V.( + x arg frg (R(z)))
(3)
Definition 4.1 (Factual LLMs). An LLM is factual VV Vo[R(O)] 1.
That is, an LLM is factual if every string out- put of the LLM refers to state of the world that actually obtains.
That is, we may have different assignments of truth- values to states of the world, without any difference in which sentence is generated by the LLM. Joe Biden in fact won the 2020 Presidential election, but given particular prompt and corpus, "Donald Trump won the 2020 Presidential election" may be the sentence that has the highest conditional probability being observed. This because the language model does not observe the state of the world referred to by either string, and does not output sentence conditional on this information. Truth-values of states of the world are not ob- served identified in the model. Hence we have Vs [(r] P.V.). V.) f(x(C, And in particular, it follows that, for every * 80 [xx[C P, V,) = [x][C, C, P). The model solution is invariant to assignments of rruth- to states of the world. To put it another way. Vo is an unidenti- fied nuisance parameter (Basu, 1977). This entails that:
factual LLM therefore solves (using Defini- tion 3.3):
Problem 4.2 (Factual LLMs).
max PP s.t. Vo[[()]] =1
This constraint encodes two additional pieces of information: what state of the world the output sentence ' refers to, and whether or not it obtains. A faithful LLM one that produces sentences that are semantically entailed by the agent's 's evi- dence. Suppose that we have an estimator of Vg. Then,
Definition 4.3 (Faithful LLMs). An LLM is faithful i'V ([(R))) 1.
faithful LLM solves:
Problem 4.4 (Faithful LLMs).
arg max f(x|C, = + Vo(R(()
(4)
max [x P) s.t. [[[[)))]
Or, in other words, sentence may be the solution to the maximization problem even if false. And hence, there is no guarantee than an LLM will be strictly truthful. In general, for any > O:
Here the constraint that the output consistent with an estimated truth-value. If Vo is a biased esti- mator of Vo. consistency with the model's evidence does not guarantee that its output is true.
D P)I <e + P.
(5)
A natural way state this is that LLM is faith- ful if its output is consistent with its information about the world. An LLM is factual, if, in addi- tion, that information is accurate. In this formaliza- tion, we can say that a faithful LLM is factual Vo= = Vo.5
<e
Statistical similarity of any two distributions does not imply statistical similarity of two distribu- tions that depend on additional semantic informa- tion about the world.
4.4 A verified training corpus is not enough: Similarity does not entail synonymy
4.3
Truth as an unidentified nuisance parameter
It might be hoped that a model of the type of Equa- tion (2) solves Problem 4.2 indirectly. After all, doesn't the training corpus contain information about states of the world (Akyürek al., 2022)? And don't L.MMs seem to generate useful informa- tion, or correctly summarize existing information, some of the time (Petroni et al., 2019)?
The solution to Problem 4.2 depends informa- tion that is not learned in the setup of Equation (2). This leads to an identification problem (van der
'In practice, we might be interested in different asymptotic conceptions of factuality: for instance, an LLM could he almost surely factual if V. 23 Vo-

---

Firstly, if the training corpus contains statements that are false, ambiguous, or fail to refer to any entity, straightforward to see that any set of generated sentences can also contain false, ambigu- ous statements, or exhibit referential failure.
[=())))) V=([(=;)) vo[[(z;)] 1. Sup- pose Ex' C, [=(((=))] 1 and Vg/ [R([)'))] 0. Then take D = x' and Vo = Vg', and the claim follows.
We say that a training corpus is verified if it contains only true, unambiguous statements with no referential failure. But it is still possible for model that solves Equation (2) fail to solve Problem 4.2.
The key step in each argument is that no infor- mation about Vo is learned by the model. So a structure can always exist which the output sen- tence is false. And since we do not observe the truth-values of states of the world, we have no way of ruling out the possibility that the structure on which the sentence is false is in fact 80-
A major innovation in the LLM literature has been to create models that successfully generate sentences that have not been previously observed, via encoder-decoder representations of the space of sentences (Wu et al., 2016; Vaswani et al., 2017). Interestingly, however, this actually makes it more likely that LLMs will produce false sentences, since it makes it possible for the model gen- erate sentences that go beyond the information contained within the verified training corpus. these previously-unseed sentences are not also con- strained to refer to facts about the world, there is no guarantee that these will be true, even when the training corpus is verified.
This result does not say that LLMs always hallu- cinate. But it does say that, when LLM learns distribution that does not incorporate explicit fac- tual or extensional information, always possi- ble for an LLM to hallucinate.
Building Factual/Faithful LLMs: How To Get (Evidential) Closure
How do we go beyond the negative result above? We require that the output of an LLM is equal to the closure under synonymy of strings that refer verified information. That is, every string output by the LLM either refers to a claim that verified, or is a synonym of a claim that is verified. By Proposition 3.5, all such sentences will be true. Any LLM that satisfies this property is then factual. If we require only that the output is closed under synonymy with strings that are synonymous with the agent's evidence, irrespective of its credibility, the LLM is faithful.
The problem is that similarity does not entail synonymy: have no guarantee that generated sentence is synonymous with any sentence in the training corpus (see Proposition 3.5). Distribution shift from the training context to the desired output context is always possible when the LLM does not learn the correct distribution.
4.5 Formal results
Theorem 4.5 (LLMs are not factual).
5.1 A Symmetry Group Semantics
arg max f(x|C, ū +> Vol =
It is helpful to use the technology of symmetry groups to formally motivate intensional and exten- sional learning. This section restates and develops results in Kiddon and Domingos (2005).
Proof. Consider structures s such that and V=(R( 0. Since
V. (.(())
V3, Vy are unobserved, we have that f(x|C, P, V.V)) = f(,|C, V.) f(x|C, P).
Definition 5.1 (Symmetry). A function g X - X is symmetry of a set X if (g(x)) x X) X.
Set Vi = Vg. Then arg max (x = 9 but
x Vo[R(() 0, and the claim follows.
Definition 5.2 (Symmetry Group). symmetry group of set X is an ordered pair (G,o) such that if g is a symmetry of X then g E G, and is function composition.
Theorem 4.6 (Training on verified information does not induce factuality).
arg max Vz, C. CV = +
Definition 5.3 (Orbit). The orbit of x E X under a symmetry group is the set {g(x) 1 E G}
[o(R())==
We motivate paraphrases as functions that, given a list of strings, permute pairs of strings that have the same referent.
Proof. Suppose Va; E C, R()) + R(xx), and consider the structures s, s such that Va, E C

---

Definition 5.4 (Paraphrase Map). A bijective func- tion π L + L is paraphrase map vl R({)= ((m(())
Proposition 5.7.
P, CAAC
Essentially, is permutation, with the added constraint that it can permute only strings in list that have the same referent. We collect the set of paraphrases in the collection II. This a symmetry group of L, since, every т II a permutation of the elements of L, and hence applying to returns the same list of strings, that is, L.
IEst
E S(ec, P ((
IEST
LLM
Intensional
Ground truhh Evidence
represents the informa- tion about the world in each string e of the source language I,
Here, [(Vo[T(e*))
Proposition 5.5. The set of paraphrase maps (II, o) is symmetry group of the set L.
If we do not have ground truth set of strings, but instead learn about the world via sensors (a vision model, for example), we can further decompose f(V[[((e) ) = 1) as follows:
Proof. We suppose that that Ω is non-empty, and that L is fully-interpreted and unambiguous, so that, for each E L, w E Ω R(6)- = w. Then, since a bijection, and hence a permuta-
Proposition 5.8.
each π E tion, we have that, VT C IT, (() & C L) = L, so that each is a symmetry of L. It is straightfor- ward to show that (II, o) satisfies the group axioms: any composition of permutations ग, T' E II defines a permutation x" с II; composition is associative; there is a trivial permutation; and each permuta- tion has an inverse permutation, Hence oII, is symmetry group of the set L.
[(Vol((ct)] =) S(R(((e) = Volw) =
w
E S((((t) 1))p(())))) =1)
WCR
Σ )W)
Extensional Learner
Perceptial Learner
Model 5.9 (A Factual/Faithful Multimodal LLM).
S(AC, 1)
Definition 5.6 (Semantic Orbit). The orbit E L under II is the set ((f) = [x)] e I]).
Σ Σ S(e/,, ()
S(r(Et) )W f(w)
TEAFTWER
L.M
Intensional Learner
Extensional Perceptual Learner
That is, the semantic orbit of a sentence is the set of sentences that refer to the same state of the world as that sentence.? We collect the set of unique orbits of a language L the set F.
Learner
In words, this models the constraint that w ob- tains, there is a sentence in the source language that refers w, and that the output sentence & is syn- onymous with sentence in the source language. Hence Model 5.9 satisfics evidential closure. The representation in Model 5.9 above covers both fac- tual and faithful LLMs.
5.2 Factual LLMs
With this setup in place, we now in position to decompose the constrained learning task described Problem 4.2. We introduce a source language L+, which contains the strings in some source set of sentences, and e the set of unique orbits of L+. We can then rewrite the objective function as follows:
Theorem 5.10. Suppose f(w) is an oracle percep- tual learner, we have consistent intensional and extensional learners, and LLM that solves Equa- tion (2). Then Model 5.9 is factual.
Proof. We have shown in Proposition 5.7 and Proposition 5.8 that f(]C P, Vo( = 1) S(AC, P)
"Note that the set of unique orbits of partitions into sets of strings that have the same referent. Further, for each unique orbit, there is unique state of the world to which every sentence that orbit refers. We can extend the notation of valuation function so that it takes the set of unique arbits as its pre-image. We write: ((] = + vł E 1(F) V[[R(O) =
(())))
Hence
'Encyclopedia authors have essentially already done the extensional and perceptual learning for us: they have encoded information about the environment as text. It is in this sense that perceptual and extensional learning are necessary for truthful language generation even in the textual casc.

---

Problem 4.2 is solved if and only if this model can be consistently estimated. Since f(w) is an oracle, Vo(w) f(w) = 1, and since f(AI((E)) F(AI(())) that
É denotes the of strings that consist of both model's 's explicit evidence about the world, and their paraphrases. This set is evidentially closed, by Proposition 3.5. So the output of Model 5.13 is evidentially closed, and the model is faithful to its evidence.
by assumption, we have P. 1), solving Problem 4.2.
The moral is that a faithful or factual LLM must learn about the world, directly (through sensor per- ception) or indirectly (through text corpora); and that its output must be constrained to be synony- mous with claims that are contained within its evi- dence set. This provides theoretical motivation for grounding, and clarifies specifically what ground- ing is intended to accomplish.
Theorem 5.11. If we have a perceptual learner that is not an oracle, consistent intensional and extensional learners, and an LLM that solves Equa- tion (2), then Model 5.9 is faithful to its perceptual learner.
Proof. Define Volw) = f(w). Then, 1, and
Volw) = 1 7 f(w)
5.4 Learn-Babble-rrune framework for factual/faithful LLMs via rejection sampling
f(ACC, PY(Ce(((t(())))(( S(AC, ([[(() lem 4.4.
1), solving Prob-
We propose a procedure we call Saan-Baablee- Prune to implement this.
5.3 Evidence Set Representation
We can state these results even more simply, how- ever. Consider the following set:
In the Learn phase, an agent learns about the world, either directly through perceptual learning, or indirectly by observing some stock verified information. If this information is acquired through perception, these sentences are translated into natu- ral language, via multimodal encoder-decoder sys- tem. The agent additionally learns stock of para- phrases of sentences, via paraphrase corpora meth- ods (Ormazabal et al., 2022), or via contrastive learning methods (Yang et al., 2021).
Definition 5.12 (Evidence Set).
We say that i is the output of an intensional learner: the set of learned paraphrases of strings. Vo is the set of stipulated or learned labels attached strings and their paraphrases. In either case, this is the set of strings that comprise, or are synony- mous with, a body of verified information about the world.
In the Babble phase, LLM generates stock of candidate sentences.
In the Prune phase, generated sentence is cross- checked against the its Evidence Set. If the tence is verified, or if a paraphrase of verified sentence, printed. Otherwise, it rejected.
This definition is helpful, because it allows us to re-express Model 5.9 as:
Model 5.13 (An Evidence-Grounded LLM).
f(A(C, P)I{EE $}
5.5 Applications of Bhaan-Babble-Prute
Theorem 5.14. Suppose i i T. Then Model 5.13 is faithful.
5.5.1 Example 1: Text-To-Text
Learn Ground truth. Scrape an online encyclope- dia, and designate this as the Evidence Set É. Intensional learning. Learn a set of paraphrases of strings in the Evidence Set, and add them to the Evidence Set.
Proof. i + I Me É} Vo[R(()) 1, so Model 5.13 solves Prob- lem 4.4.
Theorem 5.15. Suppose i + I and Vo + Vo- Then Model 5.13 is factual.
Babble An LLM generates a response to query. Prune The response is rejected if it is not para- phrase of sentence in the Evidence Set.
Proof. (o] > > = Vo(i(e)) 1, and 1-1 > Ee - Vo) = 1. so Model 5.13 solves Problem 4.2.
"This was inspired by He (2018).

---

5.5.2 Example 2: Image-To-Text
Conclusions
Learn Extensional learning. Pre-train visual en- coder, which learns a mapping from images (states of the world) to strings.
LLMs hallucinate because their output is not con- strained to be semantically consistent with their imputs, so there is guarantee that any evidence about the world contained in their inputs is pre- served in their outputs.
Perceptual learming. Designate test set of images ground truth about the environment. Apply the visual encoder to this test set of images. Designate output as our Evidence Set.
To build a faithful or factual LLM it is necessary to constrain the output of a model to be consis- tent with claims for which the model has explicit evidence.
Intensional learning. Learn a set of paraphrases of strings in the Evidence Set, and add them to the Evidence Set.
In practice, this means acquiring large bodies of machine-readable string evidence or using sensors (perceptual learning) combined with sensor-to-text encoders (extensional learning) to validate the out- put of an LLM with evidence. Paraphrase learning methods can be used to expand the LLM's vocab- ulary (intensional learning). We propose simple method to implement this in practice via rejection sampling.
Babble An LLM generates response to query. Prune The response is rejected if it is not para- phrase of sentence in the Evidence Set.
Algorithm LBP:
Text-to-Tex. Text
1: Input: (T, CP,PP
2: Learn: P(
b Learn 3: Learn: vet E E L: f(e e I(et))
4: for É do
Any input-faithful LLM is limited in what it can say by what it has evidence for. Generating large-scale evidence bases likely to be a much bigger binding constraint that the parameter size of the model, for instance, and may require a rethink of how computational and financial resources are allocated to the design of LLMs. This is a challenge for the next generation of LLMs.
5: if A(tt)ee c É then
6:
B+ÉUE
7: end if
8: end for
9: Generate: ~~ Cx
Babble Prune
if É then
Print: y
12: else
13:
Print: don't know."
Algorithm 2 LBP: Multimodal-tor toxxex
14:
end if
I: Input: (g L,,+C,,C
2: Learn: P)
b LLM
Since the source domain is arbitrary, Example covers wide variety of use cases, which can of course be combined. The output of these proce- dures is faithful, because if a given candidate out- put is not synonymous with claim for which the model has have explicit evidence, is not printed." 10
Learn: flwobs)
Perceptual
Learn: AET Ltt [(tt|
Extensional
Learn: WE L: f(e E I(et))
Intensional
for e+ E L+ do
if ff(( (altt f(wain) = then
É+ Euet
8:
9: end if
5.6 The Limits Factual or Faithful LLMs
10: end for
Any model of the type of Model 5.13 limited in what it can say by the size of its evidence base. In practice, the dimension of may be consider- ably smaller than the parametric knowledge of the language stored in many LLMs. Any use-case for factual LLMs requires the collection and verifica- tion of large amount of factual information. Any factual or faithful LLM can only generate as much output as it can verify.
11: for E L do
12: i I(Et) A
É then
É+ÉuE
13:
14: end if
15: end for
16: Generate: 9 fxx|C, P)
D Babble
17: if ú E É then
Prune
18: Print:
19: else
20:
Print: "I don't know."
10 WWitgeenttein (1922, 189): "Whereof one cannot speak, thereof one must remain silent." This also applies to L.Mss.
21: end if

---

Limitations
Acknowledgements
Empirical performance and truthfulness
This paper is dedicated to Stephen Williams. The author would like to thank Micah Carroll, Kirk Bansak, Orr Paradise, and three anonymous refer- ees for helpful comments.
Enforcing consistency with evidence via rejection sampling is relatively inefficient way to constrain output to be factual or faithful. We expect that RL approaches could implement procedure analo- gous Learn-Babble- Prune more efficiently, with tolerable loss of accuracy. The purpose of this framework to highlight, a high-level, the kind tasks that any such RL approach would have to do. As such, it is primarily intended as a conceptual contribution. Further, strict factuality may be an undesirably high bar in some applications: clearly it depends on the case.
References
Rishabh Agarwal, Marlos C. Machado, Pablo Samuel Castro, and Marc G. Bellemare. 2021. Contrastive behavioral similarity embeddings for generalization in reinforcement learning. International Conference on Learning Representations.
Ekin Akyürek, Tolga Bolukbasi, Frederick Liu, Binbin Xiong, Ian Tenney, Jacob Andreas, and Kelvin Guu, 2022. Towards tracing factual knowledge in language models back to the training data.
Safety and ground truth
Aristotle. 350 BC. Metaphysics.
A factual LLM constructed above would require either a gold-standard data set of labelled data. However, there are clear safety concerns raised by treating some data sets as ground truth com- pared to others. Further, what counts as evidence in some domains is contestable: reasonable people disagree. Widely available benchmark data sets have well-studied biases (Paullada et al., 2021).
Akari Asai, Matt Gardner, and Hannanch Ha- jishirzi. 2022. Evidentiality-guided generation for Knowledge-intensive NIP tasks.
Yejin Bang, Samuel Cahyawijaya, Naycon Lee, Wen- liang Dai, Dan Su, Bryan Wilie, Holy Lovenia, Ziwei Ji, Tiezheng Yu, Willy Chung, Quyet V. Do, Yan Xu, and Pascale Fung. 2023. multitask. multilingual. multimodal evaluation ChatGPT on reasoning, hal- lucination, and interactivity.
Compositionality
Elias Barcinboim and Judea Pearl. 2012. Causal infer- ence by surrogate experiments: z-identifiability.
Our framework does not consider the semantic con- tent of constituents of sentences, instead consid- ering strings as primitive, and assuming that they each refer to one fact. is straightforward to extend our account to sentences that refer to the compo- sition of multiple states of the world and logical operators, which we leave to future work.
Debabrata Basu. 1977. On the elimination of nuisance
parameters. Journal of the American Statistical As- sociation, 72(358):3553366
Anastasiya Belyaeva, Justin Cosentino, Farhad Hor- mozdiari, Krish Eswaran, Shravya Shetty, Greg Corrado, Andrew Carroll, Cory Y. McLean, and Nicholas A. Furlotte. 2023, Multimodal LLMs for health grounded in individual-specife data.
Language and Vagueness
We assume that stock of strings is interpretable and unambiguous. Many sentences in natural lan- guage cannot be considered to have a truth-value, or may be ambiguous.
Emily M. Bender, Timnit Gebru, Angelina McMillan- Major, and Shmargaret Shmitchell. 2021. On the dangers of stochastic parrots: Can language mod- els be too big? Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Trans- parency, FAccT '21, page 610 623, New York, NY. USA. Association for Computing Machinery.
Philosophy of language
The relevant philosophy of language literature is vast and we cannot hope to do it justice in this pa- per. Further, some conceptual distinctions that are important to understanding the papers cited are not made in this paper. The hope is that the setting provides offers a statistically tractable implemen- tation of conceptual material that is covered in the papers cited. Subtleties, and perhaps even major distinctions, are likely to be lost translation.
Emily M. Bender and Alexander Koller. 2020. Climbing towards NLU: On meaning, form, and understanding in the age of data. In Proceedings of the 58th Annual Meeting of the Association for Computational Lin- guistics, pages 5185-5198, Online, Association for Computational Linguistics.
Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Jauvin. 2003. A neural probabilistic lan- guage model. Journal of Machine Learning Re- search, 137-155

---

Evert Willem Beth. 1955. Semantic Entailment and Formal Derivability. Woord-Hollandeee
Paul W. Holland. 1986. Statistics and causal infer- ence. Journal of American Statistical Association, 91396)994--60
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017. Reading Wikipedia to answer open- domain questions. In Proceedings of the 55th Annual Meeting of the Association for Computational Lin- guistics ( (Volume 1: Long Papers), pages 1870-1879) Vancouver, Canada. Association for Computational Linguistics.
Shaohan Huang. Li Dong. Wenhui Wang, Yaru Hao. Saksham Singhal, Shuming Ma, Tengchao Lv, Lei Cui, Owais Khan Mohammed, Barun Patra, Qiang Liu, Kriti Aggarwal, Zewen Chi, Johan Bjorck, Vishrav Chaudhary; Subhojit Som, Xia Song, and Furu Wei. 2023. Language is not all you need: Align- ing perception with language models.
David Dale, Elena Voita, Janice Lam. Prangthip Hansanti, Christophe Ropers, Elahe Kalbassi, Cyn- thia Gao, Loic Barrault, and Marta Ruiz Costa-jussä 2023. HalOmi: A manually annotated benchmark for multilingual hallucination and omission detection machine translation. ArXiv, abs/2305. 1746.
John Hyman. 1992. The causal theory of perception. The Philosophical Quarterly (1950-), 42(168):277- 296.
Ziwei Ji. Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung. 2023. Survey of halluci- nation in natural language generation. ACM Comput- ing Surveys, 55(12) 15(11)1--3.
Marian David. 2022. The Correspondence Theory of Truth. In Edward N. Zalta, editor, The Stanford Ency- clopedia of Philosophy, Summer 2022 edition. Meta- physies Research Lab, Stanford University.
Chloe Kiddon and Pedro Domingos. 2005. Symmetry- based semantic parsing.
Donald Davidson. 1967. Truth and meaning, Synthese, 771)3334-3233
Kenton Lee, Ming-Wes Wei Chang, and Kristina Toutanova. 2019. Latent retrieval for weakly supervised open domain question answering.
Donald Davidson and Gilbert Harman, editors. 1972. Semantics of Natural Language. Springer Nether- lands.
Kyungjae Lee, Seung-wor wong Hwang, Sang-eun Han, and Dohyeon Lee. 2021. Robustifying multi-hop QA through pseudo beeudo-viidentiality training. In Proceed- ings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 1ith International Natural Language Processing
Gareth Evans. 1982. The Varieties of Reference. Ox- ford: Oxford University Press.
Melvin Fitting, 2022. Intensional Logic. In Edward N. Zalta and Uri Nodelman, editors, The Stanford Ency- clopedia of Philosophy, Winter 2022 edition. Meta- physics Research Lab, Stanford University.
Joint Conference (Volume 1: Long Papers), pages 61 10-6119, Online. Association for Computational Linguistics.
Gottlob Frege 1892. On Sinn and Bedeutung. In Michael Beaney, editor, The Frege Reader, pages 151-172. Blackwell.
Sanghack Lee and Elias Bareinboim. 2020. Causal effect identifiability under partial-observabiiity In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5692-5701. PMLR.
H. P. Grice and Alan R. White. 1961 Symposium: The causal theory of perception. Proceedings of the Aristotelian Society, Supplementary Volumes, 35:121- 168.
Arthur Lewbel. 2019. The identification zoo: Mean- ings of identification in econometrics. Journal of Economic Literature, 57(4):835-90)
Nuno M. Guerreiro, Elena Voita, and André Martins. 2023. Looking for needle in a haystack: A com- prehensive study of hallucinations in neural machine translation. In Proceedings of the 17th Conference of the European Chapter of the Association for Com- putational Linguistics, pages 1059-1000 1075, Dubrovnik, Croatia. Association for Computational Linguistics.
Ang Li, Scott Mueller, and Judea Pearl. 2023. Epsilon- identifiability of causal quantities.
Long Lian, Baifeng Shi, Adam Yala, Trevor Darrell, and Boyi Li. 2023. I.L.Mgroudded video diffusion models.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasu- pat, and Ming-Was Wei Chang. 2020. Realm: Retrieval- augmented language model pre-training.
Marianna Martindale and Marine Carpuat. 2018. Flu- ency over adequacy: A pilot study in measuring user trust imperfect MT. In Proceedings of the 13th Conference of the Association for Machine Transla- tion in the Americas (Volume 1: Research Track), pages 13-25, Boston, MA. Association for Machine Translation in the Americas.
Xiaoyu He. 2018 Babble.
Felix Hill, Olivier Tieleman, Tamara Glehn, Nathaniel Wong, Hamza Merzie, and Stephen Clark. 2020. Grounded language learning fast and slow.

---

Marianna Martindale, Marine Carpuat, Kevin Duh, and Paul McNamee. 2019. Identifying Fluently inade- quate output in neural and statistical machine transla- tion. In Proceedings of Machine Translation Summit
W. Quine. 2008. Animadversions on the Notion of Meaning: Philosophy Colloquium, University of Pennsylvania, December 6, 1949, pages 152-156.
Harvard University Press.
XVII: Research Track, pages 233-243, Dublin, Ire- land. European Association for Machine Translation.
W. V. Quine. 1960. Word & Object. MIT Press.
Frederick F Schmitt, editor. 2003, Theories of truth. Wiley Blackwell Readings in Philosophy, Blackwell Publishing, London, England.
Joshua Maynez, Shashi Narayan, Bernd Bohnet, and Ryan McDonald. 2020. On faithfulness and factu-
ality in abstractive summarization. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 1906-199 1919, On-
Ilya Shpitser and Judea Pearl. 2012. Effects of treatment on the treated: Identification and generalization.
line. Association for Computational Linguistics.
Alfred Tarski. 1936. The concept of truth in formalized languages. In A. Tarski, editor, Logic. Semantics, Metamathematics, pages 152-278. Oxford University Press.
John McDowell. 1998. Meaning, Knowledge, and Real- it. Harvard University Press.
I. G. McFetridge, John Haldane, and Roger Scruton. 1992. Logical necessity and other essays. Philoso- phy, 67(260):264-266
A. W. van der Vaart. 1998. M-and Z- E-Etimmators, Cam- bridge Series in Statistical and Probabilistic Mathe- matics, page 41-84. Cambridge University Press.
Nick McKenna, Tianyi Li. Liang Cheng, Moham- mad Javad Hosseini, Mark Johnson, and Mark Steed- man. 2023, Sources of hallucination by large lan- guage models inference tasks.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017, Attention is all you need.
Eliot Michaelson and Marga Reimer. 2022. Reference. In Edward N. Zalta, editor, The Stanford Encyclo- pedia of Philosophy, Summer 2022 edition. Meta- physics Research Lab, Stanford University.
Timothy Williamson. 2000. Knowledge and its Limits. Oxford University Press.
L. Wittgenstein. 1922. Tractatus Lagico-Philoxxppiicus
Mathias Müller, Annette Rios, and Rico Sennrich, 2020.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe Le, Mohammad Norouzi. Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao. Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Eukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang. Cliff Young, Jason Smith. Jason Riesa, Alex Rudnick, Oriol Vinyals. Greg Corrado, Macduff Hughes, and Jeffrey Dean. 2016. Google's neural machine translation system: Bridging the gap between human and machine trans- lation.
Domain robustness in neural machine translation.
Aitor Ormazabal, Mikel Artetxe, Aitor Soroa, Gorka Labaka, and Eneko Agirre. 2022. Principled para- phrase generation with parallel corpora. In Proceed- ings of the 60th Annual Meeting of the Association for Computational Linguistics Volume 1: Long Pa- pers), pages 1621-1638, Dublin, Ireland. Association for Computational I. Linguistics.
Amandalynne Paullada. Inioluwa Deborah Raji, Emily M. Bender, Emily Denton, and Alex Hanna. 2021. Data and its (dis)contents: A survey of dataset development and use in machine learning research. Patterns, 2(1 100336.
Yijun Xiao and William Yang Wang. 2021. On hal- lucination and predictive uncertainty in conditional language generation. In Proceedings of the 16th Con- ference of the European Chapter of the Association for Computational Linguistics: Main Volume, pages 2734-2744, Online. Association for Computational Linguisties.
Judea Pearl. 1995. Causal diagrams for empirical re- search. Biometrika, 82(4):669-688,
Maya L. Petersen and Mark J. van der Laan. 2014. Causal models and learning from data. Epidemi- ology, 25(3):118
Haoran Yang. Wai Lam, and Piji Li. 2021. Contrastive representation learning for exemplar-guided para- phrase generation.
Fabio Petroni, Tim Rocktäschel, Sebastian Riedel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, and Alexander Miller. 2019. Language models as knowl- edge bases? In Proceedings of the 2019 Confer- ence on Empirical Methods Natural Language Pro- cessing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). pages 2463-2473, Hong Kong. China, Association for Computational Linguistics.
Zhecheng Yuan, Zhengrong Xue, Bo Yuan, Xuegian Wang, Yi Wu, Yang Gao. and Huazhe Xu. 2022. Pre- trained image encoder for generalizable visual rein- forcement learning.
Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang. Enbo Zhao, Yu Zhang. Yulong Chen, Longyue Wang, Anh Tuan Luu, Wei

---

Bi, Freda Shi, and Shuming Shi. 2023, Siren's song the Al ocean: survey on hallucination in large language models.
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang. Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang. Zican Dong, Yifan Du, Chen Yang, Yushuo Chen, Zhipeng Chen, Jinhao Jiang, Ruiyang Ren, Yifan Li, Xinyu Tang, Zikang Liu, Peiyu Liu, Jian- Yun Nie, and Ji-Rong Wen. 2023a. survey of large language models.
Yang Zhao, Zhijie Lin, Daquan Zhou, Zilong Huang, Jiashi Feng, and Bingyi Kang. 2023b. BuboGPT: Enabliig visual grounding in multi-modal LLMs.


Reviews:
[{"review_id": "nZFl4K1njg", "reviewer": "Reviewer_L6mo", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and feedback! We have been thinking about how to make the proposed approach more concrete and useful for applied researchers and practitioners.\n\nWe propose: \n\ni) to include the section **Implementation examples** following $\\S 4.3$. (We consider this to be in the spirit of `reporting additional experiments'.) \n\nii) to include an abridged version of the below discussion of **multimodal encoders** and **contrastive methods** following the proposed $\\S 4.4$, either in its own section, or in the section on related literature. (We consider this to be in the spirit of `adding additional references to the literature'.) \n\n### **Applications of Learn-Babble-Prune**\n\n**Example 1: A factual text-to-text LLM**\n\n*Learn:* \n\n 1. Perceptual learning: We scrape an online encyclopedia, and designate this as our verified set of strings. \n 2. Intensional learning: We learn a set of paraphrases of the verified set of strings.\n\n*Babble:* An LLM generates a response to a query. \n\n*Prune:* The response is rejected if it is not a paraphrase of a sentence in the verified set of strings. \n\n**Example 2: A faithful image-to-text LLM** \n\n*Learn:* \n 1. Extensional: We pre-train a visual encoder, which learns a mapping from images (states of the world) to strings. \n 2. Perceptual: We designate a test set of images as ground truth about the environment. We apply the visual encoder to this test set of images.  We designate its output as our verified set of strings. \n 3. Intensional: We learn a set of paraphrases of the verified set of strings.\n\n*Babble:* An LLM generates a response to a query about the environment. \n\n*Prune:* The response is rejected if it is not a paraphrase of a sentence in the verified set of strings. \n\nSince the source domain is arbitrary, Example 2 covers a wide variety of use cases. \n\n[figures] \n\nNote that the text-to-text learning example is different to the world-to-text learning example, in that there is no explicit extensional learning in the former. There, the encoding of information about the external world has already been done -- by the authors of the encyclopedia entry.\n\n### **Examples of extensional, perceptual, and intensional learners**\n\n**Multimodal encoders as extensional and perceptual learners** \n\nWhen we train a multimodal [any domain]-to-text encoder, we do extensional learning, because we learn a mapping from some source domain (i.e. states of the world) to text. \n\nWhen we apply the multimodal encoder to a ground-truth test set (observations of our environment), we are doing perceptual learning. The output strings are treated as our knowledge about the world. \n\nThis connects to the literature on generalizable RL, especially in visual learning, where pre-trained encoders are used (e.g. Yuan et al. 2022, Radford et al, 2021, Tachet et al. 2018, Zhu et al. 2017). Similarly, approaches that use intermediate representations to improve generalization are closely related ([Chen et al. 2020](https://arxiv.org/abs/2011.06698)) This should not be entirely surprising, since the problem outlined in $\\S 3$ is an example of distribution shift. \n\n**Contrastive similarity methods for intensional and extensional learning**\n\nIntensional case: take $\\ell, \\ell' \\in L$ strings, and $\\mathcal{L}$ a loss function. Then, learning $\\mathcal{L}(\\ell, \\ell')$ is learning the similarity between strings. A paraphrase is an exact match; similarity is not synonymy, per the discussion above. But we might get synonymy when $\\mathcal{L}(\\ell, \\ell') < \\epsilon$, and contrastive pre-training could be used for intensional learning. \n\nExtensional case: take $\\ell \\in L$, $x \\in X$, training observations in some non-text domain, and $y \\in Y$ binary labels. Then learning the set of triples $(\\ell, x, y) \\:  \\mathcal{L}(\\ell, x, y) < \\epsilon $ is extensional learning. \n\n**Paraphrase methods for intensional learning**\nA wide variety of methods for generating paraphrase corpora exist (e.g. Huang and Chang. 2021;  Egonmwan and Chali, 2019; Hu et al. 2019).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This paper addresses a crucial and timely issue in the field of Language Learning Models (LLMs) – the problem of systematic hallucination. By providing a new formalization and drawing upon concepts from analytic philosophy of language, the authors offer valuable insights into the inherent challenges faced by LLMs in maintaining truthfulness. The introduction of the model comprising three essential learners – perceptual, extensional, and intensional – presents a novel approach to generate strictly truthful outputs. The proposed \"Learn-Babble-Prune\" procedure serves as a heuristic example of how to achieve this goal, guiding researchers towards conceptual clarity and highlighting the significance of addressing hallucination in language models. Overall, the paper's contributions have the potential to enhance the reliability and credibility of future LLMs.", "reasons_to_reject": "- Lack of empirical evidence: The paper lacks concrete experimental validation, weakening the credibility of its claims and proposed solutions.\n\n- Overreliance on abstract concepts: The heavy use of analytic philosophy of language makes the paper less accessible to a broader audience in the natural language processing community.\n\n- Inadequate practical demonstration: The proposed \"Learn-Babble-Prune\" procedure remains a heuristic example, with unclear feasibility and applicability, hindering its real-world impact.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper explores the challenges faced by truthful Language Learning Models (LLMs) and the identification problem of generating accurate sentences beyond the training data, leading to hallucination. The authors identify three essential tasks for a truthful LLM: perceptual learning, extensional learning, and intensional learning. They show that failure to perform these tasks can lead to hallucination, even with training on a factual learner-generated corpus. Additionally, the paper proposes the \"Learn-Babble-Prune\" procedure to ensure strictly truthful outputs from LLMs by employing rejection sampling in the presence of consistent perceptual, extensional, and intensional learners.", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JFJB5E6oVg", "reviewer": "Reviewer_Leq6", "summary": "", "questions": "A/ Below are some elements of the mathematical exposition which I find troubling. Given the very tight deadlines for reviewing, I did not have enough time to fully work out all of the details of the proposal; nonetheless I would appreciate if the authors could clarify these:\n- Definition 4.3 for an orbital seems to devolve into $X$ for all $x$ (given that all $g$'s are symmetries, all of their images should be exactly $X$). Maybe the authors meant the set $\\\\{g(x) | g \\in G \\\\}$?\n - The definition of a paraphrase map $\\pi$ lines 283 sq, seems problematic. You define it as \"_a function $\\pi$ that maps a string $\\ell$ onto its paraphrases._\" \nThis is not a function in the mathematical sense since one item is associated to multiple images, making the concept you introduce somewhat unwieldy. From a conceptual point of view I don't see how to construe paraphrasing as a function: all means of producing paraphrases need not apply to all sentences, and one sentence can have any number of paraphrases. I would suggest that a more natural way of conceiving paraphrases might be to rely on a partition of $L = \\\\pi_1 \\cap \\dots \\cap \\pi_n$ with added conditions; for instance such that $\\forall \\pi_i ~ \\forall \\ell_1, \\ell_2 \\in \\pi_i \\quad R(\\ell_1) = R(\\ell_2)$.\n- You do nonetheless provide a more rigorous definition of paraphrase maps in definition 4.4. However, unless I'm mistaken, this definition is not consistent with claim 4.5:\n  + we can construct a function $\\pi_0$ that maps all strings $\\ell$ unto a given constant string $\\ell_0$, or formally $\\forall \\ell \\in L ~ \\pi_0(\\ell) =  \\ell_0$.\n  + In such a scenario, we do have $\\exists \\ell ~ R(\\ell) = R(\\pi_0(\\ell)$: by construction, we have $\\pi_0(\\ell_0) = \\ell_0$ and thus $R(\\pi_0(\\ell_0)) = R(\\ell_0)$, thereby satisfying definition 4.4\n  + but $\\pi_0$ is *not* a symmetry of $L$, since $\\\\{\\pi_0(\\ell) : \\ell \\in L \\\\} = \\\\{\\ell_0 \\\\} \\neq L$, contradicting definition 4.1\n  + therefore claim 4.5 does not follow.\n- Another degenerate case impacts claims 4.5 and 4.7 occurs if $R$ maps onto too few elements (e.g., taking $\\forall \\ell \\in L \\quad  R(\\ell) := \\omega_0$ )", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the above comments, which are very helpful! We appreciate close attention to the math. \n\n\n**Technical points on $\\S 4.1$**\n\n- {$g(x) | g \\in G$} was indeed the intended definition.\n\n - The informal version of the definition of a paraphrase map should read ``a bijective function $\\pi$ that maps strings onto paraphrases.'' Likewise Definition 4.4 should specify that $\\pi$ is bijective, and the quantifier should be $\\forall$ rather than $\\exists$. (For expository purposes, there is actually no need to introduce $\\pi$ before $\\S 4$; we will delete the informal introduction of paraphrase maps on p.4, and edit Proposition 2.5 so that the second condition is stated in terms of R instead.)\n\n  - We do not intend to motivate $\\pi$ as a correspondence. We are interested in the collection of bijective paraphrase maps $\\Pi$. \n\n     - Intuitively: $\\pi$ is a permutation of L that swaps only strings that have the same referent (meaning). \n\n     - Constructing the collection of paraphrase maps $\\Pi$ from paraphrases $\\pi$ is then essentially the same thing as constructing the set of all permutations (hence $\\Pi$ and $\\pi$). \n\n     - The natural generating set here is the set of two-place semantic substitutions; i.e. swapping any two strings in a list that have the same referent. The collection of all such two-place substitutions is the set of all (semantic) permutations, aka paraphrases. \n\n     - The conclusion that $\\Pi$ is a symmetry group of $L$ is then essentially the same claim that the set of all permutations of $X$ is the symmetric group of $X$. \n\n- Two additional assumptions were included in an earlier version of this paper (and we propose adding these back in). We believe these rule out the degenerate cases discussed. Every string has exactly one referent, and that there is at least one referent. Specifically:\n\n     - A language $L$ is fully-interpreted if: $\\forall \\ell \\in L, \\exists ! \\omega \\in \\Omega$ such that $R(\\ell) = \\omega$.\n     \n     - $\\Omega$ is non-empty.\n\n- Since $\\pi$ is a bijection, we start with the full list of words, and every substitution of words with the same meaning returns the same list of words. (This is an informal proof of Claim 4.5.)   \n\n- Once the map $R$ is determined, $\\Pi$ is determined, so given a fully-interpreted language, the collection of acceptable transpositions is given, not something that we can construct however we like. \n\n- With this context specified, the proof of Claim 4.5 is very simple (and we propose including this). \n\n- Since each $\\pi \\in \\Pi : L \\to L$ is a bijection, and hence is a permutation of the elements of $L$, we have that, $\\forall \\pi \\in \\Pi$: {$\\pi(\\ell) : \\ell \\in L$}$ = L$. Hence $\\Pi$ is a symmetry group of the set $L$. \n\n- We propose Claim 4.6 and $\\S 4.1.2$ should be replaced by:\n\n     - Definition 4.6: The orbit of $\\ell \\in L$ under $\\Pi$ is the set $I(\\ell) =$ {$\\pi(\\ell) | \\pi \\in \\Pi$}.\n\n- This cleans up notation, since $\\pi$ is already defined in terms of R, and allows us to express the second line of model 4.9 as:\n\n$$Pr(\\ell \\in I(\\ell))Pr(I(\\ell) | \\omega)Pr(\\omega) $$ \n\nwhich is simpler. Further $\\S 4.1.2$ is not correct as written. We do not need a symmetry group account of extension: we just need a learnable map from $L \\to \\Omega$. (Thinking about visual encoders clarified this point.) \n\n- Lastly, the notational changes in Model 4.9 are carried through to Algorithm 1. \n\n- Notice that the collection of unique orbits does, in fact, define a partition of $L$, as per the reviewer's proposal.  \n\n**The scope of the term hallucination**\n\nThis point is well-taken.  \n\nNote that definition 3.1 defines (strictly) truthful LLMs, which would be a factual LLM.  We omitted from this draft the definition of a (conditionally) truthful LLM, which would be a faithful LLM. \n\nThis paper was originally titled 'Towards Truthful LLMs'. Perhaps 'Towards factual and faithful LLMs' would be more appropriate as the kicker in the title. \n\nWe would be happy to add a paragraph providing additional clarification on this point, and to contextualize the scope of the contribution as directly bearing on a subset of types of hallucination. We are also open to opting for this alternate title, if ``hallucinate'' is considered misleading or overly broad.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The paper develops a cogent theoretical framework and can provide novel insights on issues that are currently hotly debated in the NLP community. I believe it could generate interesting discussions. \n- The approach is deeply rooted in analytical philosophy, and therefore draws an interesting connection between a current issue and a vast, underused literature. I strongly believe that such approaches should be fostered \n- The paper proposes a (mostly theoretical) procedure to advance the field towards truthful LLMs, a worthwhile endeavour that the community would benefit from.", "reasons_to_reject": "- I have some concerns with specific definitions and claims. See the \"questions\" box for details; as the article currently stands, I am uncertain that the framework is mathematically sound. At the very least, there seems to be a couple of crucial assumptions being left out the formalism.\n\n- On a conceptual level, I am not certain that truthfulness necessarily encompasses everything that the community construes as hallucinations. Take the following two examples:\n  + a  model generating an incoherent cooking recipe, by introducing ingredients that were not mentioned in the list, or listing incompatible steps (e.g., pureeing and then slicing the same ingredient). As (English) recipes are usually written as sequences of instructions, this complicates the derivation of a truth value for the models' productions&mdash;whereas the community might nonetheless frame this as a hallucinatory output.\n  + a model can inject true, but entirely irrelevant strings that the community would construe as hallucinations. Consider for instance the following constructed example, which would be a strongly detached hallucination in the sense of [Guerreiro et al (2023)](https://aclanthology.org/2023.eacl-main.75/):\n> The following contains an English translation of the French sentence \"La tour Eiffel est grande.\" : \"Donald Trump did not manage to close his umbrella, and the Eiffel tower is tall.\"", "questions_to_authors": "A/ Below are some elements of the mathematical exposition which I find troubling. Given the very tight deadlines for reviewing, I did not have enough time to fully work out all of the details of the proposal; nonetheless I would appreciate if the authors could clarify these:\n- Definition 4.3 for an orbital seems to devolve into $X$ for all $x$ (given that all $g$'s are symmetries, all of their images should be exactly $X$). Maybe the authors meant the set $\\\\{g(x) | g \\in G \\\\}$?\n - The definition of a paraphrase map $\\pi$ lines 283 sq, seems problematic. You define it as \"_a function $\\pi$ that maps a string $\\ell$ onto its paraphrases._\" \nThis is not a function in the mathematical sense since one item is associated to multiple images, making the concept you introduce somewhat unwieldy. From a conceptual point of view I don't see how to construe paraphrasing as a function: all means of producing paraphrases need not apply to all sentences, and one sentence can have any number of paraphrases. I would suggest that a more natural way of conceiving paraphrases might be to rely on a partition of $L = \\\\pi_1 \\cap \\dots \\cap \\pi_n$ with added conditions; for instance such that $\\forall \\pi_i ~ \\forall \\ell_1, \\ell_2 \\in \\pi_i \\quad R(\\ell_1) = R(\\ell_2)$.\n- You do nonetheless provide a more rigorous definition of paraphrase maps in definition 4.4. However, unless I'm mistaken, this definition is not consistent with claim 4.5:\n  + we can construct a function $\\pi_0$ that maps all strings $\\ell$ unto a given constant string $\\ell_0$, or formally $\\forall \\ell \\in L ~ \\pi_0(\\ell) =  \\ell_0$.\n  + In such a scenario, we do have $\\exists \\ell ~ R(\\ell) = R(\\pi_0(\\ell)$: by construction, we have $\\pi_0(\\ell_0) = \\ell_0$ and thus $R(\\pi_0(\\ell_0)) = R(\\ell_0)$, thereby satisfying definition 4.4\n  + but $\\pi_0$ is *not* a symmetry of $L$, since $\\\\{\\pi_0(\\ell) : \\ell \\in L \\\\} = \\\\{\\ell_0 \\\\} \\neq L$, contradicting definition 4.1\n  + therefore claim 4.5 does not follow.\n- Another degenerate case impacts claims 4.5 and 4.7 occurs if $R$ maps onto too few elements (e.g., taking $\\forall \\ell \\in L \\quad  R(\\ell) := \\omega_0$ )", "paper_topic_and_main_contributions": "This paper proposes a theoretical framework to understand why LLMs struggle to produce truthful outputs. This framework is based on an analytic take on the philosophy of language, and provides a theoretical procedure to devise systems that would systematically produce truthful outputs.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "- line 543: mode 4.10 is strictly truthful, should be model 4.9\n- equation 4, Theorem 3.3, Model 4.9 should not continue on past the margins."}, "extra_text": {}}, {"review_id": "CJMeiRnGCh", "reviewer": "Reviewer_gLhZ", "summary": "", "questions": "[1] It would be very interesting to see some connections between your ideal truthful LM and contemporary NLP/AI models. How would a perceptual learner look like? Would it be something similar to a visual encoder? How would the extensional learning work? Is aligning sentences to states of the world somewhat akin to contrastive pre-training?", "limitations": "", "rating": 4, "confidence": 1, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments and feedback! Your mention of visual encoders, and contrastive methods are very germane; thinking through the use of visual encoders in this context was particularly helpful. You raise a good point, and we stress that a wide variety of existing methods could be used to perform different tasks within this framework.\n\nBy way of a response to your question, we propose: \n\ni) to include the section **Implementation examples** following $\\S 4.3$. (We consider this to be in the spirit of `reporting additional experiments'.) \n\nii) to include an abridged version of the below discussion of **multimodal encoders** and **contrastive methods** following the proposed $\\S 4.4$, either in its own section, or in the section on related literature. (We consider this to be in the spirit of `adding additional references to the literature'.) \n\n### **Applications of Learn-Babble-Prune**\n\n**Example 1: A factual text-to-text LLM**\n\n*Learn:* \n\n 1. Perceptual learning: We scrape an online encyclopedia, and designate this as our verified set of strings. \n 2. Intensional learning: We learn a set of paraphrases of the verified set of strings.\n\n*Babble:* An LLM generates a response to a query. \n\n*Prune:* The response is rejected if it is not a paraphrase of a sentence in the verified set of strings. \n\n**Example 2: A faithful image-to-text LLM** \n\n*Learn:* \n 1. Extensional: We pre-train a visual encoder, which learns a mapping from images (states of the world) to strings. \n 2. Perceptual: We designate a test set of images as ground truth about the environment. We apply the visual encoder to this test set of images.  We designate its output as our verified set of strings. \n 3. Intensional: We learn a set of paraphrases of the verified set of strings.\n\n*Babble:* An LLM generates a response to a query about the environment. \n\n*Prune:* The response is rejected if it is not a paraphrase of a sentence in the verified set of strings. \n\nSince the source domain is arbitrary, Example 2 covers a wide variety of use cases. \n\n[figures] \n\nNote that the text-to-text learning example is different to the world-to-text learning example, in that there is no explicit extensional learning in the former. There, the encoding of information about the external world has already been done -- by the authors of the encyclopedia entry.\n\n### **Examples of extensional, perceptual, and intensional learners**\n\n**Multimodal encoders as extensional and perceptual learners** \n\nWhen we train a multimodal [any domain]-to-text encoder, we do extensional learning, because we learn a mapping from some source domain (i.e. states of the world) to text. \n\nWhen we apply the multimodal encoder to a ground-truth test set (observations of our environment), we are doing perceptual learning. The output strings are treated as our knowledge about the world. \n\nThis connects to the literature on generalizable RL, especially in visual learning, where pre-trained encoders are used (e.g. Yuan et al. 2022, Radford et al, 2021, Tachet et al. 2018, Zhu et al. 2017). Similarly, approaches that use intermediate representations to improve generalization are closely related ([Chen et al. 2020](https://arxiv.org/abs/2011.06698)) This should not be entirely surprising, since the problem outlined in $\\S 3$ is an example of distribution shift. \n\n**Contrastive similarity methods for intensional and extensional learning**\n\nIntensional case: take $\\ell, \\ell' \\in L$ strings, and $\\mathcal{L}$ a loss function. Then, learning $\\mathcal{L}(\\ell, \\ell')$ is learning the similarity between strings. A paraphrase is an exact match; similarity is not synonymy, per the discussion above. But we might get synonymy when $\\mathcal{L}(\\ell, \\ell') < \\epsilon$, and contrastive pre-training could be used for intensional learning. \n\nExtensional case: take $\\ell \\in L$, $x \\in X$, training observations in some non-text domain, and $y \\in Y$ binary labels. Then learning the set of triples $(\\ell, x, y) \\:  \\mathcal{L}(\\ell, x, y) < \\epsilon $ is extensional learning. \n\n**Paraphrase methods for intensional learning**\nA wide variety of methods for generating paraphrase corpora exist (e.g. Huang and Chang. 2021;  Egonmwan and Chali, 2019; Hu et al. 2019).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "[1] Truth-theoretic semantics seems like a relevant and new approach to LLM hallucination. \n\n[2] The proofs seem sound to me (but again, I am no formal semanticist).\n\n[3] The paper is very well written.\n\n[4] The overviews over the philosophical literature is accessible to non-philosophers.", "reasons_to_reject": "[1] The paper formalizes some desiderata for truthful language models, but provide no concrete suggestions on how to implement them. For instance, consider the Learn-Babble-Prune algorithm. What the authors propose is that a model should verify its statements against its knowledge of the world and possible synonyms, and output a sentence only if it is true. The interesting thing would be how to implement this, which is not addressed in the paper. \n\n[2] I feel there are some missed opportunities to connect this approach with contemporary NLP/AI work (see Questions).", "questions_to_authors": "[1] It would be very interesting to see some connections between your ideal truthful LM and contemporary NLP/AI models. How would a perceptual learner look like? Would it be something similar to a visual encoder? How would the extensional learning work? Is aligning sentences to states of the world somewhat akin to contrastive pre-training?", "paper_topic_and_main_contributions": "The paper provides a truth-teoretic account on why LLMs allucinate. It further establishes the logical preconditions that must be met for a language model not to allucinate. These pre-conditions are that a truthful language model should comprise (a) a perceptual learner that learns information about the world; (b) an extensional learner that maps sentences onto states of the world; and (c) an intensional learner which learns which sentences are synonymous. The paper further presents a toy algorithm that constrains LMs to only output truthful sentences. \n\nAs a disclaimer, I should say that this article is not related in any way to my areas of expertise, and I am surprised to see it assigned to me. I have never worked on formal semantics nor hallucination in LLMs.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "ll. 146-147 \"that that\"\n\nll. 218-219 \"R : L → Ω, which map states of the world onto strings of the language\". Here it seems that the direction is the opposite, from language to states of the world. \n\nl. 222 \"the pair ⟨ℓ, R(ℓ)⟩ is a sentence\". In l. 144, ℓ alone was a sentence."}}]

Author rebuttal:

Meta-review: Reviews provide scores of 3,4,4 for soundness and 4,4,4 for excitement.

Condensing the reviews, strengths and weaknesses including the following were mentioned.

Strengths:

- addresses a crucial and timely issue for the field (R1, R2, R3)
- interesting links to philosophy (R1, R2)

Weaknesses:

- no empirical evidence or validation (R1, R3)
- high degree of abstraction limits accessibility (R1)
- questions about mathematical soundness were originally raised by (R2), but their final soundness score is 4
Decision: Accept-Main