Turning Crashed Rollouts into Extra Samples: Split-and-Refill Sampling Control on GPUs

Sampling-based controllers steer robots by simulating thousands of random futures in parallel on a GPU and averaging the controls that led to good outcomes. One example is Model Predictive Path Integral control (MPPI), which re-plans every 20 ms by rolling out many perturbed control sequences and weighting each one by the exponential of its negative cost. In cluttered, strongly nonlinear environments, such as a quadrotor threading a forest, most of those futures crash early. A crashed rollout gets a huge penalty and, as a result, almost zero weight. Its GPU thread nonetheless keeps integrating dynamics to the end of the planning horizon. The result is a controller that pays for thousands of samples and learns from a few dozen.

Database engines met the same shape of problem long ago under the name "data skew": a few heavy partitions decide total runtime while other workers sit idle. Their answer is to detect the heavy work at runtime, split it, and hand the pieces to idle workers. We propose to carry that answer over to sampling control. Rollouts that crash are stopped at fixed checkpoints. The GPU slots they free are refilled by cloning the surviving trajectory prefixes, and each clone continues with fresh noise. Weights are corrected so that the MPPI control update estimates exactly the same quantity as before. The aim is a larger effective sample size within the same wall-clock budget, and fewer failures in the narrow, non-convex settings where MPPI breaks down.

Core Claim

Plain MPPI does not actually suffer from a runtime straggler problem. Every thread runs the same fixed horizon, so threads finish together. The waste is in sample quality, not idle time. The skew appears only once crashed rollouts are allowed to terminate. At that point the right response is not merely to rebalance threads. It is to put the freed capacity into the part of trajectory space that is still alive.

Our claim is that weight-corrected splitting of surviving prefixes, run as a warp-level compaction-and-refill step at a few horizon checkpoints, beats three alternatives in failure rate and in effective samples per millisecond. The first is masking dead threads. The second is respawning fresh rollouts from the start. The third is simply raising the sample count to fill the same budget.

The correctness argument comes from the classical splitting estimator. Suppose a prefix alive at checkpoint $k$ is replaced by $m_i$ children, where $m_i$ may depend on the prefix's partial cost. If each child carries weight $w_i/\mathbb{E}[m_i]$, with $w_i$ the parent's current weight, then

$$ \hat u = \frac{\sum_j \tilde w_j\, e^{-S_j/\lambda}\, \delta u_j}{\sum_j \tilde w_j\, e^{-S_j/\lambda}} $$

is the same self-normalized estimator MPPI uses. In that expression $S_j$ is the total rollout cost, $\lambda$ is the MPPI temperature, $\delta u_j$ is the sampled control perturbation, and $\tilde w_j$ is the accumulated splitting weight.

Nonlinearity is the reason this matters. Under linear-Gaussian dynamics, the good region of control space could be found analytically. Under nonlinear dynamics with discontinuous crash costs, it can only be found by sampling, and splitting concentrates the samples where they still count.

Research Program

The splitting idea is taken from the skew-mitigation literature:

All three split work to finish the same answer faster. We instead split work to get a better answer in the same time, which requires the weight correction above and has no analogue in a join.

The GPU mechanism is adapted from Themis. Themis separates idle threads inside a 32-thread warp from idle warps across the chip. It redistributes work through multi-buffered parallel redistribution and reports an average intra-warp idle ratio of 1% on the JCC-H skewed benchmark. We reuse its idle-ratio metric and its redistribution-buffer idea, but apply them to trajectory prefixes rather than to query evaluation trees.

The kernel will run rollouts in segments. At checkpoints, for example $N/4$, $N/2$ and $3N/4$, a warp-cooperative compaction gathers live rollouts and writes cloned prefixes into the freed slots. Clone counts are allocated in proportion to $e^{-S_{0:k}/\lambda}$, which is the systematic-resampling rule familiar from particle filters. Before the main study we will settle two design questions. The first is how many checkpoints to use, since each one costs a barrier and a memory pass. The second is whether to split in proportion to partial-cost weight or uniformly over survivors. Uniform splitting is lower-variance but less targeted.

The analysis part of the work is a variance decomposition. It will show when splitting helps, which is when the crash fraction is high and survivors' futures are diverse. It will also show when splitting hurts, which is when clones stay too correlated because the remaining horizon is short.

The setting is MPPI as described in Model Predictive Path Integral Control: From Theory to Parallel Computation. That paper samples fixed-horizon rollouts on a GPU with a hand-tuned exploration variance and says nothing about wasted samples or thread divergence.

We deliberately leave the other gaps in the file aside:

