# SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 38 references that are in the map.
- First posted on arXiv 28 Aug 2026.

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

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [A survey of the Schr"odinger problem and some of its connections with optimal transport](https://mlsanity.com/paper/1308.0215/) (2013)
- [Online normalizer calculation for softmax](https://mlsanity.com/paper/1805.02867/) (2018)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Distributional Sliced-Wasserstein and Applications to Generative Modeling](https://mlsanity.com/paper/2002.07367/) (2020)
- [Low-Rank Sinkhorn Factorization](https://mlsanity.com/paper/2103.04737/) (2021)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [Orthogonal Estimation of Wasserstein Distances](https://mlsanity.com/paper/1903.03784/) (2019)
- [Sparsity-Constrained Optimal Transport](https://mlsanity.com/paper/2209.15466/) (2022)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Low-rank Optimal Transport: Approximation, Statistics and Debiasing](https://mlsanity.com/paper/2205.12365/) (2022)
- [Subspace Detours: Building Transport Plans that are Optimal on Subspace Projections](https://mlsanity.com/paper/1905.10099/) (2019)
- [Expected Sliced Transport Plans](https://mlsanity.com/paper/2410.12176/) (2024)
- [Optimal Transport for Machine Learners](https://mlsanity.com/paper/2505.06589/) (2025)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [FlashSinkhorn: IO-Aware Entropic Optimal Transport on GPU](https://mlsanity.com/paper/2602.03067/) (2026)
- [Importance Sparsification for Sinkhorn Algorithm](https://mlsanity.com/paper/2306.06581/) (2023)
- [Approximating Optimal Transport via Low-rank and Sparse Factorization](https://mlsanity.com/paper/2111.06546/) (2021)
- [Entropic optimal transport beyond product reference couplings: the Gaussian case on Euclidean space](https://mlsanity.com/paper/2507.01709/) (2025)
- [Sliced-Regularized Optimal Transport](https://mlsanity.com/paper/2604.23944/) (2026)

## Abstract (arXiv)

Entropic optimal transport (EOT) has been shown to offer a computationally tractable approximation to exact optimal transport. However, the standard Sinkhorn-Knopp algorithm has two main limitations. First, given discrete measures with N points, each iteration requires O(N2) operations, which restricts its use on large-scale datasets (e.g. N≥104). Second, it uses the independent coupling as a reference measure for regularisation. This assigns mass to high-cost transport edges at moderate regularisation strengths. We propose SinkSLOT, which addresses both limitations by putting forth the expected sliced lifted transport plan as a natural way to sparsify the Gibbs kernel with a non-independent prior coupling. We prove that: 1) SinkSLOT converges; 2) with L slices, each resulting sparse Sinkhorn iteration costs O(LN); and 3) the resulting objective is a divergence requiring no debiasing. Experiments on synthetic benchmarks show that SinkSLOT delivers substantial speedups over state-of-the-art dense and sparse EOT methods. We also demonstrate the applicability of the proposed divergence in a gradient flow experiment. The code is publicly available at https://github.com/cai4cai/SinkSLOT.