s-sparse-assumption-exponential-gap-facts-hallucinations
IN premise — summaries/2026/08/24/kalai-2023-hallucination-inevitable-s4-the-model-and-guarantees.md
Created 2026-08-24T17:10:59+00:00
The s-sparse facts assumption states |F| ≤ e^(−s)·|H| with probability 1 over D_world, encoding that there are exponentially more plausible false factoids than true ones (e.g., paper citations, 5W combinations).
Summary
In any given context, the number of true, specific facts (like correct citations or accurate answer combinations) is a tiny fraction of the number of false statements that still sound completely plausible. This means that a system generating text is overwhelmingly more likely to stumble onto a believable-sounding error than to land on a true fact, which is why verification and grounding steps are essential rather than optional.