3 ms·

LLMs are nothing like Markov chains I've come across or worked with. I've never used a markov chain trained with anywhere near the number of states you'd need.

by IanCal 2y ago

LLMs are nothing like Markov chains I've come across or worked with. I've never used a markov chain trained with anywhere near the number of states you'd need. This feels like saying "it's just if statements". So yeah, but also thats a terrible mental model for how to use them.

jampekka 2y ago
Any system with memoryless finite transition rule (the Markov property) and full observability of the state is a Markov chain. In language models the "traditional" Markov chain model is the very simple small-context table lookup, but in many other fields they can be a lot more complicated. E.g. Markov Chain Monte Carlo and many statistical mechanics applications. It's mathematically well understood and very poweful abstraction which is lost if they're thought only as the simple toy language model.
- CamperBob2 2y ago
  What's the Markovian interpretation of the notion of embeddings in a high-dimensional space? Or of attention? The term is being tortured beyond endurance by being forced to describe what LLMs do.
  - jampekka 2y ago
    The theory of Markov chains (or Markov processes in general) has nothing to say about what happens inside the function that maps observations to predictions of the next state, as long as the function is stateless/memoryless. It is a different level of analysis than neural network architecture and covers a very wide types of models. The Markov chain structure of a model allows for some kinds of understanding of behavior of the models fulfilling its assumptions, e.g. finite range of dependencies, existence of a stationary distribution and crucially for transformer-type architectures that they can be trained in a purely parallel manner.
    - CamperBob2 2y ago
      The problem I have is that anything deterministic can be described as Markovian. If an algorithm employing 8 billion parameters addressed by a context that is itself cross-linked with a key-value store qualifies as "memoryless" enough to be a Markov model, does the term have any meaning at all? You could argue that it's memoryless because the embeddings aren't modified on the fly based on the user's input, I suppose. My point is that describing a toy Markov text generator with the same terms that you apply to GPT3.5 is, even if technically accurate, no more meaningful than using the term "Turing machine" to describe a C-64 and a Cray.
      - Legend2440 2y ago
        It's memoryless because it's a pure function. All feedforward neural networks are memoryless. This is as opposed to an RNN, which has an internal state.
        ben_w 2y ago
        While this is absolutely correct when the RNN has ℝeal-valued internal state, in concrete implementations the internal state in an RNN has some number of bits and one can draw a Markov graph with a group of 2^n variants of states to represent all possible states of n bits in some part of the system. Likewise the context window of an LLM can be considered a state with some number of bits. It's just more explicit in an LLM's architecture vs. a RNN's runtime that the number of bits is finite.
      - Y_Y 2y ago
        > My point is that describing a toy Markov text generator with the same terms that you apply to GPT3.5 is, even if technically accurate, no more meaningful than using the term "Turing machine" to describe a C-64 and a Cray. What if we used the term "computer"?
        ben_w 2y ago
        > What if we used the term "computer"? And anthropomorphise the machines? ;) https://en.wikipedia.org/wiki/Computer_(occupation) https://en.wikipedia.org/wiki/Computer_(occupation)
  - Jensson 2y ago
    > The term is being tortured beyond endurance by being forced to describe what LLMs do. No it isn't, this is exactly the kind of process that Markov chains describe. They describe a stateless probability function that you chain over and over to produce a sequence of results, exactly like what an LLM does, they predict the next token based on precious tokens repeatedly to produce text. There is no bending of any concepts here, anyone who studied a higher level math probability course will instantly recognize LLMs as a markov chain. It is common for markov chains to have infinite number of states, like a real position, and then moving randomly from there. You can model particles in a gas like that.
    - CamperBob2 2y ago
      I'm not disagreeing that it's correct, I'm disagreeing that it's meaningful. Calling an LLM a "Markov model" reveals an agenda rather than an insight.
      - Jensson 2y ago
        > Calling an LLM a "Markov model" reveals an agenda rather than an insight. What agenda? Knowing that LLM's are markov chains helps me understand and makes me better at using them, since I know every word is just calculated probabilistically based on the previous N words, the fastest way to describe that is to say it is a Markov chain. This makes it hard for them to coordinate their early words with things that will happen later, all that from just knowing it is a Markov chain. I feel the knee jerk rejection of this statement is more of an agenda, why do you feel it is so wrong to say it is a Markov chain? Are you sure there is no agenda behind those feelings?
      - ben_w 2y ago
        The agenda may well be "pure mathematics". I don't think "Markov chain" is a useful description despite agreeing it's an accurate one, simply because I have a preference for applied maths over pure maths and a full transition table version would be obscenely large. In this, it's also technically accurate to say that a perceptron network with one hidden layer can approximate any function: technically yes, but not in any practical sense. But if you're working in the pure maths domain, knowing that it can in principle be one, means you can apply any tools that only work on Markov chains. Given what else I've seen mathematicians do, I won't be surprised if pure maths researchers can get useful results even though the transition matrix is literally too large to fit into our universe without collapsing it into a black hole — it would hardly be the first time I've even seen mathematicians talking about quantities that large.
