# Hierarchical Refinement: Optimal Transport to Infinity and Beyond

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 88 references that are in the map.
- First posted on arXiv 4 Mar 2025.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Zero-Shot Text-to-Image Generation](https://mlsanity.com/paper/2102.12092/) (2021)
- [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)
- [Diffusion Schr"odinger Bridge with Applications to Score-Based Generative Modeling](https://mlsanity.com/paper/2106.01357/) (2021)
- [Learning Generative Models with Sinkhorn Divergences](https://mlsanity.com/paper/1706.00292/) (2017)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [How to train your neural ODE: the world of Jacobian and kinetic regularization](https://mlsanity.com/paper/2002.02798/) (2020)
- [Optimal transport mapping via input convex neural networks](https://mlsanity.com/paper/1908.10962/) (2019)
- [Geometric Transformer for Fast and Robust Point Cloud Registration](https://mlsanity.com/paper/2202.06688/) (2022)
- [A mathematical perspective on Transformers](https://mlsanity.com/paper/2312.10794/) (2023)
- [CoFiNet: Reliable Coarse-to-fine Correspondences for Robust Point Cloud Registration](https://mlsanity.com/paper/2110.14076/) (2021)
- [Sinkformers: Transformers with Doubly Stochastic Attention](https://mlsanity.com/paper/2110.11773/) (2021)
- [Neural Optimal Transport](https://mlsanity.com/paper/2201.12220/) (2022)
- [Unbalanced minibatch Optimal Transport; applications to Domain Adaptation](https://mlsanity.com/paper/2103.03606/) (2021)
- [Large-Scale Optimal Transport and Mapping Estimation](https://mlsanity.com/paper/1711.02283/) (2017)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark](https://mlsanity.com/paper/2106.01954/) (2021)
- [Proximal Optimal Transport Modeling of Population Dynamics](https://mlsanity.com/paper/2106.06345/) (2021)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [Learning with minibatch Wasserstein : asymptotic and gradient properties](https://mlsanity.com/paper/1910.04091/) (2019)
- [Optimal Flow Matching: Learning Straight Trajectories in Just One Step](https://mlsanity.com/paper/2403.13117/) (2024)
- [A Wasserstein-type distance in the space of Gaussian Mixture Models](https://mlsanity.com/paper/1907.05254/) (2019)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Minibatch optimal transport distances; analysis and applications](https://mlsanity.com/paper/2101.01792/) (2021)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Hierarchical Optimal Transport for Document Representation](https://mlsanity.com/paper/1906.10827/) (2019)
- [Schr"odinger Bridge Flow for Unpaired Data Translation](https://mlsanity.com/paper/2409.09347/) (2024)
- [Optimal transport for Gaussian mixture models](https://mlsanity.com/paper/1710.07876/) (2017)

## Built on by (most cited first, 9 of 9)

- [Efficient Transferable Optimal Transport via Min-Sliced Transport Plans](https://mlsanity.com/paper/2511.19741/) (2025)
- [STRAND: Sequence-Conditioned Transport for Single-Cell Perturbations](https://mlsanity.com/paper/2602.10156/) (2026)
- [Simplifying Optimal Transport through Schatten-p Regularization](https://mlsanity.com/paper/2510.11910/) (2025)
- [Forest-Guided Semantic Transport for Label-Supervised Manifold Alignment](https://mlsanity.com/paper/2602.00974/) (2026)
- [Transport Clustering: Solving Low-Rank Optimal Transport via Clustering](https://mlsanity.com/paper/2603.03578/) (2026)
- [A Biconvex Formulation for Stable Transport of Mixture Models with a Unique Solution](https://mlsanity.com/paper/2606.02515/) (2026)
- [Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions](https://mlsanity.com/paper/2609.13010/) (2026)
- [GenoMorph: Pathway-Grounded Genomic Disease Reasoning via Adaptive Latent Computation](https://mlsanity.com/paper/2609.34079/) (2026)
- [FlashSinkhorn 2: Block-Sparse Entropic Optimal Transport](https://mlsanity.com/paper/2610.02395/) (2026)

## Abstract (arXiv)

Optimal transport (OT) has enjoyed great success in machine learning as a principled way to align datasets via a least-cost correspondence, driven in large part by the runtime efficiency of the Sinkhorn algorithm (Cuturi, 2013). However, Sinkhorn has quadratic space and time complexity in the number of points, limiting scalability to larger datasets. Low-rank OT achieves linear complexity, but by definition, cannot compute a one-to-one correspondence between points. When the optimal transport problem is an assignment problem between datasets then an optimal mapping, known as the Monge map, is guaranteed to be a bijection. In this setting, we show that the factors of an optimal low-rank coupling co-cluster each point with its image under the Monge map. We leverage this invariant to derive an algorithm, Hierarchical Refinement (HiRef), that dynamically constructs a multiscale partition of each dataset using low-rank OT subproblems, culminating in the bijective Monge map. Hierarchical Refinement runs in log-linear time and linear space, retaining the advantages of low-rank OT while overcoming its limited resolution. We demonstrate the advantages of Hierarchical Refinement on several datasets, including ones containing over a million points, scaling full-rank OT to problems previously beyond Sinkhorn's reach.