Re-understanding KL Approximation from an RL-for-LLM Lens: Notes on “Approximating KL Divergence”

What’s the difference between KL-divergence estimation methods in PPO and GRPO?

John Schulman’s blog post “Approximating KL Divergence” talks about how to approximate KL divergence via sampling (Monte Carlo), and it introduces three estimators ($k_1$, $k_2$, $k_3$) along with their bias–variance behaviors. But the original post is framed in the context of general probability distributions; it doesn’t touch the reinforcement-learning-for-LLM training setting. This write-up records the questions I had while reading, the thoughts I formed after mapping things to RL for LLMs, and a few places where I felt the original explanations could be pushed on a bit.

What “Approximating KL Divergence” Says (in my own words)

In this section, I’m imagining readers who haven’t read the original post yet, so let’s quickly pass through the most important bits. Put simply, the post is about how we can build reasonable Monte Carlo–style estimators for it, when we can’t directly compute KL divergence.

As the formula shows: when estimating the KL between two (complicated) distributions, there’s a coding trick people often use: approximate KL by the sample mean of $\log!\big(\frac{q(x)}{p(x)}\big)$ with samples drawn from $q$ (as opposed to trying to evaluate the full expectation exactly). The post then points out another move: use the sample average of $\tfrac{1}{2}(\log r)^2$ to replace the more “standard” $\log r$ form, where $r=\frac{q(x)}{p(x)}$. The write-up explains why this expression can be a good (albeit biased) estimator for KL, and how to make it unbiased while keeping its low variance.

How we compute KL depends on how we can access $p$ and $q$. Here we assume we can evaluate $p(x)$ and $q(x)$ (probabilities or densities) for any $x$, but we can’t analytically sum/integrate over $x$. Why might we fail to do the analytic sum/integral? Maybe the exact computation is too expensive in compute or memory, maybe there’s no closed form, or maybe we only store log-probs instead of full distributions to keep code simpler, especially fine when KL is just a diagnostic (as is often the case in RL). The most common strategy to approximate sums or integrals is Monte Carlo. Given samples $x_1, x_2, \dots, x_n \sim q$, how do we build a good estimator?

A good estimator should be unbiased (right mean) and low-variance. We know one unbiased estimator:

But it has high variance: by definition KL is a nonnegative quantity, yet for the estimator above, roughly “half” the sample values can be negative (if we assume no prior structure on $p$ and $q$), and this swings the average around a lot, hence high variance. For notational convenience, set $r = \frac{q(x)}{p(x)}$. Then the original KL can be written as

To reduce variance, we can design an alternative estimator:

It has lower variance, but it’s biased. Intuitively, $k_2$ feels nicer because each sample gives a nonnegative “distance” between $p$ and $q$, so it stays positive. Empirically, $k_2$ really does have much lower variance than $k_1$, and the bias can be quite small. As for why $k_2$ enjoys such a variance drop compared with $k_1$, the original post uses an $f$-divergence view to give an analytic explanation, I won’t repeat that here.

Now, can we get an estimator that is both unbiased and low-variance? A general trick is to use a control variate: start from the unbiased $k_1$ and add something whose expectation is zero and is negatively correlated with it to reduce variance. A very convenient zero-mean quantity here is $r-1$. Thus, for any $\lambda$,

is still an unbiased KL estimator. In theory we could minimize the variance over $\lambda$, but the closed-form depends on $p$ and $q$ and isn’t easy to get. Notice, though, that since $\log(x)$ is concave,

so if we pick $\lambda=1$, the expression is guaranteed nonnegative. Here, $r-1$ is the tangent of $\log r$ at $r=1$. So with $\lambda=1$ we’re really measuring the vertical gap between $\log(x)$ and its tangent. This leads to the estimator \(k_3 \;=\; (r - 1) \;-\; \log r,\) which is always nonnegative. And $k_3$ is exactly the piece where, in practice, GRPO differs from PPO in how KL is estimated (PPO uses $k_1$).

Discussing KL Estimation from an RL-for-LLM Perspective

In RL (think PPO, GRPO, etc.), we often tack a KL divergence term onto the loss to keep the new policy from drifting too far from the old one. Here, $q$ is the old policy distribution ($\pi_{\text{old}}$), $p$ is the new policy distribution ($\pi_{\text{new}}$), and $x$ is a complete action sample (in an LLM this means a token or a token sequence). We usually use $s$ to denote the state (in an LLM, that’s the prompt or context), and $x$ is a specific token generated in that context. When we compute KL, what we’re really doing is taking the KL over the action distribution given a state, and then averaging over states:

At sampling time, we typically fix a prompt (state) and then estimate this KL for that prompt.

So why can’t we just compute KL exactly instead of estimating it? The reasons are exactly those listed in the original blog post; in RL for LLMs, the main culprit is Reason #1: the action space (token space) is too large to sum/integrate over all possible $x$. For example, if a tokenizer has 50,000 vocabulary entries, even computing the KL for a single token means summing over 50,000 actions; and in RL we’re usually doing multi-step (sequence) generation, so the space blows up exponentially, which is completely impractical. There’s also a pragmatic reason: during training we generally don’t store the full distribution (all token probabilities); we only keep the log-probs of the tokens actually generated along the trajectory, to save GPU memory and I/O. So we have to use Monte Carlo sampling: draw $x$ from some distribution (usually $q$, the old policy), and use those samples to approximate KL. And that drops us squarely into the territory the blog post is about.

