# Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions

arXiv: https://arxiv.org/abs/2609.13010 · HTML: https://mlsanity.com/paper/2609.13010/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 51 references that are in the map.
- First posted on arXiv 11 Sep 2026.

## Builds on (most cited first, 30 of 30)

- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improving and generalizing flow-based generative models with minibatch optimal transport](https://mlsanity.com/paper/2302.00482/) (2023)
- [Mean Flows for One-step Generative Modeling](https://mlsanity.com/paper/2505.13447/) (2025)
- [Optimal Transport for Domain Adaptation](https://mlsanity.com/paper/1507.00504/) (2015)
- [Reconstruction vs. Generation: Taming Optimization Dilemma in Latent Diffusion Models](https://mlsanity.com/paper/2501.01423/) (2025)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Optimal Flow Matching: Learning Straight Trajectories in Just One Step](https://mlsanity.com/paper/2403.13117/) (2024)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Multiscale Strategies for Computing Optimal Transport](https://mlsanity.com/paper/1708.02469/) (2017)
- [A Sparse Multi-Scale Algorithm for Dense Optimal Transport](https://mlsanity.com/paper/1510.05466/) (2015)
- [Flow Matching with Semidiscrete Couplings](https://mlsanity.com/paper/2509.25519/) (2025)
- [Optimal Transport for Machine Learners](https://mlsanity.com/paper/2505.06589/) (2025)
- [Hierarchical Refinement: Optimal Transport to Infinity and Beyond](https://mlsanity.com/paper/2503.03025/) (2025)
- [Low-Rank Optimal Transport through Factor Relaxation with Latent Coupling](https://mlsanity.com/paper/2411.10555/) (2024)
- [AlignFlow: Improving Flow-based Generative Models with Semi-Discrete Optimal Transport](https://mlsanity.com/paper/2510.15038/) (2025)
- [A Truncated Newton Method for Optimal Transport](https://mlsanity.com/paper/2504.02067/) (2025)
- [cuPDLPx: A Further Enhanced GPU-Based First-Order Solver for Linear Programming](https://mlsanity.com/paper/2507.14051/) (2025)
- [Genetic column generation: Fast computation of high-dimensional multi-marginal optimal transport problems](https://mlsanity.com/paper/2103.12624/) (2021)
- [HPR-LP: An implementation of an HPR method for solving linear programming](https://mlsanity.com/paper/2408.12179/) (2024)
- [An Interior-Point-Inspired algorithm for Linear Programs arising in Discrete Optimal Transport](https://mlsanity.com/paper/2206.11009/) (2022)
- [Convergence proof for the GenCol algorithm in the case of two-marginal optimal transport](https://mlsanity.com/paper/2303.07137/) (2023)

## Abstract (arXiv)

Optimal transport (OT) compares distributions and aligns datasets in machine learning, yet unregularized discrete OT requires a linear program with quadratically many transport variables. We propose HELLO, a hierarchical solver that casts large-scale discrete OT as edge localization and uses dual potentials to guide both coarse-to-fine initialization and within-level refinement. Initialization propagates coarse dual potentials across a recursive subsampling hierarchy to assign candidate edges. Refinement then iteratively inserts the largest dual violators in each row and column until the relative KKT residual meets a prescribed tolerance, while budgeted pruning ensures linear memory complexity. For exact-arithmetic refinement, we prove finite termination at a global optimum under a symbolic lexicographic rule. At the million-point scale, HELLO attains lower transport objectives with order-of-magnitude runtime improvements over strong baselines across feature dimensions from single digits to thousands. It further scales to 1.28 million samples per marginal in 8192 dimensions on a single H100, using 41.6 GiB peak GPU memory while satisfying a full relative KKT residual below 10-6. Beyond standard discrete OT, the framework supports general pairwise costs and serves as a scalable balanced-OT oracle for semi-discrete OT, Gromov--Wasserstein, unbalanced OT, and OT-based Flow Matching.