I also disagree with the paper, but not for the same reason. > With this definition, you can trivially prove the titular sentence - "hallucination is inevitabl

I also disagree with the paper, but not for the same reason. > With this definition, you can trivially prove the titular sentence - "hallucination is inevitable" - is untrue. Unsurprisingly, that one sentence fragment doesn't capture the entirety of their assumptions. Instead they prove something intuitively obvious, along the lines of: LLMs with arbitrary-length inputs and certain resource restrictions (e.g. they can take up to poly-time to compute, and this poly-time behavior must be provable, so that during training they don't take even longer by mistake) cannot compute certain functions that don't have those restrictions (e.g. can take more than poly-time, or must take poly-time but a proof of this is not needed). For some cases this proof assumes P != NP. Then they argue that some useful real-world questions are likely to be in the class that the LLM cannot compute, basically because you can ask math problems to LLMs and math problems are sometimes really hard. This formal model is asymptotic (assumes arbitrary-length inputs etc), but in my experience this kind of theorem is usually true for realistic problems even at modest query lengths. But this isn't the same as proving that hallucination is inevitable, because (according to any reasonable definition) an LLM (or like, a person, or whatever) should be allowed to say "I don't know", and this should not be considered a hallucination. Then an LLM (or whatever) can avoid hallucinating, and the question becomes how much useful work it can do without hallucinating.