In that post, the estimator we keep talking about is really just a function of a sample: it takes $p(x)$ and $q(x)$ for some sampled $x$ (or their ratio $r = \frac{q(x)}{p(x)}$) and spits out a number. We then take the average of those numbers over our samples to approximate KL. For example:

• $k_1(x) = -\log r$
• $k_2(x) = \frac12 (\log r)^2$
• $k_3(x) = (r - 1) - \log r$

These $k_i$ are just different KL-estimator formulas. They all approximate KL by averaging over samples, but differ in bias and variance. Once we pick an estimator, we’re really just committing to a specific formula for approximating KL. The process looks like this:

1. Sampling
   Sample a batch of tokens (or sequences) $x_1, x_2, \dots, x_N$ from the old policy $q$.
2. Compute log-probs
   For each sample, compute the log-probabilities under both new and old policies:

and get $r_i = \frac{q(x_i)}{p(x_i)}$ or $\log r_i$.

1. Plug into the estimator formula
   For example, if we choose $k_3$:

1. Average

That’s the approximate KL value, standing in for the true KL.

If we compare this to computing the true KL (no estimation) for a discrete probability distribution (LLM single-token step): we’d need to iterate over every possible token $x$:

You can see immediately that with an estimator, the computational load is much smaller than doing the full sum, especially in high-dimensional action spaces.

Talking About Variance in Different KL Estimators

Important to note: the “variance” we’re talking about here is the variance of the values the estimator outputs over samples:

That is, how much $k(x)$ fluctuates across the sample space. An unbiased estimator means that with infinitely many samples, its mean equals the true KL. But a high-variance estimator means that even if the mean is right (unbiased), with a small number of samples the average can be way off. In RL for LLMs, the KL term is often a regularization factor in the loss (e.g., $\beta \cdot \mathrm{KL}$). If the KL estimator’s variance is large, it makes the loss noisy, which in turn makes gradients noisy and training unstable.

In the original post, to give readers an intuition for why $k_1$ is not low-variance, the author writes:

However, it ($k_1$) has high-variance, as it’s negative for half of the samples, whereas KL is always positive.

The author points out that although $k_1$ is unbiased, without prior constraints on $p$ and $q$, half the samples will have one bigger than the other, so half of the $k_1$ values are positive and half negative. Up to here I’m fine. But then the author says: because KL is always greater than 0 (a basic inequality), $k_1$ must therefore have high variance. And here I think the causal link doesn’t actually hold: you can’t use the sign of the expectation to dictate the sign of individual samples. A quick counterexample: in computing the expectation, $p(x) \log \frac{p(x)}{q(x)}$ is also sometimes positive and sometimes negative; that fact by itself tells you nothing about variance. In reality, a single-sample log ratio (whether $\log \frac{q(x)}{p(x)}$ or $\log \frac{p(x)}{q(x)}$) can be positive or negative, just like $k_1$, so sign-flipping alone is not the sole reason for high variance.

From the KL definition:

The expectation is guaranteed nonnegative, but the integrand $\log\frac{q(x)}{p(x)}$ can be positive or negative for individual samples. And $k_1$ is exactly that integrand:

So each sample value can indeed be positive or negative, same as the integrand in the KL definition.

So why does $k_1$ have high variance?

It’s not the mere “sign flipping.” The real reason is that $k_1$’s value distribution is often wide (heavy-tailed). For example, if $p(x)$ is tiny for some sample, then $\log\frac{q}{p}$ can be huge (positive or negative). These extreme values dominate the finite-sample average, pushing variance up. In other words, it’s the combination of extreme values + positive/negative cancellation: cancellation means you need more samples to converge to the true mean, and extreme values make the sample variance itself larger. So the “half negative” comment in the blog is more of an intuition hook than a complete explanation.

From this perspective, if we look at the other estimators $k_2$ and $k_3$, we see: $k_2 = \frac12 (\log r)^2$ is always positive, so there’s no cancellation, but this introduces bias; squaring also smooths the magnitude, reducing variance. $k_3$ uses a control variate to knock out part of the fluctuation source, lowering variance while keeping unbiasedness (details next).

In PPO/GRPO, if you use $k_1$ and the batch is small or the distributions are far apart, the KL estimate will jump around (because a few extreme samples can swing the mean hard). That makes the KL-penalty coefficient unstable: it might suddenly be way too strong or too weak. Switching to a lower-variance estimator ($k_2$ or $k_3$) makes each sample’s KL contribution steadier, less likely to be dominated by a handful of extreme samples.

Why can $k_3$ be unbiased and low-variance?

At first glance, $k_3$ is always positive, so you might think its mean must be larger than $k_1$’s.
But remember: $k_3$ is derived from $k_1$ via a control variate. The blog’s reasoning goes like this:

where $h(x) = r - 1$, and under $x\sim q$ its expectation is:

So adding any multiple of $h(x)$ doesn’t change the expectation. When $\lambda = 1$:

This explains why $k_3$’s expectation equals $k_1$’s expectation, and equals the KL, making it an unbiased estimator.

The reason $k_3$ has lower variance than $k_1$ is: $k_1$ only has $-\log r$, which can swing wildly (both positive and negative, with occasional huge values). But $r - 1$ and $-\log r$ are numerically highly correlated (when one grows, the other grows/shrinks), and that correlation is negative. Adding $(r - 1)$ is like injecting a negatively correlated term to cancel fluctuations. After cancellation, what’s left in $k_3$ is tighter in range, always positive, and therefore lower in sample variance.