What's actually happening in a LLM is many orders of magnitude more complex than a Markov chain. However, I agree that they're an amazing pedagogical tool for the basic principles of how a LLM works, even to a non-technical audience.
Many people try to "explain" LLMs starting with the principles of neural networks. This rarely works well: there are some significant conceptual leaps required.
However, explaining that a LLMs are really just iterated next-word prediction based on a statistical model of the preceding words is something that most people can grok, and in a useful way: in my experience, it actually helps give people a useful intuition for why and how models hallucinate and what kind of things they're good/bad at.
Markov chains are super simple iterated next-word prediction model, and can be explained in 15 minutes. It's a great way to explain LLMs to laypeople.
>However, explaining that a LLMs are really just iterated next-word prediction based on a statistical model of the preceding words is something that most people can grok, and in a useful way: in my experience, it actually helps give people a useful intuition for why and how models hallucinate and what kind of things they're good/bad at.
At risk of showing my deficient understanding: that isn't actually true, is it?[1]
LLMs do much more than simply predict subsequent text, AFAICT. I think back to the earlier LLM results that wowed the world with stuff like "now I have a model where you can ask it 'king - man + woman' ... and it returns 'queen'. Trippy!"
That is pretty clearly not mere text prediction, at least not identically. Even nearly all of the computational "hard work" comes from the math of predicting subsequent letters, that whole computation is introducing a new primitive, the concept of combining, or doing math on, models to produce other models, and thereby making a statement about what words would come next in a variety of scenarios.
That primitive is not present in the Markov predictor example, at least not without positing how a Markov predictor would be similarly transformed -- which, being very ignorant on the matter, I'm not sure is possible or not, but either way, leaves out a critical construct that enables ChatGPT to e.g. find limericks that aren't preceded by the command "Write me a limerick", as in my earlier comment[1].
Predicting subsequent text is pretty much exactly what they do. Lots of very cool engineering that’s a real feat, but at its core it’s argmax(P(token|token,corpus)):
With the caveat that I'm not an LLM expert here but have read up on some of this...
What's basically going on is that the LLM has "read" vast amounts of text and classified words in all kinds of dimensions. As it goes from word to word it's predicting based on all of those dimensions, rather than the Markov chain's simple probabilities. So it knows "king" has high values of masculinity and authority, for example, and "man" has high values of masculinity without necessary the authority. Likewise for queen and woman. This also works for connective words like plus, minus, equals, etc. This leads the LLM to judge correctly that the most plausible word to continue that equation is "queen".
With enough dimensions and enough context (preceding words to include in the calculation) you get results that look like reasoning and intelligence -- and although a lot of people have started arguing that we need to define reasoning and intelligence in a way that excludes this, I'm not so sure of that. It seems quite possible that what goes on in our own heads is not so far from this with a few extra steps.
So you're saying that the word2vec king/queen result was the result of feeding the verbatim text "king+man-woman", and that text being continued as "queen"? I assumed that was more the result of doing math on the properties the model generated for the tokens king, man, queen, etc.
And in that case, why does "Write me a limerick <meeting this criteria>" result in ChatGPT producing limericks, when vanishingly few of the limericks in the source text started that way, and vanishingly few of the commands to write a limerick were immediately followed with one?
> I assumed that was more the result of doing math on the properties the model generated for the tokens king, man, queen, etc.
This isn't wrong, the model does do a bunch of "math" (HUGE matrix and vector multiplications) on the vectors generated by the tokens, but it's not like the model has any recognizable process that resembles our own reasoning process (unless you ask it to explain "its own reasoning", but the fact that the model explains it in terms of human reasoning doesn't mean that's the way it works internally -- as of today LLMs do not have introspection capabilities).
I suspect most people who haven't thought very deeply about what computation, reasoning and intelligence is would need some time to come to terms to what generative AI is telling us about them.
If it helps, do note that the models have been trained on terrabytes of training data, and the model has "learnt" a bunch of patterns that it could apply to "king+man-woman=" to come to "queen" as the answer. We could even speculate that the word2vec vectors for king and queen would have some dimensions that roughly translates to "class" (monarch), and "gender" (same for man and woman), and it would be relatively straightforward for the model to grab the token that has a signal on those same dimensions. But that's kind of a crude way to look at LLMs since the billions of parameters aren't there only to make money for nVidia, so the actual processes involve much, much, much more compute that human minds would not be able to comprehend.
You’d also get text that has very little to do with the training material from any statistical model. A prediction may have nothing to do with the past and it might be wrong or right. For example, the weather forecast said it will rain all day, but the sun is up and bright in the sky without a cloud in sight.
The model knows what a limerick is, from the source material. It knows what your criteria is from the source material. It can predict what someone would say given that prompt.
Humans also do this. I’m usually one or two words ahead of the person I’m speaking to, sometimes even entire paragraphs ahead if I’m paying full attention. My dreams give me unrealistic situations to explore new ways of dealing with them. When I write code, I have a pretty good idea of what I’m going to write before I write it.
The main difference between a human and an LLM, is that a human has no limit. A human will still continue when overwhelmed with data, usually by shedding unimportant data. An LLM will just tell you it’s too much data. Smart humans won’t just shed the data, but “mark” it mentally as potentially important in the future and come back to it once a deeper understanding is achieved.
There are other, smaller differences as well, but that is the biggest, most annoying one, so far.
It works by computing that P(queen|"king-man+woman", corpus) > P(<other-words>|"king-man+woman", corpus), i.e. it predicts that the most likely next token after that phrase, based on the entire training corpus and the loss function, is "queen".
Now, how exactly the LLM is computing this prediction remains poorly understood.
I was curious what GPT 4 would answer with that prompt:
input: king - man + woman =
"The equation you're referring to is often used as an example of how word embeddings work in natural language processing (NLP). Word embeddings are a type of word representation that allows words to be represented as vectors in a continuous vector space. This allows for capturing semantic similarities between words based on their context.
The equation "king - man + woman" is a famous example that illustrates how word embeddings can capture analogies. In vector space, the operation is meant to find a word that is similar to "king" but more closely associated with "woman" than "man". The result of this operation is often "queen".
This result demonstrates the ability of certain word embedding models, like Word2Vec or GloVe, to capture relational similarities between words. It's a reflection of the model's capacity to understand that the relationship between "king" and "man" is similar to the relationship between "queen" and "woman", based on the learned vector representations of these words from large text corpora."
word2vec is a very cool result, but suggestive at best for how a modern LLM works. in fact the king + country - queen + capital vector Mary you’re referring to is pretty much a direct consequence of excluding nonlinear ties from the SGD-driven matrix factorization process.
Predicting the next token is how they are trained. But how they operate to achieve that goal is much, much more complicated than the principle of a Markov chain.
In theory, you are the byproduct of 'training' to survive and reproduce. Humans are very good at that task.
But their net capabilities developed to succeed at it extend far beyond the scope of the task alone.
What you described was the vector space utility and mathematics which is the result of encoding it into a dimensional space (latent?).
SOTA LLM use vector space dimensional embeddings in order to utilize a coordinate based intelligence “for free” with a vector space prediction mechanism on the index of context.
My understanding is that LLMs are basically approximations of Markov chains where the state and probability distribution is thousands of words long. If you could directly compute and use that matrix, you'd get the same result. But that would be insane.
I'm pretty sure that is a property of the word2vec embeddings. I'm not 100% sure if the embeddings/hidden states in LLM's have the same property but my guess would be they do.
I like your question, and I cannot answer it. But I have a benchmark: I can write a Markov chain "language model" in around 10-20 lines of Python, with zero external libraries -- with tokenization and "training" on a text file, and generating novel output. I wrote it in several minutes and didn't bother to save it.
I'm curious how much time & code it would take to implement this LLM stuff at a similar level of quality and performance.
A typical demonstration markov chain probably has a length of around 3. A typical recent LLM probably has more than three billion parameters. That's not precisely apppes to apples, but the LLM is certainly vastly more complicated.
Number of parameters is not the difference. A Markov chain can easily be a multi-dimensional matrix with millions of entries. The significant difference is that a length 3 Markov chain can only ever find connections between 3 adjacent symbols (words, usually). LLMs seem to be able to find and connect abstract concepts at a very long and variable distances in the input.
Nevertheless I agree with the premise of the posting. I used Markov chains recently to teach someone what a statistical model of language is, followed by explaining to them the perceptron, and then (hand waving a bit) explaining how many large, deep layers scales everything up massively.
The people I was instructing are not very technical, I had to hand-wave a lot. (Nevertheless I think they got a much better overview of the tech than they would have got by reading some pop-sci description.)
The overall structure is the same as in "use statistics to predict the next token."
With a Markov chain, the statistics are as simple as a mapping of n-grams to the number of times it appears in the corpus.
With a LLM, the statistics are the result of 50 years of research in neural network architectures, terabytes of training data, and many millions of dollars worth of hardware, along with the teams to build and manage all the data pipelines.
You can have very complex calculations and a simple output. The complexity of the process to find the weights is not necessarily the same complexity than the process using them. The numbers don't get suddenly special because of how they were calculated (like 42 is just the number 42 even after 7 million years of calculations).
The difference is the capabilities. LLMs don't necessarily need billions of Parameters. In fact, useful models (like the one used in never Apple devices' autocomplete) has only like 50 million. Markov chain... I guess there is probably a reason why we don't use them instead of neuronal networks. Maybe somebody more knowledgeable can enlighten us, but I suspect one might need magnitudes more parameters.
They are an especially useful tool right now, that might become less valuable as we get better at building LLMs. In principle the inner working of an LLM can be anything from a Markov-chain-like predictor to a beyond-human intelligence. Token prediction is the input/output format we chose, but you could communicate with a human in the same format and the human would show human-level intelligence.
What makes Markov chains such a great pedagogic tool right now is that they share (approximately) the same interface, being a token predictor, and that current LLMs are much closer to the capabilities of a fantastically good Markov chain than those of an above-human intelligence.
> In principle the inner working of an LLM can be anything from a Markov-chain-like predictor to a beyond-human intelligence.
I'm afraid I have to disagree. Next-token prediction isn't just the interface we use for LLMs, it is fundamentally what they are, to the very core. The training and loss function of the foundation models are completely oriented towards next-token accuracy.
Reasonable people can disagree about emergent behavior and if/how much the model is "planning ahead" in its weights (and what that could even mean) but it is emphatically not the case that the "next token" model is "just an interface". The analogy to human thought isn't accurate at all: we have our own recursive/iterative thought process, short and long term memory, decision making loops, etc.
A LLMs has no "thought" outside of next-token prediction and no working memory aside from its context window. We don't fully understand all the emergent behavior of a transformer model but we definitely understand exactly what's happening at the mechanical level: each token is determined, one at a time, by solving an extremely complex but deterministic equation in which the model weights are coefficients, and the output of which is a probability distribution over the next token.
There's no hidden intelligence or man behind the curtain. Whatever a LLM can do, next token prediction is how it does it.
>The training and loss function of the foundation models are completely oriented towards next-token accuracy.
This doesn't mean anything.
Loss function and training only concern themselves with the result of the prediction. The in-between, the computation, training does not care except as a means to an end.
It's not Input A > Output B.
It's Input A > Computation > Output B.
That Computation could quite literally be anything. And no, we do not automatically know what this computation might represent or if it even represents anything that would be understandable by us.
If you train a Transformer meticulously on predicting the token that is the result of an addition, you might hope the computation it learns is some algorithm for addition but you wouldn't actually know until you attempted to and successfully probed the model.
But in an LLM it is not an arbitrary computation. Very specifically, it is a single forward pass through a neural network.
Neural networks are very general function approximators so yes, there is some room for emergent behavior. But it could _not_ be "quite literally anything." It's plugging in values for a single (very big) equation.
I think we do ourselves a disservice by pretending it's more of a black box than it is.
How many passes it is irrelevant. You can perform any computation you like in a single pass if you have enough compute time.
Trained transformers have limited computer time per token so each query is compute limited, but this is trivially increased, by increasing tokens, or by increasing dimensions in the next training round so that each token permits more compute time.
A forward pass is not one big equation and I have no clue who you think it is. It's a series of computations, computations that depends on the query awaiting prediction. It's not even the same series of computations for each query because not all neurons are getting activated period and even when the same neurons get activated, they are not necessarily getting activated in the same way.
> You can perform any computation you like in a single pass if you have enough compute time.
You can't perform _any_ computation. A single forward pass through a neutral network can perform many classes of computation, and it can _approximate_ all... but that's not a guarantee that the approximation will be good (and there's classes for which the approximation is pretty much guaranteed to be bad).
You're right but I didn't say anything about guarantees since that wasn't really the point of the argument. Yes, you can guarantee nothing but the point of discussion was whether a forward pass would deny specific classes of computations simply because it was just a forward class. It won't.
First the discussion seemed to be about systems as implemented today (presumably you now concede that those actually do have practical computational limitations?) not systems that could theoretically be implemented. (Moreover adding memory is no longer the simple "forward pass" system that you were arguing had no significant computational limitations).
Second, and more importantly, the fact that through clever human manipulation you can express a Turing machine using an LLM does not mean that such a machine is learned through gradient descent training.
There is no basis to the claim that today's systems have converged on model weights that implement "higher-order" computation.
>First the discussion seemed to be about systems as implemented today (presumably you now concede that those actually do have practical computational limitations?)
You are not Turing complete. We do like to pat ourselves on the back and say, "Humans? Of course, they're Turing complete" but you're not. You do not have infinite memory either theoretically (all else fails, you'll die) or practically (boredom, lack of concentrating, lack of interest, and a memory that is very prone to making stuff up or discarding vital details at a disturbing frequency).
In fact, you are a very poor excuse for a Turing machine. Simulate any computation? You wish you could. Your brain is a finite state machine through and through.
So why do we continue to deceive and pat ourselves on the back ?
Because, well besides the dash of human exceptionalism and narcissism we're so well known for, limited =/ trivial.
You see, I don't really care how precisely Transformers meet some imaginary goal humans don't meet themselves.
It's not important how Turing complete transformers are, only that they could potentially learn any class of computations necessary via training.
>Moreover adding memory is no longer the simple "forward pass" system that you were arguing had no significant computational limitations
Memory or not, all the computation is still being performed just in the forward pass.
>Second, and more importantly, the fact that through clever human manipulation you can express a Turing machine using an LLM does not mean that such a machine is learned through gradient descent training.
It also doesn't mean it couldn't be.
>There is no basis to the claim that today's systems have converged on model weights that implement "higher-order" computation.
Results are basis enough. If I say, "you're intelligent", it's because you appear to be so. It's an assumption, not truth I've verified after peeking into your brain. All the properties I might ascribe to humans: 'intelligence', 'conciousness' are all assumptions I ascribe based on the results I see and nothing else. I have no proof you are performing any 'higher order computation' either.
There is a real difference between the computational power of different computing systems even if in practice nothing is really Turing complete because nothing is infinite. In practice there really is a difference between something that is DFA-like and something that is Turing-machine-like.
> It's not important how Turing complete transformers are, only that they could potentially learn any class of computations necessary via training.
There is no real argument for this and persuasive evidence against, as I linked to above.
> Memory or not, all the computation is still being performed just in the forward pass.
This was clearly not the meaning of "feed forward" in the discussion above (especially since no one was talking about transformers with memory because those aren't really in use).
> It also doesn't mean it couldn't be.
You were making claims about current systems which are false. Now you've switched from "it's present in current systems" to "we haven't theoretically ruled out that we could invent such a system one day" but there is no reason to believe even this claim is likely.
> I have no proof you are performing any 'higher order computation' either
Humans perform recursive computation when they count or add and probably when they form sentences.
Nothing I said about current systems is false. "It's one big equation" isn't an accurate description of a forward pass.
There's no theory barring what computation a forward pass can or can't do. That line doesn't exist.
I didn't switch to anything. You're just arguing something that was never being argued in the first place. Never did I mention anything about being Turing complete or having memory until you brought it up.
>Humans perform recursive computation when they count or add and probably when they form sentences.
Okay ?
GPT-4 can add. Anything it outputs gets fed back. The transformations of previous layers are used for latter ones. It can perform recursive computation just fine.
> Nothing I said about current systems is false. "It's one big equation" isn't an accurate description of a forward pass.
It is and presents limits as to what can be computed, as does gradient descent.
> There's no theory barring what computation a forward pass can or can't do. That line doesn't exist.
It does and I linked to a survey paper describing computational limits. The only sense that there are no limits is, as I said originally, is the same sense that a finite state machine has no limits.
> I didn't switch to anything. You're just arguing something that was never being argued in the first place. Never did I mention anything about being Turing complete or having memory until you brought it up.
Yes I brought up Turing machines to show that there are computational limitations to transformers (I didn't bring up memory, you did). Because that claim can't be refuted about the current widely-deployed systems you switched to talking about the fact that it hasn't been theoretically ruled out that we could design such systems in the future. If you didn't want to switch claims then you shouldn't have done it.
> GPT-4 can count and add. Anything it outputs gets fed back. It can perform recursive computation just fine.
It's a well known problem that it cannot consistently add arbitrary numbers. You are probably the only person who claims otherwise. As for feedback: This is obviously not part of the training process so can't be part of what is "learned".
>It's a well known problem that it cannot consistently add arbitrary numbers.
Neither can humans. Calculators aren't just for saving time. Humans regularly mess up arithmetic.
Can you add arbitrary numbers any better than GPT-4?. Test it out yourself.
>As for feedback: This is obviously not part of the training process so can't be part of what is "learned".
A token that is part of the process of an ongoing recursive computation in text being fed to a transformer is definitely part of training. Training directly incentivizes being recursive in token space.
Though it seems like there is some sensitivity around the comparison of LLMs to Markov chains, and certainly an LLM is not generated in the same way, it is pretty accurate that an LLM could be represented by a sufficiently (ie very) complex Markov chain. The states of the chain would not be the tokens themselves, as in this example, but the total context window vector of N input tokens, which would fan out to states consisting of the new context N[1:] + A, where A is any of the tokens sampled from the resulting probability distribution, and the transition probabilities are just drawn from that same distribution according to the temperature settings.
You could even do some very hand-wavy math on how staggeringly complex the resulting Markov chain would get: BERT for example has a token vocabulary of 30,000 and a context window of 512 tokens. So the number of possible states would be 30,000^512, or ~1.9 x 10^2292, with each of those having a max fan out to 30,000 other states. So clearly the LLM is a more compact representation of the concept.
It would be more accurate to say that a Markov chain is an example of a method that would perform relatively well at the same training task as a LLM.
So too, might a human trying to predict the next tokens.
But a human and a Markov chain are not the same underlying process to achieve next token prediction, and neither is the same underlying process as a LLM.
LLM are markov chains, a markov chain is a general concept and not just a text model technique. You must be thinking about the very simple markov chain models we had before where you just predicted the next word by looking up sentences with the same preceding words and picking a random of those words, that is also a markov chain just like LLM but a much simpler one, you are right LLMs aren't like that but they are still markov chains with the same kind of inputs and outputs as the old ones.
Isn't it though, if you consider the entire context to be part of the state? It seems like his argument is based on an assumption of the Markov model only using the current word as its state.
If we're broadening the scope of a Markov chain to consider the entire system as the current state that's being used to determine the next step of operation, then isn't literally every computer program a Markov chain under that definition?
You can't just include the memory of previous states which the current state is depending on as being part of the "current state" to fit the definition of a Markov chain without having broadened the scope to the point the definition becomes meaningless.
No, every computer program is not a Markov chain, because computer programs aren't random processes.
Look up the concepts of "higher-order Markov chains" or "Markov chains with memory".
Obviously, there are reasons that people don't directly implement LLMs as very high-order Markov chains. But it doesn't mean that the equivalence isn't mathematically or intuitively useful.
I'm just a non expert, but as far as I can tell, if there's an upper bound to the lookback in the context window, I don't see how that transformer isn't strictly less powerful than a Markov chain of that order. It's just a computationally tractable way to closely approximate it.
If the potential lookback distance is unbounded, then I think you could say that it's different from a finite-order Markov chain.
If you want a more in depth sense of why it's not, look at the following link that describes the transformer architecture in detail and specifically goes over moving from a Markov process to one that no longer satisfies it, specifically around the following paragraph:
> The first thing that becomes apparent is that, when trying to predict the word that comes after ran, we no longer look at just one line, but rather a whole set of them. We've moved out of the Markov realm now. Each row no longer represents the state of the sequence at a particular point. Instead, each row represents one of many features that may describe the sequence at a particular point. The combination of the most recent word with each of the words that came before makes for a collection of applicable rows, maybe a large collection. Because of this change in meaning, each value in the matrix no longer represents a probability, but rather a vote. Votes will be summed and compared to determine next word predictions.
The author made the choice to depart from a literally implementing a Markov model. That's a practical choice, but not strictly necessary if you're not worried about practicality. I think you're getting hung up on engineering decisions made to actually implement a language model, versus the theory.
In the same section, the author says:
> The difference between this second-order-with-skips and a full umpteenth-order model is that we discard most of the word order information and combinations of preceeeding words. What remains is still pretty powerful.
This implies that sure, you could hypothetically do an umpteenth-order model, but dropping down to something that approximates it "is still pretty powerful".
Thanks for the link, by the way! I'm definitely going to read through the whole thing. I'm desperately trying to understand this technology.
It's true that Markov chains are very limited in their capabilities. But one thing I love about them is that they are one of the simplest and most intuitive ways to write code that *learns* from input data.
If you're never written something that *learns*, try it out! Here's a very primitive one I wrote recently to explain the basic idea and explains it along the way.
Markov chains aren't lookup tables... Markov chains is the description of a process where you generate the next step by looking at preceding steps, that can be a lookup table but it can also be more complex like modern LLMs.
I have no idea if the author is aware, but it's worth noting why a Markov chain has the name and what the difference is from other probabilistic models. The Markov property states that the probability distribution of the next state in some system depends only upon the current state.
Obviously, language does not have this property and this has been known from the start, but Markov models are extremely computationally tractable, easy to implement, and easy to understand, while doing a good enough job. Introducing recursion and recurrent layers into multilayer neural architectures allowed explicit modeling of variable-length past context for the current state, which is a more accurate representation of how language works, but these were quite expensive to train. Transformer models introduced the attention mechanism to simulate recurrence without explicitly encoding it, reducing the training cost to make it tractable to train equivalently capable models with larger parameter sets on larger training sets, giving us the large language model.
This ability to explicitly capture variable-length context lookback is what makes things like few-shot and one-shot learning possible. The probability distribution is effectively self-modifying at inference time. It's not quite like an animal brain. There is no true plasticity with the strict separation between training and inference, but it gets a lot closer than a Markov model.
You can see in a lot of the comments here about use cases people had for Markov models where they shine. If you're making a bot intended to model one specific topical forum on a single web site, context variance is reduced compared to trying to converse with and understand arbitrary people in arbitrary situations. You're able to capture the relevant context based on how you select your training data. In contrast, current LLMs allow you to train on all text you can find anywhere and the model will perform well in any context.
I've seen Markov models mentioned a lot in these context, and my generous take has always been that something like stacked Markov models is meant. At each abstraction layer, the state is conditioned only by the previous abstract concept. At the lowest level the states would be the sequence of tokens; higher up it's concepts like turn of events in a plot. I don't think this often proposed idea of hierarchy is sufficient to describe LLMs or human cognition, but it strikes at some essence about parsimony, efficient representation, and local computation.
> This a scratch text area to test the autocomplete in another moment down would be four thousand miles i wish you know please ma am is this new zealand or conversations in another moment down stairs how funny it
^ to me it’s really a stretch that someone could read that and think “markov chains are practically an llm!”
They’re pretty limited, and everyone working on building LLMs knows about them and has probably used them at some point.
They both generate tokens/words on probabilities, but it’s hard to understate how much simpler of a probability model a Markov chain is compared to an llm.
You’ve stated that markov chains have a limited use as a simple chat bot. How do you improve an mc so that it can perform other tasks, like classification, summarization, question answering, complex text parsing, text matching, etc, etc?
The language modeling done in llms has an open pathway to scaling and improving on this statistical model, and it’s incredible to me that this is still opaque to people. I don’t believe that llms are a path to intelligence, but I can certainly recognize that they’re going to emerge as a sophisticated and very useful productivity tool.
> This is where I am right now. Want to go back to my roots. Some people work on old cars, even though they are less efficient. At the same time though, they are more fun to work on than new cars. I've decided to look into Markov chains.
Not sure there’s another side to your argument - we all agree :).
To the author: keep the faith and the excitement if you can, the actual applications of this technology (beyond chatbots) are just getting started.
Sure, LLMs are like 1024-gram Markov chains (or whatever the context limit is). But there are problems: 1) the transition matrix is far too huge to represent, and 2) it treats all pairs of 1024-grams as completely different, even if the first 1023 words are the same.
Function approximation solves both issues, and the Transformer is the best function clas we've found so far.
Markov chains are fun. I often use them when teaching a Python fundamentals course. You can create an implementation in around 100 lines of code that explores many features of the language: classes, functions, loops, dictionaries, and lists. Then, you can augment with tests, a command line app, typing, etc.
Markov Chains are cool stuff. Back in 2015 in one of my senior class projects, I built a haiku bot that would take a seed word and make a haiku from a corpus of Tweets I collected from the firehose API.
I forget now and can't find the code, but if I recall correctly, I had each tokenized word map to its syllables and used that in calculating the next word.
I wasn't able to get far enough to make each haiku make perfect grammatical sense, but it very often produced interesting results.
This is what I've been saying to people, LLMs aren't much smarter than a Markov Chain - a lot of twitter bots and earlier chat agents were driven by them.
What I do see though is the infrastructure around LLMs making a difference.
A LLM is a Markov chain with billions of associations and weights. A Makov chain is an LLM of maybe a few dozen associations and weights (so an LM, without the first L).
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.
“A human brain is just like a dog’s brain, only with more neural pathways.” True, perhaps, but largely pointless: at some point neural complexity results in a difference of kind, not of degree.
I’d argue the same is true of LLMs vs simpler models like Markov chains.
I think this vastly underplays animals intelligence though. There is so much focus on creating human level intelligence, but where is a robot that can learn to navigate the world like a dog or cat can?
That’s interesting you put the date at 2010! When I learned machine learning in ~2016-2018, markov chains were THE fundamental problem tool of NLP still. Neural networks were all the rage ofc, but still… could you tell me what tech/change you’re thinking of?
For example, I remember /r/SubredditSimulator blowing my mind, and I’m pretty sure that was markov chains
Yeah, my bad, I took a guess here, from what I remember about when neural networks became the hot buzzword (again, after the 1970's Perceptron ?) - sounds like I missed, since the transition was slower than I thought ?
P.S.: "2010" was probably from this great Ars Technica article :
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.
It's not just window size. It's the difference between syntax and semantics.
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.
I like: Intelligence is compressing information into irreducible representation.
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.
>high-dimensional latent-space embedding to a Markov model
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.
They’re doing highly specific tasks where the intelligence can come from the designer of the algorithm.
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.
SVD is used to implement lossy compression as does JPEG encoding... these algorithms are in no way intelligent.
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.
It's not. There's fundamental architectural differences that couldn't be bigger.
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.
> It's not. There's fundamental architectural differences that couldn't be bigger.
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).
This is the magical human intelligence/“AI has no soul” argument just presented in reverse. It totally ignores that human minds are emergent: no single part of your brain, nor it’s connection to the outside world are intelligent.
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.
LLMs are Markov chains in latent space, it's the latent representation that give them their power, but ultimately there's not as much difference as one would suspect.
Current LLMs are stateless as far as we know, their state when computing a new token is only the preceding text tokens, they don't store any metadata or save state from the previous calculations.
Fair, but maybe it's more of a computer science-cy type of comparison?
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).
I think it would take some spectacularly bad engineering to be that wasteful. It would need to be so inefficient that getting ChatGPT to write the code won't be bad enough.
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.
The big difference is the "deep" in "deep learning".
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).
>This is what I've been saying to people, LLMs aren't much smarter than a Markov Chain
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).
The whole point of Transformers is that they broke the Markov assumption (i.e., that the next token probability is strictly conditioned on a window of N preceding tokens).
That's not actually true, they still have a fixed history window. The idea that transformers capture through the attention mechanism is that not all past tokens are created equal, and that the importance of tokens in that history window depends on what they are.
They also scale differently - Markov Chains scale exponentially with the size of the window, while transformers scale quadratically. So in fact transformers are really more exponentially more efficient, though without bound on resources their capabilities are a strict subset of that of Markov chain.
Markov chains are defined in terms of states, which are not necessarily the same as tokens.
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.
> Markov chains are defined in terms of states, which are not necessarily the same as tokens.
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…
Yeah, and Markov chains aren't much smarter than... matrix multiplication. A lot of stuff have been built with it, but these pesky c++ libs like lapack — such a bother to use! Imagine a world where a good infrastructure have been built around it — matrix multiplication certainly would be a blast!
Markov chains were one of the coolest discoveries of my programming career and I spent years using them to make forum and social media bots trained on people’s post histories for them.
I think that experience is part of why I’ve been generally unimpressed with a lot of LLM hype. Like yeah, it’s cool and definitely more useful than a markov chain - but for the amount of resources that went into it I’d expect the gap to be quite a bit larger than it really is.
I also loved when I found about Markov chains and had a lot of fun playing with them, but have a totally different view on the gap with respect to LLMs.
Markov chains were discovered in 1906. Since then until a few years ago, advances on "building a better Markov chain" have been modest (e.g. smoothing techniques).
Enter the last 5 years, LLMs come and now you have an "uber Markov chain" that actually generates perfect syntactically coherent text, you can even ask it things and if the question is well-posed and makes sense you will get a true answer at least the majority of the time, they can be a daily tool (for practical purposes, beyond fun), help you solve problems and write interesting creative stories. A much larger leap in those 5 years than in the previous century!
I see them as what I always dreamed Markov chains to be, but they couldn't be. The gap is huge.
> I think that experience is part of why I’ve been generally unimpressed with a lot of LLM hype.
There are fundamental scale & architectural differences that make LLMs different from Markov Chains: It's like saying that you're not impressed by indoor plumbing because you have experience carrying your water from a well, and that both do the same thing - transporting water to your home.
In both cases, this line of logic ignores the improvements made to make such a thing remotely possible, and the difference in relative usefulness that can be gained from LLMs in comparison to Markov Chains.
I first learned about Markov chains in the late 90s when I ran across a Markov chain bot on IRC. The person who wrote it was nice and answered my questions about it. I managed to write my own shitty copy but was pleased enough with myself. Same as you I thought it was one of the coolest things I came across in programming.
Also same as you why I've been very cool to LLM hype. Not that LLMs aren't feats of their own but they're not nearly as smart as their hype suggests.
Gap between GPT-4 and Markov Chains is huge though. Even gap between GPT-4 and GPT-3.5 seems obviously huge to me in terms of what they are able to do.
LLM with temperature 0 will always return the same output for the same input.
Considering this, LLMs are Markov Chains, its just the output sequence as a whole can be considered as an element and whole context can be considered as "one previous element".
So, the whole block of the text on input is previous element, and whole block of the text on the output is the next element.
If we let Markov model mean a probability distribution over a sequence defined as P[ X(t) | X(t-1) ] , then a transformer is specifically not a Markov model. The Markov property means each element is conditional on only the previous element ("context length" = 1).
A discrete table based probability distribution over possible words, as in the link, is a Markov language model, but not a meaningful contestant among Markov models for language modelling. The latest contestants here are things like RWKV, ResNet, SSMs, and so on which might be better thought of as HMMs.
An HMM is a Markov chain of hidden ("latent") states, rather than over tokens or words. Variations have been used for speech recognition and language modelling for 20-30 years.
My favorite intro is https://norvig.com/ngrams/ because it shows a variety of applications using simple code. (and uh since I'm in the acknowledgements, ok.)
(The people saying modern LLMs are just fancy Markov chains in practice are being silly, though.)
Claude Shannon showed you could use n-grams to represent language. Then Chomsky invented automata / formal languages theory to show why it couldn’t work.
IIRC transformers are at the very bottom of the Chomsky hierarchy, and yet they are clearly able to master English grammar.
You didn't answer my question. I didn't ask you whether planes flew like birds do. I asked you if planes are "mimicking" flight and if that's a statement that makes any sense at all.
> Bats don't fly like either bees or birds. all these damn mimics running around.
Yes, penguins don't swim like sardines either and snakes don't "walk" like apes.
> Why is the bird privileged here ?
There is no privilege, I was just using it as an example to illustrate that what human beings do is different from what LLMs do, even though they are all called "intelligence".
Great. And the point is..who cares what humans do ? We’re not the arbiter of intelligence anymore than birds are the arbiter of flight.
Nobody is trying to build a digital human here so, “they’re not doing what humans do” is about as meaningless as it gets.
I mean sure, you could cook up whatever definition of intelligence you like, make it so that humans are the only things that pass just because. Then, what's the point? It's not a useful definition.
That’s one point but really there’s more. If you say “mimicking intelligence” is a real meaningful difference, then it should be testable. “There’s a difference here. You can’t see it in the results but trust me bro, it’s there” is really not an argument.
Well scientists do. If your to listen to talks from Yan Lecun & Geoff Hinton or Chomsky. They do care and the do want to figure it out.
> Nobody is trying to build a digital human here so, “they’re not doing what humans do” is about as meaningless as it gets.
Actually alot of AI researchers are trying todo this. It's just that we haven't yet made any significant strides in the
field. It is no coincidence that neural networks are loosely inspired by nature.
The original goal of AI research was to create a "thinkin machine" with intelligence equivalent to that of a human being.
The value of scientific insights & industrial applications this would make possible are obvious.
There haven't been any significant breakthroughs in AI comparable to human intelligence.
Industry has simply taken up auxiliary research for applications. But the core scientific goal has not yet been achieved.
>I mean sure, you could cook up whatever definition of intelligence you like, make it so that humans are the only things that pass just because. Then, what's the point? It's not a useful definition
Intelligence is a very wide spectrum. Computers, calculators, do have something that can be classified as a form of intelligence. But it is more important to understand what they are not, i.e intelligence fully that satisfies what humans are capable of.
I mean if someone says they "do drugs".
What do they mean? The drink coffee, tea, smoke tobacco, codine, weed or heroin. A pharmacist a law enforcement person, and a highschool kid will have very different classifications on what a drug really is.
That is why we need to "cook up definitions" so that we know exactly what someone is talking about. There is no word for "human specific intelligence"
>The original goal of AI research was to create a "thinkin machine" with intelligence equivalent to that of a human being.
And the wright brothers sought to create a flying machine equivalent to that of a bird. They studied birds too.
That doesn't mean they wouldn't have taken, "but but it has no feathers, it doesn't flap !!. It's only pretend flying" with anything more than a laugh to your face.
People are trying to build intelligence equivalent to a human being, not a human being.
Feel free to step out of the discussion anytime you like. That said, I don't think I'm putting words in your mouth. That was simply an analogy for the kind of arguments I feel you're making.
Ultimately, results are what people care about. "Have they truly mastered x or are they 'mimicking' it?" is a philosophical discussion.
Results are the only means you determine something has one property or another. I'm only assuming I'm speaking to an intelligent human on the other end of this discussion. I'm only assuming you are 'conscious'. I have no idea if these things are 'really' true. If I say, 'you're mimicking my intelligence. You're not really intelligent', what proof could you bring to show otherwise that wouldn't just fall back on results? None.
We haven't made machines that replace animals. A submarine can't do quick precision movement to pick up tiny objects like a fish, a plane can't do quick precision movement to fly through a forest and land gracefully on a branch like a bird.
The current machine intelligence is still clumsy like that, it can solve some problems but it is still far from the real thing.
Someone wrote a Markov chaining bot back on LambdaMOO in the early 90s, that would pretend to participate in conversation in the room, and I remember being blown away by it. Especially in the context of the limited computation power on that platform and the machine it was hosted on.
I resource I found invaluable in demystifying LLM's was Andrej Karpathy's Youtube series. In particular, his "Makemore" video built a basic LLM in the same vein as OP's.
It's long (2h), but well worth the time if anyone is curious about the technical workings of LLMs.
I agree! I'm a undergrad and I used Markov chains to explain how I'm able to predict what my colleagues are going to say! (BTW I'm a chess player so that's how I know what it is :)
> Since there is a 25% probability Alice is at the grocery store, we multiply that with the probility of her transitioning to the Planetarium: 25% ∗ 75%
In 2016 I created a Twitter bot that replicated a political activist via a Markov chain model. It was impressive how many people liked those post, also a middle level politician.
Back around 2002 we built an IRC bot that logged everything in a channel, built up a frequency table of which word follows what word and then randomly would spew out some text using a random walk of the frequency tables and had some logic for when to stop (I think probability increased with sentence length).
Sometimes it came up with very funny stuff, but mostly non-sense.
Many people try to "explain" LLMs starting with the principles of neural networks. This rarely works well: there are some significant conceptual leaps required.
However, explaining that a LLMs are really just iterated next-word prediction based on a statistical model of the preceding words is something that most people can grok, and in a useful way: in my experience, it actually helps give people a useful intuition for why and how models hallucinate and what kind of things they're good/bad at.
Markov chains are super simple iterated next-word prediction model, and can be explained in 15 minutes. It's a great way to explain LLMs to laypeople.