Certified Parallel-in-Time Sinkhorn for Dynamic Entropic Optimal Transport
2026-07-27 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster ComputingMachine Learning
AI summaryⓘ
The authors present TemporalSinkhorn, a new way to speed up solving related entropic optimal transport problems by running Sinkhorn iterations in parallel over time rather than one after another. Their method safely batches potential future results and only accepts those guaranteed to be accurate, using checks and milestones to avoid mistakes. They show TemporalSinkhorn runs significantly faster on GPUs compared to traditional sequential methods, without losing accuracy. The work offers improvements for computational tasks in areas like optimal transport and Flow Matching, though broader testing remains for the future.
Entropic Optimal TransportSinkhorn AlgorithmParallel-in-Time ComputingFlow MatchingGPU AccelerationEntropic RegularizationOptimal TransportNumerical AlgorithmsParallel ComputingAlgorithmic Auditing
Authors
Xinyang Wen
Abstract
Dynamic applications, including optimal-transport Flow Matching, repeatedly solve related entropic optimal transport problems, yet conventional distributed Sinkhorn processes frames sequentially and synchronizes after every iteration. We present TemporalSinkhorn, a parallel-in-time executor that batches future candidates and their repairs without making output accuracy speculative. A centered, row-sharded certificate accepts only a deterministic safe prefix. The remaining candidates share packed Sinkhorn updates; an online projective forgetting rate places audit milestones, while a posteriori residual checks recover from every depth underestimate. Prediction can therefore change work placement but cannot authorize an inaccurate output. On 4 A100 GPUs, a 60-run, five-seed grid at n = 2048 shows that forgetting-guided milestones reduce wall time by 1.15x-1.47x relative to auditing every packed iteration in five statistically resolved regime cells. Against a sequential soft c-transform warm start, temporal execution is 1.42x-3.55x faster across six synthetic streams, with zero marginal-tolerance violations. On Flow Matching minibatch streams, temporal execution is 3.054x-3.632x faster than sequential carry at n = 2048, with no tolerance violations. A separate fixed-kernel test on an RTX 4060 Laptop GPU gives a 4.315x geometric-mean speedup. These are complementary deployment studies rather than a controlled hardware comparison. End-to-end Flow Matching integration, optimized-solver comparisons, and multi-node validation remain open.