Spoiler: You're never going to get rid of hallucinations in the autoregressive, next token prediction paradigm (aka LeCun's Law).
The issue here is people trying to use language models as deterministic problem solvers, rather than for what they actually excel at (semi-creative text generation).
Is LeCun's Law even a thing? Searching up for it doesn't yield many results, except for a HN comment where it has a different definition. I guess it could be from some obscure paper, but with how poorly it's documented it seems weird to bring it up in this context.
* Probability e that any produced token takes us outside the set of correct answers
* Probability that answer of length n is correct
* P(correct) = (1-e)^n
* This diverges exponentially
* It's not fixable (without a major redesign)
Doesn't that argument make the fundamentally incorrect assumption that the space of produced output sequence has pockets where all output sequence with a certain prefix are incorrect?
Design your output space in such way that every prefix has a correct completion and this simplistic argument no longer applies. Humans do this in practice by saying "hold on, I was wrong, here's what's right".
Of course, there's still a question of whether you can get the probability mass of correct outputs large enough.
Wouldn't this apply to all prediction machines that make errors.
Humans make bad predictions all the time but we still seem to manage to do some cool stuff here and there.
part of an agents architecture will be for it to minimize e and then ground the prediction loop against a reality check.
making LLMs bigger gets you a lower e with scale of data and compute but you will still need it to check against reality. test time compute also will play a roll as it can run through multiple scenarios and "search" for an answer.
The difference between LLMs and other kinds of predictive models, or humans, is that those kinds of systems do not produce their output one token at a time, but all in one go, so their error basically stays constant. LeCun's argument is that LLM error increases with every cycle of appending a token to the last cycle's output. That's very specific to LLMs (or, well, to LLM-based chatbots to be more precise).
>> part of an agents architecture will be for it to minimize e and then ground the prediction loop against a reality check.
The problem is that web-scale LLMs can only realistically be trained to maximise the probability of the next token in a sequence, but not the factuality, correctness, truthfullness, etc of the entire sequence. That's because web-scale data is not annotated with such properties. So they can't do a "reality check" because they don't know what "reality" is, only what text looks like.
The paper above uses an "oracle" instead, meaning they have a labelled dataset of correct answers. They can only train their RL approach because they have this source of truth. This kind of approach just doesn't scale as well as predicting the next token. It's really a supervised learning approach hiding behind RL.
"The difference between LLMs and other kinds of predictive models, or humans, is that those kinds of systems do not produce their output one token at a time, but all in one go, so their error basically stays constant." -- This is a big, unproven assumption. Any non-autoregressive model can be trivially converted to an autoregressive model by: (i) generating a full output sequence, (ii) removing all tokens except the first one, (iii) generating a full-1 output sequence conditioned on the first token. This wraps the non-autoregressive model in an "MPC loop", thereby converting it to an autoregressive model where per-token error is no greater than that of the wrapped non-AR model. The explicit MPC planning behavior might reduce error per token compared to current naive applications of AR transformers, but the MPC-wrappped model is still an AR model, so the problem is not AR per se.
LeCun's argument has some decent points, eg, allocating compute per token based solely on location within the sequence (due to increasing cost of attention ops for later locations) is indeed silly. However, the points about AR being unavoidably flawed due to exponential divergence from the true manifold are wrong and lazy. They're not wrong because AR models don't diverge, they're wrong because this sort of divergence is also present in other models.
The loop itself is claimed to be the problem. It doesn't matter whether you use an AR or non-AR model. They both have a certain error probability that gets amplified in each iteration.
The per token error of the non-AR model wrapped with MPC is no higher than the per token error of the non-AR model without MPC. Likelihood of the entire sequence being off the true data manifold is just one minus the product of the per token errors, whether or not you're running with the MPC loop. Ie, wrapping the non-AR model in an MPC loop and thereby converting it to an AR model (with a built-in planning mechanism) doesn't increase its probability of going off track.
Per token error compounding over sequence length happens whether or not the model's autoregressive. The way in which per token errors correlate across a sequence might be more favorable wrt probability of producing bad sequences if you incorporate some explicit planning mechanism -- like the non-AR model wrapped in an MPC loop, but that's a more subtle argument than LeCun makes.
Yes. Also "other kinds of predictive models" in my comment refers to models other than generative language models, e.g. image classifiers or regression models etc. Those don't generate tokens, they output labels and the error of the labeling is constant (well, within error bounds). This was in response to OP's comment about "all prediction machines that make errors."
Could the argument be rescued by some additional assumptions?
I agree with, and have previously also stated, the point you make there about “any non-auto-regressive model can be converted into an equivalent auto-regressive model by […]”, but, if one imposes additional restrictions on e.g. computation time, or something like that, I think that construction no longer works.
Well, of course there are some additional assumptions which would rescue the argument, so I guess my real question is whether there’s some combination of extra assumptions which both rescue the argument, and actually result in it being interesting.
If one makes the assumptions that there is a positive common lower bound on the probability of each token being incorrect assuming each previous token is correct, and that if any token is incorrect, then the whole generated text is incorrect, then of course the argument goes through, though the assumption doesn’t necessarily seem very likely.
Then, if we apply the construction, you mentioned to a text generation process with a low enough probability of error, then by the contrapositive, there cannot be an especially high common lower bound on the probability of error per token.
[“edit” prior to posting: I notice that at this point I started using symbols as if I was going to start doing actual algebraic manipulations, but did not actually do any algebraic manipulations which would justify the use of said symbols. I think what I wrote below would be clearer if I had just used words. Unfortunately I don’t want to take the time to rewrite it. I apologize for introducing formalisms without having a good reason to do so.]
If we have the assumption that there is a procedure with error rate < epsilon(x) for generating an entire text response of length l(x), and which can be computed within time t(x), the construction gives an autoregressive method which has error rate less than epsilon(x) for the entire text, and doesn’t have an error rate higher than epsilon’(x) for all of the tokens, and runs in time t’(x) per token (err… I guess it should actually vary between the tokens in the generated string… depends on details I guess), where epsilon’(x) and t’(x) can be computed based on epsilon(x) and t(x) and based on how the construction works,
and epsilon’(x) will be much smaller than epsilon(x), while t’(x) l(x) >> t(x) (at least, assuming l(x) is somewhat large).
So, that particular construction does not preclude the possibility that there is no algorithm that works auto-regressively and which both has an error rate(for overall generated text) as low as [the error rate for some non-auto-regressive model that runs quickly enough], and which runs quickly enough .
If there are cryptographically secure families of hashing functions (in the sense of, asymptotically in the size of the hash length, while the hash can be computed in polynomial time, finding preimages or collisions cannot be done in polynomial time) it seems that there should probably be functions from strings to strings which can be computed in time bounded above by some polynomial, but which can’t be computed autoregressively in time bounded above by a polynomial of the same degree.
(So like, maybe it can be computed in time 5n^4 when not autoregressive, but needs at least 2n^5 time to do auto regressively)
(I’m imagining something like, “compute a string of the form ‘hash(y), y’ where y is the result of some computation done on the input which takes a polynomial amount of time to compute from the input. So, the easiest way to compute this would be to compute y and the compute hash(y). So, to do this auto-regressively, it would need to compute y again for each token in the hash.)
Of course, a single factor of n might not be that compelling, and appealing to strong hashing functions is probably trying to kill a fly with a sledgehammer(probably there are arguments that work as well without assuming this), but it’s what came to mind.
Perhaps one could do something like this to show that for some problems, any auto-regressive solution that has certain runtime bounds, will have some positive lower bound on the error rate per token?
I think it would be hard to make a solid argument that AR or non-AR is strictly better wrt full sequence error rates, whether or not we place constraints on compute, memory, etc. I'd guess that there's some intrinsic form of complexity inherent to any particular distribution of sequences which requires spending at least some amount of compute to achieve sequence generation error less than some epsilon. I'd also guess that AR and non-AR models could both achieve this bound in principle, though maybe it's practically harder with one or the other. It would be interesting to formally characterize this sort of complexity, but that's above my analytical pay grade.
The hash function example is interesting. I think the model could compute y prior to outputting any tokens and then output the `hash(y), y' sequence deterministically. In architectures like transformers, all the compute in earlier steps can be reused in later steps via attention, so it wouldn't be necessary to recompute y at each step as long as the model commits to a given y up front before starting to generate hash(y).
Ah, yeah, I guess that probably is true of transformers in practice. I was thinking about something which strictly takes in a sequence of tokens and outputs a (possibly 1-hot) probability distribution over all possible next tokens. Such a thing running autoregressively would have to recompute y each time. But, if intermediate computations are cached, as with transformers in practice, then this isn’t necessary.
No. Many prediction machines can give you a confidence value on the full outcome. By the nature of tokenization and the casual inference (you build a token one at a time, and they're not really semantically connected except in the kv cache lookups, which are generally hidden to the user), the confidence values are thrown out in practice and even a weak confidence value would be hard to retrieve.
I don't think it's impossible to obtain content with confidence assessments with the transformer architecture but maybe not in the way it's done now (like maybe another mayer on top).
Is this similar to the effect that I have seen when you have two different LLMs talking to each other, they tend to descend into nonsense ? A single error in one of the LLM's output and that then pushes the other LLM out of distribution.
I kind of oscillatory effect when the train of tokens move further and further out of the distribution of correct tokens.
This is equivalent to the problem of maximum entropy Markov models and their application to sequence output.
After some point you’re conditioning your next decision on tokens that are severely out of the learned path and you don’t even see it’s that bad.
Usually this was fixed with cost sensitive learning or increased sampling of weird distributions during learning and then making the model learn to correct the mistake.
Another approach was to have an inference algorithm that maximize the output probability, but these algorithms are expensive (viterbi and other dynamic programming methods).
Feature modeling in NNs somewhat allowed us to ignore these issues and get good performance but they will show up again.
> Is this similar to the effect that I have seen when you have two different LLMs talking to each other, they tend to descend into nonsense ?
Is that really true? I'd expect that with high temperature values, but otherwise I don't see why this would happen, and I've experimented with pitting same models against each other and also different models against different models, but haven't come across that particular problem.
That the chain-of-thought diverges from accepted truth as an incorrect token pushes it into a line of thinking that is not true. The use of RL is there to train the LLM to implement strategies to bring it back from this. In effect, two LLMs would be the same and would slow diverge into nonsense. Maybe it is something that is not so much of a problem anymore.
Yann LeCun talks about how the correct way to fix this is to use an internal consistent model of the truth; then the chain-of-thought exists as a loop within that consistent model meaning it cannot diverge. The language is a decoded output of this internal model resolution. He speaks about this here: https://www.youtube.com/watch?v=N09C6oUQX5M
It's quite fitting that the topic of this thread is self-correction. Self-correction is a trivial existence proof that refutes what LeCun is saying, because all the LLM has to say is "I made a mistake, let me start again".
Yes the main flaw of this reasoning is supposing that e does not depend on previous output. I think this was a good approximation to characterize vanilla LLMs, but the kind of RL in this paper is done with the explicit goal of making e depending on prior output (and specifically to lower it given a long enough chain of thought).
P(correct) converges to zero, so you get almost certainly incorrect, at an exponential rate. The original choice of terms is not the most rigorous, but the reasoning is sound (under the assumption that e is a constant).
Ah yes I didn't pay attention that it was the probability of being correct I misread it as the probability of being incorrect since the claim was that it diverged.
Simplistic, since it assumes probabilities are uncorrelated, when they clearly aren't. Also, there are many ways of writing the correct solution to a problem (you do not need to replicated an exact sequence of tokens).
“Label bias” or “observation bias” a phenomenon where going outside of the learned path lives little room for error correction. Lecun talks about the lack of joint learning in LLMs.
Does anyone here know, has anyone tried something like feeding the perplexity of previous tokens back into the model, so that it has a way of knowing when it's going off the rails? Maybe it could be trained to start responding less confidently in those cases, reducing its desire to hallucinate.
One way I explain it to people: Imagine a corporation that only has a PR department. Extremely good at generating press releases and answering reporter questions. But without the rest of the company, the output text isn't constrained by anything meaningful.
In an alternate universe, one where people understood this, people would be using LLMs for nothing serious, but a whole lot of fun little art projects.
If you're talking about label bias then you don't need to solve label bias to 'solve' hallucinations when the model has already learnt internally when it's bullshitting or going off the rails.
The issue here is people trying to use language models as deterministic problem solvers, rather than for what they actually excel at (semi-creative text generation).