Modern computing hardware is built for massive parallelism. GPUs and TPUs thrive when they can perform thousands of identical operations simultaneously. However, many of our most fundamental algorithms—from neural network inference and autoregressive sampling to Bayesian optimization and classical mathematical programming—are inherently sequential. They operate like a relay race: step $N+1$ cannot begin until step $N$ is finished.
This "sequential bottleneck" creates a hardware-algorithm mismatch. While a GPU might have thousands of cores, a serial algorithm leaves most of them idle, leading to low throughput and wasted energy. A growing body of research seeks to resolve this by reframing sequential dependencies as parallelizable systems, allowing us to trade redundant computation for significantly faster wall-clock times.
Reframing Sequences as Systems of Equations
The most direct way to break a sequential chain is to stop viewing it as a sequence and start viewing it as a system of equations. In a standard feedforward neural network or an autoregressive model, we typically compute activations layer-by-layer or token-by-token.
Yang Song, Chenlin Meng, and colleagues proposed a radical shift in Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving. They realized that the entire forward pass of a model can be written as a single system of nonlinear equations where all layer outputs are variables. Instead of solving this system step-by-step, they use parallel iterative solvers like the Jacobi method. By starting with an initial guess for all layers and refining them simultaneously, they can utilize the full power of a GPU to reach the same numerical result much faster than a serial pass.
Batching the Unbatchable: Bayesian Optimization
Bayesian Optimization (BO) is the gold standard for tuning expensive "black-box" functions, such as finding the best hyperparameters for a model or the right molecular structure for a drug. Traditionally, BO is a serial loop: evaluate a point, update the model, pick the next point. This is a major bottleneck when you have a cluster of 100 CPUs but the algorithm only gives you one task at a time.
To fix this, researchers have developed "Batch BO" methods that propose multiple points simultaneously. Javier González and Neil D. Lawrence introduced Local Penalization in Batch Bayesian Optimization via Local Penalization, which creates "exclusion zones" around already-selected points to ensure the batch is diverse.
Other approaches, like Parallel Predictive Entropy Search (PPES) by Amar Shah and Zoubin Ghahramani, optimize the entire batch at once to maximize information gain (Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions). By using the "reparameterization trick" for acquisition functions, as explored by James T. Wilson and Frank Hutter, these methods can use gradient-based optimization to find optimal batches, making parallel evaluation practical for high-stakes problems like COVID-19 therapeutic discovery (Pyzer-Knapp).
Matrix-Free and First-Order Solvers
In classical optimization (e.g., Linear Programming or Conic Programming), the bottleneck is often the "second-order" step—calculating a Hessian or factorizing a large matrix. These operations are difficult to parallelize across thousands of small GPU cores.
The trend is shifting toward matrix-free and first-order methods. These algorithms, such as the Primal-Dual Hybrid Gradient (PDHG) used by Fangzhao Zhang for network flow problems, replace expensive matrix factorizations with simple matrix-vector multiplications.
Similarly, Zhenwei Lin and Yinyu Ye developed PDCS, a solver that leverages GPU acceleration for massive conic programming problems (PDCS: A Primal-Dual Large-Scale Conic Programming Solver with GPU Enhancements). By avoiding the sequential nature of traditional second-order solvers, these "matrix-free" approaches can scale to problems with billions of variables that were previously considered intractable.
Structural Reparameterization
Sometimes, the sequential nature of an algorithm is baked into its mathematical representation. A classic example is the use of Householder reflections to maintain orthogonality in neural network weights. These reflections are applied one after another, creating a strict serial dependency.
In CWY Parametrization for Scalable Learning of Orthogonal and Stiefel Matrices, Valerii Likhosherstov and Jared Davis show how to use the Compact WY transform to turn these sequential reflections into a single, parallel-friendly matrix multiplication. This change doesn't alter the underlying math of orthogonality, but it changes the execution from serial to parallel, resulting in speedups of up to 1000x on GPUs and TPUs.
Why This Works: Hardware-Algorithm Alignment
The common thread across these papers is alignment. The goal is not just to make an algorithm "faster" in terms of operation count, but to make it "wider" so it fits the shape of modern hardware.
Whether it is Sören Laue redesigning L-BFGS-B to avoid sequential line searches (Optimization for Classical Machine Learning Problems on the GPU) or Kaidi Xu and Huan Zhang replacing CPU-bound LP solvers with parallel LiRPA for neural network verification (Fast and Complete), the intuition remains the same:
If you can't make the steps faster, do more of them at the same time. By reframing dependencies as simultaneous constraints, we unlock the latent power of the parallel processors that already sit on our desks.