Prune and Clone
13 min read
I have been trying to estimate how often a language model does something it almost never does: solves a problem at the very edge of its ability, or produces a response its training was supposed to rule out [WH, ’24], [JT+, ’25], [AS+, ’26]. The obvious estimator draws complete rollouts and counts the successes. For an event of probability one in a million, it needs about a million rollouts before it sees a single one. Most of that work is visibly wasted long before it finishes: a rollout whose reasoning goes wrong by token fifty still runs to the end and spends its full budget. We would rather prune the doomed rollouts early and spend the savings on the ones still going. The catch is that pruning whatever looks doomed skews the count, because the sampler is now choosing which outcomes it gets to see. The fix is one bookkeeping rule.
One in a Million
Our running example is the simplest rare event there is: flip a fair coin 20 times and succeed only if every flip comes up heads. The probability we want is:
\[ \rho = \Pr\big[\text{all 20 flips heads}\big] = 2^{-20} \approx 9.5 \times 10^{-7}, \]
about one in a million, and every number below can be checked by hand. Sampling and counting needs about \(100/\rho\) draws for ten percent relative error, since the error is set by how many successes we see and not by how many draws we take. That is a hundred million twenty-flip sequences, over two billion coin flips.
A run that opens with tails is dead at flip one, and the sampler starts the next run from nothing. When a run does reach five straight heads, a position 32 times closer to the event than the start, that progress is thrown away too the moment the run dies.
The old fix, as old as Monte Carlo itself [KH, NBS AMS ’51], is to write the rare event as a chain of easy steps:
\[ \rho = \prod_{t=1}^{20} \Pr\big[\text{flip } t \text{ heads} \mid \text{first } t-1 \text{ heads}\big] = \Big(\tfrac{1}{2}\Big)^{20}, \]
where each factor is a probability of one half, and to estimate the chain with a population of runs held at the frontier: when one run dies, replace it with a clone of one still alive. The question is what the clone should be worth.
Why Not Just Tilt the Coin?
There is a classical alternative: change the coin so the event becomes common, then correct with a likelihood-ratio weight (tilting at rare events). On this coin it works perfectly: a proposal that always flips heads produces the event every time and gives every draw weight exactly \(2^{-20}\), for zero variance. That works only because we know the event’s structure completely and can aim every single step at it, which is the reason it will not transfer.
A language model rollout has thousands of steps and no known perfect proposal, and reweighting compounds the error at every one of them. For a proposal \(q\) that factorizes across positions \(t = 1, \dots, T\), the weight is a product of per-step ratios \(w_t = p(x_t \mid x_{<t}) / q(x_t \mid x_{<t})\), and so is its mean square:
\[ \mathbb{E}_{x \sim q}\big[w(x)^2\big] = \prod_{t=1}^{T} \mathbb{E}\big[w_t^2\big]. \]
Every factor in that product is at least one, because each \(w_t\) has mean one and Jensen’s inequality bounds a second moment below by the squared mean:
\[ \mathbb{E}\big[w_t^2\big] \ge \big(\mathbb{E}[w_t]\big)^2 = 1. \]
So per-step mistakes multiply and never cancel: a proposal off by a constant factor at every step is off by that factor raised to the length of the rollout.
Selection leaves the model’s dynamics alone and corrects with a population instead of a number: a population resets every time it resamples, but an accumulated weight never does.
A Population with Weights
Keep \(n\) particles, each one a growing prefix of a rollout, each carrying a weight. Start every particle at the empty prefix with weight \(1/n\).
- March. Every particle extends its prefix by one token, drawn from the model \(p\) as usual.
- Resample (whenever you like). Choose selection probabilities \(c_1, \dots, c_n\) summing to one, any way you like: this is where a guide gets to act, piling probability on the particles it likes. Draw \(n\) children independently. Each child picks parent \(i\) with probability \(c_i\), copies that parent’s prefix, and takes weight \(w_i / (n c_i)\).
- Report. When every particle has finished its rollout, report \(\hat\rho = \sum_{i=1}^{n} w_i\, \mathbf{1}[\text{particle } i \text{ succeeded}]\), the total weight sitting on successes across the \(n\) particles.
A particle the guide likes is cloned often, and each clone carries a small weight. A particle the guide dislikes is rarely cloned, but a clone that does get drawn carries weight \(w_i/(n c_i)\), large in exact proportion to how unlikely the draw was. The weight undoes the favoritism.
To say what the scheme preserves, give each particle a value: let \(\psi(x_{<t})\) be the probability that the model, run onward from the prefix \(x_{<t}\), ends in success, and write \(\psi_i\) for the value of particle \(i\)’s current prefix. Given the population right now, the expected final total is the value-weighted mass over all \(n\) particles:
\[ \sum_{i=1}^{n} w_i\, \psi_i . \]
Claim (a resample changes nothing in expectation): for any selection probabilities with \(c_i > 0\) whenever \(w_i \psi_i > 0\), the value-weighted mass of the \(n\) children (indexed \(j\)) has the same expectation as that of the \(n\) parents (indexed \(i\)):
\[ \mathbb{E}\Big[\textstyle\sum_{j=1}^{n} w'_j\, \psi_j \,\Big|\, \text{parents}\Big] = \sum_{i=1}^{n} w_i\, \psi_i . \]
Proof
Take one child, with weight \(w'\) and value \(\psi'\). It picks parent \(i\) with probability \(c_i\), and in that case it copies the parent’s prefix and value and takes weight \(w_i/(n c_i)\), so its expected contribution is:
\[ \begin{aligned} \mathbb{E}\big[w'\, \psi'\big] &= \sum_{i=1}^{n} \Pr[\text{parent is } i] \cdot \big(\text{weight if parent is } i\big)\, \psi_i \\ &= \sum_{i=1}^{n} c_i \cdot \frac{w_i}{n c_i}\, \psi_i \\ &= \sum_{i=1}^{n} \frac{1}{n}\, w_i\, \psi_i \\ &= \frac{1}{n} \sum_{i=1}^{n} w_i\, \psi_i , \end{aligned} \]
where the first line sums over which parent the child picked, the second substitutes the selection probability and the weight rule, the third cancels \(c_i\) against the \(c_i\) in the denominator of the weight, and the fourth pulls the constant out of the sum.
The \(n\) children are drawn independently from that same rule, so their expected contributions add:
\[ \mathbb{E}\Big[\textstyle\sum_{j=1}^{n} w'_j\, \psi_j\Big] = n \cdot \frac{1}{n} \sum_{i=1}^{n} w_i\, \psi_i = \sum_{i=1}^{n} w_i\, \psi_i . \]
The support condition is what makes the cancellation legal. A parent with \(c_i = 0\) never gets cloned and contributes nothing to the sum, which is harmless only when \(w_i \psi_i = 0\) already.
Marching preserves the same quantity for free. The value of a prefix is the average value of its one-token extensions, which is the tower property of conditional probability:
\[ \psi(x_{<t}) = \sum_{x_t} p(x_t \mid x_{<t})\; \psi(x_{<t}\, x_t). \]
Reading that right to left: a particle at \(x_{<t}\) draws its next token from \(p\), so the expected value of where it lands is the value it already had.
So the running total \(\sum_{i=1}^{n} w_i \psi_i\) is untouched in expectation by both operations, in whatever order and however often they interleave. At the start it equals \(\psi(\text{empty prefix})\), which is \(\rho\). At the end every \(\psi_i\) has settled to 0 or 1, and the total is \(\hat\rho\). Chaining the stages, \(\hat\rho\) is unbiased for \(\rho\) for any guide, any resampling schedule, and any population size. Everything rests on one observation: a clone’s weight is one over the chance it was picked, so the favoritism in the picking cancels against the weight, term by term. The guide never appears in the estimate, only in the choice of \(c\), so a guide that ignores the prefixes entirely and resamples uniformly at random is still unbiased.
The one way to break this is setting \(c_i = 0\) on a particle with \(w_i \psi_i > 0\): it deletes that particle’s term from the sum, biases the estimate low, and no later stage can put it back. So outright pruning is reserved for particles that provably cannot succeed. A merely unpromising particle is pruned softly instead: a tiny \(c_i\) and, if it survives, a large weight.
Running the Coin
Now run the scheme on the coin with the obvious guide, resampling after every flip: a prefix containing tails has value zero, so prune it (legal, since \(\psi_i = 0\)), and clone the survivors uniformly. At stage \(t\), some number \(h_t\) of the \(n\) particles flip heads, and each survivor gets the same selection probability \(c = 1/h_t\), so each child’s weight is:
\[ \begin{aligned} w' &= \frac{w}{n c} \\ &= \frac{w}{n \cdot (1/h_t)} \\ &= w \cdot \frac{h_t}{n}, \end{aligned} \]
substituting \(c = 1/h_t\) and then flipping the fraction. Every particle holds the same weight throughout, so after stage \(t\) that shared weight is \((1/n) \prod_{j=1}^{t} (h_j / n)\). After the twentieth flip the \(h_{20}\) survivors are complete successes, no resample follows, and the total collapses:
\[ \begin{aligned} \hat{\rho} &= \sum_{i=1}^{n} w_i\, \mathbf{1}[\text{particle } i \text{ succeeded}] \\ &= h_{20} \cdot \frac{1}{n} \prod_{j=1}^{19} \frac{h_j}{n} \\ &= \frac{h_{20}}{n} \prod_{j=1}^{19} \frac{h_j}{n} \\ &= \prod_{t=1}^{20} \frac{h_t}{n}, \end{aligned} \]
where the second line counts the \(h_{20}\) survivors, each holding the weight after stage 19, the third groups \(h_{20}\) with the \(1/n\), and the fourth absorbs that factor into the product.
The estimate is the product of the twenty survival fractions. Each fraction \(h_t/n\) estimates one link of the chain we started from, the conditional probability of one half, and the product mirrors the factorization.
The variance is now elementary. Given the past, \(h_t\) counts \(n\) fresh fair flips, so \(h_t \sim \mathrm{Bin}(n, \tfrac12)\), with mean \(n/2\) and variance \(n/4\). One stage’s mean square is:
\[ \begin{aligned} \mathbb{E}\Big[\Big(\frac{h_t}{n}\Big)^{2}\Big] &= \frac{1}{n^2}\Big(\mathrm{Var}(h_t) + \mathbb{E}[h_t]^2\Big) \\ &= \frac{1}{n^2}\Big(\frac{n}{4} + \frac{n^2}{4}\Big) \\ &= \frac{1}{4}\Big(1 + \frac{1}{n}\Big), \end{aligned} \]
where the first line is the second moment as variance plus squared mean, the second substitutes the binomial values, and the third divides through by \(n^2\). That factor does not depend on the past, so peeling one stage at a time turns the mean square of the whole product into a product of the stage factors:
\[ \begin{aligned} \mathbb{E}\big[\hat{\rho}^2\big] &= \prod_{t=1}^{20} \mathbb{E}\Big[\Big(\frac{h_t}{n}\Big)^{2}\Big] \\ &= \Big(\frac{1}{4}\Big)^{20} \Big(1 + \frac{1}{n}\Big)^{20} \\ &= \rho^2 \Big(1 + \frac{1}{n}\Big)^{20}, \end{aligned} \]
where the second line substitutes the stage factor twenty times and the third recognizes \(4^{-20}\) as \(\rho^2\). Subtracting the squared mean gives the relative variance:
\[ \begin{aligned} \frac{\mathrm{Var}(\hat{\rho})}{\rho^2} &= \frac{\mathbb{E}[\hat{\rho}^2] - \rho^2}{\rho^2} \\ &= \Big(1 + \frac{1}{n}\Big)^{20} - 1 \\ &\approx \frac{20}{n}, \end{aligned} \]
the last line being the first-order expansion, good once \(n\) is comfortably past 20. At \(n = 2000\) the relative variance is \(0.0100\), which is ten percent relative error. That costs 20 stages of \(n\) flips each, 40,000 flips, against the naive two billion, a factor of fifty thousand. Cloning a prefix costs no flips at all, since it is only a copy. (The same discount is what makes this attractive for language models: a clone inherits its parent’s prefix, and with it the parent’s computed KV cache.)
In the figure, eight particles run the first five flips of the coin: at every stage the tails-flippers are pruned in place and survivors fork clones into the freed lanes. What we have just run by hand is multilevel splitting in miniature. The adaptive version that chooses its own stages is Cérou & Guyader’s [CG, SAA ’07], and the same design under the name subset simulation is a standard tool of reliability engineering [AB, PEM ’01].
The Perfect Guide
The value function \(\psi\) has a name in the physical sciences: the committor, the probability of committing to the event from the current state, and it is the central object of transition path theory [EVE, J. Stat. Phys. ’06]. On the coin it is explicit:
\[ \psi\big(\text{prefix of } t \text{ heads}\big) = 2^{-(20 - t)}, \]
and zero on any prefix containing a tails.
Our coin guide used only the committor’s zero set. Suppose we had all of it, and went further than selection by steering the dynamics, proposing each next token from the committor-reweighted model:
\[ q(x_t \mid x_{<t}) = p(x_t \mid x_{<t})\, \frac{\psi(x_{<t}\, x_t)}{\psi(x_{<t})}. \]
This is a legitimate distribution because the tower identity above says the numerators average to the denominator. The importance weight of a completed rollout then telescopes:
\[ \begin{aligned} w(x) &= \prod_{t=1}^{20} \frac{p(x_t \mid x_{<t})}{q(x_t \mid x_{<t})} \\ &= \prod_{t=1}^{20} \frac{p(x_t \mid x_{<t})}{p(x_t \mid x_{<t})\, \psi(x_{<t}\, x_t) / \psi(x_{<t})} \\ &= \prod_{t=1}^{20} \frac{\psi(x_{<t})}{\psi(x_{<t}\, x_t)} \\ &= \frac{\psi(\text{empty prefix})}{\psi(x)} \\ &= \frac{\rho}{1} = \rho, \end{aligned} \]
where the second line substitutes the proposal, the third cancels the model probability, the fourth cancels the telescoping interior (each denominator is the next numerator), and the fifth uses that the proposal can never produce a failure, since a continuation with zero committor gets zero proposal mass, so the final committor is 1. Every rollout succeeds and carries weight exactly \(\rho\): no variance, from a single particle, with no population and no resampling.
The perfect guide does not explore, then. It walks straight to the answer and reports its probability, which is the circularity: the committor at the empty prefix is \(\rho\), the number we wanted, the same circularity as the perfect proposal on the tilting page. Real guides are approximations: a trained value head, a heuristic progress score. The claim about resampling is what makes approximation safe: it puts the guide’s quality on the variance and leaves correctness to the weights, so resetting toward a guide’s favorites is the right move even when the guide is crude, spending a fixed budget where the estimated committor mass is at no cost in bias.
The Cost in General
The coin’s accounting generalizes. An event of rarity \(\rho\) breaks into about \(\log(1/\rho)\) constant-factor steps, the population needs \(\log(1/\rho)/\varepsilon^2\) particles for relative error \(\varepsilon\), and multiplying the two gives a total that is polylogarithmic in the rarity:
\[ \text{selection: } \sim \frac{\log^2(1/\rho)}{\varepsilon^2} \qquad \text{against} \qquad \text{naive: } \sim \frac{1}{\rho\, \varepsilon^2}. \]
In the plot, the two costs are drawn for the all-heads event as its depth grows: the naive cost climbs an exponential wall while the prune-and-clone cost grows only quadratically in the depth. That logarithmic scaling is close to optimal: for the closely related problem of estimating a Gibbs normalizing constant through a ladder of conditional samplers, matching lower bounds put the cost of any scheme at order \(\log(1/\rho)/\varepsilon^2\) sampler calls [Kolmogorov, COLT ’18], [HK, TALG ’25]. What is left is the constant, a question about the guide.
Where It’s Used
This design has been rediscovered by every field with a rare event and a simulator. Kahn & Harris built it for neutrons crossing a shield, the original rare transmission event [KH, NBS AMS ’51]. Subset simulation estimates structural failure probabilities, a bridge meeting a load it sees once in ten thousand years, by exactly this chain of steps [AB, PEM ’01]. Weighted ensemble molecular dynamics, which keeps the particle weights explicit in the same way, reaches protein binding events on timescales no direct simulation can touch [HK, Biophys. J. ’96], [ZC, Annu. Rev. Biophys. ’17]. The general theory, resampling systems as unbiased estimators of normalizing constants, is the Feynman–Kac framework [Del Moral, ’04], of which the claim above is the smallest working case. And for language models, twisted sequential Monte Carlo learns approximate committors and runs exactly this population to sample and weigh rare generations [ZBMG, ICML ’24].
The portable lesson: when a heuristic gets to choose where the samples go, weight each sample by one over its chance of being chosen, and the heuristic is then free to be wrong. That freedom is what makes a learned guide usable at all.