10 ms·

Decoder only LLMs are Markov chains with sophisticated models of the state space. Anyone familiar with Hamiltonian Markov Chains will know that for good results

Decoder only LLMs are Markov chains with sophisticated models of the state space. Anyone familiar with Hamiltonian Markov Chains will know that for good results you need a warm up period so that you're sampling from the typical set which is the area with generally the highest probability density in the distribution (not necessary the high propbability/maximum likelihood). I have spent a lot of time experimenting with Chain of Thought professionally and I have yet to see any evidence to suggest that what's happening with CoT is any more (or less) than this. If you let the model run a bit longer it enters a region close to the typical set and when it's ready to answer you have a high probability of getting a good answer. There's absolutely no "reasoning" going on here, except that some times sampling from the typical set near the region of your answer is going to look very similar to how human reason before coming up with an answer.

4b11b4 11mo ago
I wish it got called "scaffolding" instead
- eru 11mo ago
  When you adopt the probability distribution point of view, this is often called 'burn-in'. See eg the usage in https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_al...
- xwolfi 11mo ago
  That sounds a lot like bad marketing. Chain of thoughts is better, it makes you think the thing is thinking !
dhampi 11mo ago
I don't understand the analogy. If I'm using an MCMC algorithm to sample a probability distribution, I need to wait for my Markov chain to converge to a stationary distribution before sampling, sure. But in no way is 'a good answer' a stationary state in the LLM Markov chain. If I continue running next-token prediction, I'm not going to start looping.
- crystal_revenge 11mo ago
  I think you're confusing the sampling process and the convergence of those samples with the warmup process (also called 'burn-in') in HMC. When doing HMC MCMC we typically don't start sampling right away (or, more precisely we throw out those samples) because we may be initializing the sampler in a part of the distribution that involves pretty low probability density. After the chain has run awhile it tends to end up sampling from the typical set which, especially in high dimensional distribution, tends to more correctly represent the distribution we actually want to integrate over. So for language when I say "Bob has three apples, Jane gives him four and Judy takes two how many apples does Bob have" we're actually pretty far from the part of the linguistic manifold where the correct answer is likely to be. As the chain wanders this space it's getting closer until it finally statistically follow the path "this answer is..." and when it's sampling from this path it's in a much more likely neighborhood of the correct answer. That is, after wandering a bit, more and more of the possible paths are closer to where the actual answer lies than they would be if we had just forced the model to choose early. edit: Michael Betancourt has great introduction to HMC which covers warm-up and the typical set https://arxiv.org/pdf/1701.02434 https://arxiv.org/pdf/1701.02434 (he has a ton more content that dives much more deeply into the specifics)
  - dhampi 11mo ago
    No, I still don’t understand the analogy. All of this burn-in stuff is designed to get your Markov chain to forget where it started. But I don’t want to get from “how many apples does Bob have?” to a state where Bob and the apples are forgotten. I want to remember that state, and I probably want to stay close to it — not far away in the “typical set” of all language. Are you implicitly conditioning the probability distribution or otherwise somehow cutting the manifold down? Then the analogy would be plausible to me, but I don’t understand what conditioning we’re doing and how the LLM respects that. Or are you claiming that we want to travel to the “closest” high probability region somehow? So we’re not really doing burn-in but something a little more delicate?
    - igorkraw 11mo ago
pcwelder 11mo ago
In RNNs and Transformers we obtain probability distribution of target variable directly and sample using methods like top-k or temprature sampling. I don't see the equivalence to MCMC. It's not like we have a complex probability function that we are trying to sample from using a chain. It's just logistic regression at each step.
- crystal_revenge 11mo ago
  Right, you're describing sampling a single token which is equivalent to sampling from one step in the Markov Chain. When generating output you're repeating this process and updating your state sequentially which is the definition of the Markov Chain since at each state the embedding (which represents our current state) is conditionally independent of the past. Every response from an LLM is essentially the sampling of a Markov chain.
