Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
This paper establishes a rate-distortion theorem demonstrating that hallucinations in large language models are an inevitable consequence of information-theoretic optimal memory compression when storing sparse facts, forcing the model to confidently assign high scores to non-facts rather than abstain.