11 ms·

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 thin

• foobarian 3y ago
  Humans have some amount of ability to recognize they hit a wall and adjust accordingly. On the other hand this (completeness theorems, Kolmogorov complexity, complexity theory) was only arrived at what, in the 20th century?
  • digitalsushi 3y ago
    'Adjust accordingly' includes giving up and delivering something similar to what I asked, but not what I asked; is this the point at which the circle is complete and AI has fully replaced my dev team?
    • foobarian 3y ago
      Well in the example of an NP complete problem, a human might realize they are having trouble coming up with an optimal solution and start analyzing complexity. And once they have a proof might advise you accordingly and perhaps suggest a good enough heuristic.
      • lazide 3y ago
        Have you managed dev teams before? It's really nice when they do that, but that is far from the common case.
      • flextheruler 3y ago
        Is the commenter above you implying humans hallucinate to the level of LLMs? Maybe hungover freshman working on a tight deadline without having read the book do, but not professionals. Even a mediocre employees will often realize they’re stuck, seek assistance, and then learn something from the assistance instead of making stuff up.
        • groestl 3y ago
          Depending on the country / culture / job description, "making stuff up" is sometimes a viable option for "adjust accordingly", on all levels of expertise.
        • pixl97 3y ago
          People commonly realize when they are stuck... But note, the LLM isn't stuck, it keeps producing (total bullshit) material, and this same problem happens with humans all the time when they go off on the wrong tangent and some supervisory function (such as the manager of a business) has to step in and ask wtf they are up to.
        • mr_toad 3y ago
          > Even a mediocre employees will often realize they’re stuck, seek assistance, and then learn something from the assistance instead of making stuff up. Only if they’re aware of their mediocrity. It’s the ones who aren’t, who bumble on regardless who are dangerous - just like AI.
    • skywhopper 3y ago
      One thing a human might do that I’ve never seen an LLM do is ask followup and clarifying questions to determine what is actually being requested.
      • ericb 3y ago
        What makes this fascinating to me is, these LLM's were trained on an internet filled with tons of examples of humans asking clarifying questions. Why doesn't the LLM do this? Why is the "next, most-likely token" never a request for clarification?
      • bongodongobob 3y ago
        GPT4 absolutely asks for clarification all the time.
    • steveBK123 3y ago
      Everyone assumes the AI is going to replace their employees but not replace them.. fascinating.
      • Jensson 3y ago
        Uber proves we can replace Taxi management with simple algorithms, that was apparently much easier than replacing the drivers. I hope these bigger models can replace management in more industries, I'd love to have an AI as a manager.
        • steveBK123 3y ago
          Yeah on the one hand people think AI management id dystopian (probably lol), on the other hand probably fewer than 50% of ICs promoted to management are good at it. North of 25% are genuinely bad at it. We've all worked for several of these. Many of us have tried our hand at management and then moved back to senior IC tracks. Etc.
• deleted 3y ago
  [deleted]
• p1esk 3y ago
  The only way to reduce hallucinations in both humans and LLMs is to increase their general intelligence and their knowledge of the world.
  • FpUser 3y ago
    You post amounts to: in order to be smarter I need to increase my smartness. Great insight.
    • lazide 3y ago
      I think it's more subtly misleading - to be smarter, I need more knowledge. But knowledge != smart, knowledge == informed, or educated. And the problem is more - how can an LLM tell us it doesn't know something instead of just making up good sounding, but completely delusional answers. Which arguably isn't about being smart, and is only tangentially about less or more (external) knowledge really. It's about self-knowledge. Going down the first path is about knowing everything (in the form of facts, usually). Which hey, maybe? Going down the second path is about knowing oneself. Which hey, maybe? They are not the same.
      • p1esk 3y ago
        Hallucinations are an interesting problem - in both humans and statistical models. If we asked an average person 500 years ago how the universe works, they would have confidently told you the earth is flat and it rests on a giant turtle (or something like that). And that there are very specific creatures - angels and demons who meddle in human affairs. And a whole a lot more which has no grounding in reality. How did we manage to reduce that type of hallucination?
        • ottaborra 3y ago
          by taking steps to verify everything that was said
        • Anotheroneagain 3y ago
          The expression "Urbi et orbi" goes back longer than that. It's a modern myth that they didn't know the world was a sphere.
• someplaceguy 3y ago
  > 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.)
