8 ms·

A Markov Chain trained by only a single article of text will very likely just regurgitate entire sentences straight from the source material. There just isn't

A Markov Chain trained by only a single article of text will very likely just regurgitate entire sentences straight from the source material. There just isn't enough variation in sentences. But then, Markov Chains fall apart when the source material is very large. Try training a chain based on Wikipedia. You'll find that the resulting output becomes incoherent garbage. Increasing the context length may increase coherence, but at the cost of turning into just simple regurgitation. In addition to the "attention" mechanism that another commenter mentioned, it's important to note that Markov Chains are discrete in their next token prediction while an LLM is more fuzzy. LLMs have latent space where the meaning of a word basically exists as a vector. LLMs will generate token sequences that didn't exist in the source material, whereas Markov Chains will ONLY generate sequences that existed in the source. This is why it's impossible to create a digital assistant, or really anything useful, via Markov Chain. The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative.

johnisgood 11mo ago
> The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative. I have seen the argument that LLMs can only give you what its been trained on, i.e. it will not be "creative" or "revolutionary", that it will not output anything "new", but "only what is in its corpus". I am quite confused right now. Could you please help me with this? Somewhat related: I like the work of David Hume, and he explains it quite well how we can imagine various creatures, say, a pig with a dragon head, even if we have not seen one ANYWHERE. It is because we can take multiple ideas and combine them together. We know how dragons typically look like, and we know how a pig looks like, and so, we can imagine (through our creativity and combination of these two ideas) how a pig with a dragon head would look like. I wonder how this applies to LLMs, if they even apply. Edit: to clarify further as to what I want to know: people have been telling me that LLMs cannot solve problems that is not in their training data already. Is this really true or not?
- jldugger 11mo ago
  Well, there's kind of two answers here: 1. To the extent that creativity is randomness, LLM inference samples from the token distribution at each step. It's possible (but unlikely!) for an LLM to complete "pig with" with the token sequence "a dragon head" just by random chance. The temperature settings commonly exposed control how often the system takes the most likely candidate tokens. 2. A markov chain model will literally have a matrix entry for every possible combination of inputs. So a 2 degree chain will have n^2 weights, where N is the number of possible tokens. In that situation "pig with" can never be completed with a brand new sentence, because those have literal 0's in the probability. In contrast, transformers consider huge context windows, and start with random weights in huge neural network matrices. What people hope happens is that the NN begins to represent ideas, and connections between them. This gives them a shot at passing "out of distribution" tests, which is a cornerstone of modern AI evaluation.
  - theGnuMe 11mo ago
    You can have small epsilons instead of zeros.
    - ruined 11mo ago
      what, for all possible words?
      - 3eb7988a1663 11mo ago
        Instead of a naive dense matrix, you can use some implementation that allows sparsity. If element does not exist, gets a non-zero value which can still be sampled. Which theoretically enables all outputs.
        ruined 11mo ago
        i think at that point it's definitionally not a markov chain anymore. how do you sample an open set of unknown values?
thfuran 11mo ago
>Markov Chains will ONLY generate sequences that existed in the source. A markov chain of order N will only generate sequences of length N+1 that were in the training corpus, but it is likely to generate sequences of length N+2 that weren't (unless N was too large for the training corpus and it's degenerate).
- Isamu 11mo ago
  Right, you can generate long sentences from a first-order markov model, and all of the transitions from one word to the next be in the training set but the full generated sentence may not.
- Sohcahtoa82 11mo ago
  Well yeah, but N+2 but the generation of the +2 loses the first part of N. If you use a context window of 2, then yes, you might know that word C can follow words A and B, and D can follow words B and C, and therefore generate ABCD even if ABCD never existed. But it could be that ABCD is incoherent. For example, if A = whales, B = are, C = mammals, D = reptiles. "Whales are mammals" is fine, "are mammals reptiles" is fine, but "Whales are mammals reptiles" is incoherent. The longer you allow the chain to get, the more incoherent it becomes. "Whales are mammals that are reptiles that are vegetables too". Any 3-word fragment of that sentence is fine. But put it together, and it's an incoherent mess.
  - Y_Y 11mo ago
    That are reptiles!
- Jensson 11mo ago
  > A markov chain of order N will only generate sequences of length N+1 that were in the training corpus Depends on how you trained it, an LLM is also a markov chain.
