Prune and Clone
7 min read
We want to estimate the probability \(\rho\) that a random generation succeeds. The event might be a language model solving a difficult problem or a simulation reaching a rare failure state. Sampling complete attempts and counting successes works, but spends most of its effort on failures. If we can recognize progress before an attempt finishes, we can copy promising partial attempts and continue each copy independently. The copies need smaller weights so that finding more successes does not inflate the estimated probability.
Counting Rare Successes
For \(m\) independent attempts, let \(Z_r\) equal one if attempt \(r\) succeeds and zero otherwise. The usual estimate and its variance are:
\[ \hat\rho_{\mathrm{naive}}=\frac1m\sum_{r=1}^m Z_r, \qquad \operatorname{Var}(\hat\rho_{\mathrm{naive}})=\frac{\rho(1-\rho)}{m}. \]
Each indicator has variance \(\rho(1-\rho)\), and averaging independent attempts divides that variance by \(m\). The estimate is unbiased, so its relative root mean squared error is:
\[ \frac{\sqrt{\mathbb E[(\hat\rho_{\mathrm{naive}}-\rho)^2]}}{\rho} =\sqrt{\frac{1-\rho}{m\rho}}. \]
For ten percent relative error, we therefore need:
\[ m\ge\frac{1-\rho}{0.01\rho}\approx\frac{100}{\rho}. \]
To see the cost and check a different estimator, consider the event that twenty fair coin flips are all heads:
\[ \rho=2^{-20}\approx9.5\times10^{-7}. \]
The naive estimate needs about 105 million independent attempts. We can stop an attempt at its first tail. The expected number of flips per attempt is:
\[ 1+\frac12+\cdots+\frac1{2^{19}}=2(1-2^{-20}). \]
The \(j\)th flip is needed only if the first \(j-1\) were heads. Even with early stopping, the expected total is about 210 million coin flips.
An attempt that reaches ten heads has made useful progress: only ten more heads are needed. Starting several independent continuations from that prefix lets us reuse the progress. This is the idea behind multilevel splitting, introduced in early work on rare-event Monte Carlo [KH, NBS AMS ’51].
Cloning with Weights
Keep a population of \(n\) partial attempts, called particles. Each starts at the empty prefix with weight \(1/n\). Use a fixed finite horizon and leave completed attempts unchanged on later steps. Extend them using the original model’s transition probabilities, and periodically resample the population:
- A guide assigns selection probabilities \(c_1,\ldots,c_n\), summing to one, to the current particles.
- Draw \(n\) children independently. Each chooses parent \(i\) with probability \(c_i\) and copies its prefix.
- If parent \(i\) had weight \(w_i\), give its child weight:
\[ w'=\frac{w_i}{n c_i}. \]
Continue the children using fresh randomness. A frequently selected parent has many descendants, but each receives a smaller weight. When the attempts finish, the estimate is the total weight of successes:
\[ \hat\rho=\sum_{i=1}^n w_i\,\mathbf1[\text{particle }i\text{ succeeds}]. \]
There is no further division by \(n\): the initial weights already contain it. Nor do we renormalize the weights to sum to one after resampling.
The reason for the weight rule becomes clear if we imagine knowing each prefix’s true chance of eventual success. Write \(\psi_i\) for that probability for parent \(i\). We use it to analyze the method; the guide does not need to know it. Conditional on the current parents and the guide’s chosen probabilities, a child’s expected contribution is:
\[ \begin{aligned} \mathbb E[w'\psi'\mid\text{parents}] &=\sum_{i:c_i>0} c_i\frac{w_i}{n c_i}\psi_i\\ &=\frac1n\sum_{i=1}^n w_i\psi_i. \end{aligned} \]
Selection probability cancels against the inverse probability in the weight. Summing over the \(n\) children restores the parents’ total \(\sum_i w_i\psi_i\). The equality requires the support condition:
\[ c_i>0\quad\text{whenever }w_i\psi_i>0. \]
We may discard a positive-weight particle only if it cannot succeed. A merely unpromising particle must retain some chance of selection; if chosen rarely, its child carries a large compensating weight.
Extending a prefix also preserves its expected contribution. If \(p(a\mid x)\) is the original model’s probability of the next token \(a\) after prefix \(x\), conditional expectation gives:
\[ \psi(x)=\sum_a p(a\mid x)\psi(xa). \]
Thus both propagation and resampling preserve \(\sum_iw_i\psi_i\) in expectation. It starts at \(\rho\), since all particles begin at the empty prefix, and ends at \(\hat\rho\), since a completed attempt has success probability zero or one. With resampling decisions based on observations so far, iterating the conditional expectations proves:
\[ \mathbb E[\hat\rho]=\rho. \]
The guide can be inaccurate without biasing the answer, provided the support condition holds. Its accuracy determines how variable the answer is.
Twenty Heads with a Population
For the coin, resample after every flip except the last. A prefix containing tails can never succeed, so we may discard it and select uniformly among the all-heads survivors. The figure shows one possible genealogy for a small population.
Let \(h_t\) be the number of heads among the \(n\) particles at stage \(t\). If \(h_t>0\), each survivor is selected with probability \(1/h_t\), so every child’s weight becomes:
\[ w'=\frac{w}{n(1/h_t)}=w\frac{h_t}{n}. \]
All particles have the same weight after each resampling. After nineteen stages it is \((1/n)\prod_{t=1}^{19}(h_t/n)\). The \(h_{20}\) final successes therefore contribute:
\[ \hat\rho=h_{20}\frac1n\prod_{t=1}^{19}\frac{h_t}{n} =\prod_{t=1}^{20}\frac{h_t}{n}. \]
If a stage has no survivors, return zero and stop. For the calculation below, we may imagine generating the remaining counts anyway: the product is already zero.
Every surviving prefix has exactly the same future: another fresh fair coin. Consequently the stage counts are independent binomial variables, \(h_t\sim\operatorname{Binomial}(n,1/2)\), with mean \(n/2\) and variance \(n/4\). Their second moments give:
\[ \begin{aligned} \mathbb E\!\left[\left(\frac{h_t}{n}\right)^2\right] &=\frac{\operatorname{Var}(h_t)+\mathbb E[h_t]^2}{n^2}\\ &=\frac14\left(1+\frac1n\right). \end{aligned} \]
Independence lets us multiply these second moments across stages. Since the squared mean is \(\rho^2=4^{-20}\), the relative variance is:
\[ \begin{aligned} \frac{\operatorname{Var}(\hat\rho)}{\rho^2} &=\frac{\mathbb E[\hat\rho^2]}{\rho^2}-1\\ &=\left(1+\frac1n\right)^{20}-1. \end{aligned} \]
With \(n=2010\), this is below \(0.01\), giving at most ten percent relative root mean squared error. The population costs at most \(20n=40{,}200\) coin flips, compared with an expected 210 million for the naive estimate that stops each failed attempt immediately. Both count newly generated coin flips; copying a prefix uses no additional flips.
The Saving and Its Assumptions
For an all-heads event of length \(k\), the same calculation gives relative variance \((1+1/n)^k-1\). When \(n\) is large compared with \(k\), this is approximately \(k/n\). To reach relative error \(\varepsilon\), we therefore need about \(k/\varepsilon^2\) particles and \(k^2/\varepsilon^2\) coin flips. Naive attempts still need about \(2^k/\varepsilon^2\) trials, each costing fewer than two flips on average when stopped at the first tail. The plot compares both methods in coin flips, using their exact variance formulas.
Fresh randomness makes this example especially favorable. Cloned prefixes have identical future success probabilities, and every next-stage flip is independent. General simulations need not have either property: descendants share a history, and a guide can repeatedly favor the wrong histories. Having constant survival probabilities at successive levels alone does not guarantee the coin’s variance or cost scaling.
The weight cancellation still applies under the support condition. It separates the correctness of the probability estimate from the quality of the guide. For language models, learned estimates of future success can direct computation toward promising partial generations, as in twisted sequential Monte Carlo [ZBMG, ICML ’24]. Whether that saves computation depends on the guide, the cost of copying state, and the variance of the resulting weighted population.