xu-2024-hallucination-prone-problem-classes

IN premise — summaries/2026/08/24/xu-2024-hallucination-innate-s4-discussion.md

Created 2026-08-24T17:11:29+00:00

Xu et al. (2024) identify specific hallucination-prone problem classes: combinatorial listing (Ω(2ⁿ) time, guaranteed for O(nᵏ)-time LLMs), Subset Sum/SAT (guaranteed under P≠NP for polynomial-time LLMs), Presburger arithmetic (Ω(2^(2^(cn))) time, guaranteed for O(2ⁿ)-time LLMs), and first-order logic entailment (undecidable, guaranteed for all computable LLMs).

Summary

Xu et al. show that for certain categories of problems, LLMs aren't just statistically likely to make errors — they are mathematically guaranteed to produce wrong answers, because solving those problems correctly would require more computation time than the model's architecture allows. This means hallucinations on tasks like combinatorial enumeration, SAT, Presburger arithmetic, and first-order logic entailment are not fixable with better training data; they are structural impossibilities, so any system relying on an LLM for these tasks should assume failure and route those cases elsewhere.