PTLearning

Markov chains and MCMC

Random walks that forget their past, and how to design one that spends its time in proportion to any distribution you want. Behind recent methods that sample better answers from a base model without any training.

Basics used here
Key idea
Markov chains, stationary distributions, Metropolis–Hastings, power distributions, and sequential Monte Carlo
Real world
A tourist wanders a city, at each corner picking a street at random. After a long afternoon, the fraction of time spent in each square no longer depends on where they started; busy hubs get visited most. Design the rules for picking streets, and you control those fractions.
In an LLM
Low-temperature decoding sharpens each token choice, but that isn't the same as favouring the most likely whole answers. A Markov chain that proposes rewrites of an answer and accepts or rejects them can sample from the sharpened distribution over whole answers, and recent work finds that this alone lifts a base model's reasoning scores close to those of RL-trained models.

Markov chains

A Markov chain is a random process where the next state depends only on the current state, not on how you got there. "Memoryless" is the key word.

  • Weather modelled as: tomorrow depends only on today.
  • A board game: your next square depends only on your current square and the dice.
  • A language model is a Markov chain if the state is the whole text so far: the next token depends only on that. (With the state being only the last token, it isn't; that was the old n-gram model.)

Many chains settle into a stationary distribution: after enough steps, the chance of being in each state stops changing, whatever the starting point. That long-run distribution is what makes chains useful for sampling.

example · a city walk

At each corner the tourist picks one of the connecting streets at random. Run the walk for hours: big squares with many streets get visited far more than dead ends, in fixed proportions. Google's original PageRank was exactly this: a random web surfer's long-run share of time on each page.

example · rewriting an answer

State: a complete answer to a maths question. Step: pick a random position, throw away everything after it, and let the model rewrite the rest. This defines a Markov chain over answers. On its own, its long-run distribution is just the model's own distribution. Add an accept/reject rule and you can make it favour whatever you want.

MCMC: designing the chain

Markov chain Monte Carlo (MCMC) builds a chain whose stationary distribution is a target π\pi you choose. You only need to be able to compute π\pi up to a constant. The classic recipe, Metropolis–Hastings:

  1. From the current state xx, propose a new state x′x' from some proposal q(x′∣x)q(x' \mid x).
  2. Accept the move with the probability below; otherwise stay at xx.
