Markov Chains are the Original Language Models
elijahpotter.dev
elijahpotter.dev
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.
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.
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.
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.
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.
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'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).
"Transformers are not Turing complete" https://www.lifeiscomputation.com/transformers-are-not-turin...
See here for example for a survey of work on the limits of computational expressivity of transformers https://www.semanticscholar.org/paper/Transformers-as-Recogn...
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.
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.
> 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.
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.
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".
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.
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.
So yes, much more complicated.
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.
I'm curious how much time & code it would take to implement this LLM stuff at a similar level of quality and performance.
Then all of the complexity comes with the training/weight data.
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].
[1] Earlier comment on why I think it's dubious to call LLM-based products such as ChatGPT "mere LMs": https://news.ycombinator.com/item?id=35472089
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.
https://github.com/facebookresearch/llama/blob/main/llama/ge...
The engineering feats are up there with anything, but it’s a next token predictor.
Now, how exactly the LLM is computing this prediction remains poorly understood.
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.
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?
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.
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.
not everything done via SGD is a ReLU :)
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."
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.
It is. You need to go multi-dimensional; that's where "intelligence" emerges.
In fact, HMMs are discrete shallow state-space models.
I believe S4 and successors might become serious contenders to transformers.
For a detailed tutorial, see https://srush.github.io/annotated-s4
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.
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.
A blog post of you want to read more:
https://medium.com/@andrew_johnson_4/are-transformers-markov...
https://safjan.com/understanding-differences-gpt-transformer...
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.
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.
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.
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.
https://github.com/unoti/markov-basics/blob/main/markov-basi...
This starts with generating US city names, and ends with generating text based on the Dungeons and Dragons DM guide.
Linear regression is significantly simpler and also learns from input data.
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.
^ 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.
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.
Function approximation solves both issues, and the Transformer is the best function clas we've found so far.
You can contact me on my website https://metasnake.com
I wasn't able to get far enough to make each haiku make perfect grammatical sense, but it very often produced interesting results.
What I do see though is the infrastructure around LLMs making a difference.
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).
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.
"Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens"
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.
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 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.
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.
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.
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.
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.
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.
I’d argue the same is true of LLMs vs simpler models like Markov chains.
There's a qualitative difference too.
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).
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…
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.
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.
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.
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.
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.
Isn't it?
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.
https://colab.research.google.com/github/norvig/pytudes/blob...
(The people saying modern LLMs are just fancy Markov chains in practice are being silly, though.)
IIRC transformers are at the very bottom of the Chomsky hierarchy, and yet they are clearly able to master English grammar.
What gives?
Do Submarines swim like fish?
The current machine intelligence is still clumsy like that, it can solve some problems but it is still far from the real thing.
They are go up in the air like birds but what they are doing to get up & be up in the sky is very different.
Just like LLMs, planes are way less energy efficient than birds. Just like how Human brains are way more efficient than Convents & LLMs
If you mean something projecting itself into the air, then yes. Rockets fly, Kites fly, bullets fly, planes too fly.
But if by flight you mean replicating what birds do to get into the sky & come down. Rockets, Kites, bullets & planes don't do that.
Is a bee "mimicking" flight too ? Does that make any sense ? Why is the bird privileged here ?
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".
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"
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.
So, I don't think I can benefit you by continuing this discussion.
Thanks for talking though.
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.
Orange Duck has an implementation of a Markov chain in 17 lines of Python. [0]
Also, for a lab we've used Markov Chains to create 'music'. The results were terrible, but the exercise was good.
It's long (2h), but well worth the time if anyone is curious about the technical workings of LLMs.
https://www.youtube.com/watch?v=PaCmpygFfXo&list=PLAqhIrjkxb...
https://en.wikipedia.org/wiki/Markov_chain#/media/File:Marko...
> 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%
Shouldn't this be 25% * 70%?
-----
I'd rather do 0.25 * 0.75
classic
Sometimes it came up with very funny stuff, but mostly non-sense.