Monte Carlo, bias and variance

Almost every number in an LLM paper is an average over samples standing in for an expectation nobody can compute. How to judge such an estimate, and why papers fuss over "unbiased" and "low-variance".

Key idea: Estimators: Monte Carlo averages, bias, variance, and mean squared error
Real world: A pollster can't ask every voter, so they ask 1,000 and report the average. A good method is right on average (unbiased) and doesn't swing wildly from poll to poll (low variance).
In an LLM: A model's pass@10 on a problem, the KL between policy and reference, the policy gradient itself: none can be computed exactly, because each is a sum over every possible answer. Each is estimated from a few sampled answers or tokens.

Monte Carlo estimation

Most quantities in LLM training are expectations: an average over every possible answer, weighted by how likely the model is to write it. There are astronomically many answers, so the sum can never be done. Instead:

Sample a few answers from the model.
Compute the quantity for each.
Average.

This is Monte Carlo estimation, named after the casino. The law of large numbers (error bars) says the average approaches the true expectation as samples grow. The question this page answers is: how good is it with the few samples we can afford?

example · estimating a free-throw percentage

A player has a true free-throw rate of 70%. Watch 10 shots and count the makes: you might see 6, 7, 9 or 5. The method "makes ÷ shots" is right on average, but any single estimate from 10 shots is typically off by about 15 points.

example · estimating a model's success rate

A model solves a maths problem with probability 0.3. Sample 8 answers, check them, and report the fraction correct. Some runs give 1/8, others 4/8. RL methods like GRPO feed exactly this kind of noisy 8-sample estimate into every update.

Bias and variance

An estimator is a recipe that turns samples into a guess. Because the samples are random, the guess is random too. Two numbers describe it:

Bias: how far the average guess is from the truth. Zero bias means "right on average": the estimator is unbiased.
Variance: how much the guess jumps around from one batch of samples to the next. Its square root, the standard deviation, is the typical size of the error.

They combine into the mean squared error: bias² + variance. A slightly biased estimator with much lower variance often wins, which is the whole idea behind clipping and truncation in RL.

example · a bathroom scale

A scale that always reads 1 kg heavy is biased but consistent. A scale that is right on average but jumps ±3 kg each time is unbiased but has high variance. For tracking your weight week to week, the biased one is more useful: you can see the trend.

example · clipping a policy update

PPO's clip and TIS cap make the gradient estimate biased: the update is no longer exactly the true gradient on average. They're used because the unbiased version occasionally has an enormous, destabilising value. Lower variance is worth a little bias.

A trap: plugging an estimate into a formula

An unbiased estimate of $p$ does not give an unbiased estimate of a function of $p$ . The pass@k example: pass@k $= 1 - (1-p)^k$ . You might estimate $p$ by $c/n$ and plug it in. But the formula is curved, so errors in $c/n$ don't cancel, and the result is systematically too low.

The fix, from the Codex paper, is an estimator built directly for pass@k: of the $n$ samples, $c$ are correct; choose $k$ of the $n$ at random; the chance that none of them is correct is $\binom{n-c}{k} / \binom{n}{k}$ . One minus that is unbiased.

example · the chance of at least one six

Estimate a die’s chance of six by rolling 6 times and counting sixes, then plug that into "chance of at least one six in 6 rolls". See exactly one six and you get $1 - (5/6)^6 = 0.665$ , the true value. But a run with no sixes gives 0, and a run with three gives 0.98. Because the curve flattens near 1, the highs don't make up for the lows. The average of the plug-in estimates is about 0.51, not 0.665.

example · pass@10 from 20 samples

20 samples, 2 correct. The plug-in gives $1 - (1 - 0.1)^{10} = 0.65$ . The unbiased estimator gives $1 - \binom{18}{10}/\binom{20}{10} = 1 - 0.237 = 0.763$ . Averaged over a benchmark, the plug-in version would understate pass@10 for every model.

Try it

true success rate p0.10samples n20k10

solid line: each row’s averagetrue pass@k

true pass@k0.651

plug-in: average0.569

unbiased: average0.652

unbiased: spread (sd)0.295

Each experiment draws 20 samples and turns them into one estimate; each row shows where 2,000 experiments landed. The plug-in’s average (solid amber line) is 0.082 too low: plugging an estimate into a curved formula gives a biased answer. The unbiased formula’s average sits on the dashed truth.

Each experiment is repeated 2,000 times. Each row is one estimator: where its estimates land. A good estimator is centred on the dashed truth and narrow.

Three KL estimators

The KL penalty needs $\mathrm{KL}(\pi \| \pi_\text{ref})$ , a sum over the whole vocabulary at every position. Trainers estimate it from the single sampled token, using the ratio $r = \pi_\text{ref}(\text{token}) / \pi(\text{token})$ :

