kalai-2023-corollary1-lower-bound-formula
IN premise — summaries/2026/08/24/kalai-2023-hallucination-inevitable-s5-guarantees.md
Created 2026-08-24T17:10:59+00:00
Under s-sparse regular Dworld, the hallucination rate satisfies g(H) ≥ dMF − Mis_b(g,p) − 3e^{−s}/δ − √(6ln(6/δ)/n) with probability ≥ 1−δ, where s-sparse means |F| ≤ e^{−s}|H|.
Summary
When the actual information in a world is tiny compared to the full space of things a system could claim, there is a hard, unavoidable floor on how often the system will fabricate unsupported statements. This means no amount of extra training data or parameter tuning can drive that error to zero in such sparse settings; the sparsity itself guarantees a minimum level of hallucination.