Late-Data-Tolerant GPU MPC: Stream Horizon Stages Near-First and Patch the Factorization

Fast controllers for drones and legged robots increasingly solve their planning problem on a GPU. The planning problem is model predictive control (MPC): at every control tick, the robot optimizes its next $N$ moves subject to dynamics and obstacle constraints, then executes only the first move. GPU solvers for the core linear algebra are now very fast, but they quietly assume that the per-stage problem data are already sitting in GPU memory and ready when the solve starts. These data are the constraint and cost linearizations for each of the $N$ future time steps, derived from an obstacle map that perception updates continuously. On a real robot that data arrives late, and by variable amounts. It crosses a shared bus, competes with perception networks for memory bandwidth, or comes out of a linearization routine that runs long. A controller that waits for all of it inherits the worst-case arrival time as its loop latency.

We propose to change the order in which data moves and to tolerate data that arrives late, instead of only moving data faster. Stage data are streamed to the GPU nearest-future-first. The factorization starts immediately, using last tick's shifted data as placeholders for stages that have not yet arrived. When a fresh block arrives, the solver repairs only the part of the factorization that depends on it. At the control deadline it returns a solution, whatever has arrived. The bet is that the far-future stages, which are the ones most likely to be stale, are also the ones that matter least for the first command. If so, the hard deadline can be met with almost no loss in closed-loop quality.

Core Claim

Combine three things: a horizon-ordered asynchronous transfer schedule, previous-tick data as a fallback for late stage blocks, and incremental repair of a parallel block-tridiagonal factorization. The resulting MPC loop should have tail latency bounded by a chosen deadline rather than by worst-case data arrival. Its closed-loop cost and constraint violations should stay statistically indistinguishable from a solver that always waits for fully fresh data, and they should be clearly better than one that ignores new data altogether.

The repair step depends on structure from GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices. That work reorders the $N$ horizon stages by nested dissection, so they form an elimination tree of depth $\log_2 N$. Its Cholesky factorization (the standard way of solving a symmetric positive-definite linear system) runs in $O(\log_2(N)\, n^3)$ parallel time for block size $n$. In that tree, a change to one stage's block only changes the Schur complements on that stage's path to the root. A late block therefore costs roughly $\log_2 N$ block operations to absorb, not a full refactorization.

The proposal also rests on a claim about how sensitive the first command is to errors in later stages. For stabilizable systems, an error of size $\delta_k$ in the data of stage $k$ is expected to move the first control input by at most

$$\|\Delta u_0\| \le C \sum_{k=1}^{N} \rho^{k}\, \delta_k ,$$

where $0<\rho<1$ is a decay factor set by the conditioning of the stage-wise system and $C$ is a problem constant. The geometric form comes from the decay of coupling along a banded block-tridiagonal inverse. This is a hypothesis we will measure, not a result we cite. If it holds, near-first ordering puts the bus's limited time where it buys the most. That same intuition led Asynchronous Splitting Design for Model Predictive Control to give near-future stages higher update probability in its randomized solver.

Relation to Prior Work

Two lines of work motivate the gap. GPU MPC solvers make the compute side fast but treat data delivery as solved. The block-tridiagonal Cholesky solver above reports $25\times$–$40\times$ speedups over CPU BLASFEO, but it assumes all matrices are resident on the GPU. Differentiable Model Predictive Control on the GPU parallelizes across the horizon with conjugate gradients but does not address host-to-device streaming. Effective GPU Parallelization of Distributed and Localized Model Predictive Control shows that once the solve gets $50\times$ faster, precomputing the problem data becomes the bottleneck. That is exactly the stage data we propose to stream. The second line constrains the design. SOLVING QUADRATIC PROGRAMMING PROBLEMS ON GRAPHICS PROCESSING UNIT found that single small problems run slower on GPU than CPU because synchronous bus transfers dominate. Any GPU MPC scheme that does not hide or reorder transfers therefore has to beat a CPU first.

The method borrows from latency-hiding systems but changes what they assume. SwapNet double-buffers neural network blocks on Jetson devices at 6.2% average overhead, and FlashAttention-3 splits warps into producers and consumers to overlap memory copies with matrix math. Both treat every block as mandatory and wait for it. Our setting allows a block to be skipped in favor of a stale copy, and the transfer order is chosen by control relevance rather than by execution order.

The closest asynchronous-control work changes timing, not data movement. Asynchronous Computation of Tube-Based Model Predictive Control runs a fast 1.74 ms primary solve that reuses tubes computed by a slow background thread. It is CPU-only, linear time-invariant, and has no notion of partial data arrival within a single solve. SVR-AMA randomizes which stages get updated, but it runs sequentially on one core over fully available data. PAINT handles asynchronous action chunks for learned policies and enforces no constraints. To our knowledge, none of these schedules partial stage data by horizon index or repairs a parallel factorization when late data arrives.

Research Program

We will build on the open-source socu solver within a real-time-iteration-style loop: one quadratic program per tick, with linearizations taken around the shifted previous solution. Each tick has three stages. First, perception updates an egocentric occupancy ring buffer of the kind used by Usenko et al. and computes per-stage obstacle-constraint linearizations. Second, a copy-engine stream transfers stage blocks in horizon order into one of two slots per stage, each block stamped with an arrival time. Third, a compute stream factors the nested-dissection tree as soon as the first leaves arrive, filling missing leaves with shifted previous-tick blocks, and replays ancestor updates when a fresh block lands. At the deadline the solve finishes with whatever data it has.

The scheme makes "late" a first-class event wherever the delay comes from: bus contention, a slow linearization, or interference from perception kernels sharing the GPU. That generality matters for the threats discussed below.