In both cases the skew is in solver iterations rather than in samples. Neither offers the same direct trade of idle compute for estimator quality.

Baselines

Standard MPPI. The naive reference is MPPI exactly as in Model Predictive Path Integral Control: From Theory to Parallel Computation: fixed-horizon rollouts, crashes handled by a penalty, no early termination. It shares our GPU, dynamics code, horizon, temperature and per-step time budget. Its sample count is set to the largest value that fits that budget. On the forest task that paper reports completion times of about 15.2 s (MPPI) against about 17.5 s (MPC-DDP) at 3 m obstacle spacing. We will reproduce that setting before comparing.

Masked early termination. Crashed threads stop computing and their warp lanes idle. This isolates the pure systems cost of skew, measured as intra-warp idle ratio, with no gain in samples.

Compaction-and-refill without splitting. This ablation is the most important. It uses the same Themis-style redistribution, but refills freed slots with fresh rollouts from time zero. It isolates whether the benefit comes from rebalancing alone or from cloning live prefixes.

CCSMPPI. The strongest existing method on the failure-rate question is Constrained Covariance Steering Based Tube-MPPI, which adds a covariance-steering safety layer to MPPI. On its high-noise circular track it reports failure probability 1.0 for standard MPPI, 0.87 for Tube-MPPI and 0.13 for CCSMPPI. We will run it on its own double-integrator tasks under the same noise and budget.

Shared protocol. Every method gets the same hyperparameter-search budget over temperature and exploration variance. Beating a baseline means one of two things. On the cluttered tasks, lower failure rate or completion time with overlapping-interval-free confidence over seeds. On the double integrator, a failure probability at or below 0.13, reached without CCSMPPI's linear safety layer. We also report effective sample size per millisecond. No reported effective-sample-size result was found on Lacuna for any MPPI variant, so we will measure it for all methods.

Why not just…?

Why not just pad crashed rollouts and buy more samples, since GPUs are cheap? This is the default, and at low crash rates it may well be enough. Our standard-MPPI baseline is exactly this, tuned to fill the budget. The reason to doubt it is that adding fresh samples increases survivors only in proportion to the survival rate. When survival is a few percent, as in dense forests or the narrow track where standard MPPI fails with probability 1.0 per CCSMPPI, the extra samples mostly crash too. The forest-density sweep tests this directly. If the gap does not grow as obstacles get denser, the idea is wrong.

Why not just refill freed slots with fresh rollouts, i.e., plain work-stealing? This is a genuine threat, because it captures all of the systems benefit Themis demonstrates. It is our main ablation. Fresh rollouts restart from time zero and face the same early-crash odds. Clones start past the obstacles their parent already survived. If fresh refill matches splitting, then the contribution reduces to known load balancing, and we will report that outcome.

Why not just shape the sampling distribution better, with adaptive variance, cross-entropy updates, or a safety filter? Better proposals and splitting are complementary rather than competing. Cross-entropy-style refinement, as in ABC-LMPC, improves the proposal across iterations. Splitting improves the use of compute within one iteration. We will therefore also run splitting on top of CCSMPPI. CCSMPPI's covariance steering is linear and its tubes can be conservative, so splitting may help where the safety layer leaves little feasible room.

Why not just use a scalar-tube robust MPC and skip sampling? Köhler et al.'s nonlinear robust MPC runs only 4.5x slower than nominal MPC by shrinking robustness to one tube-size state. However, its uniform constraint tightening is worst-case. In narrow corridors that tightening is likely to make the problem infeasible. We will include it on the 3 m forest to check whether that happens.

Proposed Experiments

The primary benchmark is the quadrotor forest at 3, 4 and 5 m spacing from the MPPI paper, simulated in Flightmare, whose physics runs at over 200,000 steps per second. We add cart-pole swing-up as a low-crash control case, where splitting should give little benefit. The CCSMPPI circular-track and obstacle-field tasks serve for the failure-probability comparison.

For each task we report:

  • failure rate and completion time over at least 50 seeds;
  • effective sample size per control step;
  • intra-warp idle ratio in the style of Themis;
  • the time overhead of each checkpoint.

The decisive check is a curve of effective sample size against crash fraction. Splitting should beat fresh-refill by a margin that grows with crash fraction, and should match it when crashes are rare. A second check confirms that the weight correction matters. We run splitting without correction and expect a measurable bias in $\hat u$ against a high-sample reference, together with worse closed-loop failure rates. If both checks come out as predicted, the database idea of splitting heavy work becomes a principled sampling method for nonlinear control, not just a speedup.