Research map / Probabilistic and scientific modeling / Variational and generative sampling
No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical framework showing non-hallucinating learning of generative models is impossible for proper agnostic learners even with two hypotheses, while improper learners achieve it when the facts set lies in a finite-VC concept class, with matching sample-complexity bounds.
Problem
Learnability of generative models that avoid hallucinations (probability mass on non-fact outputs) from truthful training data, under proper and improper learning paradigms.
Approach
Formalizes hallucination rate relative to a facts set and a faithful demonstrator, shows agnostic proper non-hallucinating learning is impossible, and restores learnability by assuming the facts set lies in a finite-VC concept class, using a version-space learner that maximizes an information measure subject to non-hallucination.
Key results
- Theorem: for a size-2 hypothesis class, no proper learner achieves alpha-agnostic non-hallucinating learning for any alpha>0, even with relative hallucination rate and a non-hallucinating hypothesis present.
- Improper learner over a finite-VC concept class is 0-approximately non-hallucinating learnable with sample complexity O((VC log(1/eps)+log(1/delta))/eps), for any information measure.
- Matching lower bound: worst-case concept classes of VC-dimension d require Omega(d/eps) samples for the out-of-sample mass measure; Omega(d) for Shannon entropy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| restrict facts sets to a finite-VC-dimension concept class and use an improper learner | non-hallucinating generative learning · finite-VC concept classes | hallucination rate: 0 | Helped |
| restrict facts sets to a finite-VC-dimension concept class | improper non-hallucinating learning · finite-VC concept classes | sample complexity: n≤O((VC(C)log(1/ε)+log(1/δ))/ε); Ω(d/ε) | Mixed |
| rely solely on training data, without inductive bias about the facts set | proper non-hallucinating learning · hypothesis class of size 2 | hallucination rate: 1 | Hurt |
| use proper rather than improper learning when facts sets come from a finite-VC concept class | non-hallucinating generative learning · finite-VC concept classes | learnability | Hurt |
| require the demonstrator to be sufficiently informative for the concept and hypothesis classes | proper non-hallucinating learning · finite-VC concept classes | hallucination rate: ε | Helped |
| use a proper learner with two concepts and a demonstrator that provides no distinguishing information | proper non-hallucinating learning · two-set construction | hallucination rate: 0.99; 1/2 | Hurt |
| use only the out-of-sample-mass objective on worst-case VC-dimension-d classes | improper non-hallucinating learning · worst-case concept classes | sample complexity: Ω(d/ε) | Hurt |
| use Shannon entropy as the information measure | improper non-hallucinating learning · VC-dimension-d concept classes | sample complexity: Ω(d) | Hurt |
Surprising findings
- Agnostic proper non-hallucinating learning is impossible even for a hypothesis class of size two, unlike distribution PAC learning where finite classes are always learnable.
- Empirical-distribution learner never hallucinates on truthful data but fails to generalize, motivating the information-measure requirement.
Limitations
- Results are primarily conceptual; the learning rules are computationally inefficient.
- Facts set is treated abstractly; no experiments on real language or image models.
- Proper learning positive result requires a sufficiently-informative demonstrator condition that is hard to verify.
Experimental setup
Metrics: hallucination rate total variation distance out-of-sample mass Shannon entropy
Builds on: distribution PAC learning no-free-lunch theorems sigma-smoothness Fano's inequality
Closest papers by meaning
- Estimating the Hallucination Rate of Generative AI (NeurIPS 2024 · similarity 0.91)
- Self-Correcting Decoding with Generative Feedback for Mitigating Hallucinations in Large Vision-Language Models (ICLR 2025 · similarity 0.88)
- In-Context Sharpness as Alerts: An Inner Representation Perspective for Hallucination Mitigation (ICML 2024 · similarity 0.88)
- Generate, but Verify: Reducing Hallucination in Vision-Language Models with Retrospective Resampling (NeurIPS 2025 · similarity 0.88)
- Analyzing and Mitigating Object Hallucination: A Training Bias Perspective (AAAI 2026 · similarity 0.88)
- Refine Knowledge of Large Language Models via Adaptive Contrastive Learning (ICLR 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.