3 ms·

> because P != NP therefore LLMs will hallucinate answers to NP-complete problems. I haven't read the paper, but that sounds like it would only be true if the

> because P != NP therefore LLMs will hallucinate answers to NP-complete problems. I haven't read the paper, but that sounds like it would only be true if the definition of "hallucinating" is giving a wrong answer, but that's not how it's commonly understood. When people refer to LLMs hallucinating, they are indeed referring to an LLM giving a wrong (and confident) answer. However, not all wrong answers are hallucinations. An LLM could answer "I don't know" when asked whether a certain program halts and yet you wouldn't call that hallucinating. However, it sounds like the paper authors would consider "I don't know" to be a hallucinating answer, if their argument is that LLMs can't always correctly solve an NP-complete problem. But again, I haven't read the paper.

Fripplebubby 3y ago
Yes, I think you're right. I think one way to phrase the authors' argument is: * There is a class of problems which are harder than polynomial time complexity to solve, but are not np-complete * LLMs will generate an "answer" in formal language to this class of problems posed to it * LLMs can at most solve problems with polynomial time complexity due to their fundamental design and principles * Therefore, LLMs cannot solve > polynomial problems and not np-complete problems either All of which I buy completely. But I think what people are more interested in is, why is it that the LLM gives an answer when we can prove that it cannot answer this problem correctly? And perhaps that is more related to the commonsense notion of hallucination than I first gave it credit for. Maybe the reason that an LLM gives a formal language answer is the same reason it gives a hallucinatory answer in natural language. But I don't think the paper sheds light on that question
- dragonwriter 3y ago
  > why is it that the LLM gives an answer when we can prove that it cannot answer this problem correctly? Brcause LLMs are not “problem solving machines” they are text completion models, so (when trained for q-and-a response) their function is to produce text output which forms a plausible seeming response to the question posed, not to execute an algorithm which solves the logical problem it communicatss. Asking “why do LLMs do exactly what they are designed to do, even when they cannot do the thing that that behavior implies to a human would have been done to produce it” just reveals a poor understanding of what an LLM is. (Also, the fact that they structurally can't solve a class of problems does not mean that they can't produce correct answers, it means they can't infallibly produce correct answers; the absence of a polynomial time solution does not rule out an arbitrarily good polynomial time approximation algorithm, though its unlikely than an LLM is doing that, either.)
  - someplaceguy 3y ago
    > their function is to produce text output which forms a plausible seeming response to the question posed Answering "I don't know" or "I can't answer that" is a perfectly plausible response to a difficult logical problem/question. And it would not be a hallucination.
    - dragonwriter 3y ago
      > Answering "I don't know" or "I can't answer that" is a perfectly plausible response to a difficult logical problem/question. Sure, and you can train LLMs to produce answers like that more often, but then users will say your model is lazy and doesn't even try, whereas if you train it to be more likely to produce something that looks like a solution more often, people will think “wow, the AI solved this problem I couldn't solve”. And that’s why LLMs behave the way they do.
      - someplaceguy 3y ago
        > Sure, and you can train LLMs to produce answers like that more often, but then users will say your model is lazy and doesn't even try, whereas if you train it to be more likely to produce something that looks like a solution more often, people will think “wow, the AI solved this problem I couldn't solve”. Are you saying that LLMs can't learn to discriminate between which questions they should answer "I don't know" vs which questions they should try to provide an accurate answer? Sure, there will be an error rate, but surely you can train an LLM to minimize it?
        dragonwriter 3y ago
        > Are you saying that LLMs can't learn to discriminate between which questions they should answer "I don't know" vs which questions they should try to provide an accurate answer? No, I am saying that they are specific trained to do that, and that the results seen in practice on common real-world LLMs reflect the bias of the specific training they are given for providing concrete answers. > Sure, there will be an error rate, but surely you can train an LLM to minimize it? Giving some answer to a question that cannot be infallibly solved analytically is not necessarily an error. In fact, I would argue that providing useful answers in situations like that is among the motivating use cases for AI. (Whether or not the answers current LLMs provide in these cases are useful is another question, but you miss 100% of the shots you don’t take.)

Fripplebubby 3y ago

Yes, I think you're right. I think one way to phrase the authors' argument is: * There is a class of problems which are harder than polynomial time complexity to solve, but are not np-complete * LLMs will generate an "answer" in formal language to this class of problems posed to it * LLMs can at most solve problems with polynomial time complexity due to their fundamental design and principles * Therefore, LLMs cannot solve > polynomial problems and not np-complete problems either All of which I buy completely. But I think what people are more interested in is, why is it that the LLM gives an answer when we can prove that it cannot answer this problem correctly? And perhaps that is more related to the commonsense notion of hallucination than I first gave it credit for. Maybe the reason that an LLM gives a formal language answer is the same reason it gives a hallucinatory answer in natural language. But I don't think the paper sheds light on that question

dragonwriter 3y ago
> why is it that the LLM gives an answer when we can prove that it cannot answer this problem correctly? Brcause LLMs are not “problem solving machines” they are text completion models, so (when trained for q-and-a response) their function is to produce text output which forms a plausible seeming response to the question posed, not to execute an algorithm which solves the logical problem it communicatss. Asking “why do LLMs do exactly what they are designed to do, even when they cannot do the thing that that behavior implies to a human would have been done to produce it” just reveals a poor understanding of what an LLM is. (Also, the fact that they structurally can't solve a class of problems does not mean that they can't produce correct answers, it means they can't infallibly produce correct answers; the absence of a polynomial time solution does not rule out an arbitrarily good polynomial time approximation algorithm, though its unlikely than an LLM is doing that, either.)
- someplaceguy 3y ago
  > their function is to produce text output which forms a plausible seeming response to the question posed Answering "I don't know" or "I can't answer that" is a perfectly plausible response to a difficult logical problem/question. And it would not be a hallucination.
  - dragonwriter 3y ago
    > Answering "I don't know" or "I can't answer that" is a perfectly plausible response to a difficult logical problem/question. Sure, and you can train LLMs to produce answers like that more often, but then users will say your model is lazy and doesn't even try, whereas if you train it to be more likely to produce something that looks like a solution more often, people will think “wow, the AI solved this problem I couldn't solve”. And that’s why LLMs behave the way they do.
    - someplaceguy 3y ago
      > Sure, and you can train LLMs to produce answers like that more often, but then users will say your model is lazy and doesn't even try, whereas if you train it to be more likely to produce something that looks like a solution more often, people will think “wow, the AI solved this problem I couldn't solve”. Are you saying that LLMs can't learn to discriminate between which questions they should answer "I don't know" vs which questions they should try to provide an accurate answer? Sure, there will be an error rate, but surely you can train an LLM to minimize it?
      - dragonwriter 3y ago
        > Are you saying that LLMs can't learn to discriminate between which questions they should answer "I don't know" vs which questions they should try to provide an accurate answer? No, I am saying that they are specific trained to do that, and that the results seen in practice on common real-world LLMs reflect the bias of the specific training they are given for providing concrete answers. > Sure, there will be an error rate, but surely you can train an LLM to minimize it? Giving some answer to a question that cannot be infallibly solved analytically is not necessarily an error. In fact, I would argue that providing useful answers in situations like that is among the motivating use cases for AI. (Whether or not the answers current LLMs provide in these cases are useful is another question, but you miss 100% of the shots you don’t take.)