8 ms·

This paper states a completely obvious tautology which is that if you limit the context length, a LLM has a finite state size!

by Straw 2y ago

ogogmad 2y ago
The abstract mentions "stationary distributions". So they try to derive something new from that borderline obvious equivalence. The Google search engine originally used the stationary distribution to rank the importance of search results.
Jensson 2y ago
> 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.
        2y ago
  - 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 :)
Lerc 2y ago
I'm not sure how this distinguishes the process from a table of all possible input context windows(and rng state if you want temperature) with their desired output. This has been argued as a theoretical(but larger than the universe) model in philosophy for long enough that I wouldn't be surprised if it predates the notion of creating a machine intelligence. Without any mechanism for generalisation, it can be argued that it is simply a record of an intelligence with the actual mind being whatever created the table I guess you can think of Markov chains as a form of that table shrunk down to a hash table of the input storing only a set of the most probable outputs for any collisions. With the right semantic hashing you could consider it analogous to a LLM, but I feel there's a lot leaning on the term 'semantic hashing', because that's where the magic is in the LLM.

This paper states a completely obvious tautology which is that if you limit the context length, a LLM has a finite state size!

by Straw 2y ago

This paper states a completely obvious tautology which is that if you limit the context length, a LLM has a finite state size!

ogogmad 2y ago

The abstract mentions "stationary distributions". So they try to derive something new from that borderline obvious equivalence. The Google search engine originally used the stationary distribution to rank the importance of search results.

Jensson 2y ago

> 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.
        2y ago
- 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 :)

Lerc 2y ago

I'm not sure how this distinguishes the process from a table of all possible input context windows(and rng state if you want temperature) with their desired output. This has been argued as a theoretical(but larger than the universe) model in philosophy for long enough that I wouldn't be surprised if it predates the notion of creating a machine intelligence. Without any mechanism for generalisation, it can be argued that it is simply a record of an intelligence with the actual mind being whatever created the table I guess you can think of Markov chains as a form of that table shrunk down to a hash table of the input storing only a set of the most probable outputs for any collisions. With the right semantic hashing you could consider it analogous to a LLM, but I feel there's a lot leaning on the term 'semantic hashing', because that's where the magic is in the LLM.