vjerancrnjak 11mo ago
If you learn with Baum Welch you can get nonzero ood probabilities. Something like Markov Random Field is much better. Not sure if anyone managed to create latent hierarchies from chars to words to concepts. Learning NNs is far more tinkery than brutality of probabilistic graphical models.
ssivark 11mo ago
Uhhh... the above comment has a bunch of loose assertions that are not quite true, but with a enough truthiness that makes them hard to refute. So I'll point to my other comment for a more nuanced comparison of Markov models with tiny LLMs: https://news.ycombinator.com/item?id=45996794 https://news.ycombinator.com/item?id=45996794
- nazgul17 11mo ago
  To add to this, the system offering text generation, i.e. the loop that builds the response one token at a time generated by a LLM (and at the same time feeds the LLM the text generated so far) is a Markov Model, where the transition matrix is replaced by the LLM, and the state space is the space of all texts.
psychoslave 11mo ago
> You'll find that the resulting output becomes incoherent garbage. I also do that kind of things with LLM. The other day, I don't remember the prompt (something casual really, not trying to trigger any issue) but le chat mistral started to regurgitate "the the the the the...". And this morning I was trying a some local models, trying to see if they could output some Esperanto. Well, that was really a mess of random morphs thrown together. Not syntactically wrong, but so out of touch with any possible meaningful sentence.
- lotyrin 11mo ago
  Yeah, some of the failure modes are the same. This one in particular is fun because even a human, given "the the the" and asked to predict what's next will probably still answer "the". How a Markov chain starts the the train and how the LLM does are pretty different though.
  - psychoslave 11mo ago
    I never saw any human starting to loop "the" as a reaction to any utterance though. Personally my concern is more about the narrative that LLM are making "chain of thoughts", can "hallucinante" and that people should become "AI complement". They are definitely making nice inferences most of the time, but they are also totally different thing compared to human thoughts.
    - stavros 11mo ago
      I've definitely seen (and have myself) gotten stuck in phrase loops. We call it "stuttering".
      - psychoslave 11mo ago
        Good point, we human definitely have defects too. I’ll reflect on this, though this doesn’t make me consider that chip inferences to be fully analog to what happen in humans when they are thinking (or any animal/entity ongoing a thought process).
papyrus9244 11mo ago
> This is why it's impossible to create a digital assistant, or really anything useful, via Markov Chain. The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative. Or, in other words, a Markov Chain won't hallucinate. Having a system that only repeats sentences from it's source material and doesn't create anything new on its own is quite useful on some scenarios.
- Sohcahtoa82 11mo ago
  > Or, in other words, a Markov Chain won't hallucinate. It very much can. Remember, the context windows used for Markov Chains are usually very short, usually in the single digit numbers of words. If you use a context length of 5, then when asking it what the next word should be, it has no idea what the words were before the current context of 5 words. This results in incoherence, which can certainly mean hallucinations.
- vrighter 11mo ago
  You can very easily inject wrong information into the state transition function. And machine learning can and regularly does do so. That is not a difference between an LLM and a markov chain.
- stavros 11mo ago
  A Markov chain certainly will not hallucinate, because we define hallucinations as garbage within otherwise correct output. A Markov chain doesn't have enough correct output to consider the mistakes "hallucinations", but in a sense that nothing is a hallucination when everything is one.
dragonwriter 11mo ago
> A Markov Chain trained by only a single article of text will very likely just regurgitate entire sentences straight from the source material. Strictly speaking, this is true of one particular way (the most straightforward) to derive a Markov chain from a body of text; a Markov chain is just a probabilistic model of state transitions where the probability of each possible next state is dependent only on the current state. Having the states be word sequence of some number of words, overlapping by all but one word, and having the probabilities being simply the frequency with which the added word in the target state follows the sequence in the source state in the training corpus is one way you can derive a Markov chain from a body of text, but not the only one.
- JPLeRouzic 11mo ago
  > A Markov Chain trained by only a single article of text will very likely just regurgitate entire sentences straight from the source material. I see this as a strength; try training an LLM on a 42KB text to see if it can produce a coherent output.