wat10000 2y ago
It’s not a particularly useful mental model, but it does drive home a critical point some people have trouble with, namely that LLMs don’t learn when being used.
- ben_w 2y ago
  Current AIs don't learn like us. But the context length is around what a human goes through in a day so it can feel like it, and they can use tools such as databases to make direct record of "important" things, and fine-tuning on sessions is also already possible. I'm going to ignore "proper" continuous learning until that actually gets into the big-name models, because although there's plenty of "first 90%" tech demos, the Tesla FSD is also at that point and yet the cars today still come with steering wheels. Meanwhile, here's the research SOTA: https://github.com/Wang-ML-Lab/llm-continual-learning-survey https://github.com/Wang-ML-Lab/llm-continual-learning-survey Ironically, continuously updating a Markov chain is easy, given how small most of them are in practice. But a Markov chain large enough to act like an LLM would collapse into a black hole 7x10^32 times larger than the universe*, so that's kinda hard to update. * assuming the algebra was correct: http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000%5E20%29%5E2%29%2Aplank%20constant%2AGravitational%20constant%2Aln%282%29%2F%28pi%2A%28speed%20of%20light%5E3%29%29%29 http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000... Edit: I made at least two errors with that algebra, one of which was a typo; I now think it's 4.2x10^4750 universe diameters… …unless there's another error I missed: http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000%5E2048%29%2Aplank%20constant%2AGravitational%20constant%2Aln%282%29%2F%28pi%2A%28speed%20of%20light%5E3%29%29%29 http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000...
  - Jensson 2y ago
    > But a Markov chain large enough to act like an LLM would collapse into a black hole You mean a full state table Markov Chain? Markov chains doesn't need to have all states in a table, it just needs to be a function, a table is one implementation of a function but anything can do.
    - 2y ago

by IanCal 2y ago

jampekka 2y ago

Any system with memoryless finite transition rule (the Markov property) and full observability of the state is a Markov chain. In language models the "traditional" Markov chain model is the very simple small-context table lookup, but in many other fields they can be a lot more complicated. E.g. Markov Chain Monte Carlo and many statistical mechanics applications. It's mathematically well understood and very poweful abstraction which is lost if they're thought only as the simple toy language model.

CamperBob2 2y ago
What's the Markovian interpretation of the notion of embeddings in a high-dimensional space? Or of attention? The term is being tortured beyond endurance by being forced to describe what LLMs do.
- jampekka 2y ago
  The theory of Markov chains (or Markov processes in general) has nothing to say about what happens inside the function that maps observations to predictions of the next state, as long as the function is stateless/memoryless. It is a different level of analysis than neural network architecture and covers a very wide types of models. The Markov chain structure of a model allows for some kinds of understanding of behavior of the models fulfilling its assumptions, e.g. finite range of dependencies, existence of a stationary distribution and crucially for transformer-type architectures that they can be trained in a purely parallel manner.
  - CamperBob2 2y ago
    The problem I have is that anything deterministic can be described as Markovian. If an algorithm employing 8 billion parameters addressed by a context that is itself cross-linked with a key-value store qualifies as "memoryless" enough to be a Markov model, does the term have any meaning at all? You could argue that it's memoryless because the embeddings aren't modified on the fly based on the user's input, I suppose. My point is that describing a toy Markov text generator with the same terms that you apply to GPT3.5 is, even if technically accurate, no more meaningful than using the term "Turing machine" to describe a C-64 and a Cray.
    - Legend2440 2y ago
      It's memoryless because it's a pure function. All feedforward neural networks are memoryless. This is as opposed to an RNN, which has an internal state.
      - ben_w 2y ago
        While this is absolutely correct when the RNN has ℝeal-valued internal state, in concrete implementations the internal state in an RNN has some number of bits and one can draw a Markov graph with a group of 2^n variants of states to represent all possible states of n bits in some part of the system. Likewise the context window of an LLM can be considered a state with some number of bits. It's just more explicit in an LLM's architecture vs. a RNN's runtime that the number of bits is finite.
    - Y_Y 2y ago
      > My point is that describing a toy Markov text generator with the same terms that you apply to GPT3.5 is, even if technically accurate, no more meaningful than using the term "Turing machine" to describe a C-64 and a Cray. What if we used the term "computer"?
      - ben_w 2y ago
        > What if we used the term "computer"? And anthropomorphise the machines? ;) https://en.wikipedia.org/wiki/Computer_(occupation) https://en.wikipedia.org/wiki/Computer_(occupation)
