5 ms·

> This paper states a completely obvious tautology which is that if you limit the context length, a LLM has a finite state size! It has to be stated, since so

> This paper states a completely obvious tautology which is that if you limit the context length, a LLM has a finite state size! It has to be stated, since so many even here on HN believes that LLM aren't markov chains since they misunderstand basics like this.

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
Straw 2y ago
Only in the sense that anything is a markov chain with some sufficiently large state size. It tells you nothing about the behavior.
- f33d5173 2y ago
  Not anything is a markov chain. Markov chains are distinguished by probabalistic transitions between states, just like llms
  - lostmsu 2y ago
    LLM transitions are pseudoprobabilistic.
    - Jensson 2y ago
      No, LLM just returns a distribution of states, you can use a real random function to make the transition if you want it has nothing to do with the LLM itself, the pseudoprobability function is just an optimization since you need hardware to get really random numbers.
- jltsiren 2y ago
  That's only true for Markov chains with an (effectively) infinite state space. If the state space is finite, such as with an LLM with a finite set of tokens and a finite context length, it's trivial to tell the difference between the behavior of a specific Markov chain and a more sophisticated model. Once you have a specific Markov chain, the state space is fixed, and you can just ask something that requires a larger state space. The same basic idea can be found everywhere in mathematics and CS. Once you have chosen the value for your parameter, I can choose the value for my parameter to guarantee the desired outcome.
ben_w 2y ago
While it is obviously trivially (in the mathematical sense of "trivially") possible to make a Markov chain that produces the same f(input context window) => {output distribution}, that doesn't make it useful to describe LLMs as a kind of Markov chain. After all, in the same sense I can also make a Markov chain that reproduces the behaviour of any human, or even any Turing machine with finite tape — it's just that a computer with 1 GB of memory (all kinds including non-volatile) has 2^(8*(10^30)) states.
- benchmarkist 2y ago
  I've seen this nonsensical equivalence several times now so I'm going to make an example out of you to prove a point. Define the state space for the human Markov chain.
  - ben_w 2y ago
    > Define the state space for the human Markov chain. At most the Berkenstein bound for the mass of a human brain. Is that big? Yes, too huge to bother calculating. That's why I'm using it as an example to say "it's a Markov chain" is not helpful. But it is finite, and that means it's mathematically equivalent. And that's before the thing about transition matrices being (in general if not in particular) square, from any one state to any other. For fun, here's the Berkenstein bound for the equivalent transition matrix for the much smaller GPT-3 with 2048 context length, measured in (amongst other things) multiples of the size of the universe: 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... (Assuming I didn't fluff the algebra). Edit: I fluffed the agebra, see if you can spot the typo. It's much much bigger.
    - benchmarkist 2y ago
      What are the states? I didn't say give me a count of the states. I said give me the algorithm for determining whether any given state of the universe corresponds to whatever human you are reducing to a Markov chain. I don't care if it's practical or not because it seems like you're convinced this algorithm exists even though you have never actually gone through the trouble of actually formalizing it. So I'm doing you a favor, you will either learn about your ignorance or you will make your argument algorithmically formal and actually prove that people are equivalent to Markov chains.
refulgentis 2y ago
Its because they're speaking colloquially instead of pedantically. i.e. an LLM is just a bag of bytes is pedantically true, but misses enough that I'd expect to get corrections :)

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

Straw 2y ago

Only in the sense that anything is a markov chain with some sufficiently large state size. It tells you nothing about the behavior.

f33d5173 2y ago
Not anything is a markov chain. Markov chains are distinguished by probabalistic transitions between states, just like llms
- lostmsu 2y ago
  LLM transitions are pseudoprobabilistic.
  - Jensson 2y ago
    No, LLM just returns a distribution of states, you can use a real random function to make the transition if you want it has nothing to do with the LLM itself, the pseudoprobability function is just an optimization since you need hardware to get really random numbers.
jltsiren 2y ago
That's only true for Markov chains with an (effectively) infinite state space. If the state space is finite, such as with an LLM with a finite set of tokens and a finite context length, it's trivial to tell the difference between the behavior of a specific Markov chain and a more sophisticated model. Once you have a specific Markov chain, the state space is fixed, and you can just ask something that requires a larger state space. The same basic idea can be found everywhere in mathematics and CS. Once you have chosen the value for your parameter, I can choose the value for my parameter to guarantee the desired outcome.

ben_w 2y ago

While it is obviously trivially (in the mathematical sense of "trivially") possible to make a Markov chain that produces the same f(input context window) => {output distribution}, that doesn't make it useful to describe LLMs as a kind of Markov chain. After all, in the same sense I can also make a Markov chain that reproduces the behaviour of any human, or even any Turing machine with finite tape — it's just that a computer with 1 GB of memory (all kinds including non-volatile) has 2^(8*(10^30)) states.

benchmarkist 2y ago
I've seen this nonsensical equivalence several times now so I'm going to make an example out of you to prove a point. Define the state space for the human Markov chain.
- ben_w 2y ago
  > Define the state space for the human Markov chain. At most the Berkenstein bound for the mass of a human brain. Is that big? Yes, too huge to bother calculating. That's why I'm using it as an example to say "it's a Markov chain" is not helpful. But it is finite, and that means it's mathematically equivalent. And that's before the thing about transition matrices being (in general if not in particular) square, from any one state to any other. For fun, here's the Berkenstein bound for the equivalent transition matrix for the much smaller GPT-3 with 2048 context length, measured in (amongst other things) multiples of the size of the universe: 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... (Assuming I didn't fluff the algebra). Edit: I fluffed the agebra, see if you can spot the typo. It's much much bigger.
  - benchmarkist 2y ago
    What are the states? I didn't say give me a count of the states. I said give me the algorithm for determining whether any given state of the universe corresponds to whatever human you are reducing to a Markov chain. I don't care if it's practical or not because it seems like you're convinced this algorithm exists even though you have never actually gone through the trouble of actually formalizing it. So I'm doing you a favor, you will either learn about your ignorance or you will make your argument algorithmically formal and actually prove that people are equivalent to Markov chains.

refulgentis 2y ago

Its because they're speaking colloquially instead of pedantically. i.e. an LLM is just a bag of bytes is pedantically true, but misses enough that I'd expect to get corrections :)