Kinrany 11mo ago
Markov Chains could be applied on top of embeddings just as well though
vrighter 11mo ago
Building a static table of seen inputs is just one way of building a state transition table for a markov chain. It is just an implementation detail of a function (in the mathematical sense of the word. no side effects) that takes in some input and outputs a probability distribution. You could make the table bigger and fill in the rest yourself. Or you could use machine learning to do it. But then the table would be too huge to actually store due to combinatorial explosion. So we find a way to reduce that memory cost. How about we don't precompute the whole table and lazily evaluate individual cells as/when they are needed? You achieve that by passing it through the machine-learned function (a trained network is a fixed function with no side effects.) You might say but that's not the same thing!!! But remember that the learned network will always output the same distribution if given the same input, because it is a function. Let's say you have a context size of 1000 and have 10 possible tokens. There are 10^1000 possible inputs. A huge number, but most importantly, a finite number. So you could in theory feed them all in one at a time and record the result in a table. While we can't really do this in practice, because the resulting table would be huge. It is, for all mathematical purposes, equivalent and you could, in theory, freely transform one into the other. Et voila! You have built a markov chain anyway. Previous input goes in, magic happens inside (whichever implementation you used to implement the function doesn't matter), and a probability distribution comes out. It's a markov chain. It doesn't quack and walk like a duck. It IS an actual duck.
lukan 11mo ago
"This is why it's impossible to create a digital assistant, or really anything useful, via Markov Chain. The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative." That reads like anything useful needs to be creative? I would disagree here. A digital assistent, in control of a automatic door for example should not be creative, but stupidly do exactly as told. "Open the door". "Close the door". And the "creativity" of KI agents I see rather as a danger here.
- cwillu 11mo ago
  Most physical problems require some level of creativity: your door opening robot should be able to handle some level of dust on the handle, some level of slipperiness of the floor, some amount of packages blocking where it wants to stand, and crucially: some level of all of those things where it gives up rather than causing damage. You can't open-loop everything, and the edge cases in a closed-loop absolutely explodes. Yes, a “digital assistant“ responsible only for handling a door is manageable, but even “get a pot, fill it with water, and boil it” gets _remarkably_ complicated if you need reduce all the edge cases to known regions of behaviour that you can pre-program responses to.
  - lukan 11mo ago
    Yes, but I want those sensor input and fail modes handled with deterministic classical algorithms without (LLM) creativity, otherwise I envision doors that refuse to open on certain dates, because somewhere in its training corpus was a satirical sci fi story about depressed smart doors. (And no, I was not talking about a robot butler, but a automatic door. Infrared triggered, but enhanced with a text mode for control)
anshumankmr 11mo ago
>This is why it's impossible to create a digital assistant, or really anything useful, via Markov Chain. The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative. Its funny cause they say the same thing about LLMs (sort of)
sli 11mo ago
I've had a lot of fun training Markov chains using Simple English Wikipedia. I'm guessing the restricted vocabulary leads to more overlapping sentences in the training data. Anything too advanced or technical has too many unique phrases and the output degrades almost immediately.

johnisgood 11mo ago

> The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative. I have seen the argument that LLMs can only give you what its been trained on, i.e. it will not be "creative" or "revolutionary", that it will not output anything "new", but "only what is in its corpus". I am quite confused right now. Could you please help me with this? Somewhat related: I like the work of David Hume, and he explains it quite well how we can imagine various creatures, say, a pig with a dragon head, even if we have not seen one ANYWHERE. It is because we can take multiple ideas and combine them together. We know how dragons typically look like, and we know how a pig looks like, and so, we can imagine (through our creativity and combination of these two ideas) how a pig with a dragon head would look like. I wonder how this applies to LLMs, if they even apply. Edit: to clarify further as to what I want to know: people have been telling me that LLMs cannot solve problems that is not in their training data already. Is this really true or not?

jldugger 11mo ago
Well, there's kind of two answers here: 1. To the extent that creativity is randomness, LLM inference samples from the token distribution at each step. It's possible (but unlikely!) for an LLM to complete "pig with" with the token sequence "a dragon head" just by random chance. The temperature settings commonly exposed control how often the system takes the most likely candidate tokens. 2. A markov chain model will literally have a matrix entry for every possible combination of inputs. So a 2 degree chain will have n^2 weights, where N is the number of possible tokens. In that situation "pig with" can never be completed with a brand new sentence, because those have literal 0's in the probability. In contrast, transformers consider huge context windows, and start with random weights in huge neural network matrices. What people hope happens is that the NN begins to represent ideas, and connections between them. This gives them a shot at passing "out of distribution" tests, which is a cornerstone of modern AI evaluation.
- theGnuMe 11mo ago
  You can have small epsilons instead of zeros.
  - ruined 11mo ago
    what, for all possible words?
    - 3eb7988a1663 11mo ago
      Instead of a naive dense matrix, you can use some implementation that allows sparsity. If element does not exist, gets a non-zero value which can still be sampled. Which theoretically enables all outputs.
      - ruined 11mo ago
        i think at that point it's definitionally not a markov chain anymore. how do you sample an open set of unknown values?

thfuran 11mo ago

>Markov Chains will ONLY generate sequences that existed in the source. A markov chain of order N will only generate sequences of length N+1 that were in the training corpus, but it is likely to generate sequences of length N+2 that weren't (unless N was too large for the training corpus and it's degenerate).

