Why and how often hallucination occurs in LLMs

An interesting recent paper from Adam Kalai of 微软 and Santosh S. Vempala of Georgia Tech provides an interesting theoretical analysis of how often we should expect an ideal large language model (LLM) to "hallucinate" falsehoods. Simply stated, the rate of hallucinations is very close to the proportion of facts that appear exactly once in the training data.?

Their result follows from the concept of calibration in statistical estimation. If you are asked to repeatedly predict the probability of different events, we would say you are "well calibrated" if, among the times you state a 20% probability, the event ends up occurring 20% of the time, etc. LLMs are trained to predict a probability distribution over all possible textual completions. They generate their response by sampling a text completion from that distribution. Because LLMs are trained (at least during pre-training) using a proper scoring rule, usually log-likelihood, they learn to be well-calibrated predictors of text completions.

A well-calibrated LLM ought to arrive at a conditional probability distribution in which

P( never-before-seen-claim | prompt )

is well-calibrated, where "never-before-seen-claim" means that the claim did not appear in the training corpus. Assuming that far more fictional sentences are possible than factual ones, a never-before-seen-claim will almost always be false, so that this is very close to the frequency of hallucination.

After applying a mathematical theorem from I.J. Good (1953), they show this probability to be nearly equal to the proportion of claims that appear exactly once in the training data.?

Their new insight has direct applicability to addressing hallucinations of citations, biographies, legal cases, etc., and to understanding why certain types of facts might be more prone to hallucination than others. For example, with enough training data, genuinely unique medical diagnoses might be quite rare. And in some domains in which each problem solution is a chain of reasoning steps in which the logical rule used for each step occurs many times in the training data (even though the high-level problem is unique), the rate of hallucination on each step might be manageable.