The core argument in this paper it seems to me from scanning it is that because P != NP therefore LLMs will hallucinate answers to NP-complete problems. I think this is a clever point and an interesting philosophical question (about math, computer science, and language), but I think people are mostly trying to apply this using our commonsense notions of "LLM hallucination" rather than the formal notion they use in th…
The place where this argument gets into trouble is where it says "we define hallucination in a formal world where all we care about is a computable ground truth function f on S." This demands a reliable, computable predicate for truth. That alone is probably not possible.
If, however, we are willing to accept a ground truth function with outputs
- True
- False
- Unknown
- Resource limit exceeded
that problem can be avoided. Now the goal is manageable - return True or False only when those results are valid, and try to reduce the fraction of useful queries for which Unknown and Resource Limit Exceeded are returned.The same problem comes up in program verification systems, and has been dealt with in the same way for decades. Sometimes, deciding if something is true is too much work.