Large Language Models as Markov Chains
arxiv.org
arxiv.org
The paper seems to be more about the stationary distributions of such Markov chains.
The paper mentions this explicitly:
For GPT-3 (Brown et al., 2020), this represents 5 × 10^11 training tokens, which pales in comparison with the number of non-zero elements in Qf, given by T^K+1 ≈ 10^9632.
There's in principle no reason why such can't have arbitrary (but not infinite) range dependencies. The major difference is that these Markov Chains can be too huge to compute and don't have a feasible training algorithm.
A system being a Markov chain doesn't say anything more about the function mapping inputs to states than that the function has no memory and has access to the full state that affects the transition probabilities to the next state.
What do you mean? Quantum states over time are very much markov chains as well.
> It's simply a (slightly unusual) modelling choice which you can use whenever you've listed all possible inputs that can affect a transition probability
That has nothing to do with markov chains, do you mean a specific implementation? Markov chains is a probability theory concept and has nothing to do with any implementation.
It applies here too in a case where the model interacts with humans, as the LLM state doesn't include the human.
While Markov chains/processes are a powerful and general abstraction, the assumptions are quite strict. E.g. even the simplest recurrent systems aren't Markov, and this leads to things like having to assume exponential distribition of event durations in time series contexts, which is quite limiting.
In language models it draws a clear demarkation between recurrent and feedforward neural networks and brings some crucial understanding into benefits and limitations of e.g. transformers vs recurrent models.
It has to be stated, since so many even here on HN believes that LLM aren't markov chains since they misunderstand basics like this.
This feels like saying "it's just if statements". So yeah, but also thats a terrible mental model for how to use them.
It's mathematically well understood and very poweful abstraction which is lost if they're thought only as the simple toy language model.
Or of attention?
The term is being tortured beyond endurance by being forced to describe what LLMs do.
It is a different level of analysis than neural network architecture and covers a very wide types of models. The Markov chain structure of a model allows for some kinds of understanding of behavior of the models fulfilling its assumptions, e.g. finite range of dependencies, existence of a stationary distribution and crucially for transformer-type architectures that they can be trained in a purely parallel manner.
If an algorithm employing 8 billion parameters addressed by a context that is itself cross-linked with a key-value store qualifies as "memoryless" enough to be a Markov model, does the term have any meaning at all? You could argue that it's memoryless because the embeddings aren't modified on the fly based on the user's input, I suppose.
My point is that describing a toy Markov text generator with the same terms that you apply to GPT3.5 is, even if technically accurate, no more meaningful than using the term "Turing machine" to describe a C-64 and a Cray.
This is as opposed to an RNN, which has an internal state.
Likewise the context window of an LLM can be considered a state with some number of bits. It's just more explicit in an LLM's architecture vs. a RNN's runtime that the number of bits is finite.
What if we used the term "computer"?
And anthropomorphise the machines? ;)
> The problem I have is that anything deterministic can be described as Markovian.
Markov processes aren't even necessarily deterministic. See Hidden Markov models (https://en.wikipedia.org/wiki/Hidden_Markov_model) and POMDPs (https://en.wikipedia.org/wiki/Partially_observable_Markov_de...).
No it isn't, this is exactly the kind of process that Markov chains describe. They describe a stateless probability function that you chain over and over to produce a sequence of results, exactly like what an LLM does, they predict the next token based on precious tokens repeatedly to produce text.
There is no bending of any concepts here, anyone who studied a higher level math probability course will instantly recognize LLMs as a markov chain. It is common for markov chains to have infinite number of states, like a real position, and then moving randomly from there. You can model particles in a gas like that.
What agenda? Knowing that LLM's are markov chains helps me understand and makes me better at using them, since I know every word is just calculated probabilistically based on the previous N words, the fastest way to describe that is to say it is a Markov chain. This makes it hard for them to coordinate their early words with things that will happen later, all that from just knowing it is a Markov chain.
I feel the knee jerk rejection of this statement is more of an agenda, why do you feel it is so wrong to say it is a Markov chain? Are you sure there is no agenda behind those feelings?
I don't think "Markov chain" is a useful description despite agreeing it's an accurate one, simply because I have a preference for applied maths over pure maths and a full transition table version would be obscenely large.
In this, it's also technically accurate to say that a perceptron network with one hidden layer can approximate any function: technically yes, but not in any practical sense.
But if you're working in the pure maths domain, knowing that it can in principle be one, means you can apply any tools that only work on Markov chains. Given what else I've seen mathematicians do, I won't be surprised if pure maths researchers can get useful results even though the transition matrix is literally too large to fit into our universe without collapsing it into a black hole — it would hardly be the first time I've even seen mathematicians talking about quantities that large.
But the context length is around what a human goes through in a day so it can feel like it, and they can use tools such as databases to make direct record of "important" things, and fine-tuning on sessions is also already possible.
I'm going to ignore "proper" continuous learning until that actually gets into the big-name models, because although there's plenty of "first 90%" tech demos, the Tesla FSD is also at that point and yet the cars today still come with steering wheels. Meanwhile, here's the research SOTA: https://github.com/Wang-ML-Lab/llm-continual-learning-survey
Ironically, continuously updating a Markov chain is easy, given how small most of them are in practice. But a Markov chain large enough to act like an LLM would collapse into a black hole 7x10^32 times larger than the universe*, so that's kinda hard to update.
* assuming the algebra was correct: http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000...
Edit: I made at least two errors with that algebra, one of which was a typo; I now think it's 4.2x10^4750 universe diameters…
…unless there's another error I missed: http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000...
You mean a full state table Markov Chain? Markov chains doesn't need to have all states in a table, it just needs to be a function, a table is one implementation of a function but anything can do.
Although my understanding is that under quantum mechanics it's necessary to set the probability of all transitions between states to a number larger than zero, I also understand that for practical purposes the probability for the overwhelming majority of transitions are close enough to zero as to require fancy notation (at the very least, nested exponentiation) to express quite how unlikely they are.
The same basic idea can be found everywhere in mathematics and CS. Once you have chosen the value for your parameter, I can choose the value for my parameter to guarantee the desired outcome.
After all, in the same sense I can also make a Markov chain that reproduces the behaviour of any human, or even any Turing machine with finite tape — it's just that a computer with 1 GB of memory (all kinds including non-volatile) has 2^(8*(10^30)) states.
At most the Berkenstein bound for the mass of a human brain.
Is that big? Yes, too huge to bother calculating. That's why I'm using it as an example to say "it's a Markov chain" is not helpful.
But it is finite, and that means it's mathematically equivalent.
And that's before the thing about transition matrices being (in general if not in particular) square, from any one state to any other.
For fun, here's the Berkenstein bound for the equivalent transition matrix for the much smaller GPT-3 with 2048 context length, measured in (amongst other things) multiples of the size of the universe: http://www.wolframalpha.com/input/?i=sqrt%2812%2A%28%2850000...
(Assuming I didn't fluff the algebra).
Edit: I fluffed the agebra, see if you can spot the typo. It's much much bigger.
Of all the things I've heard people being dismissive of, you're the first I've heard suggest it might possibly be more than trivial to create a map from physical objects to some enumeration.
It's not like simulated physics is somehow a novel field I've had to invent in my head, it's a field that's been performing such mappings, even for quantum systems (on smaller scales than a brain, but you yourself say "I don't care if it's practical or not") for decades already.
In extremis, the Bekenstein bound, you've got a surface which — at a resolution of (IIRC) 2π bits per square Planck area — contains all the information about the interior. There's a lot of ways to map the surface of a sphere into Planck areas, pick any you want. That ordering itself defines a state down to the quantum level.
There's in the order of 10^17 of those Planck areas if a human brain was compressed into a black hole, so that's the maximum information content of any given possible arrangement of matter and energy with the mass of a human brain.
The only thing I'm struggling with right now is why you might be so confident that this is difficult that you're even thinking to try and make an example out of me?
Dude, I've written several Markov chains, starting aged something like six while still learning to read. (Family had a Commodore 64, one of the books it came with had one as a coding example).
Markov chains are stochastic processes where the transitions between possible nodes have probabilities depending only on the current node, i.e. history is irrelevant.
So, right back'atcha, if you can't see how what I wrote is a proof of equivalence — you've got a way to map reality (of a human brain) onto a number between 0 and ~2^(10^17)*.
Or perhaps, despite your previous question being answered, your actual issue is that you were unaware that the laws of quantum mechanics give you a stochastic processes where the transitions between possible states have probabilities depending only on the current state?
* exponent times whatever the constant of proportionality is
∃, ∎
False.
I've given you the state space. It's the one defined by 2^(k*10^17) bits. That's your state space. I don't know why you have a hard time with this concept, it doesn't seem particularly challenging to me.
I've also said, in what I thought was quite clear language, that writing down the transition probabilities for even a system significantly simpler than a human brain would require so much information that by the Bekenstein bound it would require a universe substantially larger than this one to avoid becoming a black hole.
If you're not going to accept that the very specific things you asked for — things which you seem to accept exist — are already sufficient to be proof that quantum mechanics and by extension all of reality including humans are in the set of things defined by Markov chains unless I literally destroy the universe by writing the function down in that fashion, then we're done.
Or are you shifting the goal posts when you wrote this?:
> and the unitary operator that corresponds to your daily activities in terms of a Markov chain
Given that what actually fits into a comment box is either a super-high-level representation where it's transitions at a macro level like "sleep" -> "get up" -> "go to work" etc. or a super-low-level representation like iħ ∂ψ/∂t |ψ> = (H^)|ψ>
In my college classes, sometimes we'd get problems involving "construct a markov chain to model this process". Doing the naive, obvious solution wouldn't make the probabilities work because we'd "forget" crucial information, so we'd just add on extra bits to the state (e.g. "flag1 flag2 flag3 ...") that would make the number of nodes exponentially larger.
But the infinite information part of markov chains is really helpful sometimes too, e.g. the position of your random walk wouldn't be encoded in your "state" (which could be infinite), it'd just be returned as a value (if you were trying to compute the distance from the origin or something).
Are you guys just arguing over "at what point does this shoving a billion bits into my state make it not really a 'markov' chain like you'd traditionally think about it"? Basically the formal definition vs what we intuitively think about as the 'point' of markov processes and why the markov observation is important?
That's an accurate description of my perception of the conversation, I can't speak for the others of course.
This has been argued as a theoretical(but larger than the universe) model in philosophy for long enough that I wouldn't be surprised if it predates the notion of creating a machine intelligence.
Without any mechanism for generalisation, it can be argued that it is simply a record of an intelligence with the actual mind being whatever created the table
I guess you can think of Markov chains as a form of that table shrunk down to a hash table of the input storing only a set of the most probable outputs for any collisions.
With the right semantic hashing you could consider it analogous to a LLM, but I feel there's a lot leaning on the term 'semantic hashing', because that's where the magic is in the LLM.