99
LLMs Will Always Hallucinate, and We Need to Live With This
arxiv.orgAs Large Language Models become more ubiquitous across domains, it becomes important to examine their inherent limitations critically. This work argues that hallucinations in language models are not just occasional errors but an inevitable feature of these systems. We demonstrate that hallucinations stem from the fundamental mathematical and logical structure of LLMs. It is, therefore, impossible to eliminate them through architectural improvements, dataset enhancements, or fact-checking mechanisms. Our analysis draws on computational theory and Godel's First Incompleteness Theorem, which references the undecidability of problems like the Halting, Emptiness, and Acceptance Problems. We demonstrate that every stage of the LLM process-from training data compilation to fact retrieval, intent classification, and text generation-will have a non-zero probability of producing hallucinations. This work introduces the concept of Structural Hallucination as an intrinsic nature of these systems. By establishing the mathematical certainty of hallucinations, we challenge the prevailing notion that they can be fully mitigated.
The thing that always bothered me about the Halting Problem is that the proof of it is so thoroughly convoluted and easy to fix (simply add the ability to return “undecidable”) that it seems wanky to try applying it as part of a proof for any kind of real world problem.
(Edit: jfc, fuck me for trying to introduce any kind of technical discussion in a pile-on thread. I wasn’t even trying to cheerlead for LLMs, I just wanted to talk about comp sci)
That’s not “a fix”, that’s called “a practical workaround” which is used in the real world all the time.
How would token prediction machine arrive at undecidable? I mean would you just add a percentage threshold? Static or calculated? How would you calculate it?
(Why jfc? Because two people downvoted you? Dood, grow some.)
It’s easy to be dismissive because you’re talking from the frame of reference of current LLMs. The article is positing a universal truth about all possible technological advances in future LLMs.
Then I’m confused what is your point on Halting Problem vis-a-vis hallucinations being un-mitigable qualities of LLMs? Did I misunderstood you proposed “return undecided (somehow magically, bypassing Halting Problem)” to be proposed solution?
How do you know something is truly undecidable and not deterministically solvable with more computation?
Mathematically you might be able to prove I don’t always (and I’m not convinced of that even; I don’t think there is an inherent contradiction like the one used for the proof of Halting), but the bar for acceptable false positives is sufficiently low and the scenario is such an edge case of an edge case of an edge case, that anyone trying to use the whole principle to argue anything about real-world applications is grasping at straws.
I suggest you re-read through the proof of the halting problem, and consider precisely what it’s saying. It really has been mathematically proven.
But fair enough, the program made in the halting problem you probably wouldn’t ever encounter. But the consequence is, if you were trying to write an algorithm that solves the halting problem, you would have to sacrifice some level of correctness - and technically any algorithm you write would fail or loop forever on an infinite number of programs, surely one of them would be useful. Consider the Collatz conjecture. I severely doubt anyone would be able to “decide” the collatz conjecture program halting without it being a very specific proof of it (with maybe some generalisations).