min⁡(1, π(x′) q(x∣x′)π(x) q(x′∣x))\min\Big(1,\ \frac{\pi(x')\, q(x \mid x')}{\pi(x)\, q(x' \mid x)}\Big)

The ratio means you never need the normalising constant, which is often impossible to compute. The catch: successive samples are correlated, and you must run the chain long enough to forget its start ("burn-in" or "mixing").

Sharpening whole answers

Here's why this matters for LLMs. Say you want the model's answers, but sharpened towards its most confident ones. Two very different things go by that description:

  • Low temperature: sharpen every token's distribution separately, which is easy and is what decoding does.
  • The power distribution p(y)αp(y)^\alpha: sharpen the distribution over whole answers, which is hard to sample directly.

They disagree whenever an opening looks likely but leads into many weak continuations. Low temperature commits early to the likely-looking opening. The power distribution weighs where each opening leads. Metropolis–Hastings can target pαp^\alpha with the base model itself as the proposal.

Try it

base model p (branch numbers in grey)power distribution p^αtemperature 1/α at each step (branch numbers after →)
base model: P(B1)36%
power: P(B1)94%
low temperature: P(B1)16%
B1 is the single most likely answer, but its first token is less likely than A’s. Low temperature sharpens each choice on its own, so it rushes into the A branch and gets lost among five weak continuations. The power distribution scores whole answers, so it favours B1. Sampling it exactly is hard for real models; the Markov chain gets there by proposing new answers from the base model and accepting each with probability min(1, (p(new)/p(current))^(α−1)). Run it and watch the dark ticks settle on the blue bars.
A model chooses an opening (A or B), then a continuation. Sharpen it two ways: low temperature at every token, or the power distribution p^α over whole answers.
example · hiring by first impressions

A recruiter who sharpens every decision separately hires whoever interviews best at each stage, even if those candidates tend to fade later. One who scores whole careers prefers the candidate whose early stage was a little weaker but whose path almost always ends well.

example · the paper's result

Karan and Du (2025) ran Metropolis–Hastings on a base model's own answers, targeting pαp^\alpha with partial rewrites as proposals, with no training, reward model or verifier. On maths, coding and science benchmarks, single-sample accuracy nearly matched, and on some tasks beat, the same model after GRPO, without the loss of diversity across samples that RL causes. It's a strong hint that much of what RL does is sharpening the distribution the base model already has (Does RL teach new skills?).

Sequential Monte Carlo

Another family keeps a population of partial answers (particles), extends them a step at a time, scores them with a reward model or constraint, and resamples: duplicate promising particles, drop weak ones. It's importance sampling applied step by step, with resampling to stop the weights degenerating. It's used for constrained generation and for inference-time scaling, where it can beat best-of-n at the same compute.

Where this shows up

  • Inference-time scaling with a base model: power sampling, particle filtering.
  • Constrained generation (must contain a word, must parse as JSON) as probabilistic inference: SMC steering.
  • Diffusion language models are a Markov chain from all-masked to complete text: diffusion LMs.
  • Best-of-n and majority vote are simpler, non-chain answers to the same question: latent variables, tilting.
going deeper

Markov chains

A chain with transition probabilities P(x′∣x)P(x' \mid x) has stationary distribution π\pi if

π(x′)=∑xπ(x) P(x′∣x)\pi(x') = \sum_x \pi(x)\, P(x' \mid x)

Detailed balance, π(x)P(x′∣x)=π(x′)P(x∣x′)\pi(x) P(x' \mid x) = \pi(x') P(x \mid x'), is a sufficient condition and is what Metropolis–Hastings is built to satisfy.

Metropolis–Hastings acceptance

A(x→x′)=min⁡(1, π(x′) q(x∣x′)π(x) q(x′∣x))A(x \to x') = \min\Big(1,\ \frac{\pi(x')\, q(x \mid x')}{\pi(x)\, q(x' \mid x)}\Big)

With an independence proposal q(x′)=p(x′)q(x') = p(x') and target π∝pα\pi \propto p^\alpha, this simplifies to min⁡(1, (p(x′)/p(x))α−1)\min\big(1,\ (p(x')/p(x))^{\alpha - 1}\big), which is what the widget runs.

Power distribution versus temperature

πα(y)=p(y)α∑y′p(y′)αvsp1/α(y)=∏tp(yt∣y<t)α∑vp(v∣y<t)α\pi_\alpha(y) = \frac{p(y)^\alpha}{\sum_{y'} p(y')^\alpha} \qquad\text{vs}\qquad p_{1/\alpha}(y) = \prod_t \frac{p(y_t \mid y_{\lt t})^\alpha}{\sum_{v} p(v \mid y_{\lt t})^\alpha}

Each per-token normaliser depends on the prefix, so the product is not proportional to p(y)αp(y)^\alpha. Karan and Du show that πα\pi_\alpha upweights tokens whose futures are high-likelihood, while low temperature only looks at the current step.

Sequential Monte Carlo

With NN particles y1:t(i)y^{(i)}_{1:t}, extend each by sampling from the model, multiply its weight by an incremental factor wt(i)w_t^{(i)} (from a reward, constraint or learned "twist" function), and resample in proportion to the weights. The particle set approximates the target π(y)∝p(y) ϕ(y)\pi(y) \propto p(y)\, \phi(y) at the end, where ϕ\phi encodes the constraint or reward.

Papers

Related

  • decoding - How a probability distribution becomes an actual word. Inverse-CDF sampling, greedy and beam search, temperature, top-k, top-p and min-p, and the Gumbel-max trick, with what each one does to the distribution you're really sampling from.
  • rejection-sampling - Sample from a distribution you can evaluate but not easily draw from, by proposing from an easier one and sometimes saying no. The same idea makes LLM inference 2–3× faster without changing a single output probability.
  • latent-variables - Treat the chain of thought as an unobserved variable between question and answer. Majority voting, rejection-sampling fine-tuning and several RL methods turn out to be standard tools for latent-variable models.