The difference is in the data structure and the size of the atoms/n-grams. The data structure Markov chain implementations use is not efficient for billions of parameters, either in storage or in processing. But the idea is the same: give a likely next token given the last n tokens. The value for n is a narrow window for Markov chains and an extremely wide window for LLM. LLM are able to maintain massive amounts of state compared to a Markov chain implementation.
To compare Markov Chain with an LLM is kind of like to compare a single cell organism to a human being because we both are based on cells.
Sure, today's LLMs blow them out of the water, but the difference was much less striking with neural networks even as late as 2010.
For example, I remember /r/SubredditSimulator blowing my mind, and I’m pretty sure that was markov chains
P.S.: "2010" was probably from this great Ars Technica article :
https://arstechnica.com/gaming/2011/01/skynet-meets-the-swar...
It's not clear to me whether neural networks were already involved (though there's already some self-learning there), you can see a few Ars and YouTube comments mentioning them, though "genetic algorithms" seems to also have been a popular buzzword ?
P.P.S.: This is about StarCraft 1 (ONE), not to be confused with DeepMind's Alpha Star wiping the floor with a pro StarCraft 2 (TWO) player in 2018.
I’d argue the same is true of LLMs vs simpler models like Markov chains.
There's a qualitative difference too.
A better comparison would be that it's like a windup toy versus a group of humans moving an entire civilization. They both move along a distance, but just listing the systems that the human group has that the windup toy doesn't is too long to fit on a page.
LLM architecture is a markov chain to the core. It isn't a lookup table like old markov chains but it is still a markov chain: next word prediction based on previous words.
Seems like most people fail to understand that LLMs (as they are implemented these days) are markov chains by definition, regardless of how much "better" they are compared to "Dissociated Press"-style markov chains based on lookup tables.
> A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which *the probability of each event depends only on the state attained in the previous event*.
Is the process calculating a probability distribution over "next token", based on a bounded-size context of "previous tokens"? Yes? Then it is a markov chain, by definition.
It's like saying that a "human" is not an "animal", since it is so much "better" and "capable" than (other/usual) animals. The more you argue, the more I'll be convinced that you either don't know what the definition of a "human" is, or that you don't know what the definition of an "animal" is (or both).
Despite this it’s equally obvious that the intelligence IS in the human brain, inside the skull. Shoot the right parts (frequently done by accident, so many subjects for research) and the intelligence is gone. It IS possible to radically change behaviour of a human by destroying part of the brain. There is no external soul that manages things behind the scene. Human intelligence and our souls are emergent. The are “software”, not hardware.
All the criticism against AI you make therefore applies equally to a human mind. Yet obviously it shouldn’t. To be more exact: it fails to differentiate between human minds and AI. Behaviours could emerge at any time in AI, even in transformer networks. Hell, transformers are famous for their emergent behaviours. Yes their components are obviously not intelligent. Neither are your components, or mine.
Yes the machine has no soul. The problem is: neither do you.
A Markov model, by definition, works only with literal token histories. It can't participate meaningfully in a conversation unless the user happens to employ token sequences that the model has seen before (ideally multiple times.) An LLM can explain why it's not just a Markov model, but the converse isn't true.
Now, if you were to add high-dimensional latent-space embedding to a Markov model, that would make the comparison more meaningful, and would allow tractable computation with model sizes that were completely impossible to deal with before. But then it wouldn't be a Markov model anymore. Or, rather, it would still be a Markov model, but one that's based on relationships between tokens rather than just their positions in a linear list.
Another analogy might be to say that a Markov model can implement lossless compression only, while a latent-space model can implement lossy compression. There's a school of thought that says that lossy compression doesn't just require intelligence, it is intelligence, and LLMs can be seen as an example of that equivalence. Not saying I agree with that school, or that you should, but as someone else pointed out, comparing Markov chains with LLMs are at best like comparing goldfish brains with human brains.
That's what we call a hidden Markov model.
>There's a school of thought that says that lossy compression doesn't just require intelligence, it is intelligence, and LLMs can be seen as an example of that equivalence.
SVD is used to implement lossy compression as does JPEG encoding... these algorithms are in no way intelligent.
In particular, JPEG has intelligence encoded about how graphics are displayed, what detail we won’t notice is missing, and what artifacts we won’t notice are present, much like the psychoacoustic models behind lossy music compression schemes like MP3.
But we had to feed an encoder that by way of algorithmic design. It’s hardcoded intelligence, like any other function, but with a lot more outside knowledge required to do it right than a sort or swap.
I’d call an LLM a more general problem solver. It can write cogent limericks, convincingly screw up math, summarize papers it’s never seen before, generate book plots or character arcs based on specific requests, translate to a language you just made up and explained in the prompt, etc.
The intelligent bits are emergent and can do something reasonable with novel input, even if it doesn’t closely resemble the exact material it was trained on.
The comparison would be a process that could lossy-compress any kind of sensory media possible with no perceptible loss, based solely on its training on human capabilities and how the reproduction devices work—i.e. it could create the JPEG algorithm, not just perform it.
You'll have to take that up with people above my pay grade. It's not that simple, apparently. Call me when a Markov model can explain why it's equivalent to an LLM.
Which leads to a wonderful tongue-in-cheek contraindication: representation types such as a particular model, when it’s complexity increases, especially via edge cases, it is then a result of agentic anti-intelligence.
That is to say, anything that increases in complexity without being refactored is a sign of a lack of intelligence or worse.
And any sense of information that is impossible to be reduced further while maintaining equal or more expressibility are signs of maximum agentic intelligence.
"Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens"
No.
I'd believe $40 for the energy cost, $120 for very slightly increased wear on their hard drives, and $400 for one engineer's 20% time project for one week.
And that's if it was trained on Google's entire internet cache rather than, say, just a Wikipedia snapshot from 2004, which sounds like the kind of thing that Google might have set as a pre-interview coding challenge.
Markov Chains are dead simple. There's not really a "training" as much as it's simply reading data and collecting statistics.
They're so simple that you can probably build one nearly as fast as you can read the training data.
We say systems can perform the same types of computations if they're both Turing complete. Yet, we wouldn't implement everything in every "language" that is Turing complete.
Perhaps, every LLM could be represented as a Markov chain, and for some it even makes sense (e.g., easier to train, easier to reason about), but in most cases it's a bad idea (e.g., expensive, bad performance).
They're based on the same principles, but extend quite beyond that, and are way smarter than Markov Chains.
So, it's not just the infrastructure that's makes the difference (if they were only as effective as Markov Chains, then having the same or even more infrastructure wouldn't make any difference).
And that's why people have been nodding, smiling politely and reaching behind their back for the doorknob.
As the article says, Markov chains can be thought of as linear operations, which are very limited, and the reason early neural networks weren't taken seriously. Notoriously, you couldn't implement a XOR operation using these early neural nets.
It all changed when we got to multi-layer perceptrons, with backpropagation. The key here is the transfer function, which is non-linear, which allows the network to do infinitely more what you can achieve with simple linear combinations. And it is also differentiable, which allows for learning using backpropagation. This is the theoretical foundation behind LLMs, diffusion models, classifiers, etc... Essentially everything we call "AI" today.
So, yes, by being non-linear, LLMs are deeply smarter than Markov chains (pun intended).
Then you're doing some combination of grossly overestimating the latter and/or underestimating the former.
A Markov Chain is a (small) language model with a context length of 1, never more, that's a definitional requirement of a Markov process.
As an example, de Bruijn graphs have been widely used in bioinformatics. There are many definitions, but the key idea is that nodes are strings of length k, and there may be an edge from u to v if the length k-1 suffix of u is the same as the length k-1 prefix of v. It's trivial to turn a de Bruijn graph into a Markov chain with a context of k symbols.
If you have the Burrows-Wheeler transform of the training data, you can use it to simulate a Markov chain over a de Bruijn graph with any context length. You can also change the context length on the fly. I toyed a little bit with that idea when I was a grad student ~15 years ago, but nothing really came out of it. Building the model was already cheap back then, while getting data was the real bottleneck.
LLMs are basically lossy approximations of Markov chains. If you have a small accurate approximation of a larger model, the approximate model probably has the ability to generalize. And it turns out that good generalization over textual data looks like intelligent behavior.
While true, I don't see how that helps? The example isn't particularly illuminating, yes you can make a Markov chain that encompasses all possible states in principle, but in practice you can't do that with a language model because you can't list all possible states (they mostly don't exist in the training set but even if they did there's no room to store them) and instead have to make a system which is, for lack of a non-anthropomorphic verbs, "trying to guess" the state — most of the cool stuff in the LLM is the system doing the guessing[0].
> If you have the Burrows-Wheeler transform of the training data, you can use it to simulate a Markov chain over a de Bruijn graph with any context length. You can also change the context length on the fly. I toyed a little bit with that idea when I was a grad student ~15 years ago, but nothing really came out of it. Building the model was already cheap back then, while getting data was the real bottleneck.
To me, the Burrows-Wheeler transform looks like a way to generate a compact tokenisation that doesn't make presumptions about data structure — while I think that's a good idea (and much better than the naive English language tokenisation of "anything that's not a letter or apostrophe" which IMO probably harmed early NLP), I don't think it's a good argument for drawing similarities between Transformer models (or even RNN models) and Markov models
> LLMs are basically lossy approximations of Markov chains. If you have a small accurate approximation of a larger model, the approximate model probably has the ability to generalize. And it turns out that good generalization over textual data looks like intelligent behavior.
I wonder if you're using "approximation" to mean something different than I would understand the term?
You can map a Turing machine to a sufficiently large Markov chain whose probabilities are always 1 or 0, but that has the same problem: Turing machines and LLMs aren't lossy approximations of Markov chains, they're at least generalisations that only look the same when you construct an extreme form.
Hopefully we both agree that it would be very weird to argue that "the language centres of human brains are basically just approximations of Markov chains"? Even though we can probably sufficiently well describe each neuron within a brain by a Markov chain?
[0] This reminds me of my issue with John Searle's Chinese room argument: Searle denies the system truly understands Chinese because the human reading the books and following the instructions doesn't know Chinese, I would argue that the intelligence and understanding is encoded in the books, and that the entity lacking understanding is the substrate upon which the instructions are processed.
To argue "the system as a whole can't be said to understand because the human doing the data processing doesn't understand" seems to me to map to saying "humans can't be said to understand because the brain cells doing the data processing don't understand", or even "… atoms conveying electrochemical signals across synapses don't understand".
But I'm clearly digressing now, so I'm glad I put this in a footnote…
What I do see though is the infrastructure around LLMs making a difference.