Isamu 11mo ago
Right, you can generate long sentences from a first-order markov model, and all of the transitions from one word to the next be in the training set but the full generated sentence may not.
Sohcahtoa82 11mo ago
Well yeah, but N+2 but the generation of the +2 loses the first part of N. If you use a context window of 2, then yes, you might know that word C can follow words A and B, and D can follow words B and C, and therefore generate ABCD even if ABCD never existed. But it could be that ABCD is incoherent. For example, if A = whales, B = are, C = mammals, D = reptiles. "Whales are mammals" is fine, "are mammals reptiles" is fine, but "Whales are mammals reptiles" is incoherent. The longer you allow the chain to get, the more incoherent it becomes. "Whales are mammals that are reptiles that are vegetables too". Any 3-word fragment of that sentence is fine. But put it together, and it's an incoherent mess.
- Y_Y 11mo ago
  That are reptiles!
Jensson 11mo ago
> A markov chain of order N will only generate sequences of length N+1 that were in the training corpus Depends on how you trained it, an LLM is also a markov chain.

vjerancrnjak 11mo ago

If you learn with Baum Welch you can get nonzero ood probabilities. Something like Markov Random Field is much better. Not sure if anyone managed to create latent hierarchies from chars to words to concepts. Learning NNs is far more tinkery than brutality of probabilistic graphical models.

ssivark 11mo ago

Uhhh... the above comment has a bunch of loose assertions that are not quite true, but with a enough truthiness that makes them hard to refute. So I'll point to my other comment for a more nuanced comparison of Markov models with tiny LLMs: https://news.ycombinator.com/item?id=45996794 https://news.ycombinator.com/item?id=45996794

nazgul17 11mo ago
To add to this, the system offering text generation, i.e. the loop that builds the response one token at a time generated by a LLM (and at the same time feeds the LLM the text generated so far) is a Markov Model, where the transition matrix is replaced by the LLM, and the state space is the space of all texts.

psychoslave 11mo ago

> You'll find that the resulting output becomes incoherent garbage. I also do that kind of things with LLM. The other day, I don't remember the prompt (something casual really, not trying to trigger any issue) but le chat mistral started to regurgitate "the the the the the...". And this morning I was trying a some local models, trying to see if they could output some Esperanto. Well, that was really a mess of random morphs thrown together. Not syntactically wrong, but so out of touch with any possible meaningful sentence.

lotyrin 11mo ago
Yeah, some of the failure modes are the same. This one in particular is fun because even a human, given "the the the" and asked to predict what's next will probably still answer "the". How a Markov chain starts the the train and how the LLM does are pretty different though.
- psychoslave 11mo ago
  I never saw any human starting to loop "the" as a reaction to any utterance though. Personally my concern is more about the narrative that LLM are making "chain of thoughts", can "hallucinante" and that people should become "AI complement". They are definitely making nice inferences most of the time, but they are also totally different thing compared to human thoughts.
  - stavros 11mo ago
    I've definitely seen (and have myself) gotten stuck in phrase loops. We call it "stuttering".
    - psychoslave 11mo ago
      Good point, we human definitely have defects too. I’ll reflect on this, though this doesn’t make me consider that chip inferences to be fully analog to what happen in humans when they are thinking (or any animal/entity ongoing a thought process).

papyrus9244 11mo ago

> This is why it's impossible to create a digital assistant, or really anything useful, via Markov Chain. The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative. Or, in other words, a Markov Chain won't hallucinate. Having a system that only repeats sentences from it's source material and doesn't create anything new on its own is quite useful on some scenarios.