Estimator	Formula	Unbiased?	Notes
k1	$-\log r$	yes	Can be negative; high variance
k2	$\tfrac12 (\log r)^2$	no	Low variance when close; biased as policies drift
k3	$(r-1) - \log r$	yes	Never negative; low variance when close; used by GRPO

k3 works because $r - 1$ has expected value zero under $\pi$ , so adding it changes nothing on average, but it cancels much of k1's noise. That's a control variate, the subject of the score function page.

Where this shows up

pass@k in every reasoning paper uses the unbiased estimator: Does RL teach new skills?.
The policy gradient is a Monte Carlo estimate; baselines are variance reduction: score function and baselines.
Importance sampling reuses samples from the wrong distribution: importance sampling in depth.
Evals are Monte Carlo estimates of a model's accuracy: error bars, comparing models.

going deeper

Definitions

For a quantity $\mu = \mathbb{E}_{x \sim p}[f(x)]$ and i.i.d. samples $x_1, \dots, x_n \sim p$ , the Monte Carlo estimator is

\hat\mu_n = \frac1n \sum_{i=1}^n f(x_i), \qquad \mathbb{E}[\hat\mu_n] = \mu, \qquad \operatorname{Var}[\hat\mu_n] = \frac{\operatorname{Var}_p[f(x)]}{n}

For any estimator $\hat\theta$ of $\theta$ :

\operatorname{Bias}(\hat\theta) = \mathbb{E}[\hat\theta] - \theta, \qquad \operatorname{MSE}(\hat\theta) = \mathbb{E}\big[(\hat\theta - \theta)^2\big] = \operatorname{Bias}(\hat\theta)^2 + \operatorname{Var}(\hat\theta)

Why plug-in estimates are biased

If $g$ is convex, Jensen's inequality gives $\mathbb{E}[g(\hat p)] \ge g(\mathbb{E}[\hat p]) = g(p)$ ; if concave, the reverse. $1 - (1-p)^k$ is concave in $p$ , so plugging in $\hat p = c/n$ underestimates pass@k. The same reasoning explains why $\log$ of an average differs from the average of $\log$ s, which shows up when papers estimate a sequence's log-likelihood from samples.

Unbiased pass@k

With $n$ samples and $c$ correct (Chen et al., 2021):

\widehat{\text{pass@}k} = 1 - \frac{\binom{n-c}{k}}{\binom{n}{k}} = 1 - \prod_{i=n-c+1}^{n} \Big(1 - \frac{k}{i}\Big)

The product form avoids overflowing binomial coefficients. Pass@k training papers go further and derive unbiased, low-variance estimators of the gradient of pass@k, so RL can optimise it directly.

KL estimators

With $r = \pi_\text{ref}(x)/\pi_\theta(x)$ and $x \sim \pi_\theta$ , using $\mathbb{E}_{\pi_\theta}[r] = 1$ :

\mathbb{E}[k_1] = \mathbb{E}[-\log r] = \mathrm{KL}(\pi_\theta \| \pi_\text{ref}), \qquad \mathbb{E}[k_3] = \mathbb{E}[r - 1 - \log r] = 0 + \mathrm{KL}

$k_3 \ge 0$ always, since $\log r \le r - 1$ . $\mathbb{E}[k_2]$ matches the KL only to second order. In papers you'll see these written per token, inside the GRPO objective, as

\mathbb{D}_\text{KL}\big[\pi_\theta \Vert \pi_\text{ref}\big] = \frac{\pi_\text{ref}(o_{i,t} \mid q, o_{i,\lt t})}{\pi_\theta(o_{i,t} \mid q, o_{i,\lt t})} - \log \frac{\pi_\text{ref}(o_{i,t} \mid q, o_{i,\lt t})}{\pi_\theta(o_{i,t} \mid q, o_{i,\lt t})} - 1

which is $k_3$ .

Papers

Evaluating Large Language Models Trained on Code (Chen et al., 2021): the unbiased pass@k estimator
Schulman, Approximating KL Divergence (blog, 2020): k1, k2, k3
DeepSeekMath (Shao et al., 2024): GRPO, with k3 in the loss
Pass@K Policy Optimization (Walder & Karkhanis, 2025): unbiased, low-variance pass@k gradient estimators
On the Design of KL-Regularized Policy Gradient Algorithms for LLM Reasoning (Zhang et al., 2025) and Rethinking KL Regularization in RLHF (Liu et al., 2025): which estimator gives the right gradient
A Comedy of Estimators: On KL Regularization in RL Training of LLMs (Shah et al., 2025): k1/k2/k3 in the reward versus the loss, compared empirically