Prune and Clone
12 min read
I have been trying to estimate how often a language model does something it almost never does: solves a problem at the edge of its ability, or produces a response its training was meant to rule out [WH, ’24], [JT+, ’25], [AS+, ’26]. Drawing complete generations and counting successes can take millions of attempts. Often a generation appears to go wrong long before it finishes, leaving us to spend computation on an increasingly unpromising attempt.
We can redirect that computation by keeping a population of attempts and copying promising ones more often. A raw success count would then exaggerate the probability we wanted to measure. Instead, each copy receives a weight that compensates for its chance of being selected: frequently copied attempts contribute less through each copy. The weighted estimate stays unbiased even when the guide is poor, provided every attempt that could still succeed retains a chance of selection.
One in a Million
How bad is plain counting, and what does it throw away? 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. 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.
Limits of Tilting
Why not change the coin so the event becomes common and correct with a likelihood-ratio weight, as in 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})\) of the model’s next-token probability to the proposal’s. Peeling off the last step and conditioning on the prefix \(x_{<T}\) it was drawn from writes the mean square of the whole weight as the mean square of the first \(T-1\) steps times a conditional factor:
\[ \mathbb{E}_{x \sim q}\big[w(x)^2\big] = \mathbb{E}_{x \sim q}\Big[\prod_{t=1}^{T-1} w_t^2 \cdot \mathbb{E}\big[w_T^2 \,\big|\, x_{<T}\big]\Big]. \]
That conditional factor is at least one, because \(w_T\) has conditional mean one and Jensen’s inequality bounds a second moment below by the squared mean:
\[ \mathbb{E}\big[w_T^2 \,\big|\, x_{<T}\big] \ge \big(\mathbb{E}[w_T \mid x_{<T}]\big)^2 = 1. \]
If every step’s conditional factor sits some fixed amount above one, repeating the peel raises that amount to the power \(T\). Per-step proposal errors multiply across the rollout, so a constant-factor error at every step becomes exponential in the rollout length. Selection instead draws from the original model and periodically resamples a weighted population, preventing a single likelihood ratio from accumulating across every step.
A Population with Weights
What should a clone be worth, if the guide that picked it is allowed to be wrong? 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\).
- Propagate. Every particle extends its prefix by one token drawn from the model \(p\).
- Resample (whenever you like). Choose selection probabilities \(c_1, \dots, c_n\) summing to one, using any guide to assign larger probabilities to preferred particles. 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.
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.
Propagating preserves the same quantity without touching any weight. 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.
The running total \(\sum_{i=1}^{n} w_i \psi_i\) is therefore unchanged in expectation by both operations, in whatever order and however often they interleave. It starts at \(\psi(\text{empty prefix}) = \rho\) and ends at \(\hat\rho\), since each terminal value \(\psi_i\) is 0 or 1. Thus \(\hat\rho\) is unbiased for any guide, resampling schedule, and population size.
Setting \(c_i = 0\) on a particle with \(w_i \psi_i > 0\) breaks the support condition, deletes that particle’s contribution, and biases the estimate low. Outright pruning is therefore reserved for particles that provably cannot succeed; an unpromising particle instead receives a tiny \(c_i\) and a correspondingly large weight if selected.
Running the Coin
What does the scheme cost on the coin? Run it 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 product contains one estimate \(h_t/n\) of each conditional probability in the twenty-link chain.
The variance comes from the binomial count at each stage. 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. This coin construction is the simplest case of multilevel splitting. 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 Committor
What would the best possible guide be? In the physical sciences, the value function \(\psi\) is called the committor: the probability of reaching the event from the current state [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)} \\ &= \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 committor of the empty prefix is \(\rho\) while the final committor \(\psi(x)\) is 1, since a continuation with zero committor gets zero proposal mass and the proposal can never produce a failure. Every rollout succeeds and carries weight exactly \(\rho\), so a single particle has zero variance.
The perfect guide is unavailable because the committor at the empty prefix is \(\rho\), just as for the perfect proposal on the tilting page. Real guides, such as a trained value head or heuristic progress score, approximate the committor. Inverse-probability weighting preserves unbiasedness while those approximations determine the variance.
The Cost in General
How does the cost scale beyond the coin? The coin’s accounting generalizes when the event can be divided into about \(\log(1/\rho)\) stages with constant conditional survival probabilities. The population then needs about \(\log(1/\rho)/\varepsilon^2\) particles for relative error \(\varepsilon\), giving the total cost:
\[ \text{selection: } \sim \frac{\log^2(1/\rho)}{\varepsilon^2} \qquad \text{against} \qquad \text{naive: } \sim \frac{1}{\rho\, \varepsilon^2}. \]
The plot compares these costs for the all-heads event as the sequence length grows. 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].
Where It’s Used
Is any of this specific to language models? This design appears across fields that study rare events with simulators. 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. For language models, twisted sequential Monte Carlo learns approximate committors and runs exactly this population to sample and weigh rare generations [ZBMG, ICML ’24].