- Jensson 2y ago
  > The term is being tortured beyond endurance by being forced to describe what LLMs do. No it isn't, this is exactly the kind of process that Markov chains describe. They describe a stateless probability function that you chain over and over to produce a sequence of results, exactly like what an LLM does, they predict the next token based on precious tokens repeatedly to produce text. There is no bending of any concepts here, anyone who studied a higher level math probability course will instantly recognize LLMs as a markov chain. It is common for markov chains to have infinite number of states, like a real position, and then moving randomly from there. You can model particles in a gas like that.
  - CamperBob2 2y ago
    I'm not disagreeing that it's correct, I'm disagreeing that it's meaningful. Calling an LLM a "Markov model" reveals an agenda rather than an insight.
    - Jensson 2y ago
      > Calling an LLM a "Markov model" reveals an agenda rather than an insight. What agenda? Knowing that LLM's are markov chains helps me understand and makes me better at using them, since I know every word is just calculated probabilistically based on the previous N words, the fastest way to describe that is to say it is a Markov chain. This makes it hard for them to coordinate their early words with things that will happen later, all that from just knowing it is a Markov chain. I feel the knee jerk rejection of this statement is more of an agenda, why do you feel it is so wrong to say it is a Markov chain? Are you sure there is no agenda behind those feelings?
    - ben_w 2y ago
      The agenda may well be "pure mathematics". I don't think "Markov chain" is a useful description despite agreeing it's an accurate one, simply because I have a preference for applied maths over pure maths and a full transition table version would be obscenely large. In this, it's also technically accurate to say that a perceptron network with one hidden layer can approximate any function: technically yes, but not in any practical sense. But if you're working in the pure maths domain, knowing that it can in principle be one, means you can apply any tools that only work on Markov chains. Given what else I've seen mathematicians do, I won't be surprised if pure maths researchers can get useful results even though the transition matrix is literally too large to fit into our universe without collapsing it into a black hole — it would hardly be the first time I've even seen mathematicians talking about quantities that large.

wat10000 2y ago

It’s not a particularly useful mental model, but it does drive home a critical point some people have trouble with, namely that LLMs don’t learn when being used.

ben_w 2y ago
Current AIs don't learn like us. But the context length is around what a human goes through in a day so it can feel like it, and they can use tools such as databases to make direct record of "important" things, and fine-tuning on sessions is also already possible. I'm going to ignore "proper" continuous learning until that actually gets into the big-name models, because although there's plenty of "first 90%" tech demos, the Tesla FSD is also at that point and yet the cars today still come with steering wheels. Meanwhile, here's the research SOTA: https://github.com/Wang-ML-Lab/llm-continual-learning-survey https://github.com/Wang-ML-Lab/llm-continual-learning-survey Ironically, continuously updating a Markov chain is easy, given how small most of them are in practice. But a Markov chain large enough to act like an LLM would collapse into a black hole 7x10^32 times larger than the universe*, so that's kinda hard to update. * assuming the algebra was correct: http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000%5E20%29%5E2%29%2Aplank%20constant%2AGravitational%20constant%2Aln%282%29%2F%28pi%2A%28speed%20of%20light%5E3%29%29%29 http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000... Edit: I made at least two errors with that algebra, one of which was a typo; I now think it's 4.2x10^4750 universe diameters… …unless there's another error I missed: http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000%5E2048%29%2Aplank%20constant%2AGravitational%20constant%2Aln%282%29%2F%28pi%2A%28speed%20of%20light%5E3%29%29%29 http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000...
- Jensson 2y ago
  > But a Markov chain large enough to act like an LLM would collapse into a black hole You mean a full state table Markov Chain? Markov chains doesn't need to have all states in a table, it just needs to be a function, a table is one implementation of a function but anything can do.
  - 2y ago