Sohcahtoa82 11mo ago
> Or, in other words, a Markov Chain won't hallucinate. It very much can. Remember, the context windows used for Markov Chains are usually very short, usually in the single digit numbers of words. If you use a context length of 5, then when asking it what the next word should be, it has no idea what the words were before the current context of 5 words. This results in incoherence, which can certainly mean hallucinations.
vrighter 11mo ago
You can very easily inject wrong information into the state transition function. And machine learning can and regularly does do so. That is not a difference between an LLM and a markov chain.
stavros 11mo ago
A Markov chain certainly will not hallucinate, because we define hallucinations as garbage within otherwise correct output. A Markov chain doesn't have enough correct output to consider the mistakes "hallucinations", but in a sense that nothing is a hallucination when everything is one.

dragonwriter 11mo ago

> A Markov Chain trained by only a single article of text will very likely just regurgitate entire sentences straight from the source material. Strictly speaking, this is true of one particular way (the most straightforward) to derive a Markov chain from a body of text; a Markov chain is just a probabilistic model of state transitions where the probability of each possible next state is dependent only on the current state. Having the states be word sequence of some number of words, overlapping by all but one word, and having the probabilities being simply the frequency with which the added word in the target state follows the sequence in the source state in the training corpus is one way you can derive a Markov chain from a body of text, but not the only one.

JPLeRouzic 11mo ago
> A Markov Chain trained by only a single article of text will very likely just regurgitate entire sentences straight from the source material. I see this as a strength; try training an LLM on a 42KB text to see if it can produce a coherent output.

Kinrany 11mo ago

Markov Chains could be applied on top of embeddings just as well though

vrighter 11mo ago

Building a static table of seen inputs is just one way of building a state transition table for a markov chain. It is just an implementation detail of a function (in the mathematical sense of the word. no side effects) that takes in some input and outputs a probability distribution. You could make the table bigger and fill in the rest yourself. Or you could use machine learning to do it. But then the table would be too huge to actually store due to combinatorial explosion. So we find a way to reduce that memory cost. How about we don't precompute the whole table and lazily evaluate individual cells as/when they are needed? You achieve that by passing it through the machine-learned function (a trained network is a fixed function with no side effects.) You might say but that's not the same thing!!! But remember that the learned network will always output the same distribution if given the same input, because it is a function. Let's say you have a context size of 1000 and have 10 possible tokens. There are 10^1000 possible inputs. A huge number, but most importantly, a finite number. So you could in theory feed them all in one at a time and record the result in a table. While we can't really do this in practice, because the resulting table would be huge. It is, for all mathematical purposes, equivalent and you could, in theory, freely transform one into the other. Et voila! You have built a markov chain anyway. Previous input goes in, magic happens inside (whichever implementation you used to implement the function doesn't matter), and a probability distribution comes out. It's a markov chain. It doesn't quack and walk like a duck. It IS an actual duck.

lukan 11mo ago

"This is why it's impossible to create a digital assistant, or really anything useful, via Markov Chain. The fact that they only generate sequences that existed in the source mean that it will never come up with anything creative." That reads like anything useful needs to be creative? I would disagree here. A digital assistent, in control of a automatic door for example should not be creative, but stupidly do exactly as told. "Open the door". "Close the door". And the "creativity" of KI agents I see rather as a danger here.

cwillu 11mo ago
Most physical problems require some level of creativity: your door opening robot should be able to handle some level of dust on the handle, some level of slipperiness of the floor, some amount of packages blocking where it wants to stand, and crucially: some level of all of those things where it gives up rather than causing damage. You can't open-loop everything, and the edge cases in a closed-loop absolutely explodes. Yes, a “digital assistant“ responsible only for handling a door is manageable, but even “get a pot, fill it with water, and boil it” gets _remarkably_ complicated if you need reduce all the edge cases to known regions of behaviour that you can pre-program responses to.
- lukan 11mo ago
  Yes, but I want those sensor input and fail modes handled with deterministic classical algorithms without (LLM) creativity, otherwise I envision doors that refuse to open on certain dates, because somewhere in its training corpus was a satirical sci fi story about depressed smart doors. (And no, I was not talking about a robot butler, but a automatic door. Infrared triggered, but enhanced with a text mode for control)

anshumankmr 11mo ago

sli 11mo ago

I've had a lot of fun training Markov chains using Simple English Wikipedia. I'm guessing the restricted vocabulary leads to more overlapping sentences in the training data. Anything too advanced or technical has too many unique phrases and the output degrades almost immediately.