kalai-2023-tightness-construction-algorithm

IN premise — summaries/2026/08/24/kalai-2023-hallucination-inevitable-s7-upper-bounds-on-hallucination-rate.md

Created 2026-08-24T17:10:59+00:00

The tightness construction defines the output distribution as g(y) = dMF/|U| for unobserved factoids and (1−dMF)/|O| for observed factoids, achieving Mis∞(g,p) ≤ 3√(ln(4/δ)/n) while hallucinating at rate g(H) ≤ dMF, proving the bound cannot be improved in general.

Summary

This result shows that a particular theoretical guarantee on how closely a system's output can track a reference distribution is the best achievable in the worst case — no smarter algorithm can beat that rate. In practice, it means any system claiming to operate near that performance ceiling is already as good as mathematically possible, and the hallucination rate it incurs is an unavoidable cost of staying within that bound.