Hacker News Reader

Hacker News

Comment by marvel_boy | Hacker News Reader

Parent Full thread

marvel_boy

Written 53 years ago, if only Shannon experimented predicting next word instead of next letter....

View on HN

Wasn't it 73 years ago?

Yes, indeed. Too late to edit.

It'd still be a Markov model so much more than generating regular grammars is out of the question.

Either I'm misunderstanding you, or you're misunderstanding the GP. The GP is getting at large language models being equivalent to very high order Markov models combined with calculating argmax over all possible outputs.

Huh, I suppose we're both right. Large language models are markov models since their transition probabilities are completely determined by the input. Consequently they cannot generate and recognize matching brackets correctly.

In practice however the state space is so humongously large that this barely comes up in any reasonable example.

"Consequently they cannot generate and recognize matching brackets correctly."

Can you expand on this? Not quite following.

This is a bit of a technicality, so forgive me for introducing some technical terms first.

I'm not sure how much you know about regular grammars, but basically they're the kind of thing that a regular expression can match. Now regular expressions can do a lot but they have their limitations, in particular they cannot distinguish a sequence of matched brackets '((())())' form one of unmatched brackets '(()(', or at least not with 100% accuracy.

It turns out that regular expressions are precisely the languages that can be recognized by finite state machines. Which is kind of equivalent to the possible outputs of a markov model.

Since large language models only have a finite number of states they must have the same limitations, which means it is fundamentally impossible to make them only generate balanced brackets. They get away with it by having a ridiculous number of states, so they might not be able to deal with arbitrarily deep nesting, but they can still get far enough that you won't generally notice.

So I can go on to ChatGPT and expect it will never be able to close brackets for me?

It think the OP is getting at, a model can never be 100% accurate at this. Instead, the limit approaches 100% as the language model grows, but it never actually gets there. There will always be aliasing going on.

I think an analogy would be like saying that you can't represent pi as a floating point number. Precision can be increased by adding more bits, but there's a fundamental limitation because of the underlying storage mechanism.

I see. In any case, I don't think anything stops them from augmenting ChatGPT(-as-seen-by-the-user) so that it incorporates modules that aren't mere language models and thus allow richer behavior, as I suspected they were already doing:

https://news.ycombinator.com/item?id=35472089

No, it means that there is some input for which it will fail to properly balance brackets. The parameter count would have to be astronomical for this to fall outside the token window size.

ChatGPT Example:

> Add the correct number of closing parentheses to this string: (((((((((((((((((((((((((((((((

>> ))))))))))))))))))))))))))))

>> The correct number of closing parentheses to balance the opening parentheses is 21.

which is not correct

You could probably get it to generate code that does the correct operation, though, right? (Returns the correct number of parents.) It's kind of funny if that's the case.

Sipser[1] provides the clearest detailed description I've seen. You don't have to read anywhere near the whole thing. He covers the regular languages and (non)deterministic finite automata in the first few chapters.

[1] https://www.goodreads.com/en/book/show/400716

"LLMs are Markov Models"... There's a reason we don't use Markov models anymore though (for language modeling - still used heavily in RL). The density of information and composability you get from MHA makes the problem far more tractable.

Transformers can't match brackets beyond some fixed depth, but RNNs and LSTMs can match unbounded brackets.

Depending on your starting assumptions, Transformers, RNNs and LSTMS can either be

a) Turing-complete, in which case they can all match unbounded brackets, or

b) they are all not Turing-complete, LSTMs might be able to match unbounded brackets (if there is only one type of bracket), while RNNs and Transformers can't.

For Transformers you would need an infinite number of self-attention layers.

For RNN/LSTM all you need is enough neurons to implement a counter.

> For RNN/LSTM all you need is enough neurons to implement a counter.

For an arbitrary depth, that would need to be an infinitely sized counter. (I presume you know this, but this is why a push-down automaton can always close parens, but a finite state machine can only close parens up to a finite nesting depth.)

So, "all you need is enough neurons" for an RNN/LSTM is equivalent to just saying you just need to scale the LMM state large enough to handle your use case.

In reality, ignoring rdrand (and other quantum noise instructions) and ignoring using I/O for external storage, all of our computers are (gigantic) finite state machines. Technically, our programming languages might be Turing complete, but our near-infinite memory implementations are actually finite state machines, not Turing-complete. Though, you only run into the difference when you fill the whole machine's memory.

So, I think a more important question is how efficiently different finite state machines make use of their state sizes for a given problem. How many neurons would it take to match parens to a maximum depth of 2^40 for an RNN/LSTM vs. an LLM?

An RNN with infinite-precision rational weights can implement a counter with a bounded number of neurons. With finite precision the number of neurons scales linearly in your desired depth of matching brackets: https://arxiv.org/pdf/2010.07515.pdf

For a Transformer you need to add a new layer of self-attention to increase bracket matching depth by 1. https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00306...

Transformers are formally a lot weaker than RNNs/LSTMs.

Reply on news.ycombinator.com