Sampling-based model predictive control plans by simulating thousands of random candidate futures on a GPU, scoring them, and averaging the best into the next motor command. It re-solves this problem tens to hundreds of times per second. A GPU runs threads in lockstep groups of 32 called warps. When some candidate futures in a warp hit an obstacle, touch the ground, or cross onto slippery terrain, those threads run different code from their neighbours, and the hardware executes each branch one after another while the other threads wait. This slowdown is called warp divergence. It becomes worst in exactly the contact-rich, cluttered scenes where fast replanning matters most. A controller runs against a fixed deadline, so the relevant cost is not average throughput. It is the slowest control cycle, and how many useful samples fit before the deadline.
The proposal rests on one observation. A controller replans from a slightly shifted version of its previous plan, so the pattern of which samples hit which contact or collision mode at which time step changes little from one cycle to the next. We propose to record that pattern each cycle and use it to assign samples to warps in the next cycle, so that threads likely to share a mode share a warp. Threads whose rollout terminated early are refilled with fresh samples instead of idling. This reuses the sorting idea that removed divergence in batched special-function evaluation, but uses time coherence to remove most of the sorting cost, which that work found to be substantial. The goal is lower worst-case cycle latency and more effective samples per deadline on the same hardware.
Core Claim
Earlier GPU work on divergence either reorganises data once, ahead of time, or pays for a fresh sort on every call. Accurate Computation of the Logarithm of Modified Bessel Functions on GPUs groups inputs by which approximation branch they take and gets large net speedups, even though the sort adds 33% runtime. CUDASW++ sorts sequences by length before a database search. Both treat each batch as independent. A receding-horizon controller is not independent from cycle to cycle.
Our claim is that for sampling-based control in scenes with discontinuous events, a mode ordering predicted from the previous cycle recovers most of the lane utilisation that a fresh sort would give, at a small fraction of the cost. Combined with refilling lanes freed by early termination, this should lower 99th-percentile cycle latency. At a fixed deadline, it should raise the number of completed rollouts, and with it closed-loop task success, relative to both unsorted execution and fully branchless formulations. We also expect a crossover. When the code inside each branch is cheap, computing every branch with masks (branchless code) should win, and scheduling should matter only once branch bodies are expensive. Finding where that crossover sits is part of the contribution, not a caveat.
Research Program
The substrate is the kernel design of MPPI-Generic, a C++/CUDA library for Model Predictive Path Integral control (MPPI, the sampling controller described above). It offers split and fused dynamics-and-cost kernels, but it assigns samples to threads in fixed order, assumes all rollouts have the same length, and does no divergence handling. We keep its dynamics and cost structure and change three things.
First, the rollout horizon is cut into short segments of a few time steps. At each segment boundary, every thread writes a small mode tag: free flight or contact, collision or clear, and a terrain class. It also sets a flag if its rollout has terminated.
Second, the next cycle's thread-to-sample assignment is built from the previous cycle's tags. The tags are shifted by one control step to match the receding horizon. New samples are perturbations of the nominal plan, so each inherits the tag sequence of its nearest parent sample. A cheap warp-level vote at each segment boundary tests whether the prediction held. When a warp's mode agreement falls below a threshold, we fall back to a local compaction within the thread block rather than a global sort. This is the same family of warp-voting tools that Rapid GPU-Based Pangenome Graph Layout uses to merge divergent branches in stochastic gradient descent.
Third, lanes whose rollouts terminated are refilled with fresh samples drawn from the current proposal distribution. This is the rollout analogue of the precomputed reset cache that Accelerating Reinforcement Learning through GPU Atari Emulation uses to keep warps uniform when games end at different times. The difference is that we are bounded by a deadline rather than by throughput: refilled samples count only if they finish before the cycle deadline. The importance weights must be corrected for samples with unequal horizons. We will truncate cost-to-go consistently and verify that the resulting control update matches plain MPPI at convergence.
A simple cost model guides the analysis. Suppose the branches present in a warp have per-step costs $c_1,\dots,c_k$. An unsorted warp pays roughly $\sum_{j \in S} c_j$, where $S$ is the set of modes present among its threads. A mode-pure warp pays only its own $c_j$, because divergent paths are serialised. The expected benefit therefore grows with the number of modes that co-occur in a warp and with how expensive the rare branches are. This is why we expect branchless masking to win when all $c_j$ are small.
The analysis has three parts. We instrument active-lane fraction per instruction with the GPU profiler. We measure how accurate the time-coherence prediction is as a function of scene clutter and speed. We characterise the failure mode where coherence breaks, such as sudden obstacle appearance or impacts, and show that the fallback bounds worst-case cost.
Baselines
The naive reference point is MPPI-Generic's fused kernel run as-is, with fixed sample-to-thread assignment and every rollout integrated to full horizon. Dead lanes stay masked. It will run on the same scenes, sample counts, horizons and GPUs as our method, with the same dynamics and cost code compiled at the same optimisation level. Its reported clean-scene figure, 16,384 samples in 0.39 ms on an RTX 4090 in MPPI-Generic, is our sanity check. We must reproduce roughly that number in obstacle-free scenes before any divergent-scene comparison is meaningful. We found no reported result on Lacuna for MPPI latency or lane utilisation in contact-rich or collision-heavy divergent scenes, so the divergent-scene numbers for this baseline will be measured by us.
The strongest existing technique for this problem is per-call input sorting in the style of Plesner et al., transplanted to rollouts. Each cycle, it runs a short probe pass to classify samples by mode, globally sorts them, then runs the full rollout. It is the strongest competitor because it directly attacks divergence and has a documented large net benefit in another domain. It gets the same sort primitives, and its segment length and sort frequency are tuned with the same budget of configurations we give our own threshold and segment length. Beating it means matching its lane utilisation to within a few percent while having lower median and 99th-percentile cycle latency, because we avoid its sort cost.
The third baseline is fully branchless evaluation. Contact and collision responses are computed for every thread and blended with masks or smooth complementarity relaxations, in the spirit of the padding-and-mask approach in GPU Computation of the Euler Characteristic Curve for Imaging Data and the smooth-penalty choice in Differentiable Model Predictive Control on the GPU. To make it fair, it uses the same physical model with the smoothing parameter tuned for closed-loop success, not for speed alone.
A split-kernel baseline launches one kernel per mode after compaction, following the dual-kernel design in the Atari emulation work.
Two ablations isolate our key ingredient. One uses predicted ordering without lane refilling. The other uses refilling with no reordering. Beating the baselines overall means that, at a fixed control deadline, our method completes more rollouts and reaches higher closed-loop success than every other configuration, in the scenes where branch costs are uneven.
Why not just…?
Why not just make everything branchless? This is the most serious threat, and we treat it as a hypothesis to measure rather than to dismiss. Masked evaluation removes divergence by construction. SOLVING QUADRATIC PROGRAMMING PROBLEMS ON GRAPHICS PROCESSING UNIT chose interior-point methods over active-set methods for exactly this regularity. Branchless code, however, pays for every branch on every thread. When one branch is expensive, such as a small iterative contact solve or a detailed collision response, and rare, such as a few percent of samples in contact, that is wasteful. Smooth relaxations also change the physics. Differentiable Model Predictive Control on the GPU itself names its penalty-only constraint handling as a limitation. We will sweep the cost ratio between the contact branch and the free-flight branch, and the fraction of samples in contact. The prediction is a crossover: branchless wins at low cost ratios, and scheduling wins above them. If branchless wins everywhere we test, that is a publishable negative result, and we would report it as such.
Why not just launch more samples and absorb the divergence? The Atari emulation work shows that aggregate throughput can outweigh divergence. That paper also stresses that throughput is not latency. A controller has one plan to deliver per cycle. Launching more samples lengthens the cycle unless the extra samples fit inside idle lanes, which is exactly what refilling provides. Our experiments hold the deadline fixed and count completed samples, so this alternative is directly the unsorted baseline at larger sample counts.
Why not just sort each cycle? It works, as Plesner et al. show. But its overhead is a fixed tax on every cycle, and that tax is proportionally worst at the small sample counts used on embedded boards such as the Jetson Nano. If the coherence prediction is poor in fast-changing scenes, per-cycle sorting will win there. Our fallback degrades toward it, and we report the prediction-accuracy regime in which each approach is better.
Why not just run it on a CPU? At the sample counts that sampling MPC needs, MPPI-Generic reports that a CPU implementation (Nav2 MPPI) takes over 60 ms where the GPU takes 0.39 ms. This proposal is about making the GPU path hold its latency once scenes stop being uniform, so the CPU is not a real competitor here.
Proposed Experiments
We use three task families that each produce a different kind of divergence.
The first is manipulator MPPI in cluttered scenes. Obstacle geometry comes from MotionBenchMaker environments for the Panda and UR5, and colliding rollouts terminate early. This family tests refilling.
The second is a planar or 3D legged or hopping system with ground contact, where rollouts switch between flight and stance. This family tests mode ordering with an expensive stance branch.
The third is vehicle drifting across friction patches, modelled on the variable-friction puddle setting of the DiffMPC Supra experiments. This family tests terrain-class divergence with cheap branches, and we expect branchless evaluation to do well there.
All three run on an RTX 4090 and a Jetson Nano, matching MPPI-Generic's platforms. Sample counts sweep from about 1,000 to 16,384.
Metrics are median, 99th-percentile and maximum cycle latency; profiler-measured active-lane fraction; completed rollouts per fixed deadline; and closed-loop task success and cost over randomised episodes at fixed control rates.
Two checks are decisive. The first holds the deadline fixed at a realistic control period and asks whether our method's extra completed samples translate into higher closed-loop success than the Plesner-style sort and the branchless baseline. The second is a coherence-stress test that injects sudden obstacles, where the time-coherence prediction should fail. If our worst-case latency there exceeds that of the unsorted baseline, the fallback design is wrong and the claim does not hold.
References
- Accurate Computation of the Logarithm of Modified Bessel Functions on GPUs
- CUDASW++: optimizing Smith-Waterman sequence database searches for CUDA-enabled graphics processing units
- MPPI-Generic: A CUDA Library for Stochastic Optimization
- Rapid GPU-Based Pangenome Graph Layout
- Accelerating Reinforcement Learning through GPU Atari Emulation
- GPU Computation of the Euler Characteristic Curve for Imaging Data
- Differentiable Model Predictive Control on the GPU
- SOLVING QUADRATIC PROGRAMMING PROBLEMS ON GRAPHICS PROCESSING UNIT
- MotionBenchMaker: A Tool to Generate and Benchmark Motion Planning Datasets