coldtea 11mo ago
How does MC warm-up fit with LLMs? With LLMs you start with a prompt, so I don't see how "warm up" applies. You're not just sampling from them like some MC cases. > If you let the model run a bit longer it enters a region close to the typical set and when it's ready to answer you have a high probability of getting a good answer. What does "let the model run a bit longer" even mean in this context?
- emil-lp 11mo ago
  The way almost all modern LLMs work is by starting with a "thinking" phase which is explicitly not part of the output. You let that process run longer.

4b11b4 11mo ago

I wish it got called "scaffolding" instead

eru 11mo ago
When you adopt the probability distribution point of view, this is often called 'burn-in'. See eg the usage in https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_al...
xwolfi 11mo ago
That sounds a lot like bad marketing. Chain of thoughts is better, it makes you think the thing is thinking !

dhampi 11mo ago

I don't understand the analogy. If I'm using an MCMC algorithm to sample a probability distribution, I need to wait for my Markov chain to converge to a stationary distribution before sampling, sure. But in no way is 'a good answer' a stationary state in the LLM Markov chain. If I continue running next-token prediction, I'm not going to start looping.

crystal_revenge 11mo ago
I think you're confusing the sampling process and the convergence of those samples with the warmup process (also called 'burn-in') in HMC. When doing HMC MCMC we typically don't start sampling right away (or, more precisely we throw out those samples) because we may be initializing the sampler in a part of the distribution that involves pretty low probability density. After the chain has run awhile it tends to end up sampling from the typical set which, especially in high dimensional distribution, tends to more correctly represent the distribution we actually want to integrate over. So for language when I say "Bob has three apples, Jane gives him four and Judy takes two how many apples does Bob have" we're actually pretty far from the part of the linguistic manifold where the correct answer is likely to be. As the chain wanders this space it's getting closer until it finally statistically follow the path "this answer is..." and when it's sampling from this path it's in a much more likely neighborhood of the correct answer. That is, after wandering a bit, more and more of the possible paths are closer to where the actual answer lies than they would be if we had just forced the model to choose early. edit: Michael Betancourt has great introduction to HMC which covers warm-up and the typical set https://arxiv.org/pdf/1701.02434 https://arxiv.org/pdf/1701.02434 (he has a ton more content that dives much more deeply into the specifics)
- dhampi 11mo ago
  No, I still don’t understand the analogy. All of this burn-in stuff is designed to get your Markov chain to forget where it started. But I don’t want to get from “how many apples does Bob have?” to a state where Bob and the apples are forgotten. I want to remember that state, and I probably want to stay close to it — not far away in the “typical set” of all language. Are you implicitly conditioning the probability distribution or otherwise somehow cutting the manifold down? Then the analogy would be plausible to me, but I don’t understand what conditioning we’re doing and how the LLM respects that. Or are you claiming that we want to travel to the “closest” high probability region somehow? So we’re not really doing burn-in but something a little more delicate?
  - igorkraw 11mo ago

pcwelder 11mo ago

In RNNs and Transformers we obtain probability distribution of target variable directly and sample using methods like top-k or temprature sampling. I don't see the equivalence to MCMC. It's not like we have a complex probability function that we are trying to sample from using a chain. It's just logistic regression at each step.

crystal_revenge 11mo ago
Right, you're describing sampling a single token which is equivalent to sampling from one step in the Markov Chain. When generating output you're repeating this process and updating your state sequentially which is the definition of the Markov Chain since at each state the embedding (which represents our current state) is conditionally independent of the past. Every response from an LLM is essentially the sampling of a Markov chain.

coldtea 11mo ago

How does MC warm-up fit with LLMs? With LLMs you start with a prompt, so I don't see how "warm up" applies. You're not just sampling from them like some MC cases. > If you let the model run a bit longer it enters a region close to the typical set and when it's ready to answer you have a high probability of getting a good answer. What does "let the model run a bit longer" even mean in this context?

emil-lp 11mo ago
The way almost all modern LLMs work is by starting with a "thinking" phase which is explicitly not part of the output. You let that process run longer.