The analysis has two parts. We will measure $\rho$ empirically by perturbing stage $k$'s data and recording $\Delta u_0$. We will also check whether the measured decay predicts the closed-loop cost gap across different deadline settings. We will not claim recursive feasibility for nonlinear dynamics. Feasibility under stale far-stage constraints will be measured instead, with a short-horizon safety backup. Full nonlinear guarantees are an open problem that we note but do not solve here.

Baselines

The naive reference is synchronous socu. It waits for every stage block, factors, and solves, using the same quadratic programs, the same GPU, and the same tick. This is the existing method deployed as intended, so its tail latency under contention is the quantity we aim to cut. Beating it means a lower 99.9th-percentile loop latency and deadline-miss rate, with closed-loop cost within its run-to-run noise.

The strongest compute-side competitor is socu with ordinary double-buffering. It overlaps next-tick transfers with the current solve, as in SwapNet or the multi-stream pattern of Evaluating the Performance Impact of Multiple Streams on the MIC-based Heterogeneous Platform, but it neither reorders stages nor tolerates late data. This is the obvious engineering fix, so the proposal must improve on it in the jitter regime specifically. We will give it the same stream count and buffer memory and tune its chunk size over the same grid.

The CPU competitor is a BLASFEO-based structured solver on the host. It avoids the bus entirely, and for small $n$ it is a genuine contender given Huang et al.'s small-problem result. We will run it on the same robot-class CPU with the same horizon. For reference, the cited GPU paper reports socu at $25\times$–$40\times$ faster than BLASFEO for factorization. No reported result was found on Lacuna for tail latency or deadline misses of any GPU MPC solver under transfer or perception contention, so these numbers will be ours.

We will also run "always stale," which solves with only the shifted previous-tick data. This is the lower bound on quality and shows that fresh data is worth something.

Two ablations isolate the key ingredients. The first keeps late-data tolerance but streams stages in natural or far-first order. If near-first ordering does not beat these, the decay hypothesis is wrong. The second keeps ordering and tolerance but refactors fully on each arrival instead of patching ancestors, which isolates the incremental repair. All variants share data, hardware, injected contention traces, and a fixed tuning budget per method.

Why not just…?

Why not just compute everything on the GPU so nothing has to transfer? This is the most serious threat. If perception, the ring buffer, and linearization all live on the GPU, bus transfers vanish. Lateness does not, because perception kernels and linearization still finish at variable times and still compete for streaming multiprocessors. We will run a fully GPU-resident configuration. If synchronous socu in that configuration already meets deadlines at the 99.9th percentile, the transfer-ordering contribution collapses. What would remain is the claim about tolerating late producers, and we will report it at that smaller size.

Why not just solve on the CPU with BLASFEO and skip the accelerator? Huang et al. show the CPU wins for small, isolated problems. Schwan et al. show the GPU pulling ahead by $25\times$–$40\times$ as the horizon grows. We will sweep $N$ and $n$ and report the crossover with and without our scheme. Shifting that crossover toward smaller problems counts as a result. If the CPU dominates at the problem sizes our tasks actually need, we will say so.

Why not just shorten the horizon or reduce the model? Online Dynamic Trajectory Optimization and Control for a Quadruped Robot reaches 18.34 ms per iteration with a two-step horizon but cannot react mid-swing. Time-Optimal Planning for Quadrotor Waypoint Flight reports about 0.7 m tracking error from simplified dynamics. We will include a short-horizon baseline tuned to meet the deadline synchronously, and compare closed-loop cost and obstacle clearance against our long-horizon, late-tolerant solver.

Why not just reuse last tick's solution as a warm start and ignore late data? That is the "always stale" baseline. The Astrobee results in Deep Learning Warm Starts for Trajectory Optimization on the International Space Station show that poor initializations can cost more iterations than a cold start. That is a warning that stale data can hurt once the environment shifts, and our moving-obstacle scenarios are designed to expose exactly this case.

Proposed Experiments

The main testbed is quadrotor obstacle flight in Flightmare Forest and Warehouse scenes, using its point-cloud interface to feed an egocentric ring buffer. Horizons will range over $N\in\{20,60,120,250\}$, with 250 being roughly where socu's logarithmic scaling saturates on an RTX 3080. We will add moving obstacles to the scenes, since stale far-stage constraints are most likely to matter there.

A second testbed uses AirSim Drone Racing Lab tracks. There, a MobileNet-style gate detector runs concurrently on the same GPU and creates realistic contention. As a sanity check where the true optimum is known, we will rerun the linear system from the asynchronous tube-MPC paper, which reports closed-loop costs of 67.36 asynchronous, 85.92 offline, and 59.07 for full online solves. This checks that our solver reaches the full-fresh cost when nothing is late.

Hardware covers two settings: a desktop RTX 3080 behind PCIe, and a Jetson-class unified-memory board on which a SwapNet-style workload is co-scheduled to create bandwidth contention. Contention traces are recorded once and replayed identically for every method.

We will report the 50th, 99th, and 99.9th percentile loop latency, deadline-miss rate, closed-loop cost relative to an offline full-fresh oracle, constraint-violation rate, collision rate, and the measured decay curve of $\Delta u_0$ against stage index.

Three checks are decisive. First, under contention, the full method must reach the double-buffered baseline's closed-loop cost within noise while cutting its 99.9th-percentile latency to the deadline. Second, near-first ordering must beat natural and far-first ordering, and by an amount that the measured $\rho$ predicts. Third, incremental repair must be measurably cheaper than full refactorization once more than a few blocks arrive late.

If the first check fails in the GPU-resident configuration, the bus-level story is wrong. If the second fails, the control-relevance argument is wrong. Either outcome is informative.