5 ms·

Though it seems like there is some sensitivity around the comparison of LLMs to Markov chains, and certainly an LLM is not generated in the same way, it is pret

by lsy 3y ago

Though it seems like there is some sensitivity around the comparison of LLMs to Markov chains, and certainly an LLM is not generated in the same way, it is pretty accurate that an LLM could be represented by a sufficiently (ie very) complex Markov chain. The states of the chain would not be the tokens themselves, as in this example, but the total context window vector of N input tokens, which would fan out to states consisting of the new context N[1:] + A, where A is any of the tokens sampled from the resulting probability distribution, and the transition probabilities are just drawn from that same distribution according to the temperature settings. You could even do some very hand-wavy math on how staggeringly complex the resulting Markov chain would get: BERT for example has a token vocabulary of 30,000 and a context window of 512 tokens. So the number of possible states would be 30,000^512, or ~1.9 x 10^2292, with each of those having a max fan out to 30,000 other states. So clearly the LLM is a more compact representation of the concept.

kromem 3y ago
It would be more accurate to say that a Markov chain is an example of a method that would perform relatively well at the same training task as a LLM. So too, might a human trying to predict the next tokens. But a human and a Markov chain are not the same underlying process to achieve next token prediction, and neither is the same underlying process as a LLM.
- Jensson 3y ago
  LLM are markov chains, a markov chain is a general concept and not just a text model technique. You must be thinking about the very simple markov chain models we had before where you just predicted the next word by looking up sentences with the same preceding words and picking a random of those words, that is also a markov chain just like LLM but a much simpler one, you are right LLMs aren't like that but they are still markov chains with the same kind of inputs and outputs as the old ones.
  - kromem 3y ago
    No, the self-attention for the transformer in GPT means it isn't a Markov Chain. A blog post of you want to read more: https://medium.com/@andrew_johnson_4/are-transformers-markov-processes-a-deeper-dive-into-the-underpinnings-of-deep-learning-401019a285d https://medium.com/@andrew_johnson_4/are-transformers-markov...
    - acjohnson55 3y ago
      Isn't it though, if you consider the entire context to be part of the state? It seems like his argument is based on an assumption of the Markov model only using the current word as its state.
      - kromem 3y ago
        It's not the only one stating this: https://safjan.com/understanding-differences-gpt-transformers-markov-models/ https://safjan.com/understanding-differences-gpt-transformer... If we're broadening the scope of a Markov chain to consider the entire system as the current state that's being used to determine the next step of operation, then isn't literally every computer program a Markov chain under that definition? You can't just include the memory of previous states which the current state is depending on as being part of the "current state" to fit the definition of a Markov chain without having broadened the scope to the point the definition becomes meaningless.
        acjohnson55 3y ago
        No, every computer program is not a Markov chain, because computer programs aren't random processes. Look up the concepts of "higher-order Markov chains" or "Markov chains with memory". Obviously, there are reasons that people don't directly implement LLMs as very high-order Markov chains. But it doesn't mean that the equivalence isn't mathematically or intuitively useful. I'm just a non expert, but as far as I can tell, if there's an upper bound to the lookback in the context window, I don't see how that transformer isn't strictly less powerful than a Markov chain of that order. It's just a computationally tractable way to closely approximate it. If the potential lookback distance is unbounded, then I think you could say that it's different from a finite-order Markov chain.

by lsy 3y ago

kromem 3y ago

It would be more accurate to say that a Markov chain is an example of a method that would perform relatively well at the same training task as a LLM. So too, might a human trying to predict the next tokens. But a human and a Markov chain are not the same underlying process to achieve next token prediction, and neither is the same underlying process as a LLM.

Jensson 3y ago
LLM are markov chains, a markov chain is a general concept and not just a text model technique. You must be thinking about the very simple markov chain models we had before where you just predicted the next word by looking up sentences with the same preceding words and picking a random of those words, that is also a markov chain just like LLM but a much simpler one, you are right LLMs aren't like that but they are still markov chains with the same kind of inputs and outputs as the old ones.
- kromem 3y ago
  No, the self-attention for the transformer in GPT means it isn't a Markov Chain. A blog post of you want to read more: https://medium.com/@andrew_johnson_4/are-transformers-markov-processes-a-deeper-dive-into-the-underpinnings-of-deep-learning-401019a285d https://medium.com/@andrew_johnson_4/are-transformers-markov...
  - acjohnson55 3y ago
    Isn't it though, if you consider the entire context to be part of the state? It seems like his argument is based on an assumption of the Markov model only using the current word as its state.
    - kromem 3y ago
      It's not the only one stating this: https://safjan.com/understanding-differences-gpt-transformers-markov-models/ https://safjan.com/understanding-differences-gpt-transformer... If we're broadening the scope of a Markov chain to consider the entire system as the current state that's being used to determine the next step of operation, then isn't literally every computer program a Markov chain under that definition? You can't just include the memory of previous states which the current state is depending on as being part of the "current state" to fit the definition of a Markov chain without having broadened the scope to the point the definition becomes meaningless.
      - acjohnson55 3y ago
        No, every computer program is not a Markov chain, because computer programs aren't random processes. Look up the concepts of "higher-order Markov chains" or "Markov chains with memory". Obviously, there are reasons that people don't directly implement LLMs as very high-order Markov chains. But it doesn't mean that the equivalence isn't mathematically or intuitively useful. I'm just a non expert, but as far as I can tell, if there's an upper bound to the lookback in the context window, I don't see how that transformer isn't strictly less powerful than a Markov chain of that order. It's just a computationally tractable way to closely approximate it. If the potential lookback distance is unbounded, then I think you could say that it's different from a finite-order Markov chain.