Robots that plan with model predictive control (MPC) re-solve a trajectory optimization problem every few milliseconds: predict the next $N$ time steps, pick controls that minimize a cost, apply the first one, and repeat. Almost all of the solver's time goes into one linear-algebra step. It factors a block tridiagonal matrix, which is a matrix whose only nonzeros are small $n\times n$ blocks on and next to the diagonal, one block per time step. This step is sequential by nature, because step $k$ depends on step $k-1$. Recent GPU work breaks that chain by reordering the time steps into a balanced tree of depth $\log_2 N$. It reports large speedups, but the logarithmic scaling only holds until the GPU runs out of processors, around $N=250$ on an RTX 3080. Past that point runtime grows linearly again (GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices).
We propose that, past this point, the right target is the time it takes to stream the matrix through memory once, not more parallelism. For the block sizes robots actually use ($n$ roughly 6 to 40), each block step does only about $n$ floating-point operations per byte it touches. On GPUs with fast double precision, that ratio makes the kernel limited by memory bandwidth rather than arithmetic. A full tree-structured elimination wastes this bandwidth. Every tree level is a global synchronization plus a round-trip of fill-in blocks through off-chip memory, and once processors are saturated those extra levels buy no parallelism. The fix borrows the two-level tiling idea from long-sequence attention kernels. Cut the horizon into chunks, eliminate each chunk sequentially inside one thread block's on-chip memory, and apply tree elimination only to the small system that couples the chunks. The chunk length is chosen by a bandwidth-and-synchronization cost model so that the solver tracks the memory-bandwidth floor at every horizon length.
Core Claim
For block tridiagonal KKT systems with $N$ well beyond the processor-saturation horizon, a chunked factorization brings runtime within a small constant of the off-chip bandwidth floor. The KKT system is the linear system of optimality conditions that the solver factors at each iteration. The chunked factorization eliminates contiguous runs of $L$ time steps in on-chip shared memory and applies nested dissection only to the $N/L$ separator blocks. Full nested dissection stays a constant factor above that floor. The bandwidth floor is
$$ T_{\text{floor}} = \frac{B(N,n)}{\beta}, \qquad B(N,n) \approx 4 N n^2 w, $$
where $\beta$ is the device's sustained memory bandwidth and $w$ is bytes per scalar. $B$ counts reading the diagonal and off-diagonal blocks and writing their factors once.
The per-step arithmetic intensity follows from roughly $2.3n^3$ flops for one block Cholesky, triangular solve, and Schur update, divided by about $4n^2 w$ bytes. That gives about $0.6\,n/w$ flops per byte. For $n=12$ this is well below the machine balance of data-center GPUs in either precision, which is why we expect the memory-bound regime. The same estimate predicts compute-bound behavior in double precision on consumer GPUs, where FP64 throughput is throttled. We treat this as a falsifiable prediction, not an assumption.
The modeled cost of the chunked scheme is
$$ T(L) \approx \max\!\Big(\tfrac{B}{\beta},\ \tfrac{F_{\text{chunk}}}{\pi}\Big) + \big(1+\log_2 \tfrac{N}{L}\big)\, t_{\text{sync}} + T_{\text{sep}}(N/L, n), $$
where $\pi$ is peak arithmetic throughput, $F_{\text{chunk}}$ is the chunk-phase flop count, $t_{\text{sync}}$ is the cost of one grid-wide synchronization with its global-memory exchange, and $T_{\text{sep}}$ is the cost of the separator system. We pick $L$ to minimize $T(L)$ subject to the chunk fitting in shared memory.
What is new is the claim about where the horizon-scaling ceiling comes from: it is mostly avoidable memory traffic and synchronization, not lack of parallelism. A second contribution is a solver whose chunk length is chosen from that diagnosis rather than hand-tuned.
Relation to Prior Work
The method's starting point is GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices. That paper permutes block tridiagonal systems by nested dissection into a tree of depth $\log_2 N$. It fuses kernels in shared memory for small blocks, pads blocks to match 128-bit memory alignment, and reports more than 2× over cuDSS and 25–40× over BLASFEO. That paper also shows the gap we target: past saturation it still runs every tree level. We keep its separator elimination and alignment padding, and replace the lower tree levels with sequential in-SRAM chunks.
The chunking idea comes from Tiled Flash Linear Attention. That work adds a second level of tiling inside each sequence chunk so that recurrent intermediate states never round-trip through high-bandwidth memory, and the change makes it faster than Mamba 2. A linear recurrence over a sequence and a Riccati-like elimination over a horizon have the same shape. As far as the file shows, nobody has carried the transfer through.
Two papers motivate attention to memory traffic and also constrain the design. Effective GPU Parallelization of Distributed and Localized MPC found that naive GPU offloading wastes its gains on data movement, while fused, locality-aware kernels halved runtime. Solving QP Problems on GPU found that shared-memory tiling gave 5× over global-memory code. It also found that GPUs lose to CPUs on QPs under 100 variables. That second finding obliges us to keep a CPU fallback at short horizons.
Can Tensor Cores Benefit Memory-Bound Kernels? (No!) is a constraint. It shows Tensor Core speedups on memory-bound FP64 kernels are capped at 1.33× and are often erased by the cost of reshaping data into the fixed matrix tiles those units require. We therefore target ordinary CUDA cores and test Tensor Cores only as an ablation.
Differentiable MPC on the GPU takes a different route around the sequential chain. It uses preconditioned conjugate gradient, an iterative solver whose every iteration touches all time steps in parallel, and reports 4–7× over trajax. That approach is a competitor rather than a component, because each of its iterations is itself a pass over memory.
Research Program
The first deliverable is a measurement study. Using the open socu (GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices) implementation, we profile factorization and solve across $N\in[16, 8192]$, $n\in\{6, 12, 24, 40\}$, single and double precision, on a consumer GPU and a data-center GPU. For each tree level we record achieved DRAM bandwidth, achieved flops, and synchronization stalls. The question is whether time past saturation tracks bytes, flops, or the number of levels. If it tracks flops, the premise fails on that device, and the note's claim is restricted to the regimes where traffic dominates.
The second deliverable is the chunked kernel. Each thread block loads $L$ consecutive diagonal and off-diagonal blocks into shared memory. It runs sequential block Cholesky over the chunk interior, holding the boundary block as a separator, and writes only the factors and a reduced coupling block. The separator system has $N/L$ blocks and is again block tridiagonal. It is factored by nested dissection, in one block if small or across the grid if large. Under a symmetric permutation this is an exact Cholesky of the same SPD matrix, so no accuracy is traded away. Triangular solves follow the same two-level structure. Where the device supports it, the phases run in a single persistent cooperative kernel to remove launch latency, which matters at sub-millisecond budgets.
The third deliverable is the dispatcher. It fits the cost model above from a few microbenchmarks per device: sustained $\beta$, $t_{\text{sync}}$, and chunk throughput. It then chooses among sequential CPU Riccati, full nested dissection, and chunked elimination with a specific $L$. We validate the model by how often its choice is within 10% of an exhaustive search over $L$.
The fourth deliverable is integration. We place the factorization inside an interior-point solver for nonlinear MPC and measure the share of the control-cycle deadline it consumes. We run this both for single long-horizon problems and for batches of independent problems. Batching saturates the GPU at small $N$, so it is the regime where bandwidth matters most.
Baselines
The naive reference is sequential block Cholesky, equivalent to a Riccati recursion, run in BLASFEO on a high-end multicore CPU with its best SIMD settings. This is what deployed MPC solvers use today. For batched problems we give it one instance per core, and we report runtime against $N$.
The strongest existing method is socu's nested-dissection solver, run on the same GPU, matrices, precision, and alignment padding. Schwan et al. report it at more than 2× over cuDSS and 25–40× over BLASFEO, with saturation near $N=250$ on an RTX 3080. The file gives no absolute runtimes, so we will re-measure them ourselves. Beating it means at least 1.5× lower factorization-plus-solve time for $N\ge 4\times$ the measured saturation horizon, no worse than 5% below saturation, and identical residuals to working precision. We also run cuDSS, because the vendor library is the default choice a practitioner would reach for.
The iterative competitor is DiffMPC's preconditioned conjugate gradient, run in JAX on the same GPU. It is compared at matched relative residual ($10^{-8}$ in double precision) rather than matched iteration count, and its tolerance is tuned with the same tuning budget we give our chunk length.
Three ablations isolate the key ingredient. The first is full nested dissection with our fused kernels, which separates the effect of the chunking from kernel engineering. The second is chunked elimination with chunks staged through global memory instead of shared memory, which isolates the on-chip residency. The third is a Tensor Core variant of the chunk update, which tests whether the reshaping cost reported by Zhang et al. also appears for MPC-sized blocks.
Why not just…?
Why not just stop nested dissection a few levels early in socu? This is close to our method, and we say so plainly. The difference is that the stopped levels must then be eliminated sequentially in on-chip memory with a single global write. Truncating the tree while still exchanging through DRAM gains little under our hypothesis. The global-memory-staged ablation measures exactly this. If that ablation matches the full method, the contribution shrinks to choosing the truncation depth, and we would report it that way.
Why not just use BLASFEO on a CPU? At short horizons and for single small problems, it should win, consistent with the small-problem finding of Huang et al. and DiffMPC's observation that Riccati is faster on CPU. That is why the dispatcher keeps a CPU path. For long horizons, Schwan et al. already report socu 25–40× ahead of BLASFEO, so the CPU is not the main threat in our target regime. Our experiments report the crossover horizon for each device.
Why not just use the conjugate-gradient solver from DiffMPC? Each iteration streams the whole system, so its cost is roughly the iteration count times a bandwidth floor. A direct method pays about one floor in total. With a strong preconditioner and a loose tolerance, PCG could still win for very long horizons. This is a real threat, and the matched-residual comparison settles it. We will also report the tolerance at which the two methods cross.
Why not just shorten the horizon or use a reduced-order model? Reduced models do reach real time on CPUs, for example 18.34 ms per iteration for ANYmal (Online Dynamic Trajectory Optimization and Control for a Quadruped Robot). That planner, however, is limited to two-step horizons and cannot re-plan mid-swing. Time-optimal quadrotor planning needs long, full-dynamics horizons and currently takes 40–65 minutes offline (Time-Optimal Planning for Quadrotor Waypoint Flight). Our work targets the regime where shortening the horizon is not an option. It does not argue that every controller needs one.
Proposed Experiments
The core benchmark is socu's synthetic block tridiagonal suite, extended to $N$ up to 8192. We add KKT matrices exported from two structured problems. The first is a time-optimal quadrotor problem in the multiple-shooting formulation with complementary progress constraints, which allows waypoint passing times to slide along the trajectory; it has long $N$ and $n\approx 17$. The second is a quadruped centroidal model at $n\approx 12$–24. Metrics are factorization and solve time, achieved DRAM bandwidth as a fraction of $\beta$, ratio to $T_{\text{floor}}$, residual norm, and, in the integrated solver, the fraction of a 10 ms and a 1 ms control deadline consumed.
The first decisive check is a scaling plot of time against $N$ past saturation. Our hypothesis predicts that chunked elimination's slope matches $T_{\text{floor}}$ within about 1.3× on data-center GPUs, while nested dissection's slope sits a constant factor higher. It also predicts the gap narrows or vanishes for consumer-GPU double precision, where the kernel is compute-bound. Observing the gap there would contradict our bandwidth explanation.
The second check is the dispatcher's selection accuracy across all $(N, n, \text{precision}, \text{device})$ cells.
The third check is batched solving. Using $B$ instances of $N=64$, we test whether chunking within instances still helps once batching alone saturates the GPU. This is the setting where bandwidth, not parallelism, should dominate from the start.
References
- GPU-Accelerated Cholesky Factorization of Block Tridiagonal Matrices
- Tiled Flash Linear Attention: More Efficient Linear RNN and xLSTM Kernels
- Effective GPU Parallelization of Distributed and Localized Model Predictive Control
- SOLVING QUADRATIC PROGRAMMING PROBLEMS ON GRAPHICS PROCESSING UNIT
- Can Tensor Cores Benefit Memory-Bound Kernels? (NO!)
- Differentiable Model Predictive Control on the GPU
- Online Dynamic Trajectory Optimization and Control for a Quadruped Robot
- Time-optimal planning for quadrotor waypoint flight