3 ms·

> hallucination is defined as inconsistencies between a computable LLM and a computable ground truth function. With this definition, you can trivially prove th

> hallucination is defined as inconsistencies between a computable LLM and a computable ground truth function. With this definition, you can trivially prove the titular sentence - "hallucination is inevitable" - is untrue. Let your LLM have a fixed input context length of one byte. Continue training the LLM until such a time as it replies to the input "A" with "yes" and all other inputs with "no". Define your computable ground truth function such that the correct output for the input "A" is "yes" and the correct output for all other inputs is "no". This LLM provable never hallucinates - we have exhaustively verified that its output matches the ground truth function for all possible inputs. There is nothing stopping inductively increasing the size of the input context and the number of entries in the ground truth table arbitrarily, and at no step do hallucinations become "inevitable".

resolutebat 3y ago
> Continue training the LLM until such a time as it replies to the input "A" with "yes" and all other inputs with "no". This is basically the same as saying "train your LLM until they never hallucinate", which reduces your claim to a tautology: an LLM trained not to hallucinate does not hallucinate. The trick is making that happen.
- ProxCoques 3y ago
  As I always tell my students: the solution to unreliable code is not to put the bugs in there in the first place.
  - paxcoder 3y ago
    [dead]
- Borealid 3y ago
  It's a tautology that for a given truth table mapping inputs to "correct" outputs there exists a function that produces that mapping. Saying that you can't train an LLM to NOT hallucinate is saying that it's impossible for any LLM to always produce output matching any particular truth table. There may exist truth tables where it's not possible to produce an LLM to match them (for some finite size of LLM perhaps), but my claim isn't a tautology - it's just an assertion that there exist some truth tables which an LLM can be trained to match. It may be tricky to make the LLM in the first place, but it's certainly not as tricky to verify it. You can test it with every input you consider to be present in the truth table, record its results, and throw it away if it doesn't match. The only possible results here are either non-convergeance or a "perfect" LLM. You can get rid of the non-convergeance if you bound the size of the LLM and literally iteratively verify every single possible model. The authors of the paper didn't do that. For trivially sized models and inputs, that's completely possible. For a 7B parameter model, nobody is doing that ever. But you can prove the title statement wrong with a ten-parameter model and a one-byte input.
deleted 3y ago
[deleted]
less_less 3y ago
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.
- Borealid 3y ago
  It's not a bad paper honestly, I just don't like it when people take a line from it and assume something untrue. The pigeonhole principle proves that if you only have N slots to work with, and you need to fit N+1 items into them, you're going to get at least one slot with at least two items. That makes sense, and it logically follows that constrained functions can't perfectly mirror less-constrained ones: at some point a "wrong" and a "right" input have to produce the same output.
  - calf 3y ago
    So is it saying LLMs have polynomial running time and that's it? LLMs can't solve SAT properly because of running time argument?
mepiethree 3y ago
> There is nothing stopping inductively increasing the size of the input context and the number of entries in the ground truth table arbitrarily This isn’t induction. You’ve only done the base case, not the induction hypothesis or induction step. Maybe you’ve done those steps in your head but that’s not really a trivial proof as you claim.
- Borealid 3y ago
  Induction is "if this is possible for value X, then it is also possible for value X+1". Where X isn't used as part of the step this is always true. Nothing I did depends on the size of either the input nor the truth table, so long as both are finite-size and so long as the truth table can be expressed as a function of the input. An LLM is an arbitrary convolution of the input text; for any mapping, some function you can call an "LLM" produces that function.

resolutebat 3y ago

> Continue training the LLM until such a time as it replies to the input "A" with "yes" and all other inputs with "no". This is basically the same as saying "train your LLM until they never hallucinate", which reduces your claim to a tautology: an LLM trained not to hallucinate does not hallucinate. The trick is making that happen.

ProxCoques 3y ago
As I always tell my students: the solution to unreliable code is not to put the bugs in there in the first place.
- paxcoder 3y ago
  [dead]
Borealid 3y ago
It's a tautology that for a given truth table mapping inputs to "correct" outputs there exists a function that produces that mapping. Saying that you can't train an LLM to NOT hallucinate is saying that it's impossible for any LLM to always produce output matching any particular truth table. There may exist truth tables where it's not possible to produce an LLM to match them (for some finite size of LLM perhaps), but my claim isn't a tautology - it's just an assertion that there exist some truth tables which an LLM can be trained to match. It may be tricky to make the LLM in the first place, but it's certainly not as tricky to verify it. You can test it with every input you consider to be present in the truth table, record its results, and throw it away if it doesn't match. The only possible results here are either non-convergeance or a "perfect" LLM. You can get rid of the non-convergeance if you bound the size of the LLM and literally iteratively verify every single possible model. The authors of the paper didn't do that. For trivially sized models and inputs, that's completely possible. For a 7B parameter model, nobody is doing that ever. But you can prove the title statement wrong with a ten-parameter model and a one-byte input.

deleted 3y ago

[deleted]

less_less 3y ago

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.

Borealid 3y ago
It's not a bad paper honestly, I just don't like it when people take a line from it and assume something untrue. The pigeonhole principle proves that if you only have N slots to work with, and you need to fit N+1 items into them, you're going to get at least one slot with at least two items. That makes sense, and it logically follows that constrained functions can't perfectly mirror less-constrained ones: at some point a "wrong" and a "right" input have to produce the same output.
- calf 3y ago
  So is it saying LLMs have polynomial running time and that's it? LLMs can't solve SAT properly because of running time argument?

mepiethree 3y ago

> There is nothing stopping inductively increasing the size of the input context and the number of entries in the ground truth table arbitrarily This isn’t induction. You’ve only done the base case, not the induction hypothesis or induction step. Maybe you’ve done those steps in your head but that’s not really a trivial proof as you claim.

Borealid 3y ago
Induction is "if this is possible for value X, then it is also possible for value X+1". Where X isn't used as part of the step this is always true. Nothing I did depends on the size of either the input nor the truth table, so long as both are finite-size and so long as the truth table can be expressed as a function of the input. An LLM is an arbitrary convolution of the input text; for any mapping, some function you can call an "LLM" produces that function.