• fauigerzigerk 3y ago
  Does the paper distinguish between hallucination and approximation? If LLMs could be trained to approximate NP-complete functions rather than making stuff up, that would be good enough in many contexts. I guess it's what humans would do.
  • thargor90 3y ago
    You cannot approximate NP-complete functions. If you could approximate them with a practically useful limited error and at most P effort you would have solved P=NP. (disclaimer my computer science classes have been a long time ago)
    • kalkin 3y ago
      This isn't correct. What you may be remembering is that some (not all) NP complete problems have limits on how accurately they can be approximated (unless P = NP). But approximation algorithms for NP complete problems form a whole subfield of CS.
      • moyix 3y ago
        The theorem that proves this is the PCP Theorem, in case anyone wants to read more about it: https://en.wikipedia.org/wiki/PCP_theorem#PCP_and_hardness_of_approximation https://en.wikipedia.org/wiki/PCP_theorem#PCP_and_hardness_o...
    • fauigerzigerk 3y ago
      Perhaps I'm not using the vocabulary correctly here. What I mean is, if you ask a human to solve a travelling salesman problem and they find it too hard to solve exactly, they will still be able to come up with a better than average solution. This is what I called approximation (but maybe this is incorrect?). Hallucination would be to choose a random solution and claim that it's the optimum.
      • alwa 3y ago
        I may be misunderstanding the way LLM practitioners use the word “hallucination,” but I understood it to describe it as something different from the kind of “random” nonsense-word failures that happen, for example, when the temperature is too high [0]. Rather, I thought hallucination, in your example, might be something closer to a grizzled old salesman-map-draftsman’s folk wisdom that sounds like a plausibly optimal mapping strategy to a boss oblivious to the mathematical irreducibility of the problem. Imagining a “fact” that sounds plausible and is rhetorically useful, but that’s never been true and nobody ever said was true. It’ll still be, like your human in the example, better than average (if “average” means averaged across the universe of all possible answers), and maybe even useful enough to convince the people reading the output, but it will be nonetheless false. [0] e.g. https://news.ycombinator.com/item?id=39450669 https://news.ycombinator.com/item?id=39450669
• kenjackson 3y ago
  Last I’d heard it was still open if P != NP. And most questions I’ve seen hallucinations on are not NP-Complete.
• Animats 3y ago
  Yes. It looks like they introduce infinities and then run into the halting problem for infinities. That may not be helpful. 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.
  • Fripplebubby 3y ago
    Well put. Overall this paper feels very Gödel Incompleteness for LLMs which is _interesting_ and perhaps even valuable to somebody, but because it attaches itself to this hot query 'hallucination', I think some people are finding themselves searching this paper for information it does not contain.
• samatman 3y ago
  Hallucination is a misnomer in LLMs and it depresses me that it has solidified as terminology. When humans do this, we call it confabulation. This is a psychiatric symptom where the sufferer can't tell that they're lying, but fills in the gaps in their knowledge with bullshit which they make up on the spot. Hallucination is an entirely different symptom. And no, confabulation isn't a normal thing which humans do, and I don't see how that fact could have anything to do with P != NP. A normal person is aware of the limits of their knowledge, for whatever reason, LLMs are not.
  • navane 3y ago
    When you talk to your mom and you remember something happening one way, and she remembers it another way, but you both insist you remember it correctly, one of you is doing what the LLM is doing (filling up gaps of knowledge with bull shit). And even when later you talk about this on meta level, no one calls this confabulation because no one uses that word. Also this is not a psychiatric syndrome, it's just people making shit up, inadvertently, to tell a coherent story without holes. It very much sounds you did the same. Everyone does this all the time.
    • jiggawatts 3y ago
      Just ask any criminal attorney or police detective. Normal people can’t get their facts straight even if they all witnessed something memorable first-hand just hours ago.
    • justinclift 3y ago
      > one of you is doing what the LLM is doing Possibly both. ;)
  • pixl97 3y ago
    >confabulation isn't a normal thing which humans do > A normal person is aware of the limits of their knowledge, for whatever reason, LLMs are not. Eh, both of these things are far more complicated. People perform minor confabulations all the time. Now, there is a medical term for confabulation to about a more serious medical condition that involves high rates of this occurring coupled with dementia, and would be the less common form. We know with things like eye witness testimony people turn into confabulatory bullshit spewing devices very quickly, though likely due to different mechanisms like recency bias and over writing memories by thinking about them. Coupled with that, people are very apt to lie about things they do know and can do for a multitude of reasons and attempting to teach an LLM to say "I don't know" when it doesn't know something, versus it just lying to you and saying it doesn't know will be problematic. Just see ChatGPT getting lazy in some of its releases for backfire effects like this.
• bitwize 3y ago
  > but rather are hallucinatory for some other interesting reason. In improv theater, the actor's job is to come up with plausible interactions. They are free to make shit up as they go along, hence improv, but they have to keep their inventions plausible to what had just happened before. So in improv if someone asks you "What is an eggplant?" it is perfectly okay to say "An eggplant is what you get when you genetically splice together an egg and a cucumber" or similar. It's nonsense but it's nonsense that follows nicely from what just came before. Large language models, especially interactive ones, are a kind of improv theater by machine: the machine outputs something statistically plausible to what had just come before; what "statistically plausible" means is based on the data about human conversations that came from the internet. But if there are gaps in the data, or the data lacks a specific answer that seems to statistically dominate, it seems like giving a definitive answer is more plausible in the language model than saying "I don't know", so the machine selects definitive, but wrong, answers.