Innovation: An Almost Characterization of Hallucination

Hallucination is a central limitation of large language models (LLMs), and substantial effort has been devoted to understanding and mitigating it. Towards this, Kalai and Vempala (STOC 2024) introduced a probabilistic framework formalizing calibration and hallucination, and showed that, with high probability, calibrated LLMs hallucinate roughly at the rate of the "missing mass", a measure of how incomplete the training data is relative to its source. This raises two fundamental questions: (i) what property of a calibrated LLM makes hallucinations unavoidable? and (ii) can hallucinations be avoided by giving up calibration? We answer these questions by introducing a simpler property we call innovation that measures the tendency of a model to produce outputs outside the training data. We show that innovation is implied by the condition for hallucination identified by Kalai and Vempala, and, further, that it is an almost characterization of hallucination: hallucination implies innovation, and conversely, innovation implies hallucination with high probability. We also provide lower bounds on the hallucination rate based on the "innovation rate", and by relating innovation rate back to missing mass, we obtain new hallucination rate lower bounds based on missing mass that extend the results of Kalai and Vempala.

Hallucination is a central limitation of large language models (LLMs), and substantial effort has been devoted to understanding and mitigating it. One way to understand how to eliminate hallucination is to ask the opposite question: what is the simplest possible requirement that can be imposed on an LLM under which it becomes inevitable that the model will hallucinate? Towards answering this, Kalai and Vempala developed a statistical framework formalizing what an LLM does, and mathematically proved that in this framework, any "calibrated" LLM must hallucinate. Their formalization of calibration, however, is quite subtle. Could there be a much simpler, and perhaps more fundamental, condition under which hallucinations become inevitable? We give a positive answer to this question by showing that a much simpler requirement, that the model "innovate" beyond its training data, already implies hallucination in this statistical framework. Our mathematical formalization of innovation also helps strengthen some of the quantitative predictions of the Kalai-Vempala theory concerning the rate at which models must hallucinate.