3 ms·

Any system with memoryless finite transition rule (the Markov property) and full observability of the state is a Markov chain. In language models the "tradition

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)
  - 3np 2y ago
    @CamperBob2 > The problem I have is that anything deterministic can be described as Markovian. Markov processes aren't even necessarily deterministic. See Hidden Markov models (https://en.wikipedia.org/wiki/Hidden_Markov_model https://en.wikipedia.org/wiki/Hidden_Markov_model) and POMDPs (https://en.wikipedia.org/wiki/Partially_observable_Markov_decision_process https://en.wikipedia.org/wiki/Partially_observable_Markov_de...).
- 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.

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)
- 3np 2y ago
  @CamperBob2 > The problem I have is that anything deterministic can be described as Markovian. Markov processes aren't even necessarily deterministic. See Hidden Markov models (https://en.wikipedia.org/wiki/Hidden_Markov_model https://en.wikipedia.org/wiki/Hidden_Markov_model) and POMDPs (https://en.wikipedia.org/wiki/Partially_observable_Markov_decision_process https://en.wikipedia.org/wiki/Partially_observable_